akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int           long long
#define pb            push_back
#define mp            make_pair
#define PI            3.14159265
#define M             1000000007
#define MM            998244353
#define fr            first
#define sc            second
#define all(v)        (v).begin(),(v).end()
#define rall(v)       (v).rbegin(),v.rend()
#define vc            vector
#define vi            vector<int>
#define pii           pair<int,int>
#define psi           pair<string,int>
#define pis           pair<int,string>
#define mii           map<int,int>
#define msi           map<string,int>

bool compare(const tuple<string,int,int> &a,const tuple<string,int,int> &b){
    if(get<0>(a)==get<0>(b)) return (get<1>(a)>get<1>(b));
    else return (get<0>(a)<get<0>(b));
}
int solve(){
    int r,d,x; cin>>r>>d>>x;
    for (int i = 1; i <= 10; ++i)
    {
        x=r*x-d;
        cout<<x<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 256
import string
s = string.ascii_lowercase


def f(x, tmp):
    if x == 0:
        return ""
    x -= 1
    if x < 26:
        return s[x] + tmp
    else:
        return f(x // 26 , s[x % 26] + tmp)


n = int(input())
r = f(n, "")
print(r)


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

int main(){ 
  string s;
  cin >> s;
  int n = sz(s);
  string t = "", l = "";
  for (int i = 0; i < (n-1) / 2; i++) {
    t += s[i];
  }
  for (int i = (n+3)/2 - 1; i < n; i++) {
    l += s[i];
  }
  if (t == l) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
} 

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        k: i32,
        x: i32,
    }

    if 500 * k >= x {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
	string s; cin >> s;
	int one = 0, zero = 0;
	for (int i = 0; i < s.size(); ++i)
		if (s[i] == '1') one++;
		else zero++;
	cout << min(zero, one) * 2 << endl;

	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
ll d[1000005];
double t[1000005];
int main(){
	int n=read(),m=read();
	int l=1,r=0,dq=0;
	double zl=0;
	for (int i=1;i<=n;i++){
		ll T=read(),V=read();
		d[++r]=V; t[r]=(double)T*V;
		zl+=t[r]; dq+=d[r];
		for (;t[r]/d[r]<t[r-1]/d[r-1]&&l<r;r--)
			if (d[r-1]+d[r]<=m) t[r-1]+=t[r],d[r-1]+=d[r];
			else{
				t[r-1]=t[r]+(t[r-1]/d[r-1])*(m-d[r]);
				dq=d[r-1]=m; zl=t[r-1]; --r; l=r;
			    break;
			}
		for (;dq>m;l++){
			if (dq-d[l]>=m) dq-=d[l],zl-=t[l];
			else {
				double k=t[l]/d[l];
				zl-=k*(dq-m);
				t[l]-=k*(dq-m);
				d[l]-=dq-m;
				dq=m; break;
			}
		}
		printf("%.7lf\n",zl/m);
	}
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = int;
using i64 = long long;
using f64 = double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf64 = vector<f64>;
using vstr = vector<string>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

struct xyz {
  i64 x, y, z;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  int n, m;
  cin >> n >> m;
  vector<xyz> v;
  rep(i, n) {
    i64 x, y, z;
    cin >> x >> y >> z;
    v.push_back({x, y, z});
  }
  i64 ans = 0;
  rep(i, bit(3)) {
    vi64 vv;
    rep(j, n) {
      i64 sum = 0;
      if (i & bit(0)) sum += v[j].x; else sum -= v[j].x;
      if (i & bit(1)) sum += v[j].y; else sum -= v[j].y;
      if (i & bit(2)) sum += v[j].z; else sum -= v[j].z;
      vv.push_back(sum);
    }
    sort(all(vv)); reverse(all(vv));
    i64 sum = 0;
    rep(j, m) sum += vv[j];
    amax(ans, sum);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};
signed main() {
	
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<int> A(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		A[i]--;
	}
	int a, b;
	UnionFind uf(N);
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		a--;
		b--;
		uf.unionSet(a, b);
	}
	for (int i = 0; i < N; i++) {
		if (uf.findSet(i, A[i])) {
			res++;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 1792
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
from queue import deque
q = deque(a)
ans = 0
for i in range(n):
    v1,v2,v3 = q.popleft(), q.popleft(), q.pop()
    ans += v2
print(ans)

Measured memory_bytes: 105176
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename A,typename B>istream&operator>>(istream&is,pair<A,B> &p){is>>p.fi>>p.se;return is;}
template<typename A,typename B>ostream&operator<<(ostream&os,const pair<A,B> &p){os<<"("<<p.fi<<","<<p.se<<")";return os;}
template<typename T>istream&operator>>(istream&is,vector<T> &t){REP(i,t.size())is>>t[i];return is;}
template<typename T>ostream&operator<<(ostream&os,const vector<T>&t){os<<"{";REP(i,t.size()){if(i)os<<",";os<<t[i];}cout<<"}";return os;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n,k;
    cin>>n>>k;
    double ans=0;
    FOR(i,1,n+1){
        int t=i;
        int cnt=0;
        while(t<k){
            cnt++;
            t*=2;
        }
        ans+=pow(2,-cnt)/n;
    }
    printf("%.16f\n",ans);
    return 0;
}

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

string s;
long long sum;

int main() {
    cin >> s;
    for(int i = 0; i < (int)s.size(); i++) {
        sum += (s[i] - '0');
    }
    if(sum % 9) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}

Measured memory_bytes: 3720
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

a, b = Is()
print((a-1)*(b-1))

Measured memory_bytes: 63340
#include<cstdio>

int main(){
    int n,i,t;
    char r[1001];
    while(1){
        scanf("%s",r);
        if (r[0] == '0') break;
        else{
            int s = 0;
            for(i = 0; r[i] != '\0'; i++ ){
                t = r[i] - '0';
                s += t;
            }
            printf("%d\n",s);
        }

    }
    return 0;
}


Measured memory_bytes: 2728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define REP(i,N) for(int i=0;i<N;i++)

struct Comp {
    bool operator() (pair<pair<string,int>,int> e1, pair<pair<string,int>,int> e2){
        return e1.first.first<e2.first.first || ((e1.first.first==e2.first.first) && e1.first.second>e2.first.second);
    }
};

int main(){
    int n; cin>>n;
    vector<pair<pair<string,int>,int>> v;
    for(int i=0;i<n;i++){
        string s; int p;
        cin>>s>>p;
        v.push_back({{s,p}, i+1});
    }
    sort(all(v),Comp());
    for(auto e:v){
        cout<<e.second<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int n, a[50], b[50], c[50], ans = 0;
	cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 1; i <= n; i++)cin >> b[i]; for (int i = 1; i < n; i++)cin >> c[i];
	for (int i = 1; i <= n; i++) { ans += b[a[i]]; if (a[i - 1] + 1 == a[i])ans += c[a[i] - 1]; }
	cout << ans << endl;
}

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

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

  int N;
  cin >> N;
  vector<int> A(N+2);
  A.at(0) = 0;
  A.at(N+1) = 0;

  int sum = 0;
  int p = 0;
  for(int i=1;i<N+1;i++){
    int a;
    cin >> a;
    A.at(i) = a;
    sum += abs(a - p);
    p = a;
  }
  sum += abs(A.at(N));

  for(int i=1;i<N+1;i++){
    int prev = A[i-1];
    int cur = A[i];
    int next = A[i+1];
    int ans = sum;
    if(prev == cur || cur == next){
      // no change
    }else if(prev < cur && cur < next){
      // no change
    }else if(next < cur && cur < prev){
      // no change
    }else if(prev < cur && next < cur){
      ans -= (cur - prev) + (cur - next);
      if(prev <= next){
	ans += (next - prev);
      }else{
	ans += (prev - next);
      }
    }else if(cur < next && cur < prev){
      ans -= (next - cur) + (prev - cur);
      if(prev >= next){
	ans += (prev - next);
      }else{
	ans += (next - prev);
      }
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <numeric>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int A,B,C;
	cin >>A>>B>>C;
	
	cout << max(C-(A-B),0)<< endl;
}

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

signed main(){
  int N,W;cin>>N>>W;
  std::vector<int> w(N),v(N);
  for(int i=0;i<N;i++)cin>>w[i]>>v[i];
  std::vector<int> dp(1e5+2,1e18);
  dp[0]=0;
  for(int i=0;i<N;i++){
    for(int j=1e5+2;j>=0;j--){
      if(j-v[i]>=0)dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
    }
  }
  int ans=0;
  for(int i=0;i<1e5+2;i++)if(dp[i]<=W)ans=i;
  cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
using pp=pair<int,pair<int,int>>;
#define MAX 200003
#define MOD 1000000007
#define INF 1000000000000000000

int main(){
  char a;
  cin>>a;
  int x=a-'a';
  if(x>=0&&x<26){
    cout<<'a'<<endl;
  }else{
    cout<<'A'<<endl;
  }
}


Measured memory_bytes: 3620
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<setprecision(10)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
 
int calcScore(vector<int> &plan, vector<int> &c, vector<vector<int>> &s) {
	int D = 365;
	int score = 0;
	vector<int> last(26, -1);
	for (int i = 0; i < D; i++) {
		score += s[i][plan[i]];
		last[plan[i]] = i;
		for (int j = 0; j < 26; j++) {
			score -= c[j] * (i - last[j]);
		}
	}
	return score;
}
 
int main() {
	int D;
	cin >> D;
	vector<int> c(26);
	for (int i = 0; i < 26; i++)cin >> c[i];
	vector<vector<int>> s(365,vector<int>(26,0));
	for (int i = 0; i < D; i++) {
		for (int j = 0; j < 26; j++)cin >> s[i][j];
	}
	
	vector<int> plan(365, 0);
	for (int i = 0; i < 365; i++) {
		int mi = 0, m = -1;
		for (int j = 0; j < 26; j++) {
			if (m < s[i][j]) {
				mi = j;
				m = s[i][j];
			}
		}
        plan[i] = mi;
	}
	int sc = calcScore(plan, c, s);
 
	for (int n = 0; n < 300000; n++) {
		if (rand() % 10 < 3) {
			int i = rand() % 365, j = rand() % 26, old = plan[i];
			plan[i] = j;
			int nsc = calcScore(plan, c, s);
			if (nsc > sc) {
				sc = nsc;
			}
			else {
				plan[i] = old;
			}
		}
		else {
			int k = rand() % 5;
			int i = rand() % (365 - k), j = i + k;
			swap(plan[i], plan[j]);
			int nsc = calcScore(plan, c, s);
			if (nsc > sc) {
				sc = nsc;
			}
			else {
				swap(plan[i], plan[j]);
			}
		}
	}
 
	for (int i = 0; i < 365; i++) {
		cout << plan[i] + 1 << endl;
	}
}

Measured memory_bytes: 3684
N = int(input())

for h in range(1, 3500+1):
  for n in range(1, 3500+1):
    if 4*h*n - N*n - N*h == 0:
      continue
    w = (N*h*n) // (4*h*n - N*n - N*h)
    if w < 1 or w > 3500:
      continue
    if 4*h*n*w == N*(n*w + h*w + n*h):
      print(h, n, w)
      exit()


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

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n-1; i++)
    {
        a[i+1] = gcd(a[i],a[i+1]);
    }
    cout << a[n-1] << endl;
}

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

int main()
{
	string s;
    cin>>s;
	int now=0;
	
    if(s[0]=='S')
	{
        if(s[1]=='U')
			now=0;
        else
			now=6;
    }
    
    if(s[0]=='M')
		now=1;
		
    if(s[0]=='T')
	{
        if(s[1]=='U')
			now=2;
        else
			now=4;
    }
    if(s[0]=='W')
		now=3;
    if(s[0]=='F')
		now=5;
		
    printf("%d\n",7-now);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
	int N, M, P;
	
	while(cin >> N >> M >> P, N+M+P){
		int x[N], sum = 0, ans = 0;
		for(int i = 0; i < N; ++i){
			cin >> x[i];
			sum += 100 * x[i];
		}
		sum =  sum * (100 - P) * 0.01;
		if(x[M - 1] != 0)
			ans = sum / x[M - 1];
		cout << ans << endl;
	}
}

Measured memory_bytes: 3084
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int> fri[100000];
vector<int> blo[100000];
int frindex[100000];
int frindexcounter[100000];
int blocounter, fricounter[100000];
int main() {

	int n, m, k;
	cin >> n >> m >> k;

	int i, j, a, b;
	for (i = 0; i < m; i++) {
		cin >> a >> b;
		fri[a - 1].push_back(b - 1);
		fri[b - 1].push_back(a - 1);
	}
	for (i = 0; i < k; i++) {
		cin >> a >> b;
		blo[a - 1].push_back(b - 1);
		blo[b - 1].push_back(a - 1);
	}

	for (i = 0; i < n; i++) {
		frindex[i] = -1;
		frindexcounter[i] = 0;
	}
	queue<int> que;
	int index = 0;
	for (i = 0; i < n; i++) {
		if (frindex[i] == -1) {
			frindex[i] = index;
			que.push(i);
			while (que.size()) {
				j = que.front(); que.pop();
				for (a = 0; a < fri[j].size(); a++) {
					if (frindex[fri[j][a]] == -1) {
						que.push(fri[j][a]);
						frindexcounter[index]++;
						frindex[fri[j][a]] = index;
					}
				}
			}
			index++;
		}
	}

	for (i = 0; i < n; i++) {
		blocounter = 0;
		for (j = 0; j < blo[i].size(); j++) {
			if (frindex[blo[i][j]] ==frindex[i]) {
				blocounter++;
			}
		}
		fricounter[i] = frindexcounter[frindex[i]] - fri[i].size() - blocounter;
		
	}
	for (i = 0; i < n; i++) {
		cout << fricounter[i] << ' ';
	}
	return 0;

}

Measured memory_bytes: 15708
#include <iostream>

using namespace std;

int main(){
  int N;
  long long int ans=0;
  cin >> N;
  for(int i=1; i<=N; i++){
    if(!(i%3 == 0 || i%5 ==0)){
      ans += i;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  string s;
  cin >> s;
  allrep (c, s) c = c == '1' ? '9' : '1';
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

def search(S, history, counter):
    new_history = [i for i in history]
    new_history.append(S)
    if len(new_history) == N:
        counter += 1
        return counter
        
    for i in range(len(A)):
        if A[i] == S and not B[i] in history:
            counter = search(B[i], new_history, counter)

    for i in range(len(B)):
        if B[i] == S and not A[i] in history:
            counter = search(A[i], new_history, counter)

    return counter

print(search(1, [], 0))


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll Q;
ll p3[40];
ll mk[5][40];
ll i, j, k;
pll zn(ll a,ll* mk){
    ll i,j=0;
    fornum(i,0,30){

        a %= p3[29 - i];
    }
}
int main(){
    p3[0] = 1;
    fornum(i,0,32){
        p3[i + 1] = p3[i] * 3;
    }
    
    scanf("%lld", &Q);
    
    while(Q--){
        ll a, b, c, d;
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        ll aa = a, bb = b, cc = c, dd = d;
        --a;
        --b;
        --c;
        --d;
        if(abs(a-c)>abs(b-d)){
            swap(a, b);
            swap(c, d);
        }
        ll flg = 0;
        for (i = 30; i > 0;--i){
            if(a/p3[i-1]==1&&a/p3[i-1]==c/p3[i-1]){
                if (abs((b / p3[i - 1] - d / p3[i - 1])) > 1)
                {
                    a %= p3[i - 1];
                    c %= p3[i - 1];
                    //printf("%lld,%lld,%lld,%lld,%lld,", a, b, c, d, p3[i - 1]);
                    printf("%lld\n", min(a+1 + c+1, abs(a - p3[i - 1]) + abs(c - p3[i - 1])) + abs(b - d));
                    flg = 1;
                    i = 1;
                }
            }
            if(a/p3[i-1]!=c/p3[i-1])
            {
                break;
            }
            a %= p3[i - 1];
            c %= p3[i - 1];
        }
        if(!flg){
            printf("%lld\n", abs(aa - cc) + abs(bb - dd));
        }
    }

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define LL long long

using namespace std;

int main()
{
    int n;
    cin>>n;
    map<string,int>  mp;
    int maxans=0;
    while(n--)
    {
        string tmp;
        cin>>tmp;
        mp[tmp]++;
        maxans=max(maxans,mp[tmp]);
    }
    set<string>  s;
    for (map<string, int>::iterator it = mp.begin(); it != mp.end();it++)
        if(it->second==maxans)
            s.insert(it->first);

      for (set<string>::iterator it = s.begin(); it != s.end();it++)
       cout<<*it<<endl;
}


Measured memory_bytes: 34560
#include<bits/stdc++.h>
#define lld long long int
#define ld long double
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,a,b)	for(lld i=a;i<=b;i++)
#define repr(i,a,b) for(lld i=a;i>=b;i--)
#define ar array
#define pb push_back
#define mp make_pair
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
lld n,m;
lld arr[300000];
lld siz[300000];
lld fact[300000];
lld par[300000];
lld fac(lld num){
    if (num==0) return 1;
    if (fact[num]!=-1)return fact[num];
    fact[num]=(num*fac(num-1))%mod;
    return fact[num];
}
lld fastpower(lld x, unsigned lld y, lld p)
{
    lld res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
string st;
ar<lld,2> dp[300000];
vector<lld> adj[300000];
void dfs_siz(lld node,lld pr){
    siz[node]=1;
    par[node]=pr;
    for(auto it:adj[node])if (it!=pr){dfs_siz(it,node);siz[node]+=siz[it];}
}
lld dfs_dp1(lld node,lld pr){
    if (dp[node][0]!=-1)return dp[node][0];
    dp[node][0]=fac(siz[node]-1);
    for(auto it:adj[node]) if (it!=pr) dp[node][0]=(((dp[node][0]*dfs_dp1(it,node))%mod)*fastpower(fac(siz[it]),mod-2,mod))%mod;
    return dp[node][0];
}
lld dfs_dp2(lld node,lld pr){
    if (dp[node][1]!=-1)return dp[node][1];
    if (pr==-1){
        dp[node][1]=1;
        return dp[node][1];
    }
    dp[node][1]=(fac(n-siz[node]-1)*dfs_dp1(pr,par[pr]))%mod;
    //for(auto it:adj[pr]) if (it!=par[pr]&&it!=node) dp[node][1]=(((dp[node][1]*dfs_dp1(it,node))%mod)*fastpower(fac(siz[it]),mod-2,mod))%mod;
    dp[node][1]=(((((dp[node][1]*fastpower(dfs_dp1(node,pr),mod-2,mod))%mod)*fac(siz[node]))%mod)*fastpower(fac(siz[pr]-1),mod-2,mod))%mod;
    dp[node][1]=(((dp[node][1]*dfs_dp2(pr,par[pr]))%mod)*fastpower(fac(n-siz[pr]),mod-2,mod))%mod;
    return dp[node][1];
}
int main()
{
     ios;
     lld TESTS,q,a,s,b,r,k,c,p,h,w,d,x,y,z,xs,ys,t;
     TESTS=1;
//     ans=0;
     //cin>>TESTS;
     memset(dp,-1,sizeof(dp));
     memset(fact,-1,sizeof(fact));
     while(TESTS--)
     {
         cin>>n;
         rep(i,0,n-2){
            cin>>a>>b;a--;b--;
            adj[a].pb(b);
            adj[b].pb(a);
         }
         dfs_siz(0,-1);
         rep(i,0,n-1) cout<<(((((fac(n-1)*fastpower((fac(siz[i]-1)*fac(n-siz[i]))%mod,mod-2,mod))%mod)*dfs_dp1(i,par[i]))%mod)*dfs_dp2(i,par[i]))%mod<<"\n";
     }
    return 0;
}


Measured memory_bytes: 31600
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
v = LIST()

e = Counter(v[0:n:2])
o = Counter(v[1:n:2])

if e.most_common()[0][0] != o.most_common()[0][0]:
    ans = n - e.most_common()[0][1] - o.most_common()[0][1]
else:
    try:
        tmp0 = n - e.most_common()[0][1] - o.most_common()[1][1]
    except:
        tmp0 = n - e.most_common()[0][1]
    try:
        tmp1 = n - e.most_common()[1][1] - o.most_common()[0][1]
    except:
        tmp1 = n - o.most_common()[0][1]
    ans = min( tmp0, tmp1 )

print( ans )

Measured memory_bytes: 24772
a,b,c = 3.times.map{gets.split.map(&:to_f)}

def area(a,b,c,d)
  return (a*d-b*c).abs
end

def length(p,q)
  return Math.sqrt((p[0]-q[0])**2+(p[1]-q[1])**2)
end

s = area(b[0]-a[0],b[1]-a[1],c[0]-a[0],c[1]-a[1])
x,y,z = length(a,b),length(b,c),length(c,a)
w = [x,y,z].max
r = s/(x+y+z)

puts w/(2+w/r)

Measured memory_bytes: 3836
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>using vv = vector<vector<T>>; template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N, D;
    cin >> N >> D;
    vv<int> X = vvec(N, D, 0);
    rep(i, N) {
        rep(j, D) cin >> X[i][j];
    }

    int ans = 0;
    rep(i, N - 1) rep(j, i + 1, N) {
        ll d = 0;
        rep(k, D) d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);

        ll dsqrt = sqrt(d) + 1e-6;
        if (dsqrt * dsqrt == d) {
            ans++;
        }
    }

    write(ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int64_t p=1000000007;
  vector<int64_t> b(60);
  for(int i=0;i<n;i++){
    int64_t a;
    cin>>a;
    for(int d=0;d<60;d++){
      b.at(d)+=a%2;
      a/=2;
    }
  }
  int64_t s=0;
  for(int d=0;d<60;d++){
    int64_t x=b.at(d)*(n-b.at(d))%p;
    for(int i=0;i<d;i++)
      x=x*2%p;
    s=(s+x)%p;
  }
  cout<<s<<endl;
}

Measured memory_bytes: 256
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <cmath>
#include <random>
#include <cctype>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MK make_pair
#define PB push_back
#define VI vector<int>
#define VII vector<int,int>
#define MSI map<string,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define W1 while(1);
const int MOD = 1000000007;
int main()
{
	string S;
	cin >> S;
	FOR(i,0,5)
	{
		cout << S.at(i);
	}
	cout << " ";
	FOR(i, 6, 13)
	{
		cout << S.at(i);
	}
	cout << " ";
	FOR(i, 14, 19)
	{
		cout << S.at(i);
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const double PI = 3.14159265358979;
static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;

ll l[201] = {};
int main() {
	ll n; cin >> n;
	rep(i, 0, 2 * n)cin >> l[i];

	sort(l, l + 2 * n);
	reverse(l, l + 2 * n);

	ll ans = 0;
	for (int i = 0; i < 2 * n; i += 2) {
		ans += l[i + 1];
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <stack>
#include <fstream>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>

using namespace std;

constexpr int INF = 1000000000;/* 1e+9a */

typedef int64_t ll;

array<array<ll, 1010>, 1010> dpx{}, dpy{}, dpz{};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<ll> x, y, z;
    for (int i = 0; i < N; ++i) {
        ll a, b, c;
        cin >> a >> b >> c;
        x.push_back(a);
        y.push_back(b);
        z.push_back(c);
    }

    ll summ = -INF;
    for (unsigned op = 0; op < 8; ++op) {
        for (int k = 0; k < N; ++k) {
            dpx[0][k] = 0;
            dpy[0][k] = 0;
            dpz[0][k] = 0;
        }
        for (int i = 1; i <= M; ++i) {
            dpx[i][i] = dpx[i-1][i-1] + x[i-1];
            dpy[i][i] = dpy[i-1][i-1] + y[i-1];
            dpz[i][i] = dpz[i-1][i-1] + z[i-1];
            for (int j = i + 1; j <= N; ++j) {
                ll dx,dy,dz;
                dx = x[j-1] + dpx[i-1][j-1];
                dy = y[j-1] + dpy[i-1][j-1];
                dz = z[j-1] + dpz[i-1][j-1];
                dx -= dpx[i][j-1];
                dy -= dpy[i][j-1];
                dz -= dpz[i][j-1];
                dx *= op & 1 ? 1 : -1;
                dy *= op & 2 ? 1 : -1;
                dz *= op & 4 ? 1 : -1;
                if(dx + dy + dz > 0){
                    dpx[i][j] = x[j-1] + dpx[i-1][j-1];
                    dpy[i][j] = y[j-1] + dpy[i-1][j-1];
                    dpz[i][j] = z[j-1] + dpz[i-1][j-1];
                }
                else{
                    dpx[i][j] = dpx[i][j-1];
                    dpy[i][j] = dpy[i][j-1];
                    dpz[i][j] = dpz[i][j-1];
                }
            }
        }
        ll sum = abs(dpx[M][N]) + abs(dpy[M][N]) + abs(dpz[M][N]);
        summ = max(sum, summ);
    }

    cout << summ << '\n';
}


Measured memory_bytes: 23552
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    int ls = s.length();
    int lt = t.length();
    int i;
    bool flg=true;
    for(i=0;i<ls;i++){
        if(s[i]!=t[i]){
            flg=false;
            break;
        }
    }
    if(flg){
        cout << "Yes" << endl;

    }else{
        
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>

using namespace std;

const int M = 1e4 + 10;

int a[M]; 

int main() {
	int n, m;
	cin >> n >> m;
	
	for (int i = 1; i <= m; i++) cin >> a[i];
	
	int res = n;
	for (int i = 1; i <= m; i++) {
		res -= a[i];
	}
	
	if (res < 0) cout << -1 << '\n';
	else cout << res << '\n';
	
	return 0;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int pa[100000];

int fnd(int n) {
	if (pa[n] < 0) return n;
	return pa[n] = fnd(pa[n]);
}
void uni(int a, int b) {
	a = fnd(a), b = fnd(b);
	if (a != b) {
		pa[a] += pa[b];
		pa[b] = a;
	}
}
int main() {
	fastio; ini(pa, -1);
	int N, M, K;
	cin >> N >> M >> K;

	vector<pii> fr;
	for (int a, b, i = 0; i < M; ++i) {
		cin >> a >> b;
		uni(--a, --b);
		fr.emplace_back(a, b);
	}

	int ans[100000]{};
	for (int i = 0; i < M; ++i) {
		if (fnd(fr[i].X) == fnd(fr[i].Y)) ++ans[fr[i].X], ++ans[fr[i].Y];
	}

	for (int a, b, i = 0; i < K; ++i) {
		cin >> a >> b;
		--a, --b;
		if (fnd(a) == fnd(b)) ++ans[a], ++ans[b];
	}

	for (int i = 0; i < N; ++i)
		cout << -pa[fnd(i)] - ans[i] - 1 << ' ';

	return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    P a, b;
    cin >> a.F >> a.S >> b.F >> b.S;
    cout << b.F - (b.S - a.S) << " ";
    cout << b.S + (b.F - a.F) << " ";
    cout << a.F - (b.S - a.S) << " ";
    cout << a.S + (b.F - a.F) << endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

ll D, T, S;

int main() {
  //
  cin >> D >> T >> S;

  if (D <= S * T) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}


Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _163B
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] NM = Console.ReadLine().Split(' ').Select(tmp => long.Parse(tmp)).ToArray();
            long[] A = Console.ReadLine().Split(' ').Select(tmp => long.Parse(tmp)).ToArray();
            long sumA = 0;

            foreach (var a in A) {
                sumA += a;
            }

            if (NM[0] >= sumA)
            {
                Console.WriteLine(NM[0] - sumA);

            }
            else {
                Console.WriteLine(-1);
            }

        }
    }
}


Measured memory_bytes: 29116
// practice with kaiboy
import java.io.*;
import java.util.*;

public class Main extends PrintWriter {
	Main() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		Main o = new Main(); o.main(); o.flush();
	}

	static final int MD = 1000000007;
	int power(long a, int k) {
		long p = 1;
		while (k > 0) {
			if ((k & 1) == 1)
				p = p * a % MD;
			a = a * a % MD;
			k >>= 1;
		}
		return (int) p;
	}
	int[] ff, gg;
	long ch(int n, int k) {
		return n < k ? 0 : (long) ff[n] * gg[k] % MD * gg[n - k] % MD;
	}
	void main() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		ff = new int[n];
		gg = new int[n];
		for (int f = 1, i = 0; i < n; i++) {
			gg[i] = power(ff[i] = f, MD - 2); 
			f = (int) ((long) f * (i + 1) % MD);
		}
		int[] aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt();
		aa = Arrays.stream(aa).boxed().sorted().mapToInt($->$).toArray();
		long ans = 0;
		for (int i = 0; i < n; i++)
			ans = (ans + (aa[i] - aa[n - 1 - i]) * ch(i, k - 1)) % MD;
		if (ans < 0)
			ans += MD;
		println(ans);
	}
}


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

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  map<int, int> mp;
  for(int i=0; i<n; i++){
    int x;
    cin >> x;
    mp[x]++;
  }
  int ans = 0;
  for(auto x : mp){
    if(x.second % 2 != 0) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4992
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int v[] = new int[n];

		for (int i=0; i<n; i++){
			v[i] = sc.nextInt();
		}
		HashMap<Integer, Integer>odd = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer>even = new HashMap<Integer, Integer>();

		for (int i=0; i<n; i++){
			if (i % 2 != 0){
				// 数列の偶数番目の処理
				if (even.containsKey(v[i])){
					even.put(v[i], even.get(v[i]) + 1);
				} else {
					even.put(v[i], 1);
				}
			} else {
				// 数列の奇数番目の処理
				if (odd.containsKey(v[i])){
					odd.put(v[i], odd.get(v[i]) + 1);
				} else {
					odd.put(v[i], 1);
				}
			}
		}
		List<Entry<Integer, Integer>> oddEntries = new ArrayList<Entry<Integer, Integer>>(odd.entrySet());

		Collections.sort(oddEntries, new Comparator<Entry<Integer,Integer>>() {
			public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2){
				return obj2.getValue().compareTo(obj1.getValue());
			}
		});

		List<Entry<Integer, Integer>> evenEntries = new ArrayList<Entry<Integer, Integer>>(even.entrySet());

		Collections.sort(evenEntries, new Comparator<Entry<Integer,Integer>>() {
			public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2){
				return obj2.getValue().compareTo(obj1.getValue());
			}
		});
		int oddMode = oddEntries.get(0).getKey();
		int oddModeCnt = oddEntries.get(0).getValue();
		int evenMode = evenEntries.get(0).getKey();
		int evenModeCnt = evenEntries.get(0).getValue();
		int ans = 0;
		if (oddMode != evenMode){
			ans = n - (oddModeCnt + evenModeCnt);
			System.out.println(ans);
		} else {
			if (oddEntries.size() == 1){
				ans = n - (oddModeCnt);
			} else {
				int ans1 =0;
				int ans2 =0;
				ans1 = n - (oddModeCnt + evenEntries.get(1).getValue());
				ans2 = n - (oddEntries.get(1).getValue() + evenModeCnt);
				ans = Math.min(ans1, ans2);
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 56516
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=200005;
const ll inf=1e18;
struct node{
	ll mn,mn2; int col,col2;
	node(ll x=inf,int c=0){
		mn=x,mn2=inf,col=c,col2=0;
	}
	node ex(ll x){
		node res=*this;
		res.mn+=x,res.mn2+=x;
		return res;
	}
	friend node operator + (node a,node b){
		if(b.mn<a.mn) swap(a,b);
		node res=a;
		if(res.col!=b.col){
			if(b.mn<res.mn2) res.mn2=b.mn,res.col2=b.col;
		}
		else{
			if(b.mn2<res.mn2) res.mn2=b.mn2,res.col2=b.col2;
		}
		return res;
	}
} f[N],g[N];
int x[N],pa[N],cur[N],n,a,b,c,con;
vector<pii> e[N];
ll val[N],ans;

int gp(int x){
	return pa[x]==x?x:pa[x]=gp(pa[x]);
}

void dfs1(int u,int fa){
	f[u]=node(x[u],gp(u));
	for(auto v:e[u]){
		if(v.fi==fa) continue;
		dfs1(v.fi,u);
		f[u]=f[u]+f[v.fi].ex(v.se);
	}
}

void dfs2(int u,int fa){
	node res=f[u]+g[u];
	if(res.col==gp(u)){
		cur[u]=res.col2,val[u]=x[u]+res.mn2;
	}
	else{
		cur[u]=res.col,val[u]=x[u]+res.mn;
	} 
	if(fa&&e[u].size()==1) return;
	int sz=e[u].size()-(fa>0),k=0;
	vector<node> pre(sz),suf(sz);
	vector<pii> sn(sz);
	for(auto v:e[u]){
		if(v.fi==fa) continue;
		sn[k]=v,pre[k]=suf[k]=f[v.fi].ex(v.se),k++;
	}
	rep(k,1,sz-1) pre[k]=pre[k-1]+pre[k];
	per(k,sz-2,0) suf[k]=suf[k+1]+suf[k];
	g[u]=g[u]+node(x[u],gp(u));
	rep(i,0,sz-1){
		int v=sn[i].fi;
		g[v]=g[u];
		if(i-1>=0) g[v]=g[v]+pre[i-1];
		if(i+1<sz) g[v]=g[v]+suf[i+1];
		g[v]=g[v].ex(sn[i].se);
		dfs2(v,u);
	}
}

int main(){
	read(n);
	rep(i,1,n) read(x[i]);
	rep(i,1,n-1){
		read(a),read(b),read(c);
		e[a].pb(mp(b,c));
		e[b].pb(mp(a,c));
	}
	rep(i,1,n) pa[i]=i;
	for(con=n;con>=2;){
		dfs1(1,0);
		g[1]=node(inf,0);
		dfs2(1,0);
		rep(i,1,n) if(val[i]<val[gp(i)]){
			val[gp(i)]=val[i],cur[gp(i)]=cur[i];
		}
		rep(i,1,n) if(gp(i)==i){
			ans+=val[i],pa[gp(cur[i])]=i,con--;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 68352
#include <math.h>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
// clang-format on

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x = 0) : x(x % mod) {}
  mint& operator+=(const mint a)
  {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

mint dp[61][2][2][2];

ll l, r;

int main(void)
{
  cin >> l >> r;
  dp[60][0][0][0] = 1;
  for (int i = 59; i >= 0; i--) {
    int lb = l >> i & 1;
    int rb = r >> i & 1;
    REP(j, 2) REP(k, 2) REP(s, 2)
    {
      mint pre = dp[i + 1][j][k][s];
      REP(x, 2) REP(y, 2)
      {
        if (x && !y) continue;  // x= 1, y = 0
        int nj = j, nk = k, ns = s;

        if (!s && x != y) continue;
        if (x && y) ns = 1;

        if (!j && !x && lb) continue;
        if (x && !lb) nj = 1;

        if (!k && y && !rb) continue;
        if (!y && rb) nk = 1;

        dp[i][nj][nk][ns] += pre;
      }
    }
  }
  mint ans;
  REP(j, 2) REP(k, 2) REP(s, 2) ans += dp[0][j][k][s];
  cout << ans.x << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>

using namespace std;

typedef struct _Node {
    int color = 0;
    vector<struct _Node*> next;
    int d = -1;
} Node;

void query(Node* node, int d, int c) {
    if (node->d >= d) {
        return ;
    }
    
    node->d = d;

    if (node->color == 0) {
        node->color = c;
    }
    
    for (vector<Node*>::iterator it = node->next.begin();
         it != node->next.end(); it++) {
        if ((*it)->d < d-1) {
            query((*it), d-1, c);
        }
    }
}

int main(void) {
    int n, m, q;
    int *a, *b, *v, *d, *c;
    Node *nodes;

    scanf("%d %d", &n, &m);
    
    nodes = new Node[n];
    a = new int[m];
    b = new int[m];

    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a[i], &b[i]);
        nodes[a[i]-1].next.push_back(&nodes[b[i]-1]);
        nodes[b[i]-1].next.push_back(&nodes[a[i]-1]);
    }

    scanf("%d", &q);

    v = new int[q];
    d = new int[q];
    c = new int[q];

    for (int i = 0; i < q; i++) {
        scanf("%d %d %d", &v[i], &d[i], &c[i]);
    }

    for (int i = q-1; i >= 0; i--) {
        query(&nodes[v[i]-1], d[i], c[i]);
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", nodes[i].color);
    }

    return 0;
}


Measured memory_bytes: 10356
N,A,B = list(map(int,input().split()))

if (A-B)%2 == 0:
    print((max(A,B)-min(A,B))//2)
else:
    print(min(min(A,B)+(max(A,B)-min(A,B))//2, N-max(A,B)+1 + (max(A,B)-min(A,B))//2))

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

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, GCD = 0;
  cin >> N;
  vector<int> H(N), CD(N+1), CDR(N+1);
  for (int i=0; i<N; i++) cin >> H[i];
  for (int j=0; j<N; j++) {
    CD[j+1] = gcd(CD[j], H[j]);
  }
  for (int j=N; j>0; j--) {
    CDR[j-1] = gcd(CDR[j], H[j-1]);
  }
  for (int i=0; i<N; i++) {
    GCD = max(gcd(CD[i], CDR[i+1]), GCD);
  }
  cout << GCD << endl;
  return 0;
}


Measured memory_bytes: 1408