akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<queue>
#include<ctime>
#include<vector>
using namespace std;
inline int rd(){
  register char ch=getchar();
  register bool flag=false;
  register int res=0;
  while(ch<'0'||ch>'9'){flag=(ch=='-');ch=getchar();}
  while(ch>='0'&&ch<='9'){
    res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
  if(flag)res=-res;
  return res;
}
int n,m;
int f[2][3010],g[2][3010];
//int *F=f+3005,*G=g+3005;

#define mod 1000000007
inline int mo(int x,int y){
  x+=y;if(x>=mod)x-=mod;return x;
}
inline void upd(int &x,int y){
  x+=y;if(x>=mod)x-=mod;
}
void work(){
  n=rd();m=rd();
  int i,j;
  for(j=1;j<=n;j++)
    f[0][j]=1;f[1][0]=1;
  //仅仅这样移动是并不行的，因为极值必须要确定才行(否则可能非法)
  for(i=1;i<=m;i++){
for(j=0;j<=n;j++)g[0][j]=f[0][j],g[1][j]=f[1][j],f[0][j]=f[1][j]=0; 
    /*for(j=2;j<=n;j++)g[j]=mo(mo((j<n?f[j]:0),f[j]),mo(f[j+1],f[j-1]));
    g[1]=mo((1<n?f[1]:0),f[2]);
    g1[1]=mo(mo(f[1],f1[0]),mo(((1<n)?f1[1]:0),f1[2]));
    g1[0]=mo(mo(f1[0],f1[1]),f[1]);
    for(j=2;j<=n;j++)g1[j]=mo(mo((j<n?f1[j]:0),f1[j]),mo(f1[j+1],f1[j-1]));*/
    //for(j=0;j<=n;j++)if(j>0)upd((j==1)?f1[j-1])
    
    //for(j=0;j<=n;j++)f1[j]=g1[j],f[j]=g[j];
   for(j=0;j<=n;j++)
     {if(j>0)upd(f[(j==1)][j],g[0][j]),upd(f[1][j],g[1][j]),
        upd(f[(j==1)][j-1],g[0][j]),upd(f[1][j-1],g[1][j]);
if(j<n)upd(f[0][j],g[0][j]),upd(f[1][j],g[1][j]),
       upd(f[0][j+1],g[0][j]),upd(f[1][j+1],g[1][j]);
      }
//  printf("i=%d\n",i);
//  for(j=0;j<=n;j++)printf("%d [%d] ",f[0][j],f[1][j]);printf("\n");
   }
  int res=0;
  for(j=0;j<=n;j++)
    upd(res,f[1][j]);//res=res*2%mod;
  printf("%d\n",res);
}
int main(){
  work();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
bool acs[maxn];
int was[maxn];
void fl()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
int main()
{
	ios::sync_with_stdio(0);
//    fl();
	int n,m;
	cin>>n>>m;
	int ac=0,wa=0;
	int ord;
	string ss;
	for(int i=1;i<=m;i++)
	{
		cin>>ord>>ss;
		if(acs[ord])
			continue;
		ac+=(acs[ord]=(ss=="AC"));
		was[ord]+=(ss=="WA");
	}
	for(int i=1;i<=n;i++)
		wa+=was[i]*acs[i];
	cout<<ac<<" "<<wa<<endl;
	return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#define task "KIENDT"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 2;
int n;
int a[N];
int s[N];

void Read(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		if(a[i] < i)
			++s[i - a[i]];
	}
}

void Solve(){
	ll ans = 0;
	for(int i = 1; i <= n; ++i){
		if(i + a[i] <= n)
			ans += (ll)s[i + a[i]];
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); if(fopen(task".INP", "r"))
	freopen(task".INP", "r", stdin),
	freopen(task".OUT", "w", stdout);
	Read();
	Solve();
}


Measured memory_bytes: 5224
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int          input;
    vector<int>  array;
    for (int i=0; i<5; ++i) {
        cin >> input;
        array.push_back(input);
    }
    sort(array.begin(), array.end(), greater<int>());
    for (vector<int>::size_type i=0; i<array.size(); ++i) {
        cout << array[i];
        cout << (i==4 ? '\n' : ' ');
    }
}

Measured memory_bytes: 1216
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		long n = Long.parseLong(sa[0]);
		int x = Integer.parseInt(sa[1]);
		int m = Integer.parseInt(sa[2]);
		br.close();

		Set<Long> set = new HashSet<>();
		long ans = x;
		long now = x;
		int i = 1;
		set.add(now);
		for ( ; i < n; i++) {
			now = now * now % m;
			ans += now;
			if (!set.add(now)) {
				i++;
				break;
			}
		}

		long sum = 0;
		int d = 0;
		set.clear();
		for ( ; i < n; i++) {
			now = now * now % m;
			ans += now;
			if (!set.add(now)) {
				i++;
				break;
			}
			sum += now;
			d++;
		}
		if (i == n) {
			System.out.println(ans);
			return;
		}

		long r = n - i;
		ans += sum * (r / d);
		r %= d;
		for (int j = 0; j < r; j++) {
			now = now * now % m;
			ans += now;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 40044
while 1:
    k=input().split()
    k[0]=int(k[0])
    k[2]=int(k[2])
    
    if k[1]=="?":
        break
    elif k[1]=="+":
        print(k[0]+k[2])
    elif k[1]=="-":
        print(k[0]-k[2])
    elif k[1]=="*":
        print(k[0]*k[2])
    elif k[1]=="/":
        print(k[0]//k[2])



Measured memory_bytes: 5596
n=int(input())
l = list(map(int, input().split()))
c=0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if l[i]+l[j]>l[k] and l[i]!=l[j] and l[i]!=l[k] and l[j]!=l[k] and l[i]+l[k]>l[j] and l[k]+l[j]>l[i]:
                c+=1
print(c)

Measured memory_bytes: 9192
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

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


int main(){
    ll X;   cin >> X;
    ll res = 0;
    res += (X / 500) * 1000;
    res += ((X % 500) / 5) * 5;

    cout << res << endl;


    return 0;
}

Measured memory_bytes: 256
import sys
def main():
    L, N = map(int, input().split())
    lines = sys.stdin.readlines()

    trees_ccw = [None] * N
    for i in range(N):
        trees_ccw[i] = int(lines[i])

    trees_cw = [L - trees_ccw[-(i+1)] for i in range(N)]
    trees_ccw_accum = [0] + [None] * N
    trees_cw_accum = [0] + [None] * N
    for i in range(N):
        trees_ccw_accum[i+1] = trees_ccw_accum[i] + trees_ccw[i]
        trees_cw_accum[i+1] = trees_cw_accum[i] + trees_cw[i]

    #print(trees_ccw)
    #print(trees_cw)
    #print(trees_ccw_accum)
    #print(trees_cw_accum)

    dist_max = 0

    for i in range(1,N+1):
        offset_left = i
        n_left = offset_left + (N-offset_left) // 2 #ccwの数
        n_right = N - n_left    #cwの数



        '''
        [print('L', end='') for _ in range(offset_left-1)]
        print('L', end='_')
        for i_ in range(N-offset_left):
            if i_ % 2 == 0:
                print('R', end='')
            else:
                print('L', end='')
        print()
        print(offset_left, n_left, n_right)
        '''


        dist_1 = 2 * (trees_ccw_accum[n_left] - trees_ccw_accum[i-1]) + 2 * trees_cw_accum[n_right]
        dist_2 = 2 * (trees_cw_accum[n_left] - trees_cw_accum[i-1]) + 2 * trees_ccw_accum[n_right]



        if (N-offset_left) % 2 == 0:
            dist_1 -= trees_ccw[n_left-1]
            dist_2 -= trees_cw[n_left-1]
        else:
            dist_1 -= trees_cw[n_right-1]
            dist_2 -= trees_ccw[n_right-1]

        if dist_max < dist_1:
            dist_max = dist_1

        if dist_max < dist_2:
            dist_max = dist_2

        #print(n_left, dist_1, dist_2, dist_max)

    print(dist_max)
    return

main()


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

int main() {
    int N;
    cin >> N;
    vector<int> num(4);
    for (int i = 3; i >= 0; i--) {
        num.at(i) = N % 10;
        N /= 10;
    }
    for (int bit = 0; bit < (1<<3); bit++) {
        string ans;
        int sum = num.at(0);
        ans.push_back('0' + num.at(0));
        for (int i = 0; i < 3; i++) {
            if (bit & (1<<i)) {
                sum += num.at(i + 1);
                ans.push_back('+');
                ans.push_back('0' + num.at(i + 1));
            }
            else {
                sum -= num.at(i + 1);
                ans.push_back('-');
                ans.push_back('0' + num.at(i + 1));
            }
        }
        if (sum == 7) {
            ans += "=7";
            cout << ans << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
using namespace std;
typedef pair<int, int> P;

signed main(){
    int n;
    while(cin >> n, n){
        vector<int> a(n);
        rep(i, 0, n) cin >> a[i];
        sort(all(a));
        int MIN = 1e9;
        rep(i, 0, n - 1){
            MIN = min(MIN, a[i + 1] - a[i]);
        }
        cout << MIN << endl;
    }
}

Measured memory_bytes: 3120
N, K = map(int, input().split())
S = input()

#累積和の準備
zero_list = []
one_list = []
tmp = S[0]
count = 1
pin = 0
if tmp == '1':
    zero_list.append(0)
for i in range(1,N):
    if S[i] == tmp:
        count += 1
    else:
        if tmp == '1':
            one_list.append(count)
            count = 1
            tmp = '0'
        else:
            zero_list.append(count)
            count = 1
            tmp = '1'
if tmp == '1':
    one_list.append(count)
else:
    zero_list.append(count)
        
if K >= len(zero_list):
    pin =1
    print(N)
else:
    start = sum(zero_list[:K]) + sum(one_list[:K])
    ans = start
    if len(one_list) > K:
        tmp = start - zero_list[0] + zero_list[K] + one_list[K]
    else:
        tmp = start - zero_list[0] + zero_list[K]
    if tmp > ans:
        ans = tmp
    basyo = 1
    last = len(one_list)
    while basyo + K < last:
        tmp = tmp -zero_list[basyo] - one_list[basyo -1] + zero_list[K + basyo] + one_list[K + basyo]
        if tmp > ans:
            ans = tmp
        basyo += 1
    if len(one_list) != len(zero_list) and K + basyo <  len(zero_list):
        tmp = tmp -zero_list[basyo] - one_list[basyo -1] + zero_list[K + basyo] 
        if ans < tmp:
            ans = tmp
if pin == 0:
    print(ans)

Measured memory_bytes: 4480
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    ll X;
    cin >> X;
    X -= 400;
    ll ans = 9;
    while (X >= 0)
    {
        X -= 200;
        ans--;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
#define readInt(x) scanf("%d", &x)
#define readStr(x) scanf("%s", x)
#define rep(i, n) for(int i=0; i<(n); ++i)
#define write(x) cout << (x) << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1 << 28;

int N, K;

int main()
{
    cin >> N >> K;
    int cnt = K;
    rep(i, N - 1)
        cnt *= K - 1;
    write(cnt);
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>

using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define int long long
//std::ios::sync_with_stdio(0); std::cin.tie(0);
signed main() {
	int x, a, y, b, t, s;
	cin >> x >> a;
	cin >> y >> b;
	cin >> t;
	s = abs(x - y);
	if (b >= a)cout << "NO" << endl;
	else if (s > t * (a - b))cout << "NO" << endl;
	else cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
typedef pair<ll,ll> Pair;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }

const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  ll x,y,z,k;
  cin >> x >> y >> z >> k;
  vl a,b,c;
  inputv(a,x);
  inputv(b,y);
  inputv(c,z);
  vl ans;
  sort(ALL(a));
  sort(ALL(b));
  sort(ALL(c));
  rep(i,x){
    if(i+1 > k) break;
    rep(j,y){
      if((i+1)*(j+1) > k) break;
      rep(l,z){
        if((i+1)*(j*1)*(l+1) > k) break;
        ans.push_back(a[x-1-i]+b[y-1-j]+c[z-1-l]);
      }
    }
  }
  sort(ALL(ans));
  rep(i,k){
    cout << ans[ans.size()-1-i] << endl;
  }
        
 return 0;
}


Measured memory_bytes: 18676
/*
─────────▄▄▄▄▄▄▄▄▄▄▄▄─────────
─────▄▄▀▀░░░░░░░░░░░░▀▀▄▄─────
───▄▀░░░░░░░░░░░░░░░░░░░░▀▄───
──█░░░░░▄▄▄▄▄░░░░▄▄▄▄▄░░░░░█──
─█░░░░░██░█░██▄▄██░█░██░░░░░█─
█░░░░░░░▀▀▀▀▀░░░░▀▀▀▀▀░░░░░░░█
█░░░░▄▄▄░░░░░░░░░░░░░░▄▄▄░░░░█
█░░░░██▀█▄▄▄▄▄▄▄▄▄▄▄▄██▀█░░░░█
─█░░░▀██▄████████▄▄▄▄██▄▀░░░█─
──█░░░░▀██▀▀▀▀████████▀░░░░█──
───▀▄░░░░▀▄▄▄▄██████▀░░░░▄▀───
─────▀▀▄▄░░░░░░░░░░░░▄▄▀▀─────
─────────▀▀▀▀▀▀▀▀▀▀▀▀─────────
*/
#include <bits/stdc++.h>

using namespace std;

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

	string s;
	cin >> s;
	int k = 0;
	string last = "";
	for (int i = 0; i < s.size(); ++i) {
		string cur;
		cur += s[i];
		if (cur == last) {
			if (i == s.size() - 1) {
				break;
			}
			cur += s[++i];
		}
		++k;
		last = cur;
	}
	cout << k;

	return 0;
}

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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX/3

const double EPS = 1e-14;
const double PI  = acos(-1.0);


int d[55][55];

typedef pair<int, int> p;

int main(){
  int h, w;
  scanf("%d %d", &h, &w);
  vector<string> v;
  queue<p> q;

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

  int black = 0;
  REP (i, h) {
    string s;
    cin >> s;
    REP (j, w) {
      if (s[j] == '#') black++;
      d[i][j] = INF;
    }
    v.push_back(s);
  }

  q.push(make_pair(0, 0));
  d[0][0] = 1;
  while(q.size()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    if (x == w - 1 && y == h - 1) break;

    REP (i, 4) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (0 <= nx && nx < w && 0 <= ny && ny < h && d[ny][nx] == INF && v[ny][nx] == '.') {
        q.push(make_pair(nx, ny));
        d[ny][nx] = d[y][x] + 1;
      }
    }
  }
  if (d[h - 1][w - 1] == INF)
    printf("-1\n");
  else
    printf("%d\n", (h * w) - black - d[h - 1][w - 1]);
}


Measured memory_bytes: 256
// Always check for base cases
            // Check for overflows and out of index
            // Do something instead of sitting idle
            #include<bits/stdc++.h>
            #define ll long long
            #define f   first
            #define s   second
            #define pb          push_back
            #define mod        1000000007
            #define mod1       1000000009
            #define hell        998244353
            #define inf         1000000000000000000LL
            #define pi          3.14159265358979323
            //#define N           100005 
            const int N=200005;
            using namespace std;
            ll n,k,sum,q,res,m,val,ans;
            ll x,y;
            double p;
            ll xx[]={1,0,-1,0};
            ll yy[]={0,1,0,-1};
            void solve()    
            {   
                cin>>n;
                vector<ll> v(n);
                for(int i=0;i<n;i++) cin>>v[i];
                ll mx=v[0];
                ll ans=0;
                for(int i=1;i<n;i++)
                {
                    if(v[i]<mx) {ans+=(mx-v[i]);}
                    else mx=max(mx,v[i]);
                }
                cout<<ans;


            }
            int main()  
            {   ios_base::sync_with_stdio(false);
                cin.tie(0);cout.tie(0);
                ll t=1;  
                //cin>>t;
                 for(ll i=1;i<=t;i++)
                    solve();
                

            }            


Measured memory_bytes: 4780
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w, n,m,k; string s,t;
char maze[60][60];
int dis[101][101]; int graph[52][52]; bool vis[52];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

int main() {
	ll d;
	cin >> n >> d;
	ll res = n / (2 * d + 1);
	if (n % (2 * d + 1) != 0) {
		res++;
	}
	cout << res << endl;
}



Measured memory_bytes: 256
from operator import itemgetter, attrgetter
N = int(input())
A = []
for i in range(N):
    tmp = input().split()
    A.append([tmp[0],-int(tmp[1]),i])
A.sort()
A.sort(key=itemgetter(0,1))
for i in range(N):
    print(A[i][2]+1)

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

int main() {
    int N, a, b;
    long long K;
    long c[1000000] = {};
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        c[a-1] += b;
    }
    long long count = 0;
    for (int i = 0; i < 1000000; i++) {
        count += c[i];
        if (count >= K) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define fileopen(filename) if (fopen(filename".INP", "r")) {freopen(filename".INP", "r", stdin);freopen(filename".OUT", "w", stdout);}
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,n) for (int i=1;i<=n;++i)
#define eb emplace_back
#define pb push_back
#define memset(a,i) memset(a,i,sizeof(a))
#define upper(v,a) upper_bound(v.begin(), v.end(), a)
#define lower(v,a) lower_bound(v.begin(), v.end(), a)
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define gcd __gcd
const int maxn=1e5+1;
const int INF=1e9+1;

signed main()
{
	fastio;
	int n;cin>>n;
	int a[3][n+1];
	rep(i,2)rep(j,n)cin>>a[i][j];
	int dp[3][n+1];
	dp[1][1]=a[1][1];dp[2][0]=0;
	for (int i=2;i<=n;++i)dp[1][i]=dp[1][i-1]+a[1][i];
	for (int i=1;i<=n;++i)dp[2][i]=max(dp[2][i-1],dp[1][i])+a[2][i];
	cout<<dp[2][n];
}

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

int main() {
	int n; cin >> n;
	pair<char, int> p[100];

	p[0] = make_pair('P', 0);
	p[1] = make_pair('W', 0);
	p[2] = make_pair('G', 0);
	p[3] = make_pair('Y', 0);

	char t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		for (int j = 0; j < 4; j++) {
			if (p[j].first == t) p[j].second = 1;
		}
	}

	int count = 0;
	for (int i = 0; i < 4; i++) {
		count += p[i].second;
	}

	if (count == 3) cout << "Three" << endl;
	else cout << "Four" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    string t;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        if (s[i] != 'x')
            t.push_back(s[i]);
    }
    int nt = t.size();
    for (int i = 0; i <= nt / 2; ++i) {
        if (t[i] != t[nt - 1 - i]) {
            cout << -1 << "\n";
            return 0;
        }
    }
    int ret  = 0;
    int left = 0, right = n - 1;
    while (left < right) {
        if (s[left] == s[right])
            ++left, --right;
        else if (s[left] == 'x')
            ++left, ++ret;
        else if (s[right] == 'x')
            --right, ++ret;
    }
    cout << ret << "\n";
    return 0;
}

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

s = input()

count = [0] * n

for i in range(n) :
    if s[i-1] + s[i] == 'AC' :
        count[i] = count[i-1] + 1
    else :
        count[i] = count[i-1]

for j in range(0, q) :
    l, r = map(int, input().split())
    print(count[r-1] - count[l-1])

Measured memory_bytes: 6060
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,raw_input().strip().split())
ices = [int(raw_input().strip()) for _ in xrange(N)]

orderN(N,L,ices)

Measured memory_bytes: 12540
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		List <Long> unko=new ArrayList<Long>();
		int N=sc.nextInt();
		long M=sc.nextLong();
		fra(M,unko);
		long[][] map=new long[65][2];

		for(int i=0; i<65; i++) {
			for(int j=0; j<2; j++) {
				map[i][j]=0;
			}
		}
		int counter=0;
		boolean zumi=false;
		while(unko.size()>0) {
			long a=unko.get(0);
			unko.remove(0);
			zumi=false;
			for(int i=0; i<=counter; i++) {
				if(a==map[i][0] && a!=1) {
					map[i][1]++;
					zumi=true;
					break;
				}
			}
			if(a!=1 && zumi==false) {
				map[counter][0]=a;
				map[counter][1]++;
				counter++;
			}
			else if(a==1) {
				//
			}
		}

		for(int i=0; i<counter; i++) {
			//System.out.println(map[i][0]+" cntr="+counter);
		}
		long ans=1;

		for(int i=0; i<=counter; i++) {
			long cmb=Combi(map[i][1]+N-1,N-1)%1000000007;
			ans=(ans*cmb)%1000000007;
		}
		System.out.println(ans);
	}


	public static void fra(long a,List<Long> p) {//long型用
		for(long i=2; i*i<=a; i++) {
			if(a%i==0) {
				p.add(i);
				fra(a/i,p);
				return;
			}
		}
		p.add(a);
	}


	public static long Combi(long n,long r) {		// nCr
		if(r==0 || r==n) return 1L;

		if(r>n-r) {
			r=n-r;
		}

		long[] bunsi=new long[(int)r];
		long[] bunbo=new long[(int)r];

		for(int k=0; k<r; k++) {
			bunsi[k]=n-r+k+1;
			bunbo[k]=k+1;
		}

		for(long p=2; p<=r; p++) {
			long pivot=bunbo[(int)p-1];
			if(pivot>1) {
				long offset=(n-r)%p;
				for(long k=p-1; k<r; k+=p) {
					bunsi[(int)(k-offset)]/=pivot;
					bunbo[(int)k]/=pivot;
				}
			}
		}

		long kotae=1;

		for(long k=0; k<r; k++) {
			if(bunsi[(int)k]>1) {
				kotae*=bunsi[(int)k];
				kotae=kotae%1000000007;
			}
		}

		return kotae;
	}
}


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

int n;

int search(const vector<int>& d,int m,int k){
	int l = 0;
	int r = m;
	if(m==0) return l;
	else{
		if(d[0]>=k){
			return l;
		}else{
			while(l+1<r){
				int med = (l+r)/2;
				if(d[med]<k) l = med;
				else r = med;
			}
			return r;
		}
	}
}

int main(){
	while(cin >> n && n>0){
		vector<int> a(n,0);
		int length = 1;
		vector<int> L(n,0);
		for(int i=0;i<n;i++){
			cin >> a[i];
		}
		L[0] = a[0];
		for(int i=1;i<n;i++){
			if(L[length-1] < a[i]){
				L[length] = a[i];
				length++;
			}else{
				int s = search(L,length-1,a[i]);
				L[s]= a[i];
			}
		}
		cout << length << endl;
	}
}

#if 0
(11/1)自分では正しく書いているつもりですが，n=50くらいでWAになっていしまいて，原因がわかりません。ご指導していただけると嬉しいです。
(11/2)コメントありがとうございました。無事通りました。ループ不変条件には気を付けたいと思います。
#endif


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

def main():
    K = int(input())
    
    if K%2==0 or K%5==0:
        print(-1)
        return
    
    if K % 7:
        L = 9*K
    else:
        L = 9*K//7
    a = 1
    for i in range(1,K+10):
        a = (a * 10) % L
        if a == 1:
            print(i)
            return
    print(-1)
main()


Measured memory_bytes: 9128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
ll INF=300000;

int main(){
    int N, X;
  	cin>>N>>X;
  	vector<int> m(N);
  	int Min=10000;
  	for(int i=0; i<N; i++){
      	cin>>m[i];
      	X -=m[i];
      	Min=min(Min, m[i]);
    }
  	cout<<N+X/Min<<endl;
  	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int read() {
	int x; scanf("%d", &x); return x;	
}
const int maxn = 2e5 + 10;
const int INF = 1e9;
int n, m, K, a[maxn];
int main() {
	#ifdef LOCAL
		freopen("1.in", "r", stdin);
	#endif
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	sort(a + 1, a + 1 + n, greater<int>());
	int cnt = 0, pos = 2;
	long long ans = a[1];
	for (int i = 3; i <= n; i++) {
		if (cnt == 2) cnt = 0, pos++;
		ans = ans + a[pos];
		cnt++;
	}
	cout << ans << endl;
	return 0;		
}

Measured memory_bytes: 4544
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279

#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 1; i <= n; i++)
#define REPR(i, n) for(ll i = n; i >= 1; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
const ld INF = 1e9+123;
#define VEC(type,A,N) vector<type> A(N+10)
#define VECi(type,A,N,i) vector<type> A(N+10,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N+10,vector<type>(M+10))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N+10,vector<type>(M+10,i))
#define ALL(v) v.begin()+1, v.end()-9
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    ll N,A,B;
    cin>>N>>A>>B;
    cout<<fixed<<setprecision(15)<<(ll)floor(N/(A+B))*A+min(A,(N%(A+B)));
    //cout<<fixed<<setprecision(15)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	float n, hiku = 0, a = 1;
	float n1, n2;//??´??°????°???°
	int count=0, end = 0; // ???????????????N?????°
	int nn1[8] = { 0 }, nn2[4] = { 0 };//??´??°??¨????°???°??¨
	cin >> n;
	while (n >= 0){
		n1 = n;
		while (n >= 1) n = n - a;
		n2 = n; n1 = n1 - n2;// ??´??°??¨?°???°???????????????
		// 1 //?°???°???????????°????????????
		if (n2 != 0){
			while (1){
				n2 = n2 * 2;
				if (n2 >= 1) {
					nn2[count] = 1;
					n2 = n2 - 1;
				}
				if (n2 == 0) break;
				count++;
				if (count >= 4){
					cout << "NA" << endl; //?????????
					end = 1; //N?????°
					break;
				}
			}
		}count = 0;
		int nnn;
		nnn = n1;
		if (end == 0){
			while (1){
				hiku = nnn / 2;
				if (nnn - (hiku * 2) == 1) nn1[count] = 1;
				count++;
				nnn = nnn / 2;
				if (nnn == 0) {
					nn1[count] = 0;
					break;
				}
				else if (nnn == 1) {
					nn1[count] = 1;
					break;
				}
				if (count >= 8){
					cout << "NA" << endl;
					end = 1;
					break;
				}
			}
		}
		if (end == 0){
		for (int i = 7; i >= 0; i--) cout << nn1[i];
		cout << ".";
		for (int i = 0; i < 4; i++) cout << nn2[i];
		cout << endl;
	}
		count = 0;
		for (int i = 7; i >= 0; i--)nn1[i] = 0;
		for (int i = 0; i < 4; i++)nn2[i] = 0;
		end = 0;
		cin >> n;
	}
 	return 0;
}

Measured memory_bytes: 1224
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int W = sc.nextInt();

		int[][] a = new int[N][2];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 2; j++) {
				a[i][j] = sc.nextInt();
			}
		}

		long[][] dp = new long[N + 1][W + 1];
		for (int i = 0; i < N + 1; i++) {
			for (int j = 0; j < W + 1; j++) {
				dp[i][j] = (int)Double.NEGATIVE_INFINITY;
			}
		}
		dp[0][0] = 0;

		for (int i = 0; i < N; i++) {
			int weight = a[i][0];
			int value = a[i][1];

			for (int j = 0; j < W + 1; j++) {
				if (dp[i][j] >= 0) {
					dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);

					if (j + weight <= W) {
						dp[i + 1][j + weight] = Math.max(dp[i + 1][j + weight], dp[i][j] + value);
					}
				}
			}
		}

		long ans = 0;
		for (int i = 0; i < W + 1; i++) {
			ans = Math.max(ans, dp[N][i]);
		}

		System.out.println(ans);
	}

}


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

int main(void){
    
  int N,X,m,min=10000,ans=0;
  cin >> N >> X;
  for(int i=0;i<N;i++){
      cin >> m;
      if(m < min) min = m;
      X -= m;
      ans++;
  }
  
  ans += (X/min);
  cout << ans << endl;
}

Measured memory_bytes: 3528
#include<iostream>
#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>

using namespace std;

int n;
int a[20];
int q;
int m[200];

bool dfs(int n, int sum, int answer)
{
	if (n <= 20)
	{
		if (sum == answer) return true;

		if (dfs(n + 1, sum + a[n], answer)) return true;

		if (dfs(n + 1, sum, answer)) return true;
	}

	return false;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> m[i];
	}

	for (int i = 0; i < q; i++)
	{
		if (dfs(0, 0, m[i]))
		{
			cout << "yes" << endl;
		}
		else
		{
			cout << "no" << endl;
		}
	}


	return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>
int main(){
  int n,a[100],i,j,x,swap=0,mimj;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  for(i=0;i<n;i++){
    mimj=i;
    for(j=i;j<=n-1;j++){
      if(a[j]<a[mimj]) mimj=j;
    }
    x=a[i];
    a[i]=a[mimj];
    a[mimj]=x;
    if(i!=mimj)swap++;
  }
  for(i=0;i<n;i++){
    if(i!=0)printf(" ");
    printf("%d",a[i]);
  }
  printf("\n");
  printf("%d\n",swap);
  return 0;
}


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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(3e3) + 17;

int n, m, u;
string s;
int R[MAXN];
int S[MAXN];
ll binomial[MAXN][MAXN], dp[MAXN][MAXN];
int U[MAXN][MAXN];

bool read() {
    if (!(cin >> n >> m >> s))
        return false;

    forn (i, m) {
        int l, r;
        cin >> l >> r;
        R[l] = max(R[l], r);
    }

    return true;
}

ll add(ll a, ll b) { return (a += b) >= INF ? a - INF : a; }

ll dfs(int i, int cnt, const vector< pair<int, int> >& v) {
    if (i == sz(v) - 1)
        return binomial[v[i].s - v[i].f + 1][cnt];

    if (U[i][cnt] == u)
        return dp[i][cnt];

    U[i][cnt] = u;
    dp[i][cnt] = 0;
    ll& res = dp[i][cnt];
    
    for (int k = 0; k <= cnt; ++k)
        if (k <= v[i + 1].f - v[i].f && cnt - k <= v[i].s - v[i + 1].f + 1)
            res = add(res, dfs(i + 1, cnt - k + S[v[i + 1].s] - S[v[i].s], v) * binomial[v[i + 1].f - v[i].f][k] % INF);

    return dp[i][cnt];
}

void solve() {
    forn (i, n)
        S[i + 1] = s[i] - '0';

    forn (i, n)
        S[i + 1] += S[i];

    binomial[0][0] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i; ++j)
            binomial[i][j] = add(binomial[i - 1][j], j ? binomial[i - 1][j - 1] : 0ll);

    ll ans = 1ll;

    for (int l = 1; l <= n; ) {
        if (R[l] == 0) {
            ++l;
            continue;
        }

        int l1 = l, mxr = l1;
        vector< pair<int, int> > vec;

        for (; l1 <= mxr; ++l1)
            if (R[l1] > mxr) {
                mxr = R[l1];
                vec.pb(mp(l1, R[l1]));
            }

        ++u;
        ans = ans * dfs(0, S[vec[0].s] - S[vec[0].f - 1], vec) % INF;
        l = l1;
    }

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
    while (read())
        solve();
    
    return 0;
}



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

int main(){
    int N; 
    cin >> N;
    vector<int> vec(N);

    for (int i = 0; i < N ; i++){
        cin >> vec.at(i) ;
    }
    int sum = 0;
    for (int i = 0 ; i < N ; i++){
        sum += vec.at(i);
    }
    int ref = 0 ;
            int refnext = 0 ;
    for (int i = 0 ; i < N ; i++){
        ref += vec.at(i);
        if (ref >= sum/2){
            refnext = ref - vec.at(i);
            break;
        }
    }
    int s , t ;
    s = sum - 2*ref ;
    if (s < 0 ){
        s *= -1;
    }
    t = sum - 2*refnext ;
    if ( t < 0 ){
        t *= -1;
    }
    int answer = min(s,t);
    cout << answer <<endl;;
    

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  string a,b,c;
  int n;
  cin >> n >> a >> b >> c;
  int cnt = 0;
  for(int i=0;i<n;i++){
    if(a[i] == b[i] && b[i] == c[i]) continue;
    else if(a[i] == b[i] || b[i] == c[i] || a[i] == c[i]) cnt++;
    else cnt += 2;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
N, M = map(int,input().split())
ans = [1]*N
H = list(map(int,input().split()))


for i in range(M):
    A, B = map(int,input().split())
    if H[A-1] > H[B-1]:
        ans[B-1] = 0
    elif H[A-1] < H[B-1]:
        ans[A-1] = 0
    else:
        ans[A-1] = 0
        ans[B-1] = 0

print(ans.count(1))

Measured memory_bytes: 20916
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

const int maxv = 200002;

int n, cnt[maxv];

long long helper(long long x) {
    return x * (x-1) / 2;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    cin >> n;
    vector<int> v(n);

    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        ++cnt[v[i]];
    }

	long long tot = 0;
    for (int i = 1; i < maxv; ++i)
        if (cnt[i] > 1)
            tot += helper(cnt[i]);

    for (int i = 0; i < n; ++i) {
        long long diff = helper(cnt[v[i]]) - helper(cnt[v[i]]-1);
        cout << tot - diff << endl;
    }

	return 0;
}

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

#define f first
#define s second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define px pair<db, db>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define input(a) for (auto& el : a) cin >> el;
#define output(a) cout << '!'; for (auto& el : a) cout << el << ' '; cout << '\n'; cout.flush();
#define sz(el) int(el.size())
#define sq(a) ((a) * (a))
#define xll bitset<128>
#define xmin(a,b) a = min(a, b)
#define xmax(a,b) a = max(a, b)
#define sun(a) sort(all(a)); a.resize(unique(all(a)) - a.begin());
/**/  /// extra
//#define forn(i,n) for (int i = 0; i < n; ++i)
//#define rforn(i,n) for (int i = n - 1; i >= 0; --i)
#define bn '\n'
#define vi vector<int>
#define vii vector<vi>
#define vl vector<ll>
#define vll vector<vl>
//#define G vector<vector<pii>>
#define GVE vector<vector<edge>>
#define usi unordered_set<int>
#define usp set<pii>
/**/

using namespace std;

const int INF = 1'000'000'017;
const ll LLINF = 1'000'000'000'000'000'017LL;
const ld inf = 1.0 / 0.0;
const ld eps = 1e-9;
const int MOD = 998244353;

//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

//uniform_int_distribution<int> uid(l, r); [l, r]
//int x = uid(rng);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n, k - q);
    for (int i = 0; i < q; ++i) {
        int x;
        cin >> x;
        --x;
        ++a[x];
    }
    for (int i = 0; i < n; ++i) {
        cout << (a[i] > 0 ? "Yes" : "No") << '\n';
    }
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> edges[110000];
int dfs(int a, int p){
	int ans = 0;
	for(int j = 0; j < edges[a].size(); j++){
		if(edges[a][j] != p){
			ans ^= (1+dfs(edges[a][j],a));
		}
	}
	return ans;
}
int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n-1; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	cout << (dfs(0, -1) == 0 ? "Bob" : "Alice") << endl;

}


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

int main()
{
     char a[102], b[102];
     scanf("%s", a);
     scanf("%s", b);
     
     int alen = strlen(a);
     int blen = strlen(b);

     if(alen > blen){
          printf("GREATER\n");
     }
     else if(alen < blen) {
          printf("LESS\n");
     }
     else
     {
          int i;
          for(i = 0; i < alen; i++)
          {
               if(a[i] > b[i]) {
                    printf("GREATER\n");
                    return 0;
               }
               if(a[i] < b[i]) {
                    printf("LESS\n");
                    return 0;
               }
          }

          printf("EQUAL\n");
     }

     return 0;
}


Measured memory_bytes: 128
class UnionFind
	Node = Struct.new(:p, :h)
	def initialize(size); @p, @r = size.times.to_a, [0]*size; end
	def unite(i, j); k, l = parent(i), parent(j); if @r[k] < @r[l]; @p[k] = l; @r[l] += 1 if @r[k] == @r[l]; else; @p[l] = k; end; end
	def united?(i, j); parent(i) == parent(j); end
	def parent(i); j = i; until i == @p[i]; j, i = i, @p[j] = @p[i]; end; i; end
end

n, m = gets.split.map &:to_i
uf = UnionFind.new n
m.times do
  a, b = gets.split.map &:to_i
  uf.unite(a-1, b-1)
end

require "set"
s = Set.new
n.times do |i|
  s << uf.parent(i)
end

p s.size-1

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

int main()
{
	int H,W;
	
	while(1){
		cin >> H >> W;
	        if ( H == 0 && W == 0) break;
		for( int i = 0; i < H; i++)
		{
			for(int j = 0; j < W; j++)
			{
				cout << "#";
			}
			
			cout << "\n" ;
}
cout << endl;
}
		
return 0;
}

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

int main() {
  int pay, numOf1yen;
  cin >> pay >> numOf1yen;
  int remain = pay % 500;
  if (remain == 0 ){
    cout << "Yes" << endl;
  }else if (remain <= numOf1yen){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>
#include <cctype>
#include <map>
#include <limits>
#include <iomanip>

using namespace std;

const int mod = 1000000007;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
#define ll long long

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

	cout << ((X >= 30) ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 3116
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args)
	{
		Scanner s=new Scanner(System.in);
		
		long m=998244353;
		
		int n=s.nextInt();
		int k=s.nextInt();
		
		pair[] arr=new pair[n];
		
		for(int i=0;i<k;i++)
		{
			int l=s.nextInt();
			int r=s.nextInt();
			
			pair p=new pair(l,r);
			arr[i]=p;	
		}
		
		long[] dp=new long[n];
		
		for(int i=n-2;i>=0;i--)
		{
			for(int j=0;j<k;j++)
			{
				int min=i+arr[j].l;
				int max=i+arr[j].r;
				
				if(min>n-1)
				{
					
				}
				else if(max>=n-1)
				{
					dp[i]=(dp[i]%m+1%m)%m;
					
					max=n-2;
					
					if(max>=min)
					{
						dp[i]=(dp[i]%m+(dp[min]%m-dp[max+1]%m+m)%m)%m;
					}
					
				}
				else
				{
					dp[i]=(dp[i]%m+(dp[min]%m-dp[max+1]%m+m)%m)%m;
				}
				
			}
			
			dp[i]=(dp[i]%m+dp[i+1]%m)%m;
			
		}
		
		System.out.println((dp[0]%m-dp[1]%m+m)%m);
		
	}
	
}

class pair
{
	int l;
	int r;
	
	public pair(int l,int r)
	{
		this.l=l;
		this.r=r;
	}
}

Measured memory_bytes: 39480
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

#define all(c) (c).begin(),(c).end()

using namespace std;

int main(){

  vector<vector<int> > s;

  int n;
  cin >> n;
  vector<int>a(n), b(n),c(n);

  for(int i=0;i<n;i++)cin >> a[i];
  for(int i=0;i<n;i++)cin >> b[i];
  for(int i=0;i<n;i++)c[i] = i+1;

  do {
    s.push_back(c);
  } while (std::next_permutation(all(c)));

  int ai=0,bi=0;

  for(int i=0;i<s.size();i++){
    bool a_flg = true;
    bool b_flg = true;
    for(int j=0;j<n;j++){
      a_flg &= (a[j] == s[i][j]);
      b_flg &= (b[j] == s[i][j]);
    }

    if(a_flg)ai=i;
    if(b_flg)bi=i;
  }
  cout << abs(ai-bi) << endl;

    return 0;
}


Measured memory_bytes: 3256
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

int main(void)
{
    int n,m,c,count = 0,total = 0;
    int a[25],b[25];
    cin >> n >> m >> c;
    for(int i = 0;i < m;i++)
    {
        cin >> b[i];
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            cin >> a[j];
            total += a[j] * b[j];
        }
        if(total + c > 0){count++;}
        total = 0;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1<<18,INF=1<<29;

int main(){
  int a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;
  cout<<a+b+c+d+e+f-min({a,b,c,d})-min(e,f)<<endl;
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1e9;
const long double EPS = 1e-10;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  vector<int> c(n, 0);
  rep(i, n) {
    while (a[i] % 2 == 0) {
      c[i]++;
      a[i] /= 2;
    }
  }

  int ans = c[0];
  rep(i, n) ans = min(ans, c[i]);
  cout << ans << endl;


  
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
INF = float("inf")
# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]
value_max = 0
for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)
    value_max += v_in


memo = [[-1] * (value_max + 1) for i in range(n + 1)]

for i in range(n + 1):
    memo[i][0] = v[i]

for i in range(value_max + 1):
    memo[0][i] = INF


def dp(i, value):
    if memo[i][value] == -1:
        if value > v[i]:
            rest = dp(i - 1, value - v[i])
            if rest == INF:
                tar = INF
            else:
                tar = rest + w[i]
            memo[i][value] = min(dp(i - 1, value), tar)
        else:
            memo[i][value] = min(dp(i - 1, value), w[i])
    return memo[i][value]


ans = -1
OK_MAX = 0
NG_MIN = value_max + 1

while OK_MAX + 1 != NG_MIN:
    i = int((OK_MAX + NG_MIN) / 2)
    ans_tmp = dp(n, i)
    if ans_tmp <= tar_w:
        OK_MAX = i
    else:
        NG_MIN = i

ans = OK_MAX

print("{}".format(ans))


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

int N,M;
int T[100005];
int K[100005];
int Kk[100005];
int Kg[100005];
void del(int id){
  if( Kk[id] ) Kk[id]--;
  else {
    Kg[id]--;
    Kk[id]++;
  }
}
int main(){
  cin >> N >> M;
  for(int i=0;i<N;i++){
    int x; cin >> x;
    T[x]++;
    K[ x % M ]++;
  }
  for(int i=0;i<=100000;i++){
    Kg[ i%M ] += T[i]/2;
    Kk[ i%M ] += T[i]%2;
  }
  int res = 0;
  //  for(int i=0;i<M;i++) cout << i << ": " << K[i] << " " << Kk[i] << " " << Kg[i] << endl;
  
  for(int i=1;i<M;i++){
    if( i + i == M ) continue;    
    int mini = min( K[ i ] , K[M-i] );
    //cout << mini << endl;
    //cout << i << ": " << K[i] << " "<< Kk[i] << " " << Kg[i] << endl;
    res += mini;
    K[i] -= mini;
    K[M-i] -= mini;
    for(int j=0;j<mini;j++){
      del(i); del(M-i);
    }
  }
  for(int i=0;i<M;i++){
    //cout << i << ": " << K[i] << " "<< Kk[i] << " " << Kg[i] << endl;
    if( i == 0 || i + i == M ){
      res += K[i]/2;
    } else
      res += Kg[i];
  }
  cout << res << endl;
}



Measured memory_bytes: 1792
n = int(input())
a = sorted(list(map(int, input().split())))

ans = 0
d = {}

for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1

for k,v in d.items():
    if k < v:
        ans += v-k
    elif k > v:
        ans += v
    else:
        pass

print(ans)

Measured memory_bytes: 18548
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<stack>
#include<map>
#include<queue>
#include<set>
#define int long long
using namespace std;
const int INF = 1e10;
const int ZERO = 0;

signed main() {
	int N;
	cin >> N;
	int ret = 0;
	for(int i = 0;i < N;i++) {
		ret += i;
	}
	cout << ret << endl;
}

Measured memory_bytes: 256