akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<chrono>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << "\n"; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " <<to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


void solve(){
  int n;
  cin>>n;
  vector<string>s(n);
  vector<int>t(n);
  int sum=0;
  rep(i,n){
    cin>>s[i]>>t[i];
    sum+=t[i];
  }
  string x;
  cin>>x;
  int ans=0;
  rep(i,n){
    ans+=t[i];
    if(s[i]==x){
      cout<<sum-ans<<"\n";
      return;
    }
  }
}
 
int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}


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

#define rep(i,n) for(int i = 0;i < n;i++)
#define REP(i,n,k) for(int i = n;i < k;i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define pi 3.1415926535
#define IINF 1e9
#define LINF 1e18
#define vi vector<int>
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

unsigned long long sttoi(std::string str) {
	unsigned long long ret;
	std::stringstream ss; ss << str;
	ss >> ret;
	return ret;
}

ull gcd(ull a, ull b) {
	if (b > a)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a%b);
}
int dp[10000];
void solve() {
  int n,t,s;
  cin >> n >> t >> s;
  rep(i,t+1)dp[i] = 0;
  vi v,w;
  rep(i,n){
    int a,b;
    cin >> a >> b;
    v.pb(a);
    w.pb(b);
  }
  rep(i,n){
    for(int j = t-w[i];j >= 0;j--){
      if(j < s && j + w[i] > s)continue;
      dp[j+w[i]] = max(dp[j+w[i]],dp[j]+v[i]);
    }
    rep(j,t){
      dp[j+1] = max(dp[j+1],dp[j]);
    }
  }
  int maxi = -1;
  rep(i,t+1){
    maxi = max(maxi,dp[i]);
  }
  P(maxi);
}

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

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];

    ll l = a[0];
    ll ma = a[0];
    rep(i, N) {
        l = lcm(l, a[i]);
        chmax(ma, a[i]);
    }

    ll x = 0;
    for (ll k = ma / 2; k <= l && k <= M; k += ma) {
        bool ok = true;
        rep(i, N) {
            if ((k - a[i] / 2) % a[i]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            x = k;
            break;
        }
    }

    if (x == 0 || M < x) {
        cout << 0 << endl;
        return 0;
    }

    cout << (M - x) / l + 1 << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include <iomanip>
#include<vector>
#include<string>
#include<string.h>
#include<math.h>
#include<utility>
#include<algorithm>
#include<functional>
using namespace std;

int n;
int a[10000];
int s=0;
int b=0;


int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	for(int i=0;i<n;i++){
		b=sqrt(a[i]);
		if(a[i]==2||a[i]==3)s++;
		for(int j=2;j<b+1;j++){
			
			
            if(a[i]%j==0)break;
		if(j==b)s++;
		}
	}

	cout<<s<<endl;

	return 0;
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t=1;
    while(t--)
    {
        int n;
        cin>>n;
        int ans=INT_MAX;
        int a[n+10];
        for(int i=0; i<n; i++) cin>>a[i];
        for(int i=-100; i<=100; i++)
        {
            int tm=0;
            for(int j=0; j<n; j++)
            {
                tm+=(i-a[j])*(i-a[j]);
            }
            ans=min(ans,tm);
        }
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 3636
#include <iostream>
#include<algorithm>
using namespace std;
int main(void){
    // Your code here!
    int a,b;
    cin >> a >> b;
    if(a  > b)for(int i=0;i<a;i++)cout << b;
    else for(int i=0;i<b;i++)cout << a;
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

void ABC109D()
{
	int H, W;
	cin >> H >> W;
	vector<vector<int> > coins(H, vector<int>(W));
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			cin >> coins[i][j];
		}
	}
	vector<vector<int> > op;
	for (int i = 0; i < H; ++i)
	{
		if (i % 2 == 0)
		{
			for (int j = 0; j < W; ++j)
			{
				if (coins[i][j] % 2 == 1)
				{
					--coins[i][j];
					if (j < W - 1)
					{
						++coins[i][j + 1];
						op.push_back({ i + 1,j + 1, i + 1,j + 2 });
					}
					else if(i+1 < H)
					{
						++coins[i + 1][j];
						op.push_back({ i + 1,j + 1, i + 2,j + 1 });
					}
				}
			}
		}
		else
		{
			for (int j = W - 1; j > -1; --j)
			{
				if (coins[i][j] % 2 == 1)
				{
					--coins[i][j];
					if (j > 0)
					{
						++coins[i][j - 1];
						op.push_back({ i + 1,j + 1, i + 1,j });
					}
					else if (i + 1 < H)
					{
						++coins[i + 1][j];
						op.push_back({ i + 1,j + 1, i + 2,j + 1 });
					}
				}
			}
		}
	}
	cout << op.size() << endl;
	for (size_t i = 0; i < op.size(); ++i)
	{
		cout << op[i][0] << ' ' << op[i][1] << ' ' << op[i][2] << ' ' << op[i][3] << endl;
	}
}
int main()
{
	ABC109D();
	return 0;
}

Measured memory_bytes: 11824
//From Naruto to Hokage
//#include <RJ>
#include<bits/stdc++.h>
using namespace std;

#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define endl        '\n'
#define mii         map<ll,ll>
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define INF         (1ll<<60)
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define rrep(i,a,b)  for(ll i=a;i>=b;i--)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const int N=100005;
void solve(){
    string s;
    cin>>s;
    ll ans=0;
    ll curr=0;
    rep(i,0,sz(s)-2){
        if(s[i]=='B' && s[i+1]=='C'){
            ans+=curr;
            i+=1;
        }
        else{
            if(s[i]=='A') curr++;
            else curr=0;
        }
    }
    // ans+=(curr*(curr+1))/2;
    cout<<ans;
}
signed main()
{
    ios
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        solve();
    }
    time
    return 0;
}

Measured memory_bytes: 720
A,B,K=map(int,input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()　#小さい順位欲しいとき
    return divisors
Anoyatu=make_divisors(A)
Bnoyatu=make_divisors(B)
ans=list(set(set(Anoyatu)&set(Bnoyatu)))
ans.sort()
ans.reverse()
#print(ans)
print(ans[K-1])

Measured memory_bytes: 3064
N = input()
W = list(map(int, input().split()))
sum_temp = 0
sum_all = sum(W)
for w in W:
  sum_temp += w
  if sum_temp > sum_all - sum_temp:
    if sum_temp - (sum_all - sum_temp) > (sum_all - sum_temp + w) - (sum_temp - w):
      print((sum_all - sum_temp + w) - (sum_temp - w))
      break
    else:
      print(sum_temp - (sum_all - sum_temp))
      break

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  for (int i = 0; i < n1; i++) L[i] = A[left + i];
  for (int i = 0; i < n2; i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i = 0, j = 0;
  for (int k = left; k < right; k++) {
    cnt++;
    if (L[i] <= R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right) {
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

int main() {
  int A[MAX], n;
  cnt = 0;

  cin >> n;
  for (int i = 0; i < n; i++) cin >> A[i];

  mergeSort(A, n, 0, n);

  for (int i = 0; i < n; i++) {
    if (i) cout << " ";
    cout << A[i];
  }
  cout << endl;

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 6908
import math
N=int(input())
rt = int(math.sqrt(N))
# print(rt)

res = 0
for a in range(1, rt+1):
    if N % a == 0:
        b1 = N // a
        b = b1-1 
        if b > a and b > 0:
            res += b

print(res)


Measured memory_bytes: 40172
from collections import deque
N = int(input())

tasks = []

for i in range(N):
    task = list(map(int, input().split()))
    tasks.append(task)

tasks.sort(key=lambda x: x[1])
dq = deque(tasks)

time = 0
task_over = False
for i in range(N):
    tmp = dq.popleft()
    time += tmp[0]
    if time > tmp[1]:
        task_over = True
        break

if task_over:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 53956
// k - i == Ai + Ak -->
// k - Ak == Ai + i

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');

const N = +lines[0];
const A = lines[1].split(' ').map(v => +v);

// console.log(`N=${N}`);
// console.log(A);

const map = {};

A.forEach((a, i) => {
    if (!map[a + i + 1]) {
        map[a + i + 1] = 1;
    } else {
        map[a + i + 1] ++;
    }
});

let count = 0;
A.forEach((a, k) => {
    if (map[k + 1 - a]) { // k - Ak = Ai + i
        count += map[k + 1 - a];
    }
});

// console.log(map);
console.log(count);


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

int main() {
	ll n, p;
	cin >> n >> p;
	//素因数分解
	vector<ll>privec;
	ll i = 2;
	while (i<=sqrt(p)) {
		if (p % i == 0) {
			privec.push_back(i);
			p /= i;
		}
		else i++;
	}
	if (p != 1)privec.push_back(p);
	map<ll,ll>priset;
	for (int i = 0; i < privec.size(); i++) {
		if (priset.count(privec.at(i)))priset.at(privec.at(i))++;
		else priset[privec.at(i)] = 1;
	}

	ll ans = 1;
	for (auto b : priset) {
		ll x = b.first;
		ll y = b.second;
		if (n <= y) ans *= pow(x, y / n);
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
L, R = map(int, input().split())
ans = 0

if L // 2019 < R // 2019:
    print(ans)
    exit()

ans = 2018
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        tmp = (i * j) % 2019
        if tmp < ans:
            ans = tmp
print(ans)

Measured memory_bytes: 3316
x, y = gets.split.map(&:to_i)
ans = (y.abs-x.abs).abs
if x*y < 0
  ans += 1
end
if x*y == 0
  if x > y
    ans += 1
  end
end
if x*y > 0
  if x > y
    ans += 2
  end
end
puts ans


Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

const int MAXN = 10010;
vector<int> T[MAXN];
vector<int> C[MAXN];
vector<int> D[MAXN];

int main(){
  int N, M;
  while(cin >> N >> M && N + M){
    REP(i, MAXN) {
      T[i].clear();
      C[i].clear();
      D[i].clear();
    }

    
    REP(i, M){
      int x, y, d, c;
      cin >> x >> y >> d >> c;
      T[x].push_back(y);
      C[x].push_back(c);
      D[x].push_back(d);
      T[y].push_back(x);
      C[y].push_back(c);
      D[y].push_back(d);
    }

    vector<int> dist(N + 1, INF);
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, 1));
    
    dist[1] = 0;
    while(!que.empty()){
      int d = que.top().first;
      int v = que.top().second; que.pop();
      if(dist[v] < d) continue;
      REP(i, T[v].size()){
        int to = T[v][i];
        int tmp = d + D[v][i];
        if(tmp < dist[to]){
          dist[to] = tmp;
          que.push(P(tmp, to));
        }
      }
    }

    int ans = 0;    

    REP2(v, 2, N + 1){
      int best = INF;
      REP(i, T[v].size()){
        int to = T[v][i];
        int di = D[v][i];
        int co = C[v][i];
        if(dist[to] + di == dist[v]) best = min(best, co);
      }
      ans += best;
    }
    cout << ans << endl;
  }
  return 0;
}

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

const int MOD = 1000000007;

int main() {
    int N, M;
    std::cin >> N >> M;

    std::vector<bool> check(N + 1);
    for (int i = 0; i < M; i++) {
        int a;
        std::cin >> a;
        check[a] = true;
    }

    int b = 0, c = 1;
    for (int i = 1; i <= N; i++) {
        if (check[i]) {
            b = c;
            c = 0;
        }
        else {
            int tmp = (b + c) % MOD;
            b = c;
            c = tmp;
        }
    }

    std::cout << c << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,A,B,ans=0;
    cin>>N>>A>>B;
    REP(i,N){
        string S=to_string(i+1);
        int sum=0;
        REP(j,S.size()){
            sum+= S[j] - '0';
        }
        if(A<=sum&&sum<=B)ans+=i+1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    int n;
    cin>>n;
    vector<double> p(n);
    for(int i=0;i<n;i++)cin>>p[i];
    vector<vector<double> > dp(n+1,vector<double>(n+1,0) );
    dp[0][0] = 1;
    for(int i=0;i<n;i++){
	dp[i+1][0] = dp[i][0] * (1-p[i]);
	for(int j=0;j<n;j++){
	    dp[i+1][j+1] = dp[i][j] * p[i] + dp[i][j+1] * ( 1-p[i] );
	}
    }
    double res = 0;
    for(int i=n/2 + 1;i<=n;i++) res += dp[n][i];
    printf("%0.10lf\n",res);
    return 0;
}


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

def main():
    n = int(input())
    d, x = map(int, input().split())

    c = 0
    for _ in range(n):
        a = int(input())
        for b in range(0,100):
            if a * b + 1 <= d:
                c += 1
            else:
                break

    print(c + x)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.next().toCharArray();
		int oddCount = 0;
		int evCount = 0;
		for (int i = 0; i < arr.length; i++) {
			if (i % 2 == 0) {
				if (arr[i] == '0') {
					oddCount++;
				} else {
					evCount++;
				}
			} else {
				if (arr[i] == '0') {
					evCount++;
				} else {
					oddCount++;
				}
			}
		}
		System.out.println(Math.min(oddCount, evCount));
	}
}


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

using namespace std;

const int N = 2e5 + 5;
int n;
long long a[N], sum, cs[N], ans = 1e18;

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

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        cs[i + 1] = cs[i] + a[i];
    }

    sum = cs[n];

    for (int i = 0; i < n - 1; i++)
    {
        ans = min(ans, abs((sum - cs[i + 1]) - cs[i + 1]));
    }

    cout << ans << "\n";
}

Measured memory_bytes: 3328
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace NotFounds
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new ConsoleInput(Console.In, ' '));
            Console.Out.Flush();
        }

        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadInt;
            var b = cin.ReadInt;
            Console.WriteLine(Math.Max(Math.Max(a + b, a - b), a * b));
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
        public void ReadIntArrays(long N, out int[] A, out int[] B) { A = new int[N]; B = new int[N]; for (long i = 0; i < N; ++i) { A[i] = ReadInt; B[i] = ReadInt; }}
    }
}


Measured memory_bytes: 11220
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

uint64_t xorsum_from0(uint64_t n)
{
  if(n==0) return 0;
  if(n%2!=0)
  {
    if(n%4==1) return 1;
    else return 0;
  }
  if((n-1)%4==3) return n;
  else return 1^n; 
}

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

  ll ans=xorsum_from0(a-1)^xorsum_from0(b);
  cout<<ans<<endl;
}

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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  string s;
  cin >> s;
  int res = INT_MAX;
  for (char c = 'a'; c <= 'z'; c++) {
    int tmp = 0;
    string ss(s);
    while (true) {
      bool ok = true;
      for (char cc : ss) {
        if (cc != c) {
          ok = false;
          break;
        }
      }
      if (ok) {
        break;
      }
      int n = ss.size();
      string s2(n - 1, c);
      for (int i = 0; i < n - 1; i++) {
        if (ss.at(i) != c && ss.at(i + 1) != c) {
          s2.at(i) = ss.at(i);
        }
      }
      ss = s2;
      tmp++;
    }
    res = min(res, tmp);
  }
  cout << res << endl;
  return 0;
}


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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

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

    vector<int> a(n);
    if (n % 2 == 0) {
        for (int i = 0; i < n / 2; i++) {
            cin >> a[n / 2 + i] >> a[n / 2 - 1 - i];
        }

    } else {
        cin >> a[n / 2];
        for (int i = 1; i <= n / 2; i++) {
            cin >> a[n / 2 + i] >> a[n / 2 - i];
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i == n - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef long double td;
typedef vector<td> vd;
typedef pair<ll,ll> ii;
typedef vector<ii> vii; typedef vector<bool> vb;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(ll i = ll(a); i < (ll)(b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define show(v,n) cerr << #v << " = "; forn(i,n) cerr << v[i] << " "; cerr << endl;
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
int MAXN = 500005;

 
int main()
{ 	
	FIN;
	#ifdef input
		freopen("test1.txt", "r", stdin);
	#endif
	
	int n, k;
	cin >> n >> k;
	vector <ll> v(n);
	forn(i,n) cin >> v[i];
	
	vector <ll> dp(100005,0), aux(100005,0), prefix(100005,0);
	ll modu = (int)(1e9+7);
	forn(i,v[0]+1) dp[i]=1;
	prefix[0]=dp[0];
	forr(i,1,k+1) prefix[i]=prefix[i-1]+dp[i];
	forr(i,1,n)
	{
		forn(j,k+1)
		{
			aux[j]=prefix[j];
			aux[j]%=modu;
			if(j-v[i] > 0) aux[j]+=modu-prefix[j-v[i]-1];
			aux[j]%=modu;
		}
		forn(j,k+1)
		{
			dp[j]=aux[j];
			if(j==0)
			{
				prefix[j]=aux[j];
				aux[j]=0;
				continue;
			}
			prefix[j]=aux[j]+prefix[j-1];
			prefix[j]%=modu;
			aux[j]=0;
		}
	}
	
	cout << dp[k] << endl;
    return 0;
}


Measured memory_bytes: 5552
n = int(input())
a = [[[0 for vv in range(10)] for ff in range(3)] for bb in range(4)]
hl = "#"*20
for i in range(n):
    b, f, r, v = map(int,input().split())
    a[b-1][f-1][r-1] += v
line = ""
for bb in range(4):
    for ff in range(3):
        for rr in range(10):
            line += " " + str(a[bb][ff][rr])
        print(line)
        line = ""
    if bb != 3:
        print(hl)


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) for (auto i = mp.begin(); i != mp.end(); ++i) { cout << i->first <<":"<<i->second << endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<" ";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,k;
    cin>>a>>b>>k;
    ll ansa = a;
    ll ansb = b;
    if (a-k >= 0) {
        ansa = a-k;
    } else if (a-k < 0 && b-(k-a) > 0) {
        ansa = 0;
        ansb = b-(k-a);
    } else {
        ansa = 0;
        ansb = 0; 
    }

    cout<<ansa<<" "<<ansb<<endl;
    return  0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;




int main()
{
    
    int N,K;
    cin >> N >> K;
    vector<int> V(N);
    rep(i,N) cin >> V[i];
    
    int ans = -2000000000;
    
    for (int A = 0; A <= min(N,K); A++) {
        for (int B = 0; B+A <= min(N,K); B++) {
            
            priority_queue<int, vector<int>, greater<int>> q;
            
            for (int i = 0; i < A; i++) q.push(V[i]);
            for (int i = N-1; i > N-1-B; i--) q.push(V[i]);
                      
            for (int C = 0; C < K-A-B; C++) {
                if(!q.empty()){
                    if(q.top()<0) q.pop();
                    else break;
                }
            }
            int an = 0;
            while (!q.empty()) {
                an += q.top();
                q.pop();
            }
           
            ans = max(an,ans);
            
        }
        
    }
    cout << ans << endl;
    
    
    return 0;
}




Measured memory_bytes: 256
// AOJ 1375 Skinny Polygon
// 2018.3.21 bal4u

#include <stdio.h>
#include <stdlib.h>

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int extended_gcd(int a, int b, int *x, int *y)
{
	int _gcd;
	if (b == 0) { *x = 1; *y = 0; return a; }
	_gcd = extended_gcd(b, a%b, y, x);
	*y -= a / b * (*x);
	return _gcd;
}

int main()
{
	int n, x, y, a, b, g;

	n = in();
	while (n--) {
		x = in(), y = in();
		g = extended_gcd(x, y, &a, &b);
		if (a < 0) a = -a;
		if (b < 0) b = -b;
		if (g < 50000) {
			printf("3\n0 0\n%d %d\n%d %d\n", x, y, b, a);
		} else {
			printf("4\n0 0\n%d %d\n%d %d\n%d %d\n", x, y-1, x/g, y/g, x-1, y);
		}
	}
	return 0;
}


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

int main() {
  int N,K,ans=1;
  cin>>N>>K;
  rep(i,N){
    if (ans*2<ans+K) {
      ans*=2;
    }
    else{
      ans+=K;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    x, y, a, b, c = map(int, input().split())
    p = sorted(list(map(int, input().split())), reverse=True)[0:x]
    q = sorted(list(map(int, input().split())), reverse=True)[0:y]
    r = sorted(list(map(int, input().split())), reverse=True)
    pq = sorted((p + q))
    for i in range(min(c, (x + y))):
        if pq[i] > r[i]:
            break
        pq[i] = r[i]
    print(sum(pq))


if __name__ == '__main__':
    main()


Measured memory_bytes: 28600
#include<stdio.h>
int main()
{
    int a,b,c,d,c1=0,c2=0;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    while(c>0)
    {
       c=c-b;
       c1++;
    }
    while(a>0)
    {
        a=a-d;
        c2++;
    }
    if(c1>c2)
    {
        printf("No\n");
    }
    else
        {
            printf("Yes\n");
        }
 
    return 0;
}

Measured memory_bytes: 1652
#include<bits/stdc++.h>
using namespace std ;
float  a , b ;
int y ;
int main()
{
	float x;
	cin >> a >> b ;
	y = ( a +b ) /2 ;
	float u = y ;
	x = (a+b ) /2;
//	cout << x << " " << u << endl;
	if ( x == u  )
		return cout << x , 0 ;	
	if ( u + 0.5 < x ) 
		cout << u <<"\n" ;
	else
		cout << u+1 << "\n" ;


}


Measured memory_bytes: 384
n = int(input())
a = list(map(int,input().split()))
rate=[0]*13
for i in a:
    rate[i//400]+=1
min = 0
for i in range(8):
    if rate[i]>0:
        min+=1

max = min + rate[8] + rate[9] + rate[10] + rate[11] + rate[12]
if min ==0:
    min=1
print(min,max)


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  if((n/11)%10==0 && n/11== n%11 * 10){
    cout << n << "\n";
  }
  else{
    while((n/11)%10 !=0 || n/11 != n%11 * 10)
      n++;
    cout << n << "\n";
  }
  return 0;
}


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

using namespace std;

const int N = 3e5 + 5000;

int main()
{
#ifdef ONLINE_JUDGE
#else
    // freopen("r.txt", "r", stdin);
    // freopen("w.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    long long x, y;
    cin >> x >> y;
    long long z = x * y;
    if (x == 1 or y == 1)
        cout << 1;
    else {
        cout << (z + 1) / 2;
    }
}

Measured memory_bytes: 256
// AOJ 1147 ICPC国内予選 2007 Problem A "ICPC 得点集計ソフトウェア"
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                int s = sc.nextInt();
                max = Math.max(max, s);
                min = Math.min(min, s);
                sum += s;
            }
            int avg = (sum - min - max) / (n - 2);
            System.out.println(avg);
        }
    }
}

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

long long n;

int main() {
  cin >> n;
  if(n == 1)
    cout << 1 << endl << 0 << endl;
  else if(n == 2)
    cout << 2 << endl << 0 << endl << 11 << endl;
  else {
    cout << n - 1 << endl;
    cout << "00" << endl;
    for(int i = 3; i <= n; ++i) {
      for(int j = 0; j < i; ++j)
        cout << (char)('0' + 1 -
                       ((j == 0) || (j == i - 1)));
      cout << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3104
import sys
H,W=map(int,input().split())
S=[]
for i in range(H):
  t=input()
  s=[]
  for j in t:
    if j==".":
      s.append(0)
    else:
      s.append(j)
  S.append(s)
#print(S)
#sys.exit()
for k in range(H):
  for l in range(W):
    if S[k][l]=="#":
      try:
#        sys.stderr.write(str(S[k-1][l-1]))
        S[k-1][l-1]+=1
        if k<=0 or l<=0:
          S[k-1][l-1]-=1
      except:
#        sys.stderr.write("1\n")
        pass
      try:
        S[k-1][l]+=1
        if k<=0:
          S[k-1][l]-=1
      except:
#        sys.stderr.write("2\n")
        pass
      try:
        S[k-1][l+1]+=1
        if k<=0:
          S[k-1][l+1]-=1
      except:
#        sys.stderr.write("3\n")
        pass
      try:
        S[k][l-1]+=1
        if l<=0:
          S[k][l-1]-=1
      except:
#        sys.stderr.write("4\n")
        pass
      try:
        S[k][l+1]+=1
      except:
#        sys.stderr.write("5\n")
        pass
      try:
        S[k+1][l-1]+=1
        if l<=0:
          S[k+1][l-1]-=1
      except:
#        sys.stderr.write("6\n")
        pass
      try:
        S[k+1][l]+=1
      except:
#        sys.stderr.write("7\n")
        pass
      try:
        S[k+1][l+1]+=1
      except:
#        sys.stderr.write("8\n")
        pass
for m in S:
  ans=""
  for n in m:
    ans+=str(n)
  print(ans)


Measured memory_bytes: 9292
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a*b/gcd(a,b);
}


signed main(void) {
    string s;
    cin >> s;
    int n = s.size();
    int ans = INF;
    rep(i,n-2){
        string t = s.substr(i,3);
        int num = 0;
        rep(j,3){
            num *= 10;
            num += t[j] - '0';
        }
        ans = min(ans, abs(753-num));
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
/*
文字を、辞書順にa,b,c,……とする。
前から順に「その時点でありえる辞書順最小の文字列」を求め、最後まで整合性が取れるかどうかチェックする。
文字列はaが大部分を占めるので、「aに関する情報は持たない」ことにして圧縮する。
例えば"aabaca"という文字列は"(2,b),(4,c),(5,a)"という(index,文字)のペアの列で持つ。
文字列の伸び縮みをうまく実装すると解ける（大変）
*/

#include <stdio.h>
#define rep(i,l,r)for(int i=(l);i<(r);i++)

int n;
int a[200010];
int q[200010];//index
int c[200010];//文字
//(q[i],c[i])の組の列で文字列を保持する

int f(int m){
	int qc=0;
	q[0]=a[0];
	c[0]=1;
	qc=1;
	rep(i,1,n){
		if(a[i]>q[qc-1]){
			//伸びるときは後ろにaを増やすだけ
			q[qc]=a[i];
			c[qc]=1;
			qc++;
		}else if(a[i]==q[qc-1]){
			//同じときは末尾の文字を変えるだけ
			c[qc-1]++;
		}else{
			//縮むときは頑張る
			while(qc&&q[qc-1]>a[i])qc--;
			if(qc&&q[qc-1]==a[i]){
				c[qc-1]++;
			}else{
				q[qc]=a[i];
				c[qc]=2;
				qc++;
			}
		}
		
		if(c[qc-1]>m){
			int t=a[i];
			//末尾は(t,>m)なので、これをpopして(t-1,*)をincしたい
			while(c[qc-1]>m){
				//1文字目が溢れたらどうしようもない
				if(t==1)return 0;
				qc--;//pop
				if(qc&&q[qc-1]==t-1){
					c[qc-1]++;
				}else{
					q[qc]=t-1;
					c[qc]=2;
					qc++;
				}
				t--;
			}
			//(a[i],1)を追加し直す
			q[qc]=a[i];
			c[qc]=1;
			qc++;
		}
	}
	return 1;
}

int main(){
	scanf("%lld",&n);
	rep(i,0,n)scanf("%lld",a+i);
	
	//答えをにぶたん
	int lans=0,rans=200010;//lはng,rはok
	while(rans-lans>1){
		int m=(lans+rans)/2;
		if(f(m))rans=m;
		else lans=m;
	}
	printf("%d",rans);
}

Measured memory_bytes: 2560
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)

int main() {
  string s;
  cin >> s;
  int g = 0, p = 0;
  rep(i, 0, s.size()) {
    g += s[i] == 'g';
    p += s[i] == 'p';
  }
  cout << max(0, (g - p) / 2) << endl;
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    int p[N];
    for (int i = 0; i < N; i++) cin >> p[i];
    sort(p, p+N);
    int sum = 0;
    for (int i = 0; i < N; i++) {
        if (i != N-1) {
            sum += p[i];
        } else {
            sum += p[i] / 2;
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int getAns(int a, int b, int c, int k){
    if(k <= a)
        return k;
    else if (k <= a + b)
        return a;
    else
        return a - (k - (a + b));
}
int main(){
    int a, b, c, k;
    scanf("%d %d %d %d", &a, &b, &c, &k);
    printf("%d", getAns(a, b, c, k));
    return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
#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()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N; cin >> N;
	vector<int> a(N, 0);
	rep (i, N){
		cin >> a[i];
	} // end rep

	map<int,int> cnt; cnt.clear();
	rep (i, N){
		++cnt[a[i]];
	} // end rep

	int even = 0;
	int odd = 0;
	map<int,int>::iterator it = cnt.begin();
	for (; it != cnt.end(); ++it){
		int n = (*it).first;
		int c = (*it).second;
		even += (c % 2 == 0);
		odd += (c % 2 != 0);
	} // end for

	int res = 0;
	res += odd;
	res += (even % 2 == 0 ? even : even - 1);
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 5376
n = gets.to_i
as = gets.split.map(&:to_i)

l = Array.new(n+1)
r = Array.new(n+1)
l[0] = 0
r[n] = 0
(1..n).each do |i|
  l[i] = l[i-1].gcd(as[i-1])
  # r[i] = l[i-1].gcd(as[i-1])
end

(n-1).downto(0).each do |i|
  r[i] = r[i+1].gcd(as[i])
end

ms = Array.new(n)
ans = []
(0..n-1).each do |i|
  ans << l[i].gcd(r[i+1])
end

puts ans.max

Measured memory_bytes: 11788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
int main() {
  int n;
  cin >> n;
  set<string> a;
  rep(i,n){
    string s;
    cin >> s;
    a.insert(s);
  }
  cout << a.size() << endl;
}


Measured memory_bytes: 19208
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<valarray>//なんとなく追加
//メモ：表示桁数を大きくする　　cout << fixed << setprecision(20) << cm << endl;
using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define pause system("pause")
#define PI acos(-1.0)


signed main() {
	ll N, K, mo=0, D=-1,deg,left;
	cin >> N >> K;
	vector<int> A(N);
	vector<int> F(N, -1);
	REP(i, N) {
		cin >> A.at(i);
	}
	for (ll i = 0; i < K; i++) {
		if (F.at(mo) != -1) {
			D = i;
			break;
		}
		F.at(mo) = i;
		mo = A.at(mo)-1;
	}
	if (D == -1) {
		cout << mo + 1 << endl;
		return 0;
	}

	deg = D - F.at(mo);
	left = (K - D) % deg;
	for (ll j = 0; j < left; j=j+1) {
		mo = A.at(mo)-1;
	}

	cout << mo+1 << endl;
	pause;
}

Measured memory_bytes: 4852
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

string S;

LL ans = 0;

void solve(){
	int N = S.size();
	reverse(S.begin(),S.end());
	//S[0]S[1]S[2]...S[i]という数値を考えた時、
	//それが2019の倍数であるかどうかを調べる

	//10のi乗を2019で割ったあまりを
	//pow10[i]とおく
	vector<LL> pow10(200001,1);
	for(int i=1;i<=200000;i++){
		pow10[i] = (pow10[i-1]*10LL)%2019LL;
	}

	LL num = 0;
	//2019で割ったあまりがiになるような数の
	//桁数をi別に保管していく
	vector<LL> counter(2019);
	for(int i=0;i<N;i++){
		LL new_digit = ((S[i]-'0')*pow10[i])%2019LL;
		num = (num + new_digit)%2019LL;
		//cout << i << ":" << num << endl;
		counter[num]++;
	}

	ans += counter[0]*(counter[0] - 1)/2LL;
	ans += counter[0];
	for(int i=1;i<2019;i++){
		//if(counter[i])cout << i << ":" << counter[i] << endl;
		ans += (counter[i]*(counter[i]-1LL))/2LL;
	}
}
 
int main(){
    cin >> S;
 
    solve();

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4620
A, B = map(int, input().split())
A -= 1


def calc(n):
    if n % 2 == 1:
        if (n + 1) % 4 == 0:
            return 0
        else:
            return 1
    else:
        return calc(n-1) ^ n


print(calc(B) ^ calc(A))



Measured memory_bytes: 38256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define ll long long

using namespace std;

int main () {
    ll n;
    cin >> n;
    multiset <ll> se;

    vector <ll> vec (n);
    for(ll i = 0; i < n; i++)
    {
        cin >> vec[i];
    }

    for(ll i = 0; i < n; i++)
    {
        ll cur = vec[i];
        auto itr = se.lower_bound(cur);

        if(itr != se.begin())
        {
            se.erase(--itr);
        }
        se.insert(cur);
    }
    cout << se.size() << endl;
    return  0 ;
}


Measured memory_bytes: 5760
from sys import exit
import math
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = li()
N = []
N.append(n[0])

for i in range(1,3,1):
    if n[i] in N: continue
    N.append(n[i])

if len(N) == 2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9184
#include<stdio.h>

#define true 1
#define false 0

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

int main(){
  int i, n, q, m;
  int A[2000];

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &A[i]);
  }

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

  return 0;
}



Measured memory_bytes: 2080
#include <iostream>
#include <string>
#include <sstream>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <bitset>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

struct dd{
    int id,f;
    dd(){
        id=0;
        f=-1;
    }
    dd(int a,int b){
        id=a;
        f=b;
    }
};
bool data[101][101]={};

void f1(dd*,int,int&,int);

int main()
{
    int N,M,num1,num2;
    dd ddata[101]={};
    cin>>N;
    int val[101]={};
    for(int i=0;i<N;i++){
        cin>>num1;
        cin>>M;
        val[num1]=-1;
        for(int j=0;j<M;j++){
            cin>>num2;
            data[num1][num2]=true;
        }
    }
    int time=1;
    queue<dd> que;
    bool vd[101]={};
    que.push(dd(1,0));
    vd[1]=true;
    for(dd ddata=que.front();!que.empty();que.pop(),ddata=que.front()){
        val[ddata.id]=ddata.f;
        for(int i=1;i<=N;i++){
            if(data[ddata.id][i]&&!vd[i]){
                vd[i]=true;
                que.push(dd(i,ddata.f+1));
            }
        }
    }
    for(int i=1;i<=N;i++){
        cout<<i<<' '<<val[i];
        cout<<endl;
    }
}

Measured memory_bytes: 1208
#include<stdio.h>
int main(void){
  int book,pay,rest;
  int a,b,c;
  
  while(1){
  scanf("%d %d",&book,&pay);
  if(book==0 && pay==0)
    break;
  rest=pay-book;
  
  a=rest/1000;
  rest=rest-1000*a;

  b=rest/500;
  rest=rest-500*b;

  c=rest/100;
  
  printf("%d %d %d\n",c,b,a);
  }
  return 0;
}
  
  

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int[] town = new int[5];

		for(int i = 0; i < 3; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			town[a]++;
			town[b]++;
		}

		for(int i = 1; i <= 4; i++) {
			if(town[i] > 2) {
				System.out.println("NO");
				return;
			}
		}

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

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

using namespace std;

int main(void) {
  int n;
  while (cin >> n, n) {
    vector<int> l(n);
    for (int i = 0; i < n; i++) {
      cin >> l[i];
    }

    const int mod = 256;
    int anss = 16, ansa = 16, ansc = 16;
    double minh = 1e9;
    for (int s = 0; s < 16; s++) {
      for (int a = 0; a < 16; a++) {
        for (int c = 0; c < 16; c++) {
          int r = s, cnt[256] = {};
          for (int i = 0; i < n; i++) {
            r = (a * r + c) % mod;
            cnt[(l[i] + r) % mod]++;
          }
          
          double h = 0.0;
          for (int i = 0; i < 256; i++) {
            if (!cnt[i]) continue;
            h += cnt[i] * log((double)cnt[i] / n);
          }
          h = -h / n;

          if (h - minh < -1e-10) {
            minh = h;
            anss = s, ansa = a, ansc = c;
          }
        }
      }
    }

    cout << anss << " " << ansa << " " << ansc << endl;
  }

  return 0;
}


Measured memory_bytes: 3320
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
        n: usize, w: usize, h: usize
    };
    println!("{}", (n-w+1)*(n-h+1));
}


Measured memory_bytes: 4352