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

typedef long long ll;


void solve(long long N, long long X, long long M){
  vector<ll> seen(M, -1);

  vector<ll> s;
  while(seen[X] == -1) {
    seen[X] = s.size();
    s.push_back(X);
    X = (X * X) % M;
  }

  ll rv = 0;
  for (ll i = 0; i < seen[X] && N > 0; ++i) {
    rv += s[i];
    N--;
  }

  ll cl = s.size() - seen[X];
  vector<ll> pss(cl);
  partial_sum(s.begin()+seen[X], s.end(), pss.begin());
  ll S = *pss.rbegin();

  rv += S * (N / cl);
  if (N % cl != 0) {
    rv += pss[(N % cl)-1];
  }

  cout << rv << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long N;
  std::cin >> N;
  long long X;
  std::cin >> X;
  long long M;
  std::cin >> M;
  solve(N, X, M);
  return 0;
}


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

a.insert(0,0)

ans = [0]*(n+1)

for i in range(n,0,-1):
    value = 0
    for j in range(2*i,n+1,i):
        value = value ^ ans[j]
    ans[i] = value ^ a[i]
print(sum(ans))
for i in range(1,n+1):
    if ans[i] == 1:
        print(i,end = " ")



Measured memory_bytes: 7148
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;
const long long OO = 1e18+25;
    
#define f first
#define s second

int n, a, b,x;
char s[10], s1[10], s2[10];
int main() {
    scanf("%d",&n);
    for(int i=0; i<n; i++) s[i] = i + '1';
    for(int i=0; i<n; i++)
    {
        scanf(" %c", s1+i);
    }
    for(int i=0; i<n; i++)
    {
        scanf(" %c", s2+i);
    }
    int i = 1;
    do
    {
        if(strcmp(s1, s) == 0) a = i;
        if(strcmp(s2, s) == 0) b = i;
        i++;
        if(a && b) break;
    }while(next_permutation(s, s+n));
    printf("%d",abs(a-b));
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include <cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<ctime>
#define rep(i,n) for (int i=0;i<n;i++)
//#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    long int W;
    cin>>N>>W;
    vector<long long> v(N),w(N);
    for (int i=0;i<N;i++) cin>>w[i]>>v[i];
    vector<vector<long long> > dp(N+1,vector<long long>(W+1,0));
    for (int i=1;i<=N;i++){
        for (int j=0;j<W+1;j++){
            if (j>=w[i-1]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[N][W]<<endl;

    return 0;
}

Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define N 200001
#define ll long long
#define int ll 
#define pi pair<int , int>
#define pip pair<pi ,int>
#define mp make_pair 
#define f first
#define s second
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
int* getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
	  lps[i] = j+1;
   i++;
   j++;
  }
  else{
		if(j != 0){
		 j = lps[j-1];
		}
		else{
		 lps[i] = 0;
		 i++;
		}
  }
 }
 return lps;
}
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return ans.x;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string str1;
string str2;
cin>>str1;
cin>>str2;
int n = str1.length();
int m = str2.length();
int dp[n+1][m+1];
for(int i = 0 ; i <= n ;i++){
    dp[i][0] = 0;
}
for(int i = 0 ; i <= m ;i++){
  dp[0][i] = 0;
}
for(int i = 1 ; i<= n ;i++){
  for(int j = 1 ; j <= m ;j++){
      if(str1[i-1] == str2[j-1]){
	   dp[i][j] = 1 + dp[i-1][j-1];
	  }
	  else if(dp[i-1][j] > dp[i][j-1]){
	     dp[i][j] = dp[i-1][j];
	  }
	  else{
	     dp[i][j] = dp[i][j-1];
	  }
  }
}
int i = n , j = m;
string str;
while(i > 0 && j > 0){
  if(str1[i-1] == str2[j-1]){
	  str += str1[i-1];
      i--;
      j--;
  }
  else if(dp[i-1][j] > dp[i][j-1]){
         i--;
  }
  else{
    j--;
  }
}
//string str = dp[n][m];
reverse(str.begin() , str.end());
cout<<str<<endl;
}



Measured memory_bytes: 70656
#include <iostream>
#include <cassert>
#include <algorithm>
#define N int(1e5+1)

using namespace std;
typedef pair<int,int>pii;
long long dp[N];
pii a[100];
int main(int argc,char ** argv)
{
    int n,w;
    cin>>n>>w;
    for(int i=0;i<n;++i)cin>>a[i].first>>a[i].second;   
    for(int i=0;i<n;++i){
        for(int j=w;j>=a[i].first;--j){
            dp[j]=max(dp[j],dp[j-a[i].first]+a[i].second);
        }
    }
    cout<<dp[w]<<endl;
    return 0;
}

Measured memory_bytes: 4376
/*
** 二叉搜索树的插入
** 中序和前序输出
*/

# include <cstdio>
# include <cstdlib>
# include <cstddef>

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *root;

void inorder(Node *u) {
    if (u == NULL)
        return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u) {
    if (u == NULL)
        return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

void insert(int k) {
    Node *y = NULL;
    Node *x = root;

    Node *z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NULL;
    z->right = NULL;

    while (x != NULL) {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;

    if (y == NULL)
        root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
}

bool find(int k) {
    Node *x = root;
    while (x != NULL) {
        if (k == x->key)
            return true;
        if (k < x->key)
            x = x->left;
        else
            x = x->right;
    }
    return false;
}

void solve() {
    int n, x;
    char com[10];

    root = NULL;

    scanf("%d", &n);    
    for (int i = 0; i < n; i++) {
        scanf("%s", com);
        if (com[0] == 'i') {
            scanf("%d", &x);
            insert(x);
        }
        else if (com[0] == 'f') {
            scanf("%d", &x);
            if (find(x))
                printf("yes\n");
            else
                printf("no\n");
        }
        else {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }
}

int main() {
    // freopen("infile", "r", stdin);
    // freopen("outfile", "w", stdout);
    solve();
    return 0;
}


Measured memory_bytes: 21356
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        String[] s=new String[N+1];
        for(int i=0;i<N;i++){
            s[i]=sc.next();
        }
        int M=sc.nextInt();
        String[] t=new String[M];
        for(int i=0;i<M;i++){
            t[i]=sc.next();
        }
        
        int ans=0;
        String se,sd;
        for(int i=0;i<N;i++){
            se=s[i];
            int count=0;
            for(int x=0;x<N;x++){
                if(se.equals(s[x])){
                    count++;
                }
            }
            for(int x=0;x<M;x++){
                if(se.equals(t[x])){
                    count--;
                }
            }
            ans=Math.max(ans,count);
        }
        
        for(int i=0;i<M;i++){
            sd=t[i];
            int count=0;
            for(int x=0;x<N;x++){
                if(sd.equals(s[x])){
                    count++;
                }
            }
            for(int x=0;x<M;x++){
                if(sd.equals(t[x])){
                    count--;
                }
            }
            ans=Math.max(ans,count);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
using System;

namespace lisson2
{
    class Program
    {
        static void Main(string[] args)
        {
            // 整数の入力
            int X = int.Parse(Console.ReadLine());
            int A = int.Parse(Console.ReadLine());
            if (1 > A) return;
            int B = int.Parse(Console.ReadLine());
            if (B > 1000) return;
            if (A + B >= X && X >= 10000) return;
            Console.WriteLine((X-A) % B);
        }
    }
}

Measured memory_bytes: 13140
package main

import (
	"fmt"
)

func main() {

	var S,T,U string

	fmt.Scan(&S,&T)

	var A,B int

	fmt.Scan(&A,&B)

	fmt.Scan(&U)


	if S==U{

		A=A-1

	}else if T==U{

		B=B-1
		
	}

	fmt.Println(A,B)

}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
vector<int> dp;
vector<int> ga[100010];
int n,m;
int a,b;
int dfs(int u){
	if(~dp[u])
	   return dp[u];
	for(int i=0;i<ga[u].size();i++){
		int v=ga[u][i];
		dp[u]=max(dp[u],dfs(v)+1);
	}
	return dp[u];
}
int main()
{
	cin>>n>>m;
	dp.resize(n+1);
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		ga[a].push_back(b);
	}
	for(int i=1;i<=n;i++)
	   dp[i]=-1;
	for(int i=1;i<=n;i++)
	   dfs(i);
	int ans=0;
	for(int i=1;i<=n;i++)
	   ans=max(ans,dp[i]);
	cout<<ans+1<<endl;
	return 0;
}



Measured memory_bytes: 8192
n = int(input())
l = list(map(int,input().split()))
color = [0]*9
def col(x):
  if 1<=x<=399:
    return 0
  elif 400<=x<=799:
    return 1
  elif 800<=x<=1199:
    return 2
  elif 1200<=x<=1599:
    return 3
  elif 1600<=x<=1999:
    return 4
  elif 2000<=x<=2399:
    return 5
  elif 2400<=x<=2799:
    return 6
  elif 2800<=x<=3199:
    return 7
  elif x>=3200:
    return 8
  
for i in l:
  a = col(i)
  color[a] += 1
color2 = [1 for i in color if i!=0]
if color[8]==0:
  print(len(color2),len(color2))
else:
  print(max(len(color2)-1,1),len(color2)-1+color[8])

Measured memory_bytes: 3064
def solve():
  n, k = map(int, input().split())
  p = [tuple(map(int, input().split())) for i in range(n)]
  p.sort()
  ans = 4000000000000000000
  for i in range(k, n + 1):
      for j in range(n - i + 1):
          x = p[i + j - 1][0] - p[j][0]
          s = [p[a][1] for a in range(j, i + j)]
          s.sort()
          y = 4000000000
          for a in range(i - k + 1):
            y = min(y, s[a + k - 1] - s[a])
          ans = min(ans, x * y)
  print(ans)
solve()

Measured memory_bytes: 9216
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <list>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

int main() {
    int n;
    cin >> n;
    set<char> a;
    rep(i, n) {
        char c;
        cin >> c;
        a.insert(c);
    }

    if(a.size() == 3) cout << "Three" << endl;
    if(a.size() == 4) cout <<"Four" << endl;
}

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

int main()
{
	int a[30] = { 0 };

	while (true)
	{
		char ch = 0;
		cin >> ch;
		if (!std::cin.good()) break;
		ch = tolower(ch);
		a[ch - 'a']++;
	}

	for (int i = 0; i < 26; i++) {
		char ch = 'a' + i;
		cout << ch << " : " << a[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 3104
n, k = map(int, input().split())
l = list(map(int, input().split()))
ans = [1] * n
for i in range(k):
    a, b = map(int, input().split())
    if l[a - 1] == l[b - 1]:
        ans[a - 1], ans[b - 1] = 0, 0
    elif l[a - 1] > l[b - 1]:
        ans[b - 1] = 0
    else:
        ans[a - 1] = 0
print(ans.count(1))



Measured memory_bytes: 19988
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int MOD = 1000000007;
main(){
    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    cout << string(tx-sx,'R') << string(ty-sy,'U');
    cout << string(tx-sx,'L') << string(ty-sy,'D');
    cout << "D" << string(tx-sx+1,'R') << string(ty-sy+1,'U') << "L";
    cout << "U" << string(tx-sx+1,'L') << string(ty-sy+1,'D') << "R" << endl;;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ggr getchar();getchar();return 0;
#define prique priority_queue
constexpr auto mod = 1000000007;
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
//combination(Nが小さい時はこれを使う
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

// 二項係数計算
long long COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}

//繰り返し二乗法（Nが大きい時の場合のcombination)
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= (i % mod); res %= mod;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
//UnionFind
class UnionFind {
protected:
	int* par, * rank, * size;
public:
	UnionFind(unsigned int size) {
		par = new int[size];
		rank = new int[size];
		this->size = new int[size];
		rep(i, size) {
			par[i] = i;
			rank[i] = 0;
			this->size[i] = 1;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		if (rank[n] < rank[m]) {
			par[n] = m;
			size[m] += size[n];
		}
		else {
			par[m] = n;
			size[n] += size[m];
			if (rank[n] == rank[m])rank[n]++;
		}
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
int dight(int n) {
	int ans = 1;
	while (n >= 10) {
		n /= 10;
		ans++;
	}
	return ans;
}
int dight_sum(int n) {
	int sum = 0;
	rep(i, 20)sum += (n % (int)pow(10, i + 1)) / (pow(10, i));
	return sum;
}
int dight_min(int n) {
	int ans = 9;
	while (n >= 10) {
		ans = min(ans, n % 10);
		n /= 10;
	}
	ans = min(ans, n);
	return ans;
}
int dight_max(int n) {
	int ans = 0;
	while (n >= 10) {
		ans = max(ans, n % 10);
		n /= 10;
	}
	ans = max(ans, n);
	return ans;
}
string s;
int k;
signed main() {
	cin >> k >> s;
	if (s.size() <= k)cout << s << endl;
	else cout << s.substr(0, k) + "..." << endl;
	ggr
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define F first
#define S second
 
// Kevin Mathew T
// Birla Institute of Technology, Mesra
// LinkedIn - https://www.linkedin.com/in/KevinMathewT/
// GitHub - https://github.com/KevinMathewT
// CodeForces - https://codeforces.com/profile/KevinMathew
// CodeChef - https://www.codechef.com/users/KevinMathew
// HackerRank - https://www.hackerrank.com/KevinMathew
 
const ll N = 200010, M = 1e9 + 7;
ll n, d, a, x[N], h[N], T[4 * N], L[4 * N];
vector<pair<ll, ll> > V;

void build(ll i, ll l, ll r){
    if(l == r){
        T[i] = V[l].S;
        return;
    }

    ll m = (l + r) / 2;
    build(2 * i, l, m);
    build(2 * i + 1, m + 1, r);
    T[i] = T[2 * i] + T[2 * i + 1];
}

void push(ll i, ll l, ll r){
    if(l != r){
        L[2 * i] += L[i];
        L[2 * i + 1] += L[i];
    }

    T[i] += (r - l + 1) * L[i];
    L[i] = 0;
}

void update(ll i, ll l, ll r, ll a, ll b, ll v){
    push(i, l, r);
    if(l > b || r < a) return;
    if(l >= a && r <= b){
        L[i] = v;
        push(i, l, r);
        return;
    }

    ll m = (l + r) / 2;
    update(2 * i, l, m, a, b, v);
    update(2 * i + 1, m + 1, r, a, b, v);
    T[i] = T[2 * i] + T[2 * i + 1];
}

ll query(ll i, ll l, ll r, ll a){
    push(i, l, r);
    if(l == r) return T[i];

    ll m = (l + r) / 2;
    if(a <= m) return query(2 * i, l, m, a);
    query(2 * i + 1, m + 1, r, a);
}

void solve(){
    cin >> n >> d >> a;
    V.assign(n, make_pair(0, 0));
    for(ll i=0;i<n;i++) cin >> V[i].F >> V[i].S;
    sort(V.begin(), V.end());

    build(1, 0, n - 1);

    ll i = 0, j = 0;
    ll tot = 0;

    // for(ll i=0;i<n;i++)
    //     cout << query(1, 0, n - 1, i) << " ";
    // cout << "\n";

    // update(1, 0, n - 1, 0, 2, -1);

    // for(ll i=0;i<n;i++)
    //     cout << query(1, 0, n - 1, i) << " ";
    // cout << "\n";

    while(i < n){
        while(i < n && query(1, 0, n - 1, i) <= 0) i++;
        if(i >= n) break;
        j = max(i, j);
        while(j < n && V[j].F - V[i].F <= 2 * d) j++;
        j--;
        ll add = ceil(query(1, 0, n - 1, i) / (a + 0.0));
        tot += add;
        update(1, 0, n - 1, i, j, -a * add);
    }

    cout << tot << "\n";
}
 
int main(){
	// freopen("input.txt", "r", stdin);		//Comment
	// freopen("output.txt", "w", stdout);		//this out.
	ios::sync_with_stdio(false);			//Not
	cin.tie(NULL);							//this.
	cout.tie(0);							//or this.
 
	// ll T;
	// cin >> T;
	// while(T--)
		solve();
 
	return 0;
}

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

const int maxn = 1e5+10 ;
vector<pair<int, int> > adj[maxn] ;
int mark[maxn] ;

void dfs(int u, int d = 0, int l = 0){

    if (d%2 == 0)
        mark[u] = l ;
    else
        mark[u] = 1-l ;
    for(auto i:adj[u]){

        if(mark[i.first] == -1){
            dfs(i.first, i.second, mark[u]) ;
        }

    }

}

int main(){

    fill(mark, mark +maxn, -1) ;
    int n ;
    cin >> n ;
    for(int i = 1; i < n; i++){

        int u, v, w;
        cin >> u >> v >> w;
        u-- ;
        v-- ;
        adj[u].push_back({v, w}) ;
        adj[v].push_back({u, w}) ;

    }
    dfs(0) ;
    for(int i = 0; i < n; i++){
        cout << mark[i] << '\n' ;
    }

}


Measured memory_bytes: 8704
#include<iostream>
#include<cstdint>
#include<algorithm>
using namespace std;

const int MAX = 100000;

typedef struct node {
	int id;
	int64_t num;
	int edge;
	int height;
	bool operator<(const node& r) const {
		return num < r.num;
	}
} Node;

int main() {
	int N;
	static Node node[MAX];
	cin >> N;
	for (int i = 0;i < N;++ i) {
		cin >> node[i].num;
		node[i].id = i + 1;
		node[i].height = 1;
	}
	sort(node, node + N);
	
	int64_t sum = 0; // 1からの距離
	for (int i = N - 1;i > 0;-- i) { // 大きい数字から確定させる
		int min = 0, max = i;
		int64_t check = node[i].num - N + (node[i].height << 1);
		for (int mid = max >> 1;max - min > 1;mid = min + (max - min >> 1)) {
			if (node[mid].num > check) max = mid;
			else min = mid;
		}
		if (node[min].num != check) { // 繋げる辺が存在しなかった
			cout << -1;
			return 0;
		}
		node[i].edge = min;
		node[min].height += node[i].height;
		sum += node[i].height;
	}
	
	if (sum != node[0].num) {
		cout << -1;
		return 0;
	}
	for (int i = N - 1;i > 0;-- i) {
		cout << node[i].id << " " << node[node[i].edge].id << endl;
	}
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

解説AC
数字の大きい方の頂点から確定させることを考える
この時、この頂点から繋ぐ辺は、自分の数-N+(現時点の自分の属する木の高さ*2)となることが数学的に証明できる(解説放送参照)
ということは二分探索していけばO(NlogN)で判定と構築ができるわけだ
最後に本当に正しいか確認だけして、問題ないなら構築完了
*/

Measured memory_bytes: 3712
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
using Graph = vector<vector<int> >;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define int long long

void solve() {
	int n; cin >> n;
    vector<int> l(n);
    rep(i, n) {
        cin >> l[i];
    }
    sort(all(l));
    int ans = 0;
    rep(i, n) {
        for(int j = i + 1; j < n; ++j) {
            int a = l[i], b = l[j];
            int k = upper_bound(all(l), b - a) - l.begin();
            int p = lower_bound(all(l), b + a) - l.begin();
            int res = p - k;
            if(k <= i && i <= p - 1) res --;
            if(k <= j && j <= p - 1) res --;
            ans += res;
        }
    }
    cout << ans / 3 << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int N = 550, M = N * N;
int n, d[N][N]; bool bn[N][N];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++)
	d[i][j]=min(min(i-1,j-1),min(n-i,n-j));
	int ans = 0; queue<int> q;
	for(int i=1,t,x,y; i<=n*n; i++){
		scanf("%d",&t); x=(t-1)/n+1, y=t-(x-1)*n;
		ans += d[x][y]; bn[x][y] = true;
		static int dx[4]={1,-1,0,0};
		static int dy[4]={0,0,1,-1};
		q.push(t);
		while(!q.empty()){
			int now = q.front(); q.pop();
			int nx = (now-1)/n+1, ny = now-(nx-1)*n;
			for(int i=0; i<4; i++){
				int tx = nx + dx[i], ty = ny + dy[i];
				if(d[tx][ty] > d[nx][ny] + 1 - bn[nx][ny]){
					d[tx][ty] = d[nx][ny] + 1 - bn[nx][ny];
					q.push((tx-1)*n+ty);
				}
			}
		}
	} cout << ans; return 0;
}

Measured memory_bytes: 5024
#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 kuji[1005][105];
 
int main()
{
//  cut here before submit 
//  freopen ("testcase.ACM", "r", stdin );
    int n, m, a;
    while (scanf ("%d %d %d", &n, &m, &a ), n, m, a ){
        memset (kuji, 0, sizeof (kuji ) );
//      rep (i, m ){
        for (int i = 1; i <= m; i++ ){
            int h, p, q;
            scanf ("%d %d %d ", &h, &p, &q );
            kuji[1000-h][p] = i; kuji[1000-h][q] = i;
        } // end rep
        int curr = a;
        for (int i = 0; i < 1005; i++ ){
            if (kuji[i][curr] ){
                if (kuji[i][curr] == kuji[i][curr-1] ) curr--;
                else curr++;
            } // end if
        } // end for
        printf ("%d\n", curr );
/*
        // for debug
        rep (i, 10 ){
            rep (j, n+1 ){
                cout << kuji[i][j];
            } // end rep
            cout << endl;
        } // end rep
        cout << endl;
*/
//      cout << curr << endl;
    } // end while
 
    return 0;
}

Measured memory_bytes: 3604
#include<cstdio>
double n, x, d, r;

int main()
{
    scanf("%lf%lf%lf", &n, &d, &x);
    d+=(n-0.5)*x;
    for(;n; d+=d/n--)
        r+=d;
    printf("%.10lf\n", r);
    return 0;
}


Measured memory_bytes: 128
N, K = map(int, input().split())
S = list(map(int, input()))

prev = S[0]
renzoku_start = [0]
for i in range(1, N):
  if prev == S[i]:
    continue
  else:
    prev = S[i]
    renzoku_start.append(i)
renzoku_start.append(N)

ans = []
l = len(renzoku_start)
for j in range(l):
  if S[renzoku_start[j]] == 0:
    if j + 2 * K >= l:
      ans.append(N - renzoku_start[j])
      break
    ans.append(renzoku_start[j + 2 * K] - renzoku_start[j])
  else:
    if j + 2 * K + 1 >= l:
      ans.append(N - renzoku_start[j])
      break
    ans.append(renzoku_start[j + 2 * K + 1] - renzoku_start[j])

if ans:
  print(max(ans))
else:
  print(N)

Measured memory_bytes: 10956
import java.util.*;
public class Main {

	public void doIt(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNextLine()){
			String str = sc.nextLine();
			int len = str.length();
			for(int i=0; i < len; i++){
				char now = str.charAt(i);
				if(now != '@'){
					System.out.print(now);
				}
				else{
					i++;
					int num = str.charAt(i)  - '0';
					i++;
					if(0 <= num && num <= 9){
						now = str.charAt(i);
						for(int j=0; j < num; j++){
							System.out.print(now);
						}
					}
				}

			}
			System.out.println("");
		}

	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doIt();

	}

}

Measured memory_bytes: 0
import functools
import collections
n = int(input())
print(sum(
    map(
        lambda x: x % 2,
        functools.reduce(
            lambda d, v: d.update({v: d[v]+1}) or d,
            [int(input()) for i in range(n)],
            collections.defaultdict(lambda: 0),
        ).values(),
    )
))


Measured memory_bytes: 16760
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> stX = new ArrayList<Integer>();
		ArrayList<Integer> stY = new ArrayList<Integer>();
		ArrayList<Integer> cpX = new ArrayList<Integer>();
		ArrayList<Integer> cpY = new ArrayList<Integer>();
		ArrayList<Integer> dis = new ArrayList<Integer>();
		int stnum = sc.nextInt();
		int cpnum = sc.nextInt();

		for (int i = 0; i < stnum; i++) {
			stX.add(sc.nextInt());
			stY.add(sc.nextInt());
		}
		for (int i = 0; i < cpnum; i++) {
			cpX.add(sc.nextInt());
			cpY.add(sc.nextInt());
		}

		for (int i = 0; i < stnum; i++) {
			int sX = stX.get(i);
			int sY = stY.get(i);
			int min = 1000000000;
			int cp = 0;

			ArrayList<Integer> disL = new ArrayList<Integer>();

			for (int k = 0; k < cpnum; k++)
				disL.add(Math.abs(sX - cpX.get(k)) + Math.abs(sY - cpY.get(k)));

			for (int j = 0; j < cpnum; j++) {
				if (min > disL.get(j)) {
					min = disL.get(j);
					cp = j + 1;
				}
			}

			dis.add(cp);
		}

		for (int i = 0; i < stnum; i++)
			System.out.println(dis.get(i));
	}
}


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

void _150() {
    string s;
    cin >> s;

    if ((s == "AAA") || (s == "BBB"))
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
}

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



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

ll gcd(ll a, ll b) {
    while (b) {
        ll x = a, y = b;
        a = y, b = x % y;
    }
    return a;
}

int main()
{
    ll N, Ma, Mb; cin >> N >> Ma >> Mb;
    ll g = gcd(Ma, Mb);
    Ma /= g, Mb /= g;
    vector<pair<pair<ll, ll>, ll>> medicine;
    rep(i, N) {
        ll a, b, c; cin >> a >> b >> c;
        medicine.push_back({{a, b}, c});
    }
    ll dp[N+1][500][500];
    rep(i, N+1) rep(j, 500) rep(k, 500) dp[i][j][k] = inf;
    dp[0][0][0] = 0;
    rep(i, N) {
        rep(j, 500) rep(k, 500) {
        dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
        if (j + medicine[i].first.first < 500 && k + medicine[i].first.second < 500) dp[i+1][j+medicine[i].first.first][k+medicine[i].first.second] = 
            min(
                dp[i+1][j+medicine[i].first.first][k+medicine[i].first.second],
                dp[i][j][k] + medicine[i].second
            );
        }
    }

    ll minn = inf;
    for (ll i = 1; Ma * i < 500 && Mb * i < 500; i++) {
        minn = min(minn, dp[N][Ma*i][Mb*i]);
    }
    cout << (minn != inf ? minn : -1) << endl;
    return 0;
}

Measured memory_bytes: 80384
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

ll dp[51][21][2],cst[51],INF=1e18,n;
string s[51];


ll solve(int wh, int pos, int pre){
	if(pos>=SZ(s[wh])-1&&pre) return 0;
	if(pos<=0&&!pre)return 0;
	if(dp[wh][pos][pre]>=0)return dp[wh][pos][pre];
	dp[wh][pos][pre]=INF;
	ll r=INF;
	
	//pongo la i en sufijo
	
	
	
	return dp[wh][pos][pre]=r;
}


const int MAXN=51*25*3;
vector<pair<int,int> > g[MAXN];  // u->[(v,cost)]
ll dist[MAXN];
void dijkstra(int x){
	memset(dist,-1,sizeof(dist));
	priority_queue<pair<ll,int> > q;
	dist[x]=0;q.push({0,x});
	while(!q.empty()){
		x=q.top().snd;ll c=-q.top().fst;q.pop();
		if(dist[x]!=c)continue;
		fore(i,0,g[x].size()){
			int y=g[x][i].fst; ll c=g[x][i].snd;
			if(dist[y]<0||dist[x]+c<dist[y])
				dist[y]=dist[x]+c,q.push({-dist[y],y});
		}
	}
}

bool pal(string s){
	fore(i,0,SZ(s)/2) if(s[i]!=s[SZ(s)-i-1])return 0;
	return 1;
}

int main(){FIN;
	cin>>n;
	map<pair<ii,int>,int> mp;
	int id=0;
	fore(i,0,n){
		cin>>s[i]>>cst[i];
		fore(j,-1,SZ(s[i])+1) fore(k,0,2) mp[{{i,j},k}]=id++;
	}
	
	
	fore(wh,0,n) fore(pos,0,SZ(s[wh])) fore(pre,0,2){
		if(pre){
			fore(i,0,n){
				int p1=pos,p2=SZ(s[i])-1;
				while(p1<SZ(s[wh])&&p2>=0&&s[wh][p1]==s[i][p2]) p1++,p2--;
				
				if(p1<SZ(s[wh])&&p2>=0) continue;
				
				pair<ii,int> nx,me={{wh,pos},pre};
				if(p1==SZ(s[wh])) nx={{i,p2},0};
				else nx={{wh,p1},pre};
				g[mp[me]].pb({mp[nx],cst[i]});
			}
		}
		else{
			fore(i,0,n){
				int p1=pos,p2=0;
				while(p1>=0&&p2<SZ(s[i])&&s[wh][p1]==s[i][p2]) p1--,p2++;
				
				if(p1>=0&&p2<SZ(s[i])) continue;
				
				pair<ii,int> nx,me={{wh,pos},pre};
				if(p1<0) nx={{i,p2},1};
				else nx={{wh,p1},pre};
				g[mp[me]].pb({mp[nx],cst[i]});
			}
		}
	}
	fore(i,0,n) g[id].pb({mp[{{i,0},1}],cst[i]});
	
	dijkstra(id);
	
	ll ans=INF;
	fore(i,0,n){
		vector<pair<ii,int>> test;
		
		//prefijo
		fore(len,0,SZ(s[i])+1){
			string x=s[i].substr(0,len);
			if(!pal(x))continue;
			int id=len-1;
			test.pb({{i,id},0});
		}
		
		//sufijo
		fore(len,0,SZ(s[i])+1){
			string x=s[i].substr(SZ(s[i])-len,len);
			if(!pal(x))continue;
			int id=SZ(s[i])-len;
			test.pb({{i,id},1});
		}
		
		for(auto x:test) if(dist[mp[x]]!=-1) ans=min(ans,dist[mp[x]]);
	}
	if(ans==INF) ans=-1;
	cout<<ans<<"\n";
}

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

class Dice{
	public:
	int diceside[6];
	char instruct[100];
	
	void Show();
	void Move();
	};

	
void Dice::Show(){
    for(int i=0;i<6;i++){
        cout<<diceside[i]<<endl;
    }
}

void Dice::Move(){
	
	int d1;
	int d2;
	int d3;
	int d4;
	int d5;
	int d6;
	
	for(int i=0;instruct[i]!='\0';i++){
		d1=diceside[0];
		d2=diceside[1];
		d3=diceside[2];
		d4=diceside[3];
		d5=diceside[4];
		d6=diceside[5];
		
		switch(instruct[i]){
			case 'N':
			diceside[0]=d2;
			diceside[1]=d6;
			diceside[2]=d3;
			diceside[3]=d4;
			diceside[4]=d1;
			diceside[5]=d5;break;
			
			case 'E':
			diceside[0]=d4;
			diceside[1]=d2;
			diceside[2]=d1;
			diceside[3]=d6;
			diceside[4]=d5;
			diceside[5]=d3;break;
			
			case 'W':
			diceside[0]=d3;
			diceside[1]=d2;
			diceside[2]=d6;
			diceside[3]=d1;
			diceside[4]=d5;
			diceside[5]=d4;break;
			
			case 'S':
			diceside[0]=d5;
			diceside[1]=d1;
			diceside[2]=d3;
			diceside[3]=d4;
			diceside[4]=d6;
			diceside[5]=d2;break;
    	}
	}
	
	cout<<diceside[0]<<endl;
}


//-------------------------------------------------------------------

int main(void){
	
	int imput;
	Dice dice1;
	for(int i=0;i<6;i++){
		cin>>imput;
		dice1.diceside[i]=imput;
	}
	
	cin>>dice1.instruct;
	
	dice1.Move();
	


	
}

Measured memory_bytes: 1164
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    X, Y = il()
    for k in range(X + 1):
        if 2 * k + 4 * (X - k) == Y:
            print('Yes')
            exit()
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 37452
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b == c || a + c == b || a == b + c)
        cout << "Yes"
             << "\n";
    else
        cout << "No"
             << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

char str[200005];

int main(int argc, char* argv[])
{
    scanf("%s", str);
    int n = strlen(str);

    ll ans=0;
    int i;
    int cnta=0;
    for(i=1; i<n; i++) {
        if(cnta>0 && str[i-1]=='B' && str[i]=='C') {
            int k0 = i-1-cnta;
            ans += cnta;
            i++;
        }
        else {
            if(str[i-1]=='A') cnta++;
            else cnta=0;
        }
    }
    printf("%lld\n", ans);

    return 0;
}


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

int main() {
   int N, X, P, W, G, Y;
   char S;
   cin >> N;
   P=0;
   W=0;
   G=0;
   Y=0;
   for(int i=0; i<N; i++){
     cin >> S;
     if(S == 'P'){
       P=1;
     }
     else if(S =='W'){
       W=1;
     }
     else if(S =='G'){
       G=1;
     }
     else if(S =='Y'){
       Y=1;
     }
     X=P+W+G+Y;
     if(X==4){
       break;
     }
   }
   if (X==4){
     cout << "Four" << endl;
   }
   else{
     cout << "Three" << endl;
   }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m,a,q;
list<int> lis;
int main(){
	cin>>n>>m>>q;
	for(int i=0;i<n;i++)lis.push_back(i);
	list<int>::iterator b=lis.begin();
	while(m--){
		cin>>a;
		if(a%2){
			while(a--){
				if(b==lis.begin())b=lis.end(),b--;
				else b--;
			}
		}
		else{
			while(a--){
				b++;
				if(b==lis.end())b=lis.begin();
			}
		}
		b=lis.erase(b);
		if(b==lis.end())b=lis.begin();
	}

	while(q--){
		cin>>a;
		b=lis.begin();
		while(true){
			if(b==lis.end()){
				cout<<"0"<<endl;
				break;
			}
			if(*b==a){
				cout<<"1"<<endl;
				break;
			}
			b++;
		}
	}
	return 0;
}

Measured memory_bytes: 9284
using System;

class Program
{
  static void Main(string[] args)
  {
    var input = Console.ReadLine().ToCharArray();
    var count = 0;
    var charArray = "abcdefghijklmnopqrstuvwxyz".ToCharArray();

    for (int i = 0; i < input.Length; i++)
    {
      if (input[i] != input[input.Length - 1 - i])
      {
        for (int j = 0; j < charArray.Length; j++)
        {
          input[i] = charArray[j];
          if (input[i] == input[input.Length - 1 - i])
            break;
        }
        count++;
      }
    }

    Console.WriteLine(count);
  }
}

Measured memory_bytes: 13140
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL K, A, B;
	in >> K >> A >> B;

	LL ans = 0;
	if ((B - A) <= 2) ans = K + 1;
	else
	{
		LL turn = std::max<LL>((K - (A - 1)) / 2, 0);
		ans = A;
		ans += B * turn - A * turn;
		if (turn * 2 + A - 1 < K) ans += K - (turn * 2 + A - 1);
	}
	out << ans << std::endl;
}


Measured memory_bytes: 256
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		ArrayList<String> list = new ArrayList<>();
		for(int i=1;i<=9;i++)list.add(i+"");
		int ind = 0;
		while(n>list.size()){
			String x=list.get(ind);
			int y = Integer.parseInt(x.charAt(x.length()-1)+"");
			if(y!=0)list.add(x+""+(y-1));
			list.add(x+""+(y));
			if(y!=9)list.add(x+""+(y+1));
			ind++;
		}
		System.out.println(list.get(n-1));
	}
}

Measured memory_bytes: 44756
#include <bits/stdc++.h>
using namespace std;
#define double long double
#define int long long
signed main() {
	int n;
	double sum;
	cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++){
	    int x;
	    cin>>x;
	    sum+=(double)1/x;
	}
	cout<<(double)1/sum;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())

print(n*n)
"""
#a = [int(i) for i in readline().split()]
x,y = [int(i) for i in readline().split()]


xx = x-2*y
yy = (-2)*x+y

ng = 0

if xx%3 != 0: ng = 1
if yy%3 != 0: ng = 1

xx //= 3 
yy //= 3
xx *= -1
yy *= -1

#print(ng,xx,yy)

if ng: print(0)
else: print(choose(xx+yy,xx)%MOD)







"""

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

using namespace std;

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

#define MOD 1000000007
#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) a.begin(), a.end()

int main() {
  int N, M, C;
  cin >> N >> M >> C;
  int B[M];
  REP(i, M) cin >> B[i];
  int A[N][M];
  REP(i, N) REP(j, M) cin >> A[i][j];
  int ans = 0;
  REP(i, N) {
    int tmp = 0;
    REP(j, M) tmp += A[i][j] * B[j];
    tmp += C;
    if (0 < tmp) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

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

const ld pie = 3.14159265358979 ;
const ll mod = 1e9 + 7 ;

void solve ( int test_case )
{
    int a , b ;
    cin >> a >> b ;

    int temp = 1 + 2 + 3 ;
    int ans = temp - a - b ;

    cout << ans ; line
}

int main()
{
    int t = 1;
    // cin >> t;

    for ( int i=0 ; i < t ; i++ ) solve(i);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// your code goes here
	int n,k;
	string str;
	cin>>n>>k>>str;
	int diff=0;
	int s=0;
	for(int i=1;i<n;i++)
	{
		if(str[i-1]==str[i]) 
			s++;
		else 
			diff++;
	}
	if(diff<=(2*k)) 
		cout<<s+diff<<endl;
	else 
		cout<<s+(2*k)<<endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream> 
using namespace std;
 
int main(){
  int n, k, cnt=0, v[1000000];
  
  cin>>n>>k;
  for(int i=0; i<n; ++i){
    cin>>v[i];
    if(v[i] >= k)cnt++;
  }
  cout<<cnt<<'\n';
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

ll n;
vector<vector<P>> v;

bool judge(ll bit){
    rep(i,n){
        if(!(bit&(1<<i))) continue;
        for(auto xy:v[i]){
            ll x=xy.first,y=xy.second;
            if(y==1 && !(bit & (1<<x))) return false;
            if(y==0 && (bit & (1<<x))) return false;
        }
    }
    return true;
}

int main(void)
{
    cin>>n;
    v.resize(n);
    rep(i,n){
        ll a; cin>>a;
        v[i].resize(a);
        rep(j,a){
            cin>>v[i][j].first>>v[i][j].second;
            --v[i][j].first;
        }
    }
    ll ans=0;
    rep(bit,1<<n){
        if(judge(bit)){
            ll cnt=0;
            rep(i,n){
                if(bit & (1<<i)) ++cnt;
            }
        ans=max(ans,cnt);
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

#define ll long long
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define M 1000000007

void solve()
{	
	ll n;
	cin>>n;
	ll p[10001]={0};
	for(ll i=0;i<=1000;i++) p[i]=pow(i,5);
	for(ll i=0;i<=1000;i++)
	{
		for(ll j=0;j<=1000;j++)
		{
			if(p[i]-p[j]==n)
			{
				cout<<i<<" "<<j;
				return;
			}
			else if(p[j]-p[i]==n)
			{
				i=-i;
				j=-j;
				cout<<i<<" "<<j;
				return;
			}
			else if(p[i]+p[j]==n)
			{
				j=-j;
				cout<<i<<" "<<j;
				return;
			}
			else if(-p[i]-p[j]==n)
			{
				i=-i;
				cout<<i<<" "<<j;
				return;
			}
		}
	}
}

int main()
{
	FAST
	ll t=1;
	//cin>>t;
	for(ll i=0;i<t;i++) solve();
	return 0;
}


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


using namespace std;


#define ll long long
#define mk make_pair
#define pb push_back
#define ff first
#define sc second
#define all(x) x.begin(), x.end()
#define sz(x) (x).size()

ll gcd(ll a, ll b);

ll sum(int n);

void go(){
   int a,b;cin>>a>>b;
   cout << a*b;
}
int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   go();

   return 0;
}

ll gcd(ll a, ll b){     
   if(b == 0) return a;
   
   return gcd(b, a % b);
}

ll sum(int n){                
   if(n == 0){
      return n;
   }else{
      return sum(n/10) + n%10;
   }
}


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

using namespace std;

int main(){
  string N;
  cin >> N;
  int before=N[0];
  int ans=0;
  for(int i=1;i<N.size();i++){
    if(before!=N[i]){
      ans++;
    }
    before=N[i];
  }
  cout << ans;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll n, m, s, t, h;
  in2(n, m);
  vector<ll> a(n);
  vector<ll> b(n);
  vector<ll> c(m);
  vector<ll> d(m);
  rep(i, n)
    in2(a[i], b[i]);
  rep(i, m)
    in2(c[i], d[i]);
  rep(i, n){
    s = 99999999999;
    h = 99999999999;
    rep(j, m){
      t = abs(a[i] - c[j]) + abs(b[i] - d[j]);
      if(s > t){
        s = t;
        h = j;
      }
    }
    h++;
    out(h);
    memi;
  }
}

Measured memory_bytes: 256
var lines = [];

var readline = require('readline');
var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {
    var v = [];
    for (var i = 0; i < 5; i++) {
        v[i] = Number(lines[i]);
    }
    var result = 0; var hoge = 0;
    var max = Infinity;
    for (var i = 0; i < 5; i++) {
        for (var j = 1; j < 10; j++) {
            if (v[i] % 10 === 0) { break; }
            if ((v[i] - j) % 10 === 0) { if (j < max) { max = j; hoge = i; } }
        }
    }
    for (var i = 0; i < 5; i++) {
        for (var j = 1; j < 10; j++) {
            if (v[i] % 10 === 0) { result += v[i];break; }
            if (i === hoge) { result += v[i]; break;}
            if ((v[i] - j) % 10 === 0) { result += v[i] + 10 - j; break;}
        }
    }
    console.log(result);
});

Measured memory_bytes: 7500
#include <stdio.h>

int main(){
  int n;
  scanf("%d", &n);
  int A[n], x, y, z, i, j;
  int p = 0;
  int r = n-1;
  for(i=0;i<n;i++)scanf("%d", &A[i]);
  x = A[r];
  i = p - 1;
  for(j=p;j<=r-1;j++){
    if(A[j]<=x){
      i = i + 1;
      y = A[i];
      A[i] = A[j];
      A[j] = y;
    }
  }
  z = A[i+1];
  A[i+1] = A[r];
  A[r] = z;
  for(j=0;j<n-1;j++){
    if(j==i+1) printf("[");
    printf("%d", A[j]);
    if(j==i+1) printf("]");
    printf(" ");
  }
  printf("%d\n", A[n-1]);
  return 0;
}


Measured memory_bytes: 2128