akhauriyash/Code-Regression huggingface dataset:
// Best practice
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <functional> // for less 
 
#define int         long long
#define pb          push_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD         1000000007
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; 
 
#define fbo find_by_order
#define ook order_of_key
 
signed main() {
   tezz
   
   int n,k,q,p;
   cin >> n >> k >> q;
   vector<int> a(n+1,k-q);
   for(int i=0; i<q; i++){
       cin >> p;
       a[p]++;
   }
   for(int i=1; i<=n; i++){
       if(a[i]>0)cout << "Yes";
       else cout << "No";
       cout << endl;
   }
   
   return 0;
}
 


Measured memory_bytes: 1408
#include <stdio.h>
#include <bits/stdc++.h>
#include <cctype>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int a = 1000;
    if(n <= 1000){
        a -= n;
    }else if(n > 1000 && n <= 2000){
        a *= 2;
        a -= n;
    }else if(n > 2000 && n <= 3000){
        a *= 3;
        a -= n;
    }else if(n > 3000 && n <= 4000){
        a *= 4;
        a -= n;
    }else if(n > 4000 && n <= 5000){
        a *= 5;
        a -= n;
    }else if(n > 5000 && n <= 6000){
        a *= 6;
        a -= n;
    }else if(n > 6000 && n <= 7000){
        a *= 7;
        a -= n;
    }else if(n > 7000 && n <= 8000){
        a *= 8;
        a -= n;
    }else if(n > 8000 && n <= 9000){
        a *= 9;
        a -= n;
    }else if(n > 9000 && n <= 10000){
        a *= 10;
        a -= n;
    }else{}
    
    cout << a << endl;
}



Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>


class SegNearTree {
	std::vector<std::vector<std::vector<int>>> vec;
	int inner_find(int depth, int from, int until, const int target) const {
		if (from >= until) return INT_MAX;
		auto length = 1 << depth;
		auto mid = (from + length - 1) / length * length;
		if (mid + length <= until) {
			return std::min({ inner_find(depth, from, mid, target), inner_find(depth, mid + length, until, target), take_nearest(depth, mid / length, target) });
		}
		else if (mid < until) {
			return std::min(inner_find(depth - 1, from, mid, target), inner_find(depth - 1, mid, until, target));
		}
		else {
			return inner_find(depth - 1, from, until, target);
		}
	}

	int take_nearest(int depth, int position, const int target) const {
		auto upper = std::lower_bound(vec[depth][position].begin(), vec[depth][position].end(), target);
		if (upper == vec[depth][position].begin()) return std::abs(target - *upper);
		if (upper == vec[depth][position].end()) return std::abs(target - *std::prev(upper));
		return std::min(std::abs(target - *upper), std::abs(target - *std::prev(upper)));
	}
public:
	SegNearTree(const std::vector<int>& state) :vec{ std::vector<std::vector<int>>() } {
		for (const auto a : state) vec.back().push_back({ a });
		while (vec.back().size() > 1) {
			std::vector<std::vector<int>> last;
			for (auto i = 0; i * 2 + 1 < vec.back().size(); ++i) {
				std::vector<int> v; v.reserve(vec.back()[i * 2].size() + vec.back()[i * 2 + 1].size());
				std::copy(vec.back()[i * 2].begin(), vec.back()[i * 2].end(), std::back_inserter(v));
				std::copy(vec.back()[i * 2 + 1].begin(), vec.back()[i * 2 + 1].end(), std::back_inserter(v));
				std::sort(v.begin(), v.end());
				last.push_back(std::move(v));
			}
			vec.push_back(std::move(last));
		}
	}
	int find_nearest(int from, int until, const int target) { return inner_find(vec.size() - 1, from, until, target); }
};

int main() {
	int n; std::cin >> n;
	std::vector<int> beans(n); for (auto& b : beans) std::cin >> b;
	SegNearTree seg(beans);
	int q; std::cin >> q;
	for (auto i = 0; i < q; ++i) {
		int l, r, d; std::cin >> l >> r >> d;
		std::cout << seg.find_nearest(l, r + 1, d) << '\n';
	}
}



Measured memory_bytes: 19152
#include<iostream>
#include<algorithm>
#include<vector>

#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long typeLong;

using namespace std;

const int INF = 100;

int main()
{

	int r, c;

	cin >> r >> c;

	int array[110][110];

	rep(i, r)rep(j, c)cin >> array[i][j];

	rep(i, r) {

		int rowSum = 0;

		rep(j, c) {
			cout << array[i][j] << " ";
			rowSum += array[i][j];
		}
		array[i][c] = rowSum;
		cout << rowSum << endl;
	}

	rep(i, c + 1) {
		int colSum = 0;
		rep(j, r) {
			colSum += array[j][i];
		}
		array[r][i] = colSum;
		cout << colSum;

		if (i != c)cout << " ";
	}

	cout << endl;

	return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

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


ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}


int main(){
    int n;
    const int A = 1000005;
    cin >> n;
    vector<int>a(A,0);
    vector<int>b(n);
    rep(i,n){
        int x;
        cin >> x;
        b[i] = x;
        a[x]++;
    }

    bool flag = true;

    for(int i = 2; i < A; i++){
        int cnt = 0;

        for(int j = i; j < A; j+=i){
            cnt += a[j];
            if(cnt > 1){
                flag = false;
            }
        }
    }


    if(flag){
        cout << "pairwise coprime" << endl;
        return 0;
    }

    int x = 0;
    rep(i,n){
        x = gcd(x,b[i]);
    }

    if(x == 1){
        cout << "setwise coprime" << endl;
        return 0;
    }

    cout << "not coprime" << endl;


    return 0;
}


Measured memory_bytes: 11176
n = int(input())
rem = n
ans = ""
step = 0
if rem == 0:
    ans = "0"
while(rem!=0):
    dig = (-2)**(step+1)
    if rem%dig == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans
        rem = rem - (-2)**(step)
    step+=1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <sstream>
typedef long long ll;
using namespace std;

int main(int argc, char const *argv[])
{
    string str;
    std::cin >> str;
    char y = str[0];
    char a = str[1];
    char k = str[2];
    char i = str[3];
    if (y == 'Y' && a == 'A' && k == 'K' && i == 'I') {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << '\n';
    }
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x]==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x==y:
            return

        if self.rank[x]<self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x]==self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x)==self.find(y)

n,m = map(int, input().split())
p = [int(x) for x in input().split()]
uf = UnionFind(n+1)
for _ in range(m):
    x,y = map(int, input().split())
    uf.unite(x,y)

cnt = 0
for i in range(1,n+1):
    if uf.same(i,p[i-1]):
        cnt += 1

print(cnt)


Measured memory_bytes: 14320
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, n = list(map(int, readline().split()))
    ab = [[0] * 2 for _ in range(n)]

    for i in range(n):
        ab[i] = list(map(int, readline().split()))

    dp = [INF] * (h + 1)
    dp[0] = 0

    for i in range(h + 1):
        mpcur = dp[i]
        for a, b in ab:
            hpnext = min(i + a, h)
            dp[hpnext] = min(mpcur + b, dp[hpnext])

    print(dp[h])


if __name__ == '__main__':
    main()


Measured memory_bytes: 42972
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
#define rep_r(i,s,n)for(int i = n-1;i>=s;i--)
#define rep_re(i,s,n)for(int i = n;i>=s;i--)
using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_N = 100001;

int  main() {
	string s, t; cin >> s >> t;
	ll ans = 0;
	ans += s[0] == t[0];
	ans += s[1] == t[1];
	ans += s[2] == t[2];

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

Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long int ll;
int main(){
	int N, L;
	ll a[100000];
	cin >> N >> L;
	for(int i = 0; i < N; i++) cin >> a[i];
	bool flag = false;
	int last_tie;
	for(int i = 0; i < N - 1; i++){
		if(a[i] + a[i + 1] >= L){
			flag = true;
			last_tie = i;
		}
	}
	if(!flag) cout << "Impossible" << endl;
	else{
		cout << "Possible" << endl;
		for(int i = 0; i < last_tie; i++){
			cout << i + 1 << endl;
		}
		for(int i = N - 1; i > last_tie; i--){
			cout << i << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

int main(){
	int n;
	int a[1010][1010];
	int ptr[1010]={};
	int ans=0;
	scanf("%d",&n);
	rep(i,0,n)rep(j,0,n-1){
		scanf("%d",&a[i][j]);
		a[i][j]--;
	}
	while(1){
		ans++;
		int flag[1010]={};
		int temp=0,temp2=n;
		rep(i,0,n){
			if(ptr[i]<n-1){
				if(!flag[i]){
					int t=a[i][ptr[i]];
					if(a[t][ptr[t]]==i&&!flag[t]){
						temp=flag[i]=flag[t]=1;
						ptr[i]++;
						ptr[t]++;
					}
				}
			}else temp2--;
		}
		if(!temp2){
			printf("%d",ans-1);
			return 0;
		}
		if(!temp){
			puts("-1");
			return 0;
		}
	}
}


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

int main(){
  int H,W;
  cin>>H>>W;
  vector<vector<int>> p(H,vector<int>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>p[i][j];
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      int a;
      cin>>a;
      p[i][j]=abs(p[i][j]-a);
    }
  }
  vector<vector<vector<int>>> dp(H,vector<vector<int>>(W,vector<int>(12800)));
  dp[0][0][p[0][0]]=1;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(i==H-1&&j==W-1){
        continue;
      }
      for(int k=0;k<12800;k++){
        if(!dp[i][j][k]){
          continue;
        }
        if(i<H-1){
          dp[i+1][j][abs(k-p[i+1][j])]=1;
          dp[i+1][j][k+p[i+1][j]]=1;
        }
        if(j<W-1){
          dp[i][j+1][abs(k-p[i][j+1])]=1;
          dp[i][j+1][k+p[i][j+1]]=1;
        }
      }
    }
  }
  int Z=0;
  while(true){
    if(dp[H-1][W-1][Z]){
      cout<<Z<<endl;
      break;
    }
    Z++;
  }
}

Measured memory_bytes: 327704
#include <bits/stdc++.h>
#define int long long
#define range(i, a, b) for(auto i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;
const int INF = sizeof(int) == sizeof(long long) ? LONG_LONG_MAX : INT_MAX;
const int MOD = 1000000007;
const long double EPS = 1e-8;

signed main() {
	int a, b;
	cin >> a >> b;
	int cnt = 0;
	range (i, a , b + 1) {
		string tmp = to_string(i);
		string rev = tmp;
		reverse(rev.begin(), rev.end());
		cnt += rev == tmp;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

int main() {
	int a, b; cin >> a >> b;
	cout << round((a+b)/2.0) << endl; 
	return 0;
} 

Measured memory_bytes: 768
n = int(raw_input())
A = [0]
B = range(1, n)
a = [[0 for i in xrange(0,n)] for j in xrange(0,n)]

for i in xrange(0,n):
 a[i] = map(int,raw_input().split())

count = 0
while B != []:
 smin = 2001
 for i in A:
  for j in B:
   if 0 <= a[i][j] < smin:
    smin = a[i][j]
    addA = j
 A.append(addA)
 B.remove(addA)
 count += smin

print count

Measured memory_bytes: 6408
#include <algorithm>
#include <numeric>
#include <map>
#include <vector>
#include <cmath>
#include <map>
#include <iostream>

using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> PP;

vector<int> primes;
const int maxn = 1121, maxk = 15;
map<PP, int> memo;
//int memo[maxn][maxk][maxn];
int l;

int rec(int n, int k, int p) {
  //  printf("%d %d %d\n", n, k ,p);
  if (k < 0) return 0;
  if (n == 0 && k == 0) return 1;
  PP tri = PP(P(n, k), p);
  if (memo.count(tri) == 0) {
	int res = 0;
	for (int i = 0; i < l && primes[i] < p && primes[i] <= n; i++) {
	  res += rec(n-primes[i], k-1, primes[i]);
	}
	memo[tri] = res;
  }
  return memo[tri];
}

int main() {
  vector<bool> nonprime(maxn, false);
  for (int i = 2; i < maxn; i++) {
	if (!nonprime[i]) {
	  primes.push_back(i);
	  for (int j = i + i; j < maxn; j += i)
		nonprime[j] = true;
	}
  }
  l = primes.size();
  //  fill_n(memo[0][0], maxn * maxn * maxk, -1);
  //  for (int i = 0; i < maxn; i++)
  //	memo[0][0][i] = 1;

  while (true) {
	int n, k;
	cin >> n >> k;
	if (n == 0 && k == 0) break;
	cout << rec(n, k, n+1) << endl;
  }
}

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

using namespace std;

#define f first
#define s second
#define pb push_back
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int INF = 0x3F3F3F3F;
const ll INFL = 0x3F3F3F3F3F3F3F3FLL;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 5;

int N, K;
int arr[MAX];

int main() {
    
    scanf("%d%d", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
    
    int pos = N + 1;
    for (int i = 1; i <= N; i++) {
        if (arr[i] >= 0 && pos == N + 1) {
            pos = i;
        }
    }
    int ans = INF;
    for (int i = 0; i <= K; i++) {
        //printf("%d\n", pos);
        if (pos + K - i - 1 <= N && pos - i >= 1 && K - i - 1 >= 0) {
            int a = i == 0 ? 0 : abs(arr[pos - i]);
            int b = i == pos ? 0 : arr[pos + K - i - 1];
            //printf("%d %d\n", a, b);
            ans = min(ans, min(a, b) * 2 + max(a, b));
        }
    }
    if (pos - K >= 1) {
        ans = min(ans, abs(arr[pos - K]));
    }
    if (pos + K - 1 <= N) {
        ans = min(ans, arr[pos + K - 1]);
    }
    printf("%d\n", ans);
    
    return 0;
}


Measured memory_bytes: 640
N,M = map(int,input().split())
 
m = []
for i in range(M):
    m.append(list(map(int,input().split())))
for i in range(10**N):
    a = str(i)
    
    if i >= 10**(N-1):
            
        for j in range(M):
            try:
                
                if a[m[j][0]-1] == str(m[j][1]):
                    True
                
                else:
                    break
            except:
                break
                
            if j == M-1:
                print(i)
                exit()
                
if M==0:
    if N == 1:
        print(0)
        
    else:
        print(10**(N-1))
        
    exit()

elif M==1:
    if N == 1:
        m == [[1,0]]
        print(0)
        exit()


print(-1)

Measured memory_bytes: 3064
from collections import deque

b=deque()

n=int(input())
a=[int(i) for i in input().split()]

for i in range(n):
    if i%2==0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
b=list(b)

if n%2==1:
    b=b[::-1]
b=[str(i) for i in b]

print(" ".join(b))


Measured memory_bytes: 39492
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a)
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;

inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=2000005;
//i_am_noob
int n,fact[maxn],invfact[maxn],pow25[maxn],ans=0;
string str;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	fact[0]=invfact[0]=1,pow25[0]=1;
	rep2(i,1,maxn) fact[i]=fact[i-1]*i%MOD;
	rep2(i,1,maxn) invfact[i]=inverse(fact[i]);
	rep2(i,1,maxn) pow25[i]=pow25[i-1]*25%MOD;
	cin >> n >> str;
	n+=sz(str);
	rep2(i,sz(str),n+1) ans=add(ans,fact[n]*invfact[n-i]%MOD*invfact[i]%MOD*pow25[n-i]%MOD);
	print1(ans);
	return 0;
}


Measured memory_bytes: 51140
# 休憩review
# League
from collections import deque
N = int(input())
G = [[] for i in range(N**2+1)]
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(1, N-1):
        _from, _to = a[j-1], a[j]
        G[N*min(i+1, _from)-N+max(i+1, _from)
          ].append(N*min(i+1, _to)-N+max(i+1, _to))


In = [0 for i in range(N**2+1)]  # In[node] = node に入る入次数
for i in range(1, N**2+1):
    for node in G[i]:
        In[node] += 1


stack = deque()
for i in range(1, N**2+1):
    if In[i] == 0:
        stack.append(i)  # stack := 入次数が0になった点を入れておく


Removed = [False for i in range(N**2+1)]  # 考慮されたか
cnt = [1 for i in range(N**2+1)]


while stack:
    x = stack.popleft()
    Removed[x] = True
    for node in G[x]:
        In[node] -= 1
        if In[node] == 0:
            cnt[node] += cnt[x]
            stack.append(node)


all_checked = all(Removed[node] == True for node in range(1, N**2+1))
if all_checked:
    answer = max(cnt)
    print(answer)
    exit()
print(-1)

Measured memory_bytes: 239964
#include<atcoder/all>
using namespace atcoder;

#include<bits/stdc++.h>
#include<array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int N;
int A[200000];
int I[200000];

int main() {
    scanf("%d", &N);
    rep(i, N) {
        int x, y; scanf("%d%d", &x, &y); x--; y--;
        A[x] = y;
        I[i] = x;
    }

    dsu G(N);

    deque<int> Q;
    rep(i, N) {
        int p = i;
        if (Q.size()) if (A[Q.back()] < A[i]) {
            p = Q.back();
            while (Q.size()) {
                if (A[Q.back()] < A[i]) {
                    G.merge(Q.back(), i);
                    Q.pop_back();
                }
                else break;
            }
        }
        Q.push_back(p);
    }

    rep(i, N) printf("%d\n", G.size(I[i]));

    return 0;
}

Measured memory_bytes: 5704
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    A, B = map(int, readline().split())
    if A%2==0 and B%2==0:
        count_1 = (B-A)//2
        ans = (count_1%2)^B
    elif A%2==0 and B%2==1:
        count_1 = (B-A+1)//2
        ans = count_1%2
    elif A%2==1 and B%2==0:
        count_1 = (B-A-1)//2
        ans = A^B^(count_1%2)
    else:
        count_1 = (B-A)//2
        ans = A^(count_1%2)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
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() {
    int x,n;cin>>x>>n;
    vec p(n+1);
    rep1(i,n) cin>>p[i];

    vec q(102,101);
    q[0]=0;

    rep1(i,101){
        bool b=true;
        rep1(j,n){
            if(i==p[j]) b=false;
        }
        if(b){q[i]=i;}
    }


    int mn=1e3, mn2=1e3,a;
    for(int i=0; i<=101; i++){
        mn= min(mn,abs(x-q[i]));
        if(mn<mn2){
            a= q[i];
        }
        mn2=mn;
    }

    cout<<a<<endl;

}

Measured memory_bytes: 3604
S = input()
A = "abcdefghijklmnopqrstuvwxyz"
if len(S)<26:
    for c in A:
        if c not in S:
            print(S+c)
            break
elif S=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    for i in range(24,-1,-1):
        for c in A:
            if c not in S[:i] and c>S[i]:
                print(S[:i]+c)
                break
        else:
            continue
        break


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<int,int> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


struct robot{
	int dir;
	int x;
	int y;
	int cost;
	robot(int a,int b,int c,int d):dir(a),x(b),y(c),cost(d){}
};
int w,h;
int s[30][30];
int dp[30][30][4];
int c[4];
vector<int> ans;
queue<robot> q;

void bfs(){
	while(q.size()){
		robot aa=q.front();q.pop();
		for(int i=0;i<4;i++){
			int t=(i+aa.dir)%4;
			int nx=aa.x+dx[t];
			int ny=aa.y+dy[t];
			if(!(0<=nx&&nx<w&&0<=ny&&ny<h)){
				continue;
			}
			if(i==s[aa.y][aa.x]){
				if(aa.cost<dp[ny][nx][t]){
					q.push(robot(t,nx,ny,aa.cost));
					dp[ny][nx][t]=aa.cost;
				}
			}else{
				if(aa.cost+c[i]<dp[ny][nx][t]){
					q.push(robot(t,nx,ny,aa.cost+c[i]));
					dp[ny][nx][t]=aa.cost+c[i];
				}
			}
		}
	}
	return;
}
			
int main(){
	while(1){
		while(q.size())q.pop();
		cin>>w>>h;
		if(w==0&&h==0)return 0;
		for(int i=0;i<30;i++){
			for(int j=0;j<30;j++){
				for(int k=0;k<4;k++){
					dp[i][j][k]=INF;
				}
			}
		}
		dp[0][0][1]=0;
		q.push(robot(1,0,0,0));
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>s[i][j];
			}
		}
		for(int i=0;i<4;i++){
			cin>>c[i];
		}
		bfs();
		
		ans.push_back(min(dp[h-1][w-1][1],dp[h-1][w-1][2]));
		cout<<min(dp[h-1][w-1][1],dp[h-1][w-1][2])<<endl;
	}
	/*for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<endl;
	}*/
	return 0;
}

	


Measured memory_bytes: 3156
import java.util.*;

import sun.font.TrueTypeFont;

import static java.lang.System.out;

public class Main{
   public static Scanner sc = new Scanner(System.in);
   public static void main(String args[]){
      // String str = sc.next();
      // int i = str.split("x").length;
      // out.println(700 + i * 100);

      int N = sc.nextInt();
      int gram = sc.nextInt();
      int[] array = new int[N];
      int count = N; //個数
      int cost = 0; //容量
      for (int i = 0; i < N; i++) {
          array[i] = sc.nextInt();
      }
      Arrays.sort(array);
      for(int make : array) {
         cost += make;
      }
      int row = array[0];
      while (row + cost <= gram) {
         cost += row;
         count++;
      }

      out.println(count);


   }

}

Measured memory_bytes: 21844
//AtCoder ABC098 A - Add Sub Mul
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;

int main() {
    ll A,B; cin>>A>>B;
    ll ans=max(A+B,A-B);
    ans=max(ans,A*B);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
    {ios::sync_with_stdio(0);
    cin.tie(0);
    long long int n,k;
    cin>>n>>k;
    long long int p[n];
    for(long long int i=0;i<n;i++){cin>>p[i];p[i]--;}
    long long int c[n];
    for(long long int i=0;i<n;i++){cin>>c[i];}
    unordered_map<long long int,long long int> mp;
    long long int maxa=-1e18;
    for(long long int i=0;i<n;i++)
        {if(mp[p[i]]){continue;}
        vector<long long int> v;
        long long int z=p[i];
        long long int sumi=0;
        vector<long long int> yo;
        while(1)
            {v.push_back(z);
            yo.push_back(z);
            sumi=sumi+c[z];
            mp[z]++;
            z=p[z];
            if(mp[z]){break;}
            }
        for(auto x:yo){v.push_back(x);}
        long long int yu=v.size();
        long long int m=yu/2;
        //for(auto x:v){cout<<x<<" ";}
        //cout<<"\n";
        //cout<<sumi<<"\n";
        long long int currmax=-1e18;
        for(long long int len=1;len<=min(k,m);len++)
            {long long int currsum=0;
            for(long long int j=0;j<len;j++){currsum+=c[v[j]];}
            currmax=max(currmax,currsum);
            long long int wtf=(k-len)/m;
            currmax=max(currmax,currsum+wtf*sumi);
            for(long long int j=len;j<yu;j++)
                {currsum=currsum+c[v[j]]-c[v[j-len]];
            currmax=max(currmax,currsum);
            currmax=max(currmax,currsum+wtf*sumi);}
            }
        maxa=max(maxa,currmax);
        }
    cout<<maxa<<"\n";
    }

Measured memory_bytes: 4056
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long LL;
const int N=100005;
int n,sz[N],f[N],q[N];LL ans;
int pp,lnk[N],nxt[N*2],to[N*2],w[N*2];
void ae(int k1,int k2,int k3){to[++pp]=k2,w[pp]=k3,nxt[pp]=lnk[k1],lnk[k1]=pp;} 
void dfs(int k1,int k2){
	sz[k1]=1;
	for(int i=lnk[k1];i;i=nxt[i])if(to[i]!=k2){
		dfs(to[i],k1);
		sz[k1]+=sz[to[i]];
		if(sz[to[i]]>f[k1])f[k1]=sz[to[i]];
		ans+=2LL*min(sz[to[i]],n-sz[to[i]])*w[i];
	}
	if(n-sz[k1]>f[k1])f[k1]=n-sz[k1];
}
int main(){
	scanf("%d",&n);
	rep(i,2,n){int k1,k2,k3;scanf("%d%d%d",&k1,&k2,&k3),ae(k1,k2,k3),ae(k2,k1,k3);}
	dfs(1,0);
	q[*q=1]=1;
	rep(i,2,n){
		if(f[i]<f[q[*q]])q[*q=1]=i;
		else if(f[i]==f[q[*q]])q[++*q]=i;
	}
	if(*q==1){
		LL now=0X7FFFFFFFFFFFFFFFLL;
		for(int i=lnk[q[1]];i;i=nxt[i]){
			now=min(now,(LL)w[i]);
		}
//		printf(">>> %lld %lld\n",ans,now);
		printf("%lld\n",ans-now);
	}else{
//		printf("q:");
//		rep(i,1,*q)printf("%d ",q[i]);puts("");
		assert(*q==2);
		for(int i=lnk[q[1]];i;i=nxt[i])if(to[i]==q[2]){
			printf("%lld\n",ans-w[i]);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 7808
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N, Q := ReadInt(), ReadInt()
	a := ReadInts(N)
	for ; Q > 0; Q-- {
		k := ReadInt()
		sum := 0
		r := 0
		ans := 0
		// 尺取法 (two pointers)
		for l := 0; l < N; l++ {
			for r < N && sum+a[r] <= k {
				sum += a[r]
				r++
			}
			ans += r - l
			if r == l {
				r++
			} else {
				sum -= a[l]
			}
		}
		fmt.Println(ans)
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}



Measured memory_bytes: 3548
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
var n,s,a;
console.log(main());
function main(){
  n = o.a();
  s = o.l();
  s.sort((a,b)=>b-a);
  a = xArray(0,1<<n);
  a[0] = 1;
  return bfs([[s[0],1]])?"Yes":"No";
}

function bfs(b){
  var l = b.length;
  var al = a.length;
  if(l === a.length)return 1;
  var q = b.concat(), c = 1;
  for(var i = 0; i < l; i++){
    if(c < b[i][1])c = b[i][1];
    for(; c < al; c++){
      if(a[c])continue;
      if(s[c] < b[i][0])break;
    }
    if(c === al)return 0;
    a[c] = 1;
    q.push([s[c],++c]);
  }
  return bfs(q.sort((a,b)=>b[0]-a[0]));
}

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

using namespace std;



int main()
{
    std::ios::sync_with_stdio(false);
    int n,w;
    cin >> n >> w;
    vector<long long> wt(n),val(n);
    for(int i = 0;i < n;i++)
    {
        cin >> wt[i] >> val[i];
    }
    long long dp[n+1][w+1];
    for(int i = 0;i <= n;i++)
    {
        for(int j = 0;j <= w;j++)
        {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= w;j++)
        {
            if(j >= wt[i-1])
                dp[i][j] = max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}

Measured memory_bytes: 79232
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define mod 1000000007
#define ft cout<<"for test"<<endl;
#define pi 2*acos(0.0)
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,i,j;
    cin>>n>>m;
    ll sum=0;
    for(i=0; i<m; i++)
    {
        cin>>j;
        sum+=j;
    }
    if(sum>n)cout<<-1<<endl;
    else cout<<n-sum<<endl;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7,MAX = 1e5;

int main()
{
	int n;
	cin >> n;
	int l=0,r=0;
	for(int i =0 ;i<n;i++)
	{
		string s,t;
		cin >> s >> t;
		if(s>t)
		l+=3;
		else if(t>s)
		r+= 3;
		else 
		{
			l++;r++;
		}
	}
	cout<<l<<' '<<r<<endl;
	return 0;
}


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

int main(){
  int N;
  cin >> N;

  string S;
  cin >> S;

  int Q;
  cin >> Q;

  for(int q = 0; q < Q; q++){
    int k;
    cin >> k;

    long long ans = 0;
    long long d_cnt = 0, dm_cnt = 0, m_cnt = 0;
    for(int i = 0; i < S.length(); i++){
      if(i - k >= 0 && S[i - k] == 'D'){
        d_cnt--;
        dm_cnt -= m_cnt;
      }
      if(i - k >= 0 && S[i - k] == 'M'){
        m_cnt--;
      }
      if(S[i] == 'D'){
        d_cnt++;
      }
      if(S[i] == 'M'){
        dm_cnt += d_cnt;
        m_cnt++;
      }
      if(S[i] == 'C'){
        ans += max(0LL, dm_cnt);
      }
    }

    cout << ans << endl;
  }
}


Measured memory_bytes: 1912
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a=0,b=0,c=0,d=0,e=0,f=0,g=0;
	cin>>a>>b>>c>>d;
    e=a-b;
    f=a-c;
    g=b-c;
    if(f<0)
    {
    	f=-f;
	}
	if(e<0)
	{
		e=-e;
	}
	if(g<0)
	{
		g=-g;
	}
	if(f<=d)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	if(e<=d && g<=d)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 764
#include<iostream>
#include<cmath>
using namespace std;
int main() {
	int n, a, b, c, d;
	while (cin >> n) {
		int cnt = 0;
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				for (int k = 0; k <= 9; k++) {
					for (int l = 0; l <= 9; l++) {
						if (i + j + k + l == n) cnt++;
					}
				}
			}
		}
		cout << cnt << endl;
	}
	cin >> n;
}

Measured memory_bytes: 3024
cnt500 = int(input())
cnt100 = int(input())
cnt50 = int(input())
X = int(input())

all = []
for a in range(cnt500+1):
    for b in range(cnt100+1):
        for c in range(cnt50+1):
            all.append(a*500 + b*100 + c*50)
print(all.count(X))

Measured memory_bytes: 8404
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(container) container.begin(),container.end()
#define fast ios::sync_with_stdio(0); cin.tie(0)
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #endif
#define int long long
const int mod = 1e9+7;  
int power(int a,int b) { if(b==0) return 1; int res = power(a,b/2); if(b&1) return res * res * a; else return res * res; }


bool isPalindrome(string &s){
  string temp = s;
  reverse(all(temp));
  if(s==temp) return true;
  else return false;
}

string substring(string s,int start,int end){
  string temp = "";
  for(int i=start;i<end;i++) temp+=s[i];
  return temp;
}

int32_t main(){
    
  fast;
  string s; cin >> s;
  int n = s.size();

  string s1 = s;
  string s2 = substring(s,0,(n-1)/2);
  string s3 = substring(s,(n+3)/2-1,n);

  if(isPalindrome(s1)&&isPalindrome(s2)&&isPalindrome(s3)){
    cout << "Yes\n";
  }else{
    cout << "No\n";
  }

  

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int a, b, c, d, e;
  scanf("%d", &e);
  a=e/100;
  b=e-100*a;
  if(a>=1&&a<=12)
  {
  	if(b>=1&&b<=12)
  	printf("AMBIGUOUS");
  	else
  	printf("MMYY");
  }
  else
  {
  	if(b>=1&&b<=12)
  	printf("YYMM");
  	else
  	printf("NA");
  }
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define ABS(a,b) max(a,b) - min(a,b)

int dp[210000];
int main() {
	REPO(i, 200000) dp[i] = INF;
	int n;
	cin >> n;
	REP(i, n) {
		int now = 1;
		REP(j, INF) {
			if (now > 100000)break;
			dp[i + now] = min(dp[i + now], dp[i] + 1);
			now *= 6;
		}
		now = 1;
		REP(j, INF) {
			if (now > 100000)break;
			dp[i + now] = min(dp[i + now], dp[i] + 1);
			now *= 9;
		}
	}
	cout << dp[n] << endl;
}

Measured memory_bytes: 1024
n,k,q = map(int,input().split())

def win(n):
    return n + 1
def lose(n):
    return n - 1


scores = [k] * n

for i in range(q):
	a=int(input())
	scores[a-1]=scores[a-1]+1

for i in scores:
    x = int(i)-q
    if x>0:
        print("Yes")
    else:
        print("No")

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;

	map<int, map<int, int>> mp;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		mp[a][b] = 1;
		mp[a][b] = 1;
	}
	bool ok = false;

	for (int i = 2; i < n; i++)
		if (mp[1][i] && mp[i][n])
			ok = true;


	if (ok)
		cout << "POSSIBLE\n";
	else 
		cout << "IMPOSSIBLE\n";
}

Measured memory_bytes: 37760
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N = sc.nextInt()
  val A = ((0, false) :: List.fill(N)(sc.nextInt() -> false)).toArray
  println(loop(1, 1).getOrElse(-1))

  @scala.annotation.tailrec
  def loop(i: Int, count: Int): Option[Int] = A(i) match {
    case (2, _) => Some(count)
    case (_, true) => None
    case (j, false) =>
      A(i) = (i, true)
      loop(j, count + 1)
  }
}


Measured memory_bytes: 66352
from sys import stdin

INF = float('inf')


def bellman_ford(n, edges, r):
    d = [INF] * n
    d[r] = 0

    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'

    return -d[n-1]


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    Edges = [None] * M

    for i in range(M):
        ai, bi, ci = [int(x) for x in stdin.readline().rstrip().split()]
        Edges[i] = (ai-1, bi-1, -ci)

    ans = bellman_ford(N, Edges, 0)

    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
	int A, B; cin >> A >> B;

	if (A == 1) {
		if (B == 2) cout << 3 << endl;
		else if (B == 3) cout << 2 << endl;
	}
	else if (A == 2) {
		if (B == 1) cout << 3 << endl;
		else if (B == 3) cout << 1 << endl;
	}
	else {
		if (B == 1) cout << 2 << endl;
		else if (B == 2) cout << 1 << endl;
	}
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define   LF      '\n'
#define   ALL(x)  x.begin(), x.end()
#define   iostreamBooster()  do{cin.tie(nullptr);ios::sync_with_stdio(false);}while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f'3f3f3f3fLL;


signed main()
{
  int N, M, X, Y;
  int x[1005], y[1005];

  cin >> N >> M >> X >> Y;
  for (int i = 0; i < N; ++i) {
    cin >> x[i];
  }
  for (int i = 0; i < M; ++i) {
    cin >> y[i];
  }

  sort(x, x+N);
  sort(y, y+M);

  bool f = false;
  for (int z = X+1; z <= Y; ++z) {
    if (x[N-1] < z && y[0] >= z) {
      f = true;
      break;
    }
  }

  if (f) {
    puts("No War");
  } else {
    puts("War");
  }
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;

int main() {

	int n;
	cin >> n;
	int a[n + 1], prev[n + 2], next[n + 2];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	prev[0] = 0, prev[1] = a[1], next[n] = a[n], next[n + 1] = 0;
	for (int i = 2; i <= n; i++) {
		prev[i] = __gcd(prev[i - 1], a[i]);
	}

	for (int i = n - 1; i >= 1; i--) {
		next[i] = __gcd(next[i + 1], a[i]);
	}

	int max_gcd = 0;
	for(int i = 1, gcd_without ; i <= n ; i++){
		gcd_without = __gcd(prev[i - 1], next[i + 1]);
		max_gcd = max(max_gcd, gcd_without);
	}
	cout << max_gcd;
	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define P pair<int,ll>
using namespace std;
typedef long long ll;
const int maxx=1e5+10;
char str[maxx];
int main(){
    int n,m; cin>>n>>m;
    scanf("%s",str+1);
    int cnt=0;
    char pre;
    for(int i=1;i<=n;i++){
        if(i==1){
            ;
        }else{
            if(pre==str[i]) cnt++;
        }
        pre=str[i];
    }
    cout<<min(n-1,cnt+m*2)<<endl;
}


Measured memory_bytes: 384
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        init();

        long n = nextLong(), a = nextLong(), b = nextLong();
        if (Math.abs(a - b) % 2 == 0) System.out.println(Math.abs(a - b)/2);
        else {
            long min = Math.min(a, b), max = Math.max(a, b);
            long leftMoves = min - 1;
            long leftPos = max - leftMoves - 1;
            long minLeft = (max - leftPos) + (leftPos - 1)/2;
            long rightMoves = n - max;
            long rightPos = min + rightMoves + 1;
            long minRight = (rightPos - min) + (n - rightPos)/2;
            System.out.println(Math.min(minLeft, minRight));
        }
    }

    //Input Reader
    private static BufferedReader reader;
    private static StringTokenizer tokenizer;

    private static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    private static String next() throws IOException {
        String read;
        while (!tokenizer.hasMoreTokens()) {
            read = reader.readLine();
            if (read == null || read.equals(""))
                return "-1";
            tokenizer = new StringTokenizer(read);
        }

        return tokenizer.nextToken();
    }

    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}

Measured memory_bytes: 22996
fun main(arg: Array<String>) {
    val (N, T) = listOfInt()
    val A = listOfInt()
    val M = IntArray(N)
    M[N - 1] = A[N - 1]
    for (n in N - 2 downTo 0) {
        if (A[n] > M[n + 1]) M[n] = A[n] else M[n] = M[n + 1]
    }
    var max = 0
    var ans = 0
    for (n in 0 until N - 1) {
        if (A[n] < M[n + 1]) {
            val m = M[n + 1] - A[n]
            if (max == m) ans += 1
            else if (max < m) {
                max = m; ans = 1
            }
        }
    }
    println(ans)
}

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfLong() = listOfString().map(String::toLong)
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }


Measured memory_bytes: 51928
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c)
{
	stack<int> S;
	S.push(r);
	color[r] = c;

	while (S.empty() == false) {
		int u = S.top();
		S.pop();
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			if (color[v] == NIL) {
				color[v] = c;
				S.push(v);
			}
		}
	}
}

void assignColor()
{
	int id = 1;

	for (int i = 0; i < n; i++) {
		color[i] = NIL;
	}

	for (int u = 0; u < n; u++) {
		if(color[u]==NIL){
			if (color[u] == NIL) {
				dfs(u, id++);
			}
		}
	}
}

int main()
{
	int s, t, m, q;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}

	assignColor();

	cin >> q;

	for (int i = 0; i < q; i++) {
		cin >> s >> t;
		if (color[s] == color[t]) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 8936
from itertools import combinations
n,m,x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]

ans = 10**9
for i in range(1,n+1):
  for j in combinations(ca, i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    
    if all(t[a] >= x for a in range(1,m+1)):
      ans = min(ans, t[0])
      
if ans == 10**9:
  print(-1)
else:
  print(ans)

Measured memory_bytes: 9168
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
typedef struct _s{
	signed* lpstr;int len;
	_s(int c){
		lpstr=new signed[101];lpstr[0]=c;lpstr[1]='\0';len=1;
	}
	_s(){
		lpstr=new signed[101];len=0;
	}
	friend _s operator +(const _s &a,const _s &b){
		_s tmp;tmp.len=a.len+b.len;int ptr=0;for(register int i=0;i<a.len;i++){
			tmp.lpstr[ptr]=a.lpstr[i];ptr++;
		}for(register int i=0;i<b.len;i++){
			tmp.lpstr[ptr]=b.lpstr[i];ptr++;
		}return(tmp);
	}
}str;
str digui(int x){
	if(x==1)return(_s(1));
	if(x%2==0){
		str ra=digui(x-1);str r=_s(ra.len+1);return(r+ra);
	}str ra=digui(x>>1);str r=_s(ra.len+1);return(ra+r);
}
signed main(){
	int n;cin>>n;str res=digui(n);
	cout<<res.len*2<<endl;
	for(register int i=1;i<=res.len;i++)printf("%lld ",i);
	for(register int i=0;i<res.len;i++)printf("%d ",res.lpstr[i]);
	return(0);
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);
    
    int h, w, n;
    char[][] map;
    int[][] cheese;
    int x, y;
    int dis;
    
    void run(){
	while(sc.hasNext()){
	    h = sc.nextInt();
	    w = sc.nextInt();
	    n = sc.nextInt();
	    if(n==0) break;

	    map = new char[h][w];
	    cheese = new int[n][2];

	    for(int i=0; i<h; i++){
		String s = sc.next();
		for(int k=0; k<w; k++){
		    map[i][k] = s.charAt(k);
		    if(map[i][k]=='S'){
			x = k;
			y = i;
		    }
		    else if(map[i][k]!='X' && map[i][k]!='.'){
			int c = map[i][k] - 49;
			cheese[c][0] = k; // x
			cheese[c][1] = i; // y
		    }
		}
	    }

	    dis = 0;
	    for(int i=0; i<n; i++){
		//System.out.println("++"+i);
		dis += solve(x, y, i);
		x = cheese[i][0];
		y = cheese[i][1];
	    }
	    System.out.println(dis);
       
	}
    }

    int solve(int nx, int ny, int level){
	//System.out.println("*"+nx+" "+ny+" "+level);
	boolean[][] visit = new boolean[h][w];
	LinkedList<int[]> que = new LinkedList<int[]>();
      	que.add(new int[]{nx, ny, 0});
	
	while(que.size()>0){
	    int[] p = que.pollFirst();
	    nx = p[0];
	    ny = p[1];
	    int sum = p[2];

	    if(nx==cheese[level][0] && ny==cheese[level][1])
		return sum;

	    if(visit[ny][nx]) continue;
	    visit[ny][nx]=true;

	    for(int i=0; i<4; i++){
		int a = nx+dX[i];
		int b = ny+dY[i];
		if(a>=0 && a<w && b>=0 && b<h && 
		   map[b][a]!='X'){
		    que.add(new int[]{ a, b, sum+1 });		
		}
	    }
	}
	return -1; // テ、ツスツソテ」ツつ湘」ツ?ェテ」ツ??  
    }
    
    int[] dX = {0, 1, -1, 0};
    int[] dY = {1, 0, 0, -1};
}

Measured memory_bytes: 125620
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll N, M;
  cin >> N >> M;
  vll X(M);
  REP(i, 0, M) {
    cin >> X[i];
  }
  sort(X.begin(), X.end(), less<>());

  if (N >= M) {
    cout << 0 << endl;
    return 0;
  }

  vll D(M - 1);
  REP(i, 0, M - 1) {
    D[i] = X[i + 1] - X[i];
  }
  sort(D.begin(), D.end(), less<>());

  ll ans = 0;
  REP(i, 0, M - N) {
    ans += D[i];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1792