akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner; 
public class Main { 
public static void main(String args[]) { 
    int n[]=new int[6];
Scanner sc = new Scanner(System.in); 
    for(int i=0;i<6;i++){
        n[i]=sc.nextInt();
    }
    String s = sc.next();
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='N'){
            n=north(n);
        }else if(s.charAt(i)=='S'){
            n=south(n);
        }else if(s.charAt(i)=='E'){
            n=east(n);
        }else if(s.charAt(i)=='W'){
            n=west(n);
        }
    }
    System.out.println(n[0]);

 }
 public static int[] north(int[] n){
     int temp = n[0];
     n[0]=n[1];
     n[1]=n[5];
     n[5]=n[4];
     n[4]=temp;
     return n;
 }
  public static int[] south(int[] n){
     int temp = n[0];
     n[0]=n[4];
     n[4]=n[5];
     n[5]=n[1];
     n[1]=temp;
     return n;
 }
    public static int[] west(int[] n){
     int temp = n[0];
     n[0]=n[2];
     n[2]=n[5];
     n[5]=n[3];
     n[3]=temp;
     return n;
 }
   public static int[] east(int[] n){
     int temp = n[0];
     n[0]=n[3];
     n[3]=n[5];
     n[5]=n[2];
     n[2]=temp;
     return n;
 }
}


Measured memory_bytes: 26140
N=int(input())
S=[list(map(str,input().split())) for _ in range(N)]
for row in S:
    row[1]=int(row[1])
SS=sorted(S)
ins=0
ans=list()
tmp=0
for i in SS:
    if i[0]==tmp:
        ans.insert(ins,i)
    else:
        ins=len(ans)
        ans.append(i)
        tmp=i[0]
for j in ans:
    print(S.index(j)+1)

Measured memory_bytes: 9216
def main():
    S = input()
    N = len(S)
    dic = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
           'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    for d in dic:
        if d in S:
            continue
        else:
            return print(S + d)
    if S == "zyxwvutsrqponmlkjihgfedcba":
        return print(-1)
    pre = S[-1]
    used = [S[-1]]
    from heapq import heapify, heappop, heappush
    heapify(used)
    for i in range(N-1)[::-1]:
        if S[i] < pre:
            c = heappop(used)
            while S[i] > c:
                c = heappop(used)
            print(S[:i] + c)
            break
        else:
            pre = S[i]
            heappush(used, pre)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

const pid_t pid = getpid();
// Problem Specific Parameter:

ll a[510][510];

vector<int> primes;

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

int main(void){
	int n = 500;

	rep(i,n)rep(j,n) a[i][j] = 1LL;

	for(int i = 2; primes.size() < 3010 ;++i){
		bool isprime = true;
		for(int j = 2; j*j <=i; ++j){
			if(i % j == 0){
				isprime = false;
			}
		}
		if(isprime) primes.push_back(i);
	}

	int idx = 0;
	rep(val,2*n+1){
		if(val % 2 == 1) continue;
		rep(i,n){
			const int j = val - i;
			if((i + j) % 2 == 1) continue;
			if(j < 0 or n <= j) continue;
			a[i][j] *= primes[idx];
		}
		idx++;
	}

	rep(val,-n,n+1){
		if(val % 2 == 1) continue;
		rep(i,n){
			const int j = val + i;
			if((i + j) % 2 == 1) continue;
			if(j < 0 or n <= j) continue;
			a[i][j] *= primes[idx];
		}
		idx++;
	}

	rep(i,n)rep(j,n){
		if((i + j) % 2 == 0) continue;
		ll val = 1LL;
		if(i-1>=0) val = lcm(val,a[i-1][j]);
		if(j-1>=0) val = lcm(val,a[i][j-1]);
		if(j+1< n) val = lcm(val,a[i][j+1]);
		if(i+1< n) val = lcm(val,a[i+1][j]);
		a[i][j] = val + 1LL;
	}

	cin >> n;
	rep(i,n){
		rep(j,n) cout << (j?" ":"") << a[i][j];
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 5248
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int p=2005;
int n,m,q,a[p],w[p],ans;
int hs(int i,int mid)
{
	int s=0,len=0,sum=0;
	for(int j=1;j<=n;++j)
	if(a[j]<w[i])
	sum+=min(s,max(0,len-m+1)),s=0,len=0;
	else if(a[j]>w[mid])++len;
	else ++len,++s;
	return sum+min(s,max(0,len-m+1));
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i)
	scanf("%d",&a[i]),w[i]=a[i];
	sort(w+1,w+n+1);
	ans=w[n]-w[1];
//for(int i=1;i<=n;++i)printf("%d ",w[i]);printf("\n");
	for(int i=1;i+q-1<=n;++i)
{
//printf("i %d\n",i);
	if(hs(i,n)<q)break;
	int l=i+q-1,r=n;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(hs(i,mid)<q)l=mid+1;
		else r=mid;
	}
//printf("l %d\n",l);
	ans=min(ans,w[l]-w[i]);
}
	printf("%d",ans);
	return 0;
}
/*
>=w[i],<=w[mid]
*/

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

int main() {
	string S;
	cin >> S;
	int N = S.size();
	if (S[0] == '0' || S[N - 1] == '1') {
		cout << -1 << endl;
		return 0;
	}
	S = S.substr(0, N - 1);
	string T = S;
	reverse(T.begin(), T.end());
	if (S != T) {
		cout << -1 << endl;
		return 0;
	}
	vector<int> V;
	for (int i = 0; i * 2 + 1 < N; i++) {
		if (S[i] == '1') V.push_back(i);
	}
	V.push_back(V[V.size() - 1] + 1);
	for (int i = V[V.size() - 1] + 1; i < N; i++) {
		cout << V[V.size() - 1] + 1 << " " << i + 1 << endl;
	}
	int NOW = 0;
	for (int i = V[V.size() - 1] - 1; i >= 0; i--) {
		if (S[i] == '1') NOW = i;
		else cout << i + 1 << " " << NOW + 1 << endl;
	}
	for (int i = 0; i < V.size() - 1; i++) {
		cout << V[i] + 1 << " " << V[i + 1] + 1 << endl;
	}
}

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

struct rect
{
  int W, H;
};

int main()
{
  auto list = std::vector<rect>{};
  int w, h;
  std::string s;
  while (std::cin >> h >> w)
  {
    auto r = rect{w, h};
    list.push_back(r);
  }

  for (auto r : list)
  {
    if (r.W == 0 && r.H == 0)
      break;

    auto line = std::string{};
    for (auto wi = 0; wi < r.W; wi++)
    {
      line += "#";
    }

    for (auto hi = 0; hi < r.H; hi++)
    {
      std::cout << line << std::endl;
    }

    if (&r != &list[list.size() - 1])
    {
      std::cout << std::endl;
    }
  }

  return 0;
}



Measured memory_bytes: 3208
using System;
using System.Collections.Generic;

using System.Text;


namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            int n =1;
            while(true)
            {
                string s =Console.ReadLine();
                if(s == "0")
                {
                    break; }

                 Console.WriteLine("Case "+n+": "+s);
                 n++;
            }


            

         
           

       

           //  for (int i = 0; i < 1000; i++)
           //{
           //     Console.WriteLine("Hello World"); }

            

        }

          
    }
}    

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long n, ans=0;
    cin >> n;
    vector<long long> a(n), b(n), c(n);
    for (long i=0; i<n; i++) cin >> a[i];
    for (long i=0; i<n; i++) cin >> b[i];
    for (long i=0; i<n; i++) cin >> c[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    for (long i=0; i<n; i++)
        ans += distance(a.begin(), lower_bound(a.begin(), a.end(), b[i])) *
            distance(upper_bound(c.begin(), c.end(), b[i]), c.end());
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

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;
}

int main() {
	int N;

	cin >> N;

	int temp1, temp2, temp3;
	int sum = 0;

	vector<vector<int>> dish(3, vector<int>());


	for(int i = 0; i < 3; i++){
		for(int j = 0 ; j < N; j++){
			if(i == 2 && j == N-1){
				continue;
			}

			cin >> temp1;
			dish[i].push_back(temp1);
		}
	}



	int now_dish = 0;

	for (int i = 0; i < N; i++) {
		now_dish = dish[0][i];
		sum += dish[1][now_dish - 1];

		if ((i != N - 1) && (dish[0][i + 1] == now_dish + 1)) {
			sum += dish[2][now_dish - 1];
		}

	}

	cout << sum << endl;

}


Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip()
 
n, m = map(int, input().split())
s = input()
ans = []
s = s[::-1]
now = 0
while True:
    for i in range(m, -1, -1):
        if i == 0:
            print(-1)
            sys.exit()
        if now + i <= n and s[now + i] == "0":
            now += i
            ans.append(i)
            if now == n:
                print(*ans[::-1])
                sys.exit()
            else:
                break
    
        


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

using namespace std;

vector<vector<long long>> paint(vector<pair<int, int>>& restriction, vector<vector<int>>& tree){
  vector<vector<long long>> ret(tree.size(), vector<long long>(tree.size(), 0));
  
  for(auto [u, v] : restriction){
    queue<int> q;
    vector<int> parent(tree.size(), -1);
    vector<bool> used(tree.size(), false);
    q.push(u);
    
    while(!used[v]){
      int node = q.front();
      q.pop();
      if(used[node]) continue;
      used[node] = true;
      
      for(int next = 0; next < (int)tree.size(); ++next){
        if(tree[node][next] == -1 || used[next]) continue;
        
        parent[next] = node;
        q.push(next);
      }
    }
    
    for(int node = v; parent[node] != -1; node = parent[node]){
      ret[u][v] |= 1ll << tree[node][parent[node]];
      ret[v][u] |= 1ll << tree[node][parent[node]];
    }
  }
  
  return ret;
}

int main(){
  int N; cin >> N;
  
  vector<vector<int>> tree(N, vector<int>(N, -1));
  for(int i = 0; i < N - 1; ++i){
    int a, b; cin >> a >> b; --a; --b;
    tree[a][b] = i; tree[b][a] = i;
  }
  
  int M; cin >> M;
  vector<pair<int, int>> restriction(M);
  for(int i = 0; i < M; ++i){
    int u, v; cin >> u >> v;
    restriction[i] = {--u, --v};
  }
  
  vector<vector<long long>> constraint = paint(restriction, tree);
  
  long long num = 0;
  for(int b = 0; b < (1 << M); ++b){
    long long p = (__builtin_popcountll(b) & 1) ? 1 : -1;
    long long edges = 0;
    for(int i = 0; i < M; ++i){
      if((b >> i) & 1){
        edges |= constraint[restriction[i].first][restriction[i].second];
      }
    }
    p *= 1ll << (N - 1 - __builtin_popcountll(edges));
    num -= p;
  }
  
  cout << num << endl;
  
  return 0;
}

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

using namespace std;

int main()
{
    int n,m,res=0,x;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>x;
        res+=x;
    }
    if(res>n)cout<<-1<<endl;
    else cout<<n-res<<endl;
    return 0;
}


Measured memory_bytes: 3636
import java.io.*;
import java.util.*;
import java.math.*;
class Main{
    public static void main(String[] args){
    BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
    try {
	while(true){
	int n = Integer.valueOf(sc.readLine());
	if(n==0) break;
	int[] sum = new int[7];
	for(int i=0; i<n; i++){
	int j = Integer.valueOf(sc.readLine());
	if(j<10)
	sum[0]++;
	else if(j<20)	
	sum[1]++;
	else if(j<30)	
	sum[2]++;
	else if(j<40)	
	sum[3]++;
	else if(j<50)	
	sum[4]++;
	else if(j<60)	
	sum[5]++;
	else	
	sum[6]++;
	}
	for(int i=0; i<7; i++)	
	System.out.println(sum[i]);
	}
    }catch(Exception e){
        System.out.println("Error");
    }
    }
}

Measured memory_bytes: 55928
def examE():
    H, W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    dp = [0]*(H*W)
    cur = abs(A[0][0] - B[0][0])
    dp[0] |= (1 << cur)
    for i in range(H):
        for j in range(W):
            now = dp[i*W + j]
            if i < H - 1:
                cur = abs(A[i + 1][j] - B[i + 1][j])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[(i+1)*W +j] |= (ni | ex)
            if j < W - 1:
                cur = abs(A[i][j + 1] - B[i][j + 1])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[i*W +j+1] |= (ni | ex)
    #print(dp[-1])
    ans = inf
    for i,f in enumerate(str(bin(dp[-1]))[::-1]):
        if f=="1":
            ans = i
            break
    print(ans)
    return

def examF():
    N, X, D = LI()

    if D==0:
        ans = N + 1
        if X==0:
            ans = 1
        print(ans)
        return

    if D<0:
        X, D = -X, -D

    S = defaultdict(list)
    for i in range(N+1):
        base = (X*i) % D
        start = (X*i) // D + i*(i-1)//2
        end = (X*i) // D + i*(N-1 + N -i)//2
        S[base].append([start,end])
    #print(S)

    ans = 0
    for d in S.values():
        d.sort()
        L, R = d[0]
        if len(d)==1:
            ans += R - L + 1
            continue

        for l,r in d[1:]:
            if r<=R:
                continue
            if R<l:
                ans += R - L + 1
                L, R = l, r
            elif R<r:
                R = r
        ans += R - L + 1
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()


Measured memory_bytes: 129296
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<30)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n, d[510];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> n;
    vector<int> c(n-1), s(n-1), f(n-1);
    rep(i, 0, n-1) cin >> c[i] >> s[i] >> f[i];
    rep(i, 0, n) {
        int t = 0;
        rep(j, i, n-1) {
            if (t < s[j]) t = s[j];
            else if (t % f[j] == 0);
            else t += f[j] - t%f[j];
            t += c[j];
        }
        cout << t << endl;
    }
    return 0;
}


Measured memory_bytes: 256
n, c, k = map(int, input().split())
s = [int(input()) for _ in range(n)]
s = sorted(s)
num = 0
i = s[0]
m = s[0] + k
p = 1
for j in s[1:]:
    if j <= m and p < c:
        p += 1
    else:
        p = 1
        num += 1
        m = j + k
    i = j
num += 1
print(num)


Measured memory_bytes: 8276
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	int N;
	cin >> N;
	vector<int> t(N), v(N), t_s(N+1,0);
	for (int i = 0; i < N; i++) {
		cin >> t[i];
		t_s[i + 1] = t_s[i] + t[i];
	}
	for (int i = 0; i < N; i++)cin >> v[i];

	vector<double> A;
	for (double a = 0; a <= t_s[N]; a += 0.5) {
		vector<double> v_f;
		v_f.push_back(a);
		v_f.push_back(t_s[N] - a);
		for (int i = 0; i < N; i++) {
			if (a <= t_s[i])v_f.push_back(v[i] + (t_s[i] - a));
			else if (t_s[i] < a && a <= t_s[i + 1])v_f.push_back(v[i]);
			else if (t_s[i + 1] < a)v_f.push_back(v[i] + (a - t_s[i + 1]));
		}
		A.push_back(*min_element(v_f.begin(), v_f.end()));
	}

	double ans = 0;
	for (int i = 0; i < A.size() - 1; i++) {
		ans += 0.25*(A[i] + A[i + 1]);
	}
	cout << setprecision(8) << ans << endl;
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    map<vi, int> dic;
    const int M = 'z' - 'a' + 1;
    rep(_, n){
        string in; cin >> in;
        vi hist(M);
        for(auto& e : in){
            hist[e - 'a']++;
        }
        dic[hist]++;
    }

    ll res = 0LL;
    for(auto& e : dic){
        ll cnt = e.second;
        if(cnt > 0){
            res += cnt * (cnt - 1) / 2;
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 19072
/**
 *    Author:  "Robin Singh" !!!
**/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define mp make_pair
#define str string 
#define szz(v) ((int)(v).size())  
#define fr(i, j, k) for(int i = j; i < k; i++)     // 0 -> n-1 (i,0,n)
#define bk(i, j, k) for(int i = j-1; i >= k; i--)  // n-1 -> 0 (i,n,0)
#define frit(it, a) for(__typeof((a).begin()) it = a.begin(); it != a.end(); ++it)
#define mem(ptr)  memset(ptr, 0, sizeof ptr)  // use fill() for value other than 0
#define rtn return 
#define nl "\n"      // avoid endl
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int,int> > vpii;
typedef vector< pair<ll, ll> > vpll;
const long long mod = 1e9+7;
const ld eps = 1e-9;
const ll INF = (1LL<<61);
const int inf = (1<<30);
//-------------------------------------------------------------------------------------------------------------
#define dbg( args...) { vector<string> _v = split( #args, ','); err( _v.begin(), args); cerr << '\n'; }
vector<string> split( const string& s, char c) { vector<string> v; stringstream ss( s); string x; 
while ( getline( ss, x, c)) v.emplace_back(x); return move(v); }
void err( vector<string>::iterator it) { } 
template<typename T, typename... Args>
void err( vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr( ( *it)[0] == ' ', it -> length()) << " = " << a << '\t'; err( ++it, args...); }
//-------------------------------------------------------------------------------------------------------------

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string s;
    ll k, i;
    cin >> s >> k;
    k--;
    for(i=0; i<s.size(); i++){
        if(i == k || s[i] != '1') break;
    }
    cout << s[i];
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

ll n, m;
vector<double> dp;
vector<ll> s, t, deg;
vector<vector<ll>> to;
vector<bool> seen;

double dfs(ll cv) {
  if (seen[cv]) return dp[cv];
  double res = 0;
  REP(nv, n) {
    if (!to[cv][nv]) continue;
    res += (dfs(nv) + 1) / deg[cv];
  }
  seen[cv] = true;
  return dp[cv] = res;
}

int main() {
  cin >> n >> m;
  s = vector<ll>(m);
  t = vector<ll>(m);
  deg = vector<ll>(n, 0);
  to = vector<vector<ll>>(n, vector<ll>(n, 0));
  REP(i, m) {
    cin >> s[i] >> t[i];
    s[i]--;
    t[i]--;
    to[s[i]][t[i]] = 1;
    deg[s[i]]++;
  }
  dp = vector<double>(n, 0.0);
  seen = vector<bool>(n, false);
  double ans = dfs(0);
  vector<ll> argmax(n);
  REP(i, n) {
    double maxi = -1;
    REP(j, n) {
      if (to[i][j] && dp[j] > maxi) {
        maxi = dp[j];
        argmax[i] = j;
      }
    }
  }
  REP(i, n - 1) {
    if (deg[i] == 1) continue;
    to[i][argmax[i]] = 0;
    deg[i]--;
    dp = vector<double>(n, 0.0);
    seen = vector<bool>(n, false);
    ans = min(ans, dfs(0));
    to[i][argmax[i]] = 1;
    deg[i]++;
  }

  cout << fixed << setprecision(10);
  cout << ans << endl;
}

Measured memory_bytes: 5888
import java.util.*;public class Main{static long mod=(long)1e9+7;public static void main(String[] args){Scanner in=new Scanner(System.in);int n=in.nextInt();int[] freq=new int[26];char[] s=in.next().toCharArray();for(char c:s)freq[c-'a']++;long ans=1L;for(int i:freq){ans*=(i+1);ans%=mod;}ans--;ans=(ans+mod)%mod;System.out.println(ans);}}

Measured memory_bytes: 27092
#include<cstdio>
#include<cstring>
#include<map>

using namespace std;
typedef pair<int,int> P;
int h,w,s,all;
int fie[35][35];
int sum[35][35];
int dp[35][35][35][35];
int min_dem[35][35][35][35];
int flag=0;

P check(int lx,int rx,int ly,int ry){
	if(dp[lx][rx][ly][ry]!=0){
		return P(dp[lx][rx][ly][ry],min_dem[lx][rx][ly][ry]);
	}
	if(all-(sum[rx][ry]-sum[rx][ly]-sum[lx][ry]+sum[lx][ly])>s)return P(-1,-1);
	dp[lx][rx][ly][ry]=1;
	min_dem[lx][rx][ly][ry]=sum[rx][ry]-sum[rx][ly]-sum[lx][ry]+sum[lx][ly];
	for(int i=lx+1;i<rx;i++){
		P c=check(lx,i,ly,ry),d=check(i,rx,ly,ry);
		if(c.first==-1 || d.first==-1)continue;
		if(c.first+d.first==dp[lx][rx][ly][ry] && min(c.second,d.second)>min_dem[lx][rx][ly][ry]){
			dp[lx][rx][ly][ry]=c.first+d.first;
			min_dem[lx][rx][ly][ry]=min(c.second,d.second);
		}
		if(c.first+d.first>dp[lx][rx][ly][ry]){
			dp[lx][rx][ly][ry]=c.first+d.first;
			min_dem[lx][rx][ly][ry]=min(c.second,d.second);
		}
	}
	for(int i=ly+1;i<ry;i++){
		P c=check(lx,rx,ly,i),d=check(lx,rx,i,ry);
		if(c.first==-1 || d.first==-1)continue;
		if(c.first+d.first==dp[lx][rx][ly][ry] && min(c.second,d.second)>min_dem[lx][rx][ly][ry]){
			dp[lx][rx][ly][ry]=c.first+d.first;
			min_dem[lx][rx][ly][ry]=min(c.second,d.second);
		}
		if(c.first+d.first>dp[lx][rx][ly][ry]){
			dp[lx][rx][ly][ry]=c.first+d.first;
			min_dem[lx][rx][ly][ry]=min(c.second,d.second);
		}
	}
	return P(dp[lx][rx][ly][ry],min_dem[lx][rx][ly][ry]);
}

int main(void){
	while(1){
		scanf("%d %d %d",&h,&w,&s);
		if(h+w+s==0)break;
		memset(dp,0,sizeof(dp));
		memset(min_dem,0,sizeof(min_dem));
		all=0;
		for(int i=1;i<=h;i++){
			for(int j=1;j<=w;j++){
				scanf("%d",&fie[j][i]);
				all+=fie[j][i];
			}
		}
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=h;i++){
			for(int j=1;j<=w;j++){
				sum[j][i]=sum[j-1][i]+fie[j][i];
			}
		}
		for(int i=1;i<=w;i++){
			for(int j=1;j<=h;j++){
				sum[i][j]+=sum[i][j-1];
			}
		}
		P res=check(0,w,0,h);
		printf("%d %d\n",res.first,s-all+res.second);
	}
	return 0;
}

Measured memory_bytes: 12772
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
	)

type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextInt64() int64 {
	i, err := strconv.ParseInt(io.Next(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}


func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func intMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func (io *Io) PrintBool(b bool, trueS, falseS string) {
	if b {
		io.PrintLn(trueS)
	} else {
		io.PrintLn(falseS)
	}
}

func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func absi(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func b2i(b bool) int {
	if b {
		return 1
	}
	return 0
}

type Int64s []int64
func (f Int64s) Len() int {
	return len(f)
}
func (f Int64s) Less(i, j int) bool {
	return f[i] < f[j]
}

func (f Int64s) Swap(i, j int) {
	f[i], f[j] = f[j], f[i]
}


func solve(io *Io) {
	s := io.NextLine()
	t := io.NextLine()

	ok := false
	for i := range(s) {
		u := s[i:] + s[:i]
		if u == t {
			ok = true
		}
	}

	io.PrintBool(ok, "Yes", "No")
}

func main() {
	io := NewIo()
	defer io.Flush()

	solve(io)
}


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

using namespace std;


struct Node
{
	int self;
	int parent;
	set<int> children;
	int points;
	int total;
};

vector<Node> v;
vector<set<int> > edge2;
void FindChildren(const Node& n)
{
	for (auto& x : n.children)
	{
		Node theNode;
		theNode.self = x;
		theNode.parent = n.self;
		theNode.children = edge2[x];
		theNode.children.erase(n.self);
		theNode.points = 0;
		v[x] = theNode;
		if (theNode.children.empty())
			continue;
		FindChildren(theNode);
	}
}

void AddPoints(Node& n, int total)
{
	n.total = total + n.points;
	for (auto& x : n.children)
	{
		auto& node = v[x];
		if (node.children.empty())
		{
			node.total = n.total + node.points;
			continue;
		}
		AddPoints(node, n.total);
	}

}

void ABC138D()
{
	int N, Q;
	cin >> N >> Q;

	vector<pair<int, int> > edge(N - 1);
	for (auto& x : edge)
	{
		int a, b;
		cin >> a >> b;
		x.first = a;
		x.second = b;
	}

	vector<pair<int, int> > pts(Q);
	for (auto& y : pts)
	{
		int p, x;
		cin >> p >> x;
		y.first = p;
		y.second = x;
	}

	edge2.resize(N + 1);
	for (auto& x : edge)
	{
		edge2[x.first].insert(x.second);
		edge2[x.second].insert(x.first);
	}



	Node base;
	base.self = 1;
	base.children = edge2[1];
	base.points = 0;

	v.resize(N+1);
	v[1] = base;

	FindChildren(base);


	for (const auto& x : pts)
	{
		int p = x.first;
		v[p].points += x.second;
	}

	AddPoints(v[1], 0);

	for (int i = 1; i <= N; ++i)
	{
		cout << v[i].total;
		if (i < N)
			cout << ' ';
	}

}

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

Measured memory_bytes: 93056
#include<bits/stdc++.h>
using namespace std;
long long a[200005],ai[200005],b[200005],bi[200005],n,m,k;
int main()
{
    cin>>n>>m>>k;
    for(long long i=1;i<=n;++i)
    {
        cin>>a[i];
        ai[i]=ai[i-1]+a[i];
    }
    for(long long i=1;i<=m;++i)
    {
        cin>>b[i];
        bi[i]=bi[i-1]+b[i];
    }
    long long ans=0,j=m;
    for(long long i=0;i<=n;++i)
    {
        if(ai[i]>k)break;
        while(bi[j]>k-ai[i])j--;
        ans=max(ans,i+j);
    }
    cout<<ans;
}


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

typedef long long ll;

int main() {
    ll N; cin >> N;
    vector<ll> B(N);
    for(ll i=0; i<N; i++){
        ll x; cin >> x;
        B[i] = x - (i + 1);
    } 

    sort(B.begin(), B.end());
    
    ll b;
    ll res1 = 0;
    b = B[N/2];
    for(ll i; i<N; i++) res1 += abs(B[i] - b);

    ll res2 = 0;
    b = B[N/2 - 1];
    for(ll i; i<N; i++) res2 += abs(B[i] - b);

    ll res = min(res1, res2);

    cout << res << endl;
}


Measured memory_bytes: 1792
#include <map>
#include <list>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int ans;
long long x,y;
int main()
{
    cin>>x>>y;
    long long i=x;
    while(i<=y)
    {
    	ans++;
    	i*=2;
    }
    cout<<ans<<endl;
}

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

const int N = 1000010;
typedef long long ll;

ll A, B;
ll p[N], cnt, vis[N];

int main() {
	scanf("%lld%lld", &A, &B);
	ll ans = 1;
	for(int i = 2; i <= 1000000; ++i) {
		if(!vis[i]) {
			p[++cnt] = i;
		}
		for(int j = 1; j <= cnt && i * p[j] <= 1000000; ++j) {
			vis[i * p[j]] = 1;
			if(i % p[j] == 0) break;
		}
	}
	for(int i = 1; i <= cnt; ++i) {
		if(A % p[i] == 0 && B % p[i] == 0) {
			++ans;
			while(A % p[i] == 0) A /= p[i];
			while(B % p[i] == 0) B /= p[i];
		}
	}
	for(int i = 1; i <= cnt; ++i) {
		while(A % p[i] == 0) A /= p[i];
		while(B % p[i] == 0) B /= p[i];
	}
	if(A != 1 && B != 1 && A == B) ++ans;
	printf("%lld\n", ans);
}

Measured memory_bytes: 10624
#include<stdio.h>
int from[100000];

int main(){
	int a,b,c,i;
	scanf("%d%d",&a,&b);
	for(i=1;i<a;i++){
		scanf("%d",&c);
		from[i]=from[i-1]+c;
	}
	i=0;
	a=0;
	while(b--){
		scanf("%d",&c);
		if(c<0)a+=from[i]-from[i+c];
		else a+=from[i+c]-from[i];
		i+=c;
a%=100000;
	}
	printf("%d\n",a);
return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<string.h>
int main() {
  long long a;
  char T[200001];
  scanf("%s",T);
  a=strlen(T);
  for(int i=0;i<a;i++){
    if(T[i]=='?'){
      T[i]='D';
    }
  }
  printf("%s",T);
  return 0;
}

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

vector<vector<int> > vi;

void permute(int a[],int l,int r)
{
	if(l==r)
	{
		vector<int> temp;
		for(int i=0;i<5;i++)
			temp.push_back(a[i]);
		vi.push_back(temp);
	}
	else
	{
		for(int i=l;i<=r;i++)
		{
			swap(a[l],a[i]);
			permute(a,l+1,r);
			swap(a[l],a[i]);  
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	int a[5];
	for(int i=0;i<5;i++)
		cin>>a[i];
	
	permute(a,0,4);
	
	int ans=1e9;
	
	for(int i=0;i<vi.size();i++)
	{
		int time=0;
		for(int j=0;j<vi[i].size()-1;j++)
		{
			if(vi[i][j]%10!=0)
				time+=((vi[i][j]/10) + 1)*10;
			else
				time+=vi[i][j];
		}
		time+=vi[i][4];
		ans = min(ans,time);
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N, K, ans=0, cnt=0, cnt2=0;
  cin >> N >> K;
  char S[N];
  for(int i=0; i<N; i++) cin >> S[i];
  for(int i=0; i<N-1; i++){
    if(S[i] == 'R' && S[i+1] == 'L') cnt++;
  }
  if(S[0] == 'L') cnt2++;
  if(S[N-1] == 'R') cnt2++;
  if(cnt >= K){
    cnt -= K;
    K = 0;
  }else{
    cnt = 0;
    K -= cnt;
  }
  cnt2 -= K;
  if(cnt2 < 0) cnt2 = 1;
  cout << N-cnt*2-cnt2*1 << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
	string s;
	cin >> s;
	if (s[0] == '7' || s[1] == '7' || s[2] == '7') {
		puts("Yes");
	} else {
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
	cin>>n;
	for (int i=0;i<=n;i+=4)
	{
		if ((n-i)%7==0)
		{
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";
	return 0;
}



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

using namespace std;
typedef long long ll;
typedef pair<int,int>pa;
map<pa,int>mp;
const int N=2e5+100;
int n,m;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int a,b;
    cin>>a>>b;
    if(a>b){
        while(a--) cout<<b;
    }
    else {
        while(b--) cout<<a;
    }
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())

int get_ans(int a, int b, int x) {
    if (a > b)
        swap(a, b);
    if (x <= a) {
        return b - x;
    } else if (b <= x) {
        return abs(x - a);
    } else {
        return min(abs(x - a), abs (x - b)) + b - a;
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    int a[n + 2], b[m + 2];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = -1e12;
    a[n + 1] = 1e12;

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    b[0] = -1e12;
    b[m + 1] = 1e12;
    for (int tc = 1; tc <= q; tc++) {
        int x;
        cin >> x;
        int sx, sy, tx, ty;
        sx = upper_bound(a, a + n + 2, x) - a;
        sy = sx - 1;
        sx = a[sx], sy = a[sy];
        tx = upper_bound(b, b + m + 2, x) - b;
        ty = tx - 1;
        tx = b[tx], ty = b[ty];
        int ans = INT64_MAX;
        ans = min(ans, get_ans(tx, sy, x));
        ans = min(ans, get_ans(ty, sx, x));
        ans = min(ans, get_ans(tx, sx, x));
        ans = min(ans, get_ans(ty, sy, x));
        cout << ans << "\n";
    }
}

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

typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#define	GE() printf(">----------\n")
#define	IN() freopen("in.txt","r",stdin)
#define	OUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;

int main()
{
    int x, y;
    while(~scanf("%d%d", &x, &y)){
        if(x+y>=10)printf("error\n");
        else printf("%d\n", x+y);
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <set>
#include <list>
#include <deque>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <iterator>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define powr(x,n,p) for(int axy=0 ; axy<p ; axy++){x=x*n;}
#define YES printf("YES\n")
#define Yes printf("Yes\n")
#define yes printf("yes\n")
#define NO printf("NO\n")
#define No printf("No\n")
#define no printf("no\n")
#define nl printf("\n")
#define fr0(n,q) for(q=0 ; q<n ; q++)
#define fr1(n,q) for(q=1 ; q<=n ; q++)
#define mp make_pair
#define scl(x) scanf("%lld",&x)
#define sci(x) scanf("%d",&x)
#define lst(x) x[x.size()-1]
#define llst(x) x[x.size()-2]
#define md 1000000007
#define check(x,y) (x&(1<<y))
#define set(x,y) x=x|(1<<y)
using namespace std;
ll dp[105][100005];
ll arr[105],v[105];
ll n,w;
ll solve(ll i, ll j){
	if(j<0) return md;
	if(j==0) return 0;
	if(i>n) return md;
	if(dp[i][j]!=-1) return dp[i][j];
	ll ret=min(arr[i]+solve(i+1,j-v[i]),solve(i+1,j));
	return dp[i][j]=ret;
}
int main()
{
	cin>>n>>w;
	int i,j;
	fr0(105,i){
		fr0(100005,j) dp[i][j]=-1;
	}
	for(i=1 ; i<=n ; i++) cin>>arr[i]>>v[i];
	for(j=100000 ; j>=0 ; j--){
		if(solve(1,j)<=w){
			cout<<j;
			nl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 85644
from sys import stdin, exit
from collections import deque

N = int(stdin.readline().rstrip())
b = [int(x) for x in stdin.readline().rstrip().split()]
ans = deque([])

while N > 0:
    index = N - 1
    while index >= 0:
        if b[index] == index + 1:
            ans.appendleft(b[index])
            b1 = b[:index]
            b2 = b[index + 1:]
            b = b1 + b2
            N -= 1
            break
        index -= 1
        if index == -1:
            print(-1)
            exit()

print(*ans)


Measured memory_bytes: 38512
import java.util.Scanner;
class Main
{
	static void sort( int A[] )
	{
		putArray(A);
		int v, j;
		for( int i = 1 ; i < A.length ; i++ )
		{
			v = A[i];
			for( j = i-1 ; 0<=j && v<A[j] ; j-- )
				A[j+1] = A[j];
			A[j+1] = v;
			putArray(A);
		}
		return;
	}
	static void putArray( int A[] )
	{
		for( int i = 0 ; i < A.length ; i++ )
		{
			if( i==A.length-1 )
				System.out.print( A[i]+"\n" );
			else
				System.out.print( A[i]+" " );
		}
		return;
	}
	public static void main( String[] args )
	{
		Scanner sc = new java.util.Scanner( System.in );
		int n = sc.nextInt();
		int A[] = new int[n];
		for( int i = 0 ; i < n ; i++ )
			A[i] = sc.nextInt();
		sort( A );
		
		return;
	}
}

Measured memory_bytes: 31616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
const int INF = 1001001001;
const int MOD = 1000000007;

// auto MOD int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


// combination MOD prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} comb(1000005);

int modPow(long long a, long long n) {
  if (n == 0) return 1; // 0乗にも対応する場合
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  long long t = modPow(a, n / 2);
  return (t * t) % MOD;
}

int main() {
    int N;
    cin >> N;
    mint a = modPow(10,N);
    a = a - modPow(9,N) - modPow(9,N) + modPow(8,N);
    cout << a << endl;

}


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

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int N, X, L, D = 0, ans = 1;

	cin >> N >> X;
	rep(i, N) {
		cin >> L;
		D += L;
		if (D <= X) ans++;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define ll long long
string s;
ll ans;
ll dfs(ll sum,ll f,ll cnt)
{
	if(cnt==s.size())
	{
		ans+=sum+f;
		return 0;
	}
	dfs(sum,f*10+(s[cnt]-'0'),cnt+1);
	dfs(sum+f,0,cnt+1);
}
int main()
{
	cin >> s;
	
	dfs(0,0,0);
	cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n){
    cin >> a[i];
  }

  ll res = a[0]-1;
  ll mx = 1;
  rep1(i,n-1){
    res += (a[i]-1)/(mx+1);
    if(a[i]==mx+1){
      mx++;
    }
  }

  cout << res << "\n";
  
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

int main()
{
	char a[1001];
	int i, w;
	scanf("%s", a);
	scanf("%d", &w);
	for (i = 0; a[i] != '\0'; i++){
		if (i%w == 0){
			printf("%c", a[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        int p,n,r,c,i,j,k;
        int[] card = new int[51];
        int[] dummy = new int[51];
        Scanner s = new Scanner(System.in);
        while(true){
            n = s.nextInt();
            r = s.nextInt();
            if(n==0&&r==0)break;
            for(i=0;i<n;i++)card[i]=n-i;
            for(i=0;i<r;i++){
                p = s.nextInt();
                c = s.nextInt();
                for(j=0;j<p-1;j++)dummy[j]=card[j];
                for(j=0;j<c;j++)card[j]=card[j+p-1];
                for(j=0;j<p-1;j++)card[j+c]=dummy[j];
            }
            System.out.println(card[0]);
        }
    }
}




Measured memory_bytes: 36712
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

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


int main(void) {
	int h, w;

	cin >> h >> w;
	vector<string> c(h);
	FOR(i, 0, h - 1) {
		cin >> c[i];
	}

	FOR(i, 0, h - 1) {
		cout << c[i] << endl;
		cout << c[i] << endl;
	}


	return 0;
}

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

using namespace std;

#define N 1200
#define M 300000

int n,m,x[M],y[M],vis[2][N][N];
vector<int> vec[N];

void dfs(int op,int o,int u,int k){
	if (vis[op][o][u]) return;
	vis[op][o][u]=k;
	for (int i=0;i<(int)vec[u].size();++i)
		dfs(op,o,vec[u][i],k);
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i){scanf("%d%d",&x[i],&y[i]); vec[x[i]].push_back(y[i]);}
	for (int i=1;i<=n;++i){
		vis[0][i][i]=vis[1][i][i]=1;
		for (int j=0;j<(int)vec[i].size();++j)
			dfs(0,i,vec[i][j],j+1);
		if (vec[i].size())
			for (int j=(int)vec[i].size()-1;j>=0;--j)
				dfs(1,i,vec[i][j],j+1);
	}
	for (int i=1;i<=m;++i){
		int u=x[i],v=y[i];
		puts((vis[0][u][v]!=vis[1][u][v])^(vis[0][v][u]>0)?"diff":"same");
	}

	return 0;
}


Measured memory_bytes: 16144
#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(){
	int n;
	cin >> n;
	map<string,int> mp;
	for(int i=0;i<n;++i){
		string s;
		cin >> s;
		if(mp[s] == 0){
			mp[s] = 1;
		}else{
			mp[s]++;
		}
	}
	int max = 0;
	for(auto itr=mp.begin();itr!=mp.end();++itr){
		if(itr->second > max)max = itr->second;
	}
	for(auto itr=mp.begin();itr!=mp.end();++itr){
		if(itr->second == max)cout << itr->first << endl;
	}
}

Measured memory_bytes: 25216
n = int(input())
l = list(map(int, input().split()))

dl = {}
du = {}

for i in range(n):
  v = l[i]
  if i%2 == 0:
    if v in dl:
      dl[v] += 1
    else:
      dl[v] = 1
  else:
    if v in du:
      du[v] += 1
    else:
      du[v] = 1

if max(dl, key=dl.get) != max(du, key=du.get):
  ans = n - max(dl.values()) - max(du.values())
else:
  vsl = list(dl.values())
  vsl.sort(reverse=True)
  vsu = list(du.values())
  vsu.sort(reverse=True)
  if len(vsl) == 1 or len(vsu) == 1:
    ans = n//2
  else:
    ans = min(n-vsu[0]-vsl[1], n-vsl[0]-vsu[1])

print(ans)


Measured memory_bytes: 17056
#include <stdio.h>

char alph[] = "abcdefghijklmnopqrstuvwxyz";
int count[26] = {};

int read(void)
{
    char c;

    while(1) {
        if(scanf("%c", &c) == EOF) return 0;
        if(c == '\n') break;

        if(c >= 'a' && c <= 'z') count[c-'a']++;
        else if(c >= 'A' && c <= 'Z') count[c-'A']++;
    }

    return 1;
}

void show(void)
{
    int i;

    for(i=0;i<26;i++) {
        printf("%c : %d\n", alph[i], count[i]);
    }
    return;
}

int main(void)
{
    while(read() != 0);
    show();

    return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
if(N%10==3){
  cout << "bon" << endl;
}
else if(N%10==0||N%10==1|| N%10== 6|| N%10==8){
  cout << "pon" <<endl;
}
else{
  cout << "hon " << endl;
}
}

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

a,b = map(int, input().split())

def cum_xor(n):
    result = (n + 1) // 2 % 2
    if (n + 1) % 2 == 1: result ^= n
    return result

print(cum_xor(a - 1) ^ cum_xor(b))


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  string s;
  cin >> s;
  int n = s.length();
  int cnt = 0;
  bool f = s[0] == '0';
  
  for(int i=1; i<n; i++) {
    if (f){
      if (s[i] == '0'){
        cnt++;
      }
    }else{
      if (s[i] == '1'){
        cnt++;
      }
    }
    f = !f;
  }
  
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>

#define MAX 1000000
#define INFTY 2000000000

int count=0;

void merge(int[],int,int,int);
void mergesort(int[],int,int);

int main(){

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

  mergesort(arr,0,n);

  for(i=0;i<n-1;i++){
    printf("%d ",arr[i]);
  }
  printf("%d\n",arr[i]);
  printf("%d\n",count);

 
  return 0;
}


void mergesort(int A[],int left,int right){
  
  int mid;

  if(left+1<right){
    mid=(left+right)/2;
    mergesort(A,left,mid);
    mergesort(A,mid,right);
    merge(A,left,mid,right);
  }
}

void merge(int A[],int left,int mid,int right){
  
  int n1,n2,i,j,k;
  
  n1 = mid - left;
  n2 = right - mid;
  
  int arr2[n1+1],arr3[n2+1];

  for(i=0;i<=n1-1;i++){
    arr2[i] = A[left+i]; 
  }

  for(i=0;i<=n2-1;i++){
    arr3[i] = A[mid+i];
  }
  
  arr2[n1] = INFTY;
  arr3[n2] = INFTY;
   
  i=0;
  j=0;

  for(k=left;k<=right-1;k++){
    count++;
    if(arr2[i]<=arr3[j]){
      A[k] = arr2[i];
      i++;
    }
    else{
      A[k] = arr3[j];
      j++;
    }
  }
  
}

Measured memory_bytes: 4860