akhauriyash/Code-Regression huggingface dataset:
// テヲツつイテ」ツ?療」ツ??
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
 
using namespace std;
 
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
 
deque<char> plus1(deque<char> const& a) {
 
  if(a == deque<char>{'0'}) { return {'1'}; }
 
  deque<char> ret; ret.push_back('0');
  copy(a.begin(), a.end(), back_inserter(ret));
  ret.back() += 1;
  int N = ret.size();
  int idx = N-1;
  while(ret[idx] == '9' + 1) {
    ret[idx] = '0';
    ret[--idx] += 1;
  }
 
  deque<char> ans;
  bool ok = false;
  REP(i, 0, N) {
    if(ok || (ret[i] != '0')) {
      ok = 1;
      ans.push_back(ret[i]);
    }
  }
 
  return ans;
}
 
deque<char> zeroclear(deque<char>& s) {
  deque<char> ret;
  bool ok = false;
  rep(i, s.size()) {
    if(ok || s[i] != '0') {
      ok = 1;
      ret.push_back(s[i]);
    }
  }
  if(ret.empty()) { ret.push_back('0'); ; }
  return ret;
}
struct comp {
bool operator() (deque<char> const& a, deque<char> const& b) {
  int asize = a.size(), bsize = b.size();
  if(asize != bsize) { return asize < bsize; }
  for(int i=0; i<asize; i++) {
    if(a[i] != b[i]) {
      return a[i] < b[i];
    }
  }
  return 0;
}
};
 
int main() {
 
  int N; cin >> N;
  string S;
  rep(i, N) {
    char ch; cin >> ch;
    S.push_back(ch);
  }
 
  set<deque<char>, comp> vs;
  rep(i, N) {
    deque<char> s;
    REP(j, i, N) {
      if(j - i > 7) { continue; }
      s.push_back(S[j]);
      vs.insert(zeroclear(s));
    }
  }
 
//  int cc = 0;
//  for(auto& s: vs) { if(++cc >= 15) { break; } rep(i, s.size()) { cout << s[i]; } cout << endl; }cout << endl;
//  rep(i, v.size()) {  cout << v[i] << endl; }cout << endl;
 
  deque<char> curr; curr.push_back('0');
  for(auto& s: vs) {
    if(curr != s) {
      rep(i, curr.size()) { cout << curr[i]; }
      cout << endl;
      exit(0);
    }
    curr = plus1(curr);
//    cout << "---\n";   cout << curr << endl;
  }
 
  rep(i, curr.size()) { cout << curr[i]; }
  cout << endl;
 
  return 0;
}

Measured memory_bytes: 7012
import itertools
import sys

"""
1個4ドルのケーキX個と1個7ドルのドーナツY個
合計Nドルとなる買い方があるときはyes、逆はno

1<= N <=100
4 * X + 7 * Y = N
0<= X <= 25, 0<= Y <= 14
"""

N = int(input())
X = list(range(26))
Y = list(range(15))

for i, j in list(itertools.product(X, Y)):
  if 4 * i + 7 * j == N:
    print('Yes')
    sys.exit()
print('No')

Measured memory_bytes: 38384
import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [str(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))
def f(n):
    #print(l)
    if n%2 == 0:
        return n//2
    else:
        return 3*n + 1
if __name__ == "__main__":
    n = i()
    c = 0
    cnt = 1
    l = [n]
    #if n != 2 or n != 1 or n != 4:l = [n]
    while c < 2:
        n = f(n)
        cnt += 1
        if n in l:
            print(cnt)
            break
        l.append(n)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;

class Vertice{
    private:
    int idx;
    vector<Vertice*> neighbors;
    public:
    void clear(){
        this->neighbors.clear();
    }
    void addNeighbor(Vertice* neighbor){
        this->neighbors.push_back(neighbor);
    }
    vector<Vertice*> &getNeighbors(){
        return this->neighbors;
    }
    void setIndex(const int index){
        this->idx=index;
    }
    int getIndex(){
        return this->idx;
    }
};

vector<int> getPath(const vector<Vertice> &vertices){
    unordered_set<void*> inque;
    deque<Vertice*> dq;
    dq.push_back((Vertice*)&vertices[0]);
    inque.insert((void*)&vertices[0]);
    for(bool updated=true; updated; ){
        updated=false;
        Vertice *u = dq.front();
        for(Vertice *v : u->getNeighbors()){
            if(!inque.count((void*)v)){
                dq.push_front(v);
                inque.insert((void*)v);
                updated=true;
                break;
            }
        }
        if(updated)continue;
        u = dq.back();
        for(Vertice *v : u->getNeighbors()){
            if(!inque.count((void*)v)){
                dq.push_back(v);
                inque.insert((void*)v);
                updated=true;
                break;
            }
        }
    }
    vector<int> foo(dq.size(), 0);
    for(int i=0; i<(int)dq.size(); i++){
        foo[i]=dq[i]->getIndex()+1;
    }
    return foo;
}

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m)!=EOF){
        vector<Vertice> vertices;
        vertices.resize(n);
        for(int i=0; i<n; i++){
            vertices[i].setIndex(i);
        }
        for(int i=0; i<m; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            u--;
            v--;
            vertices[u].addNeighbor(&vertices[v]);
            vertices[v].addNeighbor(&vertices[u]);
        }
        vector<int> foo=getPath(vertices);
        printf("%lu\n", foo.size());
        for(size_t i=0; i<foo.size(); i++){
            printf("%d%c", foo[i], " \n"[i==foo.size()-1]);
        }
    }
    return 0;
}

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
template<class T>
inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}
template<class T>
inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

int n,m,x;
int a[12][12];
int main(){
    cin >> n >> m >> x;
    vector<int> c(n);
    REP(i,n)
    {
        cin >> c[i];
        REP(j,m)cin >> a[i][j];
    }
    int ans = 1001001001;
    REP(s,1<<n){
        int co=0;
        vector<int> d(m);
        REP(i,n){
            if(s>>i&1){
                co += c[i];
                REP(j,m)d[j]+=a[i][j];
            }
        }
        bool ok = true;
        REP(j,m)if(d[j]<x)ok=false;
        if(ok)chmin(ans,co);
    }
    if(ans==1001001001)cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
#define rep(k,i,n) for(int i=k;i<n;++i)
int main(void){
    // Your code here!
    long N,sum=0;
    cin>>N;
    rep(0,i,N){
        sum+=i;
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int a,b,k,div;
  scanf("%d%d%d",&a,&b,&k);
  if (a>b){
    div=b+1;
  }
  else {
    div=a+1;
  }
  while (k>0){
    div--;
    if (a/div*div==a && b/div*div==b){
      k--;
    }
  }
  printf("%d\n",div);
  return 0;
}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    vector<vector<ll>> dp(n + 1, vector<ll>(4, 0));

    for (int i = n; i >= 0; i--) {
        for (int j = 3; j >= 0; j--) {
            if (i == n) {
                if (j == 3) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            } else {
                dp[i][j] = dp[i + 1][j] * (s[i] == '?' ? 3 : 1);
                if (j < 3 && (s[i] == '?' || (j == 0 && s[i] == 'A') || (j == 1 && s[i] == 'B') || (j == 2 && s[i] == 'C') )) {
                    dp[i][j] += dp[i + 1][j + 1];
                }
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[0][0] << endl;
}


Measured memory_bytes: 7424
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def com(com_n, com_r):
    if com_n<com_r:return 0
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

# combinationの準備
# md>n_maxの条件
md = 10**9+7
n_max = 10**5+3
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def main():
    n=int(input())
    aa=LI()
    pos=[-1]*(n+3)
    for i,a in enumerate(aa):
        if pos[a]==-1:pos[a]=i
        else:lr=n-i+pos[a]
    for k in range(1,n+2):
        ans=com(n+1,k)-com(lr,k-1)
        print(ans%md)

main()

Measured memory_bytes: 21716
/**
  * author : thegeniushead
**/
#include <bits/stdc++.h>
 
/*.....DEFINITIONS...... */
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define T() int tt; cin>>tt; while(tt--)
#define rep(i,start,lim) for(int i=start;i<lim;i++)
#define rep1(i,start,lim) for(int i=start; i<=lim; ++i)
#define repd(i,start,lim) for(int i=start;i>=lim;i--)
#define mp make_pair
#define pb push_back
#define lchild (2*node+1)
#define rchild (2*node+2)
#define ff first
#define ss second
#define br cout<<"\n"
#define MOD (1000000007LL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eps (1e-6)
#define sll(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define what_is(x) cerr << #x << " is " << x << "\n";
#define int long long int
#define infll 9e18
#define inf 1e12

using namespace std;
 
/*.....TYPEDEFS ....*/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long double ld;
 
/*....USEFUL FUNCTIONS....*/
ll pwr(ll base, ll exp, ll mod=MOD){ll res=1; while(exp>0){if(exp%2){res=(res*base)%mod;}base=(base*base)%mod;exp/=2;}return res;}
ll gcd(ll a, ll b){ if(b==0)return a; else gcd(b, a%b);}
bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if (n%2==0||n%3==0)return false;for(int i=5; i*i<=n; i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
 
/*....I/O Functions...*/
inline string rs(){char x[1234567];scanf("%s", x);string s = x; return s;}
inline int ri(){int x; scanf("%d", &x);return x;}
inline long long rl(){long long x; scanf("%lld", &x); return x;}
 
/*---------Solution below this line --------*/
 
const int N = 1234567;

string s;

int32_t main()
{
	FIO
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	cin >> s;
	
	rep(i,0,s.length()-1){
		if(s[i]=='A' and s[i+1]=='C'){
			return cout << "Yes\n", 0;
		}
	}
	
	cout << "No\n";
	
	
	
	
	return 0;
}

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

using namespace std;

#define INF 1e9

int main() {
    int n, k;

    cin >> n >> k;

    vector<int> h(n);

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

    vector<int> dp(n);

    dp.at(0) = 0;

    for(int i = 1; i < n; ++i) {
        int mintmp = INF;
        for(int j = 1; j <= k; ++j) {
            if(i - j >= 0) {
                mintmp = min(mintmp, dp.at(i - j) + abs(h.at(i) - h.at(i - j)));
            }
        }
        dp.at(i) = mintmp;
    }

    printf("%d\n", dp.at(n - 1));

    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int tra(int a)
{
    if(a==1||a==4||a==7)
        return 1;
    if(a==2||a==8)
        return 2;
    if(a==3||a==6||a==9)
        return 3;
}
int main()
{
    char str[100001];
    int number[100001];

    while(cin>>str)
    {
        int min=99999999;
        if(str[0]=='#')
            break;
        int len=strlen(str);
            for(int i=0; i<len; i++)
            {
                number[i]=tra(str[i]-'0');
            }
            for(int l=1; l<=9; l++)
            {
                if(l==5)
                {
                    continue;
                }
                for(int r=1; r<=9; r++)
                {
                    if(r==5||l==r||tra(l)>tra(r)||l==str[0]-'0'||r==str[0]-'0')
                    {
                        continue;
                    }
                    for(int j=0; j<2; j++)
                    {
                        int flag=j;
                        int left=tra(l);
                        int right=tra(r);
                        int num1=0;
                        for(int i=0; i<len; i++)
                        {
                            int tmp=number[i];
                            if(!flag)
                            {
                                if(tmp<=right)
                                {
                                    flag=1;
                                    left=tmp;
                                }
                                else
                                {
                                    right=tmp;
                                    num1++;
                                }
                            }
                            else
                            {
                                if(left<=tmp)
                                {
                                    flag=0;
                                    right=tmp;
                                }
                                else
                                {
                                    left=tmp;
                                    num1++;
                                }
                            }
                        }
                        if(min>num1)
                        {
                            min=num1;
                        }

                    }

                }
            }
            printf("%d\n",min);
        }
    return 0;
}

Measured memory_bytes: 1612
import sys
input = sys.stdin.readline

import numpy as np

MOD = 998244353  
N,M = map(int,input().split())

def cumprod_mod(arr):
    L = len(arr); Lsq = int((L**.5)+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

# x^n = a+bx mod 1-3x+x^2
Nsq = int((N**.5)+1)
a = np.zeros((Nsq,Nsq+1),dtype=np.int64)
b = np.zeros((Nsq,Nsq+1),dtype=np.int64)
a[0,0] = 1
for n in range(1,Nsq+1):
    a[0,n] = -b[0,n-1] % MOD; b[0,n] = (a[0,n-1]+3*b[0,n-1]) % MOD
u,v = a[0,Nsq],b[0,Nsq]
for n in range(1,Nsq):
    a[n] = (a[n-1]*u-b[n-1]*v) % MOD
    b[n] = (a[n-1]*v+b[n-1]*u+3*b[n-1]*v) % MOD
a = a[:,:-1].ravel()
b = b[:,:-1].ravel()
G = (-a-2*b) % MOD
G = G[:N+1]

A,B = -G[N-1],-G[N]+3*G[N-1]
A,B = A+B,-B
A %= MOD; B %= MOD

def fibonacci(n):
    # a+bx mod 1+x-x^2
    if n == 0:
        return 1,0
    a,b = fibonacci(n//2)
    a,b = a*a+b*b,2*a*b+b*b
    a,b = a%MOD,b%MOD
    return (b,a+b) if n&1 else (a,b)

x = (np.arange(N,dtype=np.int64)+M)%MOD
x[0] = 1
num = cumprod_mod(x)

x = np.arange(N,dtype=np.int64)
x[0] = 1
fact = cumprod_mod(x)

x = np.arange(N,0,-1,dtype=np.int64)
x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod_mod(x)[::-1]

if N == 1:
    x = 0
else:
    x = ((num * fact_inv % MOD)[:N-1] * G[N-2::-1] % MOD).sum() % MOD
y,z = fibonacci(M+1)
answer = (z*A + y*B + x)%MOD
print(answer)

Measured memory_bytes: 31216
N = int(input())
A = list(map(int,input().split()))
chk = [0] * N 
ans = []
cnt = 0

for i in reversed(range(1,N+1)):
    if i > N // 2:
        if A[i-1] == 1:
            ans.append(i)
            chk[i-1] = 1
            cnt += 1
    else:
        j = 2 * i
        ret = 0
        while j <= N:
            ret += chk[j-1] 
            j += i
        if A[i-1] != ret%2:
            ans.append(i)
            chk[i-1] = 1
            cnt += 1
            
print(cnt)
print(*ans)

Measured memory_bytes: 99484
n, m = map(int, input().split())

a=0
b=n
for i in range(m):
  l, r = map(int, input().split())
  a = max(a, l)
  b = min(b, r)
if b-a+1 >= 0:
  print(b-a+1)
else:
  print(0)

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

int main(){
    vector<int> v(9991);
    int month = 0;
    for(int i=1; i<=999; i++){
        for(int j=1; j<=10; j++){
            month++;
            if(i%3 == 0) v[month] = 20;
            else if(j%2 == 0) v[month] = 19;
            else if(j%2 == 1) v[month] = 20;
        }
    }

    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
        int y, m, d;
        cin >> y >> m >> d;

        m += 10*(y-1);
        int ans = 0;
        for(int j=m; j<=v.size(); j++) ans += v[j];
        ans -= (d-1);
        cout << ans << endl;
    }
}


Measured memory_bytes: 3080
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))

counter=1
now=1
gone_set={1}
gone_list=[1]
place=1
while counter<=K:
    next=A[now]
    place=next
    if next in gone_set:
        start=gone_list.index(next)
        loop=len(gone_list)-start
        last=(K-start)%loop
        place=gone_list[start+last]
        break
    else:
        gone_set.add(next)
        gone_list.append(next)
        now=next
        counter+=1

print(place)

        



Measured memory_bytes: 32308
#include<iostream>
#include<string>
using namespace std;
int main(){
  int x;
string a;
cin>>a;
if(a=="MON")
  x=6;
if(a=="TUE")
  x=5;
if(a=="WED")
	x=4;
if(a=="THU")
	x=3;
if(a=="FRI")
	x=2;
if(a=="SAT")
	x=1;
if(a=="SUN")
	x=7;
cout<<x;
}

Measured memory_bytes: 256
require 'pp'

n = gets.to_i
comb = [
    [0,0,0],[0,0,1],[0,1,0],[0,1,1],
    [1,0,0],[1,0,1],[1,1,0],[1,1,1],
]

memo = Hash.new(0)

1.upto(100) do |x|
    1.upto(100) do |y|
        1.upto(100) do |z|
            f = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            memo[f] += 1
        end
    end
end

1.upto(n) do |i|
    puts memo[i]
end


Measured memory_bytes: 16776
#include <iostream>
#define llint long long

using namespace std;

llint n;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		llint x = i*108/100;
		if(x == n) {
			cout << i << endl;
			return 0;
		}
	}
	cout << ":(" << endl;
	
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(n):
    minj=i
    for j in range(i,n):
        if a[j]<a[minj]:
            minj=j
    if i!=minj:
        a[i],a[minj]=a[minj],a[i]
        count=count+1
print(" ".join(map(str,a)))
print(count)


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

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

  static const int MAXN = 1e5 + 5;
  int n, m;
  cin >> n >> m;

  static pair<int, int> ab[MAXN];
  for (int i = 0; i < n; ++i) cin >> ab[i].first >> ab[i].second;
  sort(ab, ab + n);
  static int b[MAXN];
  for (int i = 0; i < n; ++i) b[i + 1] = ab[i].second;
  // for (int i = 0; i <= n; ++i) cerr << b[i] << ' ';
  // cerr << '\n';
  for (int i = 1; i <= n; ++i) b[i - 1] ^= b[i];

  // for (int i = 0; i <= n; ++i) cerr << b[i] << ' ';
  // cerr << '\n';
  static vector<int> adj[MAXN];
  static map<pair<int, int>, int> cords;

  for (int i = 1; i <= m; ++i) {
    int l, r;
    cin >> l >> r;
    l = lower_bound(ab, ab + n, make_pair(l, 0)) - ab;
    r = lower_bound(ab, ab + n, make_pair(r + 1, 0)) - ab;
    // cerr << l << ' ' << r << '\n';
    adj[l].push_back(r);
    adj[r].push_back(l);
    cords[make_pair(l, r)] = cords[make_pair(r, l)] = i;
  }

  static stack<int> stk1, stk2;
  static int pa[MAXN];
  for (int i = 0; i <= n; ++i) {
    stk1.push(i);
    pa[i] = -1;
  }
  while (!stk1.empty()) {
    int u = stk1.top();
    stk1.pop();
    // cerr << u << '\n';
    if (pa[u] < 0) stk2.push(u);
    for (int v : adj[u]) {
      if (pa[v] >= 0) continue;
      if (v == pa[u]) continue;
      pa[v] = u;
      stk1.push(v);
      stk2.push(v);
    }
  }

  static vector<int> ans;
  while (stk2.size() > 1) {
    int u = stk2.top();
    stk2.pop();
    if (!b[u]) continue;
    b[u] ^= 1;
    if (pa[u] < 0) {
      cout << "-1\n";
      exit(0);
    }
    b[pa[u]] ^= 1;
    ans.push_back(cords[make_pair(u, pa[u])]);
  }

  // for (int i = 0; i <= n; ++i) cerr << b[i] << ' ';
  // cerr << '\n';

  cout << ans.size() << '\n';
  sort(ans.begin(), ans.end());
  for (int x : ans) cout << x << ' ';
  return 0;
}


Measured memory_bytes: 35180
#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define MRE assert(0);
const int inf = 1e17;
const int mod = 998244353;
typedef pair<int, int> P;
typedef pair<int, P> PP;
int modpow(int a, int x) {
	int res = 1;
	while (x) {
		if (x&1)res = res*a%mod;
		a = a*a%mod;
		x >>= 1;
	}
	return res;
}
int gcd(int a, int b) {
	if (!b)return a; return gcd(b, a%b);
}
int btoi(string s) {
	int res = 0;
	rep(i, s.size()) {
		res *= 2;
		if (s[i] == '1')res++;
		res %= mod;
	}
	return res;
}

map<int, int>moebius(int n) {
	map<int, int>res;
	vector<int>prime;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0) {
			prime.push_back(i);
			while (n%i == 0)n /= i;
		}
	}
	if (n != 1)prime.push_back(n);
	int m = prime.size();

	for (int i = 0; i < (1 << m); i++) {
		int mu = 1, d = 1;
		rep(j, m) {
			if (i >> j & 1) {
				mu *= -1; d *= prime[j];
			}
		}
		res[d] = mu;
	}
	return res;
}

signed main() {
	int n; cin >> n;
	string x; cin >> x;
	vector<int>V;
	for (int i = 1; i*i <= n; i++) {
		if (n%i == 0) {
			V.push_back(i);
			if (i*i != n)V.push_back(n / i);
		}
	}
	sort(V.begin(), V.end());
	map<int, int>M1 = moebius(n);
	map<int, int>M2;
	int ans = 0;
	for (int Z : V) {
		if (Z % 2 == 0)continue;
		string p1, p2, q;
		rep(i, n / Z)p1.push_back(x[i]);
		p2 = p1;
		rep(i, p2.size()) {
			if (p2[i] == '0')p2[i]++; else p2[i]--;
		}
		rep(i, Z) {
			if (i & 1)q += p2; else q += p1;
		}
		int score;
		if (x < q)score = btoi(p1);
		else score = btoi(p1) + 1;
		int num = 0;
		for (int Y : V) {
			if (Y == Z)break;
			if (Z%Y == 0) {
				num += M2[Y];
			}
		}
		M2[Z] = 2 * n / Z - num;
		if (M2[Z] > 0) {
			ans = (ans + M2[Z] * score) % mod;
		}
		else {
			ans = (ans + -1*(abs(M2[Z])*score%mod)+mod) % mod;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1288
#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
#define lo long
const int lmax=1999999999;
const long long lmx=1999999999999999999;
int gr[100003];
int n,a[100003],k;
set<int>s;
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++){
	cin>>a[i];
}
for(int i=1;i<=k;i++){
	s.clear();
	for(int j=1;j<=n;j++){
		if(i-a[j]>=0){
			s.insert(gr[i-a[j]]);
		}
	}
	int c=0,ok=0;
	for(set<int>::iterator it=s.begin();it!=s.end();it++){
		if(c==(*it))c++;else{
		 ok=1;
			break;
		}
	}
	gr[i]=c;
}
if(gr[k]!=0){
	cout<<"First"<<endl;
}
else{
	cout<<"Second"<<endl;
}
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/





Measured memory_bytes: 640
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for i in range(n):
        a, b, c = abc[i]
        dp0, dp1, dp2 = dp
        dp = [ max(dp1 + a, dp2 + a), \
               max(dp0 + b, dp2 + b), \
               max(dp0 + c, dp1 + c) ]
    return(max(dp))

n = int(input())    # 1 <= n <= 10^5
abc = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, abc))


Measured memory_bytes: 31948
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2　//1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) (max(x,y)-min(x,y))
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;

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

  lol x, y;
  cin >> x >> y;
  lol ans = 0;
  while(x <= y){
    ans ++;
    x *= 2;
  }
  cout << ans << '\n';
  return 0;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = { 0,1,0,-1,1,-1,1,-1};
const int dx[] = { 1,0,-1, 0,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}
template<typename T>
ll FindErase(vector<T> &v,T tar){
  ll cnt = 0;
  for(auto it = v.begin(); it != v.end();){
    if(*it == tar){
      it = v.erase(it);
      ++cnt;
    }
    else{
      ++it;
    }
  }
  return cnt;
}

template<typename T>
bool SuffixErase(vector<T> &v,size_t suf){
  if(suf > v.size()) return false;
  for(auto it = v.begin(); it != v.end();){
    if(distance(v.begin(),it) == suf){
      v.erase(it);
      return true;
    }
    else{
      ++it;
    }
  }
  return false;
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m;
  while(cin >> n >> m && n && m){
    string s;
    ll k,x=1,y=1,dir = 0;
    while(cin >> s ){
      if(s == "STOP") break;
      if(s == "FORWARD"){
        cin >> k;
        x += k * dx[dir];
        y += k * dy[dir];
      }
      else if(s == "BACKWARD"){
        cin >> k;
        x -= k * dx[dir];
        y -= k * dy[dir];
      }
      else if(s == "RIGHT"){
        ++dir;
      }
      else{
        --dir;
      }
      dir +=4;
      dir %= 4;
      if(x < 1) x = 1;
      if(y < 1) y = 1;
      if(x > m) x = m;
      if(y > n) y = n;
    }
    if(x > m) x = m;
    if(y > n) y = n;
    cout << y << ' ' << x << endl;
  }
  return 0;
}

Measured memory_bytes: 3180
x, n = map(int, input().split())
p = list(map(int, input().split()))

for i in range(100):
    if x - i in p:
        if x + i in p:
            continue
        else:
            print(x + i)
            exit()
    else:
        print(x - i)
        exit()
else:
    print(x)

Measured memory_bytes: 9044
#include<iostream>
int main()
{
	int H_W[10000][2];
	int number;
	for(int i = 0;; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			std::cin >> H_W[i][j];
		}
		if(H_W[i][0] == 0 && H_W[i][1] == 0)
		{
			number = i;
			break;
		}
	}
	for(int i = 0; i < number; i++)
	{
		for(int h = 0; h < H_W[i][0]; h++)
		{
			for(int w = 0; w < H_W[i][1]; w++)
			{
				std::cout << (h % 2 == w % 2 ? '#' : '.');
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	}
	return 0;
}


Measured memory_bytes: 3084
N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(1,N-1):
  if min([P[i-1],P[i],P[i+1]]) != P[i] and P[i] != max([P[i-1],P[i],P[i+1]]):
    ans += 1
print(ans)

Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
from sys import stdin

def greatest_common_divisor3(x, y):
  xx = max(x, y)
  yy = min(x, y)
  v1 = xx % yy
  #print("{} {}".format(yy, v1))  # TODO delete
  if yy <= 0 or v1 <= 0:
    return max(yy, v1)
  else:
    return greatest_common_divisor3(yy, v1)

x_y = list(map(int, stdin.readline().split()))
print(greatest_common_divisor3(x_y[0], x_y[1]))


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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def bit_count(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()
V = inputIL()
C = inputIL()

d = [V[i]-C[i] for i in range(N)]

d.sort()
p = bisect.bisect(d,0)

print(sum(d[p:]))

Measured memory_bytes: 63980
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		boolean[] prime = get(100000);
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int p = sc.nextInt();
		while(n != -1 || p != -1){
			ArrayList<Integer> res = new ArrayList<Integer>();
			ArrayList<Integer> pl = new ArrayList<Integer>();
			for(int i = n + 1; pl.size() < p; i++){
				if(prime[i]){
					pl.add(i);
				}
			}
			
			for(int i = 0; i < pl.size(); i++){
				for(int j = i; j < pl.size(); j++){
					res.add(pl.get(i) + pl.get(j));
				}
			}
			Collections.sort(res);
			System.out.println(res.get(p - 1));
			
			n = sc.nextInt();
			p = sc.nextInt();
		}
		sc.close();
	}
	static boolean[] get(int x){
		boolean[] res = new boolean[x * 2];
		Arrays.fill(res, true);
		res[0] = false;
		res[1] = false;
		for(int i = 2; i < res.length; i++){
			if(res[i]){
				for(int j = i + i; j < res.length; j += i){
					res[j] = false;
				}
			}
		}
		return res;
	}
	static LinkedList<Integer> gett(){
		LinkedList<Integer> list = new LinkedList<Integer>();
		list.add(2);
		for(int i = 3; i < 100000; i++){
			boolean flg = true;
			for(int x : list){
				if(i % x == 0){
					flg = false;
					break;
				}
			}
			if(flg){
				list.add(i);
			}
		}
		int size = list.size() + 100;
		for(int i = 100001; list.size() <= size; i++){
			boolean flg = true;
			for(int x : list){
				if(i % x == 0){
					flg = false;
					break;
				}
			}
			if(flg){
				list.add(i);
			}			
		}
		return list;
	}
}

Measured memory_bytes: 66988
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int n;
  scanf("%d",  &n);
  int* A = malloc(n*sizeof(int));
  A[0] = 0;
  for(int i=1;i<n;i++)
  {
    int x;
    scanf("%d", &x);
    A[i] = 0;
    A[x-1]++;
   }
  for(int i=0;i<n;i++)
  {
    printf("%d\n",A[i]);
  }
}

Measured memory_bytes: 2500
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(a):
        m = len(a)
        r = []
        if a[0][0] == a[1][0]:
            if a[0][1] < a[1][1]:
                r = [(a[i][0]-a[i+1][0], a[i][1]-a[i+1][1]) for i in range(m-1)]
            else:
                r = [(a[i+1][0]-a[i][0], a[i+1][1]-a[i][1]) for i in range(m-1)]
        else:
            if a[0][0] < a[1][0]:
                r = [(a[i+1][1]-a[i][1], a[i][0]-a[i+1][0]) for i in range(m-1)]
            else:
                r = [(a[i][1]-a[i+1][1], a[i+1][0]-a[i][0]) for i in range(m-1)]
        return tuple(r)

    while True:
        n = I()
        if n == 0:
            break

        a = []
        for _ in range(n+1):
            m = I()
            a.append([LI() for _ in range(m)])

        t = f(a[0])
        r = []
        for i in range(1,n+1):
            if t == f(a[i]) or t == f(a[i][::-1]):
                rr.append(i)

        rr.append('+++++')



    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9108
//DEEPANSHU SAXENA(saxenad765)
#include<bits/stdc++.h>
#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
using namespace std;
int main()
{
	int x,y;
	cin>>x>>y;
	cout<<x+(y/2);
}

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

int main(){
	int n;
	cin >> n;
	map<string,int> mp;
	for(int i = 0;i<n;i++){
		string a;
		cin >> a;
		mp[a]++;
	}
	cout << "AC x "<<mp["AC"]<<endl; 
	cout << "WA x "<<mp["WA"]<<endl; 
	cout << "TLE x "<<mp["TLE"]<<endl; 
	cout << "RE x "<<mp["RE"]<<endl; 
}


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

namespace AtCoder.Beginner164
{
    public class ABC164C
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            var keihin = new HashSet<string>();

            for (int i = 1; i <= N; i++)
            {
                var kei = Console.ReadLine();
                keihin.Add(kei);
            }

            Console.WriteLine(keihin.Count);
        }
    }
}

Measured memory_bytes: 47044
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define n_p(v) next_permutation(v.begin(),v.end())
#define to_ll(b) stoll(b)
#define MOD 1000000007
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp

signed main(){
	int n; cin>>n;
	int ans=0;
	int max_cnt=0;
	rep(i,1,n+1){
		int a=i;
		int cnt=0;
		while(a%2==0){
			cnt++;
			a/=2;
		}
		if(max_cnt<cnt){
			ans=i;
			max_cnt=cnt;
		}
	}
	if(ans==0) ans++;
	cout<<ans;
	return 0;
}

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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

int n;
vector<string> s;
void solve() {
    int l = 0, r = 0;
    int ans = 0;
    int next = 1;
    rep(i, n) {
        if (s[i] == "lu") l = 1;
        if (s[i] == "ld") l = 0;
        if (s[i] == "ru") r = 1;
        if (s[i] == "rd") r = 0;
        if (next == l && l == r) {
            next ^= 1;
            ans++;
        }
    }
    cout << ans << endl;
}
int main() {
    while (cin >> n, n) {
        s.resize(n);
        rep(i, n) cin >> s[i];
        solve();
    }

    return 0;
}

Measured memory_bytes: 3168
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=100000;
int n;
int a[N+5];
struct node
{
	int cnt,id;
}val1[N+5],val2[N+5];

inline bool _cmp(node a,node b)
{
	return a.cnt>b.cnt;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(i&1)
		{
			val1[a[i]].cnt++;
			val1[a[i]].id=a[i];
		}
		else
		{
			val2[a[i]].cnt++;
			val2[a[i]].id=a[i];
		}
	}
	
	sort(val1+1,val1+N+1,_cmp);
	sort(val2+1,val2+N+1,_cmp);
	if(val1[1].id == val2[1].id)
		printf("%d\n",n-max(val1[1].cnt+val2[2].cnt,val1[2].cnt+val2[1].cnt));
	else
		printf("%d\n",n-val1[1].cnt-val2[1].cnt);
	return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int a[MAXN],n,k;
long long s[MAXN],opt[MAXN];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",a+i),s[i]=s[i-1]+a[i],opt[i]=opt[i-1]+max(a[i],0);
    long long ans=0;
    for(int i=1;i+k-1<=n;++i){
        long long o=max(s[i+k-1]-s[i-1],0ll)+opt[i-1]+opt[n]-opt[i+k-1];
        ans=max(ans,o);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2176
object Main extends App {
    var get = scala.io.StdIn.readLine()
    var set = get.split(" ")
    val a = set(0).toInt
    val b = set(1).toInt
    if (0 == b % a) {
        println(a + b)
    } else {
        println(b - a)
    }
}

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

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

  ll s = a / x + 1;
  ll t = b / x + 1;
  if(a % x == 0) {
  cout << t - s + 1 << endl; 
  }
  else 
  cout << t - s;


  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int x;
	cin >> x;
	int l = x / 1.08 - 5, r = x / 1.08 + 5;
	for (; l <= r; ++l)
		if (floor(l * 1.08) == x)
		{
			cout << l;
			return 0;
		}
	cout << ":(";
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int A,a=0,b=0,c=0;
	for (int i = 0; i < 10; i++){
		cin >> A;
		if (a < A){
			c = b;
			b = a;
			a = A;
		}
		else if (b < A){
			c = b;
			b = A;
		}
		else if (c < A){
			c = A;
		}
	}
	cout << a << endl << b << endl << c << endl;
	return 0;
}

Measured memory_bytes: 3068
package main

import (
	"bufio"
	"fmt"
	"math"
	"math/rand"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

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

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int
var t float64

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	d := intScanner()
	c := intSliceScanner(26)
	s := make([][]int, d)
	for i := 0; i < d; i++ {
		s[i] = intSliceScanner(26)
	}
	best := -mod
	bestSchedule := make([]int, d)
	changeNum := 10
	for x := 0; x < 1; x++ {
		schedule := make([]int, d)
		for i := 0; i < d; i++ {
			schedule[i] = rand.Intn(26)
		}
		score := calcScore(schedule, c, s, d)
		t = float64(score) * 10.
		for y := 0; y < 140000; y++ {
			changes := make([]int, changeNum)
			pres := make([]int, changeNum)
			for i := 0; i < changeNum; i++ {
				changes[i] = rand.Intn(d)
				pres[i] = schedule[changes[i]]
				schedule[changes[i]] = rand.Intn(26)
			}
			nextScore := calcScore(schedule, c, s, d)
			if prob(score, nextScore) >= math.Abs(rand.Float64()) {
				score = nextScore
			} else {
				for i := 0; i < changeNum; i++ {
					schedule[changes[i]] = pres[i]
				}
			}
			if nextScore >= best {
				best = nextScore
				copy(bestSchedule, schedule)
			}
			t *= 0.999
		}
	}
	for i := 0; i < d; i++ {
		fmt.Println(bestSchedule[i] + 1)
	}
}
func calcScore(schedule []int, c []int, s [][]int, d int) int {
	score := 0
	last := make([]int, 26)
	for i, v := range schedule {
		score += s[i][v]
		for j, _ := range last {
			last[j]++
		}
		last[v] = 0
		for j, v := range last {
			score -= c[j] * v
		}
	}
	return score
}
func prob(before int, after int) float64 {
	if before <= after {
		return 1.0
	}
	return math.Exp((float64(after) - float64(before)) / float64(t))
}


Measured memory_bytes: 6348
//in the name of allah
#include<bits/stdc++.h>
const int N = 1e5+10;
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pii;
int n, m, x, y, z, ans[N];
vector< pii > all;
vector< int > p;
int c;
ll t;
int main(){
        scanf("%d %d %lld", &n, &m, &t);
        ll shift = 0;
        for(int i = 0; i < n; i++) {    
                scanf("%d %d", &x, &c); x--;
                int sign = c == 2 ? -1 : 1, need = sign == 1 ? m - x : x + 1;
                ll pos = x + sign * t;
                p.push_back((pos % m + m) % m);
                all.push_back(pii(x, i));
                shift += sign * t / m;
                if(t % m >= need) shift += sign;
        }

        shift = (shift % n + n) % n; 
        sort(all.begin(), all.end());
        sort(p.begin(), p.end());

        for(int i = 0; i < n; i++) ans[all[i].second] = p[(i + shift) % n];

        for(int i = 0; i < n; i++){
                printf("%d\n", (1 + ans[i])%m); 
        }

        return 0;
}

Measured memory_bytes: 4080
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s,t;
  cin >> s >> t;
  int n = s.size(), m = t.size();
  rep(i,n-m+1){
    int ii = n-m-i;
    bool ok = true;
    rep(j,m){
      ok &= s[ii+j]=='?' || s[ii+j]==t[j];
    }
    if(ok){
      rep(j,m) s[ii+j] = t[j];
      rep(j,n) if(s[j]=='?') s[j] = 'a';
      cout << s << endl;
      return 0;
    }
  }
  cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 256
import math

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(math.ceil(n**0.5))):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    
    if temp != 1:
        arr.append([temp, 1])
    
    if arr == []:
        arr.append([n, 1])

    return arr

n = int(input())
if n == 1:
    print(0)
    exit(0)

fact_1i = factorization(n)

res = 0
for _, num in fact_1i:
    temp_num = 1
    while temp_num <= num:
        res += 1
        num -= temp_num
        temp_num += 1

print(res)

Measured memory_bytes: 63600
#include <stdio.h>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef long double ld;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
//typedef long long int;
const int mod = 998244353;

bool line(pii a, pii b, pii c) {
  a.first -= c.first;
  b.first -= c.first;
  a.second -= c.second;
  b.second -= c.second;
  return a.first*b.second == a.second*b.first;
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  int n;
  cin >> n;
  vl p2(n+1, 1);
  for (int i = 1; i < p2.size(); ++i) p2[i] = p2[i-1] * 2 % mod;
  vii v(n);
  for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
  ll res = p2[n] - 1 - n;
//  cerr << res << endl;
  vvi was(n, vi(n));
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (!was[i][j]) {
    vi u(2);
    u[0] = i; u[1] = j;
    for (int t = 0; t < n; ++t) if (t != i && t != j && line(v[i], v[j], v[t])) {
      u.push_back(t);
    }
    res -= p2[u.size()] - 1 - (int)u.size();
    for (int a : u) for (int b : u) was[a][b] = was[b][a] = 1;
  }
  cout << (res % mod + mod) % mod << endl;
  return 0;
}

Measured memory_bytes: 384
import java.io.*;
import java.util.Map;
import java.util.HashMap;
public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
    int i,j,n=0;
    BufferedReader sca=new BufferedReader(new InputStreamReader(System.in));;
    String yomi,sp[]=new String[2];//0:order 1:name
    try{
    n=Integer.parseInt(sca.readLine());
    }catch(Exception e){
	System.out.println(e);
    }
    HashMap<String,String> dicmap=new HashMap<String,String>(n);
    for(i=0;i<n;i++){
	try{
	sp=(sca.readLine()).split("[\\s]+");
	}catch(Exception e){
	    System.out.println(e);
	}
    	if(sp[0].equals("insert")){
	    dicmap.put(sp[1],sp[1]);
    	}
    	if(sp[0].equals("find")){
    		if(dicmap.containsKey(sp[1])){
    			System.out.println("yes");
    		}else{
    			System.out.println("no");
    		}
    	}
    }
	}

}



Measured memory_bytes: 370216