akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

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

    static class AACOrWA {
        public void solve(int testNumber, InputReader s, PrintWriter w) {
            if (s.nextInt() == s.nextInt())
                w.println("Yes");
            else
                w.println("No");
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21844
from collections import Counter
#l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
#c = Counter(l)
#print(c)   # Counter({'a': 4, 'c': 2, 'b': 1})

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

C = Counter(a)

ans = 0
for k, v in C.items():
    k = int(k)
    
    if k<v:
        ans += (v-k)
    elif k>v:
        ans += v

print(ans)

Measured memory_bytes: 18676
S = input()
Q = int(input())

hanten = 0
saki = ""
ato = ""

for i in range(Q):
    q = input().split()
    
    if q[0] == "1":
        hanten += 1
    else:
        if hanten % 2 == 0:
            if q[1] == "1":
                saki += q[2]
            else:
                ato += q[2]
        else:
            if q[1] == "1":
                ato += q[2]
            else:
                saki += q[2]

if hanten % 2 == 0:
    for i in range(len(saki)):
        print(saki[-i-1], end="")
    print(S, end="")
    print(ato)
else:
    for i in range(len(ato)):
        print(ato[-i-1], end="")
    for i in range(len(S)):
        print(S[-i-1], end="")
    print(saki)


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;


void solve()
{
	int n, k, h;
	cin >> n >> k;
	int ans = 0;
	for(int i = 0; i < n; ++i)
	{
		cin >> h;
		if (h >= k)
		{
			ans++;
		}
	}
	cout << ans;
}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    long n,m,a,b;
    int i,count=0;
    cin>>n;
    m=sqrt(n);
    for(i=1; i<=m; ++i)
    {
        if(n%i==0)
        {
            a=n/i;
            b=a>=i?a:i;
        }
    }
    do
    {
        count++;
        b /= 10 ;
    }
    while( b>0 );
    cout<<count;
    return 0;
}


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

int main() {
  long long x,k,d;
  cin >> x >> k >> d;
  x = abs(x);
  long long a;
  a = x / d;
  if(k <= a){
    x = x - k * d;
    cout << x;
    return 0;
  }
  x -= a * d;
  k = k - a;
  if(k % 2 ==0) cout << abs(x);
  else cout << abs(x-d);
  

}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    string s, t; cin >> s >> t;
    vector<string> f;

    //t[0]が入る位置を全探索
    for(int i=0; i<s.size()-t.size()+1; i++){
        if(s[i] == '?' || s[i] == t[0]){
            bool flg = true;
            for(int j=0; j<t.size(); j++){
                if(s[i+j] != t[j] && s[i+j] != '?') flg = false;
            }
            if(flg){
                //iからstring tを入れて、他の?はaにして出力
                string ans = "";
                for(int j=0; j<s.size(); j++){
                    if(j < i || i+t.size() <= j) ans += ((s[j] == '?')? 'a' : s[j]);
                    else ans += t[j-i];
                }
                f.push_back(ans);
            }
        }
    }


    if(f.size() == 0) cout << "UNRESTORABLE" << endl;
    else{
        sort(f.begin(), f.end());
        cout << f[0] << endl;
    }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = [[0]*(N+1) for _ in range(N+1)]

for wa in range(1, N+1):
    # AA[:wa]までを考える
    for x in range(wa+1):
        y = wa - x
        a, i = AA[wa-1]
        if x - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x-1][y]+a*(i-x))
        if y - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x][y-1]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

M = -INF
for x in range(N):
    y = N-x
    M = max(DP[x][y], M)
print(M)



Measured memory_bytes: 100144
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, M = map(int, input().split())
edge = []
bridge = 0
for _ in range(M):
  e = list(map(lambda x: int(x)-1, input().split()))
  edge.append(e)

for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if j == i:
      continue
    uf.unite(edge[j][0], edge[j][1])
  if uf.find_root(edge[i][0]) != uf.find_root(edge[i][1]):
    bridge += 1

print(bridge)

Measured memory_bytes: 9092
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <sstream> 
#include <cctype>
#include <stack>
#include <queue>
#include <cstring>
#include <map>
#include <list>
#include <cassert>
 
using namespace std; 

int main(){

	int n;
	cin>>n;

	long long x=0,res=0;

	vector<long long> a(n),a2(n);
	for(int i=0;i<n;i++){
		cin>>a[i];

		long long b=(a[i]-1)/(x+1);
		if(b!=0){

			a[i]=1;
			res+=b;

		}
		x=max(x,a[i]);
	}

/*
	for(int i=0;i<n;i++) cout<<a[i]<<" ";
	cout<<endl;
	for(int i=0;i<n;i++) cout<<a2[i]<<" ";
	cout<<endl;
*/
	cout<<res<<endl;



}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
#define mx 111000
#define ll long long int
int main()
{
    //ll a;
    char c;
    cin >> c;
    if(c>=65 && c<=90)
        cout << "A" << endl;
    else if(c>=97 && c<=122)
        cout << "a" << endl;
    //cout <<  << endl;
    return 0;
}


Measured memory_bytes: 3596
#include<iostream>
#include <algorithm>
using namespace std;
int main(){
    int a;
    string b;
    cin>>a;
    string name[a];
    int num[a];
    for(int i=0;i<a;i++){
        cin>>b;
        name[i]=b;
        num[i]=1;
    }
    sort(name,name+a);
    int max=1;
    for(int i=0;i<a-1;i++){
        if(name[i]==name[i+1]){
            num[i+1] = num[i+1]+num[i];
            if(num[i+1]>max){
                max = num[i+1];
            }
        }
    }
    for(int i=0;i<a;i++){
        if(num[i]==max){
            cout<<name[i]<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 15104
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
//printf("%.10f\n", n);
struct edge { ll to, cost; };
typedef pair<ll, ll>P; //firstは最短距離、secondは頂点番号
ll d[213456];//始点sから終点tまでのコストd[t]
vector<edge> GG[213456];//コスト
void dijkstra(ll s) {
	//greater<P>を指定→firstが小さい順
	priority_queue<P, vector<P>, greater<P> >qu;
	fill(d, d + 213456, INF);//←TLE気を付ける
	d[s] = 0; qu.push(P(0, s));
	while (!qu.empty()) {
		P p = qu.top(); qu.pop();
		int v = p.second;
		if (d[v] < p.first) { continue; }
		for (int i = 0; i < GG[v].size(); i++) {
			edge e = GG[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				qu.push(P(d[e.to], e.to));
			}
		}
	}
}
ll zombi[12345678], c[12345678], a[12345678], b[12345678];
ll kiken[12345678];
signed main() {
    ll n, m, k, s, p, q; cin >> n >> m >> k >> s;
    cin >> p >> q;
    for (int h = 0; h < k; h++) {
        cin >> c[h]; zombi[c[h]] = 1;
    }
    vector<vector<ll> > G(123456);
    for (int h = 0; h < m; h++) {
        cin >> a[h] >> b[h];
        G[a[h]].push_back(b[h]);
        G[b[h]].push_back(a[h]);
    }
    queue<ll> que, cnt;
    for (int i = 0; i < k; i++) {
        kiken[c[i]] = 1;
        if (s == 0) { continue; }
        for (int j = 0; j < G[c[i]].size(); j++) {
            if (kiken[G[c[i]][j]] == 0) {
                que.push(G[c[i]][j]); cnt.push(1); kiken[G[c[i]][j]] = 1;
            }
        }
    }
    while (que.size()) {
        if (cnt.front() >= s) { que.pop(); cnt.pop(); continue; }
        for (int i = 0; i < G[que.front()].size(); i++) {
            if (kiken[G[que.front()][i]] == 0) {
                que.push(G[que.front()][i]); kiken[G[que.front()][i]] = 1;
                cnt.push(cnt.front() + 1);
            }
        }
        que.pop(); cnt.pop();
    }
    for (int h = 0; h < m; h++) {
        if (zombi[b[h]] == 0) {
            if (b[h] == n) { GG[a[h]].push_back({ b[h], 0 }); }
            else if (kiken[b[h]] == 1) { GG[a[h]].push_back({ b[h], q }); }
            else { GG[a[h]].push_back({ b[h], p }); }
        }
        if (zombi[a[h]] == 0) {
            if (a[h] == n) { GG[b[h]].push_back({ a[h], 0 }); }
            else if (kiken[a[h]] == 1) { GG[b[h]].push_back({ a[h], q }); }
            else { GG[b[h]].push_back({ a[h], p }); }
        }
    }
    dijkstra(1);
    cout << d[n] << endl;
    return 0;
}



Measured memory_bytes: 34028
//             بسم الثالوث الاقدس
#include<iostream>	
#include<algorithm>
#include<cstdio>
#include<sstream>
#include<cmath>
#include<climits>
#include<string>
#include<iomanip>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
#include<fstream>
using namespace std;
//********************************************************************************************
//******************************************************************************************** 
/*
jesus help me.......
*/
typedef long long lld;
typedef char c;



/*
jesus help me.......
jesus help me.......
jesus help me.......
*/



int binarySearch(int arr[], int l, int r, int x)
{
	while (l <= r)
	{
		int m = l + (r - l) / 2;

		if (arr[m] == x)
			return m;

		if (arr[m] < x)
			l = m + 1;

		else
			r = m - 1;
	}

	return -1;

}





bool sortbysec(const pair<string, int> &a, const pair<string, int> &b)
{
	
	return (a.second > b.second);
}







int main()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);


	//freopen("keys.in", "r", stdin);

	int n;
	cin >> n;
	int x = 0, y = 0;
	int tt=0;
	bool bb = true;
	for (int i = 0; i < n; i++)
	{
		int t, a, b;
		cin >> t >> a >> b;
		int xx = abs(a - x) + abs(b - y);
		int z = (t - tt)-xx ;
		if (z % 2 == 1||z<0)
		{
			bb = false;
		}
		x = a; y = b;
		tt = t;
	}
	if (bb)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;


	///system("pause");


	return 0;
}
/*
jesus help me.......
jesus help me.......
jesus help me.......
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int x, y;
  cin >> x >> y;
  if (y % 2 == 0 && y >= 2 * x && y <= 4 * x) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}


Measured memory_bytes: 3632
import sys
import time
import math
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

K = int(input())
A, B = map(int, input().split())
for i in range(A, B+1):
	if i % K == 0:
		print('OK')
		sys.exit()
print('NG')

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)


Measured memory_bytes: 9164
#include<iostream>
#include<string>
#include<cmath>
#include<stack>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
int main()
{
	int n,k,d[10];cin>>n>>k;
	for(int i=0;i<k;i++)cin>>d[i];
	for(int i=n;;i++)
	{
		int f=0;
		for(int j=0;j<k;j++)
		{
			int a=i;
			while(a)
			{
				if(a%10==d[j])f=1;
				a/=10;
			}
		}
		if(f==0)
		{
			cout<<i<<endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
 
int main() {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
   ll x,k,d,a,b,y;
  cin>>x>>k>>d;
  a=x%d;
  b=x/d;
  if(abs(b)>k){
      if(x>=0)
   cout<<abs(x-(d*k));
   else cout<<abs(x+(d*k));
  }
  else if(abs(b)==k) cout<<abs(a);
  else{
   k=k-abs(b);
    if(k%2==0) cout<<abs(a);
    else if(k%2!=0) {
        if(a>=0)
        cout<<abs(a-d);
  else cout<<abs(a+d);
        
    }
  }
  return 0;
}

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

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    vector<vector<int>> cnt(h, vector<int>(w));
    rep(i, h){
        vector<int> done(w);
        rep(j, w){
            if(s[i][j] == '#') continue;
            if(done[j]) continue;
            int l = 0;
            while(j+l < w){
                if (s[i][j+l] == '#') break;
                l++;
            }
            rep(k, l){
                cnt[i][j+k] += l;
                done[j+k] = 1;
            }
        }
    }

    rep(j, w){
        vector<int> done(h);
        rep(i, h){
            if(s[i][j] == '#') continue;
            if(done[i]) continue;
            int l = 0;
            while(i+l < h){
                if (s[i+l][j] == '#') break;
                l++;
            }
            rep(k, l){
                cnt[i+k][j] += l;
                done[i+k] = 1;
            }
        }
    }

    int ans = 0;

    rep(i, h) rep(j, w) ans = max(ans, cnt[i][j]-1);
    cout << ans << endl;

    return 0;
}


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

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

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

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

	int XY;
	int ans = 0;

	for (int i = 0; i < N; i++) {
		XY = V[i] - C[i];

		if (V[i] > C[i]) {
			ans += XY;
		}
		else {
			continue;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
class Dice:
    def __init__(self,t,f,r,l,b,u):
        self.a=[[t,f,r,l,b,u]]
        self.direction={'S':(4,0,2,3,5,1),'N':(1,5,2,3,0,4),'E':(3,1,0,5,4,2),'W':(2,1,5,0,4,3),'U':(5,4,2,3,1,0)}
    def dice_tuple(self):
        self.b=tuple(self.a)
    def roll(self,d,n):
        self.a[n]=[self.a[n][i] for i in self.direction[d]]
    def roll2(self,d,n):
        self.a[n]=[self.b[n][i] for i in self.direction[d]]
    def roll_w(self, n):
        self.a[n] = [self.a[n][i] for i in (0, 3, 1, 4, 2, 5)]
n=int(input())
for i in range(n):
    if i==0:
        t, f, r, l, b, u = map(int, input().split())
        dice = Dice(t, f, r, l, b, u)
    else:
        a = list(map(int, input().split()))
        dice.a.append(a)
dice.dice_tuple()
s='SNEWUU'
try:
    for u in range(n - 1):
        for t in range(u + 1, n):
            for j in s:
                for r in range(4):
                    if dice.a[t] == dice.a[u]:
                        raise Exception
                    dice.roll_w(t)
                dice.roll2(j, t)
    else:
        print('Yes')
except:
    print('No')


Measured memory_bytes: 5612
use proconio::{fastout, input};
#[allow(unused_mut)]
#[fastout]
fn main() {
    input! {
        n: usize
    }
    let mut n = n;
    let mut res = vec![];
    while n != 0 {
        n -= 1;
        res.push(('a' as u8 + (n % 26) as u8) as char);
        n /= 26;
    }
    res.reverse();
    let res: String = res.iter().collect();
    println!("{}", res);
}


Measured memory_bytes: 2168
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2010;
char mp[N][N];
int c[5][N][N]={0};
int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        scanf("%s",mp[i]+1);
    }

    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
    {
        if(mp[i][j]=='#')continue;
        c[1][i][j]=c[1][i][j-1]+1;
    }

    for(int i=1;i<=h;i++)
        for(int j=w;j>=1;j--)
    {
        if(mp[i][j]=='#')continue;
        c[2][i][j]=c[2][i][j+1]+1;
    }

    for(int j=1;j<=w;j++)
        for(int i=1;i<=h;i++)
    {
        if(mp[i][j]=='#')continue;
        c[3][i][j]=c[3][i-1][j]+1;
    }

    for(int j=1;j<=w;j++)
        for(int i=h;i>=1;i--)
    {
        if(mp[i][j]=='#')continue;
        c[4][i][j]=c[4][i+1][j]+1;
    }
    int maxx=0;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
    {
        if(mp[i][j]=='.')
        {
            maxx=max(maxx,c[1][i][j]+c[2][i][j]+c[3][i][j]+c[4][i][j]-3);
        }
    }
    printf("%d\n",maxx);
    return 0;
}


Measured memory_bytes: 68736
// <string.cpp> - Sat Mar 25 20:06:07 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=500010;
const int K=20;
const int INF=1e9;
char s[MAXN];
int a[MAXN][27],b[K][MAXN];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=n;i;i--){
        a[i][s[i]-'a']=i+1;
        for(int j=s[i]-'a'+1;j<=26;j++)a[i][j]=a[a[i][j-1]][j-1];
        for(int j=0;j<s[i]-'a';j++)a[i][j]=a[a[i][26]][j];
    }
    for(int i=1;i<=n;i++)b[0][i]=a[i][26];
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)b[j][i]=b[j-1][b[j-1][i]];
    int q=gi();
    while(q--){
        int l=gi(),r=gi()+1;
        for(int i=K-1;i>=0;i--)
            if(b[i][l]&&b[i][l]<=r)l=b[i][l];
        puts(l==r?"Yes":"No");
    }
    return 0;
}

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

// ??????: http://tubo28.me/algorithm/union-find/
struct UnionFind {
    vector<int> parent;
    int set_num;

    UnionFind(int n) {
        parent.resize(n, -1);
        set_num = n;
    }

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

        if (x != y) {
            if (size(x) < size(y)) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            set_num--;
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    int find(int x) {
        if (parent[x] < 0) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    int size(int x) {
        return -parent[find(x)];
    }

    int size() {
        return set_num;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    UnionFind uf(n);

    for (int i = 0; i < q; i++) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            uf.unite(x, y);
        } else {
            cout << (uf.is_same(x, y) ? 1 : 0) << endl;
        }
    }
    return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define dbg(x) cout<<#x" = "<<(x)<<ln

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

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

/*
 * X = a+b, Y = a^b, a⊇bとして0 <= X, Y <= Nを満たすX, Yの組の数を求める
 * (a+b<=N, a^b<=Nを満たすa,bの組を求めるのとは違う)
 * a⊇bってのはaのiビットをa[i]と表すとするとa[i]>=b[i]が全てのiについて成り立つって意味
 * つまり(aのiビット、bのiビット)の組は(0,0), (1,0), (1,1)の3通りしかない (0,1)はだめ
 * この条件をつけるとX,Yの値からa,bの組を復元できる
 * Yが奇数なら(1,0)のパターンで、Yが偶数ならXも見ればわかる
 * 逆にこの条件がなかったら(0,1)と(1,0)の区別がつかなくなるから重複カウントしてしまう
 * この条件を思いつけばあとは桁dp
 */

ll n;
map<pll, ll> m;

ll f(ll s, ll x) {
	if (m[pll(s, x)]) return m[pll(s, x)];
	// a:even b:even 0-0
	ll res = f(s/2, x/2);
	// a:odd b:even 1-0
	if (s>=1 && x>=1) res += f((s-1)/2, (x-1)/2);
	// a:odd b:odd 1-1
	if (s>=2) res += f((s-2)/2, x/2);
	return m[pll(s, x)] = res % mod;
}

int main() {
	cin >> n;
	m[pll(0, 0)] = 1;
	cout << f(n, n) << ln;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(){
    int N;cin>>N;
    if(N<1000) cout<<"ABC"<<endl;
    else cout<<"ABD"<<endl;
}


Measured memory_bytes: 256
N = int(input())
H = [int(x) for x in input().split()]

MAX = 0
Flag = True
for T in range(0,N):
    if H[T]>MAX:
        MAX = H[T]
    if MAX-H[T]>=2:
        Flag = False
        break
if Flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 20488
c = [[0, 0, 0] for _ in range(3)]

for i in range(3):
    c[i][0], c[i][1], c[i][2] = map(int, input().split(" "))

success = False

for a1 in range(max([max(i) for i in c])+1):
    b1 = c[0][0] - a1
    b2 = c[0][1] - a1
    b3 = c[0][2] - a1

    if (c[1][0] - b1) == (c[1][1] - b2) and (c[1][1] - b2) == (c[1][2] - b3):
        if (c[2][0] - b1) == (c[2][1] - b2) and (c[2][1] - b2) == (c[2][2] - b3):
            success = True
            break

if success:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
// b.cpp : アプリケーションのエントリ ポイントを定義します。
//

#include <iostream>
using namespace std;
using ll = long long;
int main()
{
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	if (abs(a - b) > 1e18) cout << "Unfair";
	else if (k % 2 == 0) cout << (a - b) << endl;
	else cout << (b - a) << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;
typedef vector<char> vech;


int main() {
    ll N;cin>>N;
    vel a(N);rep0(i,N){cin>>a[i];}
    map<ll,ll> data;
    rep0(i,N){
        data[a[i]]++;
    }
    rep0(i,N){
        data[a[i]+1]++;
    }
    rep0(i,N){
        data[a[i]-1]++;
    }
    ll ans,Max=0;
    for(auto i:data){
        auto key=i.first;
        auto value=i.second;
        Max=max(Max,value);
        if(Max==value){ans=value;}
        //cout<<value<<endl;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
ll ans=0;
int n,k;
ll a[maxn],b[maxn],c[maxn],d[maxn];
void init(int s){
	for(int i=1;i<=n;i++){
		if(s&1)a[i] = -a[i];
		if(s&2)b[i] = -b[i];
		if(s&4)c[i] = -c[i];
	}
	return ;
}
int main()
{
	cin >> n >> k;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
	for(int i=0;i<=7;i++){
		init(i);
		ll cur = 0;
		for(int j=1;j<=n;j++)
			d[j]=-(a[j]+b[j]+c[j]);
		sort(d+1,d+1+n);
		for(int j=1;j<=k;j++)
			cur -= d[j];
		if(cur>ans) ans=cur;
		init(i);
	}
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 256
let split str delim =
  let rec doit s acc =
    match
      try Some (String.index s delim)
      with _ -> None
    with
    | None -> s :: acc
    | Some i ->
        let s1 = String.sub s 0 i in
        let s2 = String.sub s (i + 1) (String.length s - String.length s1 - 1) in
        doit s2 (s1 :: acc)
  in
  List.rev (doit str [])

let string_fold_left f init str =
  let n = String.length str in
  let rec doit i acc =
    if i >= n then acc
    else doit (i + 1) (f acc str.[i])
  in
  doit 0 init

let swap (a, b) = (b, a)

let make_dice = function
  | a :: b :: c :: d :: e :: f :: _ -> [(a, f); (b, e); (c, d)]
  | _ -> exit 1

let roll dice cmd =
  match dice with
  | [] | [_] | _::_::[] -> exit 1
  | x :: y :: z :: _ ->
      match cmd with
      | 'N' -> [y; swap x; z]
      | 'S' -> [swap y; x; z]
      | 'E' -> [swap z; y; x]
      | 'W' -> [z; y; swap x]
      | _ -> exit 1

let multi_roll dice cmds =
  string_fold_left (fun acc c -> roll acc c) dice cmds

let rotate_clockwise = function
  | [] | [_] | _::_::[] -> exit 1
  | x :: y :: z :: _ -> [x; z; swap y]

let all_rolled_patterns dice =
  let pin_top d =
    [d; roll d 'N'; roll d 'W'; roll d 'E'; roll d 'S'; multi_roll d "SS"]
  in
  let rotate d =
    let d1 = rotate_clockwise d in
    let d2 = rotate_clockwise d1 in
    let d3 = rotate_clockwise d2 in
    [d; d1; d2; d3]
  in
  List.concat (List.map rotate (pin_top dice))

let equal_dice_p d1 d2 = List.mem d1 (all_rolled_patterns d2)

let rec diff_paris_p = function
  | [] -> true
  | hd :: tl -> List.for_all (fun d -> not (equal_dice_p hd d)) tl && diff_paris_p tl

let () =
  let n = read_int () in
  let rec doit i acc =
    if i > n then acc
    else
      let l = read_line () in
      let d = make_dice (List.map int_of_string (split l ' ')) in
      doit (i + 1) (d :: acc)
  in
  let dices = doit 1 [] in
  if diff_paris_p dices then Printf.printf "Yes\n"
  else Printf.printf "No\n"

Measured memory_bytes: 4328
#pragma GCC optimize("O2")
#include<iostream>
using namespace std;
#define f(x,y,z) for(int x=y;x<z;++x)
bool b[6][6], r[6], c[6];
int h, w, k, rr[6], cc[6], m, sm, hs, ht;
char x;
void hit(int z) {
    if(z == h+w) {
        sm = hs = 0;
        f(i,0,h) if(r[i]) sm += rr[i];
        f(j,0,w) if(c[j]) sm += cc[j];
        f(i,0,h) if(r[i]) f(j,0,w) if(c[j] && b[i][j]) ++hs;
        sm -= hs;
        if(sm == ht-k) ++m;
    } else if(z >= h) {
        hit(z+1);
        c[z-h] = true;
        hit(z+1);
        c[z-h] = false;
    } else {
        hit(z+1);
        r[z] = true;
        hit(z+1);
        r[z] = false;
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> h >> w >> k;
    f(i,0,h) f(j,0,w) {
        cin >> x;
        if(x == '.') b[i][j] = false;
        else {
            b[i][j] = true;
            ++rr[i], ++cc[j], ++ht;
        }
    }
    hit(0);
    cout << m << '\n';
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
#include <map>
#include <ctime>
#include <cmath>
#include <string.h>
#define inf 0x7fffffff
using namespace std;
struct I
{
    int x,y;
};


int a,b,c,k,n,m,i,e,d,o[110][210][110],l[1000212],dx[20]={1,-1},dy[20]={0,0,1,-1},dz[20]={1,-1};
long long x,y,z[110];
//map <string,int> m;
int j[1060];

stack<int> s;
//char r[55];
//deque<int> d;
struct P
{
    int x,y;
    /*bool operator<(const P &a)const
    {

        return max(x,-x)<=max(a.x,-a.x);
    }*/
};
double u;
//P u[500000];
vector <int> v[211010];
queue<P> q;
string r,r1[100];
map<string,int > p;
//A==65
//Z==90

//a==97

int f(int t)
{
    if(b<0||c<0||d<0) return 0;
    if(b==0&&c==0&&d==0) return 1;
    if(t%2)
    {
        d--;
        return f(4);
    }
    if(t%4==2)
    {
        c--;
        return f(2);
    }
    int k=0;
    if(b>0)
    {
    b--;
    return f(1);
    }
    //b++;
    if(c>0)
    {
    c--;
    k=max(k,f(2));
    }
    //c++;
    d--;
    k=max(k,f(4));
    return k;
}

int main()
{
    scanf("%d",&a);
    for(int t=1;t<=a;t++)
    {
        scanf("%d",&i);
        if(i%4==0) d++;
        else if(i%2==0) c++;
              else b++;
    }
    if(f(0)) puts("Yes");
    else puts("No");
}


Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,a[305];
ll dp[900005];
ll dp2[900005];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
int main(){
	cin>>n;
	int s = 0;
	repn(i,n) {cin>>a[i];s+=a[i];}
	dp[0] = 1;
	dp2[0] = 1;
	ll hf = (mod+1)/2;
	repn(i,n){
		for(int j=300*300+2;j>=0;j--){
			dp[j+a[i]] += dp[j]*hf%mod;
			if(dp[j+a[i]] >= mod) dp[j+a[i]]-=mod;
			dp2[j+a[i]] += dp2[j];
			if(dp2[j+a[i]] >= mod) dp2[j+a[i]]-=mod;
		}
	}
	ll t = 1;
	rep(i,n) t = t*2LL%mod;
	ll ans = 1;
	rep(i,n) ans = ans*3LL%mod;
	for(int i=(s+1)/2;i<=s;i++){
		ans -= dp[i]*t%mod*3LL%mod;
	}
	if(s%2==0){
	    ans += dp2[s/2]*3LL%mod;
	}
	cout<<(ans%mod+mod)%mod<<endl;
}


Measured memory_bytes: 2944
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1

    # 辺のindexを持っておく
    T[a].append([b, i])
    T[b].append([a, i])


stack = [[0, 0]]  # [次の頂点番号, 親に続く辺の色]
visited = [0] * N
colors = [0] * (N - 1)
while stack:
    n, parent_color = stack.pop()
    visited[n] = 1
    color = 1

    for to, i in T[n]:
        if visited[to]:
            continue

        if color == parent_color:
            color += 1

        colors[i] = color
        stack.append([to, color])

        color += 1


print(len(set(colors)))
print(*colors, sep='\n')






Measured memory_bytes: 47432
#include<cassert>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<queue>
#define FL "a"
using namespace std;
typedef long long ll;
typedef long double dd;
const int N=1e5+10;
const int M=1e6+10;
const dd pi=acos(-1);
const int inf=1e9;
const int eps=1e-6;
const ll INF=1ll<<60;
inline ll read(){
  ll d=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')d=d*10+ch-48,ch=getchar();
  return d*w;
}
inline void file(){
  freopen(FL".in","r",stdin);
  freopen(FL".out","w",stdout);
}

int n,len,a[N],b[N],c[N];
inline void insert(int i,int p){
  for(int j=len+1;j>i;j--)a[j]=a[j-1];len++;a[i]=p;
}

int main()
{
  n=read();
  for(int i=1;i<=n;i++){
    b[i]=read();
    if(b[i]>i)return puts("-1"),0;
    insert(b[i],i);
  }
  for(int i=1;i<=n;i++)printf("%d\n",b[a[i]]);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////



int main(){

    int n;
    cin >> n;
    ll a[100005] = {};
    ll sum = 0;
    rep(i,0,n){
        cin >> a[i];
        sum += a[i];
    }
    rsort(a,a+n,ll);
    sum -= a[0];
    
    int ans = 1;
    
    rep(i,0,n){
        if(sum * 2 >= a[i]){
            sum -= a[i+1];
            ans++;
        }else break;
    }
    
    P(ans);
	return  0;
}

Measured memory_bytes: 1024
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        m: usize,
        v: [(usize1, usize1); m]
    }
    let mut g = vec![vec![]; n];
    for &(a, b) in &v {
        g[a].push(b);
        g[b].push(a);
    }
    let mut ans: usize = 0;
    let mut ds = vec![n; n];
    let mut single = 0;
    let mut block = 0;
    let mut con = 0;
    for i in 0..n {
        if ds[i] < n {
            continue;
        }
        ds[i] = 0;
        let (s, oc) = dfs(i, &g, &mut ds);
        if s == 1 {
            single += 1;
        } else if oc  {
            ans += 2 * block + 1;
            block += 1;
            con += 1;
        } else {
            ans += 2 * con + 2;
            block += 1;
            con += 2;
        }
    }
    ans += single * (2 * n - single);
    println!("{}", ans);
}

fn dfs(v: usize, g: &Vec<Vec<usize>>, ds: &mut Vec<usize>) -> (usize, bool) {
    let mut s = 1;
    let mut oc = false;
    for &c in &g[v] {
        if ds[c] == g.len() {
            ds[c] = ds[v] + 1;
            let sub = dfs(c, g, ds);
            s += sub.0;
            oc |= sub.1;
        } else if (ds[v] + ds[c]) % 2 == 0 {
            oc = true;
        }
    }
    (s, oc)
}


Measured memory_bytes: 25084
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
#define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/
const int MAXN = 2e5 + 10;
const int mod = 1e9 + 7;
int nums[MAXN];





int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cout.precision(10); cout << fixed;
#ifdef LOCAL
  freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
  int n; cin >> n;
  LL sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> nums[i];
    sum += nums[i];
  }
  LL ret = 0;
  for (int i = 0; i < n; i++) {
    sum -= nums[i];
    ret = (sum % mod * nums[i] % mod + ret) % mod;
  }
  cout << ret << '\n';






/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
  return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 3952
import math
def combinations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,p=map(int,input().split())
a=list(map(int,input().split()))
n0=0
n1=0
ans=0
for i in range(len(a)):
  if a[i]%2:
    a[i]=1
    n1+=1
  else:
    a[i]=0
    n0+=1
s=sum(a)
for i in range(0,s+1,2):
  ans+=combinations(n1,i)
  if p==1 and s==0:
    print(0)
    exit()
print(ans*(2**n0))

Measured memory_bytes: 3188
#include <iostream>

using namespace std;
constexpr int64_t MOD =   998'244'353;
constexpr int     MAX =       200'005;

int64_t fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
int64_t COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

template< typename T >
T mod_pow(T x, T n) {
    T ret = 1;
    while(n > 0) {
        if(n & 1) (ret *= x) %= MOD;
        (x *= x) %= MOD;
        n >>= 1;
    }
    return ret;
}
int main(void) {
    int64_t N, M, K;
    cin >> N >> M >> K;
    COMinit();

    int64_t ans = 0;
    for(int64_t i=0; i<=K; i++) {
        ans += COM(N-1, i) * mod_pow(M-1, N-1-i);
        ans %= MOD;
    }

    ans *= M;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8248
[a] = list(map(str, input().split()))

flag=1
rem1=0
count=0

for i in range(len(a)):
  if(int(a[i])==0):
    if(rem1>0):
      count+=2
      rem1-=1
    else:
      rem1-=1
  if(int(a[i])==1):
    if(rem1<0):
      rem1+=1
      count+=2
    else:
      rem1+=1

print(count)

Measured memory_bytes: 3188
#include <iostream>
#include <vector>

constexpr int ELM = 200200;
constexpr int LG = 60;
constexpr long long INF = 1e18;

int main() {
	int n;
	long long k;
	std::cin >> n >> k;
	const long long MAX = n * k;
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	
	std::vector<std::vector<long long>> next(LG, std::vector<long long>(n));
	std::vector<int> idx(ELM, -1);
	for (int id = 2 * n; id --> 0;) {
		int i = id % n;
		if (id < n) next[0][i] = idx[a[i]] - i + 1;
		idx[a[i]] = id;
	}
	
	for (int i = 1; i < LG; i++) {
		for (int j = 0; j < n; j++) {
			int id = (next[i - 1][j] + j) % n;
			next[i][j] = std::min(INF, next[i - 1][j] + next[i - 1][id]);
		}
	}
	
	long long s = 0;
	for (int i = LG; i --> 0;) {
		int id = s % n;
		if (s + next[i][id] <= MAX) s += next[i][id];
	}
	
	std::vector<int> sec;
	while (s < MAX) {
		int i = s % n;
		if (s + next[0][i] <= MAX) {
			s += next[0][i];
		} else {
			sec.push_back(a[i]);
			s++;
		}
	}
	
	for (auto e : sec) std::cout << e << ' ';

	return 0;
}

Measured memory_bytes: 100396
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define LIMIT 1000000007 //10^9+7
#define rep(i, n) for(int i=0; i<(int)n; i++)
/* 一括cin */
template<class H>
void CIN(H& h){cin>>h;}
template<class H, class... T>
void CIN(H &h, T&... t){cin>>h;CIN(t...);}

int main(){
  ll a,v,b,w,t;CIN(a,v,b,w,t);
  ll dist = abs(b-a);
  ll spd = w>v ? 0 : v-w;
  bool ok;
  if(spd==0)ok=false;
  else ok= dist <= t*spd;

  cout<<(ok?"YES\n":"NO\n");
}

Measured memory_bytes: 3592
def main():
  import sys
  a=int(input())
  b=tuple(map(int,sys.stdin.readline().split()))
  c=[None]*a
  d=1
  for e in b:
    c[e-1]=d
    d=d+1
  print(" ".join(map(str,c)))
if __name__=="__main__":
  main()

Measured memory_bytes: 17740
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

#include "bits/stdc++.h"
using namespace std;

int main() {
	string S, T;
	cin >> S;
	cin >> T;

	int cnt = 0;

	REP(i, 3) {
		if (S[i] == T[i]) {
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();

        double nn = Math.floor(n / (a+b) * 1.0);

        long blue = ((long)nn) * a;
        long red = ((long)nn) * b;

        if (blue + red + a <= n) blue += a;
        else blue += (n - (blue + red));

        System.out.println(blue);

    }
}

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

int main(){
    int N,X,T;
    cin >> N >> X >> T;
    if(N%X != 0){
        N = N/X + 1;
    }
    else{
        N = N/X;
    }
    T = T*N;
    cout << T << endl;
}

Measured memory_bytes: 3620
N=int(input())
H=list(map(int, input().split(" ")))
ans=0
buf=[0 for _ in range(N-1)]
for i in range(N-1):
    if H[i]>=H[i+1]:
        buf[i]=1
cnt=0
for i in range(N-1):
    if buf[i]==1:
        cnt+=1
    else:
        cnt=0
    if cnt>ans:
        ans=cnt
print(ans)


Measured memory_bytes: 14224
#include<iostream>
#include<cstdlib>
using namespace std;
int main(){
    long long a,b;
    cin >> a >> b;
    int c = (a+b)/2;
    if(abs(a-c) == abs(b-c)){
        cout << abs(c);
    }else {
        cout << "IMPOSSIBLE" << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>



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


map<string, int> mp;
#define ll long long

int main() {
    int n;
    cin >> n;
    int ans = 0;
    rep(i, n) {
        int a;
        cin >> a;
        ans += a;
    }
    if (ans % 2 == 0)cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256