akhauriyash/Code-Regression huggingface dataset:
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
use proconio::input;
//use proconio::marker::Usize1;
use proconio::marker::Chars;
//use std::collections::HashSet;
// use std::cmp::*;

const M: u64 = 1000_000_007;

fn main() {
    input! {
        k:u64,
        s:Chars
    }
    let n = s.len();
    // 最後の文字以降におく文字数をiとすると、
    // 文字のえらび方は、25.pow(k-i)*26.pow(i)
    // また、n-1 文字の挿入位置は (k-i+n-1 choose n-1)
    // n choose k = n*(n-1)*...*(n-k+1) /(k*...*1) なので、
    // あとは、各iについて、合計すればよい。
    let mut fact = vec![1u64; 2000010];
    let mut inv_fact = vec![1u64; 2000010];
    fact[0] = 1;
    for i in 0..2000005 {
        fact[i + 1] = fact[i] * ((i + 1) as u64) % M;
        inv_fact[i] = modInv(fact[i]);
    }
    let choose = |n, k| fact[n as usize] * inv_fact[n - k] % M * inv_fact[k] % M;
    let mut ans = 0u64;
    for i in 0..k + 1 {
        ans += choose(n + (k as usize) - (i as usize) - 1, n - 1) * modPow(25u64, k - i as u64) % M
            * modPow(26u64, i as u64)
            % M;
    }
    println!("{}", ans % M);
}
//fn choose(n: usize, k: usize, fact: &Vec<u64>, inv_fact: &Vec<u64>) -> u64 {
//    fact[n as usize] * inv_fact[n - k] % M * inv_fact[k] % M
//}
fn modPow(x: u64, a: u64) -> u64 {
    if a == 0 {
        1
    } else {
        if a == 1 {
            x
        } else {
            if a % 2 != 0 {
                (modPow(x, a - 1) * x) % M
            } else {
                let t = modPow(x, a / 2);
                t * t % M
            }
        }
    }
}
fn modInv(x: u64) -> u64 {
    modPow(x, M - 2)
}


Measured memory_bytes: 38108
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using pint = pair<int,int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

int main() {
    int n;cin>>n;
    vector<int> d(n);
    rep(i,n) cin>>d[i];
    sort(d.begin(),d.end());

    cout<<d[d.size()/2]-d[d.size()/2-1]<<endl; 
}

Measured memory_bytes: 640
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    s = list(input()[:-1])
    if s[2] == s[3] and s[4] == s[5]:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,x;
  cin >> N >> x;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  int ans=0;
  for(int i=0;i<N;i++){
    if(a.at(i)<=x){
      if(i==N-1){
        if(x==a.at(i)){
          ans++;
          break;
        }
      }else{
        ans++;
        x-=a.at(i);
      }
    }else{
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3640
def check_s(s,list):
    for i in range(len(s)):
        if not s[i] in list:
            return False

    return True


S = input()
#print(S)
l = len(S)
#print(l)
sub_S = ''
list = ['A','C','G','T']

max_len = 0

for k in range(l+1):
    for i in range(l+1-k):
        sub_S = S[i:i+k]
        #print(sub_S)
        if check_s(sub_S,list):
            if len(sub_S) > max_len:
                max_len = len(sub_S)

print(max_len)

Measured memory_bytes: 3064
// すぬけ君の塗り絵2イージー
#include <iostream>
#include <algorithm>
using namespace std;

int W,H,N;
int x,y,a;

int main(){
    cin>>W>>H>>N;
    int max_x=W,min_x=0,max_y=H,min_y=0;
    for(int i=0;i<N;i++){
        cin>>x>>y>>a;
        if(a==1){
            min_x=max(min_x,x);
        }if(a==2){
            max_x=min(max_x,x);
        }if(a==3){
            min_y=max(min_y,y);
        }if(a==4){
            max_y=min(max_y,y);
        }
    }
    cout<<(max(max_x-min_x,0)*max(max_y-min_y,0))<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define copy(x, y) memcpy(y, x, sizeof(mat))

typedef long long ll;
typedef int mat[3][3], (*pmat)[3];
typedef const int (*cpmat)[3];
const int N = 100054, mod = 1000000007;
const mat AC = {{1, 0, 1}, {1, 1, 1}, {1, 2, 2}}, RJ = {{1, 0, 0}, {1, 1, 0}, {1, 2, 1}};

int n, L;
int x[N];
mat ans = {{1, 0, 0}, {1, 0, 0}, {1, 0, 0}};

inline void __builtin_matmul(cpmat a, cpmat b, pmat ret) {
	#define MUL(i, j) ret[i][j] = ((ll)a[i][0] * b[0][j] + (ll)a[i][1] * b[1][j] + (ll)a[i][2] * b[2][j]) % mod
	#define MUL_ROW(i) MUL(i, 0), MUL(i, 1), MUL(i, 2)
	MUL_ROW(0), MUL_ROW(1), MUL_ROW(2);
}

inline void matmul(cpmat a, cpmat b, pmat ret) {mat tmp; __builtin_matmul(a, b, tmp), copy(tmp, ret);}

void matPowerMod(cpmat a, ll n, pmat c) {mat tmp; for (copy(a, tmp); n; n >>= 1, matmul(tmp, tmp, tmp)) if (n & 1) matmul(tmp, c, c);}

int main() {
	int i;
	scanf("%d%d", &L, &n);
	for (i = 1; i <= n; ++i) scanf("%d", x + i);
	L -= x[n] + 1;
	for (i = n; i; --i) x[i] -= x[i - 1] + 1;
	for (i = 1; i <= n; ++i) matPowerMod(AC, x[i], ans), matmul(RJ, ans, ans);
	matPowerMod(AC, L, ans), printf("%d\n", ans[2][0]);
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;

int main() {
	int N, sum;
  	cin >> N;
  	sum = 0;
  for(int i = 0; i < N; i++) {
  	int a, b;
    cin >> a >> b;
    sum += b - a + 1;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;
long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
int main(){
    int N;cin >> N;
    const int MAXN = 101;
    int W[MAXN];
    int a = 0;int b = 0;
    rep(i,N){
        cin >> W[i];
        a += W[i];
    }   
    
    int ans = a;
    rep(i,N){
        a -= W[i];
        b += W[i];
        ans = min(ans,abs(a-b));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584
<?php

fscanf(STDIN, "%s", $s);
$n = strlen($s);

$ans = array_fill(0, $n, 0);
// R
$cnt = 0;
for ($i = 0; $i < $n; ++$i) {
    if ($s[$i] === 'R') {
        ++$cnt;
    } else {
        // iはL
        $ans[$i - 1] += ceil($cnt / 2);
        $ans[$i] += floor($cnt / 2);
        $cnt = 0;
    }
}

// L
$cnt = 0;
for ($i = $n - 1; $i >= 0; --$i) {
    if ($s[$i] === 'L') {
        ++$cnt;
    } else {
        $ans[$i + 1] += ceil($cnt / 2);
        $ans[$i] += floor($cnt / 2);
        $cnt = 0;
    }
}
/* print_r($ans); */

echo implode(' ', $ans);


Measured memory_bytes: 35576
n = gets.chomp.chars
s = n.size
k = gets.to_i

ans = 0
(0..s-1).to_a.combination(k) do |arr|
    if arr[0] == 0
        if k != 1 && (arr[1] == 1 || n[1..arr[1]-1].all?{|e| e=="0"})
            if k != 2 && (arr[2] == arr[1]+1 || n[arr[1]+1..arr[2]-1].all?{|e| e=="0"})
                if n[arr[1]] == "0"
                    ans += (n[0].to_i-1) * 9 ** 2
                else
                    ans += (n[0].to_i-1) * 9 ** 2 + (n[arr[1]].to_i-1) * 9 + n[arr[2]].to_i
                end
            else
                ans += (n[0].to_i-1) * 9 ** (k-1) + n[arr[1]].to_i * 9 ** (k-2)
            end
        else
            ans += n[0].to_i * 9 ** (k-1)
        end
    else
        ans += 9 ** k
    end
end

puts ans

Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>

#define ll long long

using namespace std;

int main() {
	int N, Z, W;
	cin >> N >> Z >> W;
	vector<int> ax(N + 1), ay(N + 1);
	ax[0] = W;
	ay[0] = Z;
	for (int i = 1; i <= N; i++) {
		int a;
		cin >> a;
		ax[i] = a;
		ay[i] = a;
	}
	vector<int> x(N + 1), y(N + 1);
	x[N] = abs(ax[N] - ax[N - 1]);
	y[N] = abs(ay[N] - ay[N - 1]);
	for (int i = N - 1; i > 0; i--) {
		x[i] = abs(ax[i - 1] - ax[N]);
		for (int j = i + 1; j <= N; j++) x[i] = max(x[i], y[j]);
		y[i] = abs(ay[i - 1] - ay[N]);
		for (int j = i + 1; j <= N; j++) y[i] = min(y[i], x[j]);
	}
	cout << x[1] << endl;
	system("pause");
	return 0;
}

Measured memory_bytes: 504
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=9;i++){
    for(int j=1;j<=9;j++){
      if(i*j==n){
        cout<<"Yes\n";
        return 0;
      }
    }
  }
  cout<<"No\n";
  return 0;
}


Measured memory_bytes: 256
from heapq import heappush, heappop
N, M = map(int, input().split())
dic = {i:[] for i in range(1,N+1)}
ans = [0]*M
for i in range(M):
  p, y = map(int, input().split())
  heappush(dic[p], (y,i))

for k in dic.keys():
  count = 1
  p = str(k)
  while len(p)<6:
    p = '0'+p
  while dic[k]:
    y, i = heappop(dic[k])
    a = str(count)
    while len(a)<6:
      a = '0'+a
    ans[i] = p+a
    count += 1
for a in ans:
  print(a)


Measured memory_bytes: 38236
#include <bits/stdc++.h>
using namespace std;

int main() {
	long long int a,b,k;
	cin>>a>>b>>k;
	if(a>=k)
		cout<<a-k<<" "<<b<<endl;
	else {
		k=k-a;
		cout<<0<<" "<<max((long long int)0,b-k)<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int A[5];

typedef long long ll;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s[0]=='A')A[0]++;
        if(s[0]=='M')A[1]++;
        if(s[0]=='R')A[2]++;
        if(s[0]=='C')A[3]++;
        if(s[0]=='H')A[4]++;
    }
    ll ans=0;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<4;j++){
            for(int k=j+1;k<5;k++)
                ans+=1LL*A[i]*A[j]*A[k];
        }
    }
    cout<<ans;


}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int main(){
	while(true){
		int n;
		float m=0;
		cin>>n;
		if(n==0)
			break;
		int N[n];
		for(int i=0;i<n;i++){
			cin>>N[i];
			m+=N[i];
		}
		m=m/n;
		float a=0;
		for(int i=0;i<n;i++){
			a+=(N[i]-m)*(N[i]-m);
		}
		a = a/n;
		a = sqrt(a);
		printf("%.8lf\n", a);
	}
	
	return 0;
} 


Measured memory_bytes: 3152
#include <stdio.h>
int main(void)
{
	int a,b,ans;
	scanf("%d%d",&a,&b);
	ans=(a+b)/2;
	if((a+b)%2==0){
	    printf("%d",ans);
	    return 0;
	}
	else{
	    printf("%d",ans+1);
	    return 0;
	}

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define rep(i,n) for(int i = 0; i < n; i++)
 
int main() {
  int N,M;
  cin >> N >> M;
  vector<int> a(N);
  ll s = 0;
  int cnt = 0;
  rep(i,N) {
    cin >> a[i];
    s += a[i];
  }
  rep(i,N) {
    if (4*a[i]*M >= s) cnt++;
  }
  if (cnt >= M) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
int n;

bool onmp(int x,int y){return x>=0&&y>=0&&x<n&&y<n;}

bool check(const vector<string> &A){
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)if(A[i][j]=='#')return 0;
  return 1;
}

int count(int x,int y,const vector<string> &A){
  int res=0;  
  for(int i=-1;i<=1;i++)
    for(int j=-1;j<=1;j++){
      int nx = x+i,ny = y+j;
      if((i||j)&&onmp(nx,ny))res += A[ny][nx]!='.';
    }
  return res;
}

vector<string> mkmp(const vector<string> &A){
  vector<string> res=A;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
      int cnt = count(j,i,A);
      if(A[i][j]=='#')res[i][j]=(cnt==2||cnt==3)? '#':'.';
      if(A[i][j]=='.')res[i][j]=(cnt==3)? '#':'.';
      if(A[i][j]=='@')res[i][j]='@';
    }
  return res;
}


void getPos(vector<string>&A,int &x,int &y){
  for(int i=0;i<n&&x==-1;i++)
    for(int j=0;j<n&&x==-1;j++) if(A[i][j]=='@')x=j,y=i;
}



int bfs(vector<string>start){
  queue<vector<string> > Q;
  map<vector<string>,int>D;
  Q.push(start);
  D[start]=0;

  while(!Q.empty()){
    vector<string> A=Q.front();Q.pop();
    int cost = D[A];
    int x = -1,y=-1;
    getPos(A,x,y);
    if(check(A))return cost;
    if(cost>=10)continue;

    A[y][x] = '.';
    for(int dy=-1;dy<=1;dy++)
      for(int dx=-1;dx<=1;dx++){
	int nx = x+dx,ny = y+dy;
	if((!dx&&!dy)||!onmp(nx,ny)||A[ny][nx]=='#')continue;
	A[ny][nx] = '@';
	vector<string> nA = mkmp(A);
	if(!D.count(nA))Q.push(nA),D[nA] = cost+1;
	A[ny][nx] = '.';
      }
  }
  return -1;
}

int main(){
  while(cin>>n,n){
    vector<string> mp(n);
    for(int i=0;i<n;i++)cin>>mp[i];
    cout<<bfs(mp)<<endl;
  }
  return 0;
}

Measured memory_bytes: 13504
n, m = map(int, input().split(' '))
a = set()
for i in range(m):
    a.add(int(input()))


s = [0] * (n + 1)
s[0] = 1
for i in range(n):
    j = i + 1
    while(j <= min(n, i + 2)):
        if j not in a:
            s[j] += s[i]
            s[j] = int(s[j] % 1000000007)
        j += 1

print(s[n])


Measured memory_bytes: 11884
#include <bits/stdc++.h>
using namespace std;



int main() {
    int n, k;
    cin >> n >> k;
    double ans = 0.0;
    for (int i = 1; i <= n; ++i) {
        long long now = i, cnt = 0;
        while (now < k) now <<= 1, ++cnt;
        ans += 1.0 / (double) (1LL << cnt);
    }
    ans /= (double) n;
    printf("%.10f\n", ans);
    return 0;
}


Measured memory_bytes: 256
# https://beta.atcoder.jp/contests/arc096/submissions/2706219
N, C = map(int, input().split())
X, V = zip(*(map(int, input().split()) for _ in range(N)))
R = [0] * (N + 1)
Rans = [0] * (N + 1)
for i in range(N):
    R[i + 1] = R[i] + V[i]
    Rans[i + 1] = max(Rans[i], R[i + 1] - X[i])

L = [0] * (N + 1)
Lans = [0] * (N + 1)
for i in range(N, 0, -1):
    L[i - 1] = L[i] + V[i - 1]
    Lans[i - 1] = max(Lans[i], L[i - 1] - (C - X[i - 1]))

ans_1 = max(Rans[N], Lans[0])
# 初め時計回りで、折り返す
ans_2 = max(Lans[i + 1] + R[i + 1] - 2 * X[i] for i in range(N))
ans_3 = max(Rans[i - 1] + L[i - 1] - 2 * (C - X[i - 1])
            for i in range(N, 0, -1))
print(max(ans_1, ans_2, ans_3))

Measured memory_bytes: 59184
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def f(x):
    res = 0
    while(((x+1)%4)!=0):
        res ^= x
        x-=1

    return res
def main():
    A,B=MI()
    print(f(B)^f(A-1))

if __name__ == '__main__':
    main()

Measured memory_bytes: 64492
#include <iostream>
#include <string.h>

using namespace std;

int main() {
	int N;
	string S;
	string tmp1, tmp2;

	cin >> N >> S;

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (S[i] == ')') cnt--;
		if (S[i] == '(') cnt++;
		if (cnt < 0) { tmp1 += '('; cnt++; }
	}
	for (int i = 0; i < cnt; i++) tmp2 += ')';
	cout << tmp1 << S << tmp2 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  if (a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 3588
#!/usr/bin/env python3
import bisect

def main():
    N = int(input())

    # 7 1
    # 5 1
    # 3 1
    # 75 2^k - 2
    # 73 2^k - 2
    # 53 2^k - 2
    # 753 3^k - 3(2^k - 2) - 3

    digits = len(str(N))
    r = 0
    for k in range(3, digits):
        r += (3 ** k - 3 * (2 ** k - 2) - 3)

    vt = [7, 5, 3]
    for k in range(1, digits):
        nvt = []
        for v in vt:
            nvt.append(v * 10 + 7)
            nvt.append(v * 10 + 5)
            nvt.append(v * 10 + 3)
        vt = nvt

    vt.sort()
    m = bisect.bisect_right(vt, N)
    for i in range(m):
        s = str(vt[i])
        if '7' in s and '5' in s and '3' in s:
            r += 1

    print(r)


if __name__ == '__main__':
    main()



Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;

int Exp(long long int exp_n,long long int exp_e, long long exp_mod);


int main(){
  long long int N,M,O;
  cin >> N >> M;
  long long int R[N];
  
  for(long long int i=0;i<N;i++){
    R[i]=Exp(i+1,1000000005,1000000007);
  }
  
  
  long long int C=1;
  long long int L;
  
  
  
  long long int Dic = 0;
  long long int Inc = 0;
  
  int check;
  if(N%2==1){
    Dic++;
    check=0;
  }else{
    Inc++;
    check=1;
  }
  
  
  for(long long int i=0;i<N;i++){
    C = C*(N-i);
    
    if(C>1000000007){
      C=C%1000000007;
    }
   
    C = C*(M-N+i+1);
    if(C>1000000007){
      C=C%1000000007;
    }
  
    C = C*R[i];
    if(C>1000000007){
      C=C%1000000007;
    }
    
//    cout << C << ":" << check << endl;
    
    if(check==0){
      Inc = Inc + C;
      if(Inc>1000000007){
        Inc=Inc%1000000007;
      }
      check = 1;
    }else{
      Dic = Dic + C;
      if(Dic>1000000007){
        Dic=Dic%1000000007;
      }
      check = 0;
    }
    
    if(i==N-1){
      L = C;
    }
  }
  
  //cout << Inc <<endl;
  //cout << Dic <<endl;
  
  O = (Inc-Dic);
  while(O<0){
    O = O + 1000000007;
  }
  O = O*L;
  if(O>1000000007){
    O=O%1000000007;
  }
  
  
  cout << O;
  
  return 0;
}


int Exp(long long int exp_n,long long int exp_e, long long int exp_mod){
  long long int exp_o = 1;
  long long int exp_x=exp_n;
  long long int exp_tmp;
  
  while(0<exp_e){
    exp_tmp = exp_e/2;
    if(exp_e - exp_tmp*2 == 1){
      exp_o = exp_o*exp_x;
      if(exp_o>exp_mod){
        exp_o=exp_o%exp_mod;
      }
    }
    
    exp_x = exp_x*exp_x;
    if(exp_x>exp_mod){
      exp_x=exp_x%exp_mod;
    }
    exp_e = exp_tmp;
  }
  return exp_o;
}


Measured memory_bytes: 7344
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  int ans=0;
  int buff=0;
  for(int i=0; i<3; i++){
    buff = n%10;
    n = n/10;
    if(buff == 1){
      buff = 9; 
    }else{
      buff = 1;
    }
    ans += buff*pow(10,i);
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define mod 1000000007
#define P pair<int,int>
using namespace std;
int x[4];
signed main(){
	int a,su=0,sum=0;
	f(i,6){
		cin>>a;
		x[a-1]++;
	}
	f(i,4){
		if(x[i]==1) su++;
		else if(x[i]==2) sum++;
	}
	if(su==2&&sum==2)puts("YES");
	else puts("NO");
	return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

H,W,M = map(int, input().split())
BH = [0 for i in range(H)]
BW = [0 for i in range(W)]
Bomb = set()
for _ in range(M):
  h,w = map(int, input().split())
  h,w = h-1,w-1
  BH[h] += 1
  BW[w] += 1
  Bomb.add((h,w))
  
BHMAX = max(BH)
BWMAX = max(BW)
HS = set()
WS = set()
for i in range(H):
  if BH[i] == BHMAX:
    HS.add(i)
for i in range(W):
  if BW[i] == BWMAX:
    WS.add(i)
    
ans = 0
cnt = 0
for h,w in Bomb:
  if h in HS and w in WS:
    ans = max(ans, BHMAX + BWMAX - 1)
    cnt += 1

if cnt < len(HS) * len(WS):
  ans = BHMAX + BWMAX
print(ans)

Measured memory_bytes: 213764
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    sort(h.begin(), h.end(), greater<int>());

    int ans = 1000000000;
    for (int i = 0; i < n - k + 1; i++) {
        if (h[i] - h[i + k - 1] < ans) {
            ans = h[i] - h[i + k - 1];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<int> pre,in,post;
int n,pos;

void solve(int l,int r){
    if(l>=r)return;
    int root=pre[pos++];
    int m=distance(in.begin(),find(in.begin(),in.end(),root));
    solve(l,m);
    solve(m+1,r);
    post.push_back(root);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=0;i<n;i++){
        int k;
        cin >> k;
        pre.push_back(k);
    }
    for(int i=0;i<n;i++){
        int k;
        cin >> k;
        in.push_back(k);
    }
    solve(0,pre.size());
    for(int i=0;i<n;i++){
        if(i)cout << " ";
        cout << post[i];
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
    string s;
    cin >> s;

    cout << s.at(0) + to_string(s.size() - 2)  + s.at(s.size() -1) << endl;
    return 0;
}


Measured memory_bytes: 3684
use input::{Input, ReadMode};

fn main() {
    let mut input = Input::new(ReadMode::Line);

    let k: u32 = input.parse();
    let a: u32 = input.parse();
    let b: u32 = input.parse();

    if a % k == 0 || a / k * k + k <= b {
        println!("OK");
    } else {
        println!("NG");
    }
}

#[allow(dead_code)]
pub mod input {
    use std::io::{BufRead, Read};
    use std::str::{FromStr, SplitAsciiWhitespace};

    pub enum ReadMode {
        Full,
        Line,
    }

    pub struct Input<'a> {
        lock: std::io::StdinLock<'static>,
        iter: Option<SplitAsciiWhitespace<'a>>,
        mode: ReadMode,
    }

    impl<'a> Input<'a> {
        fn naive_read(&mut self) -> Option<SplitAsciiWhitespace<'a>> {
            let mut s = Box::leak(Box::new(String::new()));
            let res = match self.mode {
                ReadMode::Full => self.lock.read_to_string(&mut s),
                ReadMode::Line => self.lock.read_line(&mut s),
            };
            res.ok().expect("failed to read");
            Some(s.split_ascii_whitespace())
        }
        pub fn new(mode: ReadMode) -> Self {
            let lock = Box::leak(Box::new(std::io::stdin())).lock();
            let iter = None;
            Self { lock, iter, mode }
        }
        pub fn read_line(&mut self) -> String {
            let mut s = String::new();
            self.lock.read_line(&mut s).ok().expect("failed to read");
            s
        }
        pub fn parse<T: FromStr>(&mut self) -> T {
            match &mut self.iter {
                Some(iter) => {
                    let x = match iter.next() {
                        Some(x) => x,
                        None => {
                            self.iter = self.naive_read();
                            self.iter.as_mut().unwrap().next().expect("reached EOF")
                        }
                    };
                    x.parse().ok().expect("failed to parse")
                }
                None => {
                    self.iter = self.naive_read();
                    self.parse()
                }
            }
        }
    }
}


Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int W,H,C;
	cin >> W >> H >> C;
	int limit = min(W,H);
	for(int i=limit;i>=1;i--)
		if(W%i==0&&H%i==0)
		{
			cout<<C*W/i*H/i<<endl;
			break;
		}
}

Measured memory_bytes: 3088
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<queue>
#include<set>
#include<stack>
#include<map>

using namespace std;

int main(){
    int N;
    vector<int> G[100000];
    cin>>N;
    for(int i=0;i<N-1;i++){
        int a,b;
        cin>>a>>b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int color[100000]={};//0は色なし，1は黒色，2は白色
    color[0]=1; color[N-1]=2;
    int size=2;//色の塗られた領域の大きさ
    int black=1;
    int white=1;
    queue<int> Fen; Fen.push(0);
    queue<int> Sun; Sun.push(N-1);
    while(size<N){
        int bsz=Fen.size();
        for(int i=0;i<bsz;i++){
            int v=Fen.front(); Fen.pop();
            for(int j=0;j<G[v].size();j++){
                int u=G[v][j];
                if(color[u]==0){
                    color[u]=1;
                    black++; size++;
                    Fen.push(u);
                }
            }
        }
        int wsz=Sun.size();
        for(int i=0;i<wsz;i++){
            int v=Sun.front(); Sun.pop();
            for(int j=0;j<G[v].size();j++){
                int u=G[v][j];
                if(color[u]==0){
                    color[u]=2;
                    white++; size++;
                    Sun.push(u);
                }
            }
        }
    }
    if(black>white){
        cout<<"Fennec"<<endl;
    }else{
        cout<<"Snuke"<<endl;
    }
    return 0;
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 65;

int l, r;
int dp[N][2][2][2];

int solve(int idx, bool equal_L, bool equal_R, bool start){
   if(idx < 0){
      return start == 1;
   }

   int &ans = dp[idx][equal_L][equal_R][start];
   if(~ans)
      return ans;

   ans = 0;

   int miy = 0, mxy = 1, mix = 0, mxx = 1;

   bool nf1 = equal_R, nf2 = equal_L;
   int bit_R = (r & (1LL << idx)) > 0;

   if(nf1 == 0);
   else{
      mxy = (bit_R);
   }

   bool bit_L = (l & (1LL << idx)) > 0;
   if(nf2 == 0);
   else{
      mix = (bit_L);
   }

   for (int i = miy; i <= mxy; ++i)
   {
      for (int j = mix; j <= mxx; ++j)
      {
         if(j > i)
            continue;
         bool tnf1 = nf1, tnf2 = nf2;
         if(nf1 == 1 and i < bit_R){
            tnf1 = 0;
         }
         if(nf2 == 1 and j > bit_L){
            tnf2 = 0;
         }
         if(start == 0){
            if(i == 1 and j == 0)
               continue;
            if(i == 0 and j == 1)
               continue;
         }
         bool nstart = start;
         nstart |= (i > 0 && j > 0);
         ans += solve(idx-1, tnf2, tnf1, nstart);
         ans %= mod;
      }
   }

   return ans;
}

int32_t main(){_

   cin >> l >> r;
   memset(dp, -1, sizeof dp);

   cout<<solve(63, 1, 1, 0);

   return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define N 100000

typedef struct FIFO{
  char name[100];
  int time;
} Q;


void add(Q);
Q get();
int change(int,int);

Q IN[N];
int head,tail,count;


int main(){

  int i,n,record,alltime=0;
  Q h;

  scanf("%d %d",&count,&n);
  for(i=1;i<=count;i++){
    scanf("%s %d",IN[i].name,&IN[i].time);
  }
  head=1;
  tail=count+1;
  
  while(head!=tail){
    h = get();
    record = change(n,h.time);
    h.time -= record;
    alltime += record;
    if(h.time>0) add(h);
    else {
      printf("%s %d\n",h.name,alltime);
    }
  }
  return 0;
}

void add(Q x){
  IN[tail] = x;
  tail = (tail +1)%N;
}

Q get(){
  Q x = IN[head];
  head = (head + 1)%N;
  return x;
}

int change(int a,int b){
  if(a<b) return a;
  else return b;
}



Measured memory_bytes: 11872
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int E, Y;
    const int p[5] = {1868, 1912, 1926, 1989, 2017};
    const char q[4] = {'M', 'T', 'S', 'H'};
    cin >> E >> Y;
    if (E == 0) {
        for (int i = 0; i < 4; i++) {
            if (p[i] <= Y && Y < p[i+1]) {
                cout << q[i] << Y - p[i] + 1 << endl;
                break;
            }
        }
    } else {
        cout << p[E-1] + Y - 1 << endl;
    }        
    return 0;
}

Measured memory_bytes: 3116
#include <stdio.h>

int main(void)
{
    char b[1200];
    int i;
 
    fgets(b, sizeof(b), stdin);

	for (i = 0; b[i] != '\0'; i++){
		if ('A' <= b[i] && b[i] <= 'Z'){
			printf("%c", b[i] + 0x20);
		}
		else if ('a' <= b[i] && b[i] <= 'z'){
			printf("%c", b[i] - 0x20);
		}
		else {
			printf("%c", b[i]);
		}
	}
	
	return (0);
}




Measured memory_bytes: 2040
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<tgmath.h>
using namespace std;

#define lld long long

int main(){
    lld n,m;
    cin >> n >> m;
    cout << n*(n-1)/2 + m*(m-1)/2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> Num(N, -1);
	bool hasAns = true;
	for (int i = 0; i < M; i++) {
		int s, c;
		cin >> s >> c;
		if (Num[s - 1] >= 0 && Num[s - 1] != c) hasAns = false;
		if (N>1 && s == 1 && c == 0) hasAns = false;
		else Num[s - 1] = c;
	}
	if (!hasAns) {
		cout << -1 << endl;
		return 0;
	}
	int ans = 0;
	if (Num[0] == -1) {
		if (N > 1) Num[0] = 1;
		else Num[0] = 0;
	}
	for (int i = 0; i < N; i++) {
		ans *= 10;
		if (Num[i] > 0) ans += Num[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import static java.lang.System.*;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		int x, y;
		int A[] = { 1, 3, 5, 7, 8, 10, 12 };
		int B[] = { 4, 6, 9, 11 };
		String Xans, Yans;
		Xans = "";
		Yans = "";
		x = sc.nextInt();
		y = sc.nextInt();

		for (int i = 0; i < A.length; i++) {
			if (x == A[i])
				Xans = "A";
			if (y == A[i])
				Yans = "A";
		}
		for (int i = 0; i < B.length; i++) {
			if (x == B[i])
				Xans = "B";
			if (y == B[i])
				Yans = "B";
		}
		if (x == 2)
			Xans = "C";
		if (y == 2)
			Yans = "C";

		if (Xans.equals(Yans))
			out.println("Yes");
		else {
			out.println("No");
		}
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int h,w;
    cin>>h>>w;
    char c[h+2][w+2];
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>c[i][j];
          
        }
    }
    for(int i=0;i<h+2;i++)
    {
        for(int j=0;j<w+2;j++)
        {
            //cout<<c[i][j];
           if(i==0||i==h+1)
            cout<<"#";
            
            else if(j==0||j==w+1)
            cout<<"#";
            
            else
            cout<<c[i][j];
            
            
        }
        cout<<"\n";
            }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll A,B;
    cin >>A>>B;
    if(A%2==1 && B%2==1){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }



    return 0;
    

}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  
  string ans;
  for( int i = 0; i < s.size(); i++ ){
    if( (i + 1) % 2 == 1 ){
      ans.push_back(s.at(i));
    }
  }
  cout << ans << endl;
      
}

Measured memory_bytes: 512
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

class WeightUnionFindTree
    attr_accessor:par,:rank,:weight
    def initialize(n)
        @par=Array.new(n){|i| i}
        @rank=array(n,0)
        @weight=array(n,0)
    end

    def find(x)
        return x if @par[x]==x
        y=find(@par[x])
        @weight[x]+=@weight[@par[x]]
        @par[x]=y
        return y
    end

    def union(x,y,w)
        rx=find(x)
        ry=find(y)
        if @rank[rx]<@rank[ry]
            @par[rx]=ry
            @weight[rx]=w-@weight[x]+@weight[y]
        else
            @par[ry]=rx
            @weight[ry]=-w-@weight[y]+@weight[x]
            @rank[rx]+=1 if @rank[rx]==@rank[ry]
        end
    end

    def same?(x,y)
        return find(x)==find(y)
    end

    def diff(x,y)
        return @weight[x]-@weight[y]
    end
end

N,M=get_i
wuft=WeightUnionFindTree.new(N)
flag=true
M.times do|i|
    l,r,d=get_i
    l-=1
    r-=1
    if wuft.same?(l,r) and wuft.diff(l,r)!=d
      flag=false
      break
    end
        wuft.union(l,r,d)
end
puts yn_judge(flag)

Measured memory_bytes: 6140
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.close();
        System.out.println(getBaseMinus2Number(N));

    }

    private static String getBaseMinus2Number(int n) {
        if(n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        int a = 0;
        int b = n < 0 ? 1 : 0;
        int c = 0;
        int i = 0;
        while(true){
            c = (int) Math.pow(-2, i * 2 + b);
            a += c;
            if(Math.abs(n) <= Math.abs(a)){
                int len = i * 2 + b + 1;
                sb.append(1);
                if(len > 1){
                    String s = getBaseMinus2Number(n - c);
                    for(int j = 0; j < len - s.length() -1; j++) sb.append(0);
                    sb.append(s);
                }
                break;
            }
            i++;
        }
        return sb.toString();
    }

}


Measured memory_bytes: 22740
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


int main(){
    int N;
    cin >> N;
    //char in[120];
    pair<pair<string,int>,int> p[110];

    for(int i=0;i<N;i++){
        int level;
        string name;
        cin >> name >> level;
        p[i]=make_pair(make_pair(name,-level),i);
    }

    sort(p,p+N);

    for(int j=0; j<N; j++){
        cout << p[j].second+1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<queue>
#include<cstdio>

#define	mp	make_pair

using namespace std;

typedef	pair<int,int>	pii;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int main(){
	for(int w,h;scanf("%d%d",&w,&h),w;){
		static char land[50][51];
		static bool visited[50][50];
		for(int i=0;i<h;i++){
			scanf("%s",land[i]);
			for(int j=0;j<w;j++)	visited[i][j]=false;
		}

		int bcnt=0,wcnt=0;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++){
			if(land[i][j]!='.' || visited[i][j])	continue;
			visited[i][j]=true;
			int cnt=1;
			bool blk=false,wht=false;
			queue<pii> qu;	qu.push(mp(i,j));
			while(!qu.empty()){
				pii a=qu.front();	qu.pop();
				int x=a.second,y=a.first;
				for(int k=0;k<4;k++){
					int xx=x+dx[k],yy=y+dy[k];
					if(0<=xx && xx<w && 0<=yy && yy<h && !visited[yy][xx]){
						if(land[yy][xx]=='B'){ blk=true; continue; }
						if(land[yy][xx]=='W'){ wht=true; continue; }
						if(land[yy][xx]=='.'){
							qu.push(mp(yy,xx));
							visited[yy][xx]=true;
							cnt++;
						}
					}
				}
			}
			if(blk && !wht)	bcnt+=cnt;
			if(wht && !blk)	wcnt+=cnt;
		}

		printf("%d %d\n",bcnt,wcnt);
	}

	return 0;
}

Measured memory_bytes: 0
#import<iostream>
#import<set>
using namespace std;int C[10],n,k,j;set<int>V;int S(int b){int i,c,v;k--;for(i=n;i--;(c=C[i])?k?C[i]=0,S(v),C[i]=c:(V.insert(v),0):0)v=b*(C[i]>9?100:10)+C[i];k++;}main(){for(;cin>>n>>k,n;S(0),cout<<V.size()<<endl,V.clear())for(j=n;j--;)cin>>C[j];}

Measured memory_bytes: 0
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

template<class T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

int main() {
	int w, h, c, d;
	cin >> w >> h >> c;
	d = gcd(w, h);
	cout << w * h / (d * d) * c << endl;

	return 0;
}

Measured memory_bytes: 3084
use proconio::{input};
// use std::collections::HashSet;

fn main() {
    input! {
        n: usize,
        mut a: [usize; n]
    }

    let mut devide_array: [usize; 1_000_005] = [0; 1_000_005];

    a.sort();

    for &a_i in &a {
        if devide_array[a_i] != 0 {
            devide_array[a_i] = 2;
            continue;
        }
        for j in 1..=(1_000_005/a_i) {
            if j * a_i >= 1_000_005 {
                continue;
            }
            devide_array[j * a_i] += 1;
        }
    }

    let mut res = 0;

    for a_i in a {
        if devide_array[a_i] == 1 {
            res += 1;
        }
    }

    // let mut invalid_ids = HashSet::new();
    // 'outer: for i in 0..a.len() {
    //     for j in 0..a.len() {
    //         if i <= j && a[i] != a[j] {
    //             break;
    //         } else if (i != j) && (a[i] % a[j] == 0) {
    //             invalid_ids.insert(i);
    //             continue 'outer;
    //         } else if invalid_ids.contains(&j) {
    //             continue;
    //         }
    //     }
    //     res += 1;
    // }

    println!("{}", res);
}


Measured memory_bytes: 13176
#include <stdio.h>
#include <string.h>

int eval(char *ex, int first, int last);
int term(char *ex, int first, int last);
int factor(char *ex, int first, int last);
int literal(char *ex, int first, int last);
int find_open(char *ex, int first, int last);

int main(void)
{
	char expr[128];
	int n, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf(" %s", expr);
		printf("%d\n", eval(expr, 0, strlen(expr) - 2));
	}

	return (0);
}

int eval(char *ex, int first, int last)
{
	int i;

	for (i = last; i >= first; i--){
		if (ex[i] == ')'){
			i = find_open(ex, first, i - 1) - 1;
		}
		if (ex[i] == '+') return (eval(ex, first, i - 1) + term(ex, i + 1, last));
		if (ex[i] == '-') return (eval(ex, first, i - 1) - term(ex, i + 1, last));
	}
	return (term(ex, first, last));
}

int term(char *ex, int first, int last)
{
	int i;

	for (i = last; i >= first; i--){
		if (ex[i] == ')'){
			i = find_open(ex, first, i - 1) - 1;
		}
		if (ex[i] == '*') return (term(ex, first, i - 1) * factor(ex, i + 1, last));
		if (ex[i] == '/') return (term(ex, first, i - 1) / factor(ex, i + 1, last));
	}
	return (factor(ex, first, last));
}

int factor(char *ex, int first, int last)
{
	if (ex[first] == '('){
		return (eval(ex, first + 1, last - 1));
	}
	return (atoi(ex + first));
}

int find_open(char *ex, int first, int last)
{
	int close;
	int i;

	close = 0;
	for (i = last; i >= first; i--){
		if (ex[i] == ')') close++;
		if (ex[i] == '('){
			if (close == 0){
				return (i);
			}
			close--;
		}
	}
	return (-1);
}

Measured memory_bytes: 596
n = int(input())

dish_list = []
for i in range(n):
    ai, bi = list(map(int, input().split()))
    dish_list.append([ai, bi, ai+1+bi])


dish_list.sort(key = lambda x:x[2], reverse=True)


a, b =0, 0
turn = 1
for i in range(n):
    if turn ==1:
        a+=dish_list[i][0]
    else:
        b+=dish_list[i][1]
    turn*=-1


print(a-b)

Measured memory_bytes: 24872
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define N 100100
#define MOD 1000000007
#define int long long int
#define fn(i,n) for(int i=0;i<n;i+=1)
#define rep(i,l,r) for(int i=l;i<=r;i+=1)
int a[N];
int dp[110][N];
int pre[110][N];
int fun(int i,int j)
{
    if(j<0)return 0;
    if(j==0)return 1;
    if(i<0)return 0;
    if(dp[i][j]!=-1)return dp[i][j];
    dp[i][j]=(fun(i-1,j)+fun(i,j-1)-fun(i-1,j-a[i]-1)+MOD)%MOD;
    return dp[i][j];
}
signed main() {  
int n,k;cin>>n>>k;
fn(i,n)cin>>a[i];
fn(i,n+1){
    fn(j,k+1)dp[i][j]=-1;
}
cout<<fun(n-1,k)%MOD<<endl;


    return 0; 
}




Measured memory_bytes: 84864
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class WarshallFloyd():
    def __init__(self, e, n):
        self.E = e
        self.N = n

    def search(self):
        n = self.N
        nl = list(range(n))
        d = [[inf] * n for _ in nl]
        for i in range(n):
            d[i][i] = 0
        for k,v in self.E.items():
            dk = d[k]
            for b,c in v:
                # consider multiple edges
                if dk[b] > c:
                    dk[b] = c
        for i in nl:
            di = d[i]
            for j in nl:
                if i == j:
                    continue
                dj = d[j]
                for k in nl:
                    if i != k and j != k and dj[k] > dj[i] + di[k]:
                        dj[k] = dj[i] + di[k]
        return d

class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N
        self.nl = list(range(N))

    def max_flow(self, s, t):
        r = 0
        e = self.E
        v = None

        def f(c):
            v[c] = 1
            if c == t:
                return 1
            for i in e[c]:
                if v[i] is None and f(i):
                    e[c].remove(i)
                    e[i].add(c)
                    return 1
            return

        while True:
            v = [None] * self.N
            if f(s) is None:
                break
            r += 1

        return r

def main():
    rr = []

    def f(n,m,l):
        ma = [LI() for _ in range(m)]
        la = [LI() for _ in range(l)]
        e = collections.defaultdict(list)
        for u,v,d in ma:
            e[u].append((v,d))
            e[v].append((u,d))
        wf = WarshallFloyd(e,n)
        wd = wf.search()
        e2 = collections.defaultdict(set)
        for i in range(l):
            p1,t1 = la[i]
            for j in range(l):
                if i == j:
                    continue
                p2,t2 = la[j]
                if wd[p1][p2] <= t2-t1:
                    e2[i].add(j+l)
            e2[l*2].add(i)
            e2[i+l].add(l*2+1)
        # for k,v in e2.items():
        #     print('k,v',k,v)
        fl = Flow(e2,l*2+2)
        t = fl.max_flow(l*2,l*2+1)
        # print('t',t)
        return l - t

    while 1:
        n,m,l = LI()
        if n == 0:
            break
        rr.append(f(n,m,l))
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())



Measured memory_bytes: 75640
let N = Int(readLine()!)!
let mod = 1000000007
var dp: [[Int]] = .init(repeating: .init(repeating: 0, count: 4), count: N + 1)
dp[0][2] = 1
for n in 0..<N {
  for k in 0..<4 {
    for m in 0..<10 {
      let newState: Int
      if k == 2 && m == 0 {
        newState = 0
      } else if k == 2 && m == 1 {
        newState = 1
      } else if (k == 0 && m == 9) || (k == 1 && m == 0) {
        newState = 3
      } else {
        newState = k
      }
      dp[n+1][newState] += dp[n][k]
      dp[n+1][newState] %= mod
    }
  }
}
print(dp[N][3])

Measured memory_bytes: 93284
N = int(input())
a=b=c=d = 0
for i in range(N):
  char = input()
  if char =='AC':
    a += 1
  if char =='WA':
    b += 1
  if char =='TLE':
    c += 1
  if char =='RE':
    d += 1
print("AC x " +str(a))
print("WA x " +str(b))
print("TLE x " +str(c))
print("RE x " +str(d))

Measured memory_bytes: 8996
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append((a+b,a,b))
l.sort(reverse=True)
k=0
x=0
y=0
while k<n:
    if k%2==0:
        x+=l[k][1]
    else:
        y+=l[k][2]
    k+=1
print(x-y)

Measured memory_bytes: 20988
#include<bits/stdc++.h>
using namespace std;
int a,b,c;

int main()
{
	scanf("%d%d%d",&a,&b,&c);
	if((a==c&&a!=b)||(a==b&&a!=c)||(b==c&&b!=a))
	printf("Yes");
	else printf("No");
	return 0;
 } 

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long int
using namespace std;

int32_t main() {
    
   int n;
   cin >> n;
   
   int a[n];
   for(int i=0;i<n;i++)
   cin >> a[i];
   sort(a,a+n);
   
   int x=n/2;
   int p=a[x-1];
   int q=a[x];
   
   cout << q-p;
   
    
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        solve();
    }

    private static void solve() {
        Scanner input = new Scanner(System.in);

        int r = input.nextInt();

        int ans = (int)(3 * Math.pow(r, 2));

        System.out.println(ans);

    }
}


Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


int main(){
    ll n; cin>>n;
    cout<<n/3<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<int> d(n);
    rep(i,n)cin>>d[i];
    sort(d.begin(),d.end());
    int ans = 1;
    rep(i,n-1){
        if(d[i]!=d[i+1]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256