akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 1e5+100;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;

ll a,b;

int main()
{
	scanf("%lld%lld",&a,&b);
	if(a == b) printf("0\n");
	else if((a+b)%2 == 0){
		printf("%lld\n",(a+b)/2);
	}
	else printf("IMPOSSIBLE\n");
	return 0;
}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int M,N;
    Scd2(N,M);

    vector<int> s(N);
    vector<int> t(M);
    Rep(i,N){
        Scd(s[i]);
    }
    Rep(i,M){
        Scd(t[i]);
    }

    ll mod = 1000000007;

    vector<ll> dp(M+1,1);
    vector<ll> tmpdp(M+1,1);

    ll tmp = 0;
    Rep(i,N){
        tmp = 0;
        Rep(j,M){
            if( s[i] == t[j] ){
                tmp += dp[j];
                tmp %= mod;
            }
            tmpdp[j+1] = dp[j+1] + tmp;
            tmpdp[j+1] %= mod;
        }
        Rep(j,M+1){
            dp[j] = tmpdp[j];
        }
    }

    printf ("%llu\n", dp[M] );



    return 0;
}



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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;

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

    string s;
    cin >> s;

    bool ok = true;
    string tmp = s;
    reverse(all(tmp));

    if(s != tmp) ok = false;
    string tmp2 = s.substr(0, (s.size()-1)/2);
    tmp = tmp2;
    reverse(all(tmp2));
    if(tmp != tmp2) ok = false;
    tmp2 = s.substr((s.size()+3)/2-1, s.size());
    tmp = tmp2;
    reverse(all(tmp2));
    if(tmp != tmp2) ok = false;

    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define ind(a) scanf("%lf", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a));
//def   puts(a) printf("%s\n", a) 文字はこっち
//your code here!

ll f(ll a){
    return (a%2) ? 3*a+1 : a/2;
}

int main(void){
    ll s, ans=1;
    in(s);
    while(1){
        if(s==4||s==2||s==1){
            ans += 3;
            put(ans);
            return 0;
        }
        ans++;
        s = f(s);
    }
}


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

int n;

int main() {
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; ++i) {
        cin >> p.at(i);
    }

    int count = 0;

    for(int i = 1; i <= n-2; ++i) {
        if(p.at(i) < p.at(i+1)) {
            if(p.at(i) > p.at(i-1)) {
                count++;
            }
        }else {
            if(p.at(i) < p.at(i-1)) {
                count++;
            }
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;

ll a[N], cum[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cum[i] = cum[i - 1] + a[i];
    map<int, ll> mp;
    ll ans = 0;
    mp[0] = 1;
    for(int i = 1; i <= min(k - 1, n); i++){
        ans += mp[((cum[i] - i) % k + k) % k];
        mp[((cum[i] - i) % k + k) % k]++;
    }
    for(int i = k; i <= n; i++){
        mp[((cum[i - k] - (i - k)) % k + k) % k]--;
        ans += mp[((cum[i] - i) % k + k) % k];
        mp[((cum[i] - i) % k + k) % k]++;
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 19232
/* ex 5_4
   B30095   */

#include <stdio.h>
#define MAX_LEN 10

int isACGT(char ch);
int MaxACGTLen(char * str);

int main(void){
    int acgtLength;
    char str[MAX_LEN + 1];

    scanf("%s", str);
    acgtLength = MaxACGTLen(str);
    printf("%d", acgtLength);

    return 0;
}


/*
 *  returns 1 if ch is one of ACGT
 *  returns 0 otherwise 
 */
int isACGT(char ch){
    if(ch == 'A' || ch == 'C' || ch == 'G' || ch == 'T'){
        return 1;
    }
    else{
        return 0;
    }
}


/*
 *  returns length of the longest ACGT substring
 */
int MaxACGTLen(char * str){
    int cnt = 0, maxCnt = 0;
    char * strPtr = str;

    while(*(strPtr) != '\0'){  // scan the string through the end
        // increase cnt if the character is one of ACGT
        if(isACGT(*(strPtr))){
            cnt++;
        }
        else{
            if(cnt > maxCnt) maxCnt = cnt;  // renew max count
            cnt = 0;  // reset cnt
        } 
        strPtr++;
    }

    if(cnt > maxCnt) maxCnt = cnt;  // renew max count

    return maxCnt;
}

Measured memory_bytes: 1736
a = list(map(int,input().split()))
m=0
ans = 0
while m < 1000001:
	if a[m]%2==0:
		a.append(a[m]//2)
	else:
		a.append(3*a[m]+1)
	for i in range(m):
		if a[i] == a[m]:
			ans = m+1
			break
	if ans > 0:
		break
	m+=1
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <math.h>
#include <assert.h>
#include <set>
#include <map>
#include <bitset>
#include <ctime>
#include <time.h>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <stack>
#include <ctype.h>
#include <numeric>
#include <sstream>
#include <unistd.h>
#include <unordered_map>
#include <limits>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(int argv, char **argc){
    cin.tie(0); ios::sync_with_stdio(0);

    int a,b;
    cin >> a >> b;
    if((a + b) % 2 == 0){
        printf("%d\n", (a + b) / 2);
    }
    else {
        printf("IMPOSSIBLE\n");
    }
}

Measured memory_bytes: 256
fun main(args:Array<String>?): Unit {
    //comparator[a][b] => a.compareTo(b)
    val comparator = Array(26){IntArray(26){0}}
    while(true){
        val n = readLine()!!.trim().toInt()
        if (n == 0) return
        comparator.forEach { it.fill(0) }
        var fail = false
        val words = Array(n){readLine()!!.trim()}
        for (i in 1 until n){
            val prev = words[i - 1]
            val next = words[i]
            for (j in prev.indices){
                if (j !in next.indices){
                    fail = true
                }else if (prev[j] != next[j] && comparator[prev[j].toIndex][next[j].toIndex] == 1){
                    fail = true
                }else if (prev[j] != next[j] && comparator[prev[j].toIndex][next[j].toIndex] == 0){
                    comparator[prev[j].toIndex][next[j].toIndex] = -1
                    comparator[next[j].toIndex][prev[j].toIndex] = 1
                }
                if (j !in next.indices || prev[j] != next[j]) break
            }
        }
        if (!fail){
            outer@for (next in 1 until 26){
                for (prev in 0 until next) {
                    for (mid in 0 until 26) if (comparator[prev][mid] == comparator[mid][next] && comparator[prev][mid] != 0){
                        if (comparator[prev][next] == 0){
                            comparator[prev][next] = comparator[prev][mid]
                            comparator[next][prev] = comparator[mid][prev]
                        }else if (comparator[prev][next] != comparator[prev][mid]) {
                            fail = true
                            break@outer
                        }
                    }
                }
            }
        }
        println(
                if (fail) "no" else "yes"
        )
    }
}
val Char.toIndex: Int
        get() = this - 'a'


Measured memory_bytes: 37484
#include<bits/stdc++.h>
	using namespace std;
	#define int long long 
	#define rep(i,n) for(int i=0;i<n;i++)
	void printv(vector<char> v){
		for(int i=0;i<v.size();i++){
			cout<<v[i];
		}
		cout<<endl;
	}
	bool comp(pair<int,int>a,pair<int,int> b){
		return a.second<b.second;
	}
	bool check(int x){
		while(x!=1){
			if(x%2){
				return 0;
			}
			else x/=2;
		}
		return 1;
	}
	int tcpow(int x) {
		int pow=0;
		while(x!=0){
			x/=2;
			pow++;
		}
		return pow;
	}	
	
	// // int funt(int y){
	// // 	if(y%k || y==0)	return a*y + (y/k)*t +b*(d-y);
	// // 	else return a*y + (y/k -1)*t +b*(d-y);
	// // }
	// int minn=1e18;
	// int findy(int start,int end){
	// 	if(start==end) return funt(start);
	// 	if(start>end) return INT_MAX;
	// 	if(funt((start+end)/2)>minn) return minn;
	// 	int a=findy(start,(start+end)/2);
	// 	//cout<<a<<endl;
	// 	int b=findy((start+end)/2+1,end);
	// 	//cout<<b<<endl;
	// 	if(minn>min(a,b)) minn=min(a,b);
	// 	return min(a,b);

	// }

	void makedp(int n,int* dp){
		int x=2;
		rep(i,n+1) dp[i]=1;
		dp[0]=0;
		while(x<=n){
			int j=1;
			while(x*j<=n){
				dp[x*j]++;
				j++;
			}
			x++;
		}
	}
	int dp[10000001];
	signed main(){
		int tt=1;
		//cin>>tt;
		while(tt--){
			int n;
			cin>>n;
			
			makedp(n,dp);
			int x=0;
			for(int i=1;i<=n;i++){
				x+=(i*dp[i]);
				//cout<<dp[i]<<" "<<i<<" ";
			}
			cout<<x<<endl;

		}

	}

Measured memory_bytes: 81672
#include<bits/stdc++.h>
 
#define lli long long int
#define endl "\n"
 
using namespace std;
 
typedef long long int LLI;
typedef double DB;
 
void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
 
 
bool comparator(pair<lli,lli> a,pair<lli,lli> b)
{
    if(a.first>b.first)
        return true;
    else if (a.first==b.second)
    {
        if(a.second>=b.second)
            return false;
        return true;
    }
    return false;
}
 
int mods(int x)
{
    if(x>0)
        return x;
    return -x;
}
 
lli gcd(lli a,lli b)
{
    return __gcd(a,b);
}
 
lli lcm(lli x,lli y,lli z)
{
    lli j=gcd(x,y);
    lli k=gcd(y*x/j,z);
    return (((x*y)/j)*z)/k;
} 

int arr[3][3];
bool vis[3][3]={0};

int main()
{
    fastio();
    int n,k; cin>>n>>k;
    int count=0;
    for(int i=0;i<n;i++)
    {
        int j; cin>>j;
        count+=min(2*j,2*mods(k-j));
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
import           Data.Int

modc = 1000000007 :: Int64

fact :: Int -> Int64
fact x | x == 0    = 1 :: Int64
       | otherwise = fromIntegral x * fact (x - 1) `mod` modc

sqr :: Int64 -> Int64
sqr x = x * x `mod` modc

solve :: Int -> Int -> Int64
solve n m | n < m      = solve m n
          | n == m     = fromIntegral 2 * sqr (fact n) `mod` modc
          | n == m + 1 = fact n * fact m `mod` modc
          | otherwise  = 0

main = do
  input <- getLine
  let n : m : [] = map (read :: String -> Int) $ words input
  putStrLn . show $ solve n m
  return ()


Measured memory_bytes: 3068
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N, K = map(int, input().split())
a = list(map(int, input().split()))
if K >= N - 1:
  print(int(a[0] != 1))
  exit(0)
res = 0
if a[0] != 1:
  a[0] = 1
  res += 1
e = dd(set)
inc = [0] * (N + 1)
for i in range(N):
  if i + 1 == a[i]: continue
  e[a[i]].add(i + 1)
  inc[a[i]] += 1

t = set()
def dfs(x):
  global res
  d = 0
  for y in e[x]:
    d = max(d, dfs(y) + 1)
  if d == K - 1:
    res += (a[x - 1] != 1)
    return -1
  return d
  

dfs(1)
print(res)

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

char s[1000][1001];
int h, w, dp[1000][1000][1 << 5], dx[]{ -1,0,1,0 }, dy[]{ 0,-1,0,1 };
int a[]{ 0,2,4,3 }, b[]{ 0,2,3,1 };

int s1(int t) {
	int u = 0;
	if (t >> 3 & 1)u |= 1;
	if (t >> 4 & 1)u |= 1 << 2;
	return u;
}
int s2(int t) {
	int u = 0;
	if (t >> 1 & 1)u |= 1;
	if (t >> 3 & 1)u |= 1 << 2;
	return u;
}
int rec(int x, int y, int t) {
	int T = t;
	if (dp[x][y][t] != -1)return dp[x][y][t];
	int res = INT_MAX, p = 0;
	if ((!(t >> 3 & 1)) && s[x][y]) {
		t |= 1 << 3; p = s[x][y];
	}
	if (x == h - 1 && y == w - 1)return dp[x][y][t] = p;
	vector<P>v;
	rep(i, 4) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= h || ny >= w || !s[nx][ny])continue;
		if (i < 2 && (t >> a[i] & 1))continue;
		v.push_back(P(s[nx][ny], i));
	}
	if (v.empty()) {
		if (x + 1 < h)res = min(res, rec(x + 1, y, s1(t)) + p);
		if (y + 1 < w)res = min(res, rec(x, y + 1, s2(t)) + p);
	}
	rep(i, v.size()) {
		if (x + 1 < h) {
			int sum = p, r = t, u = 0;
			rep(j, v.size()) {
				if (i == j)continue;
				sum += v[j].first;
				if (v[j].second >= 2)u |= 1 << b[v[j].second];
				else r |= 1 << b[v[j].second];
			}
			res = min(res, rec(x + 1, y, s1(r) | u) + sum);
		}
		if (y + 1 < w) {
			int sum = p, r = t, u = 0;
			rep(j, v.size()) {
				if (i == j)continue;
				sum += v[j].first;
				if (v[j].second >= 2)u |= 1 << a[v[j].second];
				else r |= 1 << a[v[j].second];
			}
			res = min(res, rec(x, y + 1, s2(r) | u) + sum);
		}
	}
	return dp[x][y][T] = res;
}
int main() {
	scanf("%d%d", &h, &w);
	rep(i, h) {
		scanf("%s", s[i]);
		rep(j, w) {
			if (isdigit(s[i][j]))s[i][j] -= '0';
			else s[i][j] = 0;
		}
	}
	memset(dp, -1, sizeof(dp));
	printf("%d\n", rec(0, 0, 0));
}

Measured memory_bytes: 129552
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

int main(){
  int i,j;
  ll n,k,s;
  cin>>n>>k>>s;
  for(i=0;i<k;i++){
    cout<<s<<" ";
  }
  for(i=k;i<n;i++){
    if(s<1000000000) cout<<s+1<<" ";
    else cout<<s-1<<" ";
  }
  cout<<endl;

  return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<vector>
using namespace std;
int h,w;
string m[500];
int dx[]={0,-1,0,1},dy[]={1,0,-1,0};
string c="RULD";
main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++)
	{
		cin>>m[i];
	}
	vector<pair<int,int> >a,b;
	int x=0,y=0;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(m[i][j]=='#')a.push_back(make_pair(i,j));
		}
	}
	while(1&&a.size()>1)
	{
		cout<<"? U"<<endl;
		string in;cin>>in;
		if(in[0]=='Y')
		{
			b.clear();
			x--;
			for(int i=0;i<a.size();i++)
			{
				int tx=a[i].first-1,ty=a[i].second;
				if(tx>=0&&m[tx][ty]=='#')b.push_back(make_pair(tx,ty));
			}
			a=b;
		}
		else
		{
			break;
		}
	}
	int dir=2;
	while(a.size()>1)
	{
		for(int r=-1;a.size()>1&&r<3;r++)
		{
			int nowr=(dir+r+4)%4;
			cout<<"? "<<c[nowr]<<endl;
			string in;cin>>in;
			if(in[0]=='Y')
			{
				x+=dx[nowr],y+=dy[nowr];
				b.clear();
				for(int i=0;i<a.size();i++)
				{
					int tx=a[i].first+dx[nowr],ty=a[i].second+dy[nowr];
					if(tx>=0&&ty>=0&&tx<h&&ty<w&&m[tx][ty]=='#')
					{
						b.push_back(make_pair(tx,ty));
					}
				}
				dir=nowr;
				a=b;
				break;
			}
			else
			{
				b.clear();
				for(int i=0;i<a.size();i++)
				{
					int tx=a[i].first+dx[nowr],ty=a[i].second+dy[nowr];
					if(!(tx>=0&&ty>=0&&tx<h&&ty<w&&m[tx][ty]=='#'))
					{
						b.push_back(a[i]);
					}
				}
				a=b;
			}
		}
	}
	cout<<"! "<<a[0].first-x<<" "<<a[0].second-y<<endl;
}



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

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

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

	while(cin>> N >> T >> L >> R, N) {
		vector<int>flag(N + 1);
		vector<vector<vector<long double>>>p(T + 1, vector<vector<long double>>(N + 1, vector<long double>(2)));
		p[0][0][0] = 1;
		for (int i = 0; i < L; i++) {
			cin >> K;
			flag[K] = 1;
		}
		for (int i = 0; i < R; i++) {
			cin >> K;
			flag[K] = 2;
		}
		for (int i = 0; i < T; i++) {
			for (int j = 0; j < N; j++) {
				p[i + 1][j][0] += p[i][j][1];
				for (int k = 1; k <= 6; k++) {
					int nx = j + k;
					if (nx > N)nx = 2 * N - nx;
					if (flag[nx] == 0) {
						p[i + 1][nx][0] += p[i][j][0] / 6;
					}
					else if (flag[nx] == 1) {
						p[i + 1][nx][1] += p[i][j][0] / 6;
					}
					else {
						p[i + 1][0][0] += p[i][j][0] / 6;
					}
				}
			}
			p[i + 1][N][0] += p[i][N][0];
		}
		cout <<fixed<< setprecision(20) << p[T][N][0] << endl;
	}
}


Measured memory_bytes: 4004
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

constexpr int MAX_N = 100100;

using namespace std;

int n;
int arr[MAX_N];
ll suf[MAX_N];
int sub[MAX_N];
int pre[MAX_N];
bool has[MAX_N];
ll exempt[MAX_N];
ll ans[MAX_N];

ll tree1[4*MAX_N];
ll tree2[4*MAX_N];

ll update(ll *tree, int i, int a, int b, int j, int m) {
    if (b < a) return 0;
    if (b < j || j < a) return tree[i];
    if (a == b && a == j) tree[i] = m;
    else tree[i] = update(tree, 2*i+1, a, (a+b)/2, j, m)
        + update(tree, 2*i+2, (a+b)/2+1, b, j, m);
    return tree[i];
}

ll query(ll *tree, int i, int a, int b, int l, int r) {
    if (b < a) return 0;
    if (b < l || r < a) return 0;
    if (a >= l && b <= r) return tree[i];
    return query(tree, 2*i+1, a, (a+b)/2, l, r)
        + query(tree, 2*i+2, (a+b)/2+1, b, l, r);
}

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

    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + arr[i];
    }

    int ma = 0;
    for (int i = 1; i <= n; i++) {
        if (arr[i] > arr[ma]) {
            sub[ma] = i;
            pre[i] = ma;
            has[i] = true;
            ma = i;
        }
    }

    vector<pair<int, int>> events;
    for (int i = 1; i <= n; i++) {
        events.push_back(make_pair(arr[i], -i));
    }

    sort(events.begin(), events.end());

    for (pair<int, int> event : events) {
        int amt = event.first;
        int idx = -event.second;
        update(tree1, 0, 1, n, idx, amt);
        update(tree2, 0, 1, n, idx, 1);
        if (sub[idx] > 0) {
            exempt[sub[idx]] = query(tree2, 0, 1, n, sub[idx], n) * amt
                - query(tree1, 0, 1, n, sub[idx], n);
        }
    }

    ll last = 0;
    for (int i = n; i >= 1; i--) {
        if (has[i]) {
            ans[i] = suf[i] - 1LL * arr[pre[i]] * (n - i + 1)
                + exempt[i] - last;
            last += ans[i];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!has[i]) {
            printf("0\n");
        } else {
            printf("%lld\n", ans[i]);
        }
    }

    return 0;
}


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

void input(string& rsTarget)
{
  cin >> rsTarget;
}

int parse(string sTarget)
{
  const vector<string> cnvsWord{"dream", "dreamer", "erase", "eraser"};
  int ixBgn, ixEnd;
  ixBgn = sTarget.size();

  while (ixBgn)
  {
    bool bReslt = false;
    ixEnd = ixBgn;
    for (int i = 0; i < cnvsWord.size(); i++)
    {
      ixBgn = ixEnd - cnvsWord[i].size();
      if (ixBgn < 0)  continue;

      if (sTarget.substr(ixBgn, cnvsWord[i].size()) == cnvsWord[i])
      {
        bReslt = true;
        break;
      }
    }
    if (!bReslt)  return 0;
  }
  return 1;
}

int main()
{
  string sTarget;
  
  input(sTarget);
  if (parse(sTarget)) cout << "YES" << endl;
  else                cout << "NO"  << endl;

  return 0;
}

Measured memory_bytes: 3772
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <cstring>
#include <functional>
//#include<unordered_map>
//#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF ((Int)1<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P; 
const int N = 200005;
//////////////////////////////

int h, w;
char s[111][111];
int dp[111][111];

void solve()
{
	cin >> h >> w;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			cin >> s[i][j];

	for (int i = 0; i <= h; i++) dp[i][0] = INF;
	for (int j = 0; j <= w; j++) dp[0][j] = INF;
	dp[1][1] = s[1][1] == '.' ? 0 : 1;

	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++) {
			if (i == 1 && j == 1) continue;
			
			if (s[i][j] == '.') {
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
			}
			else {
				dp[i][j] = min(dp[i - 1][j] + (s[i - 1][j] == '.'), dp[i][j - 1] + (s[i][j - 1] == '.'));
			}
		}
	cout << dp[h][w] << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);
	solve();
	return 0;
}


Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
long double x,d,ans;
int n;
int main(){
	scanf("%d%Lf%Lf",&n,&x,&d);
	for(int i=1;i<=n;i++){
		int tot=2*(n-i+1);
		ans+=(x*2+(tot-1)*d)/2;
		x+=(x*2+5*d)/tot;
		d+=4*d/tot;
	}
	printf("%.9Lf\n",ans);
	return 0;
}


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

const ull mask = (1ll << 52) - 1;
const ull err = numeric_limits<ull>::max();

ull get_man(ull x) { return x & mask; }

ull get_exp(ull x) { return (x >> 52) & ((1ll << 12) - 1); }

ull get_msb(ull x) {
    for(int i = 63; 0 <= i; i--) if((x >> i) & 1) return i;
    return err;
}

ull solve(ull N, string S) {
    ull init = [&] {
        ull pow2 = 1;
        reverse(S.begin(), S.end());
        ull ret = 0;
        for(char c : S) {
            ret += (c - '0') * pow2;
            pow2 *= 2;
        }
        return ret;
    }();
    ull cur = init;

    while(N) {
        ull cur_exp = get_exp(cur);
        ull cur_man = get_man(cur);
        ull init_exp = get_exp(init);
        ull add_v_man = (1ull << 52) | get_man(init);
        cur_man |= (1ull << 52);
        add_v_man >>= (cur_exp - init_exp);
        // cout << cur_exp << ", " << cur_exp - init_exp << endl;
        if(add_v_man == 0) break;
        ull add_v_msb = get_msb(add_v_man);
        ull ng = min<ull>(N, (1ll << (52 - add_v_msb))) + 1;
        ull ok = 0;
        while(ng - ok > 1) {
            ull mid = (ok + ng) / 2;
            ull sum = add_v_man * mid;
            if((cur_man + sum) & ((~mask) ^ (1ll << 52))) ng = mid;
            else ok = mid;
        }
        if(ok < N) ok++;
        N -= ok;
        for(int i = 0; i < 64; i++) if((ok >> i) & 1) cur_man += add_v_man * (1ll << i);
        ull cur_man_msb = get_msb(cur_man);
        if(53 <= cur_man_msb) {
            cur_man >>= (cur_man_msb - 52);
            cur_exp++;
        }
        cur_man ^= (1ull << 52);
        cur = cur_man | (cur_exp << 52);
    }

    return cur;
}

int main() {
    while(true) {
        ull N;
        cin >> N;
        if(!N) break;
        string S;
        cin >> S;
        ull ret = solve(N, S);
        cout << bitset<64>(ret).to_string() << endl;
    }
    return 0;
}



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

int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;
  
  int count = 0;
  for(int i = 0;i < N-2;i++){
    if(S.at(i) == 'A' && S.at(i+1) == 'B' && S.at(i+2) == 'C'){
      count++;
    }
  }
  
  cout << count << endl;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace _005_GCDandLCM
{
	class Program
	{
		static void Main ( string[] args )
		{
			string inputStr;

			while ((inputStr = Console.ReadLine ()) != null)
			{
				int[] numArray = inputStr.Split (' ').Select (str => int.Parse (str)).ToArray ();

				int dividend = numArray.Max ();
				int divisor = numArray.Min ();

				while (dividend % divisor != 0)
				{
					int rest;
					Math.DivRem (dividend, divisor, out rest);

					dividend = divisor;
					divisor = rest;
				}

				long lcm = (long) numArray[0] * numArray[1] / divisor;

				Console.WriteLine (divisor + " " + lcm);
			}
		}
	}
}

Measured memory_bytes: 9364
import math
from scipy.misc import comb

n = int(input())
t = [list(map(int, input().split())) for _ in range(n)]
d = 0
for i in range(n - 1):
    for j in range(i, n):
        d += (((t[i][0] - t[j][0]) ** 2 + (t[i][1] - t[j][1]) ** 2)
              ** 0.5) * ((n - 1) * math.factorial(n)/comb(n, 2))

print(d/math.factorial(n))

Measured memory_bytes: 18264
package main

import "fmt"

func main() {
	a, b := 0, 0
	fmt.Scanf("%d %d", &a, &b)
	if (b-1)%(a-1) == 0 {
		fmt.Println((b - 1) / (a - 1))
	} else {
		fmt.Println((b-1)/(a-1) + 1)
	}
}


Measured memory_bytes: 1832
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
//struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } }_io;
const int maxn=1e5+10;
int l[maxn],r[maxn],a[maxn],p[maxn];
vector<int>v[maxn];
int n;
int ff;
void dfs(int u,int from,int d){
	if(ff) return ;
	if(p[u]) l[u]=r[u]=a[u];
	for(auto i:v[u]){
		if(i==from)continue;
		if(p[i]){
			if(a[i]<l[u]-1||a[i]>r[u]+1||(a[i]&1)==d){
			 ff=1;
			 return;
	   	}
	   	dfs(i,u,d^1);
	  }
	  else{
	  	l[i]=l[u]-1;
	  	r[i]=r[u]+1;
	  	dfs(i,u,d^1);
	  }
		l[u]=max(l[i]-1,l[u]);
		r[u]=min(r[i]+1,r[u]);
	}
	if(l[u]>r[u]) ff=1;
}
bool solve(int u,int from,int x){
   a[u]=x;
	 for(auto i:v[u]){
	   if(i==from) continue;
		 if(x+1>=l[i]&&x+1<=r[i]){
		  if(!solve(i,u,x+1))solve(i,u,x-1) ;
		 }
		 else solve(i,u,x-1);
	}
	return 1;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	int k;
	cin>>k;
	int root;
	while(k--){
		int x,c;
		cin>>x>>c;
		p[x]=1;
		a[x]=c;
		root=x;
	}
	dfs(root,-1,a[root]&1);
	if(ff) cout<<"No"<<'\n';
	else{
		solve(root,-1,a[root]);
		cout<<"Yes"<<'\n';
		for(int i=1;i<=n;i++) cout<<a[i]<<'\n';
	}
}
	

Measured memory_bytes: 19780
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// リング
func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	s := sc.Text()
	sc.Scan()
	p := sc.Text()
	sr := strings.Replace(s+s, p, "", -1)
	if len([]rune(s+s)) == len([]rune(sr)) {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}



Measured memory_bytes: 1120
#include<iostream>
#include<vector>
using namespace std;
const int MAX_T = 3000;
int M, start, goal, dice[6];
vector<int> N;
 
bool isPositionValid(int p){return 0<=p && p<M;}
 
int* MakePath(int *path, int from){
    static vector<bool> visit(M);
    static auto checkPath = [&path](int moveto)->int{
        if(!isPositionValid(moveto))	return 2*MAX_T;
        else{
            int position = moveto+ N[moveto];
            if(!visit[position]) MakePath(path, position);
            return  path[position]+1;
        }
    };
 
    if(path==NULL){
        path = new int[M];
		fill_n(path, M, MAX_T+1);
    }
 
    visit[from] = true;
    int bestpath = MAX_T;
    if(from==goal)  bestpath = 0;
    else{
        for(int d : dice){
            bestpath = min(bestpath, checkPath(from + d));
            bestpath = min(bestpath, checkPath(from - d));
        }
    }
    path[from] = bestpath;
    return path;
}
 
int main(){
    // 入力
    cin >> M;
    for(int r=0; r<6; r++)   cin >> dice[r];
    cin >> start >> goal;
	start--, goal--;
	N.resize(M);
	for(int m=0; m<M; m++)   cin >> N[m];
	
	// 最短経路の探索
    int* path = MakePath(NULL, start);
     
    // 本番
    int position = start;
    for(int t=0; t<MAX_T; t++){
        if(position == goal) break;
     
        int r;
        cin >> r;
        int d = dice[r-1];
 
        static auto tryMove = [&path](int moveto, int& position)->bool{
			if(isPositionValid(moveto)){
				int new_position = moveto + N[moveto];
                if(path[position] > path[new_position]){
					position = new_position;
					return true;
				}
			}
            return false;
        };
     
		int output;
        if     (tryMove(position + d, position)) output = 1;
		else if(tryMove(position - d, position)) output = -1;
		else output = 0;
		cout << output << endl;
    }
 
    delete[] path;
    return 0;
}

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

int main(){
    int h,w;
    cin>>h>>w;
    char c[h+2][w+2];
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++)cin>>c[i][j];
    }
    bool flag=true;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(c[i][j]=='.')continue;
            else{
                if(c[i][j-1]!='#'&&c[i][j+1]!='#'&&c[i-1][j]!='#'&&c[i+1][j]!='#')flag=false;
            }
        }
    }
    if(flag)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3644
rows = input().split()


ans = []
for i in rows:
    if i == "+":
        a = ans.pop()
        b = ans.pop()
        ans.append(a + b)
    elif i == "-":
        a = ans.pop()
        b = ans.pop()
        ans.append(b - a)
    elif i == "*":
        a = ans.pop()
        b = ans.pop()
        ans.append(a * b)
    else:
        ans.append(int(i))

print(' '.join(map(str, ans)))

Measured memory_bytes: 7692
n=int(input())
t=[[]for i in range(n)]
for i in range(n):
    c=input()
    for j in range(n):
        if c[j]=="1":
            t[i].append(j)
def f(x):
    a=[-1]*n
    a[x],q=1,[[x,1]]
    while q:
        b,c=q.pop(0)
        for i in t[b]:
            if a[i]!=-1:
                if abs(a[i]-c)!=1:
                    return -1
                    break
            else:
                a[i]=c+1
                q.append([i,c+1])
    return max(a)
print(max([f(i)for i in range(n)]))

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


int main() {
    int cost = 0;
    int h,w; cin >> h >> w;
    int a, b; cin >> a >> b;
    int ret = h * w - (w * a) - (h * b) + a * b;
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 256
if isfile("mystdin.txt");mystdin=open("mystdin.txt","r");redirect_stdin(mystdin);end
pI(x)=parse(Int,x)
pM(x::Array{SubString{String},1})=map(pI,x)
function main()
  n=pI(readline())
  s=[chomp(readline()) for i=1:n]
  m=pI(readline())
  t=[chomp(readline()) for i=1:m]
  u=unique(s)
  ans=0
  for i=u
    ans=max(ans,count(x->x==i,s)-count(x->x==i,t))
  end
  println(ans)
end
main()
if isdefined(Base, :mystdin);close(mystdin);end

Measured memory_bytes: 168792
n = int(input())

if n <= 10 ** 9:
    print(0, 0, n, 0, 0, 1)
elif n == 10 ** 18:
    print(0, 0, 10 ** 9, 0, 0, 10 ** 9)
else:
    rest = n % 10 ** 9
    c = 10 ** 9 - rest
    d = 1
    a = (n + 10 ** 9 - rest) // 10 ** 9
    b = 10 ** 9
    print(0, 0, a, c, d, b)



Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>

int main()
{
    int n,q,cnt =0;
    scanf("%d",&n);
    int *S = malloc(sizeof(int)*n);
    for(int i=0;i<n;i++) scanf("%d",&S[i]);
    scanf("%d",&q);
    int *T = malloc(sizeof(int)*q);
    for(int i=0;i<q;i++) scanf("%d",&T[i]);
    for(int i=0;i<q;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(S[j]==T[i])
            {
                cnt ++;
                break;
            }
        }
    }
    printf("%d\n",cnt);
    free(T);
    free(S);
}


Measured memory_bytes: 2056
import java.util.*;
// warm-up
// Good riddance manhattan. No more manhattan new york california please.
public class Main {

	static class Point {
		int x=0, y=0;
		Point (int a, int b) {
			x=a; y=b;
		}
	}

	static void solve() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(), m=sc.nextInt(), t=0, i=0;
		Point[] a = new Point[n];
		Point[] b = new Point[m];
		t=n;
		while (t-->0) a[i++] = new Point(sc.nextInt(), sc.nextInt()); 
		t=m; i=0;
		while (t-->0) b[i++] = new Point(sc.nextInt(), sc.nextInt()); 
		for (Point d : a) {
			int min=Integer.MAX_VALUE, j=0; i=1;
			for (Point c : b) {
				if ((Math.abs(d.x-c.x)+Math.abs(d.y-c.y))<min) {
					min = Math.abs(d.x-c.x)+Math.abs(d.y-c.y);
					j=i;
				}
				i++;
			}
			System.out.println(j);
		}
		sc.close();			
	}

	public static void main(String args[]) {
		solve();
	}

}

Measured memory_bytes: 35892
import sys

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return c // b

def solve():
    input = sys.stdin.readline
    X = int(input())
    L = lcm(360, X)
    print(L // X)

    return 0

if __name__ == "__main__":
    solve()

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

#define task "D"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int mod = 1e9 + 7;
int gt[2002], igt[2002];
int power(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1) res = res * 1LL * x % mod;
        y >>= 1;
        x = x * 1LL * x % mod;
    }
    return res;
}
int C(int k, int n)
{
    return ((gt[n] * 1LL * igt[k] % mod) * igt[n - k]) % mod;
}
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    int S;
    cin >> S;
    gt[0] = 1;
    rep(i, 1, S) gt[i] = gt[i - 1] * 1LL * i % mod;
    igt[S] = power(gt[S], mod - 2);
    Rep(i, S - 1, 0) igt[i] = igt[i + 1] * 1LL * (i + 1) % mod;
    int ans = 0;
    rep(n, 1, S)
    {
        int x = S - 2 * n - 1;
        if (x < n - 1) break;
        (ans += C(n - 1, x)) %= mod;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3652
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

ll MOD = 1e9 + 7;

int main(){
    int N, M;
    cin >> N >> M;
    int s[N], t[M];
    for(int i = 0; i < N; i++) cin >> s[i];
    for(int i = 0; i < M; i++) cin >> t[i];

    vector<vector<ll>> dp(N, vector<ll>(M, 0LL));
    vector<vector<ll>> sum(N + 1, vector<ll>(M + 1, 0LL));

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(s[i] == t[j]){
                dp[i][j] = sum[i][j] + 1;
                dp[i][j] %= MOD;
                sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + dp[i][j] + MOD;
                sum[i + 1][j + 1] %= MOD;
            }
            else{
                dp[i][j] = 0;
                sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + MOD;
                sum[i + 1][j + 1] %= MOD;
            }
        }
    }

    ll ans = 1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            ans += dp[i][j];
            ans %= MOD;
        }
    }

    //debug
    /*
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl;
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= M; j++){
            cout << sum[i][j] << " ";
        }
        cout << endl;
    }
    */

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 62976
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;

int main() {
  int S; cin >> S;
    int D = S%10; S /= 10;
    int C = S%10; S /= 10;
    int B = S%10; S /= 10;
    int A = S%10;  
  
  for (int bit=0; bit<(1<<3); bit++){
    int sum = A;
    char opB = '+', opC ='+', opD ='+';
      if(bit & (1<<0)) sum += B;
      else {opB = '-'; sum -=B;}
      if(bit & (1<<1)) sum += C;
      else {opC = '-'; sum -=C;}
      if(bit & (1<<2)) sum += D;
      else {opD = '-'; sum -=D;}
      
      if(sum == 7) {
        cout << A << opB << B << opC << C << opD << D << "=7" << endl;
        return 0;
      }
  }
  cout << "None" << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n; cin >> n;
  vector<int> a(n);
  int xr = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    xr ^= a[i];
  }
  for (int i = 0; i < n; ++i) {
    cout << (xr^a[i]) << " ";
  }
  cout << endl;

  
  return 0;
}




Measured memory_bytes: 3964
n,m = map(int,input().split())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
for i in edge[1]:
    if n in edge[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


Measured memory_bytes: 80844
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Sep 13 18:35:58 JST 2020
 **/


#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder


signed main() {
    Int n, Q;
    std::cin >> n >> Q;
    atcoder::dsu uf(n);
    REP(q, Q) {
        Int t, u, v;
        std::cin >> t >> u >> v;
        if (t == 0) {
            uf.merge(u, v);
        } else {
            std::cout << uf.same(u, v) << "\n";
        }
    }
}


Measured memory_bytes: 3892
import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		String[] ar = new String[n];
		for (int i=0; i<n; i++) {
			ar[i] = sc.next();
		}
		String[] ar2 = new String[n];
		for (int i=0; i<n; i++) {
			ar2[i] = ar[i];
		}
		
		
		ar = bubbleSort(ar);
		ar2 = selectionSort(ar2);
		
		
		for (int i=0; i<n; i++) {
			out.print((i==0?"":" ")+ar[i]);
		}
		out.println();
		out.println("Stable");
		boolean F = true;
		for (int i=0; i<n; i++) {
			if (ar[i].equals(ar2[i])==false) {F=false; break;}
		}
		for (int i=0; i<n; i++) {
			out.print((i==0?"":" ")+ar2[i]);
		}
		out.println();
		out.println(F==true?"Stable":"Not stable");
	}
	
	static String[] bubbleSort (String[] ar) {
		boolean F = true;
		int j = 0;
		String temp;
		while (F==true) {
			F = false;
			for (int i=ar.length-1; i>=j+1; i--) {
				if (Character.getNumericValue(ar[i].charAt(1)) < Character.getNumericValue(ar[i-1].charAt(1))) {
					temp = ar[i];
					ar[i] = ar[i-1];
					ar[i-1] = temp;
					F = true;
				}
			}
			j++;
		}
		return ar;
	}
	
	static String[] selectionSort (String[] ar) {
		int min;
		String temp;
		for (int i=0; i<ar.length-1; i++) {
			min = i;
			for (int j=i; j<ar.length; j++) {
				if (Character.getNumericValue(ar[j].charAt(1)) < Character.getNumericValue(ar[min].charAt(1))) {
					min = j;
				}
			}
			temp = ar[i];
			ar[i] = ar[min];
			ar[min] = temp;
		}
		return ar;
	}
}



Measured memory_bytes: 26476
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,m,n;
    string s;
    cin>>s;
    if(s[2]==s[3]&&s[4]==s[5])
    {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }

int main() {
  ll A, B; cin >> A >> B;
  ll result = A*B/gcd(A,B);
  cout << result << endl;
  return 0;
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

vector<ll> div(ll n)
{
    vector<ll> ret;
    for (ll i = 1; i*i <= n; i++)
    {
        if(n%i==0)
        {
            ret.push_back(i);
            if(i*i!=n)
			{
				ret.push_back(n/i);
			}
        }
    }
    return ret;
}

int main()
{
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n);
    ll sum=0;
    ll ans=1;
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sort(all(a));
    if(k>=(sum-a[n-1]))
    {
        //ans=sum;
    }
    auto yakusuu = div(sum);
    sort(all(yakusuu));
    reverse(all(yakusuu));
    
    for (int ii = 0; ii < yakusuu.size(); ii++)
    {
        ll d = yakusuu[ii];
        //cout<<d<<endl;//

        vector<pll> v(n);
        for (int i = 0; i < n; i++)
        {
            ll mod = a[i]%d;
            v[i]=make_pair((d-mod)%d, mod);
        }
        sort(all(v));
        ll mae=0, usiro=n-1;
        ll plus=0, minus=0;
        while (mae<=usiro)
        {
            if(plus<=minus)
            {
                plus+=v[mae].first;
                mae++;
            }
            else
            {
                minus+=v[usiro].second;
                usiro--;
            }
        }
        if(plus==minus && plus<=k)
        {
            ans=d;
            break;
        }
        
    }
    
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    A = set(LIN(M))
    #print(A)
    dp = [0] * (N + 1)
    dp[0]=1
    if 1 not in A:
        dp[1] = 1
    
    for i in range(2,N+1):
        if i in A:
            continue
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i]%=mod
    print(dp[-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 51036
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
char s[maxn];
int t,len,l,r;
int main()
{
scanf("%s",s+1);
len=strlen(s+1);
t=0x3f3f3f3f;
   for(int i=1;i<len;++i)
   if(s[i]!=s[i+1]) t=min(t,max(len-i,i));
   if(t==0x3f3f3f3f)
   cout<<len<<endl;
   else 
   cout<<t<<endl; 
 return 0;
 }

Measured memory_bytes: 384