akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

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

	private void run() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int q = scanner.nextInt();
		DisjoinSet ds = new DisjoinSet(n);
		for (int i = 0; i < q; i++) {
			int t = scanner.nextInt();
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			if (t == 0)
				ds.unite(a, b);
			else {
				if (ds.same(a, b))
					System.out.println(1);
				else
					System.out.println(0);
			}

		}

	}

	class DisjoinSet {
		int[] rank;
		int[] p;

		DisjoinSet(int size) {
			rank = new int[size];
			p = new int[size];
			for (int i = 0; i < size; i++) {
				p[i] = i;
			}
		}

		int findSet(int x) {
			while (true) {
				if (x == p[x])
					return x;
				x = p[x];
			}
		}

		public boolean same(int a, int b) {
			return findSet(a) == findSet(b);
		}

		public void unite(int a, int b) {
			link(findSet(a), findSet(b));
		}

		private void link(int x, int y) {
			if (rank[x] > rank[y]) {
				p[y] = x;
			} else {
				p[x] = y;
				if (rank[x] == rank[y])
					rank[y]++;
			}
		}
	}
}

Measured memory_bytes: 97652
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,s,t=0;
    cin>>n>>s;
    long a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]>=s)
         t++;
    }
    cout<<t;
    return 0;
}
     
   




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

void call(int n) {
	int i = 1;
CHECK_NUM:
	int x = i;
	if (x % 3 == 0) {
		cout << " " << i;
		goto END_CHECK_NUM;
	}
INCLUDE3:
	if (x % 10 == 3) {
		cout << " " << i;
		goto END_CHECK_NUM;
	}
	x /= 10;
	if (x) goto INCLUDE3;
END_CHECK_NUM:
	if (++i <= n) goto CHECK_NUM;

	cout << endl;
}

int main()
{
	int n;
	cin >> n;
	call(n);
	return 0;
}

Measured memory_bytes: 3084
#include "bits/stdc++.h"
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
using ll = long long;
using namespace std;

/*
ll GCD(ll a, ll b) {
	return b ? GCD(b, a%b) : a;
}
*/
//sort(a, a + N, greater<int>())   // descend
//sort(a, a+N)                    //  ascend



/** main内でnCn~nC0 生成 **
vector<vector<long long int> > v(n + 1, vector<long long int>(n + 1, 0));
	comb(v);


*/


void comb(vector<vector <long long int > > &v) {
	ll mod = 1000000007;
	for (int i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (int k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%mod;
			
		}
	}
}

int main() {
	ll n, k;
	cin >> n >> k;

	vector<vector<long long int> > v(n + 1, vector<long long int>(n + 1, 0));
	comb(v);

	ll ans[2200];
	ll mod = 1000000007;
	ans[1] = (n - k + 1) % mod;

	rep(i, 2, k + 1) ans[i] = (v[n - k+1][i] * v[k - 1][i - 1])%mod;
	rep(i, 1, k + 1) cout << ans[i] << endl;

}

Measured memory_bytes: 31616
require'prime'
f=(1..gets.to_i).reduce:*
*q=2**74
Prime.take_while{|x|x<99}.permutation(3){|x,y,z|q<<x*x*(y*z)**4<<x**4*y**14<<x**2*y**24}
p q.uniq.count{|x|f%x<1}

Measured memory_bytes: 4732
/**
 *  winners never quit
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pp pop_back
#define mp make_pair
typedef long long Long;
void FastIO(){
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
}

const int N = 1e4;

int ar[N+1];

int main()
{
  FastIO();
  int tc, ca = 0;
  for (Long i = 1;i <= N;i++){
    for (Long j = 1;j <= N;j++){
      for (Long k = 1;k <= N;k++){
        Long p = (i*i)+(j*j)+(k*k)+(i*j)+(j*k)+(k*i);
        if (p <= N){
          ar[p]++;
        }else break;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 1;i <= n;i++){
    cout << ar[i] << '\n';
  }
  return 0;
}


Measured memory_bytes: 3604
#include<iostream>

int main(){
    int a,b;
    std::cin>>a>>b;
    if(a<b){
        std::cout<<"a < b"<<std::endl;
    }else if(a>b){
        std::cout<<"a > b"<<std::endl;
        }else std::cout<<"a == b"<<std::endl;
    return 0;
}


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

using namespace std;

int main(){
    int N;
    vector<int> row;
    cin >> N;
    for(int i = 0;i<N;i++){
        int temp = 0;
        cin >> temp;
        row.push_back(temp);
    }
    int times = 0;
    bool flag = true;
    while(flag){
        flag = false;
        for(int j = N - 1 ; j > 0; j--){
            if(row[j] < row[j - 1]){
                swap(row[j ],row[j - 1]);
                times ++;
                flag = true;
            }
        }
    }
    for(int i = 0;i < N;i++){
        if(i == N - 1){
            cout << row[i] << endl;
        }else{
            cout << row[i] << " ";
        }
    }
    cout << times << endl;
    return 0;
}


Measured memory_bytes: 3144
#include <cstdio>

struct date{
	int year, month, day;
};

int era_trans(struct date d);

int era_year[4] = {1868, 1912, 1926, 1989}; //各eraの最初の年
int era_month[4] = {9, 7, 12, 1}; //各eraの最初の月
int era_day[4] = {8, 30, 25, 8}; //各eraの最初の日
char era_name[4][20] = {"meiji", "taisho", "showa", "heisei"};

int main(void)
{
	struct date d;
	int n, ans_year;

	while (scanf("%d%d%d", &d.year, &d.month, &d.day) != EOF) {
		n = era_trans(d);
		if (n == 0) {//n == 0 <-> pre-meijiだったら
			printf("pre-meiji\n");
		} else {
			ans_year = d.year - era_year[n-1] +1;
			printf("%s %d %d %d\n", era_name[n-1], ans_year, d.month, d.day);
		}
	}
}
int era_trans(struct date d)
{//eraに応じた数字を返す
	int i;
	for (i=0; i<4; i++) {
		if (d.year < era_year[i]) {
			break;
		} else if (d.year == era_year[i] && d.month < era_month[i]){
			break;
		} else if (d.year == era_year[i] && d.month == era_month[i] && d.day < era_day[i]) {
			break;
		}
	}
	//i = 0 :: pre-meiji
	//i = 1 :: meiji
	//i = 2 :: taisho
	//i = 3 :: showa
	//i = 4 :: heisei
	return i;
}

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

using namespace std;

int main()
{
	string S;
	cin >> S;

	vector < int >ans(S.size(), 0);

	int index = 0;
	while ((size_t)index < S.size()) {
		int head = index;
		int LEnd = 0;
		int REnd = 0;
		while (S[index] == 'R') {
			if ((index - head) % 2 == 0) {
				LEnd++;
			} else {
				REnd++;
			}
			index++;
		}
		if ((index - head) % 2 != 0) {
			swap(LEnd, REnd);
		}
		ans[index - 1] += REnd;
		ans[index] += LEnd;

		head = index;
		LEnd = 0;
		REnd = 0;
		while ((size_t)index < S.size() && S[index] == 'L') {
			if ((index - head) % 2 == 0) {
				LEnd++;
			} else {
				REnd++;
			}
			index++;
		}
		if ((index - head) % 2 == 0) {
			swap(LEnd, REnd);
		}
		ans[head - 1] += REnd;
		ans[head] += LEnd;
	}

	for (int i = 0; (size_t)i < S.size(); i++) {
		cout << ans[i] << " ";
	}

	cout << "\n";

	return 0;
}


Measured memory_bytes: 1024
#define _overload3(_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(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(int argc, char* argv[]){
    int a, b;
    cin >> a >> b;
    if(a + b == 15) cout << "+" << endl;
    else if(a * b == 15) cout << "*" << endl;
    else cout << "x" << endl;
}



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

int main(){
    long long a, b, k;
    cin >> a >> b >> k;
    if(k > a){
        cout << "0 " << max(b - (k - a), 0ll) << '\n';
    } else {
        cout << (a - k) << ' ' << b << '\n';
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl lcm(intl a,intl b){
    return a / gcd(a, b) * b;
}
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl a,b,c,d;
    cin >> a >> b >> c >> d;
    intl cnt = 0;
    rep(i,a + 1){
        rep(j,b + 1){
            rep(k,c + 1){
                cnt += (d == (500 * i + 100 * j + 50 * k));
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    S = input()
    youbi = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

    for i in range(len(youbi)):
        if youbi[i] == S:
            print(7 - i)


if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions

x = int(stdin.readline().rstrip())

num = 100
year = 0
while True:
    num = int(num * 1.01)
    year += 1
    if num >= x:
        print(year)
        break


Measured memory_bytes: 73084
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

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

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=100005;
const ll lmod = 1e9+7;

int main(){
  int N;
  string s1,s2;
  cin >> N >> s1 >> s2 ;
  int i = 0;
  ll ans = 1;
  bool tate;
  if(s1[0]==s2[0]){
    ans *= 3;
    i += 1;
    tate = true;
  }else{
    ans *= 6;
    i += 2;
    tate = false;
  }
  while(i<N){
    if(s1[i]==s2[i]){
      i+=1;
      (ans*=(tate ? 2 : 1))%=lmod;
      tate = true;
    }else{
      i+=2;
      (ans*=(tate ? 2 : 3))%=lmod;
      tate = false;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int h,w,i,j;
  while(1){
    scanf("%d %d", &h, &w);
    if( h == 0 && w == 0) break;
    for(i = 0; i < h; i++){
      for(j = 0; j < w; j++){
	if( ( i + j )% 2 == 0 ){
	  printf("#");
	}
	else{
	  printf(".");
	}
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}




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

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int n;
	cin >> n;
	vector<int> a(n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	int md = (int) round((double) sum / n);
	int res = 0;
	for (int i = 0; i < n; i++) {
		int x = abs(a[i] - md);
		res += x * x;
	}
	cout << res << '\n';

	return 0;
}



Measured memory_bytes: 256
class MyDict:
    def __init__(self, max):
        self.max = max
        self.pow = [1] * (self.max + 1)
        for i in range(1, self.max + 1):
            self.pow[i] = self.pow[i - 1] * 4
        self.d = [False] * (self.pow[-1])
        
    def __hash(self, val):
        l = len(val)
        h = -1
        for i in range(l):
            if val[i] == 'A':
                h += (1*self.pow[i])
            elif val[i] == 'C':
                h += (2*self.pow[i])
            elif val[i] == 'G':
                h += (3*self.pow[i])
            elif val[i] == 'T':
                h += (4*self.pow[i])
        return h
    
    def insert(self, x):
        key = self.__hash(x)
        self.d[key] = True
    
    def find(self, x):
        key = self.__hash(x)
        return self.d[key]
        

n = int(input())
dic = MyDict(12)

for _ in range(n):
    cmd, x = input().split()
    
    if cmd == 'insert':
        dic.insert(x)
    elif cmd == 'find':
        print('yes') if dic.find(x) else print('no')




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

using namespace std;

int main() {
    vector<int> A(3);
    int K;
    cin >> A[0] >> A[1] >> A[2];
    sort(A.begin(), A.end());
    cin >> K;
    for(int k=0; k<K; k++) {
        A[2] *= 2;
    }
    
    cout << A[0]+A[1]+A[2] << endl;


    return 0;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const int MOD = 998244353;
const ll INF = 1000000000000000000;


int main()
{
	string S;
	cin >> S;
	if (S[S.size() - 1] == 's') S += "es";
	else S += "s";
	cout << S << endl;
}

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

lists=[]
for i in range(m):
    a=int(input())
    lists.append(a)

fiblist=[1,1]
for j in range(10**5):
    nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
    fiblist.append(nums)
lists.insert(0,0)
lists.append(n)
ans=1
if m>=2:
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fiblist[n])
if m==1:
    print(fiblist[lists[1]-1]*fiblist[n-lists[1]-1]%(10**9+7))

Measured memory_bytes: 11056
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7;



int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    if(s.size() > n) cout << s.substr(0, n) << "...";
    else cout << s;


    return 0;

}


Measured memory_bytes: 3644
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <iostream> 
#include <iomanip>  
#include <string>
#include <sstream>  
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <cstring>
#include <cmath>
#include <cassert>


#define INF              (int)1000000007
#define EPS              1e-9
#define pb               push_back
#define mp               make_pair
#define all(c)           c.begin(), c.end()
#define forall(i,a,b)    for(int i=a;i<(b);++i)
#define trav(a,x)        for(auto & a: x)
#define in(a,b)          ((b).find(a) != (b).end())
#define sz(c)            (int)(c).size()
#define input(a)         for(auto & x : a) cin >> x;

using namespace std;

typedef vector<int>      vi;
typedef pair<int,int>    ii;
typedef vector<vi>       vvi;
typedef vector<ii>       vii;
typedef long long        ll;

#ifdef DEBUG
#define trace(...)       __f(#__VA_ARGS__, __VA_ARGS__)
#define debug(args...)   {dbg,args; clog<<endl;}
#define print_( a )      for( auto & x : a ) clog << x << ' '; clog << '\n';
#define printPair_( a )  for( auto & x : a ) clog << '(' << x.first << ',' << x.second << ')' << ' '; clog << '\n';
#else
#define trace(...)       
#define debug(args...)            
#define print_( a )               
#define printPair_( a )           
#endif

struct debugger {
  template<typename T> debugger& operator , (const T& x) {    
    clog << x << " ";    return *this;    
  }
}dbg;

template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " | ";
    __f(comma + 1, args...);
}

auto ____ =[]() { std::ios::sync_with_stdio(0); cin.tie(0); return nullptr; }();

int main( int argc, char * argv[] ){
  int n; cin >> n; 
  vi v(n); input(v);
  vi dp(n,INF);
  dp[0] = 0;
  forall(i,1,n){
    if( i > 1 ) dp[i] = min(dp[i], dp[i-2] + abs(v[i]-v[i-2]));
    dp[i] = min(dp[i], dp[i-1] + abs(v[i] - v[i-1]));
  }
  cout << dp.back() << endl;
  return 0;
}


Measured memory_bytes: 1024
A = [1, 3, 5, 7, 8, 10, 12]
B = [2]
C = [4, 6, 9, 11]

x, y = map(int, input().split())

flag = False
for g in [A, B, C]:
  if (x in g and y in g):
    flag = True
if flag:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
N = int(input())
ans = 0
for i in range(N+1):
  yaku = 0
  if (i+1) % 2 == 1:
    continue
  for j in range(i):
    if i % (j+1) == 0:
      yaku += 1
  if yaku == 8:
    ans += 1 
print(ans)
  

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
const Int MOD=1e9+9; //<- alert!!!
typedef vector<Int> arr;
typedef vector<arr> mat;
inline arr mul(mat a,arr& b,Int mod){
  arr res(b.size(),0);
  for(int i=0;i<(int)b.size();i++)
    for(int j=0;j<(int)a[i].size();j++)
      (res[i]+=a[i][j]*b[j])%=mod;
  return res;
}
inline mat mul(mat& a,mat& b,Int mod){
  mat res(a.size(),arr(b[0].size(),0));
  for(int i=0;i<(int)a.size();i++)
    for(int j=0;j<(int)b[0].size();j++)
      for(int k=0;k<(int)b.size();k++)
	(res[i][j]+=a[i][k]*b[k][j])%=mod;
  return res;
}
inline mat mat_pow(mat a,Int n,Int mod){
  mat res(a);
  for(int i=0;i<(int)a.size();i++)
    for(int j=0;j<(int)a[i].size();j++)
      res[i][j]=(i==j);
  while(n){
    if(n&1) res=mul(a,res,mod);
    a=mul(a,a,mod);
    n>>=1;
  }
  return res;
}
//END CUT HERE
mat base;
mat memo[100];
void init(mat a,Int mod){
  base=mat(a);
  for(int i=0;i<(int)base.size();i++)
    for(int j=0;j<(int)base.size();j++)
      base[i][j]=i==j;
  memo[0]=a;
  for(int k=1;k<70;k++)
    memo[k]=mul(memo[k-1],memo[k-1],mod);
}
inline mat mat_pow2(Int n,Int mod){
  mat res(base);
  int k=0;
  while(n){
    if(n&1) res=mul(memo[k],res,mod);
    n>>=1;
    k++;
  }
  return res;
}

typedef pair<Int,Int> P;
signed main(){
  Int w,h,n,cnt=0;
  while(cin>>w>>h>>n,w||h||n){
    Int x[n],y[n];
    for(Int i=0;i<n;i++) cin>>x[i]>>y[i];
    P p[n];
    for(Int i=0;i<n;i++) p[i]=P(y[i],x[i]);
    sort(p,p+n);
    for(Int i=0;i<n;i++) x[i]=p[i].second,y[i]=p[i].first;
    arr a(w,0);
    a[0]=1;
    mat b(w,arr(w,0));
    for(Int i=0;i<w;i++){
      for(Int j=0;j<w;j++) b[i][j]=0;
      b[i][i]=1;
      if(i-1>=0) b[i][i-1]=1;
      if(i+1<w)  b[i][i+1]=1;
    }
    init(b,MOD);
    Int d=1;
    for(Int k=0;k<n;k++){
      if(y[k]==d) continue;
      a=mul(mat_pow2(y[k]-d-1,MOD),a,MOD);
      Int j=k;
      mat c=b;
      while(j<n&&y[k]==y[j]){
	for(Int i=0;i<w;i++) c[x[j]-1][i]=0;
	j++;
      }
      a=mul(c,a,MOD);
      d=y[k];
    }
    a=mul(mat_pow2(h-d,MOD),a,MOD);
    cout<<"Case "<<++cnt<<": "<<a[w-1]<<endl;
  }
  return 0;
}

/*
  verified on 2017/10/29
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397
*/



Measured memory_bytes: 6432
#include <bits/stdc++.h>
using namespace std;
const int kMaxValue = 12;

int main() {
    int n; cin >> n;
    vector<int> v(n, 0);
    vector<int> f(kMaxValue + 1, 0);

    for (int i = 0; i < n; i += 1) {
        cin >> v[i];
        f[v[i]] += 1;

        if (f[v[i]] >= 3) {
            cout << "0\n";
            return 0;
        }
    }

    if (f[0] >= 1) {
        cout << "0\n";
        return 0;
    }

    if (f[12] >= 2) {
        cout << "0\n";
        return 0;
    }
   
    vector<int> state (2 * kMaxValue + 1, 0); 
    vector<int> others;
    state[0] = 1;

    for (int i = 1; i <= 12; i += 1) {
        if (f[i] == 2) {
            state[i] = 1;
            state[24 - i] = 1;
        } else if(f[i] == 1) {
            others.push_back(i);
        }
    }
    
    int k = others.size();
    int ans = 0;
    
    auto eval = [] (vector<int> state) {
        int ans = kMaxValue + 1;
        for (int i = 0; i <= 23; i += 1)
            for (int j = i + 1; j <= 23; j += 1)
                if (state[i] and state[j])
                    ans = min(ans, min(j - i, 24 - (j - i)));

        return ans;
    };

    for (int mask = 0; mask < (1 << k); mask += 1) {
        vector<int> temp_state = state;
        for (int i = 0; i < k; i += 1) {
            if ((1 << i) & mask) {
                temp_state[others[i]] = 1;
            } else {
                temp_state[24 - others[i]] = 1;
            }
        }

        ans = max(ans, eval(temp_state));
    }
    
    cout << ans << "\n";
}

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b)
        cout << c << endl;
    else if (b == c)
        cout << a << endl;
    else
        cout << b << endl;

    return 0;
}


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

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

  sort(v.begin(), v.end());

  double ans = (double)v[0];
  for (int i=1; i<N; i++){
    ans = (ans + (double)v[i]) / 2;
  }

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


Measured memory_bytes: 256
import java.util.*;
 
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double N = Integer.parseInt(sc.next());
        double K = Double.parseDouble(sc.next());
        double sum = 0;
        if(N < K) {
            for(int i = 1; i <= N; i++) {
                int kijun = 0;
                if(Math.log(K / i) / Math.log(2) == (int)(Math.log(K / i) / Math.log(2))) {
                    kijun = (int)(Math.log(K / i) / Math.log(2));
                }else {
                    kijun = (int)(Math.log(K / i) / Math.log(2)) + 1;
                }
                sum += 1 / (double)N * Math.pow(0.5, kijun);
            }
            System.out.println(sum);
        }else {
            
            for(double i = 1; i < K; i++) {
                int kijun = 0;
                if(Math.log(K / i) / Math.log(2) == (int)(Math.log(K / i) / Math.log(2))) {
                    kijun = (int)(Math.log(K / i) / Math.log(2));
                }else {
                    kijun = (int)(Math.log(K / i) / Math.log(2)) + 1;
                }
                sum += (1 / N) * Math.pow(0.5, kijun);
            }
            
            sum += (1 / N) * (N - K + 1);
            System.out.println(sum);
        }
        
    }
}

Measured memory_bytes: 21588
def chmax(dp, i, x):
  if dp[i] < x:
    dp[i] = x
    return True
  return False

n, W = map(int, input().split())
dp = [-10**9]*(W+1)
dp[0] = 0
for i in range(n):
  w, v = map(int, input().split())
  for i in range(W-w,-1,-1):
    dp[i+w] = max(dp[i+w], dp[i] + v) 
print(max(dp))

Measured memory_bytes: 41580
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define int long long 
#define ld long double
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define endl '\n'
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define loop(i,l,r) for(int i=l;i<r;i++)
#define rloop(i,r,l) for(int i=r;i>=l;i--)
#define watch(x) cerr<<(#x)<<"= "<<(x)<<endl;
#define watcharr(a) cerr<<(#a)<<"("<<sz(a)<<")= ";rep(i,sz(a))cerr<<a[i]<<",";cerr<<'\n';
#define inf 2000000000000000000LL
#define mod 1000000007
#define mod1 998244353
#define FASTIO std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;

signed main() {
    FASTIO;
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    //     freopen("stderr.txt", "w", stderr);
    // #endif

    // int tt=1;
    // cin>>tt;
    // while(tt--){
        int n;
        cin>>n;
        vector<ld> p(n);
        vector<vector<ld>> dp(n+1,vector<ld>(n+1));
        rep(i,n) cin>>p[i];
        dp[0][0]=1.0;
        loop(i,1,n+1){
            dp[i][0]=dp[i-1][0]*(1-p[i-1]);
            loop(j,1,n+1){
                dp[i][j]=dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1];
            }
        }
        // for(auto i:dp){ for(auto i2:i) cerr<<i2<<' '; cerr<<endl;}
        ld ans=0.0;
        loop(j,(n+1)/2,n+1) ans+=dp[n][j];
        cout<<fixed<<setprecision(20)<<ans<<endl;


        
    // }
    cerr<<"Time Elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" sec";
    return 0;
}

Measured memory_bytes: 141056
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut av = vec![0i32; n];
    for i in 0..n - 1 {
        av[i] = read(&mut stdin_lock, &mut buf, b' ');
    }
    av[n - 1] = read(&mut stdin_lock, &mut buf, b'\n');

    let mut ans = 0;
    for i in 0..n {
        ans += av[i] - 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
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 (a>b) { a=b; return 1; } return 0; }
template<typename T> void remove(T & vector, unsigned int index){vector.erase(vector.begin() + index);}

#define MAX_N 1000000
int prime[MAX_N]; //i番目の素数
bool is_prime[MAX_N+1]; //is_prime[i]==true->iはprime

//n以下の素数の数を返す
void sieve(int n) {
    int p = 0;
    rep(i,n+1) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    rep2(i,n+1) {
        if(is_prime[i]) {
            prime[p++] = i;
            for(int j = 2 * i; j<= n; j+= i) is_prime[j] = false;
        }
    }
    return ;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	sieve(1000000);
	int X; cin >> X;
	while(!is_prime[X]) X++;
	cout << X << endl;
    
}



Measured memory_bytes: 1536
// AtCoder DP Educational Contest
// C - Vacation

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); i++)
#define trav(a, x) for(auto a : x)
#define all(x) x.begin(), x.end()
#define INF (int) 1e9
#define sz(x) (int)(x).size()
#define ri(x) scanf("%d", &x)
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef queue<int> qi;

#define MAXN (int) 1e5 + 1

int n, dp[MAXN][3];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;

    FOR (i, 1, n+1) {
        int a, b, c;
        cin >> a >> b >> c;
        
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a;
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b;
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c;
    }
    
    int *res = max_element(dp[n], dp[n] + 3);
    cout << *res << '\n';

    return 0;
}

Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

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

ll lcm(ll a,ll b){
    a / gcd(a,b) * b;
}
const ll mod = 1e9 + 7;
const ll INF = 1e9 + 7;

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


/////////////////////////////////////////////////////////////////////////////////////////

int main(){
    string s;
    int64_t k;
    cin >> s >> k;
    char ans;
    for (int i = 0;i < k;i++){
        if (s[i] == '1'){
            ans = '1';
            continue;
        }
        else {
            ans = s[i];
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int A[2000001];
int B[2000001];
int C[10001];

void csort(int[],int[],int,int);

int main(){
  int k=0,n,i;

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

  csort(A,B,k,n);
  
  for(i=1;i<=n;i++){
    printf("%d",B[i]);
    if(i<n){
      printf(" ");
    }
  }
  printf("\n");
  return 0;
}

void csort(int A[],int B[],int k,int  n){
  int i,j;
  for(i=0;i<=k;i++){
    C[i]=0;
  }
  for(j=1;j<=n;j++){
    C[A[j]]++;
  }
  for(i=1;i<=k;i++){
    C[i]=C[i]+C[i-1];
  }
  for(j=n;j>=0;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
}

Measured memory_bytes: 16268
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
  int h,w;
  cin>>h>>w;
  int c[10][10],cost[10][10];
  rep(i,10)rep(j,10){
    cin>>c[i][j];
    cost[i][j]=c[i][j];
  }
  int a;
  rep(k,10){
    rep(i,10){
      rep(j,10){
	cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
      }
    }
  }
  int sum=0;
  rep(i,h){
    rep(j,w){
      cin>>a;
      if(a!=-1){
	sum+=cost[a][1];
      }
    }
  }
  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}
template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}
template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) {
    is >> p.first >>p.second ;
    return is;
}
template <class T>istream& operator>>(istream& is,  vector<T>& v) {
    rep(i, v.size()) {
        is >> v[i];
    }
    return is;
}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
    ll n;
    cin >>n;
	V a(50,49LL+n/50);
	n %= 50;
	int win= 51-n;
	int lose= -n;
	for (int i = 0; i < n;i++){
		a[i] += win;
	}
	for (int i = n; i < 50;i++){
		a[i] += lose;
	} 
    cout << a.size() << endl;
	rep(i, a.size()) { cout << a[i];
    if(i!=49){
		cout << " ";
	} }
	cout << endl;
}

/*
50 ... 49*50 min

pre: 49*50 + k?
last: 49 49 49 ...49
last-1: 99 48 48 48 ... 48
last-2 : 98 98 47 47 ... 47   (47* 50 + (98-47)*2)    ((50-n)*50 + (a)*n)= 50*50 -50*n + an    = 49*50 + n

50 50 .. 50 ... (50)
100 49 49 .. 49 (51)
*/

Measured memory_bytes: 3580
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int
main (
  int   argc,
  char *argv[ ]
  )
{
  int i, j;

  for ( ; ; )
  {
    char s[ 128 ];
    char o;

    scanf ( " %s %c", s, &o );
    if ( o == 'X' ) break ;

    s[ 0 ] = tolower ( s[ 0 ] );
    j = 0;
    for ( i = 0; s[ i ] != '\0'; ++i )
    {
      if ( s[ i ] == '_' )
        s[ j++ ] = toupper ( s[ ++i ] );
      else
        s[ j++ ] = s[ i ];
    }
    s[ j ] = '\0';

    if ( o == 'U' )
    {
      s[ 0 ] = toupper ( s[ 0 ] );
      puts ( s );
    }
    else if ( o == 'L' )
    {
      puts ( s );
    }
    else
    {
      for ( i = 0; s[ i ] != '\0'; ++i )
      {
        if ( isupper ( s[ i ] ) )
          printf ( "_%c", tolower ( s[ i ] ) );
        else
          putchar ( s[ i ] );
      }
      puts ( "" );
    }
  }

  return ( EXIT_SUCCESS );
}

Measured memory_bytes: 564
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
int main()
{
	int n,k,a[100005],d[100005],mins=1e9;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	sort(a,a+n);
	for(int i=k-1;i<n;i++)
	{
		int t=a[i]-a[i-k+1];
		mins=min(mins,t);
		if(mins==0)break;
	}
	cout<<mins<<endl;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>

using namespace std;

const int MAX_Q = 200000;
const int MAX = 100001;
int n, q;
string s, t[MAX_Q], d[MAX_Q];



bool left(int i){
  if(i == 0) return true;
  if(i == n + 1) return false;
  for(int j = 0; j < q; j++){
    if(t[j][0] == s[i - 1]){
      if(d[j] == "R") ++i;
      else --i;
    }
    if(i == n + 1) return false;
    if(i == 0) return true;
  }
  return false;
}

bool right(int i){
  if(i == n + 1) return true;
  if(i == 0) return false;
  for(int j = 0; j < q; j++){
    if(t[j][0] == s[i - 1]){
      if(d[j] == "R") ++i;
      else --i;
    }
    if(i == 0) return false;
    if(i == n + 1) return true;
  }
  return false;
}

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

  cin >> n >> q;
  cin >> s;
  for(int i = 0; i < q; i++){
    cin >> t[i] >> d[i];
  }

  int low = 0, high = n + 1;
  while(high - low > 1){
    int mid = (low + high) / 2;
    if(left(mid)) low = mid;
    else high = mid;
  }
  int left = high;

  low = 0, high = n + 1;
  while(high - low > 1){
    int mid = (low + high) / 2;
    if(right(mid)) high = mid;
    else low = mid;
  }
  int right = high;

  int ans = (right - left);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 22420
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
#define rep(i,a,b) for(int (i)=a;(i)<(int)(b);(i)++)
using ll = long long int ;

int gcd(ll a, ll b){
    int tmp;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    if(b==0) return a;
    else return gcd(b, a%b);
}

int main(){
    ll K,sum=0;
    cin >> K;   
    for(ll a=1;a<=K;a++){
        for(ll b=1;b<=K;b++){
            for(ll c=1;c<=K;c++){
                sum += gcd(a,gcd(b,c));
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3636
N, M = map(int, input().split())
kss = []
for i in range(M):
    tmp = list(map(int, input().split()))
    k = tmp[0]
    s = tmp[1:]
    kss.append([k, s])
ps = list(map(int, input().split()))

def check_on(s_all, s, p):
    oncnt = 0
    for i in s:
        if s_all[i]:
            oncnt += 1
    if oncnt % 2 == p:
        return True
    else:
        return False

def check_all_on(s_all, kss, ps):
    for i in range(M):
        s = kss[i][1]
        p = ps[i]
        if not check_on(s_all, s, p):
            return False
    return True


def rec(s_all, kss, ps, cnt):
    if len(s_all) == N+1:
        if check_all_on(s_all, kss, ps):
            cnt[0] += 1
            return
    else:
        s_all.append(0)
        rec(s_all, kss, ps, cnt)
        s_all.pop()

        s_all.append(1)
        rec(s_all, kss, ps, cnt)
        s_all.pop()

s_all = [0]
cnt = [0]
rec(s_all, kss, ps, cnt)
print(cnt[0])


Measured memory_bytes: 3188
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, P[5050];

i64 modpow(i64 a, i64 p = MOD - 2)
{
	if (p == 0) return 1;
	i64 t = modpow(a, p / 2);
	t = t * t % MOD;
	if (p & 1) t = t * a % MOD;
	return t;
}

int uf[5050];
int root(int p)
{
	return uf[p] < 0 ? p : (uf[p] = root(uf[p]));
}
bool join(int p, int q)
{
	p = root(p); q = root(q);
	if (p == q) return false;
	uf[p] += uf[q];
	uf[q] = p;
	return true;
}

i64 dp[5050][5050];
i64 dpow[5050], dpowi[5050];
i64 fact[5050], facti[5050];

i64 Comb(int a, int b)
{
	if (b < 0 || a < b) return 0;
	return fact[a] * facti[b] % MOD * facti[a - b] % MOD;
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", P + i);
		if (P[i] != -1) --P[i];
	}
	for (int i = 0; i < N; ++i) uf[i] = -1;

	dpow[0] = dpowi[0] = 1;
	for (int i = 1; i <= N; ++i) {
		dpow[i] = dpow[i - 1] * (N - 1) % MOD;
		dpowi[i] = modpow(dpow[i], MOD - 2);
	}

	fact[0] = facti[0] = 1;
	for (int i = 1; i <= N; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
		facti[i] = modpow(fact[i], MOD - 2);
	}
	int cyc = 0;
	for (int i = 0; i < N; ++i) if (P[i] != -1) {
		if (!join(i, P[i])) ++cyc;
	}

	vector<int> leader;
	for (int i = 0; i < N; ++i) if (P[i] == -1) {
		leader.push_back(-uf[root(i)]);
	}
	int nl = leader.size();

	/*
	dp[0][0] = 1;
	for (int i = 0; i < leader.size(); ++i) {
		i64 a = (N - nl) * dpowi[1] % MOD;
		i64 b = (nl - 1) * dpowi[1] % MOD;
		for (int j = 0; j <= N; ++j) if (dp[i][j]) {
			ADD(dp[i + 1][j + 1], a * dp[i][j]);
			ADD(dp[i + 1][j], b * dp[i][j]);
		}
	}

	i64 ave_cyc = 0;
	for (int i = 2; i <= nl; ++i) {
		i64 v = Comb(nl, i);
		if (i != 2) v = v * 2 % MOD;
		v = v * modpow(nl - 1, MOD - 1 - i) % MOD;
		ADD(ave_cyc, v);
	}

	i64 ret = 0;
	for (int i = 0; i <= N; ++i) if (dp[nl][i] != 0) {

	}
	ret = ret * dpow[nl] % MOD;
	printf("%lld\n", ret);
	*/

	i64 ave_cyc = cyc;
	// self cycle
	for (int i = 0; i < nl; ++i) {
		ADD(ave_cyc, (leader[i] - 1) * dpowi[1]);
	}
	dp[0][0] = 1;
	for (int i = 0; i < nl; ++i) {
		for (int j = 0; j <= N; ++j) if (dp[i][j] != 0) {
			ADD(dp[i + 1][j], dp[i][j]);
			ADD(dp[i + 1][j + 1], dp[i][j] * leader[i]);
		}
	}
	for (int i = 2; i <= nl; ++i) {
		ADD(ave_cyc, dp[nl][i] * dpowi[i] % MOD * fact[i - 1]);
	}
	ave_cyc = N - ave_cyc + MOD;
	ave_cyc %= MOD;
	printf("%lld\n", ave_cyc * dpow[nl] % MOD);
	return 0;
}


Measured memory_bytes: 120756
n = int(input())
aa = [1]
ac = [1]
ag = [1]
cc = [1]
cg = [1]
ca = [1]
gc = [1]
ga = [1]
gg = [1]
at = [1]
gt = [1]
t = [2]
ta = [1]
tc = [1]
tg = [1]
mod = 10**9 + 7
for i in range(n-2):
    ac.append((ca[i]+ta[i]+aa[i])%mod)
    ag.append((ca[i]+ga[i]+ta[i]+aa[i])%mod)
    cg.append((cc[i]+gc[i]+tc[i])%mod)
    aa.append((ca[i]+aa[i]+ga[i]+ta[i])%mod)
    cc.append((ac[i]+cc[i]+gc[i]+tc[i])%mod)
    ca.append((ac[i]+cc[i]+gc[i]+tc[i])%mod)
    if i > 0:
        gc.append((cg[i]+gg[i]+tg[i]-ag[i-1]-at[i-1])%mod)
    else:
        gc.append((cg[i]+gg[i]+tg[i])%mod)
    ga.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    gg.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    at.append((ca[i]+ga[i]+ta[i]+aa[i])%mod)
    gt.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    t.append((ac[i]+cc[i]+gc[i]+tc[i]+t[i]+at[i]+gt[i])%mod)
    ta.append(t[i]+at[i]+gt[i])
    if i > 0:
        tc.append(t[i]+at[i]+gt[i]-ag[i-1])
    else:
        tc.append(t[i]+at[i]+gt[i])
    tg.append(t[i]+at[i]+gt[i])
ans = 0
ans = (aa[n-2]+ac[n-2]+ag[n-2]+cc[n-2]+cg[n-2]+ca[n-2]+gc[n-2]+ga[n-2]+gg[n-2]+t[n-2]+ta[n-2]+tc[n-2]+tg[n-2]+at[n-2]+gt[n-2])%mod
print(ans)

Measured memory_bytes: 3192
#include <stdio.h>

int main(){

	int N,Y;

	scanf("%d %d",&N,&Y);

	int i,j,k;

	for(i=0;i<=N;i++){
		for(j=0;j<=N;j++){
			if(i+j<=N){
			k=N-(i+j);
			if((10000*i)+(5000*j)+(1000*k)==Y){
				printf("%d %d %d\n",i,j,k);
				return 0;
			}
			}
		}
	}

	printf("-1 -1 -1\n");

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(void){
    int A=0;
    int B=0;
    cin >> A >> B;
    
    if (max(A+B,A+A-1)<(B+B-1)) cout << B+B-1 << endl;
    else cout << max(A+B,A+A-1) << endl;

}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
#define llMAX 9223372036854775807LL
#define llMIN -9223372036854775808LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  
  // エラトステネスのふるい
  ll MAX = 1010100LL;
  ll ans=0;
  cin >> n ;

  vi a(MAX);



  vector<ll> is_prime(MAX, 1);
  is_prime[0] = 0, is_prime[1] = 0;
  for (ll i = 2; i < MAX; ++i) {
      if (!is_prime[i]) continue;
      for (ll j = i*2; j < MAX; j += i) is_prime[j] = 0;
  }



  //a(MAX)
  ll nn=n;
  for(ll i=0;i<MAX;i++){
      if (is_prime[i]==1){
        //nn=n;
        ll ii=i;
        ll j=0;
        for(j=0;j<64;j++){
          if (nn%ii==0){
            nn/=ii;
          }else{
            break;
          }
        }
        a[i]=j;
      }
  }



  ans=0;
  for(ll i=0;i<MAX;i++){
    if (a[i]!=0){
      for(ll j=1;j<64;j++){
        a[i]-=j;
        if (a[i]>=0)ans++;
        if (a[i]<0)break;
      }
    }
  }


  if (nn!=1){
    ans++;
  }


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


Measured memory_bytes: 19096
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define REP(i, N) for(int i = 0; i < N; i++)

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());
    if (s < t) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

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

using namespace std;

const int N = 310;
double dp[N][N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(9);

    int n;
    cin >> n;
    array<int, 4> cnt {};
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        ++cnt[a];
        sum += a;
    }

    for (int s = 1; s <= sum; ++s) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= n; ++k) {
                int i = s - 2 * j - 3 * k;
                if (i < 0 || i > n) continue;
                dp[i][j][k] = n;
                if (i > 0) dp[i][j][k] += i * dp[i - 1][j][k];
                if (j > 0) dp[i][j][k] += j * dp[i + 1][j - 1][k];
                if (k > 0) dp[i][j][k] += k * dp[i][j + 1][k - 1];
                dp[i][j][k] /= (i + j + k);
            }
        }
    }

    cout << dp[cnt[1]][cnt[2]][cnt[3]] << endl;

    return 0;
}


Measured memory_bytes: 227584
#include<stdio.h>

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

    scanf("%d %d %d", &a, &b, &c);
    int swap;
    swap = b;
    b = a;
    a = swap;

    swap = c;
    c = a;
    a = swap;

    printf("%d %d %d \n", a,b,c);

    return 0;
}

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

using namespace std;

struct line {
    long long m,b;
    line() {}
    line(long long _, long long __) {
        m = _, b = __;
    }
    long long eval(long long x) {
        return m * x + b;
    }
};

struct cht {
    vector<line> trick;
    cht() { pos = 0;}
    int pos;
    bool irrelevant(line l1, line l2, line l3) {
        return  (l3.b - l1.b) * (l1.m - l2.m) < (l2.b - l1.b) * (l1.m - l3.m);
    }
    
    void add(line l) {
        while(trick.size() >= 2 
          and irrelevant(trick[trick.size() - 2], trick[trick.size() - 1], l))
            trick.pop_back();
        trick.push_back(l);
    }
    long long query(long long x) {
        if(pos >= (int)trick.size()) pos = trick.size() - 1;
        while(pos + 1 < (int)trick.size() 
                and trick[pos + 1].eval(x) < trick[pos].eval(x))
            pos++;
        return trick[pos].eval(x);
    }
};
 
int n;
long long c;
long long h[1000010];

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

    for (int i = 0; i < n; ++i)
        scanf("%lld", h + i);
    
    cht dp;
    
    dp.add(line(-2 * h[0], h[0] * h[0]));

    long long cur = 0;
    for (int i = 1; i < n; ++i) {
        cur = dp.query(h[i]) + h[i] * h[i] + c;
        dp.add(line(-2*h[i], h[i] * h[i] + cur));
    }
    cout << cur << "\n";

    return 0;
}


Measured memory_bytes: 8048
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt(), y = sc.nextInt();
		sc.close();
		long ans = -1;
		if (x % y != 0) {
			ans = (long)x;
		}
		System.out.println(ans);
	}

}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 10000000000
#define MAX 1000010
#define MOD 1000000007
  
using ll = long long;
using Graph = vector<vector<pair<ll,ll>>>;

ll N,X;
vector<ll> P;
vector<ll> A;

ll f(ll level, ll x){
  if(level==0)return 1;
  if(x==A.at(level))return P.at(level);
  else if(A.at(level-1)+3<=x&&x<=A.at(level)-1){
    return P.at(level-1)+1+f(level-1,x-2-A.at(level-1));
  }else if(x==A.at(level-1)+2)return P.at(level-1)+1;
  else if(x>1)return f(level-1,x-1);
  else return 0;
}

int main(){
  cin>>N>>X;
  P.resize(N+1,0);
  A.resize(N+1,0);
  P.at(0)=1;
  A.at(0)=1;
  rep1(i,N+1)P.at(i)=2*P.at(i-1)+1;
  rep1(i,N+1)A.at(i)=A.at(i-1)*2+3;
  cout<<f(N,X)<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int data[200000];
int main()
{
	int n,i,c=0,j=1;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&data[i]);
	}
	for(i=0;i<n;i++)
	{
		if(data[i]==j)
		{
			c++;
			j++;
		}
	}
	if(c==0) printf("-1");
	else printf("%d",n-c);
	return 0;
}

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

using namespace std;
using ll = long long;

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

  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  for (int i = 0; i < n; i++)
    cin >> p[i];

  sort(p.begin(), p.end());
  int sum = 0;
  for (int i = 0; i < k; i++) {
    sum += p[i];
  }
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 3636