akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define rep(i, a) for (int (i) = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int (i) = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int (i) = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int (i) = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__ "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a;
#define lcoutln(a) cout << a << endl;
#define lcerr(a) cerr << a;
#define lcerrln(a) cerr << a << endl;
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif

#define INF 1e9

int t[16][16];
int t0[16];
int dp[1 << 16];

int v2n(vector<int> v)
{
	int x = 1;
	int res = 0;
	rep(i, v.size()) {
		res += x * v[i];
		x <<= 1;
	}
	return res;
}

int main()
{
	int N;
	cin >> N;
	while (N) {
		rep(i, 1 << N) dp[i] = INF;
		rep(i, N) {
			cin >> t0[i];
			rep(j, N) cin >> t[i][j];
		}
		dp[0] = 0;
		vector<int> v;
		rep(i, N) v.PB(0);
		rep(i, N) {
			do {
				int state = v2n(v);
				int mask = 1;
				int T[16];
				rep(j, N) T[j] = t0[j];
				rep(j, N) {
					if (mask & state) {
						rep(k, N) {
							T[k] = min(T[k], t[k][j]);
						}
					}
					mask <<= 1;
				}

				mask = 1;
				rep(j, N) {
					if ((mask & state) == 0) {
						dp[state+mask] = min(dp[state+mask], dp[state] + T[j]);
					}
					mask <<= 1;
				}
			} while (PERM(v));
			v[N-i-1] = 1;
		}
		cout << dp[(1 << N)-1] << endl;
		cin >> N;
	}
}



Measured memory_bytes: 3324
#include<bits/stdc++.h>
#define sag (root+root+1)
#define sol (root+root)
#define ort  ((bas+son)/2)
#define mod 1000000007

using namespace std;
typedef long long ll;




int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
    int n, r;
    cin >> n >> r;
    if(n>=10)
        cout << r;
    else{
        cout << r+(100*(10-n));
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a[1000],b[1000],leng=0;
int f(){
	int i,j;
	for(i=1;i<=leng;i++)
	if(b[a[i]]>0)return 1;
	return 0;
}
int main(){
	int i,j,l;
	long long k,n,m;
	cin>>k>>n;
	for(i=1;i<=n;i++)cin>>l,b[l]++;
	m=k;
	while(m>0){
		a[++leng]=m%10;
		m/=10;
	}
	while(f()){
		int s1=f();
		a[s1]++;
		k++;
		while(a[s1]>=10)a[s1]=0,s1++,a[s1]++;
		leng=max(leng,s1);
	}
	cout<<k<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<unistd.h>
#include <array>
#include <map> 
#define ALL(a)  (a).begin(),(a).end()



using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int a, int b)
{
	return a == 0 ? b : gcd(b % a, a);
}
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}

struct File {
    int aa;
    int bb;

    File(const int& aa, const int& bb)
        : aa(aa), bb(bb) {}
};

bool operator<(const File& a, const File& b)
{
    // ファイル種別、ファイル名の順番で優先順位を付けて比較
    return std::tie(a.aa, a.bb) < std::tie(b.aa, b.bb);
}

long long kaijo(long long x){
  long long l=10*10*10*10*10*10*10*10*10+7;
  long long sum=1;
  for(int i=x;i>0;i--){
    sum*=i;
    if(sum>l){
      sum%=l;
    }
  }
  return sum;
}






int main(){
  int N;
  cin>>N;
  long long A[3*N];

  for(int i=0;i<3*N;i++){
    cin>>A[i];

  }
  sort(A,A+3*N);
  long long sum=0;
  int x=0;
  for(int i=3*N-2;x<N;i-=2){
    sum+=A[i];
    x++;

  }
  cout<<sum<<endl;
}




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

#define mp(x, y) make_pair((x), (y))

typedef long long ll;

int n;
char s[100005];
int ans[100005];

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

	for(int m=0; m<4; m++) {
		ans[0]=(m&1);
		ans[1]=((m>>1)&1);
		for(int i=1; i<n-1; i++) {
			if(ans[i]==0) {
				if(s[i]=='o') ans[i+1]=ans[i-1];
				else ans[i+1]=1-ans[i-1];
			} else {
				if(s[i]=='x') ans[i+1]=ans[i-1];
				else ans[i+1]=1-ans[i-1];
			}
		}
			if(ans[0]==0) {
				if(s[0]=='o') {
					if(ans[1]!=ans[n-1]) continue;
				}
				else {
					if(ans[1]==ans[n-1]) continue;
				}
			} else {
				if(s[0]=='x') {
					if(ans[1]!=ans[n-1]) continue;
				}
				else {
					if(ans[1]==ans[n-1]) continue;
				}
			}
			if(ans[n-1]==0) {
				if(s[n-1]=='o') {
					if(ans[0]!=ans[n-2]) continue;
				}
				else {
					if(ans[0]==ans[n-2]) continue;
				}
			} else {
				if(s[n-1]=='x') {
					if(ans[0]!=ans[n-2]) continue;
				}
				else {
					if(ans[0]==ans[n-2]) continue;
				}
			}
		for(int i=0; i<n; i++) {
			if(ans[i]==0) printf("S");
			else printf("W");
		}
		printf("\n");
		return 0;
	}
	printf("-1\n");

	return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
long long v[200005];
long long _abs(long long val)
{
	if(val >= 0)
		return val;
	return -val;
}
int main()
{
	int n;
	scanf("%d",&n);
	long long ma = 0;

	int pos = 0;
	for(int i = 0 ; i < n; i++)
	{
		scanf("%lld",&v[i]);
		if(ma < v[i])
		{
			ma = v[i];
			pos = i;
		}
	}
	long long val = ma/2;
	long long mi = (1LL << 50);
	int ans = 0;
	for(int i = 0 ; i < n ; i++)
	{
		if(i != pos  && _abs(v[i] - val) < mi)
		{
			mi = _abs(v[i] - val);
			ans = i;
		}
	}
	printf("%lld %lld\n",ma,v[ans]);
	return 0;
}


Measured memory_bytes: 1024
using System;
class Program
{
    public static void Main()
    {
        char[] o = Console.ReadLine().ToCharArray();
        char[] e = Console.ReadLine().ToCharArray();
        int i = 0;
        for (; ; )
        {
            try
            {
                Console.Write(o[i]);
            }
            catch (IndexOutOfRangeException)
            {
                break;
            }
            try
            {
                Console.Write(e[i]);
            }
            catch (IndexOutOfRangeException)
            {
                break;
            }
            i++;
        }
        Console.WriteLine();
    }
}

Measured memory_bytes: 13140
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
const ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;
pq que;

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

  cin >> n >> m;
  rep(i, n) {
    cin >> a;
    que.push(a);
  }
  rep(i, m) {
    tmp = que.top();
    que.pop();
    tmp /= 2;
    que.push(tmp);
  }
  while (1) {
    if (que.empty()) break;
    tmp = que.top();
    que.pop();
    ans += tmp;
  }
  Cout(ans);
  return 0;
}

Measured memory_bytes: 1400
def resolve():
  a = list(map(int, input().split()))
  a.sort()
  ans = 0
  while a[1] < a[2]:
    ans += 1
    a[1] += 1
    a[0] += 1

  while a[0] < a[2]:
    ans += 1
    a[0] += 2

  if a[0] != a[1]:
    ans += 1

  print(ans)
  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 3064
//浮動小数点数として掛け算を行うと精度が足りません。
//B を 100 倍して、 (A × (B × 100))/100とすることで、整数の範囲で誤差なく計算することができます。

//64bit整数は、64bit分整数の情報が詰め込まれてるんだけど、
//double型などの倍精度浮動小数点数だと、符号に1bit、指数を表すのに11bitで、
//整数情報は残りの52bitしか残されない。なのでこの問題の答えを正確に計算できない
//////→いわゆる丸め誤差？近似値を用いるしかなくなって切り捨てられたりしちゃう誤差？
//////→double型でも精度はせいぜい15桁程度であり、上述の通り整数との計算でも容易に誤差が起こる
//////→だから浮動小数点数同士のイコール比較もNG(初心者どハマリポイント)

//Bを100倍する際にも誤差が発生する場合があるので注意！
//.で切り分けて整数演算するか、微小な数を足して切り捨てるかの2択でうまく行きます。

#include<iostream>
#include<cfloat> //微小な数のためにDBL_EPSILON使おうとしたけど使ったらWAだった
using namespace std;

int main(){
	long long a,ans;
    double b;
    cin >> a;
    cin >> b;
    
    //Bを100倍する際に微小な数を足して切り捨ててもらう
    //DBL_EPSILONだとテストケース1問だけWAしたんだけど！！！！！あまりにも微小過ぎるから？
    ans = (a * (long long)(b * 100.0 + 0.001)) / 100;
    
    cout << ans << endl;
}

Measured memory_bytes: 3720
#include<stdio.h>
int main(void)
{
  int num,count=0;
  scanf("%d",&num);
  int i, t[num], x[num], y[num],dt,dx,dy;
  for(i=0; i<num; i++)
  {
    scanf("%d%d%d", &t[i],&x[i],&y[i]);
  }
  dt=t[0];
  dx=x[0];
  dy=y[0];
  if(dx<0) dx=-dx;
  if(dy<0) dy=-dy;
  if(dx+dy>dt || (dt-(dx+dy))%2==1) count=1;
  for(i=1; i<num; i++)
  {
    dt=t[i]-t[i-1];
    dx=x[i]-x[i-1];
    dy=y[i]-y[i-1];
    if(dx<0) dx=-dx;
    if(dy<0) dy=-dy;
    if(dx+dy>dt || (dt-(dx+dy))%2==1) count=1;
  }
  if(count==0) printf("Yes");
  else printf("No");
  return 0;
}

Measured memory_bytes: 1280
#include <stdio.h>
#include <string.h>
#include <math.h>

int main () {
	char buff[64];
	int n;
	int result;
	
	while (fgets (buff, 64, stdin)) {
		sscanf (buff, "%d", &n);

		result = 0;
		for (int a = 0; a < 10; a++) {
			for (int b = 0; b < 10; b++) {
				for (int c = 0; c < 10; c++) {
					for (int d = 0; d < 10; d++) {
						if ((a + b + c + d) == n) {
							result++;
						}
					}
				}
			}
		}
		printf ("%d\n", result);
	}
	
	return 0;
}



Measured memory_bytes: 2036
using System;
using System.Collections.Generic;
class Program
{

    static void Main()
    {
        string N = Console.ReadLine();
        int n = int.Parse(N);
        string[] a = Console.ReadLine().Split(' ');
        int j = 0;
        int count = 0;
        for(int i=1;i<=n;i++)
        {
            j = int.Parse(a[i-1]);
            if(i%2==1&&j%2==1)
            {
                count++;
            }
        }
        Console.WriteLine(count);
    }

}

Measured memory_bytes: 27324
import itertools

# 入力
n, m, q = (int(each) for each in input().split())
a = []
for each in range(q):
    a.append([int(each) for each in input().split()])

# Aのリストを生成する
l = [i+1 for i in range(m)]
p = itertools.combinations_with_replacement(l, n)
p = set([tuple(sorted(list(v))) for v in p])

# print(p)
# Aのリストそれぞれについて、スコアを計算する
scorelist = []
for eachA in p:
    score = 0
    for linei in a:
        # print('eachA', eachA)
        # print('linei', linei)
        if eachA[linei[1]-1] - eachA[linei[0]-1] == linei[2]:
            score += linei[3]
    scorelist.append(score)

print(max(scorelist))

Measured memory_bytes: 28616
var
	now,cnt,N,M,i,j,k,s:Longint;
	A:array[1..10,1..10]of Boolean;
	P:array[1..10]of Longint;
	flag:Boolean;
begin
	read(N,M);
	for i:=1 to M do begin
		read(k);
		for j:=1 to k do begin
			read(s);
			A[i,s]:=True;
		end;
	end;
	for i:=1 to M do begin
		read(P[i]);
	end;
	for i:=0 to (1<<N)-1 do begin
		flag:=True;
		for j:=1 to M do begin
			now:=0;
			for k:=1 to N do begin
				if((i>>(k-1))mod 2=1)and A[j,k]then inc(now);
			end;
			if now mod 2<>P[j]mod 2 then begin
				flag:=False;
				break;
			end;
		end;
		if flag then inc(cnt);
	end;
	writeln(cnt);
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d, left, right;
  cin >> a >> b >> c >> d;
  
  left = a + b;
  right = c + d;
  if (left > right)
    cout << "Left" << endl;
  else if (left == right)
    cout << "Balanced" << endl;
  else if (left < right)
    cout << "Right" << endl;
  else
    cout << "Error" << endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) cout<<(#x)<<":"<<x<<endl

int n,m;
int mp[252][252];
int dst[252][3];
const int INF = 830252521;

struct State{
  int dist;
  int pos;
  int layer;
  State():dist(0),pos(0),layer(0){}
  State(int dist,int pos,int layer):dist(dist),pos(pos),layer(layer){}
};
bool operator<(const State &a, const State &b){
  if(a.dist != b.dist) return a.dist>b.dist;
  if(a.layer != b.layer) return a.layer>b.layer;
  return a.pos<b.pos;
}

void solve(){
  REP(i,n)REP(j,n)mp[i][j] = INF;
  REP(i,n)REP(j,3)dst[i][j] = INF;
  REP(i,m){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    --a;--b;
    mp[a][b] = min(mp[a][b],c);
    mp[b][a] = min(mp[b][a],c);
  }
  priority_queue<State> Q;
  Q.push(State(0,0,0));
  dst[0][0] = 0;
  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    int d,p,l;
    d = s.dist;
    p = s.pos;
    l = s.layer;
    if(l!=1 && p==n-1){
      printf("%d\n",d);
      return;
    }
    REP(to,n){
      if(mp[p][to]==INF)continue;
      if(l==0 || l==1){
        if(dst[to][l+1] > dst[p][l]){
          dst[to][l+1] = dst[p][l];
          Q.push(State(dst[p][l],to,l+1));
        }
      }
      if(l==0 || l==2){
        if(dst[to][l] > dst[p][l]+mp[p][to]){
          dst[to][l] = dst[p][l]+mp[p][to];
          Q.push(State(dst[p][l]+mp[p][to],to,l));
        }
      }
    }
  }
}

int main(){
  while(true){
    scanf("%d%d",&n,&m);
    if(n==0 && m==0)break;
    solve();
  }
  return 0;
}

Measured memory_bytes: 1296
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var abk = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			int a = abk[0];
			int b = abk[1];
			int k = abk[2];

			var nums = new List<int>();
			int temp = Math.Min(a + k - 1, b);
			for (int i = a; i <= temp; i++) {
				nums.Add(i);
			}

			temp = Math.Max(b - k + 1, temp + 1);
			for (int i = temp; i <= b; i++) {
				nums.Add(i);
			}

			var sb = new StringBuilder();
			foreach (int n in nums) {
				sb.AppendLine(n.ToString());
			}

			Console.Write(sb.ToString());
		}
	}
}

Measured memory_bytes: 13396
#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

ll n;			
vector<string> s;
vector<PLL> vp;

PLL calc(string ss){
    ll lef = 0,rig = 0;
    rep(i,ss.size()){
        if(ss[i]=='('){
            lef++;
        }else{
            if(lef!=0)lef--;
            else rig++;
        }
    }
    return mp(lef-rig,rig);
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    cin>>n;
    s.resize(n);
	ll sum = 0;
    rep(i,n){
        cin>>s[i];
		vp.pb(calc(s[i]));
		sum += vp[i].first;
    }
	if(sum!=0){
		print("No");
		return 0;
	}
	Sort(vp);
	vector<PLL> v1,v2;
	rep(i,vp.size()){
		if(vp[i].first>=0)v1.emplace_back(vp[i].second,vp[i].first);
		else v2.emplace_back(vp[i].first+vp[i].second,vp[i].second);
	}
	ll lef = 0;
	sort(all(v1));
	Sort(v2);
	bool ans = true;
	rep(i,v1.size()){
		if(lef < v1[i].first){cout<<"No"<<endl; return 0;}
		else{
			lef += v1[i].second;
		}
	}
	rep(i,v2.size()){
		if(lef < v2[i].second){cout<<"No"<<endl; return 0;}
		else{
			lef += v2[i].first - v2[i].second;
		}
	}
	Yes(lef==0 && ans);
    return 0;
}

Measured memory_bytes: 73768
n=int(input())
red=[[] for i in range(n)]
blue=[[] for i in range(n)]
for i in range(n):
    a,b=map(int,input().split())
    red[i].append(a)
    red[i].append(b)
for i in range(n):
    a,b=map(int,input().split())
    blue[i].append(a)
    blue[i].append(b)
red=sorted(red)
blue=sorted(blue)
ans=0
for i in range(n):
    x=blue[i][0]
    y=blue[i][1]
    maxy=-1
    for j in range(n):
        if x>red[j][0] and y>red[j][1]:
            maxy=max(maxy,red[j][1])
    for j in range(n):
        if x>red[j][0] and maxy==red[j][1]:
            ans+=1
            red[j][0]=1000
            break
print(ans)


Measured memory_bytes: 68968
#include <iostream>
#include<vector>
#include<algorithm>

const int MAXN=1e6+11;

using namespace std;

void print_vector(const vector<int> v){
	for(auto x=v.cbegin(); x!=v.cend(); ++x)
		cout<<*x<<' ';
	cout<<endl;
}


void deduct(vector<int>& v, int val){
	vector<int> _v;
	//deduct
	for(auto x=v.begin(); x!=v.end(); ++x){
		*x-=val;
		// _v.push_back(*x-min_v)
	}
	// print_vector(v);
	// return _v;
}


int compute(vector<int> v){
	if(v.size()==0)
		return 0;
	int steps=0;
	int min_v=*min_element(v.begin(), v.end());
	steps+=min_v;
	deduct(v, min_v);

	std::vector<int> _v;
	for(auto x=v.cbegin(); x!=v.cend(); ++x){
		if(*x==0){
			steps+=compute(_v);
			_v.clear();
		}
		else
			_v.push_back(*x);
	}
	steps+=compute(_v);
	return steps;
}

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	vector<int> v;
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin>>x;
		v.push_back(x);
	}
	cout<<compute(v)<<endl;
	return 0;
}

Measured memory_bytes: 256
object Main extends App {
	val n = scala.io.StdIn.readInt
	var a = scala.io.StdIn.readLine.split(" ").map(_.toLong)

	for(i<-0 until n){
		a(i) -= i.toLong + 1L
	}

//	println(a.mkString(" "))

	a = a.sorted

	var ans = 0L

	val t = n/2

	if(n%2 == 1){
		val b = a(t)

		for(x<-a){
			ans += math.abs(x - b)
		}
		println(ans)

	}else{
		val b1 = a(t)
		val b2 = a(t-1)

		var ans1 = 0L

		for(x<-a){
			ans += math.abs(x - b1)
			ans1 += math.abs(x - b2)
		}
		println(math.min(ans, ans1))
	}
}


Measured memory_bytes: 58844
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
    char s[10];
    char t[10];
    char u[10];
    int a,b;
    scanf("%s %s",s,t);
    scanf("%d %d",&a,&b);
    scanf("%s",u);

    if(strcmp(u,s)==0){
        printf("%d %d",a-1,b);
    }else{
        printf("%d %d",a,b-1);
    }

    return 0;
}

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

public class S
{

    private const long DP_INIT_MINUS1 = -1;
    private const double DP_INIT_DOUBLE_MINUS1 = -1.0;
	private const long MOD = 1000000007;


    //s
    private const int FIRST_WIN = 1;
    private const int SECOND_WIN = 0;

    private static long[,] dp;
    private static long[] cSum;


    public static void Main()
	{
		/*
        var input = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        var N = input[0];
        var M = input[1];
        */

        var input = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        var N = input[0];
        var K = input[1];

        solver(int.Parse(N.ToString()),K,Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse));
    }

    public static void solver(int N, long K, int[] A){

        long count = 0;
        long selfCount = 0;
        long beforeCount = 0;

        long beforeMultiplier;

        int[] x = new int[2001];

        for(int i = 0; i < N; i++){
            selfCount += x[A[i]];
            for(int k = A[i]-1; k >= 1; k--){
                x[k]++;
            }
        }

        for(int i = 0; i < N; i++){
            beforeCount += x[A[i]];
        }

        count += selfCount * K;
        count %= MOD;

        if(K % 2 == 0){
            beforeMultiplier = K / 2;
            beforeMultiplier += (beforeMultiplier-1) * K;
        }else{
            beforeMultiplier = (K/2) * K;
        }

        beforeMultiplier %= MOD;

        //ここでlongが飛んでた
        count += beforeCount * beforeMultiplier;
        count %= MOD;


        // 自分自身で発生させる物と、後ろにあるならその数発生する物がある
        // 前者は固定で、全体数は*Kで求まる。後者は*1~k-1で求まる。

        Console.WriteLine(count % MOD);



    }

}

Measured memory_bytes: 13272
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
#define n_max 10000
#define INF 10001000

#define rep(i, a, n) for(int i = a; i < n; i++)
#define rep2(i, a, n) for(int i = a; i <= n; i++)
#define rrep(i, a, n) for(int i = a; i > n; i--)
#define rrep2(i, a, n) for(int i = a; i >= n; i--)
#define lrep(i, a, n) for(long int i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl
typedef long long ll;

int main()
{
    int N, L;

    cin >> N >> L;

    if(L>0) { cout << L*(N-1) + N*(N-1)/2 << endl; }
    else    { cout << L*(N-1) + N*(N-1)/2 - min(-L,N-1)<< endl; }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  string s;
  cin >> s;
  cout << string(s.size(), 'x') << endl;
  return 0;
}

Measured memory_bytes: 3636
i = int(input())
score = [input().split() for s in range(i)]
s_list = sorted(score)

for i in range(len(s_list)):
  for j in reversed(range(i+1, len(s_list))):
    if s_list[j-1][0] == s_list[j][0] and int(s_list[j-1][1]) < int(s_list[j][1]):
      s_list[j-1], s_list[j] = s_list[j], s_list[j-1]

for s in s_list:
  for index,sc in enumerate(score):
    if s == sc:
      print(index+1)

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

using namespace std;

int n, k, x;
bool dd[20];

bool check(int x){
    while (x){
        int dig = x % 10;
        if (dd[dig]) return false;
        x /= 10;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= k; i++){
        cin >> x;
        dd[x] = true;
    }
    while (!check(n))
        n++;
    cout << n;
}


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

using ll = int64_t;

template<ll MOD=ll(1e9+7)>
ll mod_pow(ll n,ll p){
  ll ans=1LL;
  while(p){
    if(p&1)ans*=n;
    n*=n;
    p>>=1;
    ans%=MOD;
    n%=MOD;
  }
  return ans;
}


signed main(){

  ll n,k;
  cin>>n>>k;
  cout<<mod_pow(k,n)<<endl;

}


Measured memory_bytes: 3112
<?php
function c($s, $o = null) {
    while (substr_count($s, "()"))
        $s = str_replace("()", "", $s);
    if (is_null($o))
        return strlen($s) === 0 ? true : false;
    return $s;
}
$l = [];
while ($r = trim(fgets(STDIN)))
    $l[] = $r;
$a = substr_count($l[1], "(");
$b = substr_count($l[1], ")");
$c = str_repeat(")", substr_count(c($l[1], "a"), "("));
$d = str_repeat("(", substr_count(c($l[1], "a"), ")"));
$e = ($d . $l[1] . $c);
echo $a > $b ? $e : ($a === $b ? (c($l[1]) ? $l[1] : $e) : $e);

Measured memory_bytes: 4604
n = int(input())
a = list(map(int, input().split()))

b = a[:]

dig_m = 30
cnt_dig = [1]*30
for i in range(dig_m):
    cnt = 0
    for j in range(n):
        if b[j] % 2 == 0:
            cnt += 1
        b[j] //= 2
    if cnt % 2 == 0:
        cnt_dig[i] = 0
cnt_dig.reverse()
cnt_dig = int(''.join(map(str, cnt_dig)), 2)

for i in range(n):
    print(a[i] ^ cnt_dig, end=' ')

Measured memory_bytes: 93764
n, m = map(int, input().split())

if n == 1and m != 1:
    print(n * (m - 2))
elif n != 1 and m == 1:
    print((n - 2) * m)
elif n == 1 and m == 1:
    print(n * m)
else:
    print((n - 2) * (m - 2))

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>
#include <iterator>

typedef long long ll;
typedef unsigned long long ull;
constexpr ll mop = 1000000007;
constexpr ll mop2 = 998244353;

using namespace std;


int main() {
	ll n;
	cin >> n;
	vector<vector<ll>> v(n);

	for (ll i = 0; i < n; i++) {
		ll a;
		cin >> a;
		v[i].resize(32, 0);
		ll p = 0;
		while (a > 0) {
			v[i][p] = a % 2;
			p++;
			a /= 2;
		}
	}
	vector<ll> sum(32);
	for (ll i = 0; i < 32; i++) {
		ll tmp = 0;
		for (ll j = 0; j < n; j++) {
			tmp += v[j][i];
		}
		sum[i] = tmp % 2;
	}
	for (ll i = 0; i < n; i++) {
		ll ans = 0;
		ll pow = 1;
		for (ll j = 0; j < 32; j++) {
			ans += pow * (sum[j] ^ v[i][j]);
			pow *= 2;
		}
		cout << ans << endl;
	}
	
}


Measured memory_bytes: 61072
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
int main()
{
	int h, w; cin>>h>>w;
	string a[1000];
	for(int i=0; i<h; i++) cin>>a[i];
	ll dp[1000][1000]={};
	dp[0][0]=1;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(a[i][j]=='#') continue;
			if(i+1<h && a[i+1][j]!='#'){
				dp[i+1][j]+=dp[i][j];
				dp[i+1][j]%=MOD;
			}
			if(j+1<w && a[i][j+1]!='#'){
				dp[i][j+1]+=dp[i][j];
				dp[i][j+1]%=MOD;
			}
		}
	}
	cout<<dp[h-1][w-1]<<endl;
	return 0;
}

Measured memory_bytes: 9088
N, A, B = gets.chomp.split(" ").map(&:to_i)

ans = 0
(1..N).each{|n|
  wk = 0
  tmp = n
  while tmp > 0 do
    dm = tmp.divmod(10)
    wk += dm[1]
    tmp = dm[0]
  end
  ans += n if A <= wk && wk <= B
}

puts ans


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	string s;
	cin >> s;
	int n = s.size(), i, j, k;
	for (i = 0; i < 26; i++) {
		vi dp(n + 1,0);
		for (j = 0; j < n; j++) {
			if (s[j] == 'a' + i) {
				dp[j + 1] = dp[j] + 1;
			}
			else {
				dp[j + 1] = dp[j];
			}
		}
		for (j = 2; j <= n; j++) {
			k = max(0,j - 3);
			if ((dp[j] - dp[k]) * 2 > j - k) {
				cout << k + 1 << " " << j << endl;
				return 0;
			}
		}
	}
	cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    vector<long long> yoyo(n);
    for(int i=0;i<n;i++){
        cin>>yoyo[i];
    }
    vector<long long> dp(n,0);
    for(int i=1;i<n;i++){
        dp[i]=LLONG_MAX;
        for(int j=max(i-2,0);j<i;j++){
            dp[i]=min(dp[i],abs(yoyo[i]-yoyo[j])+dp[j]);
        }
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1792
/*
❤️❤️❤️I_love_QMsh❤️❤️❤️
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define x first
#define y second

using namespace std;
using namespace __gnu_pbds; // gp_hash_table<int, int> table;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // <int> .find_by_order(int) .order_of_key(int)

template<typename T> bool smin(T &a, const T &b) { bool ret = b < a; return a = (ret ? b : a), ret; }
template<typename T> bool smax(T &a, const T &b) { bool ret = a < b; return a = (ret ? b : a), ret; }

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

mt19937 rnd;

const int N = 52;

ll dp[N * N][N];

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, a;
  cin >> n >> a;
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    for (int l = n - 1; l >= 0; l--) {
      for (int sum = N * N - 1; sum >= 0; sum--) {
        if (dp[sum][l]) {
          dp[sum + x][l + 1] += dp[sum][l];
        }
      }
    }
  }
  ll ans = 0;
  for (int l = 1; l <= n; l++) {
    ans += dp[l * a][l];
  }
  cout << ans;

  return 0;
}

Measured memory_bytes: 4092
import java.io.*;
   
class Main{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int count=0;
        int a=1,b;
        if(x>=3 && x<=10000){
            for(; count<x; count++){
                 b = a/10;
                    if(a%3==0){
                        sb.append(" ");
                        sb.append(a);
                    }else{
                        b = a;
                        while(b!=0){
                            if(b%10==3){
                                sb.append(" ");
                                sb.append(a);
                                break;
                            }
                            b /= 10;
                        }
                    }
                    a++;
            }
        }
        System.out.println(sb);
    }
}

Measured memory_bytes: 25284
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
using ll = long long;
int main()
{
	int n;
	scanf("%d", &n);
	vector<ll> a(n);
	rep(i, n) scanf("%lld", &a[i]);

	//累積和 n + 1なのは 累積和の図を思い出すこと
	vector<ll> s(n + 1, 0);
	rep(i, n) s[i + 1] = s[i] + a[i]; //累積和公式
	// rep(i, n + 1) cout << s[i] << endl;

	map<ll, ll> nums; //sの中にどの数字が何個あるか連想配列で確認
	rep(i, n + 1) nums[s[i]]++;
	// for (auto i : nums) cout << i.first << " " << i.second << endl;

	// 集計処理
	ll ans = 0;
	for (auto i : nums) //nums分繰り返す
	{
		ll num = i.second; //numに特定の数字(nums = i)が何個あったか入れる
		ans += num * (num - 1) / 2; //累積和の始点と終点の2点が何通り作れるかansに追加してく
	}
	printf("%lld\n", ans);
	return 0;
}

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

const double PI = acos(-1.0);

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);	
	double r;
	cin >> r;
	cout << setprecision(10) << fixed << 2*PI*r << endl;
	return 0;
} 

Measured memory_bytes: 3800
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i]; 
    sort(a.begin(), a.end());

    ll la = 0, lb = 0;
    ll tmp = a.back();
    a.pop_back();
    for(int i = n-2; i >= 0; i--) {
        if (tmp == a.back() && la == 0) {
            la = a.back();
            tmp = 0;
        }
        else if (tmp == a.back() && lb == 0){
            lb = a.back();
            break;
        }
        else {
            tmp = a.back();
        }
        a.pop_back();
    }
    cout << la * lb << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int x;
  cin >> x;
  cout << x*x << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define mem(a) memset(a,0,sizeof(a))
#define pd(a) printf("%.10f\n",a)
#define pb(a) push_back(a)
#define in(a) insert(a)
#define pi M_PI
#define R cin>>
#define F first
#define S second
#define C class
#define ll long long
#define ln cout<<'\n'
#define _(_1,_2,_3,N,...)N
#define pr(...) _(__VA_ARGS__,pr3,pr2,pr1)(__VA_ARGS__)
template<C T>void pr1(T a){cout<<a;ln;}
template<C T,C T2>void pr2(T a,T2 b){cout<<a<<' '<<b;ln;}
template<C T,C T2,C T3>void pr3(T a,T2 b,T3 c){cout<<a<<' '<<b<<' '<<c;ln;}
template<C T>void PR(T a,int n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

ll n,m;
ll lcm(ll x, ll y) {
  long double d=(long double)x/__gcd(x,y)*y;
  if(d>m) return 0;
  return d;
}
void Main() {
  cin >> n >> m;
  ll a[n];
  double p[n];
  rep(i,n) R a[i];
  rep(i,n) {
    R p[i];
    p[i]/=100;
  }
  double ans=0;
  REP(t,1,1<<n) {
    double q=1;
    ll x=1;
    rep(i,n) {
      if(t&(1<<i)) {
        q*=p[i];
        x=lcm(x,a[i]);
      }
    }
    if(x) {
      double d=q*(m/x);
      if(__builtin_popcount(t)%2) ans+=d;
      else ans-=d;
    }
  }
  pd(ans);
}

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


Measured memory_bytes: 1276
unittest
{
	assert( [ "3 3 10", "60 2 2 4", "70 8 7 9", "50 2 3 9" ].parse.expand.solve == 120 );
	assert( [ "3 3 10", "100 3 1 4", "100 1 5 9", "100 2 6 5" ].parse.expand.solve == -1 );
	assert( [ "8 5 22", "100 3 7 5 3 1", "164 4 5 2 7 8", "334 7 2 7 2 9", "234 4 7 2 8 2", "541 5 4 3 3 6", "235 4 8 6 9 7", "394 3 6 1 6 2", "872 8 4 3 7 2" ].parse.expand.solve == 1067 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nmx = input.front.split.to!( long[] );
	auto cs = new long[ nmx[ 0 ] ];
	auto ass = new long[][]( nmx[ 0 ], nmx[ 1 ] );
	foreach( ref c, ref as; lockstep( cs, ass ) )
	{
		input.popFront;
		auto cas = input.front.split.to!( long[] );
		c = cas[ 0 ];
		as = cas[ 1 .. $ ];
	}
	return tuple( nmx[ 2 ], cs, ass );
}

auto solve( long x, long[] cs, long[][] ass )
{
	auto ans = long.max;
	foreach( b; 1L .. 1L << cs.length )
	{
		auto ct = 0L;
		auto ats = new long[ ass[ 0 ].length ];
		foreach( i, c; cs )
		{
			if( ( b & ( 1L << i ) ) == 0 ) continue;
			
			ct += c;
			ats[] += ass[ i ][];
		}
		if( ats.find!( ( a, b ) => a < b )( x ).empty ) ans = min( ans, ct );
	}
	return ( ans == long.max ) ? -1L : ans;
}


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

int main() {
  int H,W;
  cin >> H >> W;
  for (int i=0; i<W+2; i++) 
    cout << '#';
  cout << endl;
  for (int i=0; i<H; i++) {
    string S;
    cin >> S;
    cout << '#' << S << '#' << endl;
  }
  for (int i=0; i<W+2; i++) 
    cout << '#';
  cout << endl;
}


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

#define MOD_BY  998244353

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)(((int64_t)a * b) % MOD_BY);
}

#define MAX (1 << 18) /* 262144 */

int mult_11[MAX], mult_10[MAX];

void get_mult(void) {
	int i;
	mult_10[0] = 1;
	for (i = 1; i < MAX; i++) mult_10[i] = mul(mult_10[i - 1], 10);
	mult_11[0] = 0;
	for (i = 1; i < MAX; i++) mult_11[i] = add(mul(mult_11[i - 1], 10), 1);
}

int ki[MAX * 2 - 1], ki_all[MAX * 2 - 1];

int get_value(int idx, int width) {
	if (ki_all[idx] >= 0) {
		return mul(ki_all[idx], mult_11[width]);
	} else {
		return ki[idx];
	}
}

void ki_init(void) {
	int i;
	for (i = 0; i < MAX * 2 - 1; i++) {
		ki[i] = 0;
		ki_all[i] = -1;
	}
}

void ki_set_i(int idx, int qs, int qe, int ss, int se, int value) {
	if (qe <= ss || se <= qs) { /* 完全に外れている */
		/* nop */
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		ki_all[idx] = value;
	} else {
		int sm = ss + (se - ss) / 2;
		int lidx = idx * 2 + 1, ridx = idx * 2 + 2;
		if (ki_all[idx] >= 0) {
			ki_all[lidx] = ki_all[ridx] = ki_all[idx];
			ki_all[idx] = -1;
		}
		ki_set_i(lidx, qs, qe, ss, sm, value);
		ki_set_i(ridx, qs, qe, sm, se, value);
		ki[idx] = add(mul(get_value(lidx, sm - ss), mult_10[se - sm]), get_value(ridx, se - sm));
	}
}

void ki_set(int qs, int qe, int value) {
	if (qs < qe) ki_set_i(0, qs, qe, 0, MAX, value);
}

int ki_get_i(int idx, int qs, int qe, int ss, int se) {
	if (qe <= ss || se <= qs) { /* 完全に外れている */
		return 0;
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return get_value(idx, se - ss);
	} else if (ki_all[idx] >= 0) { /* 値が設定されている */
		int left = qs <= ss ? ss : qs;
		int right = se <= qe ? se : qe;
		return mul(ki_all[idx], mult_11[right - left]);
	} else {
		int rpos = qe <= se ? qe : se;
		int sm = ss + (se - ss) / 2;
		int left = ki_get_i(idx * 2 + 1, qs, qe, ss, sm);
		int right = ki_get_i(idx * 2 + 2, qs, qe, sm, se);
		if (rpos <= sm) {
			return left;
		} else {
			return add(mul(left, mult_10[rpos - sm]), right);
		}
	}
}

int ki_get(int qs, int qe) {
	return qs < qe ? ki_get_i(0, qs, qe, 0, MAX) : 0;
}

int main(void) {
	int N, Q;
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	get_mult();
	ki_init();
	ki_set(1, 1 + N, 1);
	for (i = 0; i < Q; i++) {
		int L, R, D;
		if (scanf("%d%d%d", &L, &R, &D) != 3) return 1;
		ki_set(L, R + 1, D);
		printf("%d\n", ki_get(1, 1 + N));
	}
	return 0;
}


Measured memory_bytes: 8464
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>

#define ll long long
using namespace std;

int dfs(vector<int> g[] , bool visited[] , int maxd[] , int i)
{
	if(visited[i])
	{
		return maxd[i];
	}
	//cout<<"visited : "<<i<<endl;
	
	visited[i] = true;
	int j,k;
	int size = g[i].size();
	int h = -1;
	for(j=0;j<size;j++)
	{
		k = g[i][j];
		h = max(h , dfs(g , visited , maxd , k));	
	}
	
	maxd[i] = 1 + h;
	//cout<<"maxd for i = "<<i<<" is "<<maxd[i]<<endl;
	return maxd[i];
}

main()
{
	int n,m;
	cin>>n>>m;
	int i,j;
	
	vector<int> g[n+1];
	for(i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		
		g[u].push_back(v);	
	}	
	
	bool visited[n+1] = {0};
	int maxd[n+1] = {0};
	int maxm = 0;
	for(i=1;i<=n;i++)
	{
		if(!visited[i])
		maxm = max(maxm , dfs(g , visited , maxd , i));
	}
	
	cout<<maxm;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
 
bool check(string s){
    string s1=s;
    reverse(s.begin(),s.end());
    if(s1==s) return true;
    return false;
}
 
int main(){
 
        string s;
        cin>>s;
        if(!check(s)){
            cout<<"No"<<endl;
            return 0;
        }
        int flag=0;
       for(int i=3;i<=s.size();i+=2){
            int cnt=0;
           string s1="";
           for(int j=0;j<((i-1)/2);j++){
            s1+=s[j];
           }
            if(check(s1) &&(s1.size()>1||s.size()<5)){
             flag++;
             break;
           }
       }
         for(int i=3;i<=s.size();i+=2){
           string s2="";
           for(int j=i-1;j>=(((i+3)/2)-1);j--){
            s2+=s[j];
           }
            if(check(s2) &&(s2.size()>1||s.size()<5)){
             flag++;
             break;
           }
 
 
       }
       if(flag==2) cout<<"Yes"<<endl;
       else cout<<"No"<<endl;
 
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    
    int A,B;
    
    cin >> A;
    cin >> B;
    
    int i;
    
    for( i = 0; ( A - 1 ) * i + 1 < B ; i++ ){
    }
    
    cout << i;
}


Measured memory_bytes: 384
#include <stdio.h>
int main(void) {
	int a, b, c, d, e, k;
	scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &k);
	if (e - a > k) {
		printf(":(\n");
	}
	else {
		printf("Yay!\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    set<int> st;
    rep(i,0,N){
        int a;
        cin >> a;
        if(st.count(a)){
            st.erase(a);
        }else{
            st.insert(a);
        }
    }
    cout << st.size() << endl;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    int N;  cin>>N;
    vector<ll> X(N,0);
    vector<ll> C(N,0);
    for(int i=0;i<N;i++){
        cin>>X[i];
        C[i]=X[i];
    }
    sort(C.begin(),C.end());
    ll M1,M2;
    M1=C[(N-1)/2];
    M2=C[(N-1)/2+1];
    for(int i=0;i<N;i++){
        if(X[i]>=M2){
            cout<<M1<<endl;
        }
        else if(X[i]<=M1){
            cout<<M2<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 5376
import java.util.*;
import java.io.*;

import static java.lang.System.in;

public class Main {
    static List<Integer>[] g;
    static int n;
    static int[] dep;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        //PrintWriter out = new PrintWriter(System.out);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        //String[] buf = reader.readLine().split(" ");
        n = sc.nextInt();
        dep = new int[n+1];
        g = new LinkedList[n+1];
        for(int i=0;i<=n;i++) g[i]=new LinkedList<>();
        for(int i=1;i<n;i++){
            int a =sc.nextInt(), b=sc.nextInt();
            g[a].add(b); g[b].add(a);
        }
        dfs(1,1,0);
        int maxi=0,idx=1;
        for(int i=2;i<=n;i++){
            if(dep[i]>maxi) idx=i;
            maxi=Math.max(maxi,dep[i]);
        }
        Arrays.fill(dep,0);
        dfs(idx,idx,0);
        int dia=0;
        for(int i=1;i<=n;i++) dia=Math.max(dia,dep[i]);
        String ans = dia%3==1?"Second":"First";
        System.out.println(ans);
    }
    static void dfs(int root, int from, int level){
        dep[root]=level;
        for(int to:g[root]){
            if(to==from) continue;
            dfs(to,root,level+1);
        }
    }
}

Measured memory_bytes: 153640
N = int(input())
S = []
for i in range(N):
    S.append(input())

S.sort()

dic = list((set(S)))
dic.sort()
times = [0] * len(dic)
aa=0

for s in S :
    if dic[aa] == s:
        times[aa] += 1
    else:
        aa += 1
        times[aa] += 1

ans = [0] * len(dic)
ma = max(times)

s_ans = []

for a in range(len(dic)):
    if times[a] == ma:
        s_ans.append(dic[a])

s_ans.sort()

for j in range(len(s_ans)):
    print(s_ans[j])



Measured memory_bytes: 29636
from collections import OrderedDict

temp=input()
n,k=list(map(int,temp.split(" ")))
co=OrderedDict()
ans=[]
temp=input()
nums=list(map(int,temp.split(" ")))
for i in nums:
  if i in co:
	  co[i]+=1
  else:
	  co[i]=1
for i in co:
  ans.append(co[i])
kinds=len(ans)
dif=kinds-k
if dif<=0:
    print(0)
else:
    ans.sort()
    print(sum(ans[:dif]))

Measured memory_bytes: 71700
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define MAX 200005
#define INF 200005

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  int num=1, ans=0;
  rep(i, n){
    cin >> a[i];
    if(a[i]!=num){
      ans++;
    } else {
      num++;
    }
  }
  if(num==1){
    ans=-1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};

//証言をグラフの形で保持する
int g[15][15];

int main(void){
  int N;
  cin >> N;
  rep(i,N)rep(j,N) g[i][j] = -1;  //初期化
  int A[N];
  rep(i,N){
    cin >> A[i];
    rep(j, A[i]){
      int a, x;
      cin >> a >> x;
      a--;
      g[i][a] = x;  //iからaへの証言がx
    }
  }

  int ans = 0;  //正直者の数の最大値
  rep(s,1<<N){
    vector <int> d(N);  //正直者 or 不親切の割り当て
    rep(i,N){
      if (s>>i&1){
        d[i] = 1;
      }
    }
    bool ok = true;  //これがtrueのままだったらその割り当てはok
    //i番目の人が正直者だったらその人の全部の証言を確認する
    rep(i,N){
      if (d[i]){
        rep(j,N){
          if (g[i][j] == -1) continue;
          if (g[i][j] != d[j]) ok = false;
        }
      }
    }
    //sの1の数を数える
    if (ok) ans = max(ans, __builtin_popcount(s));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3564
from collections import deque
s = input()
Q = int(input())

SS =deque(list(s))
rev_count = 0

for i in range(Q):
    que = input()
    if que[0] == '1':
        rev_count +=1
    elif que[0] == '2':
        if (rev_count + int(que[2]))%2 == 0:
            SS.append(que[4])
        else:
            SS.appendleft(que[4])

print("".join(SS) if rev_count %2 == 0 else ("".join(SS))[-1::-1])


Measured memory_bytes: 14248
import itertools
n = int(input())
maru = []
batu = []
for i in range(n):
    tmp_maru = []
    tmp_batu = []
    a = int(input())
    for i in range(a):
        x,y = map(int,input().split())
        if y == 0:
            tmp_batu.append(x)
        else:
            tmp_maru.append(x)
    maru.append(tmp_maru)
    batu.append(tmp_batu)
seq = (0,1)
list = []
for i in itertools.product(seq, repeat=n):
    list.append(i)
ans = 0
for i in list:
    tmp = [2 for i in range(n)]
    check = 0
    for j in range(n):
        if i[j] == 0:
            tmp[j] = 0
        else:
            tmp[j] = 1
    for j in range(n):
        if i[j] == 1:
            for k in maru[j]:
                if tmp[k-1] == 0:
                    check = 1
                    break
                else:
                    tmp[k-1] = 1
            for k in batu[j]:
                if tmp[k-1] == 1:
                    check = 1
                    break
                else:
                    tmp[k-1] = 0
    if check == 0:    
        x = i.count(1)
        if x > ans:
            ans = x
print(ans)






Measured memory_bytes: 8948