akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)


int main() {

int N , X;
  cin >> N >> X ; 
  vector<int> L(N);
  rep (i,N){
   cin  >> L.at(i);
  }//入力
 
 
  
  int a = 1;
  int D = 0;
  rep(i,N){
  
  D = D + L.at(i);
  
    if (D <= X ){
     a++; 
    }
  }
    cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005

int n,h[200005];

ll bit[200005],dp[200005],a[200005],ans;

void Upd(int nod, ll v){
    for(int i=nod;i<=n;i+=i&-i){
        bit[i]=max(bit[i],v);
    }
}

ll Qry(int nod){
    ll ans=0;
    for(int i=nod;i;i-=i&-i){
        ans=max(ans,bit[i]);
    }
    return ans;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        dp[i]=Qry(h[i])+a[i];
        Upd(h[i],dp[i]);
        ans=max(ans,dp[i]);
    }
    cout << ans;
}


Measured memory_bytes: 5760
N = int(input())
i = 0
ans = []
if N == 0:
  print(0)
  exit()
while N:
  if N%(2)**(i+1) > 0:
    ans.append(1)
    N -= (-2)**i
  else:
    ans.append(0)
  i += 1
ans.reverse()
print("".join(map(str,ans)))

Measured memory_bytes: 3064
//
// Created by 倉澤　一詩 on 2019/10/28.
//
#include <iostream>

int main() {

    uint16_t n;
    std::cin >> n;

    for (int i = 1; i < 10; i++) {
        for (int j = 1; j < 10; j++) {

            if (n == (i*j)) {
                std::cout << "Yes";
                return 0;
            }

        }
    }

    std::cout << "No";

    return 0;
}

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

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

	if ((100 * a + 10 * b + c) % 4 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
    int n, ctr = 0;
    scanf("%d", &n);
    int input[n];
    for(int i = 0; i < n; i++)
    {
    	scanf("%d", &input[i]);
	}
	for (int i = 0; i < n-2; i++) 
	{
	    for (int j = i+1; j < n-1; j++) 
		{
	      for (int k = j+1; k < n; k++) 
		  {
			if ((input[i] == input[j]) || (input[j] == input[k]) || (input [k] == input[i])) 
			{
	          continue;
	        }
	        if (input[i] + input[j] > input[k] && input[j] + input[k] > input[i] && input[k]+ input[i] > input[j]) 
			{
	          ctr++;
	        }
      	  }
    	}
    }
  	printf("%d", ctr);
    return 0;
}

Measured memory_bytes: 1732
#include<iostream>

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

typedef long long ll;

int main(){
    ll n;
    ll ans = 0;

    cin >> n;
    
    ll a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(a[i]%2) ans++;
    }
    if(ans%2) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
struct Edge
{
	int to;
	int nxt;
}e[10005];
int n,m,edgenum,head[5005],pa[5005],size[5005];
ll f[5005][5005],s[5005];
void add(int u,int v)
{
	e[++edgenum].to=v;
	e[edgenum].nxt=head[u];
	head[u]=edgenum;
}
void dfs(int node)
{
	f[node][1]=1;
	size[node]=1;
	for(int hd=head[node];hd;hd=e[hd].nxt)
	{
		int to=e[hd].to;
		if(to==pa[node])continue;
		pa[to]=node;
		dfs(to);
		ll v=0;
		for(int j=size[to];j>=1;j--)
		  if(j%2==0)
		    v=(v+f[to][j]*s[j/2])%MOD;
		for(int i=size[node];i>=1;i--)
		{
			for(int j=size[to];j>=1;j--)
			  f[node][i+j]=(f[node][i+j]+f[node][i]*f[to][j])%MOD;
			f[node][i]=v*(MOD-f[node][i])%MOD;
		}
		size[node]+=size[to];
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	s[0]=1;
	for(int i=1;i<=n;i++)
	  s[i]=s[i-1]*(2*i-1)%MOD;
	dfs(1);
	ll ans=0;
	for(int i=2;i<=n;i+=2)
	  ans=(ans+f[1][i]*s[i/2])%MOD;
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;

int main()
{
  int n = 0;
  fscanf(stdin, "%d", &n);
  vector<int> v(n);
  for (int i = 0; i < n; ++i) {
    fscanf(stdin, "%d", &v[i]);
  }
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    int ix = i;
    for (int j = i; j < n; ++j) {
      if (v[j] < v[ix]) {
        ix = j;
      }
    }
    if (i != ix) { ++cnt; }
    swap(v[i], v[ix]);
  }
  for (int i = 0; i < n; ++i) {
    if (i) { fprintf(stdout, " "); }
    fprintf(stdout, "%d", v[i]);
  }
  fprintf(stdout, "\n%d\n", cnt);
  return 0;
}

Measured memory_bytes: 1196
import itertools

N, K = [int(n) for n in input().split()]
P = [(int(n)+1)/2 for n in input().split()]
S = [0]+[E for E in itertools.accumulate(P)]
ans = 0
for j in range(N-K+1):
    e = S[j+K]-S[j]
    if ans < e:
        ans = e
print(ans)

Measured memory_bytes: 23616
s = list(input())
n = len(s)

l1 = ["0" if i % 2 == 0 else "1" for i in range(n)]
l2 = ["1" if i % 2 == 0 else "0" for i in range(n)]

diff1, diff2 = 0, 0

for i in range(n):
    if s[i] == l1[i]:
        diff1 += 1
    if s[i] == l2[i]:
        diff2 += 1

print(diff1 if diff1 <= diff2 else diff2)


Measured memory_bytes: 5540
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,l,ans;
  cin >> n;
  l=0;ans=0;
  int x;
  for(int i=0;i<n;i++){
    cin >> x;
    l=max(l,x);
    ans+=x;
  }
  if(ans>l*2)
    cout << "Yes" << endl;
  else
    cout << "No" <<endl;
}

Measured memory_bytes: 256
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);
}

int main()
{
	ios_init();
	int n;
	while(cin >> n) {
		vector<int> a(n), b(n);
		REP(i, n) cin >> a[i];
		REP(i, n) cin >> b[i];
		int ans = 0;
		REP(i, n) {
			if(a[i] > b[i]) {
				ans += a[i] - b[i];
			}
		}
		cout << ans << endl;
	}
	return 0;
}


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

char get_group(int a) {
    switch (a)
    {
    case 1: return 'a';
    case 2: return '2';
    case 3: return 'a';
    case 4: return 'b';
    case 5: return 'a';
    case 6: return 'b';
    case 7: return 'a';
    case 8: return 'a';
    case 9: return 'b';
    case 10: return 'a';
    case 11: return 'b';
    case 12: return 'a';
    default:
        return 'z';
    }
}
int main(void) {
    int x,y;cin>>x>>y;
    if (get_group(x) == get_group(y)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#define lint long long int
#define FOR(x, to) for(int x=0; x<(int)(to); x++) // for簡略表記
#define DUMP(ar) for(int loop=0; loop<(int)ar.size(); loop++) cout << "[" << loop << "]:" << ar[loop] << endl // 配列一覧表示
#define DUMPL(ar) for(int loop=0; loop<(int)ar.size(); loop++) { cout << ar[loop]; if(loop<(int)ar.size()-1) cout << ' '; } cout << endl; // 配列一行一覧表示
#define COUT(x) cout << x << endl // 単要素出力
#define ALL(ar) ar.begin(), ar.end() // コンテナの全要素
#define LOOPD(i) cout << "ループ[" << i << "]回目---------------" << endl // ループ回数デバグ
using namespace std;
// cout << fixed << setprecision(4) で小数点以下4桁の桁そろえ
// cout << setw(5) << ... で表示形式を5桁に設定 5桁未満なら頭に空白がつく 5桁越なら先頭から5桁まで
// cout << setw(5) << setfill('0') << ... で空白部分の埋め文字に5を使う
// getline(cin, [変数]); で空白などを含む入力の受け取り(行ごとの受け取り)
// cin >> ws; でそこまでにストリームに残されたホワイトスペースを取り除く(=以降のgetlineの有効化)

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

    int n, d;
    cin >> n >> d;
    vector<vector<int>> x(n, vector<int>(d, 0));
    FOR(i, n){
        FOR(k, d){
            cin >> x[i][k];
        }
    }

    double a = 0;
    int cnt = 0, b;

    FOR(i, n){
        for(int j=i+1; j<n; j++){
            a = 0;
            FOR(k, d){
                a += pow(fabs(x[i][k] - x[j][k]), 2);
            }
            a = sqrt(a);
            b = a;
            if(a == b) cnt++;
        }
    }

    COUT(cnt);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std; 
  
typedef long long LL; 
typedef pair<int, int> pii; 
typedef pair<LL, LL> pll; 
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef vector<pii> vii; 
typedef vector<LL> vl; 
typedef vector<vl> vvl; 
  
double EPS = 1e-9; 
int INF = 100005; 
long long int mod=1000000007;
long long TES=1000007;
long long INFF = 1000000000000000005LL; 
double PI = acos(-1); 
int dirx[8] = { -1, 0, 0, 1, -1, -1, 1, 1 }; 
int diry[8] = { 0, 1, -1, 0, -1, 1, -1, 1 }; 
  
#ifdef TESTING 
#define DEBUG fprintf(stderr, "====TESTING====\n") 
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl 
#define debug(...) fprintf(stderr, __VA_ARGS__) 
#else 
#define DEBUG 
#define VALUE(x) 
#define debug(...) 
#endif 
  
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a)) 
#define FORD(a, b, c) for (int(a) = (b); (a) >= (c); --(a)) 
#define FORSQ(a, b, c) for (int(a) = (b); (a) * (a) <= (c); ++(a)) 
#define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a)) 
#define FOREACH(a, b) for (auto&(a) : (b)) 
#define rep(i, n) FOR(i, 0, n) 
#define repn(i, n) FORN(i, 1, n) 
#define MAX(a, b) a = max(a, b) 
#define MIN(a, b) a = min(a, b) 
#define SQR(x) ((LL)(x) * (x)) 
#define RESET(a, b) memset(a, b, sizeof(a)) 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back 
#define ALL(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz 
#define SIZE(v) (int)v.size() 
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v)) 
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) 
#define PERMUTE next_permutation 
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define TC(t) while (t--)

void solve()
{
  int n,k;
  cin>>n>>k;
  int a[n];
  rep(i,n) cin>>a[i];
  sort(a,a+n);
  LL res=0;
  rep(i,k)
  res+=a[i];
  cout<<res<<endl;
}
 
int main()
{
    IOS();
    solve();
    return 0;
}





Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main() {
    string s;
    cin>>s;
    int cnt=0,maxcnt=0;
    bool flagA=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='A'){
            flagA=1;
            cnt++;
        }
        else if(s[i]=='Z'&&flagA){
            cnt++;
            maxcnt=cnt;
        }
        else if(flagA)
            cnt++;
    }
    cout<<maxcnt<<endl;
    
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
int dp[100001][13];
int main() {
    std::string s;std::cin >> s;dp[0][0] = 1;REP(i, s.size())REP(j, 13) REP(k, 10)if(s[i] == '?' || s[i] - '0' == k)(dp[i + 1][(j * 10 + k) % 13] += dp[i][j]) %= 1000000007;std::cout << dp[s.size()][5];return 0;
}


Measured memory_bytes: 5504
import math
def lcm(x,y):
    return (x*y)//math.gcd(x,y)

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

x=lcm(a[0],a[1])
i=2
for i in range(n):
    x=lcm(x,a[i])
    
print(x)


Measured memory_bytes: 5668
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    S = input()
    if S.startswith('YAKI'):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9040
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        h: usize,
        w: usize,
        n: usize,
        a: [usize; n],
    }
    let mut ans = vec![vec![0; w]; h];
    let mut p = 0;
    let mut a = a;
    for i in 0..h {
        for j in 0..w {
            ans[i][j] = p + 1;
            a[p] -= 1;
            if a[p] == 0 {
                p += 1;
            }
        }
        if i % 2 == 1 {
            ans[i].reverse();
        }
    }
    let mut out = String::new();
    for a in ans {
        for a in a {
            out.push_str(&format!("{} ", a));
        }
        out.pop();
        out.push('\n');
    }
    print!("{}", out);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,n;
    cin>>k>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=1;i<n;i++)
    {
        b[i]=a[i]-a[i-1];   
    }
    b[0]=k-a[n-1]+a[0];
    sort(b,b+n);
    cout<<k-b[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 1792
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = [0 for _ in range(m)]

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum[i] = (a,b)

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    ctr = 0
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != n:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)
    


Measured memory_bytes: 3572
#ref : https://atcoder.jp/contests/abc128/submissions/5694292
#工事を座標順に処理，工事にぶつかる人をにぶたん
#すでに更新済みだったら更新しない．-> jumpで管理
from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')

Measured memory_bytes: 57636
#include <set>
#include <vector>
#include <iostream>
using namespace std;
int n, x[200009], vis[200009]; bool dp[200009][2]; vector<int> cyc, v, g[200009];
int grundy(int pos) {
	set<int> s;
	for (int i : g[pos]) {
		if(!vis[i]) s.insert(grundy(i));
	}
	int ret = 0;
	while (s.count(ret)) ret++;
	return ret;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> x[i], g[--x[i]].push_back(i);
	int pos = 0;
	while (!vis[pos]) vis[pos] = true, pos = x[pos];
	fill(vis, vis + n, false);
	while (!vis[pos]) vis[pos] = true, cyc.push_back(pos), pos = x[pos];
	for (int i : cyc) v.push_back(grundy(i));
	int c = v.size(); bool flag = false;
	for (int i = 0; i < 2; i++) {
		dp[0][i] = true; dp[0][i ^ 1] = false;
		for (int j = 0; j < c; j++) {
			dp[j + 1][0] = dp[j + 1][1] = false;
			if (dp[j][0]) {
				if (v[(j + 1) % c] != v[j]) dp[j + 1][0] = true;
				if (v[(j + 1) % c] + 1 != v[j]) dp[j + 1][1] = true;
			}
			if(dp[j][1]) {
				if (v[(j + 1) % c] == v[j]) dp[j + 1][0] = true;
				if (v[(j + 1) % c] + 1 == v[j]) dp[j + 1][1] = true;
			}
		}
		if (dp[c][i]) flag = true;
	}
	cout << (flag ? "POSSIBLE" : "IMPOSSIBLE") << endl;
	return 0;
}

Measured memory_bytes: 14324
lst = []
ans = True
for _ in range(int(input())):
    a = input()
    if len(lst) == 0:
        lst.append(a)
    else:
        x = lst[len(lst)-1]
        if x[len(x)-1] != a[0] or a in lst:
            ans = False
            break
        lst.append(a)
print("Yes" if ans is True else "No")


Measured memory_bytes: 3060
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#define ll long long
#define fi first
#define se second
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
const int INF=0x7fffffff;
const double EPS=1e-6;
const int MAX_N=300000+5;
char s[MAX_N];
char a[MAX_N];
char b[MAX_N];
int main (void)
{
    int n;
    int i,j,k;
    scanf("%s%d",s,&n);
    int mark=1;
    int ak=0;
    int bk=0;
    while(n--)
    {
        int q;
        scanf("%d",&q);
        if(q==1)
            mark^=1;
        else
        {
            int p;
            char c;
            scanf("%d%*c%c",&p,&c);
            //cout<<p<<' '<<c<<endl;
            if(p==1)
            {
                if(mark)
                    a[ak++]=c;
                else
                    b[bk++]=c;
            }
            else
            {
                if(mark)
                    b[bk++]=c;
                else
                    a[ak++]=c;
            }
        }
    }
    if(mark)
    {
        for(i=ak-1;i>=0;i--)
            printf("%c",a[i]);
        for(i=0;i<=strlen(s)-1;i++)
            printf("%c",s[i]);
        for(i=0;i<bk;i++)
            printf("%c",b[i]);
    }
    else
    {
        for(i=bk-1;i>=0;i--)
            printf("%c",b[i]);
        for(i=strlen(s)-1;i>=0;i--)
            printf("%c",s[i]);
        for(i=0;i<ak;i++)
            printf("%c",a[i]);
    }
}

Measured memory_bytes: 896
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        long a[] = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Arrays.sort(a);

        final long aMax = (long) Math.pow(10, 18);

        if (a[0] == 0) {
            System.out.println(0);
            return;
        }

        long result = 1;
        for (long l : a) {
            if (result > aMax / l) {
                System.out.println(-1);
                return;
            }
            result *= l;
        }
        System.out.println(result);

    }
}

Measured memory_bytes: 61264
#include<iostream>
#include<string>
#include<map>

using namespace std;

int main(){
		string X,Y;
		map<char,int>num;
		num['A']=10;	num['B']=11;	num['C']=12;
		num['D']=13;	num['E']=14;	num['F']=15;
		cin>>X>>Y;
		if(num[X[0]]>num[Y[0]])cout<<">\n";
		else if(num[X[0]]<num[Y[0]])cout<<"<\n";
		else cout<<"=\n";

		return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char b;
  cin >> b;
  if(b=='A'){
    cout << 'T';
  }
  if(b=='T'){
    cout << 'A';
  }
  if(b=='C'){
    cout << 'G';
  }
  if(b=='G'){
    cout << 'C';
  }
}

Measured memory_bytes: 256
#include <iostream>

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

    int i = 1;
    bool isProgress = true;
    while (isProgress) {
        if (i % 2 == 0) {
            // 青木
            a = a - d;
            if (a <= 0) {
                std::cout << "No";
                isProgress = false;
            }
        } else {
            // 高橋
            c = c - b;
            if (c <= 0) {
                std::cout << "Yes";
                isProgress = false;
            }
        }

        i++;
    }

    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define INF 10000000000
using namespace std;
using ll = long long;
int main()
{
    int n,a;
    cin >> n >> a;
    n %= 500;
    if(max(0,n-a)){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

str_in = input()
str_set = set(str_in)

if len(str_in) != 4:
    print('No')
    quit()

if len(str_set) != 2:
    print('No')
    quit()

for s in str_set:
    if str_in.count(s) != 2:
        print('No')
        quit()

print('Yes')



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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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 (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define VIN(x) for(auto&youso_: (x) )cin>>youso_
#define VOUT(x, delim) for(auto&youso_: (x) )cout<<youso_<<delim;cout<<endl

#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) i64 __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


using T = tuple<i64, i64, i64>; // ins < del < query

int main() {
    CIN(N, Q);

    vector<T> event;
    REP(i, N) {
        CIN(s, t, x);
        event.emplace_back(s - x, 0L, x);
        event.emplace_back(t - x, 1L, x);
    }

    REP(i, Q) {
        CIN(d);
        event.emplace_back(d, 2L, i);
    }
    ALL(sort, event);

    vector<i64> ans(Q);
    multiset<i64> se;
    for (auto [t, type, v] : event) {
        if (type == 0) {
            se.insert(v);
        } else if (type == 1) {
            se.erase(se.lower_bound(v));
        } else {
            if (se.empty()) ans[v] = -1;
            else ans[v] = *(se.begin());
        }
    }

    VOUT(ans, endl);

    return 0;
}


Measured memory_bytes: 27996
N,K=[int(x) for x in raw_input().split()]
A=[int(x) for x in raw_input().split()]
B=[-1 for i in range(K+1)]
F=[]
n=0
for i in range(A[0]):
    B[i]=0
for i in range(A[0],K+1):
    tmp= [B[i-a] for a in A if i-a>-1]
    if sum(tmp) == len(tmp):
        B[i]=0
    else:
        B[i]=1
print ["Second","First","bug"][B[K]]


Measured memory_bytes: 34152
#include <bits/stdc++.h>
using namespace std;
 int h, w;
 
bool check(int i, int j){
    if(i >= 0 && i < h && j >= 0 && j < w) return true;
    return false;
}

int main(){
    
    cin >> h >> w;
    
    vector<string>a(h);
    
    for(int i = 0; i < h; i++){
        cin >> a[i];
    }
    
    
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(a[i][j] == '#'){
                if(check(i-1, j)){
                    if(a[i-1][j] == '#'){
                        continue;
                    }
                }
                if(check(i, j-1)){
                    if(a[i][j-1] == '#'){
                        continue;
                    }
                }
                if(check(i+1, j)){
                    if(a[i+1][j] == '#'){
                        continue;
                    }
                }
                if(check(i, j+1)){
                    if(a[i][j+1] == '#'){
                        continue;
                    }
                }
                cout << "No" << endl;
                return 0;
                
            }
        }
    }
    cout << "Yes" << endl;
    
    
}


Measured memory_bytes: 3644
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  ll n;
  cin>>n;
  ll ans=1;
  ll mod = 1e9+7;
  for(int i = 1; i <= n; i++){
    ans*=i;
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define repi_(i,a,b) for(int i=(a), i##_len=(b); i<=i##_len; ++i)
#define rep_(i,n) repi_(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#define POSSIBLE(c) coc(c, "POSSIBLE", "IMPOSSIBLE")
#define Possible(c) coc(c, "Possible", "Impossible")
#define possible(c) coc(c, "possible", "impossible")
#define inf INT_MAX
#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif


typedef long long lint;
typedef vector<int> ivec; typedef vector<string> svec;

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

template<class T>inline bool maxi(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool mini(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }


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

	string s; cin >> s;
	int c[4] = { s[0] - '0', s[1] - '0', s[2] - '0', s[3] - '0' };
	lint cur = 0;
	rep(i, 8) {
		cur = c[0];
		repi_(j, 1, 3) {
			if (i&(int)pow(2, j-1))cur += c[j];
			else cur -= c[j];
		}
		if (cur == 7) {
			cout << s[0] << (i & 1 ? '+' : '-') << s[1] << (i & 2 ? '+' : '-') << s[2] << (i & 4 ? '+' : '-') << s[3] << "=7\n";
			break;
		}
	}
	gc();
}

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

int main(){
    ll n, a, b;
    cin >> n >> a >> b;

    ll k = b - a;
    if(k % 2 == 0){
        cout << k / 2 << endl;
    }else{
        ll d = (a - 1);
        ll m = (n - b);

        if(d <= m){
            cout << d + 1 + ((b - a - 1) / 2)<< endl;
        }else{
            cout << m + 1 + ((b - a - 1) / 2) << endl;
        }
    }
}

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

int N; //頂点の数
vector<vector<int>> G; //グラフ
vector<int> h; //入次数
vector<int> l_depth; //最大経路長
vector<int> ans; //トポロジカルソート結果を格納

void input(){
  int n;
  cin>>n;
  vector<vector<int>> IDs(n, vector<int>(n, -1));
  N = n*(n-1)/2;
  G.resize(N);
  h.resize(N, 0);
  l_depth.resize(N, -1);

  int id = 0;
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      IDs[i][j] = id;
      IDs[j][i] = id;
      id++;
    }
  }

  int t, bufid, vsid;
  for(int i=0; i<n; i++){
    bufid = -1;
    for(int j=0; j<n-1; j++){
      cin>>t;t--;
      vsid = IDs[i][t];

      if(bufid != -1){
        G[bufid].push_back(vsid);
        h[vsid]++;
      }

      bufid = vsid;
    }
  }
}

void topoBFS(){   
  queue<int> unchecked;
  for(int i=0; i<N; i++){
    if(h[i]==0){
      unchecked.push(i); //入次数が0の頂点をキューに入れる
      l_depth[i] = 0; //そのような頂点は深さが0
    }
  }
  while(!unchecked.empty()){
    int current = unchecked.front();
    unchecked.pop();
    ans.push_back(current); //キューから取り出したらすぐソート後のリストに加える

    for(int next: G[current]){ //「行ける」頂点について
      h[next]--; //入次数を減らす
      l_depth[next] = max(l_depth[next], l_depth[current]+1); //最長経路
      if(h[next]==0){ //入次数0になったらキューに追加
        unchecked.push(next);
      }
    }
  }
}

int main(){
  input();
  
  topoBFS();

  bool isDAG = ans.size()==N;
  if(isDAG){
    int l_max = *max_element(l_depth.begin(), l_depth.end());
    cout<<l_max+1<<endl;
  }else{
    cout<<-1<<endl;
  }
}

Measured memory_bytes: 40324
#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 main(){
    int n;
    cin >> n;
    int a[n], mi=1000, ma=0;
    rep(i, n){
        cin >> a[i];
        mi=min(mi, a[i]);
        ma=max(ma, a[i]);
    }

    int ans=ma-mi;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z temp.cpp
//./a.exe



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


int n,p[10000],m = 0,ans = 0;
cin >> n;
rep(i,n){
    cin >> p[i];
}

rep(i,n){
    m = max (m,p[i]);
}

rep(i,n){
    ans += p[i];
}

cout << ans-m/2 << endl;







//////////////////////////////////////////////////////
return 0;}

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

#define ll long long
#define ull unsigned long long

using namespace std;

int main(){
	ull N;
	cin >> N;
	vector <int> A(N, 0);
	for (int ii = 0; ii < N; ++ii){
		cin >> A[ii];
	}

	ull ans = 0;
	ull L = 0;
	ull R = 1;
	ull tmp = A[0];
	while(true){
		if ( ((tmp ^ A[R]) == (tmp + A[R])) && (R < N) ){
			tmp += A[R];
			R++;
		} else {
			ans += R - L;
			tmp -= A[L];
			L++;
			if (L == R){
				if (R == N){
					break;
				} else {
					tmp = A[R];
					R++;
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
using namespace std;
int main(){
  int d;
  cin>>d;
  if(d==25) cout<<"Christmas"<<endl;
  if(d==24) cout<<"Christmas Eve"<<endl;
  if(d==23) cout<<"Christmas Eve Eve"<<endl;
    if(d==22) cout<<"Christmas Eve Eve Eve"<<endl;
 return 0 ;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 1000000
const int mod = 998244353;

int n;
int A[N+1];
int inv[N+1];
int phi[N+1];

/*
\sum_{i<j} lcm(Ai,Aj)
\sum_{i<j} Ai Aj / gcd(Ai,Aj)
\sum_{d} 1/d \sum_{i<j: gcd(Ai, Aj) = d} Ai Aj

f(d) = \sum_{i,j: gcd(Ai, Aj) = d} Ai Aj
F(d) = \sum_{i,j: d | gcd(Ai, Aj)} Ai Aj
F(d) = \sum_{i,j: d | Ai, d | Aj)} Ai Aj
F(d) = (\sum_{i: d | Ai} Ai)^2
\sum_{d} 1/d \sum_{n: d|n} m(n/d) F(n)
\sum_{n} F(n) \sum_{d: d|n} 1/d m(n/d)
*/

int main(){
  int i, j, r, s;
  scanf("%d", &n);
  s = 0;
  for(i=0;i<n;i++){
    int x;
    scanf("%d",&x);
    A[x]++;
    s += x;
    if(s >= mod) s -= mod;
  }
  inv[1] = 1;
  for(i=2;i<=N;i++) inv[i] = (long long) (mod - mod/i) * inv[mod%i] % mod;

  for(i=1;i<=N;i++){
    phi[i] += inv[i];
    if(phi[i] >= mod) phi[i] -= mod;
    for(j=2*i;j<=N;j+=i){
      phi[j] -= phi[i];
      if(phi[j] < 0) phi[j] += mod;
    }
  }

  for(i=1;i<=N;i++){
    A[i] = (long long) i * A[i] % mod;
    for(j=2*i;j<=N;j+=i){
      A[i] = (A[i] + (long long) j * A[j]) % mod;
    }
  }

  for(i=1;i<=N;i++){
    A[i] = ((long long) A[i] * A[i]) % mod;
  }
  r = mod-s;
  for(i=1;i<=N;i++){
    r = (r + (long long) A[i] * phi[i]) % mod;
  }



  printf("%d\n", r&1?(r+mod)/2:r/2);

  return 0;
}


Measured memory_bytes: 11904
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    string s;
    vector<int> arr(26, 0);
    cin >> s;
    for(char c: s)
        arr[c-'a'] = 1;
    if (accumulate(arr.begin(), arr.end(), 0) == s.size())
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    return 0;
}


Measured memory_bytes: 3568
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
ll N;
ll a[201010];
ll xsum;

int main() {
  //
  cin >> N;
  rep(i, 0, N) {
    cin >> a[i];
    xsum = xsum ^ a[i];
  }
  rep(i, 0, N) {
    ll ans = xsum ^ a[i];
    cout << ans << "\n";
  }
}


Measured memory_bytes: 5084
/// You just can't beat the person who never gives up
/// ICPC next year


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) ((long long)(x).size())
#define all(x)  x.begin(),x.end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define leastsigbit(x)     __builtin_ffs(x)
#define mod             1000000007
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define pii pair<ll,ll>
#define vpii vector<pii>
#define tt ll tt;cin >> tt;while(tt--)
#define  fio ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define D1(x) { cerr << " [" << #x << ": " << x << "]\n"; }
#define D2(x) { cerr << " [" << #x << ": "; for(auto it:x) cerr << it << " "; cerr << "]\n";}
const double PI = acos(-1);
ll power(ll a,ll b,ll m=mod){ ll ans=1; a=a%m;  while(b>0) {  if(b&1)  ans=(1ll*a*ans)%m; b>>=1;a=(1ll*a*a)%m;}return ans;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm( ll x, ll y) { return (x*y)/gcd(x,y);}
bool isprime(ll n){if(n < 2) return 0; ll i = 2; while(i*i <= n){if(n%i == 0) return 0; i++;} return 1;}
bool isPowerOfTwo(int x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));
}
void offset(vector<int>&a,int x) {
    for(int i = 0; i < sz(a);i++) {
        a[i] = x;
    }
}
struct cmp {
    bool operator() (const pair<int,int>& lhs, const pair<int,int>& rhs) const {
        return lhs.ff * rhs.ss < lhs.ss * rhs.ff;
    }
//for map<pii,int>
};


// auto cmp = [](pair<int,int>a,pair<int,int>b) {if(a.first==b.first)return a.second>b.second;
//      else return a.first > b.first;
//  };
//  multiset<pair<int,int>,decltype(cmp)>fc(cmp);
double distform(int x, int y, int z, int w) {//(x1,y1,x2,y2)
    return sqrt(1. * pow(x-z,2) + 1. * pow(y-w,2));
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    //unordered_map<long long, int, custom_hash> safe_map;
};

const int MAXN = 2e5+ 10;

#define int long long
bool cmps(pair<int,int>p1,pair<int,int>p2) {
    return p1.ss > p2.ss;
}
int32_t main() {
    fio
    int n;
    cin >>n;
    string str;
    cin>>str;
    map<char,int>m;
    m['W']; m['R'];
    for(int i=0;i<str.size();i++){
        m[str[i]]++;
    }
    string ans;
    int count=0;
    for(int i=0;i<m['R'];i++)
        ans+='R';
    for(int i=0;i<m['W'];i++)
        ans+='W';
    for(int i=0;i<ans.size();i++){
        if(ans[i]!=str[i])
            count++;
    }
    cout<<count/2<<endl;
    return 0;

    cerr <<endl <<"[ Time : " << (float)clock() / CLOCKS_PER_SEC << " secs ]" << endl;


}






Measured memory_bytes: 3872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
const int INF=1e9+5;
const int N=2e5+5;
const ll oo=1e18+5;
const ll mod=1e9+7;

int n,k;

int mul(int a,int b){
	return 1ll*a*b%mod;
}

int poww(int a,int b){
	int r=1;
	while(b){
		if(b&1){
			r=mul(r,a);
		}
		a=mul(a,a);
		b>>=1;
	}
	return r;
}

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

void sub_self(int& a,int b){
	a-=b;
	if(a<0) a+=mod;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	int ans=0;
	vector<int> cnt(k+1);
	for(int i=k;i>=1;--i){
		cnt[i]=poww(k/i,n);
		for(int j=i+i;j<=k;j+=i){
			sub_self(cnt[i],cnt[j]);
		}
		add_self(ans,mul(cnt[i],i));
	}
	cout<<ans;
	return 0;
}


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


int main() {
  int N;
  int M;
  cin >> N >> M;
  int sum =0;
  
  vector<int> A(M);
  
  for (int i = 0; i < M; i++) {
    cin >> A.at(i);
  }
  
  for (int i =0; i < M; i++) {
    sum += A.at(i);
  }
  
  if (sum > N){
    cout << -1 << endl;
  }
  else{
    cout << N - sum << endl;
  }
}



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

int main(){

  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int N;//社員の人数
  int c,sum = 0;

  cin >> N;

  int A[N];

  for(int i=0;i<N;i++){
    A[i] = 0;
  }
  for(int i=0;i<N-1;i++){
    cin >> c;
    A[c-1]++;
  }

  for(int j=0;j<N;j++){
    cout << A[j] << endl;
  }

}


Measured memory_bytes: 4400
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner (System.in);
		double n = sc.nextInt();
		double div = n;
		double count = 0;
		while (n>=1) {
			if (n%2 == 1) {
				count++;
			}
			n--;
		}
		double val = count / div;
		System.out.printf("%.10f \n", val);
	}
}


Measured memory_bytes: 35984
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  long long x; cin >> x;
  vector<long long> height(n+1);
  height[0] = 1;
  FOR(i, 1, n+1) {
    height[i] = height[i-1] * 2;
    height[i] += 3;
  }
  vector<long long> meet(n+1);
  meet[0] = 0;
  FOR(i, 1, n+1) {
    meet[i] = meet[i-1] * 2;
    meet[i] += 1;
  }
  long long ans = 0;
  for (int i = n; i >= 0; --i) {
    if (height[i] == x) {
      ans += meet[i] * 2 + 1;
      break;
    } else if (height[i]/2+1 == x) {
      ans += meet[i] + 1;
      break;
    } else if (height[i]/2+1 < x) {
      ans += meet[i] + 1;
      x -= height[i]/2+1;
    } else {
      --x;
    }
  }
  cout << ans << '\n';
  return 0;
}

// For AtCoder Problems

Measured memory_bytes: 256
import sys

def main():
    S = input()
    T = input()

    sl = len(S)
    tl = len(T)

    res = tl
    for i in range(sl-tl+1):
        count = 0
        s = S[i:i+tl]
        for ti, si in zip(T, s):
            if ti != si:
                count += 1
        if count < res:
            res = count

    print(res)

if __name__ == "__main__":
    main()

Measured memory_bytes: 67704
n=input()
n=int(n)
arr=list(map(int,input().rstrip().split()))
b=arr
count=0
for i in range(len(arr)-1):
    if arr[i+1]<arr[i]:
        count=count+(arr[i]-arr[i+1])
        arr[i+1]=arr[i+1]+(arr[i]-arr[i+1])
        
print(count)
    

        

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

void solve()
{
    char c;
    cin>>c;
    if(isupper(c)) cout<<"A";
    else cout<<"a";
}

int main(void){
    int t;//cin>>t;
    t=1;
    while(t--)
    solve();
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(){
	multiset<int> x;
	int n;
	cin>>n;
	int a[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		x.insert(a[i]);
	}
	for(int i=1;i<=n;i++){
		if(*--x.end()!=a[i]){
			cout<<*--x.end()<<endl;
		}else{
			cout<<*--(--x.end())<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 11776
package main

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

var sc = bufio.NewScanner(os.Stdin)

func contains(target string, list []string) bool {
	for _, r := range list {
		if target == r {
			return true
		}
	}
	return false
}

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

func nextInt() int {
	sc.Scan()

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

func nextF64() float64 {
	sc.Scan()

	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func isInteger(x float64) bool {
	return math.Floor(x) == x
}

func Ave(s []int) int {
	val := 0
	for _, i := range s {
		val += i
	}
	return int(val / len(s))
}
func cal(i int) (sum int) {
	for i != 0 {
		sum += i % 10
		i /= 10
	}
	return
}
func max(a []int) (idx int, val int) {
	max := a[0]
	idx = 0
	for j, i := range a {
		if max < i {
			max = i
			idx = j
		}
	}
	return idx, max
}

func draw(i int, a []int) (l []int) {
	// p = a[i]
	for j := i; j < len(a); j++ {
		if j != len(a)-1 {
			a[j] = a[j+1]
		} else if j == len(a)-1 {
			a = a[:len(a)-1]
		}
	}
	return a
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	var x []int
	var wa int
	out := math.MaxInt32

	for i := 0; i < n; i++ {
		x = append(x, nextInt())
	}

	sort.Ints(x)

	for i := x[0]; i <= x[len(x)-1]; i++ {
		wa = 0
		for _, j := range x {
			wa += int(math.Pow(float64(j-i), 2))
		}
		if out > wa {
			out = wa
		}
	}
	fmt.Println(out)

}


Measured memory_bytes: 1788
#include<stdio.h>

int n,A[50];

int solve(int i,int m){
if(m==0) return 1;
if(i>=n) return 0;
	int res = solve(i+1,m) || solve(i+1,m-A[i]);
	return res;
}

int main(){
int q,M,i;

scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",&A[i]);
scanf("%d",&q);
for(i=0;i<q;i++){
 scanf("%d",&M);
 if( solve(0,M) ) printf("yes\n");
else printf("no\n");
}

return 0;
}
 

Measured memory_bytes: 1804
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
l = []
for i in range(1, m):
  l.append(abs(x[i]-x[i-1]))
if n >= m:
  print(0)
else:
  l.sort()
  print(sum(l[:m-n]))

Measured memory_bytes: 20536
/**
 *    author:  tourist
 *    created: 11.05.2020 14:18:41       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  for (int it = 0; a > 0 && c > 0; it++) {
    if (it % 2 == 0) {
      c -= b;
    } else {
      a -= d;
    }
  }
  cout << (a > 0 ? "Yes" : "No") << '\n';
  return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
	int x,y;
}a[100001];
bool cmp(node x,node y)
{
	return x.x<y.x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].x);
		a[i].y=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	printf("%d ",a[i].y);
    return 0;
}

Measured memory_bytes: 1536