akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define P pair<ll, ll>
#define VI vector<ll>
#define int long long
using namespace std;

int a, b;
void solve() {
  if (a + b == 15) {
    cout << '+' << endl;
  } else if (a * b == 15) {
    cout << '*' << endl;
  } else {
    cout << 'x' << endl;
  }
}

signed main() {
  cin >> a >> b;

  solve();
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(h)]
    B=[list(map(int,input().split())) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    offset=12800
    dp[0][0]|=1<<(x+offset)
    dp[0][0]|=1<<(-x+offset)

    from itertools import product
    for i,j in product(range(h),range(w)):
        if(i==0 and j==0): continue
        x=abs(A[i][j]-B[i][j])
        S=0
        if(i>0): S|=dp[i-1][j]
        if(j>0): S|=dp[i][j-1]
        dp[i][j]=(S<<x)|(S>>x)

    for i in range(12800):
        if((dp[-1][-1]>>(i+offset))&1):
            print(i)
            return
resolve()

Measured memory_bytes: 55132
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fixed cout.setf(ios::fixed);
#define rep1    for( i=0; i<n; i++)
#define Precise cout.precision(7);
using namespace std;

int main()
{
    ll a,b;
    cin>>a;
    if(a%2)
    cout<<a/2+1<<endl;
    else
    cout<<a/2<<endl;

    return 0;
}





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

const int N = 55, P = 1e9 + 7, M = 205;

int n, m, k, dfn[N], cn[N], ans = 1, low[N], bl[N], cnt, stu[N], stv[N], top, tot, C[M][M], si[N], Gr[N];

vector<int>V[N];

void Min (int &x, int y) { if (x > y) x = y; }

void Tarjan (int x, int fa) {
	dfn[x] = low[x] = ++cnt;
	for (auto v : V[x]) if (v != fa) {
		if (!dfn[v]) {
			int la = ++top; stu[top] = x; stv[top] = v;
			Tarjan(v, x);
			if (low[v] > dfn[x]) { ans = 1ll * ans * k % P; top = la - 1; continue ; }
			if (low[v] == dfn[x]) {
				for (++tot; top >= la; --top, ++cn[tot]) {
					if (bl[stu[top]] != tot) {
						bl[stu[top]] = tot;
						++si[tot];
						cn[tot] += Gr[stu[top]];
					}
					if (bl[stv[top]] != tot) {
						bl[stv[top]] = tot;
						++si[tot];
						cn[tot] += Gr[stv[top]];
					}
				}
				cn[tot] -= Gr[x];
			} else Min(low[x], low[v]);
		} else if (dfn[v] <= dfn[x]) Min(low[x], dfn[v]), ++Gr[x];
	}
}

int qp (int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) c = 1ll * c * a % P; return c; }
int gcd (int a, int b) { return b ? gcd(b, a % b) : a; }

int main () {
	scanf("%d%d%d", &n, &m, &k);
	C[0][0] = 1;
	for (int i = 1; i <= m + k; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
	}
	for (int i = 0, u, v; i < m; ++i) {
		scanf("%d%d", &u, &v);
		V[u].emplace_back(v);
		V[v].emplace_back(u);
	}
	for (int i = 1; i <= n; ++i) if (!dfn[i]) Tarjan(i, 0);
//	si[2] = 5; cn[2] = 5; ++tot; si[tot] = 4; cn[tot] = 5;
	for (int i = 1; i <= tot; ++i) {
		if (si[i] != cn[i]) ans = 1ll * ans * C[cn[i] + k - 1][k - 1] % P;
		else {
			int tmp = 0, n = cn[i];
			for (int i = 0; i < n; ++i) tmp = (tmp + qp(k, gcd(i, n))) % P;
			tmp = 1ll * tmp * qp(n, P - 2) % P;
			ans = 1ll * ans * tmp % P;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

int n,m;

void solve(istream& cin, ostream& cout) {
	cin >> n >> m;
	vector<int> A(n);
	cin >> A;
	int total = 0;
	REP(i, n) total += A[i];
	int cnt = 0;
	REP(i, n) if(A[i]*4*m >= total)  cnt++;
	if(cnt >= m) cout << "Yes" << endl;
	else cout << "No" << endl;
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int a,b;
  cin >> a >> b;
  int ans = a;
  if(b<a) --ans;
  cout << ans << endl;
}


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

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    int s, w;
    cin >> s >> w;

    if (w >= s) {
        cout << "unsafe" << endl;
    } else{
        cout << "safe" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
using System;
using System.Linq;
using CompLib.Util;

public class Program
{

    public void Solve()
    {
        var sc = new Scanner();
        string s = sc.Next();
        if (s == "ABC")
        {
            Console.WriteLine("ARC");
        }
        else
        {
            Console.WriteLine("ABC");
        }
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 25816
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pairs;

#define MOD 998244353


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

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}


int main(){
    ll a,b; cin>>a>>b;
    cout<<a*b<<" "<<a*2+b*2<<endl;
    return 0;
}
 
    
    



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

template<typename T>
struct CumulativeSum2D {
    vector<vector<T>> acc;
    CumulativeSum2D(int h = 0, int w = 0) : acc(h + 1, vector<T>(w + 1)) { }
    void add(int i, int j, int x) { acc[i + 1][j + 1] += x; }
    void build() {
        int H = acc.size(), W = acc[0].size();
        for (int i = 1; i < H; i++) for (int j = 1; j < W; j++) {
            acc[i][j] += acc[i][j - 1] + acc[i - 1][j] - acc[i - 1][j - 1];
        }
    }
    T sum(int si, int sj, int ti, int tj) {     // [si, ti) x [sj, tj)
        return acc[ti][tj] - acc[si][tj] - acc[ti][sj] + acc[si][sj];
    }
};

const int INF = (int)1e9 + 7;
int main() {
    int n, k; cin >> n >> k;
    int sz = k * 2;
    CumulativeSum2D<int> acc(sz, sz);
    int black = 0, white = 0;
    while (n--) {
        int x, y; char c; cin >> x >> y >> c;
        acc.add(x % sz, y % sz, c == 'B' ? 1 : -1);
        black += c == 'B';
        white += c == 'W';
    }
    acc.build();
    int ma = -INF;
    for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) {
        int tmp = white;
        tmp += acc.sum(0, 0, i, j);
        tmp += acc.sum(i + k, 0, sz, j);
        tmp += acc.sum(0, j + k, i, sz);
        tmp += acc.sum(i, j, i + k, j + k);
        tmp += acc.sum(i + k, j + k, sz, sz);
        ma = max({ma, tmp, black + white - tmp});
    }
    cout << ma << endl;
    return 0;
}

Measured memory_bytes: 16000
def main():
	x, y, z, k = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = [0]*x*y
	for i in range(x):
		for j in range(y):
			d[i*y+j] = a[i]+b[j]
	d.sort(reverse=True)
	c.sort(reverse=True)

	c_len = min(k, z)
	d_len = min(k, x*y)
	e = [0]*d_len*c_len
	for i in range(d_len):
		for j in range(c_len):
			e[i*c_len+j] = d[i] + c[j]
	e.sort(reverse=True)
	for i in range(k):
		print(e[i])


if __name__ == '__main__':
    main()

Measured memory_bytes: 97660
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long a, b, c, d, k, l, g;
  cin >> a >> b >> c >> d;
  k=c;
  l=d;
  if(c<d){
    k=d;
    l=c;
  }
  g=l%k;
  while(g!=0){
    l=k;
    k=g;
    g=l%k;
  }
  cout << b-a+1-b/c+(a-1)/c-b/d+(a-1)/d+b/(c/k*d)-(a-1)/(c/k*d) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
typedef long long LL;
class ele{
	public:
		LL sz,cnt[30];
		ele(){
			sz=0;
			memset(cnt,0,sizeof(cnt));
		}
		ele(LL SZ,char *inp){
			int xb;
			sz=SZ;
			memset(cnt,0,sizeof(cnt));
			for(xb=0;xb<sz;xb++) cnt[inp[xb]-'a']++;
		}
		inline void print(){
			int xb;
			for(xb=0;xb<26;xb++){
				printf("%lld ",cnt[xb]);
			}
			printf("\n");
		}
}firsts[3][200005],res;
char inp[200005],nxt[500005],nnxt[1000005];
int Z[500005],match[500005],ilen,nlen,match2[500005],nnlen,bct[3];
LL L,R;
vector < ele > eles;
ele operator +(const ele &a,const ele &b){
	ele ret=ele();
	ret.sz=a.sz+b.sz;
	int xb;
	for(xb=0;xb<30;xb++) ret.cnt[xb]=a.cnt[xb]+b.cnt[xb];
	return ret;
}
ele operator -(const ele &a,const ele &b){
	ele ret=ele();
	ret.sz=a.sz+b.sz;
	int xb;
	for(xb=0;xb<30;xb++) ret.cnt[xb]=a.cnt[xb]-b.cnt[xb];
	return ret;
}
void zz(char *fa,int *mth){
	int k,l,r,x2,cnt=0,sfa=strlen(fa);
	l=r=-1;
	memset(mth,0,sizeof(mth));
	match[0]=1;
	memset(Z,0,sizeof(Z));
	for(k=1;k<sfa;k++){
		if(k>r || l==-1){
			for(x2=k;x2<sfa && fa[x2]==fa[x2-k];x2++);
			x2-=k-1;
			if(x2>1){
				Z[k]=x2-1;
			}
		}
		else if(Z[k-l]<=r-k){
			Z[k]=Z[k-l];
		}
		else{
			Z[k]=r-k+1;
			for(x2=r+1;x2<sfa && fa[x2]==fa[x2-k];x2++);
			Z[k]+=x2-r-1;
		}
		if(Z[k]+k-1>r){
			r=Z[k]+k-1;
			l=k;
		}
		if(Z[k]<(sfa>>1)) mth[k+Z[k]-1]=MAX(mth[k+Z[k]-1],Z[k]);
	}
}
inline char *gc(int d){
	return (d?((d==1)?nxt:nnxt):inp);
}
inline void cal(char *stt,int d,int len){
	int xb,x2;
	for(xb=0;;xb++){
		int stp=10*xb;
		if(stp<len){
			ele v=ele(10,stt+stp);
			if(xb) v=v+firsts[d][xb-1];
			firsts[d][xb]=v;
		}
		else break;
	}
	bct[d]=xb;
}
ele getele(LL rb,int p){
	if(rb<0) return ele();
	if(rb>=eles[p].sz-1) return eles[p];
	if(p<3){
		rb=MIN(rb,eles[p].sz);
		ele ret;
		if(rb>=10) ret=firsts[p][rb/10-1]; else ret=ele();
		int xb;
		for(xb=(LL)((LL)rb/10LL)*10LL;xb<=rb;xb++) ret.cnt[gc(p)[xb]-'a']++;
		return ret;
	}
	ele ret=getele(rb,p-1);
	if(rb>=eles[p-1].sz) ret=ret+getele(rb-eles[p-1].sz,p-2);
	return ret;
}
int main(){
	scanf("%s",inp);
	scanf("%lld %lld",&L,&R);
	L--;
	R--;
	zz(inp,match);
	ilen=strlen(inp);
	memcpy(nxt,inp,sizeof(inp));
	memcpy(nxt+ilen,inp+match[ilen-1],sizeof(char)*(ilen-(match[ilen-1]<<1)));
	nlen=strlen(nxt);
	zz(nxt,match2);
	memcpy(nnxt,nxt,sizeof(nxt));
	memcpy(nnxt+nlen,nxt+match2[nlen-1],sizeof(char)*(nlen-(match2[nlen-1]<<1)));
	nnlen=strlen(nnxt);
	eles.resize(3);
	int xb,x2;
	eles[0]=ele((ilen>>1),inp);
	eles[1]=ele((nlen>>1),nxt);
	eles[2]=ele((nnlen>>1),nnxt);
	while(eles.back().sz<=R){
		eles.push_back(eles.back()+eles[eles.size()-2]);
	}
	cal(inp,0,ilen);
	cal(nxt,1,nlen);
	cal(nnxt,2,nnlen);
	res=getele(R,eles.size()-1)-getele(L-1,eles.size()-1);
	res.print();
	return 0;
}

Measured memory_bytes: 152832
n=gets.chomp.to_i
ary=gets.chomp.split(" ").map(&:to_i)

i = 0
ttl = 0
ary.each do |a|
  if i <= a
    i = a
  else
    ttl += (i - a)
    i = a
  end
end

puts (ttl + ary[-1])

Measured memory_bytes: 1788
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<iso646.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

#define FOR(counter,initial_value,condition) for(int counter = initial_value; counter < condition;counter++)

int digitSum(int n,int digit=8) {
	// digit > 2
	int x = 1;
	FOR(i,0,digit){
		x *= 10;
	}
	int sum = 0;
	FOR(i, 0, digit) {
		sum += n / x;
		n %= x;
		x /= 10;
	}
	sum += n;
	return sum;
}

int main()
{
	int n, k;
	cin >> n >> k;
	int min = 3000;
	int tmp;
	FOR(i, 0, n+1) {
		tmp = std::pow(2, i) + (n - i)*k;
		if (tmp < min) min = tmp;
	}
	cout << min << endl;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(void){
    int A, B, K;
    scanf("%d %d %d",&A,&B,&K);
    int i;
    for(i=A;i<=B;i++){
        if(A+K-1>=i||i>=B-K+1){
            printf("%d\n",i);
        }
    }
    return 0;
}

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

int main(){
    ll N, M ; cin >> N >> M;
    ll res = 0;
    if(N == 1){
        if(M == 1) cout << 1 << endl;
        else cout << M - 2 << endl;
    }else if(M == 1){
        cout << N - 2 << endl;
    }else{
        cout << (N - 2) * (M - 2) << endl;
    }
}

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

const int MAX_N = 20002;
int N;

int P[MAX_N];

ll A[MAX_N];
ll B[MAX_N];

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

    cin >> N;

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

    for (int i = 0; i < N; ++i) {
        A[i] = 30000 * (i + 1) + 1;
        B[i] = 30000 * (N - (i+1) + 1) + 1;
    }

    for (int i = 0; i < N; ++i) {
        B[P[i]] += i;
    }


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

    for (int i = 0; i < N; ++i) {
        cout << B[i];
        if (i != N-1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 1024
h,w,a,b=map(int,input().split())
plus=[0 if i<a else 1 for i in range(w)]
minus=[1 if i<a else 0 for i in range(w)]

for i in range(h):
    if i<b:
        print(*plus,sep="")
    else:
        print(*minus,sep="")

Measured memory_bytes: 69596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;cin>>s>>t;
    int a,b;cin>>a>>b;
    string u; cin>>u;
    if(u==s) a--;
    else b--;
    cout<<a<<" "<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
	int d,l,ans,ans1;
	cin>>d>>l;
	if(d%l==0){
		cout<<d/l<<endl;
	}else{
		cout<<d/l+d%l<<endl;
	}
	return 0;
}

Measured memory_bytes: 3120
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

a, b = map(int, input().split())

a_div = divisor(a)
b_div = divisor(b)
ans = set(a_div) & set(b_div)

count = 0
for i in ans:
    if is_prime(i):
        count += 1

print(count + 1)

Measured memory_bytes: 41840
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int n,t; cin >> n >> t;
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    priority_queue<int,vector<int>,greater<>>que;
    map<int,int>mp;
    int maxi = -INF;
    for(auto e : v){
        if(que.size() == 0){
            que.push(e);
            mp[e]++;
        } else {
            int dif = e - que.top();
            que.push(e);
            if(dif > 0){
                mp[dif]++;
                cmax(maxi,dif);
            }
        }
    }
    cout << max(1LL,mp[maxi]) << endl;
}



Measured memory_bytes: 8052
#include<bits/stdc++.h>
/**CLICK ss---> ctrl+j**/
#define PI 2.0*acos(0.0)
#define ll              long long int
#define gcd(a,b)        __gcd(a,b)
#define lcm(a,b)        ((a)*(b))/gcd(a,b)
#define MOD             1000000007
#define mx              123456789
using namespace std;
void solve()
{
   char c;
   cin>>c;
   if(c>='A' && c<='Z')
    cout<<'A'<<endl;
   else
    cout<<'a'<<endl;
}
int main()
{
    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3620
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

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

		List<List<Integer>> g = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			g.add(new ArrayList<>());
		}
		for (int i = 0; i < N - 1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			g.get(a).add(b);
			g.get(b).add(a);
		}

		long[] counter = new long[N + 1];

		for (int i = 0; i < Q; i++) {
			int p = sc.nextInt();
			int x = sc.nextInt();
			counter[p] += x;
		}

		sc.close();

		boolean[] visited = new boolean[N + 1];
		Queue<Integer> q = new ArrayDeque<>();
		q.add(1);
		visited[1] = true;

		while (!q.isEmpty()) {
			int n = q.poll();

			for (int m : g.get(n)) {
				if (!visited[m]) {
					counter[m] += counter[n];
					q.add(m);
					visited[m] = true;
				}
			}
		}

		StringBuffer ans = new StringBuffer();
		for (int i = 1; i <= N; i++) {
			ans.append(counter[i]);
			ans.append(" ");
		}

		out.println(ans.substring(0, ans.length() - 1));

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 196108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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; }




int main() {
  string s;
  cin >> s;
  int n;
  n = s.length();

  int ref = n;
  bool flug = true;
  while(n>=7){
    if(s[ref-1]=='m' && s[ref-2]=='a' && s[ref-3]=='e' && s[ref-4]=='r' && s[ref-5]=='d') {
      n -= 5;
      ref -= 5;
    }
    else if(s[ref-1]=='r' && s[ref-2]=='e' && s[ref-3]=='m' && s[ref-4]=='a' && s[ref-5]=='e' && s[ref-6]=='r' && s[ref-7]=='d'){
      n -= 7;
      ref -= 7;
    }
    else if(s[ref-1]=='e' && s[ref-2]=='s' && s[ref-3]=='a' && s[ref-4]=='r' && s[ref-5]=='e') {
      n -= 5;
      ref -= 5;
    }
    else if(s[ref-1]=='r' && s[ref-2]=='e' && s[ref-3]=='s' && s[ref-4]=='a' && s[ref-5]=='r' && s[ref-6]=='e'){
      n -= 6;
      ref -= 6;
    }
    else{
      flug = false;
      n = 0;
    }
  }

  // cout << ref-1 << endl;
  // cout << s[ref-5] << endl;
  // cout << n << endl;

  if(n==5){
    if(s[ref-1]=='m' && s[ref-2]=='a' && s[ref-3]=='e' && s[ref-4]=='r' && s[ref-5]=='d');
    else if(s[ref-1]=='e' && s[ref-2]=='s' && s[ref-3]=='a' && s[ref-4]=='r' && s[ref-5]=='e');
    else flug = false;
  }
  else if(n==6){
    if(s[ref-1]=='r' && s[ref-2]=='e' && s[ref-3]=='s' && s[ref-4]=='a' && s[ref-5]=='r' && s[ref-6]=='e');
    else flug = false;
  }
  else if(n==0);
  else flug = false;

  if(flug == true) cout << "YES" << endl;
  else cout << "NO" << endl;
}



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

int main(){
	int a;
	int b;
	cin>>a;
	cin>>b;
	if (a<b){
	cout<<"a < b"<<endl;
	}
	if (a>b){
	cout<<"a > b"<<endl;
	}
	if (a==b){
	cout<<"a == b"<<endl;
}
    return 0;
}
    
    
    
    
  
   



	
	
	
	




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

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;
    set<string> check;

    char prev;
    REP(i, N) {
        string s;
        cin >> s;

        if (check.count(s) >= 1) {
            cout << "No" << endl;
            return 0;
        }

        if (i > 0 && s[0] != prev) {
            cout << "No" << endl;
            return 0;
        }

        prev = s[s.size()-1];
        check.insert(s);
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
struct edge{ll to,cost;};
const int inf = 1<<28;
const ll INF = 1LL<<53;
const int COMBMAX = 500005;
const ll MOD = 1e9+7;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;++i)
#define repf(i,n) for(int i=0;i<=n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eachdo(v, e) for(const auto& e : v)
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance(v.begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance(v.begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n,ll mod=MOD){ll res=1;while(n>0){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v,a)-lower_index(v,a);} 
template<class T> bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
template<class T> void debug2(T v){rep(i,v.size()){rep(j,v[i].size())cout<<v[i][j]<<" ";cout<<endl;}}
template<class T> void rdv(T &v){rep(i,v.size())cin>>v[i];}
template<class T> void rdvv(T &v){rep(i,v.size()){rep(j,v[i].size())cin>>v[i][j];}}
// multimap
// mmap.emplace(key,value);
// auto ngw = list.equal_range("");
// for(auto e = ngw.first; it != ngw.second ; ++e)

struct SegmentTree{
private:
    ll unit = 0;
    ll op(ll a,ll b){return a + b;}
    ll n;
    vector<ll> node;

public:
SegmentTree(vector<ll> v){
    ll sz = (ll)v.size();
    n = 1;while(n<sz) n *= 2;
    node.resize(2*n-1,unit);
    for(ll i=0;i<sz;i++) node[i+n-1]=v[i];
    for(ll i=n-2;i>=0;i--) node[i]=op(node[2*i+1],node[2*i+2]);
}

    void update(ll x,ll val){
        x += n-1;
        node[x] = val;
        while(x>0){
            x = (x-1)/2;
            node[x] = op(node[2*x+1],node[2*x+2]);
        }
    }

    ll query(ll a,ll b,ll k = 0,ll l = 0,ll r = -1){
        if (r<0) r = n;
        if (r<=a || b<=l) return unit;
        if (a<=l && r<=b) return node[k];
        ll vl = query(a,b,2*k+1,l,(l+r)/2);
        ll vr = query(a,b,2*k+2,(l+r)/2,r);
        return op(vl,vr);
    }
};

int main(){
    ll N; cin >> N;
    vl a(N); rdv(a);
    SegmentTree st(a);
    ll ans = INF;
    rep(i,N-1){
        chmin(ans,abs(st.query(0,i+1) - st.query(i+1,N)));
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#define int long long

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, s;
    
    cin >> a >> s;
    
    int ans = (a-2) * (s-2);
    
    if(a == 1 || s == 1)
    {
        ans = a + s - 3;
    }
    if(a == 1 && s == 1)
    {
        ans = 1;
    }
    if(a == 2 || s == 2)
    {
        ans = 0;
    }
    
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n,h=0,m=0,s=0,a;
    scanf("%d",&n);
    if(n<60){
        s=n;
    }
    else if(n<3600){
        m=n/60;
        s=n%60;
    }
    else{
       h=n/(60*60);
       a=n%(60*60);
       m=a/60;
       s=a%60;
    }
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}



Measured memory_bytes: 2064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n,t;cin>>n>>t;
    vint a(n);
   rep(i,n) cin>>a[i];

   int res=t;
   rep(i,n-1) res+=min(t,a[i+1]-a[i]);
   cout<<res<<endl;
}

Measured memory_bytes: 4728
class Problem
  attr_accessor :a, :b, :n, :m, :h, :w

  def initialize
    @n = gets.to_s.to_i
    @a = Array.new(n){ gets.to_s.to_i }
  end

  def solve
    a.inject(1, &:lcm)
  end

  def show(ans)
    puts ans
  end
end

Problem.new.instance_eval do
  show(solve)
end


Measured memory_bytes: 14264
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100001
#define ll long long
#define dmp make_pair
#define dpb push_back
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);
const int inf = 2147483647;

int n, dat[10*MAX];
void init(int m){
	n = 1;
	while(n < m)n *= 2;
	for(int i = 0;i < 2*n;i++)dat[i] = inf;
}

void change(int x, int y){
	x += n-1;
	dat[x] = y;
	while(x > 0){
		x = (x-1)/2;
		dat[x] = min(dat[x*2+1], dat[x*2+2]);
	}
}

int query(int a, int b, int k, int l, int r){
	if(b <= l || r <= a)return inf;
	if(a <= l && r <= b)return dat[k];
	int vl = query(a, b, 2*k+1, l, (l+r)/2);
	int vr = query(a, b, 2*k+2, (l+r)/2, r);
	return min(vl, vr);
}

int main(){
	int m, q, c, x, y, ans;
	scanf("%d%d", &m, &q);
	init(m);
	while(q--){
		scanf("%d%d%d", &c, &x, &y);
		if(!c)change(x, y);
		else printf("%d\n", query(x, y+1, 0, 0, n));
	}
	return 0;
}

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

const ll INF = pow(10, 9) + 7;

int main() {
  int n;
  cin >> n;
  string s,t;
  cin >> s >> t;
  rep(i,2*n){
    if(i%2==0) cout << s.at(i/2);
    if(i%2==1) cout << t.at(i/2);
  }
}

Measured memory_bytes: 256
import sys
from statistics import median

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 0


def resolve():
    def dfs(S):
        """ デバッグ用 """
        global res
        if len(S) == 1:
            res = S[0]
            return

        tmp = []
        for i in range(1, len(S) - 1):
            t = median([S[i - 1], S[i], S[i + 1]])
            tmp.append(t)
        dfs(tmp)

    n, x = map(int, input().split())
    if x == 1 or x == 2 * n - 1:
        print("No")
        exit()
    n = 2 * n - 1
    ans = [0] * n
    num = x
    for i in range(n // 2, n):
        ans[i] = num
        num += 1
        if num > n:
            num = 1
    for i in range(n // 2):
        ans[i] = num
        num += 1
        if num > n:
            num = 1
    print("Yes")
    print(*ans, sep="\n")
    # dfs(ans)
    # print(res == x)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 21916
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

class UnionFind{
public:
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

int main(){
    init();
	ll N;
	cin>>N;
	ll max=pow(10,5)+5;
	UnionFind uf=UnionFind(max*2);
	vector<ll>x(N);
	vector<ll>y(N);
	for(int i=0;i<N;i++){
		cin>>x[i]>>y[i];
		uf.unite(x[i],max+y[i]);
	}
	//xの連結成分ごとの個数
	vector<ll>xnum(2*max,0);
	vector<ll>ynum(2*max,0);
	for(int i=0;i<max;i++){
		xnum[uf.find(i)]++;
	}
	for(int i=max;i<2*max;i++){
		ynum[uf.find(i)]++;
	}
	ll ans=0;
	for(int i=0;i<2*max;i++){
		ans+=xnum[i]*ynum[i];
	}
	cout<<ans-N<<endl;
}

Measured memory_bytes: 5760
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <map>
#include <cstring>
using namespace std;

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

int m, n;
pair<int,int> bloc[100][100], tmp[100][100];

void dfs(int idx, int x, int y, int dist) {
    if (dist < bloc[y][x].second) {
        bloc[y][x] = make_pair(idx, dist);
        for (int i=0; i<6; ++i) {
            if (0 <= x+dx[y%2][i] && x+dx[y%2][i] < m &&
                0 <= y+dy[y%2][i] && y+dy[y%2][i] < n) {
                dfs(idx, x+dx[y%2][i], y+dy[y%2][i], dist+1);
            }
        }
    } else if (idx != bloc[y][x].first && dist == bloc[y][x].second) {
        bloc[y][x] = make_pair(-1, dist);
    }
}

int main() {
    while (cin >> m >> n, (m || n)) {
        for (int i=0; i<100; ++i) for (int j=0; j<100; ++j) {
            bloc[i][j] = make_pair(INT_MAX, INT_MAX);
        }
        int s;
        cin >> s;
        int x, y;
        for (int i=0; i<s; ++i) {
            cin >> x >> y;
            dfs(i, x-1, y-1, 0);
        }
        int t;
        cin >> t;
        int p, q, res = 0;
        for (int i=0; i<t; ++i) {
            cin >> p >> q;
            memcpy(tmp, bloc, sizeof bloc);
            dfs(s, p-1, q-1, 0);
            int cnt = 0;
            for (int i=0; i<n; ++i) {
                for (int j=0; j<m; ++j) {
                    if (bloc[i][j].first == s) {
                        ++ cnt;
                    }
                }
            }
            res = max(res, cnt);
            memcpy(bloc, tmp, sizeof tmp);
        }
        cout << res << endl;
    }
    return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  if ((a + b) % 2 == 0) {
    cout << (a+b)/2 << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }  
  return 0;
}

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

int main(){
    ll x; cin>>x;
    ll ans=100;
    int year=0;
    while(ans<x){
        ans+=ans/100;
        year++;
    }
    cout<<year<<endl;
    return 0;
}


Measured memory_bytes: 3644
//10-4 カード並べ
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<time.h>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<set>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<random>
#include<cassert>
using namespace std;
#define LL long long
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define ROOP() while(true)

int n,k;
int num[10];
bool used[10];
set<string> ans;

void choose(string now, int nokori){
    if(nokori==0){
        ans.insert(now);
    }
    else{
        for(int i=0; i<n; i++){
            if(used[i] == false){
                used[i] = true;
                choose(to_string(num[i])+now, nokori-1);
                used[i] = false;
            }
        }
    }
}

int main(){
    ROOP(){
        cin >> n >> k;
        if(n==0 && k==0) break;

        ans.clear();

        for(int i=0; i<n; i++){
            int tmp;
            cin >> tmp;
            num[i] = tmp;
            used[i] = false;
        }

        for(int i=0; i<n; i++){
            used[i] = true;
            choose(to_string(num[i]), k-1);
            used[i] = false;
        }

        cout << ans.size() << endl;
    }
    return 0;
}



Measured memory_bytes: 3456
def solve():
    N = int(input())
    t, x, y = 0, 0, 0
    for i in range(N):
        t_i, x_i, y_i = list(map(int, input().split()))
        delta_t = t_i - t
        distance = x_i - x + y_i - y
        if not (delta_t >= distance and (delta_t - distance) % 2 == 0):
            print("No")
            return
        else:
            t, x, y = t_i, x_i, y_i
    print("Yes")
            


solve()

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

const int N = 100010;
vector<pair<int, int>> G[N];
vector<int> C(N);
vector<bool> seen(N);

int n;

void dfs(int now, int pre){
    seen[now] = true;
    for(int i = 0; i < G[now].size(); i++){
        int to = G[now][i].first;
        if(to == pre or seen[to]) continue;
        
        int cost = G[now][i].second;
        if(cost % 2){
            C[to] = C[now] ^ 1;
        }else{
            C[to] = C[now];
        }
        dfs(to, now);
    }
}


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

    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        w %= 2;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    dfs(0, -1);

    for(int i = 0; i < n; i++){
        cout << C[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 9216
/**
 *   author: Shubham Srivastava
 *   created: 31 May 2020  17:44:23
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define MOD 1000000007
#define INF 0x7fffffff
#define sorti(v) sort(v.begin(),v.end())
#define sortd(v) sort(v.rbegin(),v.rend())
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
ll parent[2000005];

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int a,b;cin>>a>>b;
    cout<<a*b;
return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
 
		int L = 0;
		int R = N;
 
		for (int i=0; i<M; i++) {
			int L2 = sc.nextInt();
			int R2 = sc.nextInt();
 
			L = Math.max(L, L2);
			R = Math.min(R, R2);
		}
 
		int ans = R-L+1;
		if (ans>0) System.out.println(ans);
		else System.out.println(0);
	}
}

Measured memory_bytes: 61288
/*
m 个数的集合的中位数定义成将集合升序排序之后得到的数组中下标(从 0 开始)为
floor(m/2) 的数.

求所有连续子串的中位数的中位数.

对一个含有 n 个数的集合, x 如果是它的中位数, 等价于:

1. <= x 的数至少有 floor(n/2) 个;
2. x 是满足 1 的数中最小的.

如果一个子串长度是 l, 那么至少有 floor(l/2) 个数 <= 其中位数; 又假设这个中位数 <=
x, 那么就有 floor(l/2) 个数 <= x.

<= x 者设为 n1 个, > x 者设为 n2 个:

  n1 >= floor(l/2)
  n2 <= l-floor(l/2) = ceil(l/2)
  n2 - n1 <= ceil(l/2) - floor(l/2) = l % 2

当 l % 2 == 0, 要求  >= 0.

当 l % 2 == 1, 要求 n1-n2 >= 1, 但是 n1-n2 = 0 的情况是不可能存在的(否则
l=n1+n2 是偶数), 所以也等价于 n1-n2 >= 0.

于是对 >= x 者取 f[] 为 1, 对 < x 者取 -1, 数列中位数 >= x 等价于 f[] 的和 >= 0.

设 sum[i] 是 f[0] + f[1] + ... + f[i-1], sum[0] 设为 0.

每个 sum[j]-sum[i] (0 <= i < j <= n) 都对应一个子串的 f 的和. 每个和只要 >= 0
则说明有一个子串的中位数 >= x. 即要判断其个数是否是 >= ceil(子串数 / 2) 的.

sum[j]-sum[i] >= 0, 意味着 sum[j] >= sum[i], 也就是要在 sum 数组上统计逆序数.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

typedef long long llong;

constexpr int kMaxN = 1e5 + 10;

template <typename T>
void CopyN(T* dst, T* src, int n) {
  if (n <= 0) {
    return;
  }
  memcpy(dst, src, sizeof(T) * n);
}

llong MergeSort(int a[], int n, int aux[]) {
  llong cnt = 0;
  for (int d = 1; d <= n; d <<= 1) {
    int d2 = (d << 1);
    for (int l = 0; l < n; l += d2) {
      int m = std::min(l + d, n);
      int r = std::min(m + d, n);

      int w = l;
      int u = l;
      int v = m;

      while (u < m && v < r) {
        if (a[u] <= a[v]) {
          aux[w++] = a[u++];
          cnt += r - v;
        } else {
          aux[w++] = a[v++];
        }
      }

      CopyN(aux + w, a + u, m - u);
      CopyN(aux + w, a + v, r - v);
    }
    CopyN(a, aux, n);
  }
  return cnt;
}

llong Count(int a[], int n, int mid) {
  static int sum[kMaxN];
  static int aux[kMaxN];

  sum[0] = 0;
  for (int i = 0; i < n; ++i) {
    sum[i + 1] = sum[i] + (a[i] >= mid ? 1 : -1);
  }

  return MergeSort(sum, n + 1, aux);
}

int main() {
  int n;
  scanf("%d", &n);

  static int a[kMaxN];
  int maxa = 10;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    maxa = std::max(maxa, a[i]);
  }

  llong total = static_cast<llong>(n) * (n + 1) / 2;
  llong total2 = (total + 1) / 2;
  int low = 0;
  int upp = maxa + 10;

  while (upp - low > 1) {
    int mid = (low + upp) / 2;
    if (Count(a, n, mid) >= total2) {
      low = mid;
    } else {
      upp = mid;
    }
  }

  printf("%d\n", low);
  return 0;
}


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

vector<string> subs(string s) {
  int parcnt = 0;
  for (auto c: s) {
    if (c == '[') parcnt++;
  }
  if (parcnt == 1) {
    vector<string> ss;
    ss.push_back(s.substr(1, s.size() - 2));
    return ss;
  }
  parcnt = 2;
  vector<string> ss;
  string cur = "[";
  for (int i = 2; i < s.size() - 1; i++) {
    char c = s[i];
    if (c == '[') {
      parcnt++;
      cur += c;
    } else if (c == ']') {
      parcnt--;
      if (parcnt == 1) {
        cur += ']';
        ss.push_back(cur);
        cur = "";
      } else {
        cur += c;
      }
    } else {
      cur += c;
    }
  }
  return ss;
}

long findmin(string s) {
  if (s[0] != '[') {
    return stoi(s) / 2 + 1;
  }
  vector<long> vs;
  for (auto a: subs(s)) {
    vs.push_back(findmin(a));
  }
  long ret = 0;
  sort(vs.begin(), vs.end());
  for (int i = 0; i < vs.size() / 2 + 1; i++) {
    ret += vs[i];
  }
  return ret;
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    cout << findmin(s) << endl;
  }
}



Measured memory_bytes: 3288
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[2500];
void init(){
    for(int i=3; i<=2000; i++){
        dp[i]=1;
        if(i-3>=3){///dp[i]=1;
            for(int j=3; j<=i-3; j++)dp[i]=(dp[i]+dp[j])%mod;
        }
    }
}
int main()
{
    init();
    int n;cin>>n;
    if(n<=2)return cout<<0<<endl,0;
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 3148
# coding=utf-8

###
### for atcorder program
###

import sys
import math
import array

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

def main():
    N, K = [int(x) for x in input().split()]

    A = N - K
    B = N % K

    if B == 0:
        print("0")
    else:
        print(A)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = 1e17;
const ll MOD = 1e9+7;

int main() {
    // input, ready, resolve
    int N;
    cin >> N;
    map<string,int> map;

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        map[str]++;
    } 
    vector<pair<int,string>> vp;
    for (auto m : map) {
        vp.push_back(make_pair(m.second, m.first));
    }
    sort(vp.begin(), vp.end());
    int maxnum = vp[vp.size()-1].first;
    for (auto v : vp) {
        if (v.first == maxnum) {
            cout << v.second << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 29040