akhauriyash/Code-Regression huggingface dataset:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    n = int(input())
    pay = 800 * n
    back = (n // 15) * 200
    print(pay-back)
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 38508
#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 100000;
int c[maxn + 1], v[maxn + 1];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M, ans = 0;
    cin >> N >> M;
    for(int i = 1; i <= N; i += 1) c[i] = 1;
    v[1] = 1;
    for(int i = 1, x, y; i <= M; i += 1){
        cin >> x >> y;
        c[x] -= 1;
        c[y] += 1;
        if(v[x]) v[y] = 1;
        if(not c[x]) v[x] = 0;
    }
    for(int i = 1; i <= N; i += 1) ans += v[i];
    cout << ans;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<stack>
#include<string>

using namespace std;
int a[200];
int main(){
    string s;
    int a, b;
    a=b=0;
    cin >> s;
    for(int i=0;i<3;i++){
        if(s[i]=='A') a=1;
        if(s[i]=='B') b=1;
    }
    if(a==1&&b==1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter

n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]

cs = Counter(s)
ct = Counter(t)

ans = 0
for key in cs.keys():
    ans = max(ans, cs[key] - ct[key])

print(ans)


Measured memory_bytes: 3316
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.d = [-1] * n

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)


    def size(self, x):
        return -self.d[self.find(x)]


n, k, l = map(int, input().split())
uf1 = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    uf1.unite(p, q)
uf2 = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    uf2.unite(r, s)
dic = {}
for i in range(n):
    val = (uf1.find(i), uf2.find(i))
    if val in dic:
        dic[val] += 1
    else:
        dic[val] = 1

for i in range(n):
    print(dic[(uf1.find(i), uf2.find(i))])

Measured memory_bytes: 41184
import collections


def solve(n, balls):
    counts = collections.Counter(balls)

    totalWays = 0

    for count in counts.values():
        totalWays += count*(count-1)//2

    results = []

    for ball in balls:
        waysWithoutBall = totalWays - (counts[ball]*(counts[ball]-1)//2)

        results.append(waysWithoutBall +
                       ((counts[ball]-1)*(counts[ball]-2)//2))

    return results


n = int(input().strip())
balls = list(map(int, input().strip().split()))

results = solve(n, balls)

for result in results:
    print(result)


Measured memory_bytes: 27268
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <iomanip>
#include <numeric>
using namespace std;

struct obj 
{
	int t;
	int x;
	int y;
};

int main()
{
	int N;
	cin >> N;
	vector<obj> list(N);
	for (int i = 0; i < N; i++)
	{
		obj item;
		cin >> item.t >> item.x >> item.y;
		list[i] = item;
	}

	bool result = true;
	for (int i = 0; i < N; i++)
	{
		obj item = list[i];

		int modt = item.t % 2;
		int modd = (item.x + item.y) % 2;

		if (item.x + item.y > item.t)
		{
			result = false;	
			break;
		}

		if (modt != modd)
		{
			result = false;	
			break;
		}

	}

	if (result)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}

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

using ll = long long;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SIZE(a) ((int)(a).size())

const int N = 2005;

int n, m, q;
char s[N][N];

int s1[N][N], s2[N][N], s3[N][N];

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

	cin >> n >> m >> q;
	REP(i, n) cin >> (s[i+1] + 1);

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (s[i][j] == '1') {
				++s1[i][j];
				if (j > 1 && s[i][j-1] == '1') ++s2[i][j];
				if (i > 1 && s[i-1][j] == '1') ++s3[i][j];
			}
			s1[i][j] += s1[i-1][j] + s1[i][j-1] - s1[i-1][j-1];
			s2[i][j] += s2[i-1][j] + s2[i][j-1] - s2[i-1][j-1];
			s3[i][j] += s3[i-1][j] + s3[i][j-1] - s3[i-1][j-1];
		}
	}

	REP(i, q) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		--x1; --y1;
		int x = s1[x2][y2] - s1[x1][y2] - s1[x2][y1] + s1[x1][y1];
		++y1;
		int y = s2[x2][y2] - s2[x1][y2] - s2[x2][y1] + s2[x1][y1];
		--y1; ++x1;
		int z = s3[x2][y2] - s3[x1][y2] - s3[x2][y1] + s3[x1][y1];
		int result = x-y-z;
		cout << result << '\n';
	}

	return 0;
}

Measured memory_bytes: 52864
N, M = map(int, input().split())
if N == 1 and M == 1:
    print(1)
elif N == 1 and M > 1:
    print(M-2)
elif M == 1 and N > 1:
    print(N-2)
elif N > 1 and M > 1:
    print((N-2)*(M-2))


Measured memory_bytes: 2940
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, long long K){
  ll i=0;
  while(N) {
    i++;
    N/=K;
  }
  std::cout << i << std::endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  long long K;
  scanf("%lld",&K);
  solve(N, K);
  return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
		int[] h = new int[n];
		for(int i=0;i<n;i++) {
			x[i] = in.nextInt();
			y[i] = in.nextInt();
			h[i] = in.nextInt();
		}
		int H = 0;
		int cx = 0;
		int cy = 0;
		boolean flag = false;
		for(cx=0;cx<=100;cx++) {
			for(cy=0;cy<=100;cy++) {
				int i = 0;
				H = 0;
				for(i=0;i<n;i++) {
					if(h[i]==0) continue;
					H = h[i] + Math.abs(x[i]-cx) + Math.abs(y[i]-cy);
					break;
				}
				for(i=0;i<n;i++) {
					if(H != h[i] + Math.abs(x[i]-cx) + Math.abs(y[i]-cy)) {
						if(h[i]==0 && H-Math.abs(x[i]-cx)-Math.abs(y[i]-cy)<0) continue;
						break;
					}
				}
				if(i==n) {
					flag = true;
					break;
				}
			}
			if(flag) break;
		}
		System.out.println(cx+" "+cy+" "+H);

	}

}


Measured memory_bytes: 23124
import sys
import math
import collections
n = int(input())
#n, k = map(int, input().split())
#s = input()
x = list(map(int, input().split()))

ans = 1000000
for i in range(1,101):
  p = 0
  for j in range(n):
    p += abs(x[j]-i) ** 2

  if p < ans:
    ans = p

print(ans)


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

template <class T>
inline void read(T &x)
{
	static char ch; 
	static bool opt; 
	while (!isdigit(ch = getchar()) && ch != '-'); 
	x = (opt = ch == '-') ? 0 : ch - '0'; 
	while (isdigit(ch = getchar()))
		x = x * 10 + ch - '0'; 
	if (opt)
		x = ~x + 1; 
}

template <class T>
inline void putint(T x)
{
	static char buf[45], *tail = buf; 
	if (!x)
		putchar('0'); 
	else
	{
		if (x < 0)
			putchar('-'), x = ~x + 1; 
		for (; x; x /= 10) *++tail = x % 10 + '0'; 
		for (; tail != buf; --tail) putchar(*tail); 
	}
}

template <class T>
inline bool tense(T &x, const T &y)
{
	return y < x ? x = y, true : false; 
}

template <class T>
inline bool relax(T &x, const T &y)
{
	return x < y ? x = y, true : false; 
}

using std::min; 
using std::max; 
using std::pair; 
using std::cin; 
using std::cout; 
using std::vector; 
typedef long long s64; 
typedef long double ld; 
typedef std::pair<int, int> pii; 
#define mp(x, y) std::make_pair(x, y)

const int MaxN = 5e2 + 5; 
const int MaxS = MaxN * MaxN; 

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

int n, s; 
int dis[MaxN][MaxN]; 
bool opt[MaxN][MaxN]; 

inline void bfs_init()
{
	static int que[MaxS][2]; 
	int qr = 0; 

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (dis[i][j])
			{
				++qr; 
				que[qr][0] = i; 
				que[qr][1] = j; 
			}

	for (int i = 1; i <= qr; ++i)
	{
		int x = que[i][0]; 
		int y = que[i][1]; 

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

			if (nx < 1 || ny < 1 || nx > n || ny > n)
				continue; 

			if (!dis[nx][ny])
			{
				dis[nx][ny] = dis[x][y] + 1; 

				++qr; 
				que[qr][0] = nx; 
				que[qr][1] = ny; 
			}
		}
	}
}

inline void bfs(int x, int y)
{
	static int que[MaxS][2]; 
	int qr = 1; 

	que[1][0] = x; 
	que[1][1] = y; 

	for (int i = 1; i <= qr; ++i)
	{
		int x = que[i][0]; 
		int y = que[i][1]; 

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

			if (nx < 1 || ny < 1 || nx > n || ny > n)
				continue; 

			if (tense(dis[nx][ny], dis[x][y] + opt[nx][ny]))
			{
				++qr; 
				que[qr][0] = nx; 
				que[qr][1] = ny; 
			}
		}
	}
}

int main()
{
	read(n); 
	s = n * n; 

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			opt[i][j] = true; 
	for (int i = 1; i <= n; ++i)
		dis[1][i] = dis[i][1] = dis[n][i] = dis[i][n] = 1; 
	bfs_init(); 

	int res = 0; 
	for (int i = 1; i <= s; ++i)
	{
		int p; 
		read(p); 

		int x = (p - 1) / n + 1, y = p - (x - 1) * n; 

		// std::cerr << x << ' ' << y << ':' << dis[x][y] << '\n'; 
		res += --dis[x][y], opt[x][y] = false; 

		bfs(x, y); 
	}

	std::cout << res << '\n'; 

	return 0; 
}

Measured memory_bytes: 8760
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define lamsort(v,p) sort(v.begin(),v.end(),[](p a, p b){return a.num < b.num;});
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
const long long INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll x, y; cin >> x >> y;
    ll mod = 1000000007;
    if((x+y)%3!=0) {
        cout << 0 << endl;
        return 0;
    }
    if(min(x,y)*2<max(x,y)) {
        cout << 0 << endl;
        return 0;
    }
    ll left = (x+y)/3;
    ll right = (x+y)/3*2 - x;
    ll ans = 1;
    ll ans2 = 1;
    ll num = right;
    rep(i,num) {
        ans *= (left-i);
        ans2 *= (right-i);
        ans %= mod;
        ans2 %= mod;
    }
    cout << ans*modinv(ans2,mod) %mod << endl;


    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,N-1,0)
#define RREPS(i,n) RFOR(i,N,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;

signed main(){
    int H,W,A,B;cin>>H>>W>>A>>B;
    char Z[H][W];
    REP(i,H)REP(j,W)Z[i][j]='0';
    REP(i,B)REP(j,A)Z[i][j]='1';
    REP(i,H-B)REP(j,W-A)Z[B+i][A+j]='1';
    REP(i,H){
        REP(j,W)cout<<Z[i][j];
        cout<<endl;
    }
}


Measured memory_bytes: 2176
from sys import stdin
from decimal import Decimal
def main():
    #入力
    readline=stdin.readline
    li=readline().strip().split()
    a=Decimal(str(li[0]))
    b=Decimal(str(li[1]))
    ans=int(a*b)
    print(ans)

if __name__=="__main__":
    main()

Measured memory_bytes: 10064
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define jkl int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<int, Pi> V;
typedef vector<ll> VE;
const ll mod = 1e10 + 7; //10^9+7


int main(){
    ll n;
    ll a[200002];
    ll X = 0, sum = 0;
    cin >> n;
    REP(i, n){
        cin >> a[i];
        X += a[i];
    }
    jkl;
    ll ans = mod;
    ll x, y;
    REP(i, n){
        sum += a[i];
        y = X - sum;
        if(i < n - 1)ans = min(ans, abs(sum - y));
    }
    print(ans);
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))

long long gcd(long long x,long long y){
	if(y==0)return x;
	return gcd(y,x%y);
}

int main(){
	long long a[3],m[3],t[3],cnt,n;
	for(;;){
		rep(i,3)cin >> a[i] >> m[i];
		if(a[0]==0)break;
		rep(i,3){
			t[i]=1;
			cnt=0;
			do{
				t[i]=(a[i]*t[i])%m[i];
				cnt++;
			}while(t[i]!=1);
			t[i]=cnt;
		}
		rep(i,2){
			n=gcd(t[2],t[i]);
			t[2]=(t[2]/n)*t[i];
		}
		cout << t[2] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
#define pw(x) (1LL<<(x))
static const int fast_io = [](){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();
static const int precise_doubles = [](){cout<<fixed<<setprecision(20);return 0;}();
typedef pair<int, int> PII;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(k) - iterator to kth largest, order_of_key(k) - #things < k
typedef long double LD;
typedef long long LL;
#define EVAL(x) x
#define SPA(x) EVAL({cout << #x" = " << x << ' ';})
#define NEWL EVAL({cout << '\n';})
#define SPAR(a, b) EVAL({cout<<#a" = ";for(auto it=a;it!=b;)cout<<*(it++)<<" ";cout<<'\n';})
#define SPAV(v) EVAL({cout<<#v" = ";for(auto it=v.begin();it!=v.end();)cout<<*(it++)<<" ";cout<<'\n';})
const int INF = 0x3f3f3f3f; // 1.0e9
const LL LINF = 0x3f3f3f3f3f3f3f3fll; // 4.5e18
const LD eps = 1e-20;
const int mod = 3;
inline int msum(int x, int y) {return (x+y<mod ? x+y : x+y-mod);}
inline int mdif(int x, int y) {return (x>=y ? x-y : x-y+mod);}
inline int mprod(int x, int y) { return (1ll*x*y) % mod; }
inline int mpow(int x, LL y) {LL r=1;while(y){if(y&1)r=mprod(r,x);x=mprod(x,x);y>>=1;}return r;}
inline int minv(int x) { return mpow(x, mod-2); }
#define DIE EVAL({cout << -1 << '\n'; exit(0);})
//------------------------------------------------------------------------------------------------------

const int N = 2e5 + 10;
int n, k;
vector<pair<LL, int>> events;
const int base = (1<<18);
int seg[base<<1];

void update(int pos, int val) {
    for(int u = base+pos; u > 0; u >>= 1) {
        seg[u] += val;
    }
}

int query(int l, int r, int u = 1, int L = 0, int R = base-1) {
    if(l == L and r == R) return seg[u];
    int M = (L+R)>>1;
    if(r <= M) return query(l, r, u<<1, L, M);
    if(l > M) return query(l, r, u<<1|1, M+1, R);
    return query(l, M, u<<1, L, M) + query(M+1, r, u<<1|1, M+1, R);
}

int main() {
    cin >> n >> k;
    LL sum = 0;
    events.push_back({0, 0});
    FOR(i, 1, n+1) {
        int a; cin >> a;
        sum += a;
        events.push_back({sum - (LL)k*i, i});
    }
    sort(events.begin(), events.end());
    LL ans = 0;
    for(auto e : events) {
        int pos = e.second;
        ans += query(0, pos);
        update(pos, 1);
    }
    cout << ans << '\n';
}






























Measured memory_bytes: 6256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
/*-------------------------------------------*/

class FastFourierTransform {
    static void dft(vector<complex<double>> &func, int inverse) {
        int sz = func.size();
        if(sz == 1) return;
        vector<complex<double>> va, vb;
        rep(i, sz / 2) {
            va.push_back(func[2 * i]);
            vb.push_back(func[2 * i + 1]);
        }
        dft(va, inverse);
        dft(vb, inverse);
        complex<double> now(1);
        complex<double> zeta(polar(1.0, inverse * 2.0 * acos(-1) / sz));
        rep(i, sz) {
            func[i] = va[i & (sz >> 1) - 1] + now * vb[i & (sz >> 1) - 1];
            now *= zeta;
        }
    }

  public:
    template <typename T>
    static vector<double> multipli(const vector<T> &f, const vector<T> &g) {
        vector<complex<double>> nf, ng;
        int sz = 1;
        int n = f.size() + g.size();
        while(sz < n)
            sz <<= 1;
        nf.resize(sz);
        ng.resize(sz);
        rep(i, f.size()) nf[i] = f[i];
        rep(i, g.size()) ng[i] = g[i];
        dft(nf, 1);
        dft(ng, 1);
        rep(i, sz) nf[i] *= ng[i];
        dft(nf, -1);
        vector<double> res;
        for(const auto &z : nf)
            res.push_back(z.real() / sz);
        return res;
    }
};

constexpr int P = 200003;
int mul[P], inv[P];

ll ans;

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

    int num = 1;
    FOR(i, 0, P - 1) {
        mul[i] = num;
        inv[num] = i;
        num = num * 2 % P;
    }

    int n;
    cin >> n;
    vector<int> a(P - 1);
    rep(i, n) {
        int x;
        cin >> x;
        if(x != 0) {
            a[inv[x]]++;
            ans -= 1LL * x * x % P;
        }
    }

    vector<double> res = FastFourierTransform::multipli(a, a);

    rep(i, res.size()) ans += ll(res[i] + .5) * mul[i % (P - 1)];

    cout << ans / 2 << endl;

    return 0;
}

Measured memory_bytes: 38772
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> r(n);
	for(int i=0; i<m; i++){
		int a, b;
		cin >> a >> b;
		r[a-1]++;
		r[b-1]++;
	}
	for(int i=0; i<n; i++)
		cout << r[i] << '\n';
	return 0;
}

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

class P
{
    static void Main()
    {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(Math.Abs(s[1] - s[0]) > Math.Abs(s[2] - s[0]) ? "B" : "A");
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
int dy[]={1,-1,0,0};
int dx[]={0,0,1,-1};

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

  for(int i=0;i<N;i++){
    cin>>a[i]>>b[i]>>c[i];
  }
  vector<vector<ll>> dp(3,vector<ll>(N,1e12));
  dp[0][0]=a[0];
  dp[1][0]=b[0];
  dp[2][0]=c[0];
  for(int i=1;i<N;i++){
    dp[0][i]=max(dp[1][i-1],dp[2][i-1])+a[i];
    dp[1][i]=max(dp[0][i-1],dp[2][i-1])+b[i];
    dp[2][i]=max(dp[1][i-1],dp[0][i-1])+c[i];
  }
  cout<<max(dp[0][N-1],max(dp[1][N-1],dp[2][N-1]))<<endl;
  return 0;
}




Measured memory_bytes: 4608
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(mi())

as_mp = [(-1)*a if i%2==0 else a for i, a in enumerate(As)]
as_pm = [(-1)*a for a in as_mp]

x1_mb2 = sum(as_pm)
x2_mb2 = sum(as_mp) + As[0] + As[0]

x1 = x1_mb2 // 2

#print(x2_mb2)

Anss = [0] * N
Anss[0] = x1

prevans = x1
for i in range(N-1, 0, -1):
  prevans = As[i] - prevans
  Anss[i] = prevans

for eachans in Anss:
  print(eachans * 2)



Measured memory_bytes: 64112
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
const long long INF = numeric_limits<long long>::max();
int main()
{
    int N, D, X;
    cin >> N >> D >> X;
    vector<int> A( N );
    for( auto &x : A )
    {
        cin >> x;
    }
    int res = N;
    for( int i = 0; i < N; ++i )
    {
        for( int j = 1; j <= D; ++j )
        {
            if( A[ i ] * j + 1 <= D )
            {
                res += 1;
            }
        }
    }
    cout << res + X << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a = [LI() for _ in range(3)]
n = I()
b = [I() for _ in range(n)]
if n < 3:
    print('No')
    quit()
for i in range(3):
    for j in range(3):
        if a[i][j] not in b:
            break
    else:
        print('Yes')
        quit()

for i in range(3):
    for j in range(3):
        if a[j][i] not in b:
            break
    else:
        print('Yes')
        quit()

for i in range(3):
    if a[i][i] not in b:
        break
else:
    print('Yes')
    quit()

for i in range(3):
    if a[i][-(i+1)] not in b:
        break
else:
    print('Yes')
    quit()

print('No')

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var num = new List<string>();
            num.Add("3");
            num.Add("5");
            num.Add("7");
            for (int i = 1; i < N.ToString().Length; i++)
            {
                var tmp = new List<string>();
                foreach(var n in num)
                {
                    tmp.Add(n + "3");
                    tmp.Add(n + "5");
                    tmp.Add(n + "7");
                }
                foreach (var t in tmp) num.Add(t);
                num = num.Distinct().ToList();
            }
            num = num.Skip(12).ToList();
            var cnt = 0;
            foreach(var n in num)
            {
                var chk = int.Parse(n);
                if (chk > N) continue;
                var three = false;
                var five = false;
                var seven = false;
                while (chk > 0)
                {
                    var tmp = chk % 10;
                    chk /= 10;
                    if (tmp == 3) three = true;
                    else if (tmp == 5) five = true;
                    else if (tmp == 7) seven = true;
                }
                if (three && five && seven) cnt++;
            }
            
            Console.WriteLine(cnt);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 19808
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e5+5;

int n,a[N];
long long ans;

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		if(i==1||a[i]>=a[i-1]) continue;
		else {
			ans+=a[i-1]-a[i];
			a[i]=a[i-1];
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 4604
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for(int i = 1; i <= n; ++ i)
#define mem(x, y) memset(x, y, sizeof(x))
#define rep(i, a, b) for(int i = a; i <= b; i++)

using namespace std;

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	if(a + b == 15) { puts("+"); return 0; }
	if(a * b == 15) { puts("*"); return 0; }
	puts("x");
	return 0;
}

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

int main() {
    int N;

    cin>>N;
    vector <int> h(N);

    for(int i=0;i<N;i++){
        cin>>h.at(i);
    }
    int count=0;
    int marker=0;

    for(int i=0;i<N;i++){
        if(h.at(i)==(i+1)){
            if(marker==1){
                marker = 0;
            }else{
                count++;
                marker = 1;
            }
        }else{
            marker = 0;
        }

    }

    cout<<count<<endl;

    return 0;



}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int mod=2019;
int l,r;
inline int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}

int main(){
    int minn=2020;
    l=read(),r=read();
    for(int i=l;i<=r-1;++i){
        for(int j=i+1;j<=r;++j){
            int bz=((i%mod)*(j%mod))%mod;
            if(bz<minn) minn=bz;
            if(minn==0){
                printf("%d\n",minn);
                return 0;
            }
        }
    }
    printf("%d\n",minn);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100000

int parent(int i){
  return i/2;
}

int left(int i){
  return (2*i);
}
int right(int i){
  return ((2*i)+1);
}


int main(){
  int H, i, A[MAX+1];
  
  scanf("%d",&H);

  for(i=1;i<=H;i++){
    
    scanf("%d",&A[i]);
    
  }
  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(parent(i)>=1){
      printf("parent key = %d, ",A[parent(i)]);
    }
    if(left(i)<=H){
      printf("left key = %d, ",A[left(i)]);
    }
    if(right(i)<=H){
      printf("right key = %d, ",A[right(i)]);
    }
    printf("\n");
  }
  return 0;
}




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

int main() {
    long long n, m;
    cin >> n >> m;
    if (min(n, m) == 1) printf("%lld\n", max(1LL, max(n, m) - 2));
    else printf("%lld\n", (n - 2) * (m - 2));
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF (1LL<<61 + 1<<29)
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
void _OUTPUT_IMPL_() {};
template <class T, class... Args> void _OUTPUT_IMPL_(T dest, Args... args) { cout<< dest << (sizeof...(Args)?" ":""); _OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define out(...) _OUTPUT_IMPL_(__VA_ARGS__)
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

int main() {
	int f[200] = {}, r=0;
	in_v(int, t, 3);
	for (int i : t) {
		if (!f[i]) ++r;
		++f[i];
	}
	out(r);
}

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define CEIL(n, m) ceil(n/pow(10.0, m))*pow(10.0, m)
#define FLOOR(n, m) floor(n/pow(10.0, m))*pow(10.0, m)
#define ROUND(n, m) round(n/pow(10.0, m))*pow(10.0, m)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define llong long long
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve()
{
  vector<int> a(3);
  for (int i=0; i<3; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  cout << a[2]-a[0] << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
typedef long long ll;
ll MOD = 1e9+7;

using namespace std;

int main()
{
	ll a,b,x;
	ll ans=0;
	
	cin>>a>>b>>x;
	ans = (b/x+1);
	if(a!=0)
		ans-=(a-1)/x+1;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#ABC094C
N=int(input())
X=list(map(int, input().split()))
X_sorted=sorted(X)
small=X_sorted[int(N/2)-1]
large=X_sorted[int(N/2)]

for i in range(N):
    if X[i]<=small:
        print(large)
    else:
        print(small)


Measured memory_bytes: 25620
n=int(input())
List = [int(i) for i in input().split()]
ans = 0
Counter = 1
flag = 0
for i in range(n):
  tmp = List[i]
  if tmp==Counter:
    Counter+=1
    flag=1
  else:
   	ans+=1
if flag==0:
  print(-1)
else:
  print(ans)

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

using namespace std;

int main () {
	int n;
	cin >> n;
	vector <int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int ans = 0;
	for (int i = 0; i < n; i += 2)
		ans += (a[i] % 2);
	cout << ans;
	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os << *i << (i==end(v)-1 ? "" : "\n"); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is >> *i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
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;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int x,a,b;
    cin>>x>>a>>b;
    cout<<(abs(x-a)<abs(x-b)?"A":"B")<<endl;
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	int b, f, r, v, p = 0;
	int room[4][3][10] = { {} };
	for (int i = 0; i < n; i++) {
		cin >> b >> f >> r >> v;
		while (b < 1 && b > 4 && f < 1 && f > 3 && r < 1 && r > 10) {
			cin >> b >> f >> r >> v;
		}
		room[b - 1][f - 1][r - 1] = room[b - 1][f - 1][r - 1] + v;
		if (room[b - 1][f - 1][r - 1] > 9) {
			room[b - 1][f - 1][r - 1] = 9;
		}
		else if (room[b - 1][f - 1][r - 1] < 0) {
			room[b - 1][f - 1][r - 1] = 0;
		}
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 10; k++) {
				cout << " " << room[i][j][k];
			}
			cout << endl;
		}
		if (i < 3)
			cout << "####################" << endl;
	}
}


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

#define pb push_back

using namespace std;

int n, m, a[5000][5000], d[5000][5000];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        for(int j = 1; j <= m; j++)
            if(s[j - 1] == '#')
                a[i][j] = 1;
    }
    d[1][1] = 1;
    for(int i = 2; i <= n; i++){
        if(a[i][1] == 1)
            break;
        d[i][1] = 1;
    }
    for(int i = 2; i <= m; i++){
        if(a[1][i] == 1)
            break;
        d[1][i] = 1;
    }
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= m; j++)
            if(a[i][j])
                continue;
            else
                (d[i][j] += d[i - 1][j] + d[i][j - 1]) %= (int)1e9 + 7;
    cout << d[n][m];
}


Measured memory_bytes: 41984
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, x, sum, minx = 0x3f3f3f3f;
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) scanf("%d", &x), minx = min(minx, x), sum += x;
	printf("%d\n", (m - sum) / minx + n);
	return 0;
}

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


using namespace std;


typedef vector<int> vi;

#define looplr(i,l,r) for(int i=l;i<=r;++i)

#define pb push_back

//int arr[MAX];
int n,sum=0,sum1=0,sum2=0,tc,x,y,z,count1=0,count2=0,rem,a,b,c,d,l,r,m,len;
//string s,s1,s2;

int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//fastio;
vi v;
scanf("%d",&tc);
while(tc--){
scanf("%d",&n);
if(n==0) {
scanf("%d",&a);
v.pb(a);
}
else if(n==1) {
scanf("%d",&a);
printf("%d\n",v[a]);
}
else if (n==2){
v.pop_back();
}
}

//cout << clock()*1.0/ CLOCKS_PER_SEC << endl;
return 0;
}


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

int main(){
  int N,a;
  cin >> N;
  for(int i=9;i>0;i--){
    if(N%i==0){
      a = N/i;
      if(a<=9){
        cout << "Yes" << endl;
        return 0;
      }
      else{
        cout << "No" << endl;
        return 0;
      }
    }
  }    
}
  

Measured memory_bytes: 256
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <time.h>

#include <string>

struct Node {
    int color;
    std::vector<int> neighbor;
    int lock_dist;
};

const int MAX_N = 100050;
int N;
long long A[MAX_N];

std::vector<long long> vec;

bool condition(int idx) {
    long long tmp = 0;
    for (int i = 0; i <= idx; i++) {
        tmp += vec[i];
    }

    for (int i = idx + 1; i < N; i++) {
        if (vec[i] <= tmp * 2) {
            tmp += vec[i];
        } else {
            return false;
        }
    }
    return true;
}


int main(int argc, char **argv) {
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        std::cin >> A[i];
    }

    for (int i = 1; i <= N; i++) {
        vec.push_back(A[i]);
    }

    std::sort(vec.begin(), vec.end());

    if (condition(0)) {
        std::cout << N << std::endl;
        return 0;
    }

    int lb = 0;
    int ub = N - 1;

    while (lb + 1 < ub) {
        int mid = (lb + ub) / 2;
        if (condition(mid)) {
            ub = mid;
        } else {
            lb = mid;
        }
    }

    std::cout << N - ub << std::endl;

    return 0;
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
#define lli long long
int dp[100005];
int a[100005];

int main() 
{
    int n;
    cin >> n;
    
    for(int i=1;i<=n;i++) cin >> a[i];
    
    dp[0] = dp[1] = 0;
    
    dp[2] = dp[1] + abs(a[1]-a[2]);
    
    for(int i=3;i<=n;i++) dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]), dp[i-2]+abs(a[i-2]-a[i]));
    
    cout<<dp[n]<<endl;
    
	return 0;
}

Measured memory_bytes: 1024
#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(){
    string s;
    cin >> s;
    int q;
    cin >> q;
    bool rev = false;
    rep(i, q){
        int query;
        cin >> query;
        if(query==1){
            rev = !rev;
        }else{
            int query;
            char c;
            cin >> query >> c;
            if(query==1){
                if(rev) s.push_back(c);
                else s.insert(s.begin(), c);
            }else{
                if(!rev) s.push_back(c);
                else s.insert(s.begin(), c);
            }
        }
    }
    if(rev){
        reverse(s.begin(), s.end());
    }

    cout << s << endl;
    return 0;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2e5 + 5;
ll n, k;
int main() {
    cin >> n >> k;
    double ans = 0;
    for(ll i = 1; i <= n; i++) {
        ll c = i;
        double p = 1.0 / n ;
        while(c < k) {
            c *= 2;
            p /= 2;
        }
        ans += p ;
    }
    printf("%.45f", ans) ;
    return 0;
}
/*
100000 5
*/


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


int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i< n; i++) cin >> a[i];
  int sum_Al=0, sum_Bo=0;
  sort(a.begin(), a.end());
  while(a.size()){
    sum_Al += a.back();
    a.pop_back();
    //cout << "sizea: " << a.size() << endl;
    if(a.size() == 0) break;
    sum_Bo += a.back();
    a.pop_back();
    //cout << "sizeb: " << a.size() << endl;
  }
  cout << sum_Al - sum_Bo;
  return 0;
}  

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string>
#include<vector>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n0,n) for(int i=n0;i<n;i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)
#define W(x) cout<<x<<endl;
#define Debug(x) cout<<"#DEBUG "<<x<<endl;
#define INF (1<<29)
#define INF2 (long long)8*(long long)INF*(long long)INF
using namespace std;
int min(int x,int y){if(y<x)return y;else return x;}
int max(int x,int y){return x+y-min(x,y);}
//int fact(int x){int i=1;rep(j,x){i*=(j+1);} return i;}
long long fact(long long x){long long i=1;rep(j,x){i*=(j+1);} return i;}

int main()
{
    int n,k;
    cin>>n>>k;
    if((n-1)%(k-1)==0)
    {
        W((n-1)/(k-1))
        
    }
    else W((n-1)/(k-1)+1)
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long
const int N = 3000001;
const int mod = 1e9 + 7;
LL a[N + 20], fact[N + 20], inv[N + 20];
LL qpow(LL a, LL b, LL p = mod) {
	LL ans = 1;
	for (; b; b >>= 1) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
	}
	return ans % p;
}
void prework() {
	fact[0] = 1;
	for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % mod;
	inv[N - 1] = qpow(fact[N - 1], mod - 2) % mod;
	for (int i = N - 2; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
LL nCr(int n, int r) {  // calculate nCr
	if (n - r < 0 || r < 0) return 0;
	return fact[n] % mod * inv[r] % mod * inv[n - r] % mod % mod;
}
main() {
  int k; cin >> k;
  string s; cin >> s;
  int n = s.length();
  prework();
  int S = 26;  // alphabet size
  LL ans = 0;
  for (int r = n; r <= n + k; r++) {
    LL v = nCr(n + k, r) * qpow(S - 1, n + k - r) % mod;
    ans = (ans + v) % mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 51232
#include <stdio.h>
int main(void)
{
    int sum=0,ave=0;
    int l=0,m=0;
    int n = 0;
    while(scanf("%d,%d",&l ,&m) != EOF){
    	sum += l * m;
    	ave += m;
    	n++;
    }
	if(((double)ave/n)-(ave/n) >= 0.5){
		ave = ave/n+1;
	}else{
		ave = ave /n;
	}
	
	printf("%d\n%d\n" ,sum ,ave);
	return 0;
}

Measured memory_bytes: 592
#include <iostream>
using namespace std;
int main() {
	char A[3],B[3];
	for (int i = 0;i < 3;i++) {
		cin >> A[i];
	}
	for (int i = 0;i < 3;i++) {
		cin >> B[i];
	}
	for (int i = 0;i < 3;i++) {
		if (A[i] != B[2 - i]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}

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

using namespace std;

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0 ; i < n ; i++) cin >> a[i];
    
    int light = a[0];
    int count = 1;
    while(light != 2 && count <= n){
        light = a[light-1];
        count++;
    }
    
    if(count > n)
        cout << "-1" << endl;
    
    else
        cout << count << endl;
}


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

int main()
{
   //freopen("LCS.inp","r",stdin);
   int n,m;
   string s,t;
   getline(cin,s);
   getline(cin,t);
   n=s.length();
   m=t.length();
   int a[n],b[m],f[n+1][m+1];
   char c[m];
   for(int i=1;i<=n;i++)
   {
       a[i]=s[i-1]-48;
   }
   for(int i=1;i<=m;i++)
   {
       b[i]=t[i-1]-48;
   }
   for(int i=0;i<=n;i++)
   {
       f[i][0]=0;
   }
   for(int i=0;i<=m;i++)
   {
       f[0][i]=0;
   }
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=m;j++)
       {
           if(a[i]==b[j])
           {
             f[i][j]=f[i-1][j-1]+1;
           }
           else
            {
                f[i][j]=max(f[i-1][j],f[i][j-1]);
            }

       }
   }
   int i=n,j=m,k=1;
   while(i>0 && j>0)
   {
       if(a[i]==b[j])
       {
           c[k]=a[i]+48;
           k++;
           i--;
           j--;
       }
       else
        {
            if(f[i][j-1]==f[i][j]) j--;
             else
             {
                 i--;
             }
        }
   }
   for(int i=k-1;i>=1;i--)
   {
       cout<<c[i];
   }


}


Measured memory_bytes: 35456
#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#define ll long long
#define lson (rt<< 1)
#define rson (rt<< 1 | 1)
#define gmid ((l+r)>> 1 )
using namespace std;

const int maxn=20000050;
string s;
int main()
{
	ll n,t=1;
	cin>>n;
    while(n>0)
      {
      	  t=(n-1)%26;
      	  n=(n-1)/26;
      	  s=(char)('a'+t)+s;
      }
	cout<<s<<endl;  
	
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll,ll> p;
const int N = 5005;

ll dp[N][N];
p a[N];
int n;

bool cmp(p x,p y){
    return x.first+x.second < y.first+y.second;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].second >> a[i].first;
    }
    sort(a+1,a+n+1,cmp);
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            dp[i][j] = -1;
        }
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            dp[i][j] = dp[i-1][j];
            if(dp[i-1][j-1] != -1 && dp[i-1][j-1] <= a[i].second){
                if(dp[i][j] == -1){
                    dp[i][j] = dp[i-1][j-1] + a[i].first;
                }
                else{
                    dp[i][j] = min(dp[i][j],dp[i-1][j-1]+a[i].first);
                }

            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    int sol = 1;
    for(int i = 1; i <= n; i++){
        if(dp[n][i] != -1){
            sol = i;
        }
    }
    cout << sol << endl;
}


Measured memory_bytes: 195840
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <tuple>
#include <algorithm>
#include <array>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0; i<n; ++i)
inline constexpr ll Inf = (1ULL << 62) -1;

void updatemin(ll& a, ll b) { if (b < a) a = b; }

ll n=0, wmax=0;
vector<ll> w, v;

int main() {
    cin >> n >> wmax;
    w.resize(n);
    v.resize(n);
    rep(i,n) cin >> w[i] >> v[i];

    const ll maxsumv = 100*1000+1;
    vector<ll> dp(maxsumv, Inf); // minimum weight
    dp[0] = 0;
    rep(i,n) {
        for (ll j=maxsumv-v[i]-1; j >= 0; --j) {
            updatemin(dp.at(j+v[i]), dp.at(j) + w[i]);
        }
    }

    ll ans = 0;
    rep(i,maxsumv) {
        if (dp[i] <= wmax)
            ans = i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3664