akhauriyash/Code-Regression huggingface dataset:
let query ac = 
  Scanf.scanf " %d %d" (fun l' r' -> (
    let l = l' - 1 in
    let r = r' - 1 in
    ac.(r) - ac.(l) |> string_of_int |> print_endline
  ))
;;

let () = Scanf.scanf "%d %d\n%s" (fun n q s -> (
  let ac = Array.init (n + 1) (fun i -> if i = n || i = 0 || s.[i - 1] <> 'A' || s.[i] <> 'C' then 0 else 1) in (
    Array.iteri (fun i e -> if i > 0 then ac.(i) <- ac.(i - 1) + e) ac;
    for i = 1 to q do
      query ac
    done
  )
))

Measured memory_bytes: 8064
# ALDS1_3_D.

def show(a):
    # 配列の中身を出力する。
    _str = ""
    for i in range(len(a) - 1):
        _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def main():
    data = list(input())
    a = []  # '\\'の位置を格納していく。
    b = []  # 同じだが、池の集約に使う。
    ponds = []  # 池の面積のリスト(必要に応じて集約).
    Area = 0  # 総面積
    N = len(data)
    for i in range(N):
        if data[i] == '\\':
            a.append(i); b.append(i)
        elif data[i] == '/':
            if len(a) == 0: continue
            else:
                left = a.pop()  # '/'と対になる'\\'の位置
                Area += i - left
                ponds.append(i - left)
                # leftより右にあるbの元を先頭から見てあればカット、
                # その分だけpondsを集約する。
                while left < b[len(b) - 1]:
                    b.pop()
                    x = ponds.pop(); y = ponds.pop(); ponds.append(x + y)
    print(Area)
    ponds.insert(0, len(ponds))
    show(ponds)
    
if __name__ == "__main__":
    main()


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

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<ll> a(n);
  ll x = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    x ^= a[i];
  }
  for (int i = 0; i < n; i++) {
    cout << (x ^ a[i]) << " ";
  }
  cout << "\n";
  return 0;
}


Measured memory_bytes: 4768
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int r=n%10;
    if(r==2 || r==4 || r==5 || r==7 ||r==9)
        cout<<"hon"<<endl;
    else if(r==3)
        cout<<"bon"<<endl;
    else
        cout<<"pon"<<endl;
}


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

int main() {

  long long int n, k;
  cin >> n >> k;

  long long int a;

  for ( long long int i = 0; i < n; i++ ) {

    long long int in;
    cin >> in;

    if ( in == 1 ) a = i;

  }

  if ( n == k ) {
    cout << 1 << endl;
    return 0;
  }
  n--;
  k--;
  if ( ( n % k ) == 0 ) {
    cout << n / k << endl;
  } else {
    cout << n / k + 1 << endl;
  }

  return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
using namespace std;


int main()
{
	char str[1001];
	int sum;

	while (1) {
		scanf("%s", &str);
		sum = 0;
		if (str[0] == '0')break;
		for (int i = 0; i < strlen(str); i++) {
			sum += (str[i] - '0');
		}
		cout << sum << endl;
	}
	return 0;
}


Measured memory_bytes: 3168
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

class branch{
  int to;
  branch(int to){
    this->to = to;
  }
};

int main(){
  int n; cin >> n;
  vector<branch> graph[n+1];
  int g[n+1][n+1];
  memset(g, 0, sizeof(g));

  int v, k, to;
  for(int i=0; i<n; i++){
    cin >> v;
    cin >> k;
    for(int j=0; j<k; j++){
      cin >> to;
      g[v][to]=1;
    }
  }

  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      cout << g[i][j];
      if(j!=n) cout << " ";
    }
    cout << endl;
  }

  return 0;
}



Measured memory_bytes: 3128
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <complex>
#include <set>
#include <list>
#include <iomanip>
#include <map>
#include <memory.h>



using namespace std;
static const double EPS = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a,0,sizeof(a))
#define minus(a) memset(a,0xff,sizeof(a))
#define chmax(a,b) a=min((a),(b))
#define chmin(a,b) a=max((a),(b))


#define MOD 1000000007

typedef pair<int,int>P;
#define INF (1<<29)
 
struct edge { 
	int from, to; 
	edge (int from, int to){
		this->from=from; this->to=to;
	}
};
 
int V,E;
typedef vector<edge> edges;
vector<edges> G;

int n;
string s;
string ans;
char anim[2] = { 'S','W' };

char nextch(char cur, char left, char a) {
	if ((cur == 'S'&& a == 'o') || (cur == 'W'&& a == 'x'))
		return left;

	if ((cur == 'S'&& a == 'x') || (cur == 'W'&& a == 'o'))
		return left=='S'?'W':'S';

}

bool check(char cur, char left, char right, char a) {
	if ((cur == 'S' && a == 'o') || (cur=='W' && a=='x')) {
		return left == right;
	}
	if ((cur == 'S' && a == 'x') || (cur == 'W' && a == 'o')) {
		return left != right;
	}
}

bool go(char a, char b) {
	ans.clear();
	ans.resize(s.size());
	ans[0] = a; ans[1] = b;
	FOR(i, 2, n-1) {
		ans[i]=nextch(ans[i - 1], ans[i - 2], s[i - 1]);
	}
	bool flg = check(ans[0], ans[n - 1], ans[1], s[0]);
	flg = flg & check(ans[n - 1], ans[n - 2], ans[0], s[n - 1]);
	return flg;
}

int main(){
	cin >> n >> s;
	ans.resize(s.size());
	
	rep(i, 2) {
		rep(j, 2) {
			if (go(anim[i], anim[j])) {
				rep(k, ans.size()) {
					cout << ans[k];
				}
				cout << endl;
				return 0;
			}
		}
	}
	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 640
/*input
3 5
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}

//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}

int main()
{
	IOS;
	int  n;
	cin>>n;
	int a[25];
	REP(i,n)cin>>a[i];
	int ans=0;
	REP(i,n){
		bool f=1;
		for(int j=0;j<i;j++) if(a[i]<a[j]) f=0;
		ans+=f;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    int a[n];
    for(int i=1;i<n;i++)
        cin>>a[i];
    n=n-1;
    long long sum=a[1]+a[n];
    for(int i=2;i<=n;i++)
        sum+=min(a[i],a[i-1]);
    cout<<sum<<endl;

}


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

constexpr long long MOD = 1'000'000'007;

class binomial_coefficients {
	long long MAX_VAL;
	vector<long long> fac, mmi;

public:

	binomial_coefficients(){
	}
	
	binomial_coefficients(long long num){
		init(num);
	}
	
	~binomial_coefficients(){
		
	}
	
	void init(long long num){
		MAX_VAL = num+1; 
		fac.resize(MAX_VAL);
		mmi.resize(MAX_VAL);
		
		factorial_mod();
		modular_multiplicatibe_inverse();
	}
	
	void factorial_mod(){
		 fac[0] = 1;
		for(long long i = 1; i < MAX_VAL; fac[i] %= MOD, i++)
			fac[i] = fac[i - 1] * (i % MOD);
	}
	
	long long power(long long x, long long n){
		long long ans = 1;
		for(;n;n >>= 1, x *= x, ans %= MOD, x %= MOD)
			if(n&1)ans*=x;
		return ans % MOD;
	}
	
	void exgcd(long long a, long long b, long long &x, long long &y){
		if(b == 0){
			x = 1;
			y = 0;
			return ;
		}
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
	
	void modular_multiplicatibe_inverse(){
		long long x, y;  
		exgcd(fac[MAX_VAL - 1], MOD, x, y);
		mmi[MAX_VAL-1] = (x % MOD + MOD) % MOD;
		// mmi[MAX_VAL-1] = power(fac[MAX_VAL-1], MOD-2);
		for(long long i = MAX_VAL - 2; i >= 0; mmi[i]%=MOD, i--)
			mmi[i] = mmi[i + 1] * ((i + 1) % MOD);
	}
	
	long long combination(long long n, long long r){
		return r < 0 ? 0 :n < r ? 0 :fac[n] * (mmi[r] * mmi[n-r] % MOD) % MOD;
	}
};


int main(){
	
	long long n, k;
	long long ans = 0;
	binomial_coefficients bc;
	vector<vector<long long>> dp;
	
	cin>>n>>k;
	
	bc.init(n+k);
	
	dp.resize(n+1, vector<long long>(k+1));
	
	dp[0][0] = 1;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++){
			dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1];
			dp[i][j] %= MOD;
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++){
			dp[i][j] += dp[i][j-1];
			dp[i][j] %= MOD;
		}
	}
	
	ans = dp[n][k];
	
	cout<<ans<<endl;
}


Measured memory_bytes: 10728
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int w = in.nextInt();
		int h = in.nextInt();
		int x = in.nextInt();
		int y = in.nextInt();
		int r = in.nextInt();
		String result = "Yes";
		
		if ((x < 0) || (y < 0)) {
			result = "No";
		} else if ((w < (x + r)) || (h < (y + r))) {
			result = "No";
		}

		System.out.println(result);
	}
}

Measured memory_bytes: 26248
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        int[] east;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            String word = in.next();
            east = new int[N];

            for (int i = 0; i < N; i++) {
                if (i == 0) {
                    east[i] = word.charAt(0) == 'E' ? 1 : 0;
                } else {
                    east[i] = east[i - 1] + (word.charAt(i) == 'E' ? 1 : 0);
                }
            }

            int ans = Integer.MAX_VALUE;

            for (int i = 0; i < N; i++) {
                ans = Math.min(ans, sum(0, i - 1, true) + sum(i + 1, N - 1, false));
            }
            out.println(ans);
        }

        private int sum(int start, int end, boolean toEast) {
            if (start > end) return 0;
            int len = end - start + 1;
            if (start == 0) {
                return !toEast ? east[end] : (len - east[end]);
            }
            return !toEast ? (east[end] - east[start - 1]) : (len - (east[end] - east[start - 1]));
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 27860
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int n, a = 0, b = 0; string s, ss; cin >> n;
	for (int h = 1; h <= n; h++) {
		cin >> s >> ss;
		if (s > ss) {
			a += 3;
		}
		else if(s < ss) {
			b += 3;
		}
		else {
			a++; b++;
		}
	}
	cout << a << ' ' << b << endl;
	cin >> n;
}


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

int main(){
  int k,a,b;
  cin >> k >> a >> b;
  if (a%k==0){
    cout << "OK\n";
  }else if (b >= a + k - a%k){
    cout <<"OK\n";
  }else{
    cout <<"NG\n";
  }
  return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        String S = sc.next();

        if(K==1){
            S= new String(S.charAt(K-1)+"").toLowerCase() + S.substring(K);
        }else{
            S= S.substring(0,K-1) + new String(S.charAt(K-1)+"").toLowerCase() + S.substring(K);
        }


        System.out.println(S);


    }

}


Measured memory_bytes: 21844
def main():
    s = input()
    t = input()
    
    s = s.replace('?','.')
    import re
    for i in range(len(s)-len(t),-1,-1):
        if re.match(s[i:i+len(t)],t):
            s = s.replace('.','a')
            print(s[:i]+t+s[i+len(t):])
            return 0
    print('UNRESTORABLE')
 
if __name__ == '__main__':
    main()


Measured memory_bytes: 38348
#include<cstdio>
using namespace std;
int main(){
  int h,w,r[500][500]={},g[500][500]={};
  char a[501][501];
  scanf("%d %d",&h,&w);
  for(int i=0;i<h;i++)
    scanf("%s",a[i]);
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      if(j==0)
        r[i][j]=1;
      else if(j==w-1)
        g[i][j]=1;
      else if(i%2==0)
        r[i][j]=1;
      else
        g[i][j]=1;
    }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='#'||r[i][j])
        printf("#");
      else
        printf(".");
    }
    printf("\n");
  }
  printf("\n");
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='#'||g[i][j])
        printf("#");
      else
        printf(".");
    }
    printf("\n");
  }
}

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

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 

void solve(){
    int n;
    cin >> n;
    map<string,llint>mp;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    llint ans=0;
    for(auto &p:mp){
        llint x=p.second;
        ans+=x*(x-1)/2;
    }
    cout << ans << endl;

}

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


Measured memory_bytes: 11136
N = input()
dic = {}
max = 0
for i in range(int(N)):
  word = input()
  if word not in dic.keys():
    
    if max == 0:
      max += 1
    dic[word] = 1
    
  else:
    
    if max == dic[word]:
      max += 1
    dic[word] += 1

candidates = sorted([word for word in dic.keys() if dic[word] == max])
for word in candidates:
  print(word)


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

int main() {
	int H, W;
	cin >> H >> W;
	string S[H];
	for (int i=0; i<H; i++){
	    cin >> S[i];
	}
	for (int i=0; i<H; i++){
	    cout << S[i] << endl;
	    cout << S[i] << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define int long long
  #define endl "\n"
  #define all(v) v.begin(),v.end()
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<< ": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  const int N = 200005;


int32_t main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    IOS
    int d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d)
        cout<<"Yes \n";
    else
        cout<<"No \n";
    return 0;
}

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

int main() {
  
  int N;
  cin >> N;
  vector<long int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A.at(i);
  }
  int out1 = 0;
  int out2 = 0;
  for(int i = 0; i < N - 1; i++){
    if(A.at(i) >= A.at(i + 1)){
      out1++;
    }else{
      if(out1 > out2){
        out2 = out1;
      }
      out1 = 0;
    }
    if(i == N - 2){
      if(out1 > out2){
        out2 = out1;
      }
    }
  }
  cout << out2;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
class ModInt {
  static int MOD;
  long long x;

 public:
  static void mod(int m) { MOD = m; }

  ModInt(long long v = 0) : x(v % MOD) {
    if (x < 0) x += MOD;
  }

  ModInt& operator+=(const ModInt& r) {
    x += r.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }

  ModInt& operator-=(const ModInt& r) {
    x -= r.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    x = (x * r.x) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; }
  ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; }
  ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; }
  ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; }
  bool operator==(const ModInt& r) const { return x == r.x; }
  bool operator!=(const ModInt& r) const { return x != r.x; }

  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(long long n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.x; }

  friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; }

  int getMod() { return MOD; }

  long long val() { return x; }
};
int ModInt::MOD = 1000000007;

int N;
vector<int> C;

int main() {
  cin >> N;
  C.resize(N);
  rep(i, N) cin >> C[i];
  sort(all(C));

  ModInt ans = 0;
  rep(i, N) { ans += ll(N + 1 - i) * C[i]; }
  ans *= ModInt(2).pow(2 * N - 2);
  cout << ans << endl;

  return 0;
}


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

int main(void){
  int n;
  int id,m1,s1,m2,s2,m3,s3,m4,s4;
  int t;
  while(1){
    cin>>n;
    if(n==0)break;
    map<int,int> d;
    vector<int> v;
    for(int i=0;i<n;i++){
      cin>>id>>m1>>s1>>m2>>s2>>m3>>s3>>m4>>s4;
      t=60*(m1+m2+m3+m4)+s1+s2+s3+s4;
      v.push_back(t);
      d[t]=id;
    }
    sort(v.begin(),v.end());
    cout<<d[v[0]]<<endl;
    cout<<d[v[1]]<<endl;
    cout<<d[v[v.size()-2]]<<endl;
  }
  return 0;
}



Measured memory_bytes: 3344
n=int(input())
a=[int(input()) for i in range(n)]
cnt=0
button=0
flag=False
#ボタン1が最初光っている(インデックスは0)
for i in range(n):
    #ボタンを押す
    cnt+=1
    button=a[button]-1
    if button==1:
        flag=True
        break
if flag:
    print(cnt)
else:
    print(-1)

Measured memory_bytes: 13060
while True:
    h,w=map(int,input().split())
    if ([w,h]==[0,0]):
        exit()
    for i in range(h):
        if (i % 2 == 0):
            print('#.'*(w//2) + '#'*(w%2))
        else:
            print('.#'*(w//2) + '.'*(w%2))
    print()


Measured memory_bytes: 5616
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)

class E {
  public:
    int in;
    vector<int> path;
    char c;
};

int const N_MAX = 52;
ll const MOD = 1000000007;

int N;
string S1, S2;
string ss[2];
vector<E> G[N_MAX + 1];
map<int, bool> used;

int main() {
  scanf("%d", &N);
  cin >> S1 >> S2;
  ss[0] = S1;
  ss[1] = S2;

  rep(j, N) {
    rep(i, 2) {
      int s = ss[i][j];
      if (G[s].empty()) {
        E e;
        e.in = 0;
        e.c = s;
        G[s].push_back(e);
      }

      if (i == 0) {
        int x = ss[1][j];
        if (s != x && G[x].empty()) {
          G[s][0].path.push_back(x);
        }
      }
      if (j + 1 < N) {
        int y = ss[i][j + 1];
        if (s != y && G[y].empty()) {
          if (i == 1 && s == ss[0][j] && y == ss[0][j + 1]) continue;

          G[s][0].path.push_back(y);
        }
      }
      if (i == 0 && j > 1) {
        int b = ss[i][j - 1];
        if (s != b) continue;
        int za = ss[1][j - 1];
        int zb = ss[1][j];
        if (za != zb) continue;
        int zc = ss[0][j - 2];
        int zd = ss[1][j - 2];
        if (zc == zd) continue;
        G[s][0].in--;
      }
    }
  }

  queue<E> Q;
  int s = ss[0][0];
  Q.push(G[s][0]);
  used[s] = true;
  while (!Q.empty()) {
    E e = Q.front();
    Q.pop();
    if (e.path.empty()) continue;

    for (int x : e.path) {
      G[x][0].in++;

      if (used[x]) continue;
      used[x] = true;
      Q.push(G[x][0]);
    }
  }

  used.clear();
  ll colors = 1;
  Q.push(G[s][0]);
  used[s] = true;
  while (!Q.empty()) {
    E e = Q.front();
    Q.pop();

    colors = colors * (3 - e.in) % MOD;

    for (int x : e.path) {
      if (used[x]) continue;

      used[x] = true;
      Q.push(G[x][0]);
    }
  }
  printf("%lld\n", colors);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
map<string, int> mem;

int main(){
    ll n, mx = 0;
    cin >> n;
    string s[n], a;
    for(int i = 0; i < n; ++i){
        cin >> s[i];
        mem[s[i]] += 1;
    }
    for(const auto& i : mem){
        int j = i.second;
        if(j > mx){
            mx = j;
        }
    }
    for(const auto& i : mem){
        if(i.second == mx)
            cout << i.first << endl;
    }
    return 0;
}


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

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll> Pll;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

ll dp[10010][110];
ll sum[210];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string K;cin>>K;
  ll D;cin>>D;
  ll d=0;
  while(d<10){
    d+=D;
  }
  dp[K.length()][0]=1;
  //debug(d);
  for(ll i=K.length()-1;i>=0;i--){
    sum[0]=dp[i+1][0];
    for(ll j=1;j<2*d;j++){
      sum[j] = (sum[j-1]+dp[i+1][j%D])%MOD;
    }
    //debugArray(sum,D);
    for(ll j=0;j<d;j++){
      dp[i][j] = (sum[j+d]-sum[j-10+d]+MOD)%MOD;
    }
  }
  ll ans = 0;
  sum[0]=0;
  for(ll i=0;i<(ll)K.length();i++){
    ll k=K[i]-'0';
    for(ll j=0;j<k;j++){
      ll n=(d+D-sum[0]-j)%D;
      //debug(n);
      ans = (ans+dp[i+1][n])%MOD;
      //debug(ans);
    }
    sum[0] = (sum[0]+k)%D;
  }
  ans = (ans-1+MOD)%MOD;
  if(sum[0]%D==0){
    ans=(ans+1)%MOD;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std ;
typedef long long int ll ;
#define MXN 100005

int main(){
	ios;
	ll n,m,q,a[MXN],p[MXN];
	cin>>n>>m>>q;
	for(int i=0; i<q; i++)cin>>a[i];
	for(int i=0; i<n; i++)p[i]=m-q;
	for(int i=0; i<q; i++){
		p[a[i]-1]++;
	}
	for(int i=0; i<n; i++){
		if(p[i]>0)cout<<"Yes\n";
		else cout<<"No\n"; 
	} 
	return 0;
}



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

int n;
string a[10],b[10];
string x,y;

int lim;

bool conv(int k){
    string to;
    int cur=0;
    int before=x.size();
    while(cur<x.size()){
        if(cur+a[k].size()<=x.size()&&x.substr(cur,a[k].size())==a[k]){
            to+=b[k];
            cur+=a[k].size();
        }
        else{
            to+=x[cur];
            cur++;
        }
    }
    x=to;
    return before<x.size();
}

bool dfs(int t=0){
    if(x==y)return true;
    if(t==lim)return false;
    if(x.size()>=y.size())return false;

    bool ret=false;
    for(int i=0;i<n;i++){
        string _x=x;
        if(!conv(i))continue;
        ret|=dfs(t+1);
        x=_x;
    }

    return ret;
}

int main(){
    while(cin>>n,n){
        for(int i=0;i<n;i++)cin>>a[i]>>b[i];
        cin>>x>>y;

        for(lim=0;lim<10;lim++)if(dfs())break;
        if(lim==10)cout<<-1<<endl;
        else cout<<lim<<endl;
    }
    return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <stdio.h>

using namespace std;

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

const int C_MAX = 1;

char C[C_MAX + 1];
char Alphabet[27] = "abcdefghijklmnopqrstuvwxyz";
int n = 26;

char searchNext() {
  REP(i, n) {
    if (C[0] == Alphabet[i]) {
      return Alphabet[i + 1];
    }
  }
}

void solve() {
  char ans = searchNext();
  printf("%c\n", ans);
}

void input() {
  scanf("%s", C);
}

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


Measured memory_bytes: 256
using System.Collections.Generic;
using System.Linq;
using System;
using static System.Console;
class E { static void Main() => new J(); }
class J
{
	public const int Inf = 1073741789;
	int[] G() => ReadLine().Split().Select(int.Parse).ToArray();
	public J() { WriteLine(string.Join(" ", Calc())); }
	IEnumerable<int> Calc()
	{
		var N = G()[0];
		var a = G();
		var rev = new int[N];
		var par = new[] { new RMQ(N), new RMQ(N) };
		for (var i = 0; i < N; i++)
		{
			rev[--a[i]] = i;
			par[i & 1][i] = a[i];
			par[1 - (i & 1)][i] = Inf;
		}
		var que = new PriorityQueue();
		var dict = new Dictionary<int, P>();
		Action<P> add = p =>
		{
			var z = par[p.l & 1].Min(p);
			if (z < Inf) { dict[z] = p; que.Enqueue(z); }
		};
		add(new P(0, N));
		while (que.Count > 0)
		{
			int x = que.Dequeue(), i = rev[x];
			var p = dict[x];
			int f = p.l & 1, y = par[1 - f].Min(i + 1, p.r), j = rev[y];
			yield return x + 1;
			yield return y + 1;
			add(new P(p.l, i));
			add(new P(i + 1, j));
			add(new P(j + 1, p.r));
		}
	}
}
struct P
{
	public int l, r;
	public P(int x, int y) { l = x; r = y; }
}
class RMQ
{
	int N2;
	int[] seg;
	public RMQ(int N)
	{
		N2 = 1;
		while (N2 < N) N2 <<= 1;
		seg = new int[2 * N2 - 1];
		for (var i = 0; i < 2 * N2 - 1; i++) seg[i] = J.Inf;
	}
	public void Update(int i, int v)
	{
		i += N2 - 1;
		seg[i] = v;
		while (i > 0)
		{
			i = (i - 1) / 2;
			seg[i] = Math.Min(seg[i * 2 + 1], seg[i * 2 + 2]);
		}
	}
	public int this[int n] { set { Update(n, value); } }
	public int Min(P p) => Min(p.l, p.r);
	public int Min(int from, int to) => Min(from, to, 0, 0, N2);
	int Min(int from, int to, int node, int l, int r)
	{
		if (to <= l || r <= from) return J.Inf;
		else if (from <= l && r <= to) return seg[node];
		else return Math.Min(Min(from, to, 2 * node + 1, l, (l + r) >> 1), Min(from, to, 2 * node + 2, (l + r) >> 1, r));
	}
}
class PriorityQueue
{
	List<int> list = new List<int>();
	public int Count { get; private set; } = 0;
	public void Enqueue(int x)
	{
		var pos = Count++;
		list.Add(x);
		while (pos > 0)
		{
			var p = (pos - 1) / 2;
			if (list[p] <= x) break;
			list[pos] = list[p];
			pos = p;
		}
		list[pos] = x;
	}
	public int Dequeue()
	{
		var value = list[0];
		var x = list[--Count];
		list.RemoveAt(Count);
		if (Count == 0) return value;
		var pos = 0;
		while (pos * 2 + 1 < Count)
		{
			var a = 2 * pos + 1;
			var b = 2 * pos + 2;
			if (b < Count && list[b] < list[a]) a = b;
			if (list[a] >= x) break;
			list[pos] = list[a];
			pos = a;
		}
		list[pos] = x;
		return value;
	}
}

Measured memory_bytes: 46196
import std.stdio, std.string, std.array, std.conv, std.algorithm, std.typecons, std.range, std.container, std.math, std.algorithm.searching, std.functional,std.mathspecial, std.numeric;

void main(){
    readln.split.map!(to!int).map!"a-1".reduce!"a*b".writeln;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	int n = in(), k = in(), x = in(), y = in();
	cout << x * min(n, k) + max((n - k) * y, 0) << endl;
}

Measured memory_bytes: 256
// fuck ratings, i am in love with learning process

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define tez ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
int main()
{
	tez;
	ll n;
	cin>>n;
	ll ar[n];
	for(ll i=0;i<n;i++)
	{
		cin>>ar[i];
	}
	ll prev = ar[0];
	ll ans=0;
	for(ll i=1;i<n;i++)
	{
		if(ar[i]>=prev)
		{
			prev = ar[i];
		}
		else
		{
			ans+= abs(prev-ar[i]);
			ar[i]= prev;
		}
	}
	cout<<ans<<"\n";
} 

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

int disx,disy,x1,y1,x2,y2;

int main() {
	cin >> x1 >> y1 >> x2 >> y2;
	
	disx = x2-x1;
	disy = y2-y1;
	
	for(int i=0;i<disx;i++) cout << "R";
	for(int i=0;i<disy;i++) cout << "U";
	for(int i=0;i<disx;i++) cout << "L";
	for(int i=0;i<disy;i++) cout << "D";
	
	cout << "D";
	for(int i=0;i<disx+1;i++) cout << "R";
	for(int i=0;i<disy+1;i++) cout << "U";
	cout << "L" << "U";
	for(int i=0;i<disx+1;i++) cout << "L";
	for(int i=0;i<disy+1;i++) cout << "D";
	cout << "R";
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  string W[N];
  string ans = "Yes";
  for(int i = 0;i<N;i++){
    cin >> W[i];
  }
  for(int i=1;i<N;i++){
    if(W[i-1].back() != W[i].front()) ans = "No";
  }
  
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(i==j) break;
      if(W[i] == W[j]) ans = "No";
    }
  }
  cout << ans << endl;  
}


Measured memory_bytes: 256
#!/user/bin/env pypy3
import sys
from typing import NamedTuple, List


def fast_input():
    return sys.stdin.readline()[:-1]


class Position(NamedTuple):
    t: int
    x: int
    y: int

    def _calc_diff_move(self, position) -> int:
        diff_x = self.x - position.x
        diff_y = self.y - position.y
        return abs(diff_x) + abs(diff_y)

    def can_move_from(self, prev) -> bool:
        diff_t = self.t - prev.t
        diff_move = self._calc_diff_move(prev)
        if not diff_t % 2 == diff_move % 2:
            return False
        return diff_t >= diff_move


def result_format(b: bool) -> str:
    return "Yes" if b else "No"


def solve(positions: List[Position]) -> bool:
    positions = [Position(t=0, x=0, y=0)] + positions
    for p_ind in range(len(positions) - 1):
        p_curr = positions[p_ind]
        p_next = positions[p_ind + 1]
        if not p_next.can_move_from(p_curr):
            return False
    return True


def main():
    n = int(fast_input())
    positions = []
    for _ in range(n):
        t, x, y = list(map(int, fast_input().split()))
        positions.append(Position(t=t, x=x, y=y))
    result = solve(positions)
    print(result_format(result))


main()


Measured memory_bytes: 25812
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
int main(){
        string S;
        int ans = 0;
        cin >> S;
        if(S[0] == '1')ans++;
        if(S[1] == '1')ans++;
        if(S[2] == '1')ans++;
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int n, max1, max1_i, max2;

  //cin >> n >> max1 >> max2;
  cin >> n;
  max1 = max2 = 0;

  //if (max1 < max2) {
  //  int tmp;
  //  max1_i = 1;
  //  tmp = max1;
  //  max1 = max2;
  //  max2 = tmp;
  //} else {
  //  max1_i = 0;
  //}

  //for (int i = 2; i < n; i++) {
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (max1 <= a) {
      max1_i = i;
      max2 = max1;
      max1 = a;
    } else if (max2 <= a) {
      max2 = a;
    }
  }
  for (int i = 0; i < n; i++) {
    if (i == max1_i) {
      cout << max2 << endl;
    } else {
      cout << max1 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 1664
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 100010;
int a[N], cnt[N];

int main()
{
	int n;
	scanf("%d", &n);
	int mn = n;
	Rep(i, n) {
		scanf("%d", &a[i]);
		cnt[a[i]] ++, mn = min(mn, a[i]);
	}
	if (cnt[mn] > 2) printf("Impossible\n");
	else {
		int len = mn * 2;
		bool flag = false;
		if (cnt[mn] == 2) len --;
		for (int i = mn + 1; i <= len; i ++) if (cnt[i] <= 1) flag = true;
		for (int i = len + 1; i <= n; i ++) if (cnt[i]) flag = true;
		if (flag) printf("Impossible\n");
		else printf("Possible\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
import Control.Applicative

lSearch :: [Int] -> Int -> Bool
lSearch [] _ = False
lSearch (x:xs) q
  | x == q = True
  |otherwise = lSearch xs q

solver :: [Int] -> [Int] -> Int
solver ss qs =
  let bAns = map (lSearch ss) qs
  in
      length $ filter (== True) bAns

main :: IO()
main = do
  _ <- getLine
  ss <- map (read :: String -> Int) . words <$> getLine
  _ <- getLine
  qs <- map (read :: String -> Int) . words <$> getLine
  print $ solver ss qs

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

int partition(vector<int> &arr, int p,int r){
    int x = arr.at(r);
    int i = p-1;
    for(int j=p; j<r; j++){
        if(arr.at(j) <= x){
            i++;
            swap(arr.at(i),arr.at(j));
        }
    }
    swap(arr.at(i+1),arr.at(r));
    return i+1;
}

int main(){
    int n;
    cin >> n;
    vector<int> array(n);
    for(int i=0; i<n; i++) cin >> array.at(i);
    int par = partition(array,0,n-1);
    for(int i=0; i<n; i++){
        if(i == par){
            cout << "[" <<array.at(i) << "]" ;
        }else{
            cout << array.at(i) ;
        }

        if(i != n-1){
            cout << " ";
        }

    }
    cout << endl;
}


Measured memory_bytes: 3132
N = int(input())
cnt = [0] * (N + 1)
for A in range(1, N+1):
    B = 1
    while A * B <= N:
        cnt[A * B] += 1
        B += 1
ans = 0
for C in range(1, N):
    ans += cnt[N - C]
print(ans)

Measured memory_bytes: 75292
import java.util.*;
public class Main {
public static void main(String[] args) {
		
		Scanner keyboard = new Scanner(System.in); 
		
		int N  = keyboard.nextInt();
		int[] A = new int[N];
		int[] B = new int[N];
		for(int i=0; i<N; i++) {
			 A[i] = keyboard.nextInt();
			 B[i] = A[i];
		}
		
		Arrays.sort(A);
		int count = 0;
		for(int j= 0; j<N; j++) {
			if(A[j] != B[j]) {
			count++;
			}
		}
		if(count == 2 || count == 0) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
		keyboard.close();	
	}
}


Measured memory_bytes: 21204
/*
17/10/2017
*/
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
n%=26;
for(int i=0;i<s.length();i++)
{
s[i]+=n;
if(s[i]>'Z')
{
s[i]='A'+(s[i]-'Z'-1);
}
}
cout<<s;
}

Measured memory_bytes: 3612
def mkdiv(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
ans=0
n=int(input())

for i in range(n+1):
  if len(mkdiv(i))==8 and i%2:
    ans+=1
print(ans)

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

struct State{
	string s;
	int d;
};

int N,size[10];
string a[10],b[10],src,dst,str;

int solve(){
	queue<State>Q;
	Q.push((State){src,0});
	set<string>visited;
	visited.insert(src);
	while(!Q.empty()){
		State now=Q.front();Q.pop();
		string s=now.s;
		if(s==dst)return now.d;
		
		for(int i=0;i<N;i++){
			string next="";
			for(int j=0;j<s.size();j++){
				string sub=s.substr(j,size[i]);
				if(sub==a[i]){
					next+=b[i];
					j+=size[i]-1;
				}else{
					next+=s[j];
				}
			}
			if(next.size() > dst.size()) continue;
			if(!visited.count(next)){
				visited.insert(next);
				Q.push((State){next,now.d+1});
			}
		}
	}
	return -1;
}

int main(){
	while(cin >> N, N){
		for(int i = 0 ; i < N ; i++){
			cin >> a[i] >> b[i];
			size[i] = a[i].size();
		}
		cin >> src >> dst;
		cout << solve() << endl;
	}
	return 0;
}


Measured memory_bytes: 1456
# C
# todo まず標準入力を受け取ること
n = int(input())
# todo マス目、リスト型にして受け取る
h = list(map(int, input().split()))
# todo ここに関して確認中
moved = 0
# todo 回答を格納する変数を定義する
result = 0
# マス目の数を元に繰り返し処理を開始オフセット値は0から始まるため、n -1 とする
for i in range(n - 1):
    # 隣のマスの値が現在地以上の高さを持っていた場合、
  if h[i + 1] <= h[i]:
      # 移動回数？に+1
    moved += 1
      # 高さが足りなかった場合は
  else:
    # 移動できない == tは0のまま？
    result = max(moved, result)
    moved = 0
# 最大値を答えとして格納？
result = max(moved, result)
print(result)


Measured memory_bytes: 14252
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
inline int read(){
	int f=1,ans=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
	return f*ans;
}
const int MAXN=1600001;
int n,tot;
struct node{
	int val,id;
}g[MAXN];
struct Edge{
	int u,v,nex;
}x[MAXN];
int RR;
int head[MAXN],cnt,Id[MAXN],tmp[MAXN];
int dfn[MAXN],low[MAXN],scc[MAXN],sta[MAXN],num,M[MAXN];
inline void add(int u,int v){
	RR=max(RR,max(u,v));
	x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;
}
struct Segment{
	inline int Q(int l){
		if(l%2==0) return l-1;
		return l+1;
	}
	inline void build(int k,int l,int r){
		if(l==r){add(k+2*n,M[Q(g[l].id)]);return;}
		int mid=l+r>>1;
		add(k+2*n,(k<<1)+2*n),add(k+2*n,(k<<1|1)+2*n);
		build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	}
	inline void ins(int k,int l,int r,int x,int y,int u){
		if(x<=l&&r<=y) {add(u,k+2*n);return;}
		int mid=l+r>>1;
		if(x<=mid) ins(k<<1,l,mid,x,y,u);
		if(mid<y) ins(k<<1|1,mid+1,r,x,y,u);
		return;
	}
}segment;
bool cmp(node x1,node x2){return x1.val<x2.val;}
inline void tarjan(int u){
	dfn[u]=low[u]=++num;sta[++sta[0]]=u;
	for(int i=head[u];i!=-1;i=x[i].nex){
		int v=x[i].v;
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		scc[u]=++scc[0];
		while(sta[sta[0]]!=u){
			scc[sta[sta[0]]]=scc[0];
			sta[0]--;
		}sta[0]--;
	}return;
}
inline bool check(int res){
	RR=0;
	memset(dfn,0,sizeof(dfn)),memset(scc,0,sizeof(scc)),memset(low,0,sizeof(low)),num=0;
	memset(head,-1,sizeof(head)),cnt=0;
	segment.build(1,1,2*n);
	for(int i=1;i<=2*n;i++){
		int L=lower_bound(tmp+1,tmp+tmp[0]+1,g[i].val-res+1)-tmp,R=upper_bound(tmp+1,tmp+tmp[0]+1,g[i].val+res-1)-tmp-1;
		if(L<i) segment.ins(1,1,2*n,L,i-1,i);
		if(i<R) segment.ins(1,1,2*n,i+1,R,i);
	}
	for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=2*n;i++) if(scc[i]==scc[M[segment.Q(g[i].id)]]) return 0;
	return 1;
}
signed main(){
//	freopen("flags.in","r",stdin);
//	freopen("flags.out","w",stdout);
	n=read();
	for(int i=1;i<=2*n;i++) g[++tot].val=read(),g[tot].id=i;
	sort(g+1,g+2*n+1,cmp);
	for(int i=1;i<=2*n;i++) M[g[i].id]=i;
	for(int i=1;i<=2*n;i++) tmp[++tmp[0]]=g[i].val;
	int l=0,r=INT_MAX,res;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){res=mid,l=mid+1;}
		else r=mid-1;
	}printf("%lld\n",res);
}

Measured memory_bytes: 79104
import sys
import os
import math
import bisect
import collections
import itertools
from fractions import gcd

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    sm = sum(A)
    print(min([gcd(sm, a) for a in A]))


if __name__ == '__main__':
    main()


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

    int n;
    cin >> n;
    int p[MAX+1], m[MAX+1][MAX+1];
    for(int i=1; i<=n; i++){
        cin >> p[i-1] >> p[i];
    }

    for(int i=1; i<=n; i++){
        m[i][i] = 0;    //初期化
    }

    for(int l=2; l<=n; l++){
        for(int i=1; i<=n-l+1; i++){
            int j = i + l - 1;
            m[i][j] = INT_MAX;     //INFいれる
            for(int k=i; k<=j-1; k++){
                m[i][j] = min(m[i][j], ( m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] ) );
            }
        }
    }

    cout << m[1][n] << endl;
   
    return 0;
}


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

#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (a); i >= (int)(b); i--)
#define all(x) (x).begin(), (x).end()
using i32 = int32_t;
using i64 = int64_t;
using f32 = float;
using f64 = double;
using P = pair<int, int>;

template <class T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}
template <class T>
bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

template <class T>
void dump_vec(const vector<T>& v) {
    auto len = v.size();
    rep(i, 0, len) {
        cout << v[i] << (i == (int)len - 1 ? "\n" : " ");
    }
}

struct FastIO {
    FastIO() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} FASTIO;

//---------------------------------------------------------------------------------------------------

//---------------------------------------------------------------------------------------------------

signed main() {
    f64 a;
    cin >> a;
    auto b = a / 3.0;
    auto ans = b * b * b;
    cout << ans << "\n";
}


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

#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long

int main()
{
	int n; cin>>n;
	vector<int> a(n);
	int sum=0;
	rep(i,n){
		cin>>a[i];
		sum+=a[i];
	}
	bool can=true;
	rep(i,n){
		if(sum-a[i]<=a[i]) can=false;
	}
	if(can) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


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

int main() {
    int N, odd = 0, even = 0;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (A[i] % 2 == 1) odd++;
    }
    even = N - odd;
    bool can = true;
    if (odd % 2 == 1) can = false;
    if (can) cout << "YES" << endl;
    else cout << "NO" << endl;

}

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

int main() {
  string s, t;
  cin >> s >> t;
  int sl = s.size();
  bool ok = false;
  rep(i, sl) {
    if(s == t) ok = true;
    s = s.back() + s.substr(0, sl-1);
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}
    

Measured memory_bytes: 3604
#include <iostream>
#include <cmath>
#include <algorithm>
#define FOR(i, a, b)  for(int i=a;i<b;++i)
#define rep(i, n) for(int i=0;i<n;++i)
using namespace std;

int main(){
  int h, w;
  cin >> h >> w;
  string s[h];
  rep(i, h) cin >> s[i];
  rep(i, h){
    rep(j, w){
      bool exist = false;
      if(s[i][j]=='#'){
        if(i-1>=0 && s[i][j] == s[i-1][j]){
          exist = true;
        }
        if(i+1<h && s[i][j] == s[i+1][j]){
          exist = true;
        }
        if(j-1>=0 && s[i][j] == s[i][j-1]){
          exist = true;
        }
        if(j+1<w && s[i][j] == s[i][j+1]){
          exist = true;
        }
        if(!exist) {cout<<"No"<<endl; return 0;}
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=101;

int f[N][N][N];

int a,b,c;

int main()
{
	scanf("%d%d%d",&a,&b,&c);
	int mx=max(max(a,b),c);
	for(int i=a;i<=mx+2;i++)
		for(int j=b;j<=mx+2;j++)
			for(int k=c;k<=mx+2;k++)
			{
				if(i==a&&j==b&&k==c)
					continue;
				f[i][j][k]=1000;
				if(i-1>=a&&j-1>=b)
					f[i][j][k]=min(f[i][j][k],f[i-1][j-1][k]+1);
				if(i-1>=a&&k-1>=c)
					f[i][j][k]=min(f[i][j][k],f[i-1][j][k-1]+1);
				if(j-1>=b&&k-1>=c)
					f[i][j][k]=min(f[i][j][k],f[i][j-1][k-1]+1);
				if(i-2>=a)
					f[i][j][k]=min(f[i][j][k],f[i-2][j][k]+1);
				if(j-2>=b)
					f[i][j][k]=min(f[i][j][k],f[i][j-2][k]+1);
				if(k-2>=c)
					f[i][j][k]=min(f[i][j][k],f[i][j][k-2]+1);
			}
	int ans=1001;
	for(int i=mx;i<=mx+2;i++)
		ans=min(ans,f[i][i][i]);
	printf("%d",ans);
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    ll s;
    cin>>s;
    int x=0,y=0;
    int n=1e9;
    x=(n-s%n)%n;
    y=ceil((double)s/n);
    cout<<"0 0 1000000000 1 "<<x<<" "<<y<<endl;
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args)
    {
        String strData1 = Console.ReadLine();
        String strData2 = Console.ReadLine();

        strData1 += strData1;

        if (strData1.IndexOf(strData2) != -1)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 9816
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    ll n;
    cin >> n;
    ll ans_1 =0;
    ll ans_2 =0;
    for(ll i=1; i*i<=n; i++){
        if(n%i ==0){
            ans_1 = i;
            ans_2 = n/i;
        }
    }
    cout << ans_1 -1 + ans_2 -1 << endl;
}

Measured memory_bytes: 256