akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

struct UnionFind{
	vector<int> p;
	UnionFind(int n){
		p.resize(n, -1);
	}

	int find(int x){
		if(p[x] == -1)return x;
		else return p[x] = find(p[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);

		if(x == y)return;
		p[x] = y;
	}
};

struct Edge{
	int from, to, cost;
	Edge(int from, int to, int cost) : from(from), to(to), cost(cost){}

	bool operator<(const Edge& e) const {
		return cost < e.cost;
	}
};

struct Graph{
	int n;
	vector<Edge> es;
	Graph(int n) : n(n){}

	ll kruskal(){
		UnionFind uf(n);
		sort(es.begin(), es.end());
		// for(auto e : es)cout << e.from << " " <<  e.to << " " << e.cost << endl;

		ll min_cost = 0;
		for(auto e : es){
			if(uf.find(e.from) == uf.find(e.to))continue;
			uf.unite(e.from, e.to);
			min_cost += e.cost;
		}
		return min_cost;
	}

	void addEdge(int a, int b, ll c){
		es.push_back(Edge(a, b, c));
	}
};

struct Point{
	ll x, y;
	int id;
	Point(int id, ll x, ll y) : id(id), x(x), y(y){}
};

bool cmp(Point &a, Point &b){
	return a.x < b.x;
}

bool cmp2(Point &a, Point &b){
	return a.y < b.y;
}

int main(){
  int n;
  cin >> n;
  vector<Point> points;
  for(int i = 0; i < n; ++i){
  	ll x, y;
  	cin >> x >> y;
  	points.push_back(Point(i, x, y));
  }

  Graph g(n);
  sort(points.begin(), points.end(), cmp);
  for(int i = 0; i < n - 1; ++i){
  	ll x1 = points[i].x;
  	ll x2 = points[i + 1].x;
  	int id = points[i].id;
  	int id2 = points[i + 1].id;
  	g.addEdge(id, id2, x2 - x1);
  }

  sort(points.begin(), points.end(), cmp2);
  for(int i = 0; i < n - 1; ++i){
  	ll y1 = points[i].y;
  	ll y2 = points[i + 1].y;
  	int id = points[i].id;
  	int id2 = points[i + 1].id;
  	g.addEdge(id, id2, y2 - y1);
  }

  cout << g.kruskal() << endl;
  return 0;
}


Measured memory_bytes: 8688
h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
starts = [str(i) for i in range(n)]
goals = [str(i+1) for i in range(n)]
starts_y = [0 for i in range(n)]
starts_x = [0 for i in range(n)]
goals_y = [0 for i in range(n)]
goals_x = [0 for i in range(n)]

starts[0] = "S"
for y in range(h):
	for x in range(w):
		if stage[y][x] in starts:
			starts_y[starts.index(stage[y][x])] = y
			starts_x[starts.index(stage[y][x])] = x
		if stage[y][x] in goals:
			goals_y[goals.index(stage[y][x])] = y
			goals_x[goals.index(stage[y][x])] = x


sum = 0

for start_y, start_x, goal_y, goal_x in zip(starts_y, starts_x, goals_y, goals_x):
	bfs_map = [[-1 for j in range(w)] for i in range(h)]
	data_y = [start_y]
	data_x = [start_x]
	bfs_map[start_y][start_x] = 0
	goal = False
	
	while len(data_y) != 0 and not goal:
		y = data_y.pop(0)
		x = data_x.pop(0)
		goal = False
	
		for i in range(4):
			ny = y + [0,1,0,-1][i]
			nx = x + [1,0,-1,0][i]
			
			if ny >= 0 and ny < h and nx >= 0 and nx < w:
				if bfs_map[ny][nx] == -1 and stage[ny][nx] != "X":
					bfs_map[ny][nx] = bfs_map[y][x]+1
					data_y.append(ny)
					data_x.append(nx)
			if bfs_map[goal_y][goal_x] != -1:
				sum += bfs_map[goal_y][goal_x]
				goal = True
				break

print(sum)


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

using namespace std;
using ll = long long;

const int nax = 1005;
char sl[nax][nax];

const int mod = 1e9 + 7;

void add_self(int& a, int b) {
    a += b;
    if (a >= mod) {
        a -= mod;
    }
}

signed main() {
    int h, w;
    scanf("%d%d", &h, &w);
    for(int row = 0; row < h; row++) {
        scanf("%s", sl[row]);
    }
    vector<vector<int>> dp(h, vector<int>(w));
    dp[0][0] = 1;
    for (int row = 0; row < h; row++) {
        for (int col = 0; col < w; col++) {
            for (int r2 : {row, row + 1}) {
                int c2 = col;
                if (r2 == row) {
                    c2 = col + 1;
                }
                if (r2 < h && c2 < w && sl[r2][c2] == '.') {
                    add_self(dp[r2][c2], dp[row][col]);
                }
            }
        }
    }
    printf("%d\n", dp[h - 1][w - 1]);   
    return false;
}

Measured memory_bytes: 5120
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        System.out.println(solve(n));
    }

    private static int solve(long n){
        int[] factors = new int[1000001];
        long temp = n;
        for(int prime=2;prime<=1000000;prime++){
            while(temp%prime==0){
                factors[prime]++;
                temp/=prime;
            }
        }
        int count=0;
        for(int i=2;i<=1000000;i++){
            int fac = factors[i];
            for(int j=1;j<=fac;j++){
                fac-=j;
                count++;
            }
        }
        if(temp>1)
            count++;
        return count;
    }


}

Measured memory_bytes: 29752
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int a = in.nextInt();
		String s = in.next();
		if (a >= 3200)
			System.out.println(s);
		else
			System.out.println("red");
	}
}

Measured memory_bytes: 23252
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int[] a = new int[1000001];
		a[0] = 7 % k;
		for (int i = 1; i <= k; i++) {
			a[i] = (a[i-1] * 10 + 7) % k;
		}
		
		boolean flg = false;
		for (int i = 0; i < k; i++) {
			if (a[i] == 0) {
				System.out.println(i+1);
				flg = true;
				break;
			}
		}
		if (!flg) {
			System.out.println(-1);
		}
		
			
		
	}
}


Measured memory_bytes: 39584
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
ans = 0
for i in range(1, N+1):
    if i %3 !=0 and i %5!=0:
        ans += i
print(ans)

Measured memory_bytes: 9220
#C
N, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

over = a[0]-x
if over < 0:
    over = 0
eat, a[0] = over, a[0]-over
for i in range(N-1):
    over = a[i]+a[i+1]-x
    if over < 0:
        over = 0
    eat, a[i+1] = eat + over, a[i+1]-over
print(eat)

Measured memory_bytes: 14152
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;
    cout << max(0, C - A + B) << endl;
    return 0;
}


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

using namespace std;

int main(){
	int n;
	cin >> n;
  set<string> s;
  for (int i = 0; i < n; i++){
    string ss;
    cin >> ss;
    s.insert(ss);
  }
  cout << s.size() << endl;
	return 0;
}

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

using namespace std;
#define sqr(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define GCD(a, b) (__gcd(a, b))
#define LCM(a, b) ((a)/GCD(a,b)*(b))
#define PI (3.14159265358979323846)
#define MP make_pair
#define n1 first
#define n2 second
#define ALL(x) (x).begin(), (x).end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDB pair<db,db>
#define SI set<int>
#define SL set<ll>
#define MS multiset
#define MSI multiset<int>
#define MSLL multiset<ll>
#define PB push_back
#define PF push_front
#define VI vector<int>
#define VPI vector<pair<int,int>>
#define VLL vector<ll>
#define VS vector<string>
#define SZ(x) ((int)x.size())

typedef long long ll;

typedef unsigned long long ull;
typedef long double ld;
typedef double db;
const db eps = 0.000001;
const int INF = 1000000007;
const ll LINF = 1000000000000000555;
const int N = 1550555;
const int M = 5125;

void solve() {
    ll l, r, d;
    cin >> l >> r >> d;

    cout << r/d - (l-1)/d;

}

int main() {
    ios_base::sync_with_stdio(false);
#ifdef dxz05
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

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

typedef long long ll;
using namespace std;

ll H, N;
vector<ll> A(1000), B(1000);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    ll dp[10001];
    fill(dp, dp + 10000, -1);
    dp[H] = 0;
    for (ll i = H; i >= 0; i--) {
        if (dp[i] == -1) {
            continue;
        }
        for (int k = 0; k < N; k++) {
            ll idx = max((ll)0, i - A[k]);
            if (dp[idx] < 0) {
                dp[idx] = dp[i] + B[k];
            } else {
                dp[idx] = min(dp[i] + B[k], dp[idx]);
            }
        }
    }
    cout << dp[0] << endl;
    return 0;
}


Measured memory_bytes: 384
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int x = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        int result;
        if (x <= 599) {
            result = 8;
        } else if (x <= 799) {
            result = 7;
        } else if (x <= 999) {
            result = 6;
        } else if (x <= 1199) {
            result = 5;
        } else if (x <= 1399) {
            result = 4;
        } else if (x <= 1599) {
            result = 3;
        } else if (x <= 1799) {
            result = 2;
        } else {
            result = 1;
        }

        // 出力
        System.out.println(result);
    }
}


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


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


int main() {
    ll A,B;
    cin >>A>>B;
    if(A==1){
        A+=13;
    }
    if(B==1){
        B+=13;
    }

    if(A==B){
        cout<<"Draw"<<endl;
    }else if(A>B){
        cout<<"Alice"<<endl;
    }else{
        cout<<"Bob"<<endl;
    }
    
    


    return 0;
    

}

Measured memory_bytes: 3596
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[10086],n,k,ans=0;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=n-1;i>n-k-1;i--)
    {
        ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;

ll rep_pow(ll a, ll b){//繰り返し2乗法
    if(b==0) return 1;
    else if(b%2==0){
        ll memo = rep_pow(a, b/2);
        return memo*memo%mod;
    }else{
        return rep_pow(a, b-1)*a%mod;
    }
}

ll nCr(ll n, ll r){//mod逆元使ったnCr
    ll ret=1;
    rep(i,r){
        ret *= n-i;//分子
        ret %= mod;
        ret *=rep_pow(r-i, mod-2);//mod逆元によりr!で割ると同値
        ret %= mod;
    }
    return ret;
}
ll gcd(ll a, ll b){ if(b==0) return a; return gcd(b, a%b);}



int main(){
    fast_io

    int n,k;
    cin>>n>>k;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];

    sort(h.begin(), h.end());
    ll ans=1001001001;
    rep(i,n-k+1){
        ans=min(ans, h[i+k-1]-h[i]);
    } 
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;
const double PI=acos(-1);

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};



int main() {
    string S; cin>>S;
    int N=S.length();
    int ans=MOD;

    for (int i = 0; i < N-1; ++i) {
        if(S[i]!=S[i+1]) {
            ans = min(ans, max(i + 1, N - i - 1));
        }
    }
    if(ans==MOD) ans=N;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define pf push_front
#define eb emplace_back
using namespace std;
typedef long long ll;
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b; return true;} return false;}
template<class t,class u> bool chmin(t&a,u b){if(a>b){a=b; return true;} return false;}
template<class t,class u> t MAX(t a,u b){if(a>=b) return a; return b;}
template<class t,class u> t MIN(t a,u b){if(a<=b) return a; return b;}
template<class t> int SIZE(t s){return (int)s.size();}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using vvi=vc<vc<int>>;
using pi=pair<int,int>;
using vi=vc<int>;
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
const long long INF = 1LL << 60;

int main(){
    cout << fixed << setprecision(20);
    int si; cin >> si;
    string s; cin >> s;
    int ans = 0, cur = ans;
    rep(i,si){
        if(s[i] == 'I') cur++;
        else cur--;
        chmax(ans,cur);
    }
    cout << ans << endl;
    return 0;
}

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

int main(){

int i;
double a[6];
double x,y;

while(scanf("%lf",&a[0])!=EOF){

for(i=1;i<6;i++)scanf("%lf",&a[i]);

x = (a[4]*a[2]-a[5]*a[1])/(a[4]*a[0]-a[3]*a[1]);

if(x==0) x=fabs(x);

y = (a[3]*a[2]-a[5]*a[0])/(a[3]*a[1]-a[4]*a[0]);

if(y==0) y=fabs(y);

printf("%.3f %.3f\n",x,y);

}

return 0;
}

Measured memory_bytes: 652
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
      
       Scanner scan = new Scanner(System.in);
       
       int S = scan.nextInt();
       
       System.out.print(S / 3600);
       System.out.print(":");
       System.out.print(S % 3600 / 60);
       System.out.print(":");
       System.out.println(S % 3600 % 60 ); 
   }
}


Measured memory_bytes: 26352
#include <stdio.h>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int main(){
    double max = -1,min = 1000001,tmp;
 
    while(scanf("%lf",&tmp)!=EOF){
        max = (max >= tmp)?max:tmp;
        min = (min <= tmp)?min:tmp;
    }
 
    printf("%.1lf\n",max-min);
 
    return 0;
}


Measured memory_bytes: 2576
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            String s = in.next();
            out.println(s.charAt(0) + "" + (s.length() - 2) + "" + s.charAt(s.length() - 1));
        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isPrintableChar(int c) {
            return c >= 33 && c <= 126;
        }

        public String next() {
            StringBuilder sb = new StringBuilder();

            int b = readByte();
            while (!isPrintableChar(b))
                b = readByte();

            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }

            return sb.toString();
        }

    }
}



Measured memory_bytes: 22740
#include <iostream>



int main(){
	int arr[2];
  	std::cin >> arr[0] >> arr[1];
  
  	int sum = 6;
  	for (int i=0; i<2; i++){
     	 sum -= arr[i];
    }
  	
  	std::cout<<sum;
  
  
  
  
  
  
}

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

typedef long long ll;
using namespace std;
const int maxn=2e5+10;

int a[maxn];
multiset<int> st;

int main() 
{
	int n;
	scanf("%d",&n);
	for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	ll ans=a[n],cnt=n-2;
	for( int i=n-1;i>=1;i-- )
	{
		if( cnt==0 ) break;
		ans+=a[i];
		cnt--;
		if( cnt==0 ) break;
		ans+=a[i];
		cnt--;
	}  printf("%lld\n", ans);
	
	
	
}

Measured memory_bytes: 4476
# coding: utf-8

N = int(input())
s = []
for i in range(N):
    a = input().split()
    a[1] = int(a[1])
    s.append(a)
X = input()

flag = False
ans = 0
for i in range(N):
    if (flag):
        ans += s[i][1]
    if (s[i][0] == X):
        flag = True
print(ans)

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define ll1 1ll
#define ONE 1ll
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
	os << p.first << " " << p.second;
	return os;
}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}
/*
typedef __int128_t Int;
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
  if (s) {
	__uint128_t tmp = value < 0 ? -value : value;
	char buffer[128];
	char *d = std::end(buffer);
	do {
	  --d;
	  *d = "0123456789"[tmp % 10];
	  tmp /= 10;
	} while (tmp != 0);
	if (value < 0) {
	  --d;
	  *d = '-';
	}
	int len = std::end(buffer) - d;
	if (dest.rdbuf()->sputn(d, len) != len) {
	  dest.setstate(std::ios_base::badbit);
	}
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
	if ('0' <= s[i] && s[i] <= '9')
	  ret = 10 * ret + s[i] - '0';
  return ret;
}
*/

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template <class T> bool chmin(T &a, const T &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
int gcd(int x, int y) { return (y == 0 ? x : gcd(y, x%y)); }
int gcd(vector<int>&v) {
	int ret = v[0];
	rep(i, 1, v.size()) {
		ret = gcd(ret, v[i]);
	}
	return ret;
}
signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int N; cin >> N;
	vector<int>a(N); rep(i, 0, N) { cin >> a[i]; }
	cout << gcd(a) << endl;

	return 0;
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
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; }
//template end

template<typename M,typename N=M>
struct LazySegmentTree{
   using F=function<M(M,M)>; using G=function<M(M,N)>; using H=function<N(N,N)>;
   int sz,height; vector<M> data; vector<N> lazy;
   const F f;const G g; const H h; const M m1; const N n1;
   LazySegmentTree(int n,const F f,const G g,const H h,const M &m1,const N n1):f(f),g(g),h(h),m1(m1),n1(n1){
      sz=1,height=0; while(sz<n)sz<<=1,height++;
      data.assign(2*sz,m1); lazy.assign(2*sz,n1);
   }
   void build(vector<M> v){
      rep(i,0,v.size())data[i+sz]=v[i];
      rrep(k,sz-1,0)data[k]=f(data[2*k],data[2*k+1]);
   }
   M ref(int k){return lazy[k]==n1?data[k]:g(data[k],lazy[k]);}
   void recalc(int k){while(k>>=1)data[k]=f(ref(2*k),ref(2*k+1));}
   void thrust(int k){rrep(i,height,0)eval(k>>i);}
   void eval(int k){
      if(lazy[k]!=n1){
         lazy[2*k]=h(lazy[2*k],lazy[k]); lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
         data[k]=ref(k); lazy[k]=n1;
      }
   }
   void update(int a,int b,N x){
      thrust(a+=sz); thrust(b+=sz-1);
      for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
         if(l&1)lazy[l]=h(lazy[l],x),++l;
         if(r&1)--r,lazy[r]=h(lazy[r],x);
      }
      recalc(a); recalc(b);
   }
   M query(int a,int b){
      thrust(a+=sz); thrust(b+=sz-1);
      M L=m1,R=m1;
      for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
         if(l&1)L=f(L,ref(l++)); if(r&1)R=f(ref(--r),R);
      } return f(L,R);
   }
};

typedef pair<ll,ll> P;

int main(){
   int n; ll d,a; scanf("%d%lld%lld",&n,&d,&a);
   vector<P> v(n);
   rep(i,0,n)scanf("%lld%lld",&v[i].first,&v[i].second);
   sort(ALL(v));
   LazySegmentTree<ll> seg(n,
   [](ll a,ll b){return a+b;},
   [](ll a,ll b){return a+b;},
   [](ll a,ll b){return a+b;},0,0);
   rep(i,0,n){
      seg.update(i,i+1,(v[i].second+a-1)/a);
   }
   ll res=0;
   rep(i,0,n){
      ll val=seg.query(i,i+1);
      if(val<=0)continue;
      int idx=lower_bound(ALL(v),P{v[i].first+2*d+1,-INF})-v.begin();
      res+=val; seg.update(i,idx,-val);
   }
   printf("%lld\n",res);
   return 0;
}

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

int main(){
  int64_t a,b,c;
  cin >> a >> b >> c;
  if(a+b>=c){
    cout << "No" << endl;
  }else if(c*c+a*a+b*b-2*c*a-2*c*b-2*a*b>0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, V, P = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype = np.int64)

A.sort()
r = N
l = 0
border = N - P
AP = A[border]
B = AP - A
np.cumsum(B, axis = 0, out = B)

def solve(ind):
	if A[ind] + M < AP:
		return 0
	if ind >= V - P:
		return 1

	score_border = A[ind] + M
	tmp = 0
	tmp += (ind + P) * M
	tmp += B[border] - B[ind]
	tmp += (score_border - A[border]) * (border - ind)
	if tmp >= M * V:
		return 1
	else:
		return 0

while r - l > 1:
	mid = (r + l) // 2
	if solve(mid):
		r = mid
	else:
		l = mid

if solve(l):
	print(N - l)
else:
	print(N - r)



Measured memory_bytes: 23196
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  if(s=="RRR")
    cout<<3<<endl;
  else if(s=="RRS" || s=="SRR")
    cout<<2<<endl;
  else if(s=="RSR" ||s=="RSS" ||s=="SSR" ||s=="SRS")
    cout<<1<<endl;
  else
    cout<<0<<endl;
}
    

Measured memory_bytes: 3556
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      int A = sc.nextInt();
      int B = sc.nextInt();
      if(A<=8 && B<=8){
        System.out.println("Yay!");
      }else{
        System.out.println(":(");
      }
    }
}

Measured memory_bytes: 35664
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int w , a  , b;
int main()
{
	while(~scanf("%d%d%d" , &w , &a , &b)){
		int ans = 1 << 30;
		if(b > a + w) cout << b - a - w << endl;
		else if(a > b + w) cout << a - b - w << endl;
		else cout << 0 << endl;
	}
}

Measured memory_bytes: 256
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=100
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(p):
    s=gcd(cul(i,a[:p]),a[p])
    if s>ans: ans=s

print(ans)

Measured memory_bytes: 14588
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    long long cnt = 0;
    while (1)
    {
        int l = 0;
        int r = n;
        int tmp = 0;
        for (int i = 0; i < n; i++)
        {
            if(h[i]>0){
                l = i;
                break;
            }
            if(h[i]==0){
                tmp++;
            }
        }
        if(tmp==n)
            break;
        for (int i = l; i < n; i++)
        {
            if(h[i]==0){
                r = i;
                break;
            }
        }
        for (int i = l; i <r; i++)
        {
            if(h[i]>0) h[i]--;
        }
       /* for (int i = 0; i < n; i++)
        {
            cerr << h[i] << " ";
        }
        cerr << "\n";
*/
        cnt++;
        }
        cout << cnt << endl;

        return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int x,n,l[105],ans;
int sh=1;
int main(){
    cin>>n>>x;
    for (int i=0; i<n; i++) {
        cin>>l[i];
        ans+=l[i];
        sh++;
        if (ans>x) {
            ans-=l[i];
            sh--;
            break;
        }

    }
            cout<<sh<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    a, b, c, k = mi()
    if k <= a + b:
        print(min(a, k))
    else:
        print(a - (k - (a + b)))


if __name__ == "__main__":
    main()


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

int main() {
    string s, t; cin >> s >> t;
    int dp[s.size() + 1][t.size() + 1];
    REP(i, 0, s.size() + 1) REP(j, 0, t.size() + 1) dp[i][j] = 0;

    REP(i, 0, s.size()) {
        REP(j, 0, t.size()) {
            if (s[i] == t[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j]);
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1]);
        }
    }
    string ans = "";
    int i = s.size(), j = t.size();
    while(i > 0 && j > 0) {
        if (dp[i][j] == dp[i][j - 1]) {
            j--;
        } else if (dp[i][j] == dp[i - 1][j]) {
            i--;
        } else {
            ans = s[i - 1] + ans;
            i--; j--;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 35456
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args) {
		Scanner scn=new Scanner(System.in);
		ArrayList<Integer> list=new ArrayList<>();
		ArrayList<Integer> list1=new ArrayList<>();
		
		int t=scn.nextInt();
		
		for(int i=0;i<t;i++) {
			int x=scn.nextInt();
			
			list.add(x);
			list1.add(x);
		}
		Collections.sort(list);
		
		int count=0;
		for(int i=0;i<list.size();i++) {
			
			if(list.get(i)!=list1.get(i)) {
				count++;
				if(count>3) {
					break;
				}
			}		
		}
		if(count<3) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
		scn.close();
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int main(){
    long a;
    long b;
    long g;
    cin>>a>>b;
    //aとbの最小公倍数を求めれば良い．
    int t;    // 補助変数
    long a1=a;
    long b1=b;
    if(a>b){
        while ( b != 0 ) {          // 他方が0になるまで
      t = a%b;
            if(t<0){
                t+=b;
            }
                a = b; b = t;    // 一方を剰余に置き換える
    }
        g=a;
    }else{
        while ( a != 0 ) {          // 他方が0になるまで
        t = b%a;
            if(t<0){
                t+=a;
            }
            b = a; a = t;    // 一方を剰余に置き換える
    }
        g=b;
    }
    if(g==1){
        cout<<a1*b1;
    }else{
    cout<<a1*b1/g;
    }
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    String s=sc.next();
    if(a>=3200){
      System.out.println(s);
    }else{
      System.out.println("red");
    }
  }
}


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

int main(){
  int N;
  cin>>N;
  float x[N],y[N];
  for(int i=0;i<N;i++){
    cin>>x[i]>>y[i];
  }
  if(N%2==1){
    cout<<"NA"<<endl;
    return 0;
  }
  float tx,ty;
  tx=(x[0]+x[N/2])/2;
  ty=(y[0]+y[N/2])/2;

  for(int i=0;N/2+i<N;i++){
    int a,b,c,d;
    a=i;
    b=N/2+i-1;
    c=N/2+i;
    d=i-1;
    if(d==-1) d=N-1;
    if(!((x[d]-x[a]==x[c]-x[b])&&(y[d]-y[a]==y[c]-y[b]))){
      cout<<"NA"<<endl;
      return 0;
    }
  }
  printf("%f %f\n",tx,ty);
  return 0;
}
/*
int main(){
  int N;
  cin>>N;
  float x[N],y[N];
  for(int i=0;i<N;i++){
    cin>>x[i]>>y[i];
  }
  if(N%2==1){
    cout<<"NA"<<endl;
    return 0;
  }
  float tx,ty;
  tx=(x[0]+x[N/2])/2;
  ty=(y[0]+y[N/2])/2;
  //cout<<" "<<" "<<tx<<" "<<ty<<endl;
  for(int i=0;i<N/2;i++){
    float dx=(x[i]+x[i+N/2])/2,dy=(y[i]+y[i+N/2])/2;
    if(max(abs(dy-ty),abs(dx-tx))>0.0001){
      cout<<"NA"<<endl;
  //    cout<<dx<<" "<<dy<<" "<<tx<<" "<<ty<<endl;
      return 0;
    }
  }
  float k=pow(abs(x[i+1]-x[i]),2)+pow(abs(y[i+1]-y[i]),2);
  float l=pow(abs(x[1]-x[0]),2)+pow(abs(y[1]-y[0]),2);
  for(int i=0;i<N-1;i++){
    if(abs(l-k)>=1){
      cout<<"NA"<<endl;
      return 0;
    }
  }
  printf("%f %f\n",tx,ty);
  return 0;
}
*/



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

using namespace std;

int main() {
  int n,m;
  cin>>n>>m;
  vector<int> vec(n);
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    vec[a]++;
    vec[b]++;
  }
  rep(i,n)cout<<vec[i]<<endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=2001,INF=1<<30;
 
int main(){
    
    int N;cin>>N;
    vector<vector<char>> S(N,vector<char>(N));

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>S[i][j];
        }
    }

    int cnt=0;

    for(int k=0;k<N;k++){
        bool flag=true;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(S[(i+k)%N][j]!=S[(j+k)%N][i]) flag=false;
            }
        }
        if(flag) cnt++;
    }

    cout<<cnt*N<<endl;
}


Measured memory_bytes: 384
#include <stdio.h>

int main() {

  int n;
  int a;
  int b;
  scanf("%d", &n);
  scanf("%d", &a);
  scanf("%d", &b);

  int train = n * a;
  int taxi = b;

  int min = train;

  if (train > taxi)
    min = taxi;
    
  printf("%d\n", min);
  
  return 0;
}

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

const int N=400005;
int n,a[N];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[0]^=a[i];
	for(int i=1;i<=n;i++) printf("%d ",a[0]^a[i]);
}

Measured memory_bytes: 4488
INFTY = 10**9+7
N,M = map(int,input().split())
A = []
for _ in range(M):
    A.append(int(input()))
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
cur = 0
if M>0 and A[0]==1:
    dp[1] = 0
    cur = 1
for i in range(2,N+1):
    if M>0 and cur<M and i==A[cur]:
        cur += 1
    else:
        dp[i] = (dp[i-1]+dp[i-2])%INFTY
print(dp[N])

Measured memory_bytes: 7856
#include <iostream>

using namespace std;

int SortAlgorithm(int* A, int N) {

	int swapCount = 0;

	for (int i = 0; i < N; i++) {
		int minIndex = i;

		for (int j = i + 1; j < N; j++) {
			if (A[j] < A[minIndex]) {
				minIndex = j;
			}
		}

		if (i != minIndex) {
			swap(A[i], A[minIndex]);
			swapCount++;
		}
		
	}


	return swapCount;
}


int main() {

	int A[100], N, swapCount;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];

	swapCount = SortAlgorithm(A, N);

	for (int i = 0; i < N; i++) {
		if (i) cout << " ";
		cout << A[i];
	}

	cout << endl;
	cout << swapCount << endl;

	return 0;
}


Measured memory_bytes: 3100
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"
#include "cmath"
#include "set"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll> > mat;

int main()
{
  int n;
  cin >> n;
  bool ans = true;
  int a[110];
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    if (a[i] % 2 == 0 && a[i] % 3 != 0 && a[i] % 5 != 0)
    {
      ans = false;
    }
  }
  cout << (ans ? "APPROVED" : "DENIED") << "\n";
}


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

using namespace std;

typedef long long ll;

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

  int n, r;
  cin >> n >> r;
  if (n >= 10) cout << r << " "; else cout << r + 100 * (10 - n) << "\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
bool check(int n)
{
  int a[7],x=0;
  while(n){
    x++;
    a[x]=n%10;
    n/=10;
  }
  for(int i=1;i<=x/2;i++)
    if(a[i]!=a[x+1-i])
      return false;
  return true;
}
int main()
{
  int a,b,ans=0;
  cin>>a>>b;
  for(int i=a;i<=b;i++)
    if(check(i))
      ans++;
  cout<<ans;
  return 0;
}

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

using namespace std; 

typedef long long ll;

struct edge {
    int from;
    int to;
    ll w;
};

int main() {
    int N;
    cin >> N;
    vector<vector<edge>> G(N);
    for (int i=0; i<N-1; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        --u;
        --v;
        G[u].emplace_back(edge{u, v, w});
        G[v].emplace_back(edge{v, u, w});
    }

    vector<int> C(N, -1);
    C[0] = 1;
    queue<edge> que;
    for (edge& e: G[0]) {
        que.push(e);
    }

    while (!que.empty()) {
        edge e = que.front();
        que.pop();
        if (C[e.to] != -1) continue;
        if (e.w % 2 == 0) {
            C[e.to] = C[e.from];
        } else {
            C[e.to] = (C[e.from] - 1) * (-1);
        }
        for (edge& e_: G[e.to]) {
            que.push(e_);
        }
    }

    for (int c: C) {
        cout << c << endl;
    }

    return 0;
}

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

template <typename T>
class fenwick_tree {
	const int n;
	vector<T> data;
public:
	fenwick_tree(int n_) : n(n_), data(n + 1) {}
	T find(int p) const {
		T res = 0;
		while (p > 0) {
			res += data[p];
			p -= p & -p;
		}
		return res;
	}
	T find(int l, int r) const {
		return find(r) - find(l);
	}
	void add(int p, T val) {
		++p;
		while (p <= n) {
			data[p] += val;
			p += p & -p;
		}
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<vector<int>> rs(N + 1);
	for (int i = 0; i < M; i++) {
		int L, R;
		cin >> L >> R; --L;
		rs[R].push_back(L);
	}
	vector<tuple<int, int, int>> qs;
	for (int i = 0; i < Q; i++) {
		int p, q;
		cin >> p >> q; --p;
		qs.emplace_back(q, p, i);
	}
	sort(qs.begin(), qs.end());
	vector<int> res(Q);
	fenwick_tree<int> ft(N);
	for (int i = 1, j = 0; i <= N; i++) {
		for (auto p : rs[i]) ft.add(p, 1);
		while (j < Q && get<0>(qs[j]) == i) {
			int p, q, id;
			tie(q, p, id) = qs[j++];
			res[id] = ft.find(p, q);
		}
	}
	for (int i = 0; i < Q; i++) {
		printf("%d\n", res[i]);
	}
	return 0;
}


Measured memory_bytes: 3708
#include <stdio.h>

int main()
{
  int n, q;
  int s[10000];
  int t[500];
  int count = 0;

  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d", &s[i]);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d", &t[i]);
    s[n] = t[i];
    int j;
    for (j = 0; s[j] != t[i]; j++);
    if (j != n)
      count++;
  }
  printf("%d\n", count);
  
  return 0;
}
  


  



Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
const int N=2500;
int n,m,q;
char dit[maxn];
int ditu[N][N];
int dx,dy,ddx,ddy;
int sum1[N][N];//点数的前缀和 
int sum2[N][N];//横边
int sum3[N][N];//纵边 
//连通块数=点数-边数 
int ans1,ans2;
int main(){
	//freopen("duty.in","r",stdin);
	//freopen("duty.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		scanf("%s",dit+1);
		for(int j=1;j<=m;j++){
			ditu[i][j]=(dit[j]=='1');
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sum1[i][j]=sum1[i-1][j]+sum1[i][j-1]-sum1[i-1][j-1]+ditu[i][j];
			sum2[i][j]=sum2[i-1][j]+sum2[i][j-1]-sum2[i-1][j-1]+(ditu[i][j]&&ditu[i][j+1]);
			sum3[i][j]=sum3[i-1][j]+sum3[i][j-1]-sum3[i-1][j-1]+(ditu[i][j]&&ditu[i+1][j]); 
		}
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d%d%d",&dx,&dy,&ddx,&ddy);
		ans1=sum1[ddx][ddy]-sum1[dx-1][ddy]-sum1[ddx][dy-1]+sum1[dx-1][dy-1];
		ans2=sum2[ddx][ddy-1]-sum2[ddx][dy-1]-sum2[dx-1][ddy-1]+sum2[dx-1][dy-1];
		ans2+=sum3[ddx-1][ddy]-sum3[ddx-1][dy-1]-sum3[dx-1][ddy]+sum3[dx-1][dy-1];
		printf("%d\n",ans1-ans2);
	}
	return 0;
}

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

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define pii pair<ll , ll>
#define all(x) x.begin(),x.end()
#define nl "\n"
#define ump unordered_map

const ll N=2e6+5,mod=1e9 + 7;
ll fct[N],inv[N],invfct[N];
void init(){
    fct[0]=fct[1]=1;
    inv[1]=1;
    invfct[0]=invfct[1]=1;
    for(ll i=2;i<N;i++){
        fct[i]=i*fct[i-1]%mod;
        inv[i]=(ll)(mod-inv[mod%i])*(mod/i)%mod;
        invfct[i]=(ll)(inv[i])*invfct[i-1]%mod;
    }
}
ll ncr(ll n,ll r){
    if(n<0 || r<0 || n-r<0)return 0;
    ll ans = fct[n]*invfct[r];
    ans%=mod;
    ans = ans * invfct[n-r];
    ans%=mod;
    return ans;
}

void doit(){
	ll x, y;
	cin >> x >> y;
	if( (x + y) % 3 != 0){
		cout << 0 << nl;
		return;
	}
	ll n, m;
	if((2*y - x)%3 != 0){
		cout << 0 << nl;
		return;
	}
	n = (2*y - x)/3;
	m = y - 2*n;
	if(n < 0 or m < 0){
		cout << 0 << nl;
		return;
	}
	init();
	cout << ncr(n+m,n) << nl;
}

int main() {
#ifndef ONLINE_JUDGE
  //freopen("input1.txt","r",stdin);
  //  freopen("output1.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    for(ll i = 1; i <= t; i++){
        doit();
    }
}



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

#define MAX 100000
class Queue
{
    pair<string, int> a[MAX];
    int head;
    int tail;
public:
    Queue() { head = tail = 0; }
    void enqueue(string s, int val) {
        a[tail] = make_pair(s, val);
        tail = (tail + 1) % MAX;
    }
    void dequeue(string& s, int& x) {
        s = a[head].first;
        x = a[head].second;
        head = (head + 1) % MAX;
    }
    bool isEmpty(void) { return head == tail; }
};

int main(void)
{
    int n, q;
    string p_name;
    int p_time;
    int all_time = 0;
    Queue queue;
    
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> p_name >> p_time;
        queue.enqueue(p_name, p_time);
    }
    
    while (!queue.isEmpty()) {
        queue.dequeue(p_name, p_time);
        if (q < p_time) {
            all_time += q;
            queue.enqueue(p_name, p_time-q);
        } else {
            all_time += p_time;
            cout << p_name << " " << all_time << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 7056
#include "bits/stdc++.h"
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr = ds.begin(); itr != ds.end(); ++itr)
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
#define PI 3.1415926536
typedef long long ll;
typedef pair<int, int> P;

int main() {
	int N;
	cin >> N;
	vector<bool> isPrime(N + 1, true);
	vector<int> prime;

	isPrime[0] = isPrime[1] = false;
	rep(i, N + 1) {
		if (!isPrime[i])continue;
		prime.push_back(i);
		rep(j, N / i) {
			isPrime[i*j] = false;
		}
	}
	vector<int> fact(prime.size());
	vector<int> prime_ord(N + 1);
	rep(i, prime.size()) {
		prime_ord[prime[i]] = i;
	}

	repl(i, 2, N + 1) {
		int n = i;
		rep(j, prime.size()) {
			while (n%prime[j] == 0) {
				fact[prime_ord[prime[j]]]++;
				n /= prime[j];
			}
		}
	}

	ll ans = 1;
	rep(i, prime.size()) {
		ans *= fact[i] + 1;
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256