akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include<functional>
#include<queue>
#include<regex>
#include<time.h>

/*
#include <thread>
#include <exception>
*/

using namespace std;

#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl

#define Tof(x) (x) ? Yes : No
#define TOF(x) (x) ? YES : NO
#define tof(x) (x) ? yes : no

using ll = long long;

constexpr ll MOD = 1000000007;
constexpr ll INF = 1050000000;



/*for文でx,yを上下左右確認するやつだよ。正直使いづらいよ。

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


for (int i = 0; i < 4; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
}

*/

/*繰り返し二乗法だよ。modもとってくれるよ。n^kをmodで割った余りでやってくれるよ。

ll POW_MOD(ll n, ll k, ll mod) {
	ll r = 1;

	for (; k > 0; k >>= 1) {
		if (k & 1) {
			r = (r * n) % mod;
		}
		n = (n * n) % mod;
	}
	return r;
}

*/

/*2重for文書くのめんどくなった時用だよ。

for (int i = 0; i < h; ++i) {
	for (int j = 0; j < w; ++j) {

	}
}

*/



int main() {
	double n, d; cin >> n >> d;

	cout << ceil(n / (d*2 + 1)) << endl;


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main() {
	LL N, K;
	cin >> N >> K;

	vector<vector<LL>> black(K, vector<LL>(K, 0));
	vector<vector<LL>> white(K, vector<LL>(K, 0));

	REP(i, N) {
		LL X, Y;
		char c;
		cin >> X >> Y >> c;
		X = X % (2 * K);
		Y = Y % (2 * K);

		bool isblack;

		if (c == 'B') {
			isblack = true;
		}
		else {
			isblack = false;
		}

		if (X >= K) {
			isblack = !isblack;
		}

		if (Y >= K) {
			isblack = !isblack;
		}

		if (isblack) {
			black[X%K][Y%K]++;
		}
		else {
			white[X%K][Y%K]++;
		}
	}

	vector<vector<LL>> sumblack(K + 1, vector<LL>(K + 1, 0));
	vector<vector<LL>> sumwhite(K + 1, vector<LL>(K + 1, 0));

	FOR(x,1, K+1) {
		FOR(y, 1, K + 1) {
			sumblack[x][y] = black[x - 1][y - 1] + sumblack[x - 1][y] + sumblack[x][y - 1] - sumblack[x - 1][y - 1];
			sumwhite[x][y] = white[x - 1][y - 1] + sumwhite[x - 1][y] + sumwhite[x][y - 1] - sumwhite[x - 1][y - 1];
		}
	}

	LL max = -1;

	FOR(x, 1, K + 1) {
		FOR(y, 1, K + 1) {
			LL sum = 0;
			sum += sumblack[x][y];

			sum += sumwhite[x][K];
			sum -= sumwhite[x][y];

			sum += sumwhite[K][y];
			sum -= sumwhite[x][y];

			sum += sumblack[K][K];
			sum -= sumblack[K][y];
			sum -= sumblack[x][K];
			sum += sumblack[x][y];

			if (N - sum > sum) {
				sum = N - sum;
			}

			if (sum > max) {
				max = sum;
			}
		}
	}

	cout << max << endl;
}

Measured memory_bytes: 31616
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k); i > (n); i--)
#define FORre(i, k, n) for(int i = (k); i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;
const int mod = 1000000007;

int main(void){
  int r;
  cin >> r;
  cout << 3*r*r << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	long long n,k,d,a,b;
	scanf("%lld %lld %lld",&n,&k,&d);  //x起步 k步 d距离 
	if(n < 0)
		n = n*(-1);
 	a = n/d;
 	
	if(a >= k){
		printf("%lld \n",n - k*d);
	}else{
		b = k - a;
		if(b%2 == 0){
			printf("%lld \n",n%d);
		}else{
			printf("%lld \n",d - n%d);
		}
	}
	
	return 0;
} 

Measured memory_bytes: 1732
// abc149_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif
    
    int N, i;
    cin >> N >> i;

    int ans = N - i + 1;
    print(ans);

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define pi 3.14159265358979323846264338327950L
int main()
{
        fast;

        int t=1;
       // cin>>t;
        while(t--)
        {
                 int a,b,h,m;
                cin>>a>>b>>h>>m;
                long double rad=2*pi*((long double)(h/12.0+(m/60.0)/12.0)  - (long double)(m/60.0));

                long double ans=(long double)((a*a)+(b*b)-(long double)(2*a*b*cos(rad)));


                cout<<fixed<<setprecision(20)<<(long double)sqrt(ans)<<endl;

        }
}

Measured memory_bytes: 4136
#include<bits/stdc++.h>
using namespace std;
int c[5][5];
int main(){
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    cin>>c[i][j];
    int b11,b12,b13,b21,b22,b23,b31,b32,b33;
    for(int a1=0;a1<=100;a1++){
        b11=c[1][1]-a1;
        b21=c[1][2]-a1;
        b31=c[1][3]-a1;
        for(int a2=0;a2<=100;a2++){
            b12=c[2][1]-a2;
            b22=c[2][2]-a2;
            b32=c[2][3]-a2;
            if(b11!=b12||b21!=b22||b31!=b32)continue;   
            for(int a3=0;a3<=100;a3++){
                b13=c[3][1]-a3;
                b23=c[3][2]-a3;
                b33=c[3][3]-a3;
                if(b11==b13 && b21==b23 && b31==b33){
                    cout<<"Yes";
                    return 0;
                }
            }
        }
    }
    cout<<"No";
    return 0;
}

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

signed main()
{
    int a,b,k;
    cin>>a>>b>>k;
    int z=min(a,k);
    a-=z;
    k-=z;
    z=min(b,k);
    k-=z;
    b-=z;
    cout<<a<<" "<<b;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
const ll MOD=1e9+7;

vector<int> combination(int n,int k){
	vector<int> ans;
	int x = (1<<k)-1;
	int f = x<<(n-k);
	while(1){
		ans.push_back(x);
		if(x==f)return ans;
		x += x&-x;
		int pcount = bitset<32>(x).count();
		x|=(1<<(k-pcount))-1;
	}
}

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

	int N;
	cin >> N;
	int a[N][N];
	FOR(i,0,N)FOR(j,0,N){
		cin>>a[i][j];
	}

	int dp[N+1][(1<<N)]={};

	dp[0][0] = 1;
	FOR(i,0,N){
		for(auto j:combination(N,i)){
			FOR(k,0,N){
				if( a[i][k] && !(j&(1<<k)) ){
					(dp[i+1][j+(1<<k)] += dp[i][j] ) %= MOD;
				}
			}
		}
	}
	cout << dp[N][(1<<N)-1] << endl;

}


Measured memory_bytes: 183952
A = int(input())
B = int(input())
C = int(input())
X = int(input())

num_x = 0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if i*500 + j*100 + k*50 == X:
                num_x += 1

print(num_x)

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

using namespace std;

#define int long long
#define fi first
#define se second
#define inf 1e9
const int mod=(int)1e9+7;

void test_case(){
	int x;
	cin>>x;
	int ans=0;
	ans+=(x/500)*1000;
	x=x%500;
	//cout<<x<<"\n";
	ans+=(x/5)*5;
	cout<<ans;
}

signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--)test_case();
}


Measured memory_bytes: 256
#include<stdio.h>
typedef long long ll;

#define int ll

int map[16][16];
int memo[16][16];
int f(int,int);

int f(int a,int b){
    if(a<0||b<0||map[a][b]==-1)return 0;
    if(memo[a][b]!=-1)return memo[a][b];
    return memo[a][b]=f(a-1,b)+f(a,b-1);
}

signed main(void){
    while(1){
        int mapx,mapy,x,y,n,i,j;
        for(i=0;i<16;i++){
            for(j=0;j<16;j++){
                memo[i][j]=-1;
                map[i][j]=0;
            }
        }
        memo[0][0]=1;
        scanf("%lld %lld",&mapx,&mapy);
        if(mapx==0&&mapy==0)break;
        scanf("%lld",&n);
        for(i=0;i<n;i++){
            scanf("%lld %lld",&x,&y);
            map[x-1][y-1]=-1;
        }
        printf("%lld\n",f(mapx-1,mapy-1));
    }
    return 0;
}

Measured memory_bytes: 604
import 'dart:io';
import 'dart:convert';

main(List<String> args) async {
  int N = int.parse(stdin.readLineSync());
  var lines = stdin.transform(utf8.decoder).transform(LineSplitter());
  // List<int> A =
  //     stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
  var A = new List();
  await for (var line in lines) {
    A = line.split(" ").map((x) => int.parse(x)).toList();
    break;
  }
  var ans = new List.filled(N, 0);
  for (var x in A) {
    ans[x - 1] += 1;
  }
  for (var x in ans) {
    print(x);
  }
}


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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

int main(){
    int N, M;
    cin >> N >> M;
    tuple<int, int, int> T[M];
    for(int i = 0; i < M; i++){
        int p, y;
        cin >> p >> y;
        T[i] = make_tuple(y, p, i);
    }
    sort(T, T+M);

    int cnt[N+1];
    fill(cnt, cnt+N+1, 0);

    pair<int, int> id[M];

    for(int i = 0; i < M; i++){
        int y, p, idx;
        tie(y, p, idx) = T[i];
        cnt[p]++;
        id[idx] = make_pair(p, cnt[p]);
    }

    for(int i = 0; i < M; i++){
        cout << setw(6) << setfill('0') << id[i].first;
        cout << setw(6) << setfill('0') << id[i].second << endl; 
    }

    return 0;
}

Measured memory_bytes: 3840
x = input().split(' ')
a = int(x[0])
b = int(x[1])
c = int(x[2])

if a <= b <= c:
    print(a, b, c)
elif a <= c <= b:
    print(a, c, b)
elif b <= a <= c:
    print(b, a, c)
elif b <= c <= a:
    print(b,  c,  a)
elif c <= a <= b:
    print(c, a, b)
else:
    print(c, b, a)

Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n ;
vector<ll> arr(100001), dp(100001);
void solve(){
	dp[2]=abs(arr[1]-arr[2]);
	for(ll i=3 ; i<= n ; i++){
		ll f1=abs(arr[i]-arr[i-1])+dp[i-1];
		ll f2=abs(arr[i]-arr[i-2])+dp[i-2];
		dp[i]=min(f1,f2);
	}
	cout<<dp[n]<<endl;
}
int main(){
	cin>>n;
	for(ll i=1; i<=n; i++)cin>>arr[i];
	solve();
}

Measured memory_bytes: 1792
/*
─────────────────────
───────────████████──
──────────███▄███████
──────────███████████
──────────███████████
──────────██████─────
──────────█████████──
█───────███████──────
██────████████████───
███──████AJ████──█───
███████████████──────
███████████████──────
─█████████████───────
──███████████────────
────████████─────────
─────███──██─────────
─────██────█─────────
─────█─────█─────────
─────██────██────────
─────────────────────
*/

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

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long

vector<vector<int>> comp(21, vector<int>(21, 0));
int N;
ll mod = 1e9 + 7;
vector<vector<ll>> dp;

ll getMax(int index, int w) {
	// Function returns for index'th man and the woman left
	// in w how many ways can they be arranged
	// All men explored => index of man I'm currently on is == N

	if (index == N) {
		return (w != 0 ? 0 : 1);
	}

	if (dp[index][w] != -1) return dp[index][w];


	ll ans = 0;
	for (int i = 0; i < N; i++) {
		if (comp[index][i] && (((1 << i) & w) != 0)) {
			int v = w ^ (w & (1 << i));
			ans += getMax(index + 1, v) % mod;
		}
	}

	return dp[index][w] = (ans % mod);
}


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> comp[i][j];
		}
	}
	dp = vector<vector<ll>> (N, vector<ll>(1 << N, -1));
	int w = (1 << N) - 1;
	ll result = getMax(0, w);
	cout << result << endl;
	return 0;
}

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

int main() {
  char c;
  cin >> c;

  int count=0;
  // ここにプログラムを追記
  for (int i=1;i<5;i++)
  {
    if(c=='a')
      count += 1;
    else if(c=='i')
      count += 1;
    else if(c=='u')
      count += 1;
    else if(c=='e')
      count += 1;
    else if(c=='o')
      count += 1;
  }

  if (count==0)
    cout << "consonant" << endl;
  else
    cout << "vowel" << endl;
}

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

using namespace std;

#define ull unsigned long long

void printString(ull n) 
{ 
  string res = "";
  while (n) {
    n--;
    res += 'a' + n % 26;
    n /= 26;
  }
  reverse(res.begin(), res.end());
  cout << res;
  cout << endl;
} 

int main() {
  ull n;
  cin >> n;
  printString(n);
}

Measured memory_bytes: 3656
#define SUBMIT

#include <bits/stdc++.h>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;

int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    auto s = std::string(R"(31 -41 -59 26
)");
    stringstream stream(s);
#endif
    int x1, y1, x2, y2;
    stream >> x1 >> y1 >> x2 >> y2;

    auto dx12 = x2 - x1;
    auto dy12 = y2 - y1;

    auto x3 = x2 - dy12;
    auto y3 = y2 + dx12;

    auto x4 = x3 - dx12;
    auto y4 = y3 - dy12;

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}

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

vector<int> b(100);
int n;
bool vfind(int x) {
	bool ret = false;
	for(int i = 0; i < n; ++i) {
		if(x == b[i]) {
			ret = true;
			break;
		}
	}
	return ret;
}
void yess() {
	cout << "Yes";
}
void noo() {
	cout << "No";
}
int main() {
	int a[3][3];
	for(int i = 0; i < 3; ++i) {
		for(int j = 0; j < 3; ++j) {
			cin >> a[i][j];
		}
	}
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> b[i];
	for(int i = 0; i < 3; ++i) {
		if(vfind(a[i][0]) && vfind(a[i][1]) && vfind(a[i][2])) {
			yess();
			return 0;
		}
	}
	for(int i = 0; i < 3; ++i) {
		if(vfind(a[0][i]) && vfind(a[1][i]) && vfind(a[2][i])) {
			yess();
			return 0;
		}
	}
	if(vfind(a[0][0]) && vfind(a[1][1]) && vfind(a[2][2])) {
		yess();
		return 0;
	}
	if(vfind(a[2][0]) && vfind(a[1][1]) && vfind(a[0][2])) {
		yess();
		return 0;
	}
	noo();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define MAX_N 100000
ll dp[MAX_N][3];

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

    int N; cin >> N;
    ve_vel a(N, vel(3));
    rep(i,N) rep(j,3) cin >> a[i][j];

    rep(i,N) rep(j,3) rep(k,3) {
        if(j == k) continue;
        chmax(dp[i+1][k], dp[i][j] + a[i][k]);
    }

    ll res = 0;
    rep(j,3) chmax(res, dp[N][j]);
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 8064
#include <iostream>
#include <string>

using namespace std;

int main() {
    string S, pred;
    cin >> S;
    string weather[3];
    weather[0] = "Sunny";
    weather[1] = "Cloudy";
    weather[2] = "Rainy";
    for( int i=0; i<3; i++){
        if(weather[i].compare(S) == 0 )
            pred = weather[(i+1)%3];
    }

    cout << pred << endl;
    return 0;
}

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

int main()
{
  int n, m;
  cin >> n >> m;
  vector<priority_queue<pair<int, int>>> v(100000);

  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    v[a].emplace(b, a);
  }

  int ans = 0;
  priority_queue<pair<int, int>> pq;

  for (int i = 0; i < m; i++) {
    if (!v[i].empty()) {
      pq.push(v[i].top());
      v[i].pop();
    }
    if (!pq.empty()) {
      auto t = pq.top();
      pq.pop();
      ans += t.first;
      if (!v[t.second].empty()) {
        pq.push(v[t.second].top());
        v[t.second].pop();
      }
    }
  }
  cout << ans << endl;
}


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

template <typename T>
T pow(T a, long long n, T e = 1) {
    T ret = e;
    while (n) {
        if (n & 1) ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}

struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod) x -= mod;
    }
    ModInt& operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    ModInt& operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0) x += mod;
        return *this;
    }
    ModInt& operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt& operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }

    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }

    friend ostream& operator<<(ostream& s, ModInt a) {
        s << a.x;
        return s;
    }
    friend istream& operator>>(istream& s, ModInt& a) {
        s >> a.x;
        return s;
    }
};

using mint = ModInt;

mint fact[3000];
mint factinv[3000];

void init() {
    fact[0] = 1;
    for (int i = 1; i < mod; i++) {
        fact[i] = fact[i - 1] * i;
    }
    factinv[mod - 1] = fact[mod - 1].inv();
    for (int i = mod - 2; i >= 0; i--) {
        factinv[i] = factinv[i + 1] * (i + 1);
    }
    assert(factinv[0] == 1);
}

mint ncr(int n, int r) { return fact[n] * factinv[r] * factinv[n - r]; }

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

    cin >> mod;
    init();
    vector<mint> bs(mod);
    for (int i = 0; i < mod; i++) {
        mint a;
        cin >> a;
        mint pw = 1;
        for (int j = mod - 1; j >= 0; j--) {
            mint cf = -ncr(mod - 1, j) * pw;
            pw *= -i;
            if (j == 0) cf += 1;
            bs[j] += a * cf;
        }
    }
    for (int i = 0; i < mod; i++) {
        cout << bs[i] << ' ';
    }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;


/*----------------------------------------------------------------*/
signed main(){

	int n,m;
	cin >> n >> m;
	if(m == 0){
		cout << "0 0" << endl;
		return 0;
	}

	vll p(m);
	vector<string> s(m);
	rep(i,m)cin >> p[i] >> s[i];
	int isac[100010] = {0};
	int wacnt[100010] = {0};
	rep(i,m){
		int x = p[i]-1;
		if(s[i] == "WA" && isac[x] == 0)wacnt[x]++;
		else if(s[i] == "AC" && isac[x] == 0){
			isac[x] = 1;
		}
	}
	int ac = 0;
	int pn = 0;
	rep(i,n){
		if(isac[i] == 1){
			ac++;
			pn += wacnt[i];
		}
	}
	cout << ac << " " << pn << endl;

	
	
	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://ddcc2020-qual.contest.atcoder.jp/tasks/ddcc2020_qual_b
// rm -r -f test;oj dl https://abc151.contest.atcoder.jp/tasks/abc151_b

Measured memory_bytes: 8064
#include<iostream>
using namespace std;
int main(){string s,r,a="AIDUNYAN";cin>>s;r=s;int c[26]={},z=0,p;for(char k:a)c[k-'A']--;for(int i=0;i<s.size();i++){if(i>7){if(!c[p=s[i-8]-'A']--)z--;if(!c[p])z++;}if(!c[p=s[i]-'A']++)z--;if(!c[p])z++;if(z==6){for(p=0;p<8;p++)r[i-7+p]=a[p];r[i-5]='Z';}}cout<<r<<endl;}

Measured memory_bytes: 1196
use std::io;

fn read<T: std::str::FromStr>() -> T {
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    n.trim().parse().ok().unwrap()
}
fn main() {
    for i in 1..10005 {
        let x: i32 = read();
        if x == 0 {
            break;
        }
        println!("Case {}: {}", i, x);
    }
}



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

                                                                                   

int main(){


    int a, b, c, k;


    cin >> a >> b >> c;


    if( a == b ) k = c;

    else if( b == c ) k = a;

    else if( a == c ) k = b;


    cout << k << endl;


    return 0;

    }

Measured memory_bytes: 256
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

typedef pair<int, int> pii;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

int H, W;

// ?????? N ??????????????°?????????????????¢???????????§
// Verified: AOJ DPL_3_C: Largest Rectangle in a Histogram
int histArea(vector<int> h) {
    // ??????
    int N = h.size();
    h.push_back(0); N++;

    // height, position
    int ans = 0;
    stack<pii> S;
    rep(i,0,N+1) {
        if(S.empty()) S.push(pii(h[i], i));

        if     (S.top().first < h[i])
            S.push(pii(h[i], i));
        else if(S.top().first > h[i]) {
            int lastpos = 0;
            while(!S.empty() && S.top().first >= h[i]) {
                lastpos = S.top().second;
                chmax(ans, S.top().first * (i-lastpos));
                S.pop();
            }
            S.push(pii(h[i], lastpos));
        }
    }
    return ans;
}

// ?????§????????¢??????
// 0 -> ?¶??????????????????? 1 -> ?±??????????????????????
int maxRectangle(vector< vector<int> > board) {
    int H = board.size(), W = board[0].size();
    vector< vector<int> > sum(H, vector<int>(W));
    rep(i,0,H) rep(j,0,W) {
        if(board[i][j] == 1) continue;
        sum[i][j] = (i > 0 ? sum[i-1][j] : 0) + 1;
    }
    int ret = 0;
    rep(i,0,H) {
        chmax(ret, histArea(sum[i]));
    }
    return ret;
}

signed main() {
    cin >> H >> W;
    vector< vector<int> > board(H, vector<int>(W));
    rep(i,0,H) rep(j,0,W) cin >> board[i][j];
    cout << maxRectangle(board) << endl;
    return 0;
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> ii;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vii;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<bool> vbl;
typedef vector<vbl> mbl;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(s) (s).begin(), (s).end()
const ll MOD = 1e9 + 7;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int a[5];
    for (int i = 0; i < 5; i++)
    {
        cin >> a[i];
        if (a[i] == 0)
        {
            cout << i + 1;
            return 0;
        }
    }
}

Measured memory_bytes: 3644
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func bitCount(bits int) int {

	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff)
}

const mod = 1000000007

func rec(N int, a [22][22]int) int {
	var dp [22][1 << 22]int
	dp[0][0] = 1
	for i := 0; i < N; i++ {
		for bit := 0; bit < 1<<uint(N); bit++ {
			if bitCount(bit) == i {
				for j := 0; j < N; j++ {
					if (bit&(1<<uint(j))) == 0 && a[i][j] != 0 {
						pos := bit | (1 << uint(j))
						dp[i+1][pos] += dp[i][bit]
						dp[i+1][pos] %= mod
					}
				}
			}
		}
	}
	return dp[N][(1<<uint(N))-1]
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	var a [22][22]int
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			a[i][j] = getInt()
		}
	}

	res := rec(N, a)
	out(res)
}


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

int main() {
  int N, K;
  cin >> N;
  cin >> K;
  vector<int> x(N);
  for(int i=0; i<N; i++) {
    cin >> x.at(i);
  }
  int cnt=0;
  for(int i=0; i<N; i++) {
    cnt+=min(abs(K-x.at(i)),x.at(i));
  }
  cout << cnt*2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define si set<int>
#define stk stack<int>
#define que queue<int>
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
using namespace std; 

int main(){
	int n,x;
	cin>>n>>x;
	if(n*500>=x)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
}

Measured memory_bytes: 256
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n;
struct node { int l,r; } a[N];
bool operator <(node a,node b) { return a.l<b.l; }
priority_queue<int> Q;

int main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        int x=read(),d=read();
        a[i].l=x-d,a[i].r=x+d;
    }
    sort(a+1,a+n+1); int ans=0;
    for (re int i=1;i<=n;++i) {
        if (!Q.empty()&&a[i].l<Q.top()) {
            if (Q.top()>a[i].r) Q.pop(),Q.push(a[i].r);
        }
        else ++ans,Q.push(a[i].r);
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1660
l,k=map(int,input().split())
s=input()+'?'
ss=[]
prev=0
for i in range(l):
  if s[i]!=s[i+1]:
    ss.append(s[prev:i+1])
    prev=i+1
ll=len(ss)
s2=''
cnt=0
for i in range(ll):
  if i%2==0:
    s2+=ss[i]
  else:
    if cnt<k:
      cnt+=1
      if ss[i][0]=='R':
        s2+='L'*len(ss[i])
      else:
        s2+='R'*len(ss[i])
    else:
      s2+=ss[i]
s2+='?'
ans=0
cnt=0
for i in range(l):
  if s2[i]==s2[i+1]:
    cnt+=1
  else:
    ans+=cnt
    cnt=0
print(ans)

Measured memory_bytes: 5116
#include <iostream>

using namespace std;

int main() {
	int n = 0;
	cin >> n;
	for(int i=1;i<=n;i++){
		if(i% 3 == 0 ||  i% 10 == 3){cout << " " << i;continue;}
		int x=i/10;
		while(x>0){
			if(x% 10 == 3){cout << " " << i;break;}
			x/=10;
		}
	}
	cout << endl;
}



Measured memory_bytes: 3112
h,w,k=map(int,input().split())
l=[]

for i in range(h):
    l.append([x for x in input()])

ans=0
for i in range(2**h):
    row=bin(i)[2:]
    while len(row)<h:row='0'+row
    for j in range(2**w):
        col=bin(j)[2:]
        while len(col) < w: col = '0' + col

        s=0
        for x in range(h):
            for y in range(w):
                if l[x][y]=='#' and row[x]=='0' and col[y]=='0':
                    s+=1

        if s==k:
            ans+=1
print(ans)






Measured memory_bytes: 68448
n = int(input())
a = [int(i) for i in input().split()]

a_odd = a[0::2]
a_even = a[1::2]

if n % 2 == 0:
    a_even.reverse()
    b = a_even + a_odd 
else:
    a_odd.reverse()
    b = a_odd + a_even

print(*b)


Measured memory_bytes: 25156
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

using namespace std;

int getint()
{
    char ch=getchar();
    int f=1,x=0;
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0'; ch=getchar();}
    return f*x;
}

const int N=3030;
const int MOD=1000000007;

int n,m;
char s[N];
int sum[N];
int l[N],r[N];
long long c[N][N],f[N][N];

void init()
{
    n=getint(),m=getint();
    scanf("%s",s+1);
    for(int i=1; i<=n; i++) sum[i]=sum[i-1]+s[i]-'0';
    int tot=0;
    for(int i=1; i<=m; i++){
        int ll=getint(),rr=getint();
        if(ll==l[tot]){
            r[tot]=max(r[tot],rr);
        }else if(rr<=r[tot]){
        }else{
            tot++;
            l[tot]=ll;
            r[tot]=rr;
        }
    }
    m=tot;
    for(int i=0; i<=n; i++){
        c[i][0]=1;
        for(int j=1; j<=i; j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
        }
    }
    l[m+1]=n+1;
    r[m+1]=n+1;
}

int main()
{
    //freopen("in.txt","r",stdin);
    init();
    f[0][0]=1;
    for(int i=1; i<=m; i++){
        int nxt=r[i]>=l[i+1]?r[i]-l[i+1]+1:0;
        int pre=r[i-1]>=l[i]?r[i-1]-l[i]+1:0;
        for(int k=0; k<=pre; k++){
            if(f[i-1][k]==0) continue;
            int lb=max(nxt-(r[i]-l[i]+1-(sum[r[i]]-sum[l[i]-1])-(pre-(sum[l[i]+pre-1]-sum[l[i]-1]))+pre-k),0);
            int rb=min(sum[r[i]]-sum[l[i]-1]-(sum[l[i]+pre-1]-sum[l[i]-1])+k,nxt);
            for(int j=lb; j<=rb; j++){
                f[i][j]=(f[i][j]+f[i-1][k]*c[r[i]-l[i]+1-nxt][sum[r[i]]-sum[l[i]-1]-(sum[l[i]+pre-1]-sum[l[i]-1])+k-j])%MOD;
            }
        }
    }
    printf("%lld\n",f[m][0]);
    return 0;
}


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

int h,w;
vector <vector <int>> m,m2;
queue <vector <int>> q,q2;
vector <int> ss(2);

int tansaku(int sx,int sy,int gx, int gy){
    m2=m;
    q2=q;
    if(m[sx][sy]==-1){
        return 0;
    }
    
    m2[sx][sy]=0;
    q2.push({sx,sy});
    while(q2.size()!=0){
        ss=q2.front();
        q2.pop();
        sx=ss[0];
        sy=ss[1];
        //cout << " " << sx << sy << endl;
        if(sx==gx and sy==gy){
        return m2[sx][sy];
        break;
        }

        if(sx<w-1){
            if(m2[sx+1][sy]==1000){
                q2.push({sx+1,sy});
                m2[sx+1][sy]=m2[sx][sy]+1;
            }
        }
        if(sx>0){
            if(m2[sx-1][sy]==1000){
                q2.push({sx-1,sy});
                m2[sx-1][sy]=m2[sx][sy]+1;
            }
        }
        if(sy<h-1){
            if(m2[sx][sy+1]==1000){
                q2.push({sx,sy+1});
                m2[sx][sy+1]=m2[sx][sy]+1;
            }
        }
        if(sy>0){
            if(m2[sx][sy-1]==1000){
                q2.push({sx,sy-1});
                m2[sx][sy-1]=m2[sx][sy]+1;
            }
        }
    }

}

int main(){
    
    cin >> h >> w;
    m.resize(w, vector <int> (h));
    string s;
    rep(i,h){
        cin >> s;
        rep(j,w){
            if(s[j]=='.'){
                m[j][i]=1000;
            }
            else{
                m[j][i]=-1;
            }
        }
    }

    int ans;
    int t;
    ans=0;
    rep(i,w){
        rep(j,h){
            rep(ig,w){
                rep(jg,h){
                    //cout << i << j << ig << jg << endl;
                    t=tansaku(i,j,ig,jg);
                    ans=max(ans,t);
                }
            }
            
        }
    }

    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main(void){
    char ch[1200];
    int i, n = 0;

    for(;;){
        scanf("%c", &ch[n]);
        if(ch[n] == '\n') break;

        if('A' <= ch[n] && ch[n] <= 'Z') 
            ch[n] += 32;
        else if('a' <= ch[n] && ch[n] <= 'z') 
            ch[n] -= 32;
        
        n++;
    }

    for(i = 0; i < n; i++){
        printf("%c", ch[i]);
    }
    putchar('\n');
    return 0;
}


Measured memory_bytes: 3144
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.List (unfoldr)
import Control.Monad
import Control.Monad.ST
import Control.Monad.State.Strict
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as BS

main = do
  [n,m,p] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  edges <- U.replicateM m $ do
    [a,b,c] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (a-1,b-1,p-c)
  let edges_to :: V.Vector [Int]
      edges_to = V.create $ do
        vec <- VM.replicate n []
        U.forM_ edges $ \(a,b,_) -> do
          VM.modify vec (a :) b
        return vec
  let reachable_from_end :: U.Vector Bool
      reachable_from_end = U.create $ do
        vec <- UM.replicate n False
        let dfs !i = do
              b <- UM.read vec i
              unless b $ do
                UM.write vec i True
                forM_ (edges_to V.! i) dfs
        dfs (n-1)
        return vec
  let edges' = U.filter (\(a,b,c) -> reachable_from_end U.! b) edges
  let result :: Maybe (U.Vector Int)
      result = runST $ do
        d <- UM.replicate n maxBound
        UM.write d 0 0
        let loop !i
              | i >= n = return Nothing
              | otherwise = do
                  update <- execStateT (U.forM_ edges' $ \(a,b,c) -> do
                                           a' <- UM.read d a
                                           b' <- UM.read d b
                                           when (a' /= maxBound && b' > a' + c) $ do
                                             UM.write d b (a' + c)
                                             put True
                                       ) False
                  if update
                    then loop (i + 1)
                    else Just <$> U.unsafeFreeze d
        loop 0
  case result of
    Nothing -> putStrLn "-1"
    Just d -> print $ max 0 (negate (d U.! (n - 1)))


Measured memory_bytes: 1276
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    int A[N];
    rep(i, N) {
        cin >> A[i];
    }

    sort(A, A+N); 

    int t = A[0];
    int k = 0;
    int c[N];
    rep(i,N) {
        c[i] = 0;
    }   

    rep(i, N) {
        if(t < A[i]) {
            t = A[i];
            k++;
            c[k]++;
        } 
        else {
            c[k]++;
        }
    }

    int ans = 0;

    rep(i, N) {
        if(c[i]%2 == 1) {
            ans++;
        }
    }
    
    cout << ans;
    
    cout << endl;
    return 0;
}

Measured memory_bytes: 1024
from itertools import accumulate
from operator import xor

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

MOD = 10**9 + 7

acc = list(accumulate(A, xor))
M = max(acc)
dp = [[0, 0, 0] for _ in range(M + 1)]
z = 0
for x in acc:
    if x == 0:
        z += 1
    else:
        dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
        dp[x][0] = (dp[x][0] + dp[x][1] + 1) % MOD
        dp[x][2] = z
for x in range(1, M + 1):
    dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
ans = (
    dp[acc[-1]][1] + 1 if acc[-1] != 0 else
    sum(dp[x][0] for x in range(1, M + 1)) + pow(2, acc.count(0) - 1, MOD)
) % MOD

# 出力
print(ans)

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

void print_vector (const vector<int> &a) {
	for (size_t i = 0; i < a.size(); i++) {
		cout << a[i] << " \n"[i + 1 == a.size()];
	}
}

void insertion_sort (vector<int> &a, size_t n) {
	for (size_t i = 1; i < n; i++) {
		print_vector(a);
		int v = a[i];
		size_t j = i - 1;
		while (j >= 0 and a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
	}
}

int main() {
	size_t n;
	cin >> n;
	vector<int> a(n);
	for (size_t i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	insertion_sort(a, n);
	print_vector(a);
}


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
int mod = 1000000000+7;

int main(){

    int n,k,d;
    cin>>n>>k;
    int a;
    int ans[n]={};
    rep(i,k){
        cin>>d;
        rep(j,d){
            cin>>a;
            ans[a-1]++;
        }
    }
    int count=0;
    rep(i,n)if(ans[i]==0)count++;
    cout<<count<<endl;


    return 0;
}


Measured memory_bytes: 3620
using System;

namespace ConsoleApp12
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            if (a % 2 == 0)
                Console.WriteLine(a / 2);
            else if (a % 2 > 0)
                Console.WriteLine(a / 2 + 1);

        }
    }
}


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

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

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

  string ans;
  while(n*m) {
    if (s[n-1]==t[m-1] && dp[n][m] == dp[n-1][m-1] + 1) {ans += s[n-1];n--;m--;}
    else if (dp[n][m] == dp[n-1][m]) n--;
    else m--;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}

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


namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            MainStream();
        }
        static void MainStream()
        {
            Scan sc = new Scan();
            write wr = new write();

            int[] ab = sc.intarr;
            int a = ab[0];
            int b = ab[1];

            if((a + b) % 2 == 0)
            {
                wr.wri((a + b) / 2);
            }
            else
            {
                wr.wri("IMPOSSIBLE");
            }
        }


    }

    class Scan
    {
        public string str => Console.ReadLine();

        public string[] strarr => str.Split(' ');

        public long[] longarr => strarr.Select(long.Parse).ToArray();
        public int[] intarr => strarr.Select(int.Parse).ToArray();
        public char[] chararr => str.ToArray();


    }



    class write
    {
        public void wri<Type>(Type x)
        {
            Console.WriteLine(x);
        }
    }

    class Method
    {
        static public int max(params int[] nums)
        {

            int maxx = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                maxx = Math.Max(maxx, nums[i]);
            }
            return maxx;
        }
    }
}


Measured memory_bytes: 13396
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yosiiii
 */


#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long int i=0;i<(n);++i)
typedef long long int ll;

class BDistance {
public:
	void solve(std::istream& in, std::ostream& out) {
        int n,d;
        in >>n >> d;
        vector<double> x(n),y(n);
        vector<double> z(n);
        out << setprecision(16);
        rep(i,n){
            in >> x[i] >> y[i];
            z[i] = sqrt(x[i]*x[i]+y[i]*y[i]);
        }
        sort(z.begin(),z.end());
        int ans = 0;
        rep(i,n){
            if(z[i]<=d)ans++;
            else break;
        }
        out << ans << endl;
	}
};


int main() {
	BDistance solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 8072
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct UnionFind{
  int n;
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
  int size(int x){
    return r[find(x)];
  }
};
//END CUT HERE

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

//INSERT ABOVE HERE

signed DSL_1_A(){
  int n,q;
  cin>>n>>q;
  UnionFind uf(n);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c) cout<<uf.same(x,y)<<"\n";
    else uf.unite(x,y);
  }
  cout<<flush;
  return 0;
}
/*
  verified on 2019/03/03
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp
*/

signed ABC120_D(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m),b(m);
  for(int i=0;i<m;i++) cin>>a[i]>>b[i];

  UnionFind uf(n);
  vector<Int> ans(m+1,0);
  ans[m]=n*(n-1)/2;
  for(int i=m-1;i>=0;i--){
    a[i]--;b[i]--;
    ans[i]=ans[i+1];
    if(uf.same(a[i],b[i])) continue;
    
    Int x=uf.size(a[i]),y=uf.size(b[i]);
    ans[i]-=x*y;
    
    uf.unite(a[i],b[i]);
  }
  ans.erase(ans.begin());
  for(Int x:ans) cout<<x<<"\n";
  cout<<flush;
  return 0;
}

/*
  verified on 2019/03/03
  https://atcoder.jp/contests/abc120/tasks/abc120_d
*/

signed main(){
  DSL_1_A();
  //ABC120_D();
  return 0; 
}



Measured memory_bytes: 3224
n = int(input())
a = list(map(int, input().split()))
MOD = 1000000007

bits = [0 for _ in range(60)]
for i in range(n):
    for b in range(60):
        if a[i] & 2 ** b > 0:
            bits[b] += 1

ans = 0
for i, b in enumerate(bits):
    if b > 0:
        ans += (2 ** i) * (b * (n-b))
        ans %= MOD
print(ans)


Measured memory_bytes: 123016
using System;

namespace AtCoder.ABC._131
{
    class b
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine().Trim();
            var spl = line.Split(' ');
            var N = int.Parse(spl[0]);
            var L = int.Parse(spl[1]);
            var sum = (L * 2 + N - 1) * N / 2;
            if(L * (L + N - 1) <= 0)
            {
                Console.WriteLine(sum);
            }
            else if (L > 0)
            {
                Console.WriteLine(sum - L);
            }
            else
            {
                Console.WriteLine(sum - (L + N - 1));
            }
        }
    }
}


Measured memory_bytes: 11092
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scan(&N)

	keta := 6
	warukazu := 100000
	for N/warukazu < 1 {
		warukazu /= 10
		keta--
	}

	var count int
	if keta <= 1 {
		count = N
	} else if keta <= 2 {
		count = 9
	} else if keta <= 3 {
		count = N - 90
	} else if keta <= 4 {
		count = 909
	} else if keta <= 5 {
		count = N - 9090
	} else if keta <= 6 {
		count = 90909
	}

	fmt.Printf("%d\n", count)

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
ll INF = 1000000007;

int main()
{
	string s;
	string t;
	cin>>s;
	cin>>t;
	ll k=0;
	for(ll i=0;i<s.size();i++)
	{
		if(s[i]==t[i])
			k++;
		else
			break;
	}
	if(k==s.size())
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n;
  cin >> k;
  int a[n];
  int asum;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    asum += a[i];
  }

  int divisor[30000];
  int cursor = 0;

  for(int i = 1; i * i <= asum; i++) {
    if(asum % i == 0) {
      divisor[cursor] = i;
      if(i * i != asum) divisor[cursor + 1] = asum / i;
      cursor += 2;
    }
  }

  int divisorlen = cursor;
  sort(divisor, divisor + divisorlen,  greater<int>());

  int rem[n];
  int r;
  int sum, nsum;

  for(int i = 0; i < divisorlen; i++) {
    int d = divisor[i];
    sum = 0;
    nsum = 0;
    for(int i = 0; i < n; i++) {
      r = a[i] % d;
      sum += r;
      rem[i] = r;
    }

    sort(rem, rem + n, greater<int>());

    for(int i = 0; i < n; i++) {
      if(sum == nsum) {
        if(sum <= k) {
          cout << d <<"\n";
          return 0;
        } else {
          continue;
        }
      }
      sum -= rem[i];
      nsum += d - rem[i];
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n][3];
    for(int i=0;i<n;i++)
        for(int j=0;j<3;j++)
        {
            cin>>a[i][j];        }

    int dp[n][3];
    for(int i=0;i<3;i++)dp[0][i]=a[0][i];
    




    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            int x=INT_MIN;
            for(int k=0;k<3;k++)
            {
                if(k!=j)
                x=max(x,dp[i-1][k]);
            }
            dp[i][j]=a[i][j]+x;
        }
    }

    
    
    
    
    
    
    int ans=INT_MIN;
    for(int i=0;i<3;i++)
     ans=max(ans,dp[n-1][i]);
    cout<<ans;
}


Measured memory_bytes: 2560