akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, k;
long double ans, sum;
int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i){
		sum = (long double)1 / (long double)n;
		int j = i;
		while(j < k){
			j *= 2;
			sum *= (long double)1 / (long double)2;
		}
		ans += sum;
	}
	printf("%0.12Lf\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
//	cut here before submit 
//	freopen ("testcase.trading", "r", stdin );

	string str = "";
	map<int,int> last_month; last_month.clear();
	while (getline (cin, str ) ){
		if (str.empty() ) break;
		str = str.replace (str.find (','), 1, " " );
		stringstream ss (str );
		int id, day;
		ss >> id >> day;
		last_month[id]++;
	} // end loop

	map<int,int> curr_month; curr_month.clear();
	while (getline (cin, str ) ){
		str = str.replace (str.find (','), 1, " " );
		stringstream ss (str );
		int id, day;
		ss >> id >> day;
		curr_month[id]++;
	} // end while

	vector<P> res; res.clear();
	map<int,int>::iterator it = last_month.begin();
	for (; it != last_month.end(); it++ ){
		int id = (*it).first;
		int cnt = (*it).second;
		if (curr_month.count (id ) ){
			int cnt2 = curr_month[id];
			res.push_back (P (id, cnt+cnt2 ) );
		} // end if
	} // end for

	if (!res.empty() ) sort (ALL (res ) );
	rep (i, res.size() ){
		cout << res[i].first << ' ' << res[i].second << endl;
	} // end rep
		
	return 0;
}

Measured memory_bytes: 1228
import java.util.*;
public class Main
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int a=in.nextInt();
int b=in.nextInt();
int c=in.nextInt();
if(c>=a&&c<=b)
System.out.println("Yes");
else
System.out.println("No");
}
}

Measured memory_bytes: 23636
#[allow(unused_imports)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize, mut p: [usize; n]);
    let pp = p.clone();
    p.sort();

    let mut count = 0_usize;
    for i in 0..n {
        if p[i] != pp[i] {
            count += 1;
        }
    }

    println!("{}", if count <= 2 { "YES" } else { "NO" });
}


Measured memory_bytes: 2164
N = int(input())
A = list(map(int, input().split()))

L = [A[0]]
for i in range(1, N):
  if A[i] != A[i - 1]:
    L.append(A[i])

N = len(L)

if N == 1:
  print(1)
  exit()

f = L[1] > L[0]
ans = 1

i = 2
while i < N:
  if (L[i] > L[i - 1]) != f:
    ans += 1
    if i == N - 1:
      break
    i += 1
    f = L[i] > L[i - 1]

  i += 1
 
print(ans)

Measured memory_bytes: 91364
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	char a[3],b[3];
	int i;
	for(i=0;i<3;i++)
	cin>>a[i];
	for(i=0;i<3;i++)
	cin>>b[i];
	if(a[0]==b[2]&&a[1]==b[1]&&a[2]==b[0])
	cout<<"YES";
	else cout<<"NO";
	return 0;
}

Measured memory_bytes: 256
import sys
imput=sys.stdin.readline
n=int(input())
dp=[float('inf')]*(n+1)
dp[1]=1
i=0
while 9**i<=n:
    dp[9**i]=1
    i+=1
j=0
while 6**j<=n:
    dp[6**j]=1
    j+=1
#print(dp[1],dp[9],dp[36],dp[127])
for i in range(2,n+1):
    for j in range(1,8):
        if i-6**j>=1 and i-9**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j],dp[i-9**j])+1)
        elif i-6**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j])+1)
        else:
            dp[i]=min(dp[i],dp[i-1]+1)
#print(dp)
#int(dp[1],dp[9],dp[36],dp[127])
print(dp[n])

Measured memory_bytes: 47696
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, T = MAP()
t = LIST()
tt = []

for i in range(1, N):
	tt.append(min(T, t[i]-t[i-1]))

tt.append(T)
print(sum(tt))

Measured memory_bytes: 35148
#include <stdio.h>
#include <math.h>
#include <complex>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef complex<double> P;
#define EPS (1e-12)

P unit(const P& p) { return 1/abs(p)*p; }
P rot90(const P& p) { return p*P(0, 1); }

int n;
P ps[128];

int f(const P& p) {
    int c = 0;
    rep (i, n) if (abs(p-ps[i]) <= 1+EPS) c++;
    return c;
}

int main() {
    for (;;) {
        scanf("%d", &n);
        if (n == 0) return 0;
        rep (i, n) {
            double x, y;
            scanf("%lf,%lf", &x, &y);
            ps[i] = P(x, y);
        }
        int ans = 1;
        rep (i, n) rep (j, i) {
            const double d = abs(ps[i]-ps[j]);
            if (d <= 2+EPS) {
                const P m = 0.5*(ps[i]+ps[j]);
                const P dir = rot90(unit(ps[j]-ps[i]));
                const double y = sqrt(max(0.0, 1-(d/2)*(d/2)));
                ans = max(ans, f(m+y*dir));
                ans = max(ans, f(m-y*dir));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 0
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    counter_A = Counter(A)
    flag = [True] * 1000001

    count = 0
    for i in sorted(counter_A.keys()):
        if counter_A[i] == 1 and flag[i]:
            count += 1
        multiple = i
        while multiple < 1000001:
            flag[multiple] = False
            multiple += i

    print(count)


main()

Measured memory_bytes: 40204
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 9223372036854775807
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;

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

  int n,m;
  cin >> n >> m;
  
  if(n+m == 15) cout << "+" << endl;
  else if(n*m == 15) cout << "*" << endl;
  else cout << "x" << endl;


  return 0;
}


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];  }
  
  sort(a.begin(), a.end());
  cout<<a[N-1]-a[0];
  
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))

dp= [0] * (N)

for i in range(1,len(H)):

    if i == 1:
        dp[i] = abs(H[1] - H[0])
        continue

    if i > 1:
        dp[i] = min(dp[i - 1] + abs(H[i] - H[i-1]),dp[i - 2] + abs(H[i] - H[i-2]))
    
print(dp[N - 1])

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

// 插入此處

struct Item {
    LL w, v;
} items[105];

int main() {
    LL n, w;
    cin >> n >> w;
    for (int i = 0; i < n; i++) {
        cin >> items[i].w >> items[i].v;
    }
    map<LL, LL> dp;
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        vector<pair<LL, LL>> kvs;
        for (auto iter = dp.rbegin(); iter != dp.rend(); iter++) {
            kvs.push_back(make_pair(iter->first + items[i].w, iter->second + items[i].v));
        }
        for (auto kv: kvs) {
            if (dp[kv.first] < kv.second) {
                dp[kv.first] = kv.second;
            }
        }
    }
    LL ans = 0;
    for (auto kv: dp) {
        if (kv.first <= w) {
            ans = max(ans, kv.second);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 4124
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <stack>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

bool ask(int x, int y) {
  cout << "? " << x << ' ' << y << endl;
  char ans;
  cin >> ans;
  return ans == 'Y';
}

int main() {
  int a, b;
  cin >> a >> b;
  if (a <= b) {
    cout << "Impossible\n";
  } else {
    int n = a + b;
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      if (stk.empty() || ask(stk.top(), i))
        stk.push(i);
      else
        stk.pop();
    }
    string ans;
    for (int i = 0; i < n; ++i)
      if (i == stk.top() || ask(stk.top(), i))
        ans.push_back('1');
      else
        ans.push_back('0');
    cout << "!" << ans;
  }
  return 0;
}


Measured memory_bytes: 724
w1 = str(input())
w2 = []
for i in range(len(w1)):
    w2.append(w1[i])
from collections import Counter
w = Counter(w2).most_common()
x = 'Yes'
for h in range(len(w)):
    if w[h][1]%2 != 0:
        x = 'No'
        break
print(x)

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define dbg(S) { int f=1; for(auto x:S) cerr<<(f?"[":", ")<<x, f=0; cerr<<"]\n"; }

using namespace std;

int main(){
	int n,m; scanf("%d%d",&n,&m);
	vector<vector<int>> G(n);
	rep(i,m){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		G[u].emplace_back(v);
	}

	double dp0[600]={};
	for(int u=n-2;u>=0;u--){
		for(int v:G[u]){
			dp0[u]+=dp0[v];
		}
		dp0[u]=dp0[u]/G[u].size()+1;
	}

	double ans=1e77;
	double dp[600];
	rep(i,n){
		int j=-1;
		for(int k:G[i]){ if(j==-1 || dp0[j]<dp0[k]) j=k; }

		dp[n-1]=0;
		for(int u=n-2;u>=0;u--){
			dp[u]=0;
			int deg=0;
			for(int v:G[u]) if(u!=i || v!=j) {
				dp[u]+=dp[v];
				deg++;
			}
			dp[u]=dp[u]/deg+1;
		}
		ans=min(ans,dp[0]);
	}
	printf("%.15f\n",ans);

	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define INF 100100100
#define NMAX 100
#define MMAX 1000

int d[NMAX][NMAX];
vector<pair<int, int>> g[NMAX];

void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    for (int i = 0; i < NMAX; i++)
        d[s][i] = INF;
    d[s][s] = 0;
    que.push({0, s});
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int v = p.second;
        if (d[s][v] < p.first)
            continue;
        for (int i = 0; i < g[v].size(); i++) {
            auto e = g[v][i];
            if (d[s][e.second] > d[s][v] + e.first) {
                d[s][e.second] = d[s][v] + e.first;
                que.push({d[s][e.second], e.second});
            }
        }
    }
}

int main(void) {
    int n, m;
    int a[MMAX], b[MMAX], c[MMAX];
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
        g[a[i]].push_back({c[i], b[i]});
        g[b[i]].push_back({c[i], a[i]});
    }
    for (int i = 0; i < n; i++)
        dijkstra(i);
    int ans = m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (d[j][a[i]] + c[i] == d[j][b[i]]) {
                ans--;
                break;
            } 
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;

int main(){
    int N;
    LL x;
    cin >> N >> x;
    LL a[N];
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    LL ans=0;
    for(int i=1;i<N;i++){
        if(a[i-1]>=x){
            ans+=a[i-1]+a[i]-x;
            a[i]=0;
        }
        else if(a[i]+a[i-1]>x){
            ans+=a[i]+a[i-1]-x;
            a[i]=x-a[i-1];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Globalization;
using System.IO;
using System.Runtime.ExceptionServices;

class Program
{
    static void Main(string[] args) {
        var scan = new Scanner();
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(Solve(scan));
        Console.Out.Flush();
    }
    static object Solve(Scanner scan) {
        var N = Console.ReadLine();
        var K = scan.NextInt();
        var digits = N.Length;
        var dp = new long[digits + 1, 2, K + 1];
        dp[0, 0, 0] = 1;
        for (int d = 0; d < digits; d++) {
            var cur = N[d] - '0';
            for (int s = 0; s <= 1; s++) {
                for (int c = 0; c <= K; c++) {
                    var m = c == K ? 0 :
                            s == 1 ? 9 : cur;
                    for (int n = 0; n <= m; n++) {
                        var isSmall = s == 1 || n < cur ? 1 : 0;
                        var count = c == K ? K : 
                                    n != 0 ? c + 1 : c;
                        dp[d + 1, isSmall, count] += dp[d, s, c];
                    }
                }
            }
        }
        return dp[digits, 0, K] + dp[digits, 1, K];
    }
}

class Scanner
{
    string[] s;
    int i;
    public Scanner() {
        s = new string[0];
        i = 0;
    }
    public string Next() {
        if (i < s.Length) return s[i++];
        string str = Console.ReadLine();
        while (str == "") str = Console.ReadLine();
        s = str.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Next();
        i = 0;
        return s[i++];
    }
    public int NextInt() => int.Parse(Next());
}

Measured memory_bytes: 27548
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;

int main(){
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    printf("%.7lf\n", sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)));
    return 0;
}


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

int main() {
  int r=2;
  int D=10;
  int X=20;
  cin >> r;
  cin >> D;
  cin >> X;
  for(int i=0;i<10;i++){
    X=r*X-D;
    cout << X << endl;
  }
	return 0;
}


Measured memory_bytes: 3624
#include<stdio.h>

int main()
{
    int sx, sy, tx, ty;
    while(~scanf("%d%d%d%d", &sx, &sy, &tx, &ty))
    {
        for(int i = sx+1; i <= tx; i++)   printf("R");
        for(int i = sy+1; i <= ty; i++)   printf("U");
        for(int i = tx-1; i >= sx; i--)   printf("L");
        for(int i = ty-1; i >= sy; i--)   printf("D");

        printf("D");
        for(int i = sx+1; i <= tx+1; i++)   printf("R");
        for(int i = sy; i <= ty; i++)   printf("U");
        printf("LU");
        for(int i = tx-1; i >= sx-1; i--)   printf("L");
        for(int i = ty; i >= sy; i--)   printf("D");
        printf("R\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>

using namespace std;

int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.setf(ios::showpoint);
    cout.precision(12);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    map<int, int> subs;
    for (int i = 0; i < N; ++i) {
        subs[i] = 0;
    }
    for (int i = 1; i < N; ++i) {
        int super;
        cin >> super;
        ++subs[super - 1];
    }
    for (int i = 0; i < N; ++i) {
        cout << subs[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 13036
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    A = LMIIS()

    num_broken = 0
    pre_required = 0
    for i, a in enumerate(A):
        required = i-(a-1)
        if required != num_broken:
            num_broken += 1
    print(num_broken if num_broken < N else -1)




if __name__ == '__main__':
    main()

Measured memory_bytes: 71324
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int main(){
	int A,B,C;
	scanf("%d%d%d",&A,&B,&C);
    if(A+B>=C){
    	printf("%d",B+C);
	}else{
		printf("%d",A+2*B+1);
	}
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;

#define ll long long
#define mst(a) memset(a, 0, sizeof a)

const int mod = 1e9+7;
const int maxn = 1e5+50;
const int inf = 1e9;

int l[maxn];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        l[b] = max(l[b], a);
    }
    int R = 1;
    int ans = 0;
    for (int i = 2; i <= n; ++i)
    {
        //printf("%d %d %d\n", i, l[i], R);
        if (l[i] >= R)
        {
            R = i;
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
import math
import itertools

N, = (int(x) for x in input().split())
xy_arr = []
for _ in range(N):
    x,y = (int(x) for x in input().split())
    xy_arr.append((x,y))

d = 0.0
for (x1,y1),(x2,y2) in itertools.permutations(xy_arr, 2):
    d += math.sqrt((x2-x1)**2+(y2-y1)**2)
d *= 1.0/N

print(d)
    



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

class Program {
    static void Main (string[] args) {
        var inp = Console.ReadLine().Split(' ');
        int H1 = int.Parse(inp[0]);
        int M1 = int.Parse(inp[1]);
        int H2 = int.Parse(inp[2]);
        int M2 = int.Parse(inp[3]);
        int K = int.Parse(inp[4]);

        Console.WriteLine((H2 - H1) * 60 + (M2 - M1) - K);
    }
}

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

int main()
{
  int N;
  int A[10]={0};
  int B[10]={0};
  int C[10]={0,1,2,3,4,5,6,7,8,9};
  int aa=0;
  int bb=0;
  int Z[10]={0}; 
  cin>>N;
  Z[N-1]=1;
  for(int i=2;i<N;i++){
    Z[N-i]=Z[N+1-i]*i;
  }
  for(int i=1;i<=N;i++){
    cin>>A[i];
    aa+=Z[i]*C[A[i]];
    for(int j=A[i];j<10;j++)C[j]--;
  }
  int D[10]={0,1,2,3,4,5,6,7,8,9};
  for(int i=1;i<=N;i++){
    cin>>B[i];
    bb+=Z[i]*D[B[i]];
    for(int j=B[i];j<10;j++)D[j]--;
  }
  cout<<max(bb-aa,aa-bb)<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<string>

using namespace std;

	long long height[100900];
	long long dp[100900];

int main(){

	height[0] = 1000000000;

	int n; cin >> n;
	for(int i = 1; i <= n; i++) cin >> height[i];
	for(int i = 2; i <= n; i++){
		dp[i] = min(dp[i-1] + abs(height[i-1] - height[i]), dp[i-2] + abs(height[i-2] - height[i]));
	} cout << dp[n];



	return 0;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int main() {
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << 0 << endl;
        return 0;
    }
    cout << n - k << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
int main(){
    int x,y;
    cin >> x >> y;
    bool ok = false;
    for(int i=0; i<=x; i++){
        int turu = i;
        int kame = x-i;
        int asi = turu*2 + kame*4;
        if(asi == y) ok = true;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		TreeMap <Long, Integer> store = new TreeMap <Long, Integer>();
		long Ai=0;
		
		for (int i = 0; i<N; i++){
			Ai = sc.nextLong();
 
			if (store.containsKey(Ai)) 
				store.put(Ai, store.get(Ai) + 1);
			else 
				store.put(Ai, 1);
		}
		long a=0;
		long b=0;
		
		
		int freq=0;
		
		while (store.isEmpty()!=true){
			a = store.lastKey();
			freq = store.get(a);
			store.pollLastEntry();
			if (freq>1)
				break;	
		}
		
		if (freq>3)
			System.out.println(a*a);
		
		else {
			while (store.isEmpty()!=true){
				b = store.lastKey();
				freq = store.get(b);
				store.pollLastEntry();
				if (freq>1)
					break;
				
			}
			if (freq>1)
				System.out.println(a*b);
			else
				System.out.println(0);
		}
		
	
		
		sc.close();
	}

}


Measured memory_bytes: 65588
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main() {
  long long n; cin >> n;
  long long a, b; cin >> a >> b;
  if ((b-a)%2 == 0) {
    cout << (b-a)/2 << endl;
  } else {
    cout << min(a+b-1, 2*n-b-a+1)/2 << endl;
  }

  return 0;
}

// EOF


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main(void){
	int i,len;
	char str[1200];
	fgets(str,sizeof str,stdin);
	//sscanf(str,"%d %d",&a,&b);
	//scanf("%s",str);
	len=strlen(str);	//????????°??°???
	//printf("len=%d\n",len);
	for(i=0;i<len;i++){
		if( isupper(str[i]) ){	//??§???????????¨???
			str[i]=tolower(str[i]);//??§??????????°??????????
		}
		else{
			str[i]=toupper(str[i]);//?°????????????§?????????
		}
	}
	
	printf("%s",str);
	
	
	
	return 0;
}

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

using namespace std;

#define ll long long
#define PI acos(-1.0)

int main()
{
	ll t, a[100005], b[100005], c[100005];
	
	scanf("%lld", &t);
	for(int i = 1; i <= t; i++) scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
	for(int i = 2; i <= t; i++)
	{
		a[i] = a[i] + max(b[i-1],c[i-1]);
		b[i] = b[i] + max(a[i-1],c[i-1]);
		c[i] = c[i] + max(a[i-1],b[i-1]);
	}
	printf("%lld\n",max(a[t],max(b[t],c[t])));
	return 0;
}


Measured memory_bytes: 2560
from fractions import Fraction
import math
n = int(input())
candidate = [sorted(list(input())) for _ in range(n)]
ans = 0
candidate.sort()

# 有理数型をインポート
# 組合せの総数


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
# def comb(n, k):

#     if n < 0 or k < 0:
#         pdt = 0

#     else:
#         pdt = 1
#         for s in range(1, k + 1):
#             pdt *= Fraction(n - s + 1, s)

#     # 戻り値をint型にするために分子を取り出す
#     return pdt.numerator


cnt = []
num = 1
for i in range(1, n):
    if candidate[i] == candidate[i - 1]:
        num += 1
        if i == n - 1 and num > 1:
            cnt.append(num)
    else:
        if num > 1:
            cnt.append(num)
        num = 1
for i in cnt:
    if i > 1:
        ans += combinations_count(i, 2)
print(ans)

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

int main() {
  int N, Y;
  cin >> N >> Y;
  
  int ok = 0;
  for (int a = 0; a < N + 1; a++) {
    for (int b = 0; b < N - a + 1; b++) {
      int c = N - a - b;
      if (10000 * a + 5000 * b + 1000 * c == Y) {
        cout << a << ' ' << b << ' ' << c << endl;
        ok = 1;
        break;
      }
    }
    if (ok == 1)
      break;
  }
  
  if (ok == 0)
    cout << -1 << ' ' << -1 << ' ' << -1 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int x;
	int i = 1;
	
	while (1) {
		scanf("%d", &x);

		if (x == 0) {
			break;
		}

		printf("Case %d: %d\n" ,i ,x);
		i++;
	}

	return 0;
}


Measured memory_bytes: 2040
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;

using namespace std;

vector<int> as;

ll get_ans(bool even){
    int n = as.size();
    ll sum = 0;
    ll ans = 0;
    rep(i, n){
        // 偶数番目が正
        sum += as[i];
        if(even){
            if(i % 2 && sum >= 0){
                ans += sum + 1;
                sum = -1;
            }
            if(i % 2 == 0 && sum <= 0)
            {
                ans += 1 - sum;
                sum = 1;
            }
        }else{
            if(i % 2 && sum <= 0){
                ans += 1 - sum;
                sum = 1;
            }

            if(i % 2 == 0 && sum >= 0){
                ans += sum + 1;
                sum = -1;
            }

        }
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    as = vector<int>(n, 0);
    rep(i, n){
        cin >> as[i];
    }
    ll ans = get_ans(true);
    ans = min(get_ans(false), ans);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
# 入力を受け取る
B_MAX = 100000
N = int(input().strip())
B = input().strip().split()

# B_MAX + 1を入れておくことで 必ずmin(B[0], B[1]) = B[1], min(B[N-1], B[N]) = B[N-1]となる
B = [B_MAX + 1] + [int(b) for b in B] + [B_MAX + 1] # 整数に変換

sum = 0
for i in range(1, N + 1): # i = 1, 2, ..., N
    sum += min(B[i-1], B[i]) # A[i] <= min(B[i-1], B[i])

print(sum)


Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

ll DP[3005][3005];

int main() {
  ll mod1 = 998244353;
  ll A, B, C, D;
  cin>>A>>B>>C>>D;
  DP[A][B] = 1;
  for(ll i=A;i<=C;++i){
    for(ll j=B;j<=D;++j){
      if(i==A && j==B) continue;
      if(i>A && j>B){
        DP[i][j] = DP[i-1][j]*j%mod1 + DP[i][j-1]*i%mod1 - (DP[i-1][j-1]*(i-1)*(j-1)%mod1);
      }
      else{
        DP[i][j] = DP[i-1][j]*j%mod1 + DP[i][j-1]*i%mod1;
      }
      while(DP[i][j]<0) DP[i][j] += mod1;
      DP[i][j] %= mod1;
    }
  }
  cout<<DP[C][D]<<endl;
}



Measured memory_bytes: 73948
object Main {
	def square(x: BigInt): BigInt = x * x
	
	def main(args:Array[String]) = {
	    val sc = new java.util.Scanner(System.in)
	    val N = sc.nextInt
	    for(i <- 0 until N){
	      val list = List.fill(3)(sc.nextInt).sorted.reverse
	      if(square(list(0)) == square(list(1)) + square(list(2))) println("YES") else println("NO")
	    }
	    
    }
}

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

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MOD = 1e9+7;
const ll INF = 1e16;

int main() {
    FASTIO

    int n;
    cin >> n;
    vector<pair<ll,ll>> p(n);
    for(auto& q : p) {
        cin >> q.first >> q.second;
    }
    ll maxDist = -INF;
    ll x1 = -INF, y1 = -INF, x2 = INF, y2 = INF;
    for(auto q : p) {
        if(q.first + q.second > x1 + y1) {
            x1 = q.first, y1 = q.second;
        }
        if(q.first + q.second < x2 + y2) {
            x2 = q.first, y2 = q.second;
        }
    }
    maxDist = max(maxDist, abs(x1-x2)+abs(y1-y2));
    
    x1 = -INF, y1 = INF, x2 = INF, y2 = -INF;
    for(auto q : p) {
        if(q.first - q.second > x1 - y1) {
            x1 = q.first, y1 = q.second;
        }
        if(q.first - q.second < x2 - y2) {
            x2 = q.first, y2 = q.second;
        }
    }
    maxDist = max(maxDist, abs(x1-x2)+abs(y1-y2));
    
    cout << maxDist << "\n";
    
    return 0;
}

Measured memory_bytes: 6360
h,w,a,b=map(int,input().split(' '))

for i in range(h):
  ans = ""
  for j in range(w):
    if j < a:
      if i < b:
        ans = ans + "1"
      else:
        ans = ans + "0"
    else:
      if i < b:
        ans = ans + "0"
      else:
        ans = ans + "1"
  print(ans)

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

#define REP(i,n) for(int i = 0; i < (n); ++i)
#define REP1(i,n) for(int i = 1; i <= (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
#define ALL(a) begin(a), end(a)
#define MP(a,b) make_pair((a), (b))
#define ROUNDUP(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))
#define X first
#define Y second
#define DEBUG(a) cout << #a << ": " << a << "\n"
// #define DEBUG(a) {}

using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

constexpr int MOD = 1e9 + 7;

constexpr ll LLINF = 4 * 1e18 + 1;
constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

template<typename T>
T debug(T x) {
	DEBUG(x);
	return x;
}

struct edge{
	int to, cost;
	edge(){};
	edge(int _to, int _cost){
		to = _to;
		cost = _cost;
	}
};

vi x;
vector<edge> g[100000];


bool dfs(int i){
	bool ret = true;
	for(const auto &e : g[i]){
		if(x[e.to] != INF && e.cost != x[e.to] - x[i]) return false;
		else if(x[e.to] != INF) continue;
		x[e.to] = x[i] + e.cost;
		if(!dfs(e.to))return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	x = vi(n, INF);
	REP(i, m){
		int f, t, c;
		cin >> f >> t >> c;
		f--; t--;
		g[f].push_back(edge(t, c));
		g[t].push_back(edge(f, -c));
	}
	bool ans = true;
	REP(i, n){
		if(x[i] == INF){
			x[i] = 0;
			ans = ans && dfs(i);
		}
	}
	if(ans) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}


Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int N;

vector<i64> L,R;

int main(){
    cin >> N;
    L.resize(N);
    R.resize(N);
    rep(i,0,N - 1) cin >> L[i] >> R[i];

    using P = pair<i64,i64>;
    vector<i64> LL,RR;
    rep(i,0,N - 1){
      LL.push_back(L[i] * 2);
      RR.push_back(-R[i] * 2);
    }

    sort(LL.rbegin(),LL.rend());
    sort(RR.rbegin(),RR.rend());
    i64 ans = 0;

    {
      i64 sum = 0;
      for(int i = 0;i < N;i++){
        sum += LL[i];
        ans = max(ans , sum);
        sum += RR[i];
        ans = max(ans , sum);
      }
    }
    {
      i64 sum = 0;
      for(int i = 0;i < N;i++){
        sum += RR[i];
        ans = max(ans , sum);
        sum += LL[i];
        ans = max(ans , sum);
      }
    }

    cout << ans << endl;
}



Measured memory_bytes: 3572
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	long s=sc.nextLong();
    long a,b,c;
    a=s/500;
    b=(s%500)/5;
    c=a*1000+b*5;
    System.out.print(c);
  }
}

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

int main() {
  ll n;
  string s;
  cin >> n >> s;
  string s1,s2;
  rep(i,n/2){
    char a = s[i];
    s1 += a;
  }
  for(ll i = n/2; i<n; i++){
    char a = s[i];
    s2 += a;
  }
  if(s1==s2) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 3596
#include <stdio.h>
#define MAX 100000

int n,k,i,j;
long long T[MAX];

int check(long long P)
{
	for(j=0,i=0;j<k;j++)
	{
		long long s=0;
		while(s+T[i]<=P)
		{
			s+=T[i];
			i++;
			if(i==n)
			{
				return n;
			}
		}
	}
	return i;
}

int solve()
{
	long long l=0;
	long long r=100000*10000;
	long long m;
	while(r-l>1)
	{
		m=(l+r)/2;
		int v=check(m);
		if(v>=n)
		{
			r=m;
		}
		else
		{
			l=m;
		}
	}
	return r;
}

int main(void)
{
	scanf("%d %d",&n,&k);
	for(i;i<n;i++)
	{
		scanf("%d",&T[i]);
	}
	long long ans=solve();
	printf("%d\n",ans);
}


Measured memory_bytes: 2548
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define all(x) x.begin(),x.end()
#define gll greater<ll>()

const ll mx=1e18;

void solve(){
 ll n;
 cin >> n;
 vll a(n);
 rep(i,0,n) cin >> a[i];
  sort(all(a));
 ll ans=1;
 rep(i,0,n){ 
   if(a[i]==0) {
     cout << 0 << endl;
     return;
   }
   if(mx/ans<a[i]){
    cout << -1 << endl;
    return;
   }
  ans*=a[i];
 }
  cout << ans << endl;
}
int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}  

Measured memory_bytes: 3952
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "Alice" << endl; else cout << "Bob" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}

struct edge{int to, cost;};

class Graph
{
public:
    int V;
    vector<vector<edge>> G;

    Graph(int V): V(V){
        G = vector<vector<edge>>(V, vector<edge>(0));
    }

    void add_edge(int from, int to, int cost){
        G[from].push_back(edge({to, cost}));
    }

    void add_edge2(int v1, int v2, int cost){
        add_edge(v1, v2, cost);
        add_edge(v2, v1, cost);
    }

    int Grundy(int v, int par){
        int g = 0;
        REP(k, G[v].size()) if(G[v][k].to != par)
            g ^= (1 + Grundy(G[v][k].to, v));
        return g;
    }

};

signed main(){

    int N; cin >> N;
    Graph G(N);
    int x, y;
    REP(i, N - 1){
        cin >> x >> y;
        G.add_edge2(x - 1, y - 1, 0);
    }
    ANS(G.Grundy(0, -1));
    
    return 0;
}

Measured memory_bytes: 12160
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = Counter(A)
divs = set()
for i in range(N):
  if A[i] in divs: ### Aiが含まれるならAiの倍数も含まれる
    continue
  if cnt[A[i]]>=2:
    divs.add(A[i]) ### 同じ値はdivリストに格納→最後の判定でカウントされなくなる
  for j in range(2, 10**6//A[i]+1):
    divs.add(A[i]*j) ### 倍数列挙の時点でAiを含めない
ans = 0
for i in range(N):
  if A[i] in divs:
    continue
  ans += 1
print(ans)

Measured memory_bytes: 103692
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner	sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt();
		int[] sum = new int[n];
		int all = Math.abs(a[0]);
		for(int i = 1 ; i < n ; i++) {
			all += Math.abs(a[i] - a[i - 1]);
		}
		all += Math.abs(a[n - 1]);
		for(int i = 0 ; i < n ; i++) {
			if(i == 0) {
				sum[i] = Math.abs(a[i]) + Math.abs(a[i + 1] - a[i]);
			} else if(i == n - 1) {
				sum[i] = Math.abs(a[i]) + Math.abs(a[i] - a[i - 1]);
			} else {
				sum[i] = Math.abs(a[i] - a[i - 1]) + Math.abs(a[i + 1] - a[i]);
			}
		}
//		System.out.println(all);
//		System.out.println(Arrays.toString(sum));
		for(int i = 0 ; i < n ; i++) {
			if(i == 0) {
				System.out.println(all - sum[i] + Math.abs(a[1]));
			} else if(i == n - 1) {
				System.out.println(all - sum[i] + Math.abs(a[n - 2]));
			} else {
				System.out.println(all - sum[i] + Math.abs(a[i + 1] - a[i - 1]));
			}
		}
	}
}


Measured memory_bytes: 63392
#include"iomanip"
#include"iostream"
#include"limits"
#include"cmath"
#include"vector"
#include"algorithm"
#include"list"
#include"queue"
#include"stack"
#include"set"
#include"unordered_set"
#include"map"
#include"unordered_map"
#include"string"
#include"cstring"
#include"assert.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define mp make_pair
#define pb push_back
#define mset(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
struct ty
{
	ll price;
	char a;
	bool operator<(const ty & ob)const 
	{
		return price<ob.price;
	}
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n;
	//cin>>q>>h>>s>>d>>n;
	vector<ty>rec(4);
	ll mul=8;
	for(int i=0;i<4;++i)
	{
		cin>>rec[i].price;
		rec[i].price*=mul;
		mul/=2;
		rec[i].a='a'+i;
	}
	sort(all(rec));
	cin>>n;
	ll ans=0;
	for(int i=0;i<4;++i)
	{
		if(n==0)break;
		ll pr=rec[i].price;
		char ch=rec[i].a;
		if(ch=='d')
		{
			ans+=(n/2)*pr;
			n-=(n/2)*2;
		}
		else
		{
			pr/=2;
			ans+=pr*n;
			n-=n;
		}
	}
	cout<<ans<<'\n';
}











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

class UnionFindTree {
private:
    vector<int> parent;
public:
    UnionFindTree(int n) : parent(n) {
        // 最初は全てを根として初期化
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    int get_root(const int x) {
        // データxが属する木の根を取得する
        if (parent[x] == x) return x;
        // 取得したものは直接木の根をつなぐ(経路圧縮)
        return parent[x] = get_root(parent[x]);
    }

    void unite(const int x, const int y) {
        // xとyの木を併合する
        int rx = get_root(x);
        int ry = get_root(y);
        // 元から同じ木に属している場合は何もしない
        if (rx == ry) return;
        // xの属する木をyの属する木につける
        parent[rx] = ry;
    }

    bool is_same_root(const int x, const int y) {
        return get_root(x) == get_root(y);
    }
};

int main(){
    int n, q;
    cin >> n >> q;

    UnionFindTree tree(n);

    for (auto i = 0; i < q; i++) {
        int com, x, y; cin >> com >> x >> y;
        if(com) {
            cout << tree.is_same_root(x, y) << endl;
        } else {
            tree.unite(x, y);
        }
    }

    return 0;
}


Measured memory_bytes: 3160
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() { // 日本語文字列のテスト
    int w = readint;
    int n = readint;

    auto xs = new int[w + 1];
    for (int i = 0; i < xs.length; i++)
        xs[i] = i;

    for (int i = 0; i < n; i++) {
        auto ab = readln.chomp.split(",").to!(int[]);
        int a = ab[0], b = ab[1];
        swap(xs[a], xs[b]);
    }

    foreach (x; xs[1 .. $])
        writeln(x);
}

Measured memory_bytes: 2412
#include<bits/stdc++.h>
using namespace std;
#define ALL(A) A.begin(), A.end()
#define MEM(a, b) memset(a, b, sizeof(a))
#define FOR(n) for (int i = 0; i < n; ++i)
#define FOR_(n) for (int i = 1; i <= n; ++i)
#define FOR_J(n) for (int j = 0; j < n; ++j)
#define FOR_J_(n) for (int j = 1; j <= n; ++j)
#define IT_FOR(A) for (auto i = A.begin(); i != A.end(); ++i)
#define INF 0x3f3f3f3f
#define N ((int)1e6)
//#define max(_a,_b) (((_a) > (_b)) ? (_a) : (_b))
//#define min(_a,_b) (((_a) < (_b)) ? (_a) : (_b))
const int mod = 1000000007;
typedef long long ll;

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

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("wa4.txt","w",stdout);
	int _ = 1;
	//_ = read();	
	while (_--) {
		int a[200005] = { 0 };
		int n;
		n = read();
		int x = 0;
		FOR(n) {
			a[i] = read();
			x ^= a[i];
		}
		FOR(n) 
			cout << (a[i] ^ x) << ' ';
		
	}
	return 0;
}

Measured memory_bytes: 4372
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
#define TE 2e5
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int H, W; cin >> H >> W;
	pair<int, int> st, go;
	cin >> st.first >> st.second >> go.first >> go.second;

	st.first--, st.second--, go.first--, go.second--;
	vector<string> grid(H);
	for (int i = 0; i < H; i++) {
		cin >> grid[i];
	}


	vector<vector<pair<int, bool>>> maze(H, vector<pair<int, bool>>(W, make_pair(1e7, false)));
	deque <pair<int, pair<int,int>>> deq;
	deq.push_back(make_pair(0, st));
	maze[st.first][st.second] = make_pair(0, true);
	int b = 0;
	while (!deq.empty()) {
		int cst = deq.front().first;
		int x = deq.front().second.first, y = deq.front().second.second;
		maze[x][y].second = true;
		deq.pop_front();
		/*
		cout << "x=" << x << " y=" << y;
		cout << " cst=" << cst << endl;
		*/
		for (int i = -2; i <= 2; i++) {
			for (int j = -2; j <= 2; j++) {
				int xto = x + i, yto = y + j;
				if (xto < 0 || H <= xto || yto < 0 || W <= yto)continue;
				if (grid[xto][yto] == '#')continue;
				if (maze[xto][yto].second)continue;

				if (abs(xto - x) + abs(yto - y) <= 1) {
					deq.push_front(make_pair(cst, make_pair(xto, yto)));
					maze[xto][yto].first = min(maze[xto][yto].first, cst);
					maze[xto][yto].second = true;
				}
				else {
					deq.push_back(make_pair(cst + 1, make_pair(xto, yto)));
					maze[xto][yto].first = min(maze[xto][yto].first, cst + 1);
				}
			}
		}

		b++;
		//if (maze[go.first][go.second].second)break;

	}

	if (maze[go.first][go.second].second) cout << maze[go.first][go.second].first << endl;
	else cout << -1 << endl;

}


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

using namespace std;

#define ll long long

const int N=1e6+5;

int m,n,k,ans,l,r,u,x,tc,y,q,d,a[N];


char s[N];

int len,sz[N],pos[N];

pair <int,ll> v[N];

vector <int> g[N];

int dfs(int u,int p){
    sz[u]=1;
    pos[u]=len;
    v[len++]={u,0};
    for(auto v:g[u])
        if (v!=p)
            sz[u]+=dfs(v,u);
    return sz[u];
}

int main(){ 
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    scanf("%d%d",&n,&q);
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0,0);
    while(q--){
        scanf("%d%d",&u,&x);
        u--;
        v[pos[u]].second+=x;
        v[pos[u]+sz[u]].second-=x;
    }
    for(int i=1;i<n;i++)
        v[i].second+=v[i-1].second;
    for(int i=0;i<n;i++){
        printf("%lld ",v[pos[i]].second);
    }
}




Measured memory_bytes: 52864
#include <bits/stdc++.h>
#define FOR(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define FORUL(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define FORULE(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#if defined(_MSC_VER) || __cplusplus > 199711L
#define AUTOVAR(newvar,v) auto newvar = (v)
#else
#define AUTOVAR(newvar,v) __typeof(newvar) r = (v)
#endif
#define PB(x) push_back(x)
#define MP(x,y) make_pair((x),(y))
#define MEMSET(m,v) memset(m,v,sizeof(m))

typedef long long				 ll;
typedef unsigned long long		ull;

#define DEBUG 1

#if DEBUG
#define DOUT cout<<"["<<__LINE__<<"]:"
#else
#define DOUT 0 && cout
#endif

using namespace std;

#define MAX_N 50
int N;
int d[MAX_N+5];
ll sum;

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);


	cin >> N;
	FOR(n,N) {
		cin >> d[n];
	}
	FOR(i,N){
		for(int j=i+1;j<N;j++) {
			sum += d[i]*d[j];
		}
	}

	cout << sum << endl;

	return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>

using namespace std;

int main()
{
    string s;
    cin >> s;

    long tsum = 0;
    for (int i = 0; i < (1 << s.size()-1); i++) {
        long sum = 0;
        long term = 0;
        for (int j = 0; j < s.size(); j++) {
            term = term * 10 + (s[j] - '0');
            if (i & (1 << j)) {
                sum += term;
                term = 0;
            }
        }
        sum += term;
        tsum += sum;
    }
    cout << tsum << endl;
    return 0;
}

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

const int MOD = 1000000007;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to))
#define sort(a) sort(a.begin(), a.end())
#define reverse(s) reverse(s.begin(), s.end())
#define p(s) cout << (s) << endl

typedef long long ll;
using namespace std;

template<class T>
void load(vector<T> &v, int n) {
  for (int i = 0; i < n; ++i) {
    T t;
    cin >> t;
    v.push_back(t);
  }
}

template<class T>
T max(vector<T> &v) {
  return *max_element(v.begin(), v.end());
}

template<class T>
T min(vector<T> &v) {
  return *min_element(v.begin(), v.end());
}

void py(bool isUpper = false) {
  if (isUpper) {
    p("YES");
  } else {
    p("Yes");
  }
}

void pn(bool isUpper = false) {
  if (isUpper) {
    p("NO");
  } else {
    p("No");
  }
}

int main() {
  int n;
  cin >> n;
  for (int i = n; i < 1000; ++i) {
    // 3桁なので、111の倍数ならば良い
    if (i % 111 == 0) {
      p(i);
      return 0;
    }
  }
}

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

int main(){
	// sengen
	int n;
	// nyuryoku
	cin >> n;
	vector<int> p(n),q(n);
	for(int i=0;i<n;i++){
		cin >> p[i];
	}
	for(int i=0;i<n;i++){
		cin >> q[i];
	}
	// keisan
	vector<int> a(n);
	for(int i=0;i<n;i++){
		a[i] = i+1;
	}
	map<vector<int> , int> mp;
	int count = 0;
	do{
		mp[a] = count;
		count++;
	}while(next_permutation(a.begin(),a.end()));
	// syutsuryoku
	cout << abs(mp[p] - mp[q]);
}

Measured memory_bytes: 5248