akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
string s;
cin >> s;
int n = s.length();
REP(i, 0, n) { cout << s[i];
  ++i;
}
cout << endl;

return 0;
}


Measured memory_bytes: 512
# C - Peaks

N, M = map(int, input().split())
H = list(int(x) for x in input().split())
G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

ans = [1] * N

for i in range(N):
    for j in G[i]:
        if H[i] <= H[j]:
            ans[i] = 0
            break

print(sum(ans))

Measured memory_bytes: 30300
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n; cin >> n;
	vector<vector<pi>> e(n);
	vi ans(n, -1);
	rep(i, n - 1){
		int a, b, c; cin >> a >> b >> c; a--; b--;
		e[a].emplace_back(b, c % 2);
		e[b].emplace_back(a, c % 2);
	}
	function<void(int,int,int)> rec = [&](int c, int p, int col){
		ans[c] = col;
		for(pi i : e[c]) if(i.first != p && ans[i.first] < 0){
			rec(i.first, c, (col + i.second) % 2);
		}
	};
	rec(0, 0, 0);
	for(int i : ans) cout << i << endl;
	return 0;
}

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

typedef long long ll;

int main(void) {

    int N, T; cin >> N >> T;
    vector<int> t(N);
    for (int i = 0; i < N; i++) cin >> t[i];

    ll ans = T;
    for (int i = 1; i < N; i++) {
        if (t[i] - t[i-1] >= T) {
            ans += T;
        } else {
            ans += t[i]-t[i-1];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
// 150 B - Count ABC 2020/01/10
#include <bits/stdc++.h>
#define rep(i ,n) for(int i=0;i<(int)(n);++i)
using namespace std;
typedef long long int int64;
typedef unsigned long long uint64;

int main(){
    int n; cin >> n;
    string s; cin >> s;
    int ans=0;
    rep(i ,n-2){
        if(s[i]=='A'){
            if(s[i+1]=='B'){
                if(s[i+2]=='C'){
                    ++ans;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define REP(i,j) for(int i=0;i<j;i++)
#define FORN(i,j,k) for(int i=j;i<k;i++)
#define vi vector<int>
#define vvi vector<vi >
#define pii pair<int,int>
#define vpii vector<pii >
using namespace std;
int n;
int a[200005],b[200005];
int main(void){
	cin>>n;
	REP(i,n){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b,b+n);
	int larger=b[n/2],smaller=b[n/2-1];
	REP(i,n){
		if(a[i]<=smaller)cout<<larger<<endl;
		else cout<<smaller<<endl;
	}
	return 0;
}

Measured memory_bytes: 3712
#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


struct edge
{
	long long to; long long len;
	bool operator<(const edge& rhs) const {
		return len > rhs.len;
	}
};

int main() {
	ll a, b, c;
	cin >> a >> b >> c;

	if (c > a + b + 1) {
		cout << b + a + b + 1 << endl;
	}
	else {
		cout << b + c << endl;
	}
}

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

int main()
{
  i64 n;
  cin >> n;
  set<vector<i64>> s;
  for (i64 i = 0; i < n; i++)
  {
    vector<i64> a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    s.insert(a);
  }
  cout << n - s.size() << endl;
  return 0;
}



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

int main()
{
    char ch;
    long a,b,c;

    while(cin>>a>>ch>>b)
    {
        if(ch=='?')
            break;
        switch(ch)
        {
        case '+':
            c=a+b;
            break;
        case '-':
            c=a-b;
            break;
        case '*':
            c=a*b;
            break;
        case '/':
            c=a/b;
            break;
        }
        cout<<c<<endl;

    }
    return 0;
}

Measured memory_bytes: 3092
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 1987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 998244353;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int a[500],t[500];
int n,k;
bool chk(int x)
{
	ll c=0;
	fup(i,0,n-1,1)
	{
		t[i]=a[i]%x;
	}
	sort(t,t+n);
	int l=0,r=n-1;
	while(l<r)
	{
		int tt=min(t[l],x-t[r]);
		c+=tt;
		t[l]-=tt,t[r]+=tt;
		if(t[l]==0)l++;
		if(t[r]==x)r--;
	}
	return c<=k;
}
int main() {
	scanf("%d%d",&n,&k);
	int sum=0;
	fup(i,0,n-1,1)
	{
		scanf("%d",a+i);
		sum+=a[i];
	}
	int ans=1;
	for(int i=1;i*i<=sum;i++)
	{
		if(i<ans)break;
		if(sum%i==0)
		{
			if(chk(i))ans=max(ans,i);
			if(chk(sum/i))ans=max(ans,sum/i);
		}
	}
	printf("%d",ans);
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b;
  scanf("%d%d",&a,&b);
  if(a>b)
    printf("%d\n",2*a-1);
  else if(a==b)
    printf("%d\n",a+b);
  else
    printf("%d\n",2*b-1);
  return 0;
}


Measured memory_bytes: 128
import sys

A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))

N = int(input())
a = [int(input()) for i in range(N)]

if (A1[0] in a) and (A1[1] in a) and (A1[2] in a):
  print("Yes")
  sys.exit()
  
elif (A2[0] in a) and (A2[1] in a) and (A2[2] in a):
  print("Yes")
  sys.exit()
  
elif (A3[0] in a) and (A3[1] in a) and (A3[2] in a):
  print("Yes")
  sys.exit()
  
elif (A1[0] in a) and (A2[0] in a) and (A3[0] in a):
  print("Yes")
  sys.exit()

elif (A1[1] in a) and (A2[1] in a) and (A3[1] in a):
  print("Yes")
  sys.exit()
  
elif (A1[2] in a) and (A2[2] in a) and (A3[2] in a):
  print("Yes")
  sys.exit()
 
elif (A1[0] in a) and (A2[1] in a) and (A3[2] in a):
  print("Yes")
  sys.exit()

elif (A1[2] in a) and (A2[1] in a) and (A3[0] in a):
  print("Yes")
  sys.exit()
  
print("No")

Measured memory_bytes: 3188
<?php
function getArrayFromStdin() {
	$line = trim(fgets(STDIN));
	$line = str_replace(array("\r\n","\r","\n"), '', $line);
	$line = explode(" ", $line);
	return $line;
}
 
$s = getArrayFromStdin();
 
$result = ($s[0] * $s[1]) % 2 === 1 ? 'Odd' : 'Even';
echo $result;

Measured memory_bytes: 4604
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#define rep(i,n) for (int i= 0;i<(n);++i)
using namespace std;
typedef long long ll;
const ll maxSum = 50*50+1;
int main() {
    vector<int> a(3);
  for(int i=0;i<3;i++){
    cin >> a[i];
  }
  
  sort(a.begin(),a.end());
  
  int ans=0;
  int x = (a[2]-a[0])/2;
  a[0] += 2*x;
  ans += x;
  int y = (a[2] - a[1])/2;
  a[1] += 2*y;
  ans += y;
  
  sort(a.begin(),a.end());
  
  if(a[0] == a[1] && a[1] == a[2]){
    cout << ans << endl;
  }else if(a[0] == a[1] - 1 && a[1] == a[2]){
    ans += 2;
    cout << ans << endl;
  }else{
    ans++;
    cout << ans << endl;
  }
 
    return 0;
}

Measured memory_bytes: 3608
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<char>> v(n, vector<char>(n));
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      cin >> v[i][j];
    }
  }
  
  vector<vector<char>> w(m, vector<char>(m));
  for(int i=0; i<m; i++) {
    for(int j=0; j<m; j++) {
      cin >> w[i][j];
    }
  }
  
  //25**4
  int count = 0;
  bool include = false;
  for(int i=0; i<=n-m; i++) {
    for(int j=0; j<=n-m; j++) {
      for(int k=0; k<m; k++) {
        for(int l=0; l<m; l++) {
          if(v[i+k][j+l] == w[k][l]) count++;
        }
        if(count == m*m) include = true;
      }
      if(include) goto SKIP;
      count = 0;
    }
  }
  SKIP:
  if(include) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1e5+5;

ll ara[MX], csm[MX];

int main(){
     ll i, j, k;
     ll n;
     cin >> n;
     for(i=0; i<=n; ++i) cin >> ara[i];
     for(i=n; i>=0; --i) csm[i]=csm[i+1]+ara[i];
     ll cur=1, ans=1;
     for(i=0; i<=n; ++i){
          cur-=ara[i];
          if(cur<0){
               puts("-1");
               return 0;
          }
          cur*=2LL;
          cur=min(cur, csm[i+1]);
          ans+=cur;
     }
     cout << ans << endl;
}


Measured memory_bytes: 5164
import sys

read = sys.stdin.read


def main():
    N, K = map(int, read().split())

    dp1 = [0] * (K + 1)
    dp2 = [0] * (K + 1)
    dp1[0] = 1

    for x in map(int, str(N)):
        dp1, dp1_prev = [0] * (K + 1), dp1
        dp2, dp2_prev = [0] * (K + 1), dp2
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] = dp2_prev[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1_prev[j - 1] * (x - 1)
            dp2[j] += dp2_prev[j]
            if x != 0:
                dp2[j] += dp1_prev[j]
                
            if x != 0:
                if j > 0:
                    dp1[j] = dp1_prev[j - 1]
            else:
                dp1[j] = dp1_prev[j]

    print(dp1[K] + dp2[K])
    return


if __name__ == '__main__':
    main()


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

struct Benri {
    Benri() {
        std::cin.tie(0); ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
    }
} benri;
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; }

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353


vector<vll> dp(2010,vll(2010,0));

int main() {
    int N, M; cin >> N >> M;
    vi S(N), T(M);
    rep(i, N) cin >> S[i];
    rep(j, M) cin >> T[j];

    rep(i,N+1) dp[i][0] = 1;
    rep(j,M+1) dp[0][j] = 1;

    for (int i = 1; i <=  N ; i ++) {
        for (int j = 1; j <= M ; j++) {
            if (S[i - 1] == T[j - 1]) {
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
            }
            else{
                dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + MOD) % MOD;
            }
        }
    }
    cout << dp[N][M] << endl;

}


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

int main() {
	string s;
	cin >> s;
	int count = 0;
	for (int i = 0; i < s.size()-1; ++i) {
		if (s[i] != s[i + 1])++count;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 512
import copy
N = int(input())
A = list(map(int, input().split()))
A_sum = 0
A2 = []
idx = dict()

for i in A:
  if i in idx:
    idx[i] += 1
  else:
    idx[i] = 1
    
for key in idx:
  if idx[key] == 1:
    idx[key] = [idx[key], 0]
  else:
    temp = int(idx[key] * (idx[key] - 1)/2)
    A_sum += temp
    temp = temp - int(temp * (idx[key] - 2) / idx[key])
    idx[key] = [idx[key], temp]
  
for i in range(N):
  key = A[i]
  print(A_sum - idx[key][1])


Measured memory_bytes: 114944
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define PI acos(-1.0)
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//next_permutation(ALL(p));
//typedef priority_queue<int> pque;//これは大きい順
//typedef priority_queue<int, vector<int>, greater<int>> pque;//これは小さい順
//factorizeは、素因数分解用の関数

int main(){
	int a;
  cin >> a;
  cout << a + a * a + a * a * a << endl;
  
  return 0;
}


Measured memory_bytes: 3636
N = int(input())
T = list(map(int,input().split()))
M = int(input())
PX =[list(map(int,input().split())) for i in range(M)]

for i in range(M):
    sum=0
    for j in range(N):
        if PX[i][0] == j+1:
            sum+=PX[i][1]
        else:
            sum+=T[j]
    print(sum)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back 
#define mod 1e9+7

int main(){
      ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);    
      int x,y;
       cin>>x>>y;
       int a=0,b=0;
       for(int i=0; i<x;  i++)
          a=10*a+y;
        for(int i=0; i<y; i++)
          b=10*b+x;
          
          if(x>y)
            cout<<a<<endl;
            else
             cout<<b<<endl;  
    }
//aaaaa


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()


int main(){
    int h,w,k;
    string c[6];
    string c2[6];

    cin>>h>>w>>k;
    rep(i,h) cin>>c[i];

    int ans=0;
    rep(mskh,1<<h) rep(mskw,1<<w){
        rep(i,h) c2[i]=c[i];
        rep(i,h){
            if(mskh & 1<<i){
                rep(j,w) c2[i][j]='R';
            }
        }
        rep(j,w){
            if(mskw & 1<<j){
                rep(i,h) c2[i][j]='R';
            }
        }

        int cnt=0;
        rep(i,h) rep(j,w){
            if(c2[i][j]=='#') cnt++;
        }
        if(cnt==k) ans++;
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 3648
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define MOD 998244353
#define inf 100000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
#define ar array
#define ld long double
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
char c[4]={'D' , 'R' , 'U' , 'L'};
const ll maxN=2e5+5;
ll n , W , w[maxN] , v[maxN];
ll dp[101][maxN];
void solve(){
	cin>> n >> W ;
	for(ll i=0;i<n ;i++){
		cin>>w[i]>>v[i];
	}
	for(ll i=0;i<=n ;i++){
		for(ll j=0;j<maxN ; j++)dp[i][j]=inf;
		for(ll j=0;j<maxN ; j++){
			if(i==0 && j==0)dp[i][j]=0;
			else if(i==0)dp[i][j]=inf;
			else{
				dp[i][j]=min(dp[i][j],dp[i-1][j]);
				if(j-v[i-1]>=0)dp[i][j]=min(dp[i][j] , w[i-1]+dp[i-1][j-v[i-1]]);
			}
		}
	}
	ll ans=0;
	// for(ll i=0;i<=n ;i++){
	// 	for(ll j=0;j<=20 ; j++)cerr<<dp[i][j]<<" ";
	// 	cerr<<endl;
	// }
	for(ll i=0;i<maxN ; i++){
		if(dp[n][i]<=W)ans=i;
	}
	cout<<ans<<endl;

}
int main(){
	//mahakal();
	fast;
	ll t =1 ;
	//cin>> t ; 
	while(t--)solve();
	//cerr << "\ntime taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
	return 0;
}

Measured memory_bytes: 161480
#include <iostream>
#include <string>
#include <math.h>
#include <vector>

using namespace std;

int main() {

	char M[3];
	int i;
	
	for (i = 0; i < 3; i++) {
		cin >> M[i];
	}
	for (i = 0; i < 3; i++) {
		if (M[i] == '7') {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";

	return 0;
}

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

int main(){
	int n;
	cin >> n;
	vector<vector<double>> dp(n + 1, vector<double>(n + 1));
	double p[3000];
	//for(int i = 0; i <= n; i++) dp[0][i] = 1;
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++) cin >> p[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= i; j++){
			if(j > 0)dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i];
			else dp[i][j] = dp[i - 1][j] * (1.0 - p[i]);
			//cout << dp[i][j] << endl;
		}
	}
	double ans = 0;
	for(int i = (n + 2)/2; i <= n; i++){
		ans += dp[n][i];
	}
	cout << std::fixed;
    cout << std::setprecision(10);
	cout << ans << '\n';
}

Measured memory_bytes: 70784
#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <type_traits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <complex>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
int main(){
	ll A, B, C;
	cin >> A >> B >> C;
	if(C > (A - B)){
		cout << C - (A - B) << endl;
	} else {
		cout << 0 << endl;
	}
}


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

int main() {
   char a, b;
   cin >> a >> b;
   if (a == b) {
       cout << 'H' << endl;
   } else {
       cout << 'D' << endl;
   }
}

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

int main() {
  int64_t a, b, x, count;
  cin >> a >> b >> x;
  
  count =  b / x - (a - 1) / x;
  if (a == 0) count = b / x + 1;
  cout << count << endl;
}

Measured memory_bytes: 3620
d = list(map(int, input().split()))
rq = list(input())
for i in rq:
  if i == "E":
    d[0], d[2], d[3], d[5] = d[3], d[0], d[5], d[2]
  elif i == "N":
    d[0], d[1], d[4], d[5] = d[1], d[5], d[0], d[4]
  elif i == "S":
    d[0], d[1], d[4], d[5] = d[4], d[0], d[5], d[1]
  elif i == "W":
    d[0], d[2], d[3], d[5] = d[2], d[5], d[0], d[3]
print(d[0])


Measured memory_bytes: 5600
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define INF      (int)1e9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef pair<int,int> pii;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
template<class Type> void join(const Type &a){for(auto elem:a)cout<<elem<<' ';cout<<endl;}

#define PI 3.14159265359

double f(double x,double y){
	return sqrt(pow(x,2)+pow(y,2));
}

int main(){
	double a,b,x;
	cin>>a>>b>>x;
	
	x/=a;
	
	if(a*b/2>=x) printf("%.10f\n",180*acos((2*x/b)/f(b,2*x/b))/PI);
	else{
		double c=2*x/a-b;
		printf("%.10f\n",180*atan((b-c)/a)/PI);
	}
}

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

int main()
{
  int n;
  cin >> n;
  vector<int> t;
  for (int i = 0; i < n; i++) {
	int s;
	cin >> s;
	t.push_back(s);
  }
  int m;
  cin >> m;
  vector<pair<int, int>> d;
  for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	d.push_back(make_pair(a, b));
  }
  int ans;
  for (int i = 0; i < m; i++) {
	int p = d[i].first;
	ans = 0;
	for (int j = 0; j < n; j++) {
	  if (j == (p - 1)) {
		ans += d[i].second;
	  }
	  else {
		ans += t[j];
	  }
	}
	cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 256
while True:
	n=int(input())
	if n==0:
		break
	a=list(map(str,input().split()))
	cnt=0
	l=r=0
	q=0
	for i in range(n):
		if a[i]=="lu":
			l=1
		elif a[i]=="ru":
			r=1
		elif a[i]=="ld":
			l=0
		else:
			r=0
		if l==r==1 and q==0:
			cnt+=1
			q=1
		elif l==r==0 and q==1:
			cnt+=1
			q=0
	print(cnt)




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

signed main() {
  int N, A, B;
  cin >> N >> A >> B;
  
  if( B < A || ( N == 1 && A != B ) ){
    cout << 0 << endl;
    return 0;
  }else if( B == A || N <= 2 ){
    cout << 1 << endl;
    return 0;
  }
  
  int C = (N-1)*A+B;
  int D = (N-1)*B+A;
  
  cout << D-C+1 << endl;
  
  
}

Measured memory_bytes: 256
from collections import defaultdict as dd, deque, Counter
n = int(input())
C = Counter(map(int,input().split()))

if len(C) == 1:
    if list(C)[0] == 0:
        print('Yes')
    else:
        print('No')
elif len(C) == 2:
    it = list(C.items())
    k1,v1 = it[0]
    k2,v2 = it[1]
    if v1 == 2*v2 or v2 == 2*v1 and 0 in [k1,k2]:
        print('Yes')
    else:
        print('No')
elif len(C) == 3:
    it = list(C.items())
    k1,v1 = it[0]
    k2,v2 = it[1]
    k3,v3 = it[2]

    if v1 == v2 == v3 and k1^k2 == k3:
        print('Yes')
    else:
        print('No')
else:
    print('No')


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

int main(){
    long a,b,x;
    cin >> a >> b >> x;
    long co = b/x;
    long am = (a-1)/x;
    
    if(a==0){
        cout << co + 1 << endl;
    }
    else{
        cout << co -am << endl; 
    }
    return 0;
}

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

#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define vi vector<int>
using namespace std;
int mod = 1'000'000'000 + 7;
namespace uf {
    vector<int> par, rank;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = root(par[x]);
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y)return;
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
    }
}
namespace choose {
    vector<vector<ll>> v;
    vector<ll> vv;

    void init_simple(int N) {
        vv.resize(1);
        vv[0] = 1;
        v.push_back(vv);
        for (int i = 1; i <= N; i++) {
            vv.resize(i + 1);
            for (int j = 1; j < i; j++) {
                vv[j] = v[i - 1][j - 1] + v[i - 1][j];
            }
            vv[i] = 1;
            v.push_back(vv);
        }
    }

    ll simple(int p, int q) {
        return v[p][q];
    }
}
namespace prime {
    vector<bool> is_not_prime{1, 1, 0};

    void make_is_not_prime(int N) {
        int l = is_not_prime.size();
        if (l >= N + 1) {
            return;
        }
        is_not_prime.resize(N + 1);
        for (int i = 2; i <= N; i++) {
            if (!is_not_prime[i]) {
                for (int j = max(((l + i - 1) / i) * i, i + i); j <= N; j += i) {
                    is_not_prime[j] = 1;
                }
            }
        }
    }

    vector<ll> list(ll a, ll b) {
        //{a, b)
        a = max(2LL, a);
        set<ll> st;
        for (ll i = a; i < b; i++) {
            st.insert(i);
        }
        ll l = sqrt(b);
        make_is_not_prime(l);
        for (ll i = 2; i <= l; i++) {
            if (!is_not_prime[i]) {
                for (ll j = max(((a + i - 1) / i) * i, i + i); j < b; j += i) {
                    st.erase(j);
                }
            }
        }
        vector<ll> res;
        for (auto x:st) {
            res.push_back(x);
        }
        return res;
    }
}

ll pow_mod(ll n, ll k, ll m) {
    ll r = 1;
    for (; k > 0; k >>= 1) {
        if (k & 1) r = (r * n) % m;
        n = (n * n) % m;
    }
    return r;
}

ll Manhattan(ll a, ll b, ll c, ll d) {
    return abs(a - c) + abs(b - d);
}

ll Manhattan(pair<ll, ll> a, pair<ll, ll> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

ll gcd(ll a, ll b) {
    if (b == 0)return a;
    return gcd(b, a % b);
} // C++17
void COME_LET_THE_GAMES_BEGIN() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(20);
}

ll N;

int main() {
    COME_LET_THE_GAMES_BEGIN();
    cin >> N;
    cout << "ABC" << N << endl;
}

Measured memory_bytes: 256
// #pragma GCC optimize("unroll-loops", "omit-frame-pointer", "inline")
// #pragma GCC option("arch=native", "tune=native", "no-zero-upper")
// #pragma GCC
// target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("tree-vectorize","openmp","predictive-commoning")
// #pragma GCC option("D_GLIBCXX_PARALLEL","openmp")

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

template <class T>
void chmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T &a, const T &b) {
  if (a < b) a = b;
}

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

#define endl "\n"

void solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  cin >> A;
  int Q;
  cin >> Q;
  ll ans = 0;
  map<int, int> m;
  for (int i = 0; i < N; i++) {
    ans += A[i];
    m[A[i]]++;
  }
  for (int i = 0; i < Q; i++) {
    int b, c;
    cin >> b >> c;
    ans += (ll)(c - b) * (ll)m[b];
    m[c] += m[b];
    m[b] = 0;
    cout << ans << endl;
  }
  return;
}

signed main() {
  fastio();
  solve();
  // int t; cin >> t; while(t--)solve();

  // int t; cin >> t;
  // for(int i=1;i<=t;i++){
  //   cout << "Case #" << i << ": ";
  //   solve();
  // }
  return 0;
}


Measured memory_bytes: 7968
#include<iostream>
#include <string> 
#include <vector>  
#include<math.h>
#include <algorithm>
#include<iomanip>
#define INF 1000000000
#define LM 55555
#define LL long long
using namespace::std;


long long Q,ch[501][501],mc,pc,p[100001],m[100001],n, bc, now, C, H, W, X[100000],K, Y, ans, r, l, numcon, N, M;
string S,s,a[101],b[101],c[101];
bool h,k[101];

int main() {
	cin >> N>>M>>Q;
	for (int i = 0; i < M; i++) {
		cin >> H >> W;
		ch[H][W]++;
	}
	N++;
	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			ch[i][j] += ch[i - 1][j];
		}
	}
	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			ch[i][j] += ch[i][j-1];
		}
	}

	for (int i = 0; i < Q; i++) {
		cin >> H >> W;
		cout<<ch[W][W]-ch[H-1][W]-ch[W][H-1]+ch[H-1][H-1]<<endl;
	}
	return 0;

}




Measured memory_bytes: 3200
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<climits>
using namespace std;
typedef long long int lli;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reg(i,a,b) for(int i=(a);i<=(b);i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=(b);i>=(a);i--)
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX

lli nc[100005];

lli fuct[100005];
#define MOD 1000000007

void init(){
	fuct[0]=1;
	reg(i,1,100004){
		fuct[i]=(((lli)(i))*fuct[i-1])%MOD;
	}
}

typedef struct{
	int n;
	int s[400005];
	void init(int in){
		n = 1;
		while(n<=in)n*=2;
		rep(i,n*2)s[i]=0;
	}
	void rupd(int k){
		if(k==0)return;
		s[k]+=1;
		rupd(k/2);
	}
	void upd(int k){
		rupd(k+n);
	}
	
	lli rsum(int l,int r,int k,int a,int b){
		if(a<=l && r<=b)return s[k];
		if(b<=l || r<=a)return 0;
		int m = (r+l)/2;
		return rsum(l,m,k*2,a,b) + rsum(m,r,k*2+1,a,b);
	}
	lli sum(int k){
		return rsum(0,n,1,0,k);
	}
		
} segtree;




int main(void){
	init();
	
	while(1){
		int n;
		scanf("%d",&n);
		if(n==0)break;
		segtree seg;
		seg.init(n);
		rep(i,n){
			nc[i]=i+1;
		}
		
		int r;
		scanf("%d",&r);
		rep(i,r){
			int a,b;
			scanf("%d%d",&a,&b);
			a--; b--;
			swap(nc[a],nc[b]);
		}
		/*
		rep(i,n){
			printf("%d ",nc[i]);
		}
		printf("\nns\n");*/
		lli ans=0;
		rep(i,n){
			lli nz = nc[i] - seg.sum(nc[i]) -1;
			ans = (ans + ((nz * fuct[n-i-1])%MOD))%MOD;
			//printf("%d  ..  nz .. %lld sum .. %lld ans .. %lld\n",i,nz,seg.sum(nc[i]),ans);
			seg.upd(nc[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 3624
//#include"bits/stdc++.h"
#include<algorithm>
#include<cassert>
#include<cmath>
#include<climits>
#include<iostream>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define ll long long
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define rep(i, j) FOR(i, 0, j, 1)
#define MP make_pair
#define PB push_back
#define endl "\n"
#define MOD 1000000007
#define DEB(x) cout<<"##"<<x<<"##"<<endl
const int INF=(int)2e9+9;
const int SIZE=(int)2e5+5;
//Brute force answers(BINARY SEARCH) symmetry
//Change perspective
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,k;
    cin>>n>>k;
    int ar[n];
    rep(i,n){
        cin>>ar[i];
    }   
    sort(ar,ar+n);
    int l=1,h=(int)1e9;
    while(h>=l){
        int mid=(h+l)/2;
        ll cnt=0;
        for(int i=0;i<n;i++){
            cnt+=ceil(ar[i]/(mid+0.0))-1;
        }   
        if(cnt>k){
            l=mid+1;
        }
        else{
            h=mid-1;
        }
    }
    cout<<l;
} 

Measured memory_bytes: 4300
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define PB push_back
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1510,mod=998244353;
inline void Add(int &x,int y) { x+=y; if(x>=mod) x-=mod; }
inline int Pow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*(ll)x%mod;
		x=x*(ll)x%mod,y>>=1;
	}
	return res;
}
int n;
char S[N][N];
vector<int> c[N][N];
int ty[N][N];
vector<int> G[N];
int v[N],vis[N],num;
void dfs(int u) {
	if(vis[u]) return;
	vis[u]=1,num+=v[u];
	for(int i=0;i<G[u].size();++i) dfs(G[u][i]);
}
int main() {
	rd(n);
	for(int i=1;i<n;++i) scanf("%s",S[i]+1);
	for(int i=0;i<=n;++i) {
		int x=0,y=i;
		int dx=1,dy=1;
		for(int ii=0;ii<((i>0&&i<n)?2*n:n);++ii) {
			c[x][y].PB(i);
			if(x+dx<0||x+dx>n) dx=-dx;
			if(y+dy<0||y+dy>n) dy=-dy;
			x+=dx,y+=dy;
		}
	}
	memset(ty,-1,sizeof(ty));
	for(int i=1;i<n;++i)
		for(int j=1;j<n;++j) if(S[i][j]!='?') {
			int x=c[i][j][0],y=c[i][j][1];
			if(ty[x][y]!=-1&&ty[x][y]!=(S[i][j]=='o')) {
				printf("0");
				return 0;
			}
			ty[x][y]=(S[i][j]=='o');
		}
	int ETOT[2]={0,0};
	for(int i=0;i<=n;++i)
		for(int j=i+2;j<=n;j+=2)
			if(ty[i][j]==-1) G[i].PB(j),G[j].PB(i),ETOT[i&1]++;
			else v[i]^=ty[i][j],v[j]^=ty[i][j];
	int ans=1;
	for(int d=0;d<2;++d) {
		int ntot=(n-d)/2+1;
		if(ntot&1) {
			int cnt=0;
			for(int i=d;i<=n;i+=2) if(!vis[i]) {
				cnt++,num=0;
				dfs(i);
				if(num&1) {
					printf("0");
					return 0;
				}
			}
			ans=ans*(ll)Pow(2,ETOT[d]-(ntot-cnt))%mod;
		}
		else ans=ans*(ll)Pow(2,ETOT[d])%mod;
	}
	printf("%d",ans);
	return 0;
}

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

#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'

typedef long long ll;
const int N=2002;
const ll mod=1e9+7;
ll fact[N], invf[N];

ll bigmod(ll a, ll b, ll mod){
  a %= mod;
  ll ret = 1;
  while(b){
    if(b&1) ret = ret*a%mod;
    a = a*a%mod;
    b >>= 1;
  }
  return ret;
}

void pre(){
  fact[0]=1;
  for (int i = 1; i < N; ++i){
    fact[i]=fact[i-1]*i%mod;
  }
  invf[N-1]=bigmod(fact[N-1], mod-2, mod);
  for (int i = N-2; i >= 0; --i){
    invf[i] = invf[i+1]*(i+1)%mod;
  }
}

ll nCr(ll n, ll r){
  return fact[n]*invf[n-r]%mod*invf[r]%mod;
}

ll ways(ll n, int k){
  return nCr(n-1, k-1);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  
  pre();
  ll n; cin >> n;
  ll ans = 0;
  for (ll i = 1; 3*i <= n; ++i){
    ans += ways(n-2*i, i);
    if(ans>=mod)  ans-=mod;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3668
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_set>
#include <deque>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>
#define PP pair<ll, P>

ll n, ans[210000], now[4], s[4];
vector<ll> c[2];
vector<ll> g[210000];

bool used[210000];
void dfs(ll a, ll b) {
	used[a] = true;
	c[b].push_back(a);
	REP(i, g[a].size()) if (!used[g[a][i]])dfs(g[a][i], 1 - b);
}

void solve(ll a, ll b) {
	REP(i, c[a].size()) {
		REPO(j, 3) {
			if (j == b)continue;
			if (now[j] < s[j]) {
				ans[c[a][i]] = now[j] * 3 + j;
				now[j]++;
				break;
			}
		}
	}
}
void solve2(ll a) {
	REP(i, c[a].size()) {
		ans[c[a][i]] = now[3] * 3 + 3;
		now[3]++;
	}
}
int main() {
	cin >> n;
	REP(i, n - 1) {
		ll a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0, 0);
	REPO(i, 3)s[i] = (n + 3 - i) / 3;
	if (c[0].size() <= n / 3) {
		solve2(0);
		solve(1, 0);
	}
	else if (c[1].size() <= n / 3) {
		solve2(1);
		solve(0, 0);
	}
	else {
		solve(0, 1);
		solve(1, 2);
	}
	REP(i, n) {
		if (i != 0)cout << " ";
		cout << ans[i];
	}
	cout << endl;
}



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

using namespace std;

int n, a[100005], b[100005];

int main () {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		b[a[i]] = i;
	}
	for(int i = 1; i <= n; i++) {
		cout << b[i] << " ";
	}
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
#include <vector>
#include <chrono>
#include <cstdlib>
#include <bitset>
using namespace std;
int main() {
    int x, a;
    cin >> x >> a;
    if(x < a) cout << 0 << endl;
    else cout << 10 << endl;
   
}

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

int main() {
  string s;
  cin >> s;
  if(s == "ABC") cout << "ARC" << endl;
  else cout << "ABC" << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
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(){
  cout << fixed << setprecision(15);
  int n, m; cin >> n >> m;
  vi p(m); rep(i, m) cin >> p[i];

  ll ans = 0;
  sort(all(p));
  vi d(m - 1);
  rep(i, m - 1) d[i] = p[i + 1] - p[i];
  sort(all(d));
  rep(i, m - n) ans += d[i];

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
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;
}
 
using namespace std;

//ここから

using P=pair<int,int>;
void solve(){
  int l;
  cin>>l;
  int mul=2,cnt=1;
  while(mul*2<=l){
    mul*=2;
    ++cnt;
  }
  vector<vector<P>>g(cnt);
  rep(i,cnt){
    g[i].eb(i+1,0);
    g[i].eb(i+1,(int)pow(2,i));
  }
  int lb=(int)pow(2,cnt);
  for(int i=cnt-1;i>=0;--i){
    int x=pow(2,i)-1;
    if((l-1)-x>=lb){
      g[i].eb(cnt,l-1-x);
      l-=x+1;
    }
  }
  int edge=0;
  for(auto e:g){
    edge+=e.size();
  }
  cout<<cnt+1<<" "<<edge<<endl;
  rep(i,cnt){
    for(auto e:g[i]){
      cout<<i+1<<" "<<e.first+1<<" "<<e.second<<endl;
    }
  }
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define INT long long
using namespace std;
INT n, t, ans = 1;

INT lcm(INT a, INT b)
{
    INT g = __gcd(a, b);
    return a/g*b;
}

int main()
{
    cin>>n;
    for(int i = 0 ; i < n ; i++ )
    {
        cin>>t;
        ans = lcm(t, ans);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int>   vi;
typedef vector<long long> vll;
typedef vector<pair<int,int> > vii;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pq priority_queue
#define mii map<int,int>
#define sf1(x) scanf("%d",&x)
#define sf2(x,y) scanf("%d %d",&x,&y)
#define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z)
int inf = (1e9) + 7;
int mod = 998244353;

int cnt[100005];

int main(){

	int a,b,c;
	sf3(a,b,c);

	if(a == b) printf("%d\n",c);
	if(c == b) printf("%d\n",a);
	if(a == c) printf("%d\n",b);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 100000000000000000
#define EPS 1e-9
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fr first
#define se second
#define pb push_back

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;

vector<vector<int>>dp(30,vector<int>(500,0));

signed main(){
  int a;
  vector<int> input;
  while(true){
    cin>>a;
    if(a==0)break;
    input.push_back(a);
  }
  vector<int> pollock(200),dp0(1000010),dp1(1000010);

  REP(i,0,200){
    pollock[i]=(i+1)*(i+2)*(i+3)/6;
  }
  dp0[0]=dp1[0]=0;
  REP(i,1,1000002){
    dp0[i]=dp1[i]=i;
    REP(j,0,200){
      if(i<pollock[j])break;
      dp0[i]=min(dp0[i],dp0[i-pollock[j]]+1);
      if(pollock[j]%2==1){
        dp1[i]=min(dp1[i],dp1[i-pollock[j]]+1);
      }
    }
  }
  // debug(dp1)
  each(v,input){
    cout<<dp0[v]<<' '<<dp1[v]<<"\n";
  }


}



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


int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());
    int A = 0;
    int B = 0;
    REP(i, N) {
        if (i %2 == 0) A += a[i];
        else B += a[i];
    }
    cout << A - B << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iterator>
#include <tuple>
using namespace std;
using ll = long long;

int main()
{
  int n, a, b;
  cin >> n >> a >> b;
  string s;
  cin >> s;

  int sum = 0;
  int cntb = 0;
  for (int i = 0; i < s.size(); ++i)
  {
    bool flag = false;
    if (s[i] == 'a')
    {
      if (sum < a + b)
      {
        flag = true;
        sum++;
      }
      else
        flag = false;
    }
    else if (s[i] == 'b')
    {
      if (sum < a + b && cntb < b)
      {
        flag = true;
        cntb++;
        sum++;
      }
      else
        flag = false;
    }
    cout << (flag ? "Yes" : "No") << endl;
  }

  return 0;
}

Measured memory_bytes: 896