akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
#include <vector>
#include <unordered_map>

using namespace std;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

using P = pair<int, int>;
long long pairToInt(P p, P wholeSizePair) { //wholeSizePairについて：計算に使うのはpairの2個目の繰り上がり値（最大値+1)だけ
	if (p.first < wholeSizePair.first && p.second < wholeSizePair.second) {
		return (long long)p.first*wholeSizePair.second + p.second;
	}
	else {
		cerr << "error:範囲外参照(UnionFind::pairToInt)" << endl;
		exit(1);
	}
}
P intToPair(long long x, P wholeSizePair) {
	if (x < wholeSizePair.first * wholeSizePair.second) { //wholeSizePairについて：計算に使うのはpairの2個目の繰り上がり値（最大値+1)だけ
		return make_pair(x / wholeSizePair.second, x % wholeSizePair.second);
	}
	else {
		cerr << "error:範囲外参照(UnionFind::intToPair)" << endl;
		exit(1);
	}
}

int N, K, L;
int p, q;
int r, s;

void solve() {
	int ans;
	cin >> N >> K >> L;

	UnionFind uf_road(N + 1);
	for (int i = 0; i < K; i++)
	{
		cin >> p >> q;
		uf_road.unionSet(p, q);
	}
	UnionFind uf_metro(N + 1);
	for (int i = 0; i < L; i++)
	{
		cin >> r >> s;
		uf_metro.unionSet(r, s);
	}

	P wholeSizePair(N + 1, N + 1);
	unordered_map<long long, int> um_both;

	for (int i_city = 1; i_city <= N; i_city++)
	{

		P p(uf_road.root(i_city), uf_metro.root(i_city));
		++um_both[pairToInt(p, wholeSizePair)];
	}
	for (int i_city = 1; i_city <= N; i_city++)
	{
		P p(uf_road.root(i_city), uf_metro.root(i_city));
		ans = um_both[pairToInt(p, wholeSizePair)];
		cout << ans << " ";
	}

	return;
}

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

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

int N;

int main() {
    bool okay = true;
    cin >> N;
    int t_prev, x_prev, y_prev;
    t_prev = x_prev = y_prev = 0;

    for (int i = 1; i <= N; ++i) {
        int t, x, y;
        cin >> t >> x >> y;
        int t_distance = t - t_prev;
        int x_distance = abs(x - x_prev);
        int y_distance = abs(y - y_prev);
        int distance = x_distance + y_distance;

        if (t_distance % 2 != distance % 2) {
            okay = false;
        } else if (distance > t_distance) {
            okay = false;
        }

        t_prev = t;
        x_prev = x;
        y_prev = y;
    }

    cout << (okay ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <complex>
#include <bitset>
#define full(c) c.begin(), c.end()
#define vector2d(name,type,h,w,init) vector<vector<type>> name(h,vector<type>(w,init)) 
const int PRIME = 1000000007;
const int INT_INF = 2147483647;
const long long int LL_INF = 9223372036854775807;
const double PI = acos(-1);
const double EPS = 0.000000001;
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;

int main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	ll i, n, b, sum = 0;
	cin >> n;
	vector<ll> a(n);
	for (i = 0; i < n; i++){
		cin >> a[i];
		a[i] -= i + 1;
	}
	sort(full(a));
	if (n % 2 == 0) b = (a[n / 2] + a[n / 2 - 1]) / 2;
	else b = a[n / 2];
	for (i = 0; i < n; i++) sum += abs(a[i] - b);
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long int llint;

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

	int dp[N];
	for(int i=0;i<N;i++){
		dp[i]=-1;
	}

	dp[0]=0;
	dp[1]=abs(H[1]-H[0]);

	for(int i=2;i<N;i++){
		int costA=abs(H[i]-H[i-1])+dp[i-1];
		int costB=abs(H[i]-H[i-2])+dp[i-2];
		if(costA<costB){
			dp[i]=costA;
		}else{
			dp[i]=costB;
		}
	}
	cout << dp[N-1] << endl;
	return 0;
}


Measured memory_bytes: 1024
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Xs = list(map(int, list(input())))
rXs = Xs[::-1]

num = sum(Xs)
pos = 0
neg = 0

pow_pos = [0]*N
pow_neg = [0]*N
dic = {0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 2, 8: 1}

for m in range(1, num+2):
    c = bin(m)[2:].count('1')
    dic[m] = dic[m%c]+1
    
for i in range(N):
    pow_pos[i] = pow(2, i, num+1)
    if not num==1:
        pow_neg[i] = pow(2, i, num-1)

for i, x in enumerate(rXs):
    if x==0:
        continue
    pos += pow_pos[i]
    if not num==1:
        neg += pow_neg[i]

anss = []
for i, x in enumerate(rXs):
    if num==1 and x==1:
        anss.append(0)
        continue
    if x==0:
        mod = num+1
        tmp = (pos+pow_pos[i])%mod
    else:
        mod = num-1
        tmp = (neg-pow_neg[i])%mod
    ans = dic[tmp]+1
    anss.append(ans)

for ans in anss[::-1]:
    print(ans)
        
            

Measured memory_bytes: 109432
N, M = map(int, input().split())
H = list(map(int, input().split()))
P = [1] * N
ans = N
for i in range(M):
    a, b = map(int, input().split())
    h_a = H[a - 1]
    h_b = H[b - 1]
    if ((h_a > h_b) and (P[b - 1] == 1)):
        ans = ans - 1
        P[b - 1] = 0
    elif ((h_b > h_a) and (P[a - 1] == 1)):
        ans = ans - 1
        P[a - 1] = 0
    elif (h_a == h_b):
        if (P[a - 1] == 1):
            ans = ans - 1
            P[a - 1] =  0
        if (P[b - 1] == 1):
            ans = ans - 1
            P[b - 1] =  0
print(ans)

Measured memory_bytes: 20160
import { COPYFILE_FICLONE_FORCE } from 'constants';

namespace Coder {
  class Scanner {
    private buffer: string = '';
    private stdinQueue: any = [];

    constructor() {
      process.stdin.resume();
      process.stdin.setEncoding('utf8');
      process.stdin.on(
        'data',
        (chunk): void => {
          this.buffer += chunk;
          while (this.stdinQueue.length > 0) {
            const i = this.buffer.indexOf('\n');
            if (i < 0) {
              break;
            }
            let line = this.buffer.substr(0, i);
            if (line.endsWith('\r')) {
              line = line.slice(0, -1);
            }
            this.buffer = this.buffer.substr(i + 1);
            this.stdinQueue.shift()(line);
          }
        },
      );
    }
    public getLine(): Promise<string> {
      return new Promise((resolve, reject) => {
        const i = this.buffer.indexOf('\n');
        if (i >= 0 && this.stdinQueue.length == 0) {
          let line = this.buffer.substr(0, i);
          if (line.endsWith('\r')) {
            line = line.slice(0, -1);
          }
          this.buffer = this.buffer.substr(i + 1);
          resolve(line);
        } else {
          this.stdinQueue.push(resolve);
        }
      });
    }

    public close(): void {
      process.stdin.pause();
    }
  }

  const checkFlag = (f: any) => {
    return f['A'] && f['B'] && f['C'];
  };

  async function slove() {
    const sc = new Scanner();
    const input = [];
    for (let i = 0; i < 6; i += 1) {
      input.push(+(await sc.getLine()));
    }
    const N = input.shift();
    const min = Math.min(...input);
    console.log(Math.ceil(N / min) + 4);

    sc.close();
  }

  slove();
}


Measured memory_bytes: 7628
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
char arr[123][123];
int main(){
    //~ freopen("file.in", "r", stdin);
    int a,b;
    scanf("%d%d",&a,&b);
    char c='.',d='#';
    if(a>b)
		swap(a,b),swap(c,d);
	int n=100,m=100;
	printf("%d %d\n",n,m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)	
			arr[i][j]=c;
	a--;
	vector<PII>v;
	for(int i=1;i<n;i+=4)
		for(int j=1;b and j+8<m;j+=4){
			for(int k=0;k<3;k++)
				for(int h=0;h<3;h++)
					arr[i+k][j+h]=d;
			v.pb(mp(i+1,j+1));		
			b--;
		}
	for(int i=0;a-- and i<int(v.size());i++)	
		arr[v[i].ff][v[i].ss]=c;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)
			printf("%c",arr[i][j]);
		puts("");	
	}		
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>


int main(void){
  int tarm=0; // ターン数カウント
  int i=0,j;
  int cnt_taro=0, cnt_hana=0;
  char a[101], b[101];

  scanf("%d", &tarm);
  while(i<tarm){
    scanf("%s %s", a, b);
    for(j=0;;j++){
      if(a[j]>b[j]){
        cnt_taro+=3;
        break;
      }else if(a[j]<b[j]){
        cnt_hana+=3;
        break;
      }else if(a[j]+b[j]==0){
        cnt_taro++;
        cnt_hana++;
        break;
      }
    }
    i++;
  }
  printf("%d %d\n", cnt_taro, cnt_hana);
  return 0;
}



Measured memory_bytes: 1996
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {
    
    int n;
    cin >> n;
    
    int ans=n;
    
    for(int i=0;i<=n;i++){
        int m=n-i;
        
        int a=m;
        int p=0;
        while(a>0){
            p += a%6;
            a = a/6;
        }
        
        int b=i;
        int q=0;
        while(b>0){
            q += b%9;
            b = b/9;
        }
        
        if(p+q < ans){
            ans =p+q;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    vector<ll> P(N + 1); // 正の部分だけの累積和
    vector<ll> Q(N + 1); // 全部の累積和
    
    ll ps = 0, qs = 0;
    rep(i, N){
        if(A[i] > 0) ps += A[i];
        qs += A[i];
        P[i + 1] = ps;
        Q[i + 1] = qs;
    }
    
    ll ret = 0;
    
    rep(i, N - K + 1){
        
        ll def = P[N];
        def -= P[i + K] - P[i];
        ret = max(ret, def);
        def += Q[i + K] - Q[i];
        ret = max(ret, def);
        
    }
    output(ret);
    
    return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var inputs = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var n = inputs[0];
        var m = inputs[1];

        var h = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

        Dictionary<long, List<long>> Towers = new Dictionary<long, List<long>>();

        for (int i = 0; i < n; i++) Towers[i] = new List<long>();

        for(int i = 0; i < m; i++)
        {
            var ab = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

            Towers[ab[0] - 1].Add(ab[1]);
            Towers[ab[1] - 1].Add(ab[0]);
        }

        // 一個もないもの
        long ans = Towers.Where(t => t.Value.Count == 0).Count();

        // 一番高い
        var tmp = Towers.Where(t => t.Value.Count != 0).ToArray();
        foreach(var item in tmp)
        {
            bool flag = true;

            foreach(var tour in item.Value)
            {
                if (h[item.Key] <= h[tour - 1]) flag = false;
            }

            if (flag) ans++;
        }

        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 58884
from operator import itemgetter

N = int(input())
SP = []
for i in range(N):
    Si, Pi = input().split(" ")
    SP.append([Si, int(Pi), i+1])
SP = sorted(SP, key=itemgetter(0, 1))
before = SP[0][0]
stack = []
for Si, Pi, i in SP:
    if before == Si:
        stack.append(i)
    else:
        for j in reversed(stack):
            print(j)
        stack = [i]
        before = Si
if len(stack) > 0:
    for j in reversed(stack):
        print(j)


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

int main() {
    int K, X;
    cin >> K >> X;
    if (500 * K >= X) cout << "Yes" << endl;
    else cout << "No" << endl;
    return (0);
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <algorithm>

typedef long long ll;
typedef long double ld;

using namespace std;
int main()
{
  int k, n, p[1100], sum = 0;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> p[i];
  sort(p, p + n);
  for (int i = 0; i < k; ++i) sum += p[i];
  cout << sum;
}


Measured memory_bytes: 3604
def check(S):
    size = len(S)
    if S[0]=="0" or S[-1]=="1":
        return False
    else:
        for i in range(size-1):
            a, b = i, size-i-2
            if (S[a]=="1" and S[b]=="0") or (S[a]=="0" and S[b]=="1"):
                return False
        return True


S = input()
if check(S):
    N = len(S)
    l = [1]
    p = False
    for i in range(2, N+1):
        if p:
            l.append(i)
        else:
            print(l[-1], i)
        p = (S[i-1]=="1")
    for i in range(len(l)-1):
        print(l[i], l[i+1])
else:
    print(-1)


Measured memory_bytes: 8576
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>

using namespace std;

#define mod 1000000007

int main()
{
	int a, b;
	cin >> a >> b;
	cout << (a + b) % 24 << endl;
}

Measured memory_bytes: 256
//
//  header_useful.h
//  c++_acm
//
//  Created by 李弘辰 on 2019/7/23.
//  Copyright © 2019 李弘辰. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)
#define cio ios::sync_with_stdio(false);

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */


int main() {
    int x;
    scanf("%d",&x);
    ll v = 0;
    while (x >= 500) {
        x -= 500;
        v += 1000;
    }
    while (x >= 5) {
        x -= 5;
        v += 5;
    }
    printf("%lld\n",v);
    return 0;
}


Measured memory_bytes: 888
#include <stdio.h>

int linersearch(int *,int key);
int n;
int q;
int T[100000];

int main(){
  int i,j;
  int c=0;
  int S[100000];
  int Q[100000];
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0; i<q; i++){
    scanf("%d",&Q[i]);
  }
  for(i=0; i<n; i++){
    T[i] = -1;
  }
  
  for(i=0; i<q; i++){
    c += linerSearch(S,Q[i]);
  }
  printf("%d\n",c);
  return 0;
}

int linerSearch(int *A,int key){
  int i,j,m;
  int l = 0;
 int  r = n;
 while( l<= r-1 ){
    m = (l + r)/ 2;
    if(A[m]==key){
      return 1;
    }else if(key < A[m]){
      r = m;
    }
    else{
      l = m + 1;
    }
  }
  return 0;
  
}




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

using ll = long long; 

const int nax = 1e5+5;
vector<int> edges[nax];
int in_degree[nax];
bool visited[nax];
int dist[nax];

void dfs(int a) {
    visited[a] = true;
    for (int b : edges[a]) {
        dist[b] = max(dist[b], dist[a] + 1);
        in_degree[b] -= 1;
        if (in_degree[b] == 0 && !visited[b]) {
            dfs(b);
        }
    }
}

int main() {
    int n;
    int m;
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < m; i++) {
        int from;
        int to;
        scanf("%d%d", &from, &to);
        edges[from].push_back(to);
        in_degree[to] += 1;
    }
    
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && in_degree[i] == 0) {
            dfs(i);
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dist[i]);
    }
    
    printf("%d", ans);
    
	
	return 0;
}

Measured memory_bytes: 9728
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    if ((a + d - 1) / d >= (c + b - 1) / b)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


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

class Queen {
public:
	int Q[8][8], R[8], C[8], posit[8 * 2 - 1], negat[2 * 8 - 1]; 

	Queen() {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				Q[i][j] = 0;
			}
		}
		for (int i = 0; i < 8; i++) {
			R[i] = 0; 
			C[i] = 0;
		}
		for (int i = 0; i < 2 * 8 - 1; i++) {
			posit[i] = 0;
			negat[i] = 0;
		}
	}

	void recursive(int i) {
		if (i == 8) {
			displayQ();
			return;
		}
		for (int j = 0; j < 8; j++) { 
			if (C[j] || posit[i + j] || negat[i - j + 8 - 1]) { 
				continue;
			}
			R[i] = j; 
			C[j] = posit[i + j] = negat[i - j + 8 - 1] = 1; 
			recursive(i + 1);
			R[i] = C[j] = posit[i + j] = negat[i - j + 8 - 1] = 0; 
		}
	}

	void setQ(int x, int y) {
		Q[x][y] = 1;
	}

	void displayQ() {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if (Q[i][j] && R[i] != j) return; 
			}
		}

		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				cout << ((R[i] == j) ? 'Q' : '.');
			}
			cout << endl;
		}
	}
};

int main() {
	int k;
	cin >> k;
	Queen q = Queen();
	int x, y;
	for (int i = 0; i < k; i++) {
		cin >> x;
		cin >> y;
		q.setQ(x, y);
	}

	q.recursive(0);

	return 0;
}



Measured memory_bytes: 3116
/*  
    Beyond the door
    There's peace I'm sure
    And I know there'll be no more
    Tears in heaven
    _________________________
    _________________________
    792 Hours of Solitude
    Quarantine_Day : 33
*/

#include<bits/stdc++.h>

using namespace std;

typedef long long int       ll;
typedef vector<int>         vi;
typedef vector<ll>          vl;
typedef pair<int, int>      pii;

#define pb(n)           push_back(n)
#define GSORT(v)        sort(v.begin(), v.end(), greater<int>())
#define SORT(v)         sort(v.begin(), v.end());
#define REV(v)          reverse(v.begin(), v.end());
#define db(a)           cout<<#a<<" = "<<a<<endl;
#define FIN             freopen("in.txt","r",stdin);
#define FOUT            freopen("out.txt","w",stdout);
#define REP(i,n)        for(int i = (int)(0); i < (int)(n); i++)
#define FOR(i, a, b)    for(int i = (int)a; i <= (int)b; i++)    

#define MAX 55

ll n;
double a;
vl v(MAX);
ll dp[MAX][MAX][2500];

ll go(ll idx, ll taken, ll sum){
	if(idx >= n){
		if(((double)sum / (double)taken) == a) return 1;
		else return 0;
	}
	if(dp[idx][taken][sum] != -1) return dp[idx][taken][sum];

	return  dp[idx][taken][sum] = go(idx + 1, taken + 1, sum + v[idx]) + go(idx + 1, taken, sum);
}

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

	cin>>n>>a;
	REP(i, n) cin>>v[i];

	memset(dp, -1, sizeof(dp));
	cout<<go(0, 0, 0)<<"\n";
	return 0;
}


Measured memory_bytes: 59392
import copy

def insertion_sort(List):
	l=len(List)
	for i in range(l):
		for j in range(i):
			if List[i]<List[j]:
				temp=copy.copy(List)
				for k in range(j,i):
					List[k+1]=temp[k]
				List[j]=temp[i]
				break
		print(" ".join(map(str,List)))

N=input()
N_List=map(int,raw_input().split())
insertion_sort(N_List)

Measured memory_bytes: 6476
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 3011;

ll n, mod, i, j;
ll ans, aux, inside, outside;

ll p2[maxN * maxN], p2_spec[maxN * maxN];
ll comb[maxN][maxN];

ll dp[maxN][maxN]; //! pui j biti in i grupe (+ grupa nula)
ll ways[maxN][maxN];

ll poww(ll a, ll b, ll moddo) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void solve() {
    ll i, j, step, ans, aux, a, b, c;

    dp[0][0] = 1;
    for (i = 0; i <= n; i++) {
        for (j = i; j <= n; j++) {
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % mod;
            dp[i][j + 1] = (dp[i][j + 1] + dp[i][j] * (i + 1)) % mod;
        }
    }

    ans = 0;

    for (a = 0; a <= n; a++) {
        for (b = 0; a + b <= n; b++) {
            c = n - a - b;

            if (a + b == 0) {
                ans = poww(2, p2_spec[n], mod);
                continue;
            }

            aux = (dp[a][a + b] * p2[c * a]) % mod;
            aux = (aux * poww(2, p2_spec[c], mod)) % mod;
            aux = (aux * comb[n][a + b]) % mod;

            if ((a + b) % 2 == 0)
                ans = (ans + aux) % mod;
            else
                ans = (ans - aux + mod) % mod;
        }
    }

    printf("%lld", ans);
}

int main()
{
   // freopen("test.in","r",stdin);

    cin >> n >> mod;

    p2[0] = p2_spec[0] = 1;
    for (i = 1; i <= n * n; i++) {
        p2[i] = (p2[i - 1] * 2) % mod;
        p2_spec[i] = (p2_spec[i - 1] * 2) % (mod - 1);
    }

    for (i = 0; i <= n; i++) {
        comb[i][0] = 1;
        for (j = 1; j <= i; j++)
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
    }

    solve();


    return 0;
}


Measured memory_bytes: 284288
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,q;
  cin>>n>>m;
  string s="kogakubu10gokan",t;
  while(n--){
    cin>>q>>t;
    if(q<=m)s=t;
  }
  cout<<s<<endl;
}

Measured memory_bytes: 3188
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int x = (X - a) / b;

		int answer = X - (a + b*x);

		System.out.println(answer);

	}
}

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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,bool>;

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

int V, E, s, t;
int residue[110][110], ex[110], d[110];
vector<int> G[110]; // destination
queue<int> Q;

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

    std::cin >> V >> E;
    s = 0; t = V - 1;
    
    for(int i=0;i<E;++i){
        int u, v, c;
        std::cin >> u >> v >> c;

        G[u].emplace_back(v);
        G[v].emplace_back(u);
        
        if(u != s){
            residue[u][v] += c;
        }else{
            residue[v][u] += c;
            ex[u] -= c;
            ex[v] += c;
        }
    }

    d[s] = V;
    
    for(int i=0;i<V;++i){
        if(ex[i] > 0 && i != s && i != t){
            Q.emplace(i);
        }
    }

    while(!Q.empty()){
        int v = Q.front();
        Q.pop();

        if(ex[v] == 0){continue;}

        for(auto w : G[v]){
            if(residue[v][w] > 0 && d[v] == d[w] + 1){
                // push
                int delta = min(ex[v], residue[v][w]);
                residue[v][w] -= delta;
                residue[w][v] += delta;

                if(ex[w] == 0 && w != s && w != t){
                    Q.emplace(w);
                }
                
                ex[v] -= delta;
                ex[w] += delta;
                
                if(ex[v] == 0){break;}
            }
        }

        if(ex[v] == 0){continue;}

        d[v] = 3 * V;
        // relabel
        for(auto w : G[v]){
            if(residue[v][w] > 0){
                d[v] = min(d[v], d[w] + 1);
            }
        }
        
        Q.emplace(v);
    }
    
    int res = -ex[s];
    std::cout << res << std::endl;
}



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

int main(){
    ll n,a,b,c,d,e;
    cin >> n >> a >> b >> c >> d >> e;
    ll q = (n-1)/a;
    ll r = (n-1)/b;
    ll s = (n-1)/c;
    ll t = (n-1)/d;
    ll u = (n-1)/e;
    cout << max({q,r,s,t,u}) + 5 << endl;
}

Measured memory_bytes: 256
def s(n):
    return[m(t)for t in d(f(n))]
def f(n):
    l=[]
    b,e=2,0
    while b*b<=n:
        while not n%b:
            n//=b
            e+=1
        if e:
            l.append((b,e))
        b,e=b+1,0
    if n>1:
        l.append((n,1))
    return l
def d(l):
    b,e=l.pop()
    p=d(l)if l else[[]]
    v=[[(b,k)]for k in range(e+1)]
    return[s+t for s in p for t in v]
def m(l):
    a=1
    for b,e in l:
        a*=b**e
    return a
N,M=map(int,input().split())
if M<2:print(1);exit()
a=0
for i in sorted(s(M))[::-1]:
    if M//i>=N:
        a=i
        break
print(a)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 100000+5;
const int M = N*2;
int n,m;
typedef pair<int,int> pii;
struct Edge {
    int v, d,c;
    int next;
}edge[M];
int head[N], d[N], tot;
int cost[N];
int vis[N];
void addedge(int u, int v, int d,int c) {
    edge[tot].v = v;
    edge[tot].d = d;
    edge[tot].c = c;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dij(int s) {
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    for(int i = 1; i <= n; i++) d[i] = 10000000+5;
    d[s] = 0;
    cost[s] = 0;
    memset(vis, 0, sizeof(vis));
    Q.push(make_pair(d[s], s));
    while(!Q.empty()) {
        pii tmp = Q.top();
        Q.pop();
        int x = tmp.second;
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i+1; i = edge[i].next) {
            if(d[edge[i].v] > d[x] + edge[i].d) {
                d[edge[i].v] = d[x] + edge[i].d;
                cost[edge[i].v] = edge[i].c;
                Q.push(make_pair(d[edge[i].v], edge[i].v));
            }
            if(d[edge[i].v] == (d[x] + edge[i].d))
            {
                cost[edge[i].v] = min(cost[edge[i].v],edge[i].c);
            }
        }
    }
}

int main()
{
   while(scanf("%d%d",&n,&m))
   {
       if(m == 0&& n ==0) break;
       memset(head,-1,sizeof(head));
       tot = 1;
       for(int i = 0; i < m; i++)
       {
           int u,v,d,c;
           scanf("%d%d%d%d",&u,&v,&d,&c);
           addedge(u,v,d,c);
           addedge(v,u,d,c);
       }
       dij(1);
       int ans = 0;
       for(int i = 1; i <= n; i++)
       {
           ans += cost[i];
       }
       cout << ans << endl;
   }

}


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

int N;
int p[111111];

signed main() {
   // 入力
   cin >> N;
   for (int i = 0; i < N; i++) {
      cin >> p[i];
   }

   int cnt = 0;
   for (int i = 0; i < N; ) {
      int add = 1;
      if (p[i] == i+1) {
         cnt++;
         // swap(p[i], p[i+1])をするためp[i+1]を見る必要は無い。なのでi+=2する
         add = 2; 
      }
      i += add;
   }

   cout << cnt << endl;

   return 0;
}

Measured memory_bytes: 640
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
top = [0]*(N+1)
bot = [0]*(N+1)
for i in range(N):
    top[i+1] = gcd(top[i],A[i])
    bot[N-i-1]= gcd(bot[N-i],A[N-i-1])
# print(top,bot)
ans = 0
for i in range(N):
    # print(gcd(top[i], bot[i + 1]))
    ans = max(ans,gcd(top[i],bot[i+1]))
print(ans)

Measured memory_bytes: 16120
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>



using namespace std;
int main(void){
  int n;
  cin >> n;
  int k;
  cin >> k;
  char s[n];
  cin >> s;
  if(s[k-1]=='A'){
    s[k-1]='a';
    cout << s;
    return 0;
  }
  else if(s[k-1]=='B'){
    s[k-1]='b';
    cout << s;
    return 0;
  }

  else if(s[k-1]=='C'){
    s[k-1]='c';
    cout << s;
    return 0;
  }

  return 0;
}


Measured memory_bytes: 256
#--Fifty-Fifty
import collections

S = list(input())

c = collections.Counter(S)

check_1 = int(c.most_common()[0][1])
if (check_1 == 2):
  pass
else:
  print("No")
  exit()

check_2 = int(c.most_common()[1][1])
if (check_2 == 2):
  print("Yes")
else:
  print("No")
  exit()


Measured memory_bytes: 3316
//Ilm kave oi, you know ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)1e12;
int n, m, sz, cyc, visited[MAXN], md0, md1, md2, e;
vector<pair<int, int> > H[MAXN];
void dfs(int u, int num)
{
	sz++;
	visited[u] = num;
	if(num == 0)	
		md0++;
	else
	if(num == 1)
		md1++;
	else
		md2++;
	
	for (auto v : H[u])
	{
		e++;
		int nw = num;
		if(v.second == 0)
			nw = (nw + 1) % 3;
		else
			nw = (nw + 2) % 3;
		if(visited[v.first] == -1)
			dfs(v.first, nw);
		else
		if(visited[v.first] != nw)
			cyc = 1;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		H[u].push_back({v, 0});
		H[v].push_back({u, 1});
	}
	memset(visited, -1, sizeof visited);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		if(visited[i] == -1)
		{
			sz = 0, cyc = 0, md0 = 0, md1 = 0, md2 = 0, e = 0, dfs(i, 0);
			if(cyc == 1)
				ans += 1LL * sz * sz;
			else
			if(md0 && md1 && md2)
				ans += 1LL * md0 * md1 + 1LL * md1 * md2 + 1LL * md2 * md0;
			else
				ans += e / 2;
		}
	cout << ans;
}


Measured memory_bytes: 10752
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("game.in","r",stdin)
#define OUT freopen("game.out","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define LOG 19
#define off 2
#define sq(x) ((x)*(x))
using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less< i64 >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//#define mod 998244353LL
#define INF 1000000000
#define maxn 5000005
#define LL long long

vector <int> g[maxn] ;

int main()
{
    int n , m ;
    scanf("%d %d",&n,&m) ;

    for(int i=1 ; i<=m ; i++)
    {
        int u , v ;
        scanf("%d %d",&u,&v) ;
        g[u].pb(v) ; g[v].pb(u) ;
    }

    int fl = 1 ;
    for(int i=1 ; i<=n ; i++)
    {
        if( g[i].size()%2 == 1 ) fl = 0 ;
    }

    if(fl==0)
    {
        printf("No\n") ;
        return 0 ;
    }

    int four = 0 , six = 0 ;

    for(int i=1 ; i<=n ; i++)
    {
        if( g[i].size() == 4 ) four++ ;
        if( g[i].size() >= 6 ) six++ ;
    }

    if( six || four >= 3 )
    {
        printf("Yes\n") ;
        return 0 ;
    }

    if( four<=1 )
    {
        printf("No\n") ;
        return 0 ;
    }

    int u=-1 , v=-1 ;
    for(int i=1 ; i<=n ; i++)
    {
        if( g[i].size()==4 )
        {
            if(u==-1) u = i ;
            else v = i ;
        }
    }

    for(int i=0 ; i<g[u].size() ; i++)
    {
        int x=g[u][i] , prev = u ;

        while( x!=u && x!=v )
        {
            int Next = (g[x][0]^g[x][1]^prev) ;
            prev = x ;
            x = Next ;
        }
        if(x==u)
        {
            printf("Yes\n") ;
            return 0 ;
        }
    }

    printf("No\n") ;

    return 0 ;
}


Measured memory_bytes: 120576
X = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
Y = make_divisors(X)

for i in Y:
    for j in range(-1000,1000):
        A = j
        B = A - i
        if A**5 - B**5 == X:
            print(A,B)
            exit()

Measured memory_bytes: 68020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int inf = 0x3f3f3f3f;
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
int t;
int n,m; 
int a[1005],b[1005],c;
int p[1005];
int dp[(1<<13)];
int dis[15][15];
int main()
{
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d%d",&n,&m);
	int N = (1<<n);
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&a[i],&b[i]);
		p[i] = 0;
		for(int j=1;j<=b[i];++j)
		{
			scanf("%d",&c); --c;
			p[i]|=(1<<c);
		}
//		printf("(%d,%d)\n",i,p[i]);
	}
	memset(dp,0x3f,sizeof dp);
	dp[0] = 0;
	for(int i=0;i<m;++i)
	{
		for(int j=0;j<N;++j)
		{
			dp[j|p[i]] = min(dp[j|p[i]],dp[j]+a[i]);
		}
	}
	printf("%d\n",dp[N-1]==inf?-1:dp[N-1]);
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  char s[100000];
  int i;
  int cnt=0;
  
  scanf("%s",s);
  
  for(i=0;i<100000;i++){
      if(s[i]==s[i+1]){
        if(s[i]=='0'){
          s[i+1]='1';
          cnt++;
        }
        if(s[i]=='1'){
          s[i+1]='0';
          cnt++;
        }
      }
   }
     printf("%d\n",cnt);
    return 0;
  }
        

Measured memory_bytes: 256
m = list(map(int,input().split()))
l = sorted([list(map(int,input().split())) for i in range(m[0])], key=lambda x: x[0])
r = 0
c = 0
for a in l:
  if (c + a[1]) >= m[1]:
    r += a[0] * (m[1] - c)
    break
  c += a[1]
  r += a[0] * a[1]
print(r)

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

bool betemp(string sleft, string sright, int left, int right) {
    if (sleft == sright) return (right - left) % 2 == 1;
    else return (right - left) % 2 == 0;
}

void solve(int N) {
    string vac = "Vacant";
    string sleft, sright, str;
    int left = 0, right = N/2;
    cout << left << endl;
    cin >> sleft;
    if (sleft == vac) return;
    cout << right << endl;
    cin >> sright;
    if (sright == vac) return;

    if (!betemp(sleft, sright, left, right)) {
        swap(sleft, sright), left = right, right = N;
    }
    while (right - left > 1) {
        int mid = (left + right) / 2;
        cout << mid << endl;
        cin >> str;
        if (str == vac) return;
        if (betemp(sleft, str, left, mid)) sright = str, right = mid;
        else sleft = str, left = mid;
    }
}

int main() {
    int N;
    while (cin >> N) solve(N);
}

Measured memory_bytes: 852
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include <iomanip>
#include<deque>
#include<stack>
#include<set>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
const int INF = 111111111;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const int DIV = 1000000007; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;




int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	//==================================


	ll N;
	cin >> N;


	vector<ll> alp(5);
	for (ll i = 0; i < 5; i++) {
		alp[i] = 0;
	}
	for (ll i = 0; i < N; i++) {
		string S;
		cin >> S;
		if (S[0] == 'M') {
			alp[0]++;
		}
		else if (S[0] == 'A') {
			alp[1]++;
		}
		else if (S[0] == 'R') {
			alp[2]++;
		}
		else if (S[0] == 'C') {
			alp[3]++;
		}
		else if (S[0] == 'H') {
			alp[4]++;
		}
	}

	ll ans = 0;
	for (ll i = 0; i < 5; i++) {
		for (ll j = i + 1; j < 5; j++) {
			for (ll k = j + 1; k < 5; k++) {
				ans += alp[i] * alp[j] * alp[k];
			}
		}
	}

	cout << ans;


}	


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

signed main(){
	int N,W;cin>>N>>W;
	vector<int>w(N),v(N);
	rep(i,N)cin>>w[i]>>v[i];
	vector<vector<int>>v4(4);
	vector<vector<int>>sm(4,vector<int>(101,0));
	int w0=w[0];
	rep(i,N){int x=w[i]-w0;v4[x].push_back(v[i]);}
	rep(i,4){sort(begin(v4[i]),end(v4[i]),greater<int>());}
	vector<int>sz(4);
	rep(i,4)sz[i]=v4[i].size();
	rep(i,4)rep(j,sz[i])sm[i][j+1]=sm[i][j]+v4[i][j];

	int ret=0,ans=0;
	rep0(i,sz[0])rep0(j,sz[1])rep0(k,sz[2])rep0(l,sz[3]){
		
		if(i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)>W)continue;
		ret=0;
		ret+=sm[0][i];ret+=sm[1][j];ret+=sm[2][k];ret+=sm[3][l];
		ans=max(ans,ret);
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

const ll MOD = 1000000000;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
// const ll MAXN = 

ll s;
/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> s;
    if (s == 1000000000000000000) {
        cout << 0 << " " << 0 << " " << MOD << " " << 0 << " " << 0 << " " << MOD << endl; 
    } else {
        cout << 0 << " " << 0 << " " << MOD << " " << 1 << " " << MOD - s % MOD << " " << s/MOD+1 << endl; 
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		prepareFact();
		int numQ = sc.nextInt();
		for(int i = 0; i < numQ; i ++) {
			long x = sc.nextLong();
			long d = sc.nextLong();
			long num = sc.nextLong();
			if(x == 0) { System.out.println(0); continue; }
			if(d == 0) { System.out.println(powerMod(x, num)); continue; };
			x = mod(x * invMod(d));
			if(x + num - 1 >= MOD) { System.out.println(0); continue; }
			long ans = mod(factMod[(int)(x + num - 1)] * invMod(factMod[(int)(x - 1)]));
			ans = mod(ans * powerMod(d, num));
			System.out.println(ans);
		}
	}
	static int MOD = 1_000_003;
	public static long mod(long i) {
		return i % MOD + ((i % MOD) < 0 ? MOD : 0);
	}
	
	static long powerMod(long x, long y) {
		if (y == 0) {
			return 1;
		} else if (y == 1) {
			return x;
		} else if (y % 2 == 0) {
			long tmp = powerMod(x, y / 2);
			return mod(tmp * tmp);
		} else {
			long tmp = powerMod(x, y / 2);
			return mod(mod(tmp * tmp) * x);
		}
	}
	
	static long invMod(long x) {
		return powerMod(x, MOD - 2);
	}
	
	static int MAX_FACT = MOD;
	static long factMod[] = new long[MAX_FACT];
	static void prepareFact() {
		factMod[0] = 1;
		for(int i = 1; i < MAX_FACT; i ++) {
			factMod[i] = mod(factMod[i - 1] * i);
		}
	}
	
	static long combiMod(int n, int r) {
		if(n < 0 || n < r) { return 0; }
		if(r == 0 || r == n) { return 1; }
		return mod(mod(factMod[n] * invMod(factMod[r])) * invMod(factMod[n - r]));
	}
}

Measured memory_bytes: 101900
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>

using namespace std;

#define ll long long

int main(){
	ll R,G,B,N;
	cin >> R >> G >> B >> N;
	int ans = 0;
	for(ll r = 0;r <= N;r++){
		for(ll g = 0;g <= N;g++){
			ll sum = R*r + G*g;
			ll left = N - sum;
			if(left < 0)continue;
			if(left%B==0){
				// cout << r << "," << g << "," << left/B << endl;
				ans++;
			}
		}
	}
	cout << ans << endl;
}

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

template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  int H,W,A,B;cin>>H>>W>>A>>B;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++)cout<<((i<B)^(j<A));
    cout<<endl;
  }
}


Measured memory_bytes: 1280
import java.io.*;

public class Main {
	public static void main(String[] args) {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		try {
			int n;
			int id = 1;
			
			while(true){
				/* input from here */
				String line = r.readLine();
				n = Integer.parseInt(line);
				if(n==0){
					break;
				} else if(n==1){
					System.out.println("Case " + id + ":");
					System.out.println("  1");
					id++;
					continue;
				}
				/* input till here */
				
				/* output matrix */
				int[][] m = new int[n][n];
				m[0][0] = 1;
				//first row
				for(int column=0;column<n;column++){
					if(column%2==1){
						m[0][column] = m[0][column-1] + 1;
					} else if(column!=0){
						m[0][column] = m[0][column-1] + 2*column;
					}
				}
				//2nd row to 2nd to last row
				for(int row=1;row<n-1;row++){
					//2nth row
					if(row%2==1){
						for(int column=0;column<n-1;column++){
							if(column%2==0){
								m[row][column] = m[row-1][column+1] + 1;
							} else {
								m[row][column] = m[row-1][column+1] - 1;
							}
						}
						if(n%2==0){
							m[row][n-1] = m[row-1][n-1] + (n-row)*2;
						} else {
							m[row][n-1] = m[row-1][n-1] + 1;
						}
					} else {//(2n+1)th row
						for(int column=0;column<n-1;column++){
							if(column%2==0){
								m[row][column] = m[row-1][column+1] - 1;
							} else {
								m[row][column] = m[row-1][column+1] + 1;
							}
						}
						if(n%2==1){
							m[row][n-1] = m[row-1][n-1] + (n-row)*2;
						} else {
							m[row][n-1] = m[row-1][n-1] + 1;
						}
					}
				}
				//final row
				if(n%2==0){
					m[n-1][0] = m[n-2][1] + 1;
					for(int column=1;column<n;column++){
						if(column%2==1){
							m[n-1][column] = m[n-1][column-1] + 1;
						} else if(column!=0){
							m[n-1][column] = m[n-1][column-1] + (n-column)*2;
						}
					}
				} else {
					m[n-1][0] = m[n-2][0] + 1;
					for(int column=1;column<n;column++){
						if(column%2==1){
							m[n-1][column] = m[n-1][column-1] + (n-column)*2;
						} else {
							m[n-1][column] = m[n-1][column-1] + 1;
						}
					}
				}
				
				/* output */
				System.out.println("Case " + id + ":");
				for(int row=0;row<n;row++){
					for(int i=0;i<n;i++){
						System.out.print(String.format("%3d",m[row][i]));
					}
					System.out.println();
				}
				id++;
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 19088
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;

char win(char s) {
	switch (s) {
	case 'r':
		return 'p';
	case 's':
		return 'r';
	case 'p':
		return 's';
	default:
		return 'q';
	}
}

int main(void) {
	int n, k, r, s, p;
	char t[100001];
	cin >> n >> k >> r >> s >> p;
	for (int i = 0; i < n; ++i) {
		cin >> t[i];
	}
	ll score = 0;
	for (int i = 0; i < n; ++i) {
		switch (win(t[i])) {
		case 'r':
			if (i < k || t[i] != t[i - k]) {
				score += r;
			}
			else {
				t[i] = 'q';
			}
			break;
		case 's':
			if (i < k || t[i] != t[i - k]) {
				score += s;
			}
			else {
				t[i] = 'q';
			}
			break;
		case 'p':
			if (i < k || t[i] != t[i - k]) {
				score += p;
			}
			else {
				t[i] = 'q';
			}
			break;
		}
	}
	cout << score;
}


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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

signed main(){
	while(true){
		int x=read(),y=read(),s=read();
		if(x||y||s){
			int ans=0;
			for(int i=1;i<s;i++){
				for(int j=1;j<s;j++){
					if(i*(100+x)/100+j*(100+x)/100 == s){
						ans = max(ans,i*(100+y)/100+j*(100+y)/100);
					}
				}
			}
			cout << ans << endl;
		}
		else return 0;
	}
}

Measured memory_bytes: 3124