akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns #-}

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Mutable as VM
import Control.Monad.ST
import Data.Foldable
import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as B
-- import Debug.Trace

kFix :: Int
kFix = 1000000007

binFix :: (Int -> Int -> Int) -> Int -> Int -> Int
binFix op !a !b = (a `op` b) `rem` kFix

addFix = binFix (+)
subtFix !a !b = (a - b + kFix) `rem` kFix
mulFix = binFix (*)

sumFix :: [Int] -> Int
sumFix = foldl' addFix 0 

nMax :: Int
nMax = 200000

vPow :: VU.Vector Int
vPow = VU.iterateN (nMax + 1) f 1
  where f x = (x * 2) `rem` kFix

type IVal = (Int, Int)
-- (x, m) :: Ival
--    means that the number of node is m, and out of 2^m cases
--    there is a stone in x' cases where x' \equiv x mod kFix

goUp :: [IVal] -> IVal
goUp ivs = (x, m) where (_, x, m) = goUpSub ivs

goUpSub :: [IVal] -> (Int, Int, Int)
--                   (numCases0, numCases1, m)
goUpSub = foldl' guBin (1, 0, 0)
  where
    guBin :: (Int, Int, Int) -> IVal -> (Int, Int, Int)
    guBin arg1@((!x0, !x1, !m)) arg2@(!x', !m') = 
      -- The two p values should be equal
      let newM = m + m'
          xNeg = vPow VU.! m' `subtFix` x'
          newX0 = x0 `mulFix` xNeg
          newX1 = (x0 `mulFix` x') `addFix` (x1 `mulFix` xNeg)
      in (newX0, newX1, newM)

body :: Int -> [Int] -> Int
body numNodes parent = 
  let f :: IVal -> Int
      f (x, p) = x `mulFix` (vPow VU.! (numNodes - p))
  in foldl' addFix 0 $ map f $ accumulate 0
  where

    accumulate :: Int -> [IVal]
    accumulate i = (1, 1) : rest
      where
        rest = case children V.! i of
          []   -> []
          [j]  -> accumulate j
          cs@_ -> map goUp $ transpose $ map accumulate cs


    children :: V.Vector [Int]
    children = V.create $ do
      v <- VM.replicate numNodes []
      for_ (zip [1..] parent) $ \(i, p) -> VM.modify v (i :) p
      return v

main :: IO ()
main = do
  cont <- B.getContents
  let [[n], ps] =
        map (map (fst . fromJust . B.readInt) . B.words) (B.lines cont)
  putStrLn $ show $ body (n + 1) ps



Measured memory_bytes: 66940
#include<iostream>
#include<algorithm>

int main(){

	bool flg = true;

	int r1 = 0, r2 = 0, r3 = 0;

	int data[3];
	while (std::cin >> data[0] >> data[1] >> data[2]){
		if (!flg)continue;

		std::sort(data, data + 3);

		if (data[2] >= data[1] + data[0]){
			std::cout << r1 + r2 + r3 << " " << r2 << " " << r1 << " " << r3 << std::endl;
			flg = false;
		}

		if (data[2] * data[2] < data[1] * data[1] + data[0] * data[0])r1++;
		if (data[2] * data[2] == data[1] * data[1] + data[0] * data[0])r2++;
		if (data[2] * data[2] > data[1] * data[1] + data[0] * data[0])r3++;
	}

	return 0;
}

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

int main(){
    bool cards[4][14];
    int n , rank;
    char suit;

    for ( int s= 0 ; s < 4 ; s++)
      for ( int r = 1 ; r <= 13 ; r ++)
        cards[s][r] = 0;
    
    cin >> n;
    for ( int i = 0; i < n ; i++){
        cin >> suit >> rank ;
        if (suit == 'S') cards[0][rank] = 1;
        if (suit == 'H') cards[1][rank] = 1;
        if (suit == 'C') cards[2][rank] = 1;
        if (suit == 'D') cards[3][rank] = 1;
    }

    for ( int s=0  ; s < 4 ; s++){
      for ( int r = 1; r <=13; r++){
            if ( cards[s][r]) continue;
            if ( s == 0) suit = 'S';
            if ( s == 1) suit = 'H';
            if ( s == 2) suit = 'C';
            if ( s == 3) suit = 'D';
            cout << suit << " " << r << endl;

      }
    }
    return 0;
}


Measured memory_bytes: 3084
A=[list(map(int,input().split())) for i in range(3)]
n=int(input())
for k in range(n):
  s=int(input())
  for i in range(3):
    for j in range(3):
      if s == A[i][j]:
        A[i][j]=0   
if A[0][0]==0 and A[1][0]==0 and A[2][0]==0:
  print("Yes")
   
elif A[0][1]==0 and A[1][1]==0 and A[2][1]==0:
  print("Yes")
elif A[0][2]==0 and A[1][2]==0 and A[2][2]==0:
  print("Yes")
elif [0,0,0] in A:
  print("Yes")
  
elif A[0][2]==0 and A[1][1]==0 and A[2][0]==0:
  print("Yes")
  
elif A[0][0]==0 and A[1][1]==0 and A[2][2]==0:
  print("Yes")
  
else:
  print("No")


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(){
    int n, m;
    cin >> n >> m;
    vector<ll> score(n, -(1ll<<60));
    score[0] = 0;
    vector<pair<pair<int,int>,int>> edge;
    int a, b, c;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        a--, b--;
        edge.push_back({{a,b},c});
    }
    for(int loop = 1; loop < n; loop++){
        vector<ll> next = score;
        for(int i = 0; i < m; i++){
            int from = edge[i].first.first, to = edge[i].first.second;
            next[to] = max(next[to], score[from]+edge[i].second);
        }
        score = next;
    }

    // 本当はここの負閉路チェックが1回で終わってほしいんだけど、多分だめ
    // 腑に落ちないがひとまずもうn回ループして位置n-1におけるスコア上昇にのみ
    // 注意すれば良い(多分)
    
    // 解説を読んだ.負閉路長が最大でnなので追加でn回ループを回す必要がある.
    bool valid = true;
    for(int loop = 0; loop < n; loop++){
        vector<ll> next = score;
        for(int i = 0; i < m; i++){
            int from = edge[i].first.first, to = edge[i].first.second;
            if(next[to] < score[from]+edge[i].second){
                next[to] = score[from]+edge[i].second;
                if(to == n-1)   valid = false;
            }
        }
        score = next;
    }
    if(valid)   cout << score[n-1] << endl;
    else        cout << "inf" << endl;
    return 0;
}


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

using namespace std;

int main()
{
    string s;
    cin>>s;
    if(s[6]>'4'||(s[5]=='1'&&s[6]=='0')||(s[5]=='1'&&s[6]=='1')||(s[5]=='1'&&s[6]=='2'))
        cout<<"TBD"<<endl;
    else
        cout<<"Heisei"<<endl;
return 0;
}


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

int main(){
  int S;
  cin>>S;
  int k=S/100;
  int v=S%100;
  if(k>12||k==0){
    if(v>12||v==0)
      cout<<"NA"<<endl;
    else
      cout<<"YYMM"<<endl;
  }
  else{
    if(v>12||v==0)
      cout<<"MMYY"<<endl;
    else
      cout<<"AMBIGUOUS"<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int i,l,c=1;
  char s[10001];
  cin>>s;
  l=strlen(s);

  for(i=0;i<(l/2);i++)
  {

   if(s[i]!=s[l-i-1])
   {
    
    c=0;
   
    break;
   }
  }
  if(c==0)
  {
    cout<<"No"<<endl;
    return 0;
  }
  c=1;
  int x=(l-1)/2;
  for(i=0;i<x;i++)
  {
    if(s[i]!=s[x-i-1])
    {
      c=0;
      break;
    }
  }
  if(c==0)
  {
    cout<<"No"<<endl;
    return 0;
  }
  c=1;
    x=(l+3)/2;
  for(i=x;i<l;i++)
  {
    if(s[i]!=s[l-i-1])
    {
      c=0;
      break;
    }
  }
  if(c==0)
  {
    cout<<"No"<<endl;
    return 0;
  }
  cout<<"Yes"<<endl;
  return 0;

} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
typedef pair<int, int> P;

int main()
{
   int r;
   cin>>r;
   cout<<r*r<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

bool ok(string s){
  int n = s.size();
  if(n==0) return true;
  if(n%2==1) return false;
  rep(i,n/2) if(s[i] != s[i+n/2]) return false;
  return true;
}

int main(){
  string s;
  cin>>s;
  do {
    s = s.substr(0, s.size()-2);
  } while(!ok(s));

  cout << s.size() << endl;

  return 0;
}


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

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

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

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a;}

//head
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	cout << (n) * (n-1) / 2 + (m)*(m-1)/2 << "\n";
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
    //データ取り込み
		Scanner sc = new Scanner(System.in);
		//String S = sc.next();
    //int B = sc.nextInt();
    //System.out.println();
		int X = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		System.out.println((X-A)%B);
	}
}

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

// Nが同じ数字を3つ以上連続して並んでいる場合にtrueを返す関数
bool GoodIntger(int N);

int main()
{
  int N;
  cin>>N;

  if(GoodIntger(N))
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

  return 0;
}

bool GoodIntger(int N)
{
  int a = (N - N%1000)/1000;
  N -= a*1000;
  int b = (N - N%100)/100;
  N -= b*100;
  int c = (N - N%10)/10;
  N -= c*10;
  int d = N;
  
  if((a==b&&b==c)||(b==c&&c==d))
    return true;
  else
    return false;
}


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


int main(){
  long long int N, M;
  cin >> N >> M;
  vector<vector<long long int>> A(N, vector<long long int>(2));
  for(auto& a : A){
    cin >> a[0] >> a[1];
  }
  sort(A.begin(), A.end(), [](const vector<long long int>& a, const vector<long long int>& b){
    return a[0] < b[0];
  });
  long long int ans = 0;
  for(auto& a : A){
    if(M > a[1]){
      ans += a[0] * a[1];
      M -= a[1];
    }else{
      ans += a[0] * M;
      break;
    }
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 5760
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int d[] = new int[n];
    for(int i = 0 ; i < n ; ++i){
      d[i] = sc.nextInt();
    }
    int ans = 1;
    Arrays.sort(d);
    for(int i = 1 ; i < n ; ++i){
      if(d[i]!=d[i-1]){
        ans++;
      }
    }
    System.out.println(ans);
    
  }
}

Measured memory_bytes: 35968
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<ll,ll> pint;
const long long INF = 1LL<<60;
const ll MOD = 1000000007;
ll gcd(ll a,ll b){
    if(b==0){
        return a;
    }
    else{
        return gcd(b,a%b);
    }
}
vector<ll> dx={0,1};
vector<ll> dy={1,0};
int main(){
    ll h,w;cin>>h>>w;
    vector<string> meiro(h);
    rep(i,h)cin>>meiro[i];
    vector<vector<ll>> ans(h,vector<ll>(w,0));
    ans[0][0]=1;
    rep(i,h){
        rep(j,w){
            if(i+1<h&&meiro[i+1][j]=='.'){
            ans[i+1][j]+=(ans[i][j]%MOD);
            ans[i+1][j]%=MOD;
            }
            if(j+1<w&&meiro[i][j+1]=='.'){
                ans[i][j+1]+=(ans[i][j]%MOD);
                ans[i][j+1]%=MOD;
            }
        }
    }
    cout<<ans[h-1][w-1]<<endl;
}


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

int main(){
    int a,b,c,d;
    cin >> a >> b;
    c = a + b;
    d = c / 2;

    if(c % 2 == 0) {
        cout << d << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }


    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N-1];
		int[] b = new int[N-1];
		Integer[] c = new Integer[N];
		ArrayList<List<Integer>> edge_1 = new ArrayList<List<Integer>>();
		for (int i=0;i<N;i++) {
			List<Integer> x = new ArrayList<Integer>();
			edge_1.add(x);
		}
		for (int i=0;i<N-1;i++) {
			a[i]=sc.nextInt()-1;
			b[i]=sc.nextInt()-1;
			if (a[i]>b[i]) {
				int tmp=a[i];
				a[i]=b[i];
				b[i]=tmp;
			}
			edge_1.get(a[i]).add(b[i]);
			edge_1.get(b[i]).add(a[i]);
		}
		int min=0;
		for (int i=0;i<N;i++) {
			c[i]=sc.nextInt();
			min+=c[i];
		}
		Arrays.sort(c,Comparator.reverseOrder());
		min-=c[0];

		int[] ans = new int[N];
		int z = 0;

		//DFS
		Queue<int[]> queue_1 = new ArrayDeque<int[]>();
		int M = edge_1.get(0).size();
		ans[0]=c[z];
		z++;
		for (int i=0;i<M;i++) {
			int a_i=0;
			int b_i=edge_1.get(0).get(i);
			int[] add_init = {a_i,b_i};
			queue_1.add(add_init);
		}

		while(!queue_1.isEmpty()) {
			int[] rem=queue_1.remove();
			int a_x=rem[0];
			int b_x=rem[1];

			int P = edge_1.get(b_x).size();
			for (int i=0;i<P;i++) {
				int a_i=b_x;
				int b_i=edge_1.get(b_x).get(i);
				if (ans[b_i]==0) {
					int[] add_array={a_i,b_i};
					queue_1.add(add_array);
				}
				int Q = edge_1.get(b_i).size();
				if (P>=2 && ans[a_i]==0) {
					ans[b_x]=c[z];
					z++;
				}
			}
		}
		int h=0;
		while (z<N) {
			if (ans[h]==0) {
				ans[h]=c[z];
				z++;
			}
			h++;
		}
		System.out.println(min);
		for (int i=0;i<N;i++) {
			if (i!=N-1) {
				System.out.print(ans[i] + " ");
			} else {
				System.out.println(ans[i]);
			}
		}
	}
}


/*
9
1 2
2 3
2 6
7 2
3 8
9 3
4 1
4 5
2 4 1 3 5 6 7 8 9

*/

Measured memory_bytes: 46760
#include <stdio.h>
#include <string.h>

void CSLength(char *,char *);

int c[1001][1001],a[1001];

int main() {
  int i,j=0,q;
  char s[1001],x[1001],y[1001];

  scanf("%d",&q);

  for(i=0;i<q;i++){

    scanf("%s",s);
    strcpy(&x[1],s);

    scanf("%s",s);
    strcpy(&y[1],s);

    x[0]='a';
    y[0]='a';

    CSLength(x,y);


    a[i]=c[strlen(x)-1][strlen(y)-1];
  }

  for(i=0;i<q;i++){
    printf("%d\n",a[i]);
  }

  return 0;
}

void CSLength(char *x,char *y){
  int m,n,i,j;


  m = strlen(x);
  n = strlen(y);

  for(i=1;i<m;i++) c[i][0] = 0;
  for(j=1;j<n;j++) c[0][j] = 0;

  for(i=1;i<m;i++){
    for(j=1;j<n;j++){  
      if(x[i]==y[j]){
	c[i][j] = c[i-1][j-1] + 1;
      }
      else if(c[i-1][j] >= c[i][j-1]){
	c[i][j] = c[i-1][j];
      }
      else c[i][j] = c[i][j-1];
    }
  }



}

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

using namespace std;
int a[3001][3001]={-1};

int main()
{
    string s,t,u;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    for(int i=0;i<n+1;i++)
        for(int j=0;j<m+1;j++)
         if(i==0 || j==0)
            a[i][j]=0;

   for(int i=1;i<n+1;i++)
        for(int j=1;j<m+1;j++)
        {
            if(s[i-1]==t[j-1])
                a[i][j]=1+a[i-1][j-1];
            else
                a[i][j]=max(a[i-1][j],a[i][j-1]);
        }

   while(m>0 && n>0)
        {
            if(s[n-1]==t[m-1])
             {u.push_back(s[n-1]);
               n--;
               m--;}
            else
            {
                if(a[n-1][m]>a[n][m-1])
                  n--;
                else
                    m--;

            }

        }
        reverse(u.begin(),u.end());
        cout<<u;

}


Measured memory_bytes: 38816
_ = int(input())
A = list(map(int, input().split()))

ret = float('inf')

sign = 1
s = 0
k = 0
for a in A:
    if sign * (s + a) > 0:
        s += a
    else:
        k += abs(s + a) + 1
        s = sign
    sign *= -1
ret = min(ret, k)

sign = -1
s = 0
k = 0
for a in A:
    if sign * (s + a) > 0:
        s += a
    else:
        k += abs(s + a) + 1
        s = sign
    sign *= -1

ret = min(ret, k)


print(ret)


Measured memory_bytes: 14468
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N= 1e5 +10;

int n, m;
int p[N], F[N];
int x, y;
set<int> S[N];
ll ans;

void init() {
	REP(i, 1, n) F[i]=i;
}

int Find(int x) {
	if (F[x]==x) return F[x];
	else return F[x]=Find(F[x]);
}

void Union(int a, int b) {
	int p=Find(a);
	int p2=Find(b);
	if (p!=p2) F[p]=p2;
}

int main() {
	cin>>n>>m;
	init();
	REP(i, 1, n) {
		cin>>p[i];
	}
	REP(i, 1, m) {
		cin>>x>>y;
		Union(x, y);
	}
	REP(i, 1, n) {
		S[Find(i)].insert(p[i]);
	}

	REP(i, 1, n) {
		if (S[Find(i)].count(i)) ans++;
	}

	cout<<ans<<endl;

	//cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
	return 0;
}

Measured memory_bytes: 10368
N, X, Y = map(int, input().split())

cost = [[0 for _ in range(N)] for _ in range(N)]
output = [0 for i in range(N-1)]


X -= 1
Y -= 1
for i in range(N-1):
    for j in range(i+1, N):
        if i <= X:
            if j <= X:
                c = j-i
            elif X < j <= Y:
                c = X - i + min(j-X, Y-j+1)
            elif Y < j:
                c = X - i + j - Y + 1
        elif i < Y:
            if j <= Y:
                c = min(j-i, Y-j+i-X+1)
            else:
                c = j - Y + min(Y - i, i - X + 1)
        else:
            c = j-i
        output[c-1] += 1

for i in range(N-1):
    print(output[i])

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

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, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n; std::cin >> n;
  int ans = 0;
  rep(i, n) {
    int a; std::cin >> a;
    if (i == 0) ans = a;
    else ans = gcd(ans, a);
  }
  std::cout << ans << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

int main()
{
	std::string a, b;
	std::cin >> a >> b;

	std::string sample[16]{ "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F" };

	int aIndex, bIndex;

	for (int i = 0; i < 16; i = i + 1)
	{
		if (a == sample[i])
		{
			aIndex = i;
			break;
		}
	}

	for (int i = 0; i < 16; i = i + 1)
	{
		if (b == sample[i])
		{
			bIndex = i;
			break;
		}
	}

	if (aIndex > bIndex)
	{
		std::cout << ">";
	}
	else if (aIndex == bIndex)
	{
		std::cout << "=";
	}
	else
	{
		std::cout << "<";
	}

    return 0;
}

Measured memory_bytes: 256
using System;

namespace AtCoder.Problems
{
    public class ProblemB
    {
        public static void Main(string[] args)
        {
            var s = new SolveB();
            s.Solve();
        }

        public class Scanner
        {
            private string[] _s;
            private int _i;
            private readonly char[] _separators = new char[] {' '};

            public Scanner()
            {
                _s = new string[0];
                _i = 0;
            }

            public string Next()
            {
                if (_i < _s.Length) return _s[_i++];
                string st = Console.ReadLine();
                while (st == "") st = Console.ReadLine();
                _s = st.Split(_separators, StringSplitOptions.RemoveEmptyEntries);
                if (_s.Length == 0) return Next();
                _i = 0;
                return _s[_i++];
            }

            public int NextInt() => int.Parse(Next());
            public long NextLong() => long.Parse(Next());
            public ulong NextULong() => ulong.Parse(Next());
            public double NextDouble() => double.Parse(Next());

            public int[] GetIntArray(int n, int add = 0)
            {
                int[] array = new int[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = NextInt() + add;
                }
                return array;
            }

            public long[] GetLongArray(int n, long add = 0)
            {
                long[] array = new long[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = NextLong() + add;
                }
                return array;
            }

            public double[] GetDoubleArray(int n, double add = 0)
            {
                double[] array = new double[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = NextDouble() + add;
                }
                return array;
            }
        }
    }

    public class SolveB
    {
        public void Solve()
        {
            var cin = new ProblemB.Scanner();
            var a = cin.NextInt();
            var b = cin.NextInt();
            var c = cin.NextInt();
            var d = cin.NextInt();

            var result = GetAnswer(a,b,c,d);
            Console.WriteLine(result);
        }

        public string GetAnswer(int a, int b, int c, int d)
        {
            while (true)
            {
                c -= b;
                if (c <= 0) { return "Yes"; }
                a -= d;
                if (a <= 0) { return "No"; }
            }
            return null;
        }
    }
}

Measured memory_bytes: 27556
#include<stdio.h>
main(){
  double x[100],y[100];
  double a,b,c,d;
  int j;
  while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x[j],&y[j],&x[j+1],&y[j+1],&x[j+2],&y[j+2],&x[j+3],&y[j+3])){
    a=x[j]-x[j+1];
    b=y[j]-y[j+1];
    c=x[j+2]-x[j+3];
    d=y[j+2]-y[j+3];
    if((a*c+b*d)==0){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
    j++;
  }
  return 0;
}

Measured memory_bytes: 612
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _170B
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] num = Console.ReadLine().Split(' ').Select(tmp => long.Parse(tmp)).ToArray();
            long X = num[0];
            long Y = num[1];

            double turtle = ((double)Y - 2 * (double)X) / 2;
            double crane = X - turtle;
            if (turtle == (int)turtle && turtle >= 0 &&  crane >= 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }

        }
    }
}


Measured memory_bytes: 28088
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int g[110][110];

int main(){
    int n, k;
    cin >> n >> k;
    int ma = (n-1) * (n-2) / 2;
    if(ma < k) {
        cout << -1 << '\n';
        return 0;
    }
    int d = ma - k;
    int m = 0;
    REP(i, 1, n) {
        g[0][i] = 1;
        ++m;
    }
    REP(i, 1, n) REP(j, i+1, n) {
        if(d > 0) {
            g[i][j] = 1;
            --d;
            ++m;
        }
    }
    cout << m << '\n';
    rep(i, n) REP(j, i+1, n) {
        if(g[i][j] == 1) {
            cout << i+1 << " " << j + 1 << '\n';
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n],dp[k+1]={};
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<=k;i++)
    {
        if(dp[i]==0)
        {
            for(int j=0;j<n;j++)
            if(i+arr[j]<=k) dp[i+arr[j]]=1;
        }
    }
    if(dp[k]==1) cout<<"First";
    else cout<<"Second";
}


Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 998244353;
int f[305][305][305], n, m, a[305];
char s[305];
inline int abs(const int &x){return x<0?-x:x;}
inline int add(const int &x, const int &y){return x+y>=mod?x+y-mod:x+y;}
int main() {
	scanf("%s%d",s+1,&m);
	for(int i=1, L=strlen(s+1), pre=0;i<=L;i++) {
		if(s[i]=='0') {
			a[++n]=i-pre-1;
			pre=i;
		} else if(i==L) {
			a[++n]=i-pre;
		}
	}
	m=min(m,int(strlen(s+1)));
	f[n+1][0][0]=1;
	for(int i=n+1;i>1;i--) {
		for(int p=0;p<=m;p++) {
			for(int j=0;j<=m;j++) if(f[i][p][j]){
				for(int k=0;k<=m;k++) {
					if(k<=p) {
						f[i-1][p-k][j]=add(f[i][p][j],f[i-1][p-k][j]);
					}
					if(k<=a[i-1]&&k) {
						f[i-1][p+k][j+k]=add(f[i][p][j],f[i-1][p+k][j+k]);
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=add(ans,f[1][0][i]);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 18064
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define vsort(v) sort(v.begin(),v.end())
#define asort(a,n) sort(a, a + n)
#define vi vector<int>
#define vd vector<double>

//ここからAtCoder向けdefine
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;

using namespace std;

char letter[6] = {'A', 'B', 'C', 'D', 'E', 'F'};

int main(){
    ios::sync_with_stdio(false);
    char a, b;
    cin >> a >> b;
    int anum, bnum;
    rep(i, 6){
        if(a == letter[i]){
            anum = i;
        }
        if(b == letter[i]){
            bnum = i;
        }
    }
    if(anum > bnum){
        cout << ">" << endl;
    }else if(anum == bnum){
        cout << "=" << endl;
    }else{
        cout << "<" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
// AOJ Volume 0 Problem 0061

#include <stdio.h>
#include <string.h>

typedef struct {
	int team;
	int score;
} RESULT;


int main(void)
{
    RESULT result[1000];
	int score_list[31];
	int team_no;
	int team;
	int rank;
	int i;
	int score;
	
	memset(score_list, 0, sizeof(score_list));
	team_no = 0;
	while (1){
		scanf("%d,%d", &result[team_no].team, &result[team_no].score);
		score_list[result[team_no].score] = 1;
		if (result[team_no].team == 0 && result[team_no].score == 0){
			break;
		}
		team_no++;
	}
	

	while (scanf("%d", &team) != EOF){
		for (i = 0; i < team_no; i++){
			if (result[i].team == team){
				score = result[i].score;
				break;
			}
		}
		
		rank = 1;
		for (i = score + 1; i <= 30; i++){
			rank += score_list[i];
		}
		printf("%d\n", rank);
	}

	return (0);
}

Measured memory_bytes: 0
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False
# cython: cdivision=True
# False:Cython はCの型に対する除算・剰余演算子に関する仕様を、(被演算子間の符号が異なる場合の振る舞いが異なる)Pythonのintの仕様に合わせ、除算する数が0の場合にZeroDivisionErrorを送出します。この処理を行わせると、速度に 35% ぐらいのペナルティが生じます。 True:チェックを行いません。

ctypedef long long LL
from libc.stdio cimport scanf, printf
from libcpp.vector cimport vector
ctypedef vector[LL] vec


cdef class UnionFind:
    cdef:
        LL N,n_groups
        vec parent

    def __init__(self, LL N):
        self.N = N  # ノード数
        self.n_groups = N  # グループ数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = vec(N,-1)  # idxが各ノードに対応。

    cdef LL root(self, LL A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    cdef LL size(self, LL A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    cdef bint unite(self,LL A,LL B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる
        self.n_groups -= 1

        return True

    cdef bint is_in_same(self,LL A,LL B):
        return self.root(A) == self.root(B)


cdef LL N,M,_
scanf('%lld %lld',&N, &M)

cdef UnionFind uf = UnionFind(N)
cdef LL a,b
for _ in range(M):
    scanf('%lld %lld',&a, &b)
    uf.unite(a-1, b-1)

print(-min(uf.parent))
'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode


Measured memory_bytes: 19972
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

# Written by NoKnowledgeGG @YlePhan

#import math
#mod = 10**9+7



def main():
  a,b,c,d = map(int,input().split())
  if b >= c:
    if a <= d:
      l = max(a,c)
      r = min(b,d)
      print(abs(r-l))
      exit()
    else:
      print(0)
      exit()
  else:
    print(0)
    exit()
if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N0, N, sum(0);
    cin >> N0;
    N = N0;
    while (N > 0)
    {
        sum += (N % 10);
        N /= 10;
    }
    if (N0 % sum == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
    int a,b,N;
    cin >> a >> b >> N;
    int i,s,f;
    bool flag = true;
    for(i=0;i<N;i++) {
        cin >> s >> f;
        if(s<b && a<f)flag = false;
    }
    cout << (flag?0:1) << endl;
}


Measured memory_bytes: 3116
var
s:string;
i,l,a,b:longint;
begin
readln(s);
l:=length(s);
if (s[1]<>'A') or (s[2]='C') or (s[l]='C') then
begin
writeln('WA');
halt;
end;
a:=0; b:=0;
for i:=2 to l do
begin
if s[i]='C' then inc(a);
if s[i] in ['A'..'Z'] then inc(b);
end;
if (a=1) and (b=1) then writeln('AC')
else writeln('WA');
end.


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define Rep(i,n) for (int i = (int)(n); i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define rever(vec) reverse(all(vec));
#define cend printf("\n");
#define prique(T) priority_queue<T, vector<T>, greater<T>>
#define prique2(T) priority_queue<T>

#define yes printf("Yes\n")
#define Yes printf("YES\n")
#define no printf("No\n")
#define No printf("NO\n")

struct edge { int to, cost; };
using P = pair<int, int>;
using PP = pair<P, int>;
using D = pair<double, double>;
//const long long mod = 998244353;
const long long mod = 1e9 + 7, inf = 3e18;
const string sp = " ";
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = max(a, b);
		return true;
	}
	return false;
}
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = min(a, b);
		return true;
	}
	return false;
}

int modpow(int x, int n) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) {
			ans *= x;
			if (mod <= ans) ans %= mod;
		}
		x *= x;
		if (mod <= x) x %= mod;
		n >>= 1;
	}
	return ans;
}

int fact[1000000];
void f_init(int n) {
	if (1000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= n; ++i) {
		fact[i] *= fact[i - 1];
		if (mod <= fact[i]) fact[i] %= mod;
	}
	return;
}

int comb(int n, int r) {
	if (n < r) return 0;
	int ans = fact[n] * modpow(fact[n - r], mod - 2) % mod * modpow(fact[r], mod - 2);
	if (ans < 0) return ans + mod;
	return ans;
}

int perm(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	int ans = fact[n] * modpow(fact[n - r], mod - 2) % mod;
	if (ans < 0) return ans + mod;
	return ans;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

bool pri(int p) {
	for (int i = 2; i * i <= p; ++i) if (p % i == 0) return false;
	return p > 1;
}

map<int, int> factring(int n) {
	map<int, int>ans;
	for (int i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++ans[i];
		}
	}
	if (n != 1) ++ans[n];
	return ans;
}

int n, t, mi = inf;
int a, ans, cnt;
signed main() {
	cin >> n >> t;
	rep(i, n) {
		cin >> a;
		mi = min(mi, a);
		if (ans < a - mi) {
			ans = a - mi;
			cnt = 1;
		}
		else if (ans == a - mi) cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;
lint p=998244353;

lint calc(int k, vector<vector<int>> &c){
  lint ret=1;
  for(auto e:c[k]){
    ret*=calc(e,c);
    ret%=p;
  }
  ret++;
  ret%=p;
  return ret;
}

int main(){
  int N;
  cin>>N;
  map<lint,lint> m,mc;
  map<lint,int> index;
  bool r[N];
  REP(i,N)r[i]=true;
  REP(i,N){
    lint X,D;
    cin>>X>>D;
    m[X]=D;
    index[X]=i;
  }
  vector<vector<int> > c(N+1);
  mc=m;
  for(auto e=mc.rbegin();e!=mc.rend();++e){
    auto X=e->first;
    auto D=e->second;
    // cerr<<" "<<X<<" "<<D<<endl;
    auto pb=m.find(X);
    pb++;
    for(auto p=pb;p!=m.end()&&p->first<X+D;){
      c[index[X]].push_back(index[p->first]);
      r[index[p->first]]=false;
      auto pc=p;
      ++p;
      m.erase(pc);
    }
  }
  REP(i,N)if(r[i])c[N].push_back(i);
  // REP(i,N+1){
  //   for(auto e:c[i])cerr<<e<<" ";
  //   cerr<<endl;
  // }
  cout<<calc(N,c)-1<<endl;
  // REP(i,N){
  //   cerr<<calc(i,c)<<endl;
  // }
  return 0;
}


Measured memory_bytes: 52096
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		
		int n = sc.nextInt();
		int count = 0;
		int ans = -1+1;
		
		for(int i =1; i<=n; i++) {
			for(int j = 1; j<=i; j++) {
				if(i%j ==0) {
					count +=1;
				}
			}
			if(count==8) {
				ans +=1;
			}
			count = 0;
			i++;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 35804
from collections import Counter

N = int(input())
A = sorted(Counter(list(map(int, input().split()))).most_common(), reverse=True)

tmp = []
for elt, cnt in A:
    if 1 >= cnt:
        continue
    if cnt >= 4:
        tmp.append(elt)
        tmp.append(elt)
        break
    if cnt >= 2:
        tmp.append(elt)

if len(tmp) >= 2:
    print(tmp[0] * tmp[1])
else:
    print(0)


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

int main()
{
	string N;
	bool flag = true;
	cin >> N;
	for ( int i = 1; i < N.size(); i++ ) {
		if ( N[i] != '9' ) flag = false;
	}
	if ( flag ) {
		cout << (N[0] - '0') + 9 * (N.size() - 1) << endl;
	} else {
		cout << (N[0] - '1') + 9 * (N.size() - 1) << endl;
	}
	return ( 0 );
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <cmath>
using Int = long long;
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
int main()
{
    int X; cin >> X;
    int t, sum;
    for (t = 0, sum = 0; sum < X; t++) sum += t + 1;
    cout << t << endl;
    return 0;
}

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

// alias templates
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

// alias declaration
using ll = long long;
using str = string;

using vll = V<ll>;
using vvll = V<vll>;
using vs = V<str>;

// loops
#define FOR(i, a, b)  for (ll i = (a); i <= (ll)(b); i++) // [a,b]
#define rFOR(i, a, b) for (ll i = (b); i >= (ll)(a); i--) // [b,a]
#define REP(i, a) FOR((i), 0, (ll)(a)-1) // [0,a-1]

// for debug
#define dbg(a) cerr << "  " << (#a) << ": " << (a) << "\n";

// procon common constants
const ll MOD_BIG = 1e9 + 7;

int main(void){
    ll n;
    cin >> n;
    vll d(n);
    REP(i,n){
        cin >> d[i];
    }
    sort(d.begin(),d.end());
    ll t = d[n/2]-d[n/2-1];
    if(t==0){
        cout << 0 << endl;
    }else{
        cout << t << endl;
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define ull unsigned long long int
#define forn(i,n)for(ll i=0;i<(n);i++)
#define forn_rev(i,n)for(ll i=(n)-1;i>=0;i--)
#define for1n(i,n) for(ll i=1;i<=(n);i++)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(*a)
#define MOD 1000000007
#define MAXN 1000005

using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    ll T=1;
    //cin>>T;
    while(T--)
    {


      ll N;
      cin>>N;
      ll ans=0;
      ll rem=N/500;
      N-=500*rem;
      ans+=1000*rem;
      while(N>=500){
        N-=500;
        ans+=1000;
      }
      while(N>=5){
        N-=5;
        ans+=5;
      }
      cout<<ans;







    }



    return 0;
}


Measured memory_bytes: 256
import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))


Measured memory_bytes: 116648
# coding: utf-8
S = input()
t = len(S)
ans = 0

for i in range(t):
  if S[i:i+1] in S[i+1:i+2]:
    ans +=1
    if S[i+1:i+2] in "0":
      S = S[:i+1]+"1"+S[i+2:] 
    else:
      S = S[:i+1]+"0"+S[i+2:] 
    
print(ans)

Measured memory_bytes: 3436
def resolve():
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    n,m = map(int, input().split())

    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int ,input().split())
        a -= 1
        b -= 1
        uf.union(a, b)
    ans = 0
    for i in range(n):
        ans = max(ans, uf.size(i))
    print(ans)
resolve()

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define MAX_H 500
#define MAX_W 500

i64 G[MAX_H][MAX_W];
i64 ops[MAX_H * MAX_W][4];

int main() {
    i64 H, W; cin >> H >> W;
    REP(i, H) REP(j, W) cin >> G[i][j];

    i64 cnt = 0;
    auto run_op = [&](i64 y, i64 x, i64 ny, i64 nx) {
        G[y][x]--; G[ny][nx]++;
        ops[cnt][0] = y + 1;
        ops[cnt][1] = x + 1;
        ops[cnt][2] = ny + 1;
        ops[cnt][3] = nx + 1;
        cnt++;
    };
    REP(y, H) {
        REP(x, W - 1) {
            if (G[y][x] % 2 == 0) continue;
            run_op(y, x, y, x + 1);
        }
    }
    REP(y, H - 1) {
        if (G[y][W - 1] % 2 == 0) continue;
        run_op(y, W - 1, y + 1, W - 1);
    }

    cout << cnt << endl;
    REP(i, cnt) {
        REP(j, 4) {
            if (j > 0) cout << " ";
            cout << ops[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 9856
// E.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
	while (true) {
		int n = -1, m = -1;
		cin >> n >> m;
		if (n <= 0) break;
		int bm = 1 << n;
		vector<int> cost[2];
		cost[0] = vector<int>(bm, 1 << 30);
		cost[0][0] = 0;
		for (int i = 0; i < m; ++i) {
			int prev = i & 1, curr = prev ^ 1;
			int a, b, c, f = 0;
			cin >> a >> b;
			for (int j = 0; j < b; ++j) {
				cin >> c;
				f |= 1 << (c - 1);
			}
			cost[curr] = cost[prev];
			for (int j = 0; j < bm; ++j) {
				cost[curr][j | f] = min(cost[curr][j | f], a + cost[prev][j]);
			}
		}
		int ans = cost[m & 1][bm - 1];
		cout << (ans < (1 << 30) ? ans : -1) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
nn=int(input())
n=10**5+100
ar=[0]*(n)
ar[1]=0
ans=0
pre=1
for i in range(2,n):
    if ar[i]==0:

        for j in range(2*i,n,i):
            ar[j]=1
ans=1
if ar[nn]==0:
    print(nn)
else:
        
    for i in range(nn,n):
        if ar[i]==0:
            print(i)
            break
        

        

Measured memory_bytes: 3828
#include<iostream>
#define N 1000
using namespace std;

int main(){
  while(1){
    int n,q,e[N],w[N],que,f;
    string str[N];
    cin>>n>>q;
    if(n+q==0) break;
    for(int i=0;i<n;i++)cin>>str[i]>>e[i]>>w[i];
    for(int i=0;i<q;i++){
      cin>>que,f=0;
      for(int j=0;j<n;j++)if(e[j]-(w[j]-que)>0 && e[j]-(w[j]-que)<=e[j]) cout<<str[j]<<" "<<e[j]-(w[j]-que)<<endl,f=1;
      if(!f) cout<<"Unknown"<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1276
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

c = 0
for i in T:
    left = 0
    right = n
    while left < right:
        mid = (left + right)//2
        if S[mid] == i:
            c +=1
            break
        elif S[mid] > i:
            right = mid
        else:
            left = mid + 1

print(c)


Measured memory_bytes: 16704
n, m, x = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')

for i in range(2**n):
  count = [0]*(m+1)
  for j in range(n):
      if (i >> j) & 1:
        for k in range(m+1):
          count[k] += lst[j][k]
  judge = True
  for j in range(1, m+1):
    if count[j] < x:
      judge = False
      break
  if judge:
    ans = min(ans, count[0])
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Measured memory_bytes: 9244
// problem: "https://atcoder.jp/contests/abc148/tasks/abc148_e"

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll count_0(ll n)
{
    if(n%2)
        return 0;
        
    ll c = 0;
    ll i;

    i = 5;
    while(i <= n)
    {
        c += n/(i*2);
        i *= 5;
    }

    return c;
}

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

    cout<<count_0(n);       // define
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long dp[200009],arr[200009];
int bt(int x)
{
    if(dp[x]!=-1)return dp[x];
    long long &ret=dp[x];
    ret=bt(x-1)+abs(arr[x]-arr[x-1]);
    for(int i=x-1,j=1;i>=0&&j<=k;i--,j++)ret=min(bt(x-j)+abs(arr[x]-arr[x-j]),ret);
    return ret;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>arr[i];
    cout<<bt(n-1);
    //for(int i=0;i<n;i++)cout<<dp[i]<<" ";
}


Measured memory_bytes: 7296