akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

int n;
const int n_max = 505;
int A[n_max][n_max];


void solve(int l, int r, int cnt){
    if(l +1 >= r ) return;
    int mid = (l + r) / 2;
    FOR(i,l,mid){
        FOR(j,mid,r){
            A[i][j] = cnt;
            A[j][i] = cnt;
        }
    }
    solve(l,mid,cnt + 1);
    solve(mid,r,cnt + 1);
}

signed main(){
    cin >> n;
    solve(0,n,1);
    REP(i,n-1){
        FOR(j,i+1,n){
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 2432
import sys
sys.setrecursionlimit(10**9)

N = int(input())
T = [[] for _ in range(N+1)]

for _ in range(N-1) :
    a,b,c = map(int,input().split())
    T[a].append([b,c])
    T[b].append([a,c])

Q,K = map(int,input().split())

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = []

for _ in range(Q) :
    u,v = map(int,input().split())
    ans.append(dist[u]+dist[v])

print(*ans,sep="\n")


Measured memory_bytes: 140588
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long double a,b,h,m;
  cin>>a>>b>>h>>m;
  long double rad = PI * 2 * ((long double)h / 12.0 + ((long double)m / 60.0) / 12.0 - (long double)m / 60.0);
  cout<<fixed<<stp(17)<<sqrt((long double)(a*a)+(long double)(b*b)-(long double)(2.0*a*b*cos(rad)))<<'\n';
  return(0);
}


Measured memory_bytes: 4180
N = gets.chomp.to_i
A = gets.chomp.split(' ').map(&:to_i)

ans = []

maxi = 0
mini = 0
max = A[maxi]
min = A[mini]

(1..(N-1)).each do |i|
    if A[i] > max
        max = A[i]
        maxi = i
    end

    if A[i] < min
        min = A[i]
        mini = i
    end
end

basei = maxi
base = max

if min >= 0
    base = max
    basei = maxi

    (0..(N-2)).each do |i|
        ans << [i, i + 1]
    end
elsif max < 0
    base = min
    basei = mini

    (0..(N-2)).each do |i|
        ans << [N-1 - i, N-2 - i]
    end
elsif max.abs >= min.abs
    base = max
    basei = maxi

    (0..(N-1)).each do |i|
        ans << [basei , i] unless i == basei
    end
    (0..(N-2)).each do |i|
        ans << [i, i + 1]
    end
else
    base = min
    basei = mini

    (0..(N-1)).each do |i|
        ans << [basei , i] unless i == basei
    end
    (0..(N-2)).each do |i|
        ans << [N-1 - i, N-2 - i]
    end
end



# newa = A.map.with_index do |a, i|
#     if i == basei
#         a
#     else
#         ans << [basei, i]
#         a + base
#     end
# end

# (0..(N-2)).each do |i|
#     if newa[i] > newa[i+1]
#         if base >= 0
#             ans << [i, i+1]
#         else
#             ans << [i+1, i]
#         end
#     end
# end

puts ans.length
ans.each do |a|
    puts "#{a[0] + 1} #{a[1] + 1}"
end


Measured memory_bytes: 1788
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))

h,w = list(map(int, input().split()))

s = []
for i in range(h):
    ss=[]
    a=input()
    for j in range(w):
        if(a[j]=='.'):
            ss.append(0)
        else:
            ss.append(1)
    s.append(ss)
        
dp = [[999 for j in range(w)]for i in range(h)]
dp[0][0] = s[0][0]

for i in range(h+w-2):
    for j in range(i+2):
        x = j
        y = i+1-j
        
        if(0<= x and x<=h-1 and 0<=y and y<=w-1):
            #print(x,y)
            if(s[x][y]==0):
                dp[x][y] = min(dp[max(0,x-1)][y], dp[x][max(0,y-1)])
            else:
                if(x!=0 and s[x-1][y]==1):
                    dp[x][y] = dp[x-1][y]
                elif(x!=0 and s[x-1][y]==0):
                    dp[x][y] = dp[x-1][y]+1
                if(y!=0 and s[x][y-1]==1):
                    dp[x][y] = min(dp[x][y],dp[x][y-1])
                elif(y!=0 and s[x][y-1]==0):
                    dp[x][y] = min(dp[x][y],dp[x][y-1]+1)
                   




print(dp[-1][-1])













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

using namespace std;

using ll = long long;
using ii = pair<int,int>;

#define ff first
#define ss second

const int maxn = 2e5+10;

int p[maxn],sz[maxn];

void init(){
	for(int i=0;i<maxn;++i){
		p[i]=i;
		sz[i]=1;
	}
}

int find_set(int x){
	return p[x] == x ? x : p[x] = find_set(p[x]);
}

void union_set(int a,int b){
	a = find_set(a);
	b = find_set(b);
	if(a==b) return;
	if(sz[a]>sz[b])swap(a,b);
	p[a]=b;
	sz[b]+=sz[a];
}

vector<int> g[maxn],ts;
bitset<maxn> vs;

int cicle=0;

void dfs(int x){
	if(vs[x]){
		cicle=x;
		return;
	}
	vs[x]=true;
	for(auto &u:g[x])
		dfs(u);
	ts.push_back(x);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	int n;
	ll k;
	cin >> n >> k;
	vector<int> A(n);
	for(int i=1;i<=n;++i){
		cin >> A[i-1];
		g[i].push_back(A[i-1]);
	}
	dfs(1);
	reverse(ts.begin(),ts.end());
	vector<int> towns;
	//cout << "cicle start at value = " << cicle << '\n';
	for(int i=0;i<ts.size();++i){
		//cout << ts[i] << " \n"[i==ts.size()-1];
		if(ts[i]==cicle){
			for(int j=i;j<ts.size();++j)
				towns.push_back(ts[j]);
			break;
		}
	}
	if(k<ts.size()){
		cout << ts[k] << '\n';
	}
	else{
		k-=ts.size();
		//cout << "k = " << k << " towns.size() = "<< towns.size() << " k%t.sz() = "<< k%towns.size() << '\n';
		cout << towns[k%towns.size()] << '\n';
	}
	return 0;
}

Measured memory_bytes: 27512
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} 



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

int N, x; cin >> N >> x;

if (x == 1 || x == 2*N-1)
    cout << "No\n";
else if (N == 2) 
    cout << "Yes\n1\n2\n3";
else if (x == 2){
    cout << "Yes\n";
    rep(i, 5, N+3) cout << i << "\n";
    cout << "3\n2\n1\n4\n";
    rep(i, N+3, 2*N) cout << i << "\n";
}
else {
    cout << "Yes\n";
    VI n(2*N-1); iota(ALL(n), 1);
    n.erase(RANGE(n, x-3, x+1));
    VI I = {x-1, x, x+1, x-2};
    n.insert(n.begin()+(N-2), ALL(I));
    for(int i:n) cout << i << "\n";
}

return 0;
}
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。
// 実行エラー：vector添え字超え．0割り．



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

int main(void){
  int x, y;

  cin >> x >> y;

  if(x == 2 || y == 2) cout << "No" << endl;
  else if(y <= 7){
    if(((x%2) && (y%2)) || (!(x%2) && !(y%2)))
      cout << "Yes" << endl;
    else cout << "No" << endl; 
  }
  else if(y > 7){
    if(x > 7){
      if(((x%2)&&(y%2)) || (!(x%2)&&!(y%2)))
        cout << "Yes" << endl;
      else cout << "No" << endl;
    }
    else{
      if(((x%2)&&!(y%2)) || (!(x%2)&&(y%2)))
        cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }


  return 0;
}

Measured memory_bytes: 256
s = input()
s2 = list(s)
ch = [chr(i) for i in range(97, 97+26)]
flg = 0
for k in ch:
	if not k in s2:
		s += k
		flg = 1
		break

if flg == 1:
	print(s)
	exit(0)
else:
	l = len(s)
	ans = ''
	for i in range(l-1,0,-1):
		for k in ch:
			if k <= s[i]:
				continue
			elif not k in s2[:i]:
				ans = s[:i] + k
				print(ans)
				exit(0)

	if s[0] == 'z':
		print(-1)
	else:
		print(chr(ord(s[0])+1))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<60)
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define dbgp(x) cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa

using namespace std;

struct yes { int p1, p2, p3, p4; };

const int mod = 1000000007;
int d[10005][10][100][2];
///d[nr cifre][ult cifra][rest mod k][exista cifra strict mai mica decat cea din n?]

int modk (int a, int b, int k) {
  return (a+b) % k;
}

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

int main () {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  string n; int k; cin >> n >> k;
  for (char &ch: n) ch -= '0'; ///wow!!
  int i, j, x, y, z, ans = 0;
  d[0][0][0][0] = 1;
  for (i = 0; i < sz(n); i++)
    for (j = 0; j <= 9; j++)
      for (x = 0; x < k; x++) {
        mad(d[i+1][n[i]][modk(x,n[i],k)][0], d[i][j][x][0]);
        for (z = 0; z < n[i]; z++) mad(d[i+1][z][modk(x,z,k)][1], d[i][j][x][0]);
        for (z = 0; z <= 9; z++) mad(d[i+1][z][modk(x,z,k)][1], d[i][j][x][1]);
      }
  for (j = 0; j <= 9; j++) {
    mad(ans, d[sz(n)][j][0][0]);
    mad(ans, d[sz(n)][j][0][1]);
  }
  cout << (ans-1+mod) % mod;///d[0][0][0][0]
  ///exista alt mod?
  return 0;
}


Measured memory_bytes: 78464
#include<iostream>
using namespace std;
#include<string>
#include<utility>
#include<algorithm>
#include<vector>

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

Measured memory_bytes: 3968
# -*- coding: utf-8 -*-
"""
Created on Thu May  7 14:17:13 2020

@author: shinba
"""
import sys

A = [list(map(int,input().split())) for i in range(3)]
N = int(input()) 
Bingo = [[0 for i in range(3)] for j in range(3)]

for i in range(N):
    b = int(input())
    for j in range(3):
        for k in range(3):
            if A[j][k] == b:
                Bingo[j][k] = 1

for i in range(3):
    if Bingo[i] == [1,1,1]:
        print("Yes")
        sys.exit()
    if Bingo[0][i] == 1 and Bingo[1][i] == 1 and Bingo[2][i] == 1:
        print("Yes")
        sys.exit()

if Bingo[0][0] == 1 and Bingo[1][1] == 1 and Bingo[2][2] == 1:
    print("Yes")
    sys.exit()
if Bingo[2][0] == 1 and Bingo[1][1] == 1 and Bingo[0][2] == 1:
    print("Yes")
    sys.exit()

print("No")

        



Measured memory_bytes: 3064
#include <iostream>
#include <istream>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
	//マッチした単語数
	int cnt = 0;

	//単語
	string W;

	//文章
	string T;

	string eot = "END_OF_TEXT";

	//単語を入力
	cin >> W;

	//単語Wは全て小文字に変換する
	transform(W.begin(), W.end(), W.begin(), ::tolower);

	//1行ずつ文章を入力
	while(getline(cin, T))
	{
		//"END_OF_TEXT"が入力されたら終了
		if(T == eot) break;

		string tmp;
		istringstream stream(T);

		//空白区切りで文字列を読み込む
		while(getline(stream, tmp, ' '))
		{
			//読み込んだ文字列tmpはすべて小文字に変換する
			transform(tmp.begin(), tmp.end(), tmp.begin(), ::tolower);

			//読み込んだ単語が入力した単語Wと一致
			if( tmp == W )
			{
				cnt++;
			}
		}
	}

	//マッチした単語数を出力
	cout << cnt << endl;

	return 0;
}


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

using namespace std;

int main(){

	int n;
	int p,d1,d2;
	int max_n,max_i;

	while(1){

		cin>>n;
		if(n==0) break;

		max_i=-1;
		max_n=-1;

		for(int i=0;i<n;i++){
			cin>>p>>d1>>d2;
			if(d1+d2>max_n){
				max_n=d1+d2;
				max_i=p;
			}
		}

		cout<<max_i<<" "<<max_n<<endl;
	}

}

Measured memory_bytes: 1160
a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if i * 500 + j * 100 + k * 50 == x:
        ans += 1
print(ans)

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

const int maxn = 1e5+15;
int n, m, x, y, res;
vector<int> adj[maxn];
bool visited[maxn];

void dfs(int node) {
    visited[node] = true;
    for (int u: adj[node]) {
        if (!visited[u])
            dfs(u);
    }
}
int count() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            cnt++;
            dfs(i);
        }
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    res = count();
    cout << res-1;
}

Measured memory_bytes: 9704
n = int(input())
A= [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]

A.sort()
B.sort()
C.sort(reverse=True)

ans = 0
ai = 0
ci = n-1

for b in B:
  while ai <n and  A[ai] <b:
    ai +=1
  while ci >=0 and C[ci] <=b:
    ci -= 1
  ans += ai *(ci +1)
print(ans)

Measured memory_bytes: 23644
import math
n, m = map(int, input().split())

if abs(n - m) > 1:
    print(0)
elif n == m:
    print(math.factorial(n) ** 2 * 2 % (pow(10, 9)+7))
else:
    print(math.factorial(n) * math.factorial(m) % (pow(10, 9)+7))

Measured memory_bytes: 54640
import sys
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

a,b,n = Mi()
if b-1 < n:
  print((a*(b-1))//b)
else:
  print((a*n)//b)

Measured memory_bytes: 9140
# スペース区切りの整数の入力
a, b= map(int, input().split())
string = input()

flag = 1

for i in range(a):
    if string[i] == '-':
        flag = 0

if string[a] != '-':
    flag = 0

for i in range(a+1,a+b+1):
    if string[i] == '-':
        flag = 0

if flag == 1:
    print("Yes")

else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>

using std::cin;
using std::cout;
using std::endl;

using std::vector;

using std::string;

bool ismine(vector<string> ss, int w, int h, int i, int j){
    if(!(0 <= i && i < h)){
        return false;
    }
    if(!(0 <= j && j < w)){
        return false;
    }
    return ss[i][j] == '#';
}

int main(void){
    int h, w;
    cin >> h >> w;
    vector<string> ss(h);

    for(int i = 0; i < h; i++){
        string s;
        cin >> s;
        ss[i] = s;
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(ss[i][j] != '.'){
                continue;
            }
            int cnt = 0;
            cnt += ismine(ss, w, h, i+1, j+1);
            cnt += ismine(ss, w, h, i+1, j  );
            cnt += ismine(ss, w, h, i+1, j-1);
            cnt += ismine(ss, w, h, i  , j+1);
            cnt += ismine(ss, w, h, i  , j-1);
            cnt += ismine(ss, w, h, i-1, j+1);
            cnt += ismine(ss, w, h, i-1, j  );
            cnt += ismine(ss, w, h, i-1, j-1);
            ss[i][j] = cnt + '0';
        }
    }
    for(int i = 0; i < h; i++){
        cout << ss[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
H, W = map(int, input().split())
a = [input().split() for l in range(H)]
ansK=[]

ans = int(0)
count = int(0)

for i in range(W):
    for j in range(H):
        if j!=H-1:
            if i!=W-1:
                if int(a[j][i])%2==1:
                    a[j][i+1] = int(a[j][i+1])+1
                    a[j][i]   = int(a[j][i])  -1
                    ansK.append([j+1,i+1,j+1,i+2])
                    count += 1
            elif i ==W-1:
                if int(a[j][i])%2==1:
                    a[j+1][i] = int(a[j+1][i])+1
                    a[j][i]   = int(a[j][i])-1
                    ansK.append([j+1,i+1,j+2,i+1])
                    count += 1
        else:
            if i != W - 1:
                if int(a[j][i])%2==1:
                    a[j][i+1] = int(a[j][i+1])+1
                    a[j][i]   = int(a[j][i])-1
                    ansK.append([j+1,i+1,j+1,i+2])
                    count += 1

ans = count
print(ans)
[print(' '.join(map(str, i))) for i in ansK]




Measured memory_bytes: 30836
def p_c():
    nb, mb = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = 1
    fb = [1, 1]
    current = 0
    for _ in range(mb):
        a = int(input())
        width = a - current - 1
        if width == -1:
            ans = 0
            break
        while width > len(fb) - 1:
            fb.append(fb[-1] + fb[-2])
        ans *= fb[width]
        current = a + 1
        ans %= mod
    width = nb - current
    while width > len(fb) - 1:
        fb.append(fb[-1] + fb[-2])
    ans *= fb[width]
    ans %= mod
    print(ans)
    
p_c()

Measured memory_bytes: 472076
# coding=utf-8

line = input().split(" ")
H = int(line[0])
W = int(line[1])

s = []
cnt_w = 0
for _ in range(H):
    line = list(input())
    for x in line:
        if x==".":
            cnt_w += 1
    s.append(line)

INF = 100000

diff = [
    [0,1]
    ,[0,-1]
    ,[1,0]
    ,[-1,0]
]

def dfs():
    q = []
    m = []
    for i in range(H):
        m.append([INF for _ in range(W)])
    q.append((0,0))
    m[0][0] = 1

    while len(q)>0:
        p = q.pop(0)
        if H-1==p[0] and W-1==p[1]:
            break

        for d in diff:
            ni = p[0]+d[0]
            nj = p[1]+d[1]
            if 0<=ni<H and 0<=nj<W:
                if s[ni][nj]=="." and m[ni][nj]==INF:
                    q.append((ni,nj))
                    m[ni][nj] = m[p[0]][p[1]]+1

    return m[H-1][W-1]

r = dfs()

if r == INF:
    print("-1")
else:
    print(cnt_w - r)


Measured memory_bytes: 3188
// Problem : A - ∴ (Therefore)
// Contest : AtCoder - AtCoder Beginner Contest 168
// URL : https://atcoder.jp/contests/abc168/tasks/abc168_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

#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 RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 1e6 + 5;
const ll MOD = 1e9 + 7;

// sprawdz MODULO!
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	n %= 10;
	if (n == 3) cout << "bon";
	else if (n == 0 || n == 1 || n == 6 || n == 8) cout << "pon";
	else cout << "hon";
	return 0;
}
 


Measured memory_bytes: 3636
#coding: UTF-8
N = int(input())
S = input()

x = 0
X = 0
for i in range(1,N+1):
    if S[i-1] == 'I':
        x+=1
    elif S[i-1] == 'D':
        x-=1
    if x >= X:
        X = x
print(X)

Measured memory_bytes: 3192
h, w = gets.split.map(&:to_i)
ch, cw = gets.split.map(&:to_i)
dh, dw = gets.split.map(&:to_i)

c = [?., ?#]
s = Array.new(h+3) {Array.new(w+3, c[1])}
h.times {|i| s[i+1][1,w+1] = gets.chars}

move = [[1,0], [-1,0], [0,1], [0,-1]]
warp = (-2..2).to_a.product((-2..2).to_a) - move - [[0,0]]

init = 1 << 20
d = Array.new(h+3) {Array.new(w+3, init)}
d[ch][cw] = 0
t = [[ch, cw]]

(0..).each do |k|
    break if t.empty? || d[dh][dw] < init
    u = []

    while (x,y = t.pop)
        move.each do |i,j|
            xx = x + i
            yy = y + j
            if s[xx][yy] == c[0] && d[xx][yy] > k
                d[xx][yy] = k
                t << [xx, yy]
            end
        end

        warp.each do |i,j|
            xx = x + i
            yy = y + j
            if s[xx][yy] == c[0] && d[xx][yy] > k + 1
                d[xx][yy] = k + 1
                u << [xx, yy]
            end
        end
    end

    t = u
end

p d[dh][dw] == init ? -1 : d[dh][dw]


Measured memory_bytes: 110620
// SeeAlso: https://atcoder.jp/contests/abc052/tasks/abc052_a

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

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

    ll ans = max((a*b), (c*d));
    print(ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

// coding: 13:50
// test:
//  s: abxybc
//  t: axxxyb
//
//  i: s index, j = t index
//  dp(i, j) = max(dp(i + 1, j + 1) + rew(i, j), dp(i + 1, j), dp(i, j + 1));
//  rew(i, j) = if (si == tj) 1 else 0

using namespace std;

const int NMAX = 3e3 + 11;

string s, t;
int    mem[NMAX][NMAX];

string reconstruct(int i, int j)
{
    if (i == 0 or j == 0)
        return "";
    if (s[i - 1] == t[j - 1])
        return reconstruct(i - 1, j - 1) + s[i - 1];
    else
    {
        if (mem[i - 1][j] > mem[i][j - 1])
            return reconstruct(i - 1, j);
        else
            return reconstruct(i, j - 1);
    }
}

string solve(void)
{
    int n = s.size();
    int m = t.size();

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (s[i - 1] == t[j - 1])
                mem[i][j] = mem[i - 1][j - 1] + 1;
            else
                mem[i][j] = max(mem[i - 1][j], mem[i][j - 1]);
        }
    }

    return reconstruct(n, m);
}

int main(void)
{
    cin >> s >> t;

    cout << solve() << endl;
    return 0;
}


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


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

	if (A.size() != B.size()) {//桁数が異なる場合
		if (A.size() > B.size()) {
			cout << "GREATER" << endl;
		}
		else {
			cout << "LESS" << endl;
		}
	}
	else {//桁数が等しい場合

		if (A == B) {
			cout << "EQUAL" << endl;
		}
		else {

			for (unsigned int i = 0; i < A.size(); ++i) {
				if (A[i] != B[i]) {
					if (A[i] > B[i]) {
						cout << "GREATER" << endl;
						break;
					}
					else {
						cout << "LESS" << endl;
						break;
					}
				}

			}

		}



	}





	return 0;

}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <set>

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define inc( i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec( i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

typedef long long   signed int LL;
typedef long long unsigned int LU;

template<typename T> void swap(T &x, T &y) { T t = x; x = y; y = t; return; }
template<typename T> T abs(T x) { return (0 <= x ? x : -x); }
template<typename T> T max(T a, T b) { return (b <= a ? a : b); }
template<typename T> T min(T a, T b) { return (a <= b ? a : b); }
template<typename T> bool setmin(T &a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T &a, T b) { if(b <= a) { return false; } else { a = b; return true; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, e, t, x[100002];
LL dp[100001];
int m[100001];
const LL MAX = 1000000000000000LL;

std::multiset<LL> ms;

LL mi1_v = MAX;
LL mi1(int i) {
	incID(j, m[i - 1], m[i]) { setmin(mi1_v, dp[j] - 2 * x[j + 1]); }
	return mi1_v;
}

LL mi2(int i) {
	incID(j, m[i - 1], m[i]) {
		auto it1 = ms.find(dp[j]);
		auto it2 = it1;
		it2++;
		ms.erase(it1, it2);
	}
	ms.insert(dp[i - 1]);
	return *ms.begin();
	
	/*
	ms.clear();
	incID(j, m[i], i) { ms.insert(dp[j]); }
	return *(ms.begin());
	*/
}

int main() {
	scanf("%lld%lld%lld", &n, &e, &t);
	inc1(i, n) { scanf("%lld", &x[i]); }
	
	int mm = 0;
	inc1(i, n) {
		while( (x[i] - x[mm + 1]) * 2 > t) { mm++; }
		m[i] = mm;
	}
	
	inc1(i, n) {
		dp[i] = min(mi1(i) + 2 * x[i], mi2(i) + t);
	}
	
	printf("%lld\n", dp[n] + e);
	
	return 0;
}


Measured memory_bytes: 4096
#include<iostream>
using namespace std;
int main(){
  int  a,b,c,d,x;
  cin>>x;
  a=x/1000;
  b=(x%1000)/100;
  c=(x%100)/10;
  d=(x%10);
  if(a==b||b==c||c==d){
    cout<<"Bad"<<endl;
  }
  else{
    cout<<"Good"<<endl;
  }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atc_0024
{
    class Program
    {
        static void Main(string[] args)
        {
            var rStr = Console.ReadLine();

            long N = long.Parse(rStr.Split(' ')[0]);
            long A = long.Parse(rStr.Split(' ')[1]);
            long B = long.Parse(rStr.Split(' ')[2]);

            if (A == 0)
            {
                Console.WriteLine(0);
                return;
            }

            long result = 0;

            if (N % (A + B) != 0)
            {
                if (N % (A + B) >= A)
                {
                    result = (N / (A + B)) * A + A;
                }
                else
                {
                    result = (N / (A + B)) * A + N % (A + B);
                }
            }
            else
            {
                result = (N / (A + B)) * A;
            }

            Console.WriteLine(result);

        }
    }
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	for (auto &u : v) os << u << el;
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

int main() {
	int N; cin >> N;
	vector<vint> g(N), rg(N);
	vint p(N);
	vint grundy(N, 0);
	bitset<200005> notloop;
	vint in(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> p[i]; --p[i];
		g[p[i]].push_back(i);
		rg[i].push_back(p[i]);
		in[p[i]]++;
	}

	queue<int> que;
	for (int i = 0; i < N; i++) if (in[i] == 0) que.push(i);
	while (!que.empty()) {
		int u = que.front(); que.pop();
		notloop[u] = true;
		set<int> st;
		for (auto &to : g[u]) st.insert(grundy[to]);
		while (st.count(grundy[u])) grundy[u]++;
		for (auto &r : rg[u]) if (--in[r] == 0) que.push(r);
	}
	
	int s;
	for (int i = 0; i < N; i++) if (!notloop[i]) { s = i; break; }

	vector<int> tr;
	{
		set<int> st;
		for (auto &to : g[s]) if (notloop[to]) st.insert(grundy[to]);
		while (st.count(grundy[s])) grundy[s]++;
		tr.push_back(grundy[s]);
		grundy[s]++;
		while (st.count(grundy[s])) grundy[s]++;
		tr.push_back(grundy[s]);
	}

	for (auto &x : tr) {
		//cout << x << endl;
		bitset<200005> used = notloop;
		vint gr = grundy, in2 = in;
		gr[s] = x;

		used[s] = true;
		int u = s;
		for (auto &r : rg[s]) if (!used[r] && --in2[r] == 0) { u = r; break; }
		while (!used[u]) {
			used[u] = true;
			set<int> st;
			for (auto &to : g[u]) if (used[to]) st.insert(gr[to]);
			while (st.count(gr[u])) gr[u]++;
			//cout << u << " " << gr[u] << endl;
			for (auto &r : rg[u]) if (!used[r] && --in2[r] == 0) { u = r; break; }
		}
		set<int> st;
		int v = 0;
		for (auto &to : g[s]) st.insert(gr[to]);
		while (st.count(v)) v++;
		if (v == gr[s]) {
			cout << "POSSIBLE" << endl;
			return (0);
		}
	}
	cout << "IMPOSSIBLE" << endl;
	return (0);
}


Measured memory_bytes: 24832
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    s = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def dfs(cy, cx, tmp):
        tmp.append((cy, cx))
        visited[cy][cx] = True
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == '#' and not visited[ny][nx]:
                dfs(ny, nx, tmp)

    # 大きさ1の#の島があったらダメ
    is_ok = True
    visited = [[False] * W for _ in range(H)]
    for i, j in itertools.product(range(H), range(W)):
        if s[i][j] == '#' and not visited[i][j]:
            tmp = []
            dfs(i, j, tmp)
            if len(tmp) == 1:
                is_ok = False
                break

    if is_ok:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 12524
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
sum=0
for i in range(n):
  sum+=b[a[i]-1]
  if i!=0 and a[i]==a[i-1]+1:
    sum+=c[a[i-1]-1]
print(sum)

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string>
#include <map>
#include <set>

using namespace std;

int main() {
	long long mod = 1000000007ll;
	int N; scanf("%d", &N);
	long long ans = 1ll; int cnt = 0;
	for (int i = 0; i < N; ++i) {
		int x; scanf("%d", &x);
			while ((i - cnt) * 2 + 1 > x) {
				ans *= (long long) (i - cnt + 1);
				ans %= mod;
				cnt++;
			}
	}
	while (cnt < N) {
		ans *= (long long) (N - cnt);
		ans %= mod;
		cnt++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int main(){
  int n;
  int x[109];
  cin>>n;
  rep(i,n){
    cin>>x[i];
  }
  int ans=INF;
  for(int i=0;i<=101;i++){
    int sum=0;
    rep(j,n){
      sum+=(x[j]-i)*(x[j]-i);
    }
    ans=min(ans,sum);
  }
  cout<<ans<<endl;
  return(0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    string s, t;
    cin >> s >> t;
    vector<vector<int>> v(26);
    int n = s.size();
    int m = t.size();
    rep(i, 0, n) v[s[i] - 'a'].push_back(i);
    ll ans = 0;
    int p = 0;
    rep(i, 0, m) {
        int c = t[i] - 'a';
        if (lower_bound(all(v[c]), p) - v[c].begin() < (int)v[c].size()) {
            p = *lower_bound(all(v[c]), p) + 1;
        } else {
            p = 0;
            if (lower_bound(all(v[c]), p) - v[c].begin() == (int)v[c].size()) {
                cout << -1 << endl;
                return 0;
            } else {
                p = *lower_bound(all(v[c]), p) + 1;
                ans += n;
            }
        }
    }
    ans += p;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1216
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}
 

int main(){
	int N;
  	cin >> N;
  	int num = (N+1000-1)/1000;//切り上げ (a+b-1)/b
  	int ans = (num*1000) - N;
  	cout << ans << endl;

}


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

from pprint import pprint
import sys
sys.setrecursionlimit(10 ** 6)

n_towns, k_times = map(int, input().split())
teleport = list(map(int, input().split()))

seq = []
flags = [False] * n_towns
visited = [0] * n_towns

flags[0] = True
seq.append(0)
visited[0] += 1

town_prev = 0

while True:
    town_next = teleport[town_prev] - 1
    visited[town_next] += 1
    if flags[town_next]:
        seq.append(town_next)
        break
    seq.append(town_next)
    flags[town_next] = True
    town_prev = town_next

loop_len = 0
for town, count in enumerate(visited):
    if count == 2:
        loop_idx = seq.index(town)
# print(loop_idx)

# print(f'seq: {seq}')

if k_times < loop_idx:
    print(seq[k_times] + 1)
else:
    arr = seq[loop_idx:len(seq) - 1]
    r = (k_times - loop_idx) % len(arr)
    print(arr[r] + 1)


Measured memory_bytes: 104972
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
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;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

class UnionFind {
  private:
    vector<int> parent;
    vector<int> height;
    vector<int> m_size;

  public:
    UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
        for(int i = 0; i < size_; ++i)
            parent[i] = i;
    }
    void init(int size_) {
        parent.resize(size_);
        height.resize(size_, 0);
        m_size.resize(size_, 0);
        for(int i = 0; i < size_; ++i)
            parent[i] = i;
    }
    int find(int x) {
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y)
            return;
        int t = size(x) + size(y);
        m_size[x] = m_size[y] = t;
        if(height[x] < height[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(height[x] == height[y])
            ++height[x];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) {
        if(parent[x] == x)
            return m_size[x];
        return size(parent[x] = find(parent[x]));
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> u(N - 1);
    vector<int> v(N - 1);
    vector<long long> w(N - 1);
    REP(i, N - 1) { cin >> u[i] >> v[i] >> w[i]; }
    UnionFind tree(2 * N);
    // REP(i, N) { cout << tree.find(i); }
    vector<vector<int>> even(N);
    REP(i, N - 1) {
        if(w[i] % 2 == 0) {
            tree.unite(u[i] - 1, v[i] - 1);
            tree.unite(u[i] + N - 1, v[i] + N - 1);
        } else {
            tree.unite(u[i] - 1, v[i] + N - 1);
            tree.unite(u[i] + N - 1, v[i] - 1);
        }
    }

    cout << "0" << endl;
    for(int i = 1; i < N; i++) {
        if(tree.same(0, i)) {
            cout << "0" << endl;
        } else {
            cout << "1" << endl;
        }
    }
}

Measured memory_bytes: 6656
while True:
    n, x = map(int, input().split())

    ans=0
    if n == 0 and x == 0:
        break
    for n1 in range(1,n-1):
        for n2 in range(n1+1,n):
            n3=x-n1-n2
            if n2<n3<=n:
                ans+=1
    print(ans)


Measured memory_bytes: 5592
#include<bits/stdc++.h>
using namespace std;
inline int cnt(int x){
	int res=0;
	while(x){
		if(x&1)res++;
		x>>=1;
	}
	return res;
}
int n;
int a[300100];
int x[50][50],y[50][50];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for(int j=1;j<=a[i];j++){
			scanf("%d%d",&x[i][j],&y[i][j]);
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		int flag=1;
		for(int j=1;j<=n;j++){
			if(!(i & (1<<(j-1))))continue;
			for(int k=1;k<=a[j];k++){
				if(((i>>(x[j][k]-1)) & 1)^y[j][k])flag=0;
			}
		}
		if(flag)ans=max(ans,cnt(i));
	}
	cout<<ans;
	return 0;
} 

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

int main() {
    int n, dd;
    cin >> n;
    map<int, int> d;
    for (int i = 0; i < n; i++) {
        cin >> dd;
        d[dd]++;
    }
    int m, t;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> t;
        if (d[t] > 0) d[t]--;
        else {
            cout << "NO" << endl;
            return 0;
        } 
    }
    cout << "YES" << endl;
}

Measured memory_bytes: 12892
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long

int main(void){
	ll n;
	cin >> n;
	for(int i = 1; i < 4000; ++i){
		for(int j = 1; j < 4000; ++j){
			if((ll)4 * i * j - n * (i + j)==0)continue;
			if((ll)(n * i * j) % (4 * i * j - n * (i + j) ) % (n * i * j) == 0 && (ll)((n * i * j) / (4 * i * j - n * (i + j)) > 0)){
				cout << i << " "<< j << " " << (ll)(n * i * j) / (4 * i * j - n * (i + j) )<< endl;
				return 0;
			}
		}
	}
	return 0;
}


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

int main() {

    int N;
    cin >> N;

    vector<int> vec(N);
    for(int i = 0; i<N; i++) cin >> vec.at(i);

    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());

    int A=0, B=0;

    for(int i=0; i<N; i++){
        if(i%2!=0) B+=vec.at(i);
        else A+=vec.at(i);
    }
    cout << A-B << endl;
}


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

/*
  ch は小さいほうが良い
 */

struct Trie {
    struct Node {
        int val;
        Node * ch[26];
        Node() : val(0) {
            fill(ch, ch+26, nullptr);
        }
        ~Node(){
            for(auto & p : ch) if(p != nullptr) delete p;
        }
    };
    Node *r;

    void insert(string const &s){
        auto p = s.begin();
        auto cur = r;
        while(1){
            if(p == s.end()){
                cur->val++;
                break;
            } else {
                auto &nxt = cur->ch[(int)*p-'A'];
                if(nxt == nullptr) nxt = new Node();
                cur = nxt;
                ++p;
            }
        }
    }
    bool erase(string const &s){
        auto p = s.begin();
        auto cur = r;
        while(1){
            if(p == s.end()) return cur->val > 0 ? cur->val--, true : false;
            auto &nxt = cur->ch[(int)*p-'A'];
            if(nxt == nullptr) return false;
            cur = nxt;
            ++p;
        }
    }
    bool find(string const& s){
        auto p = s.begin();
        auto cur = r;
        while(1){
            if(p == s.end()) return cur->val > 0;
            auto &nxt = cur->ch[(int)*p-'A'];
            if(nxt == nullptr) return false;
            cur = nxt;
            ++p;
        }
    }
    Trie() : r(new Node()) {}
    ~Trie() { delete r; }
};

int main(){
    int n;
    cin >> n;
    Trie t;
    rep(i,n){
        char com[15], str[15];
        cin >> com >> str;
        if(com[0] == 'i'){
            t.insert(str);
        } else {
            puts(t.find(str) ? "yes" : "no");
        }
    }
}

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

using namespace std;

int n;
int h[100001];

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        scanf("%d",&h[i]);
    h[0] = 0;
    for(int i = 1;i <= n;i++)
    {
        if(h[i] > h[i - 1])
            h[i]--;
    }
    for(int i = 1;i <= n;i++)
        if(h[i] < h[i - 1])
        {
            printf("No\n");
            return 0;
        }
    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 640
using System;
using static System.Console;
using static System.Math;

public class Hello{
    public static void Main(){
        string[] input = ReadLine().Split(' ');
        long a = long.Parse(input[0]);
        long b = long.Parse(input[1]);
        long x = long.Parse(input[2]);
        
        long ans = 0;
        ans += b/x;
        if(a>x){
        if(a%x == 0){
            ans -= (a/x)-1;
        }else{
            ans -= a/x;
        }
        }
        if(a==0){
            ans++;
        }
        WriteLine(ans);
    }
}

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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define rep(i, x, y) for(decltype(y) i = (x) - ((x) > (y)); i != (y) - ((x) > (y)); i += 1 - 2 * ((x) > (y)))
#define trav(i,a) for(auto& (i) : (a))
#define all(a) (a).begin(),(a).end()
#define sz(a) int((a).size())
#define clr(a,x) memset((a),(x),sizeof(a)) // array (0,-1)
#define dbg(x) cerr << "STDERR => " << __LINE__ << ": " << #x << " = " << (x) << "  :(\n";
#define eb emplace_back
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void cpuTime() { cerr << "cpu time : " << double(clock())/CLOCKS_PER_SEC << "\n"; return; }
using ll = long long;
using ull = unsigned long long;
using F = float;
using D = double;
using vi = vector<int>;
using pii = pair<int,int>;



void solve(){

    int n;
    cin >> n;
    vi a(n);
    rep(i,0,n) cin >> a[i];

    int ans = a[0];
    rep(i,1,n) ans ^= a[i];

    if(ans) cout << "No\n";
    else cout << "Yes\n";


    return;
}

/*
 read the question carefully ( what're the exact constraints? )
 look out for SPECIAL CASES (n=1?) and OVERFLOW (ll vs int?) ARRAY OUT OF BOUNDS
 Check datatypes
*/
int main(){

    fast_io;
    int t=1;
    // cin >> t;

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

    cpuTime();
return 0;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
static const double pi = 3.141592653589793;



int main(){
    ll N;
    cin>>N;
    vector<ll> A(N);
    rep(i, N){
        cin>>A[i];
    }
    sort(ALL(A));
    ll X=A[N-1];
    ll Y=-1;
    if(X%2){
        rep(i, N){
            ll S=min(abs(X/2-Y), abs(X/2+1-Y));
            ll T=min(abs(X/2-A[i]), abs(X/2+1-A[i]));
            if(S>T){
                Y=A[i];
            }
        }
    }
  	else{
      	rep(i, N){
            ll S=abs(X/2-Y);
            ll T=abs(X/2-A[i]);
            if(S>T){
                Y=A[i];
            }
        }
    }
    cout<<X<<" "<<Y<<endl;
}

Measured memory_bytes: 1024
N = int(input())
li = list(map(int,input().split()))
li2 = list(map(int,input().split()))
sum = 0
max = 0
for k in range(N):
    for m in range(N-k):
        sum += li[m]
    for l in range(N-1-k,N):
        sum+=li2[l]
    if (max<=sum):
        max = sum
    sum = 0
print(max)

Measured memory_bytes: 3064