akhauriyash/Code-Regression huggingface dataset:
//Link : https://codeforces.com/contest/1279/problem/D

#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define N 3002
#define mod 1000000007
int add(int x,int y) {
  return (x+y)%mod;
}
int mul(int x,int y) {
  return (ll)x*y%mod;
}
int dp[N][N];
int maxR[N];
char s[N];
int preNumZero[N];
int solveDp(int ind,int zero,int n) {
  if(ind>n) {
    assert(zero==0);
    return 1;
  }
  int &ret = dp[ind][zero];
  if(ret!=-1) {
    return ret;
  }
  if(maxR[ind-1]<maxR[ind]) {
    zero += preNumZero[maxR[ind]] - preNumZero[maxR[ind-1]];
  }
  int one = (maxR[ind] - preNumZero[maxR[ind]])
    - ( ind-1 - preNumZero[maxR[ind]] +zero);
  ret = 0;
  if(zero>0) {
    ret = add(ret, solveDp(ind+1,zero-1,n));
  }
  if(one>0) {
    ret = add(ret, solveDp(ind+1,zero,n));
  }
  return ret;
}
void solve() {
  int n,m;scanf("%d %d ", &n,&m);
  scanf(" %s ", s+1);
  for(int i=1;i<=n;++i) {
    preNumZero[i] = preNumZero[i-1] + (s[i]=='0' ? 1 : 0);
  }
  for(int i=0;i<m;++i) {
    int l,r;scanf("%d %d ", &l,&r);
    maxR[l] = max(maxR[l],r);
  }
  for(int i=1;i<=n;++i) {
    maxR[i] = max(maxR[i],maxR[i-1]);
    maxR[i] = max(maxR[i],i);
  }
  memset(dp,-1,sizeof(dp));
  printf("%d\n", solveDp(1,0,n));
}
int main() {
    //freopen("input.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 35712
import sys

def solve():
    input = sys.stdin.readline
    A, B, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    minP = min(A) + min(B)
    for _ in range(M):
        x, y, c = map(int, input().split())
        minP = min(A[x-1] + B[y-1] - c, minP)
    print(minP)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 18616
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define szof(a) (int)a.size()
#define allof(a) a.begin(), a.end()
#define f first
#define s second

int main() {
#ifdef LOCAL
    freopen("data.txt", "r", stdin);
#endif
    cin.tie(0);
    cin.sync_with_stdio(0);
    string s;
    int k;
    cin >> s >> k;
    int n = szof(s);
    if (count(allof(s), s[0]) == n) {
        cout << 1LL * n * k / 2 << "\n";
        return 0;
    }
    int start = -1;
    ll ans = 0;
    for (int i = 0; i < n;) {
        int j = i;
        while (j + 1 < n && s[j + 1] == s[i]) ++j;

        if (start == -1) {
            start = j - i + 1;
        }
        const int L = (j - i + 1) / 2;
        if (j < n - 1) {
            ans += 1LL * L * k;
        } else if (s[i] != s[0]) {
            ans += 1LL * L * k;
        } else {
            ans -= 1LL * (start / 2) * (k - 1);
            ans += 1LL * ((start + j - i + 1) / 2) * (k - 1);
            ans += 1LL * L;
        }
        i = j + 1;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.DeepSeq
import Data.Array
import Data.Bits
import Data.Char
import Data.Functor.Identity
import Data.List
import Data.Maybe
import Data.Ord
import Data.Tree
import Data.Tuple
import qualified System.IO
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.Sequence as Q
import qualified Data.ByteString.Char8 as B

main = do
  [a,b,c] <- getInts
  print $ solve a b c

solve a b c
  | any even [a,b,c] = 0
  | otherwise
  = let [x,y,_] = sort [a,b,c] in x*y
    

 
type Z = Int
type Q = Rational
type R = Double
type S = String

fint :: (Integral a, Num b) => a -> b
fint = fromIntegral

getInt = fst . fromJust . B.readInt <$> B.getLine
getIntPair = (\[a,b]->(a,b)) <$> getInts
getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine
getStr = B.unpack <$> B.getLine

yesNo :: Bool -> String
yesNo True = "YES"
yesNo False = "NO"

printList :: (Show a) => [a] -> IO ()
printList = putStrLn . unwords . map show

readLnList :: (Read a) => IO [a]
readLnList = map read . words <$> getLine


-----  Union-find
type UnionFindT v m a = StateT (M.Map v (UnionFindVal v)) m a
newtype UnionFindVal v = UnionFindVal v

runUnionFindT :: (Monad m) => UnionFindT v m a -> m a
runUnionFindT = flip evalStateT $ M.empty

runUnionFind = runIdentity . runUnionFindT

ufFresh :: (Monad m, Ord v) => v -> UnionFindT v m ()
ufFresh v = modify $ M.insert v (UnionFindVal v)

ufClass :: (Monad m, Ord v) => v -> UnionFindT v m v
ufClass v = do
  (UnionFindVal pv) <- gets (M.! v)
  if v == pv
    then return v
    else do
      c <- ufClass pv
      modify $ M.insert v (UnionFindVal c)
      return c

ufUnify v w = do
  cv <- ufClass v
  cw <- ufClass w
  modify $ M.insert cw (UnionFindVal cv)
  return $ cv /= cw


Measured memory_bytes: 380
#include <stdio.h>

int main (void){
	int x = 0;
	int num[100000];
	while(num[x] == 0){
		scanf("%d",&num[x]);
		if(num[x] == 0) break;
		x++;
	}

	for(int i = 0;i < x;i++){
		printf("Case %d: %d\n",i+1,num[i]);
	}

	return 0;
}

Measured memory_bytes: 1072
#

import sys
input=sys.stdin.readline
MOD=10**9+7

fact=[1]*(10**5+1)
for i in range(1,10**5+1):
    fact[i]=(fact[i-1]*i)%MOD
    
def comb(n,r):
    nhri=pow(fact[n-r],MOD-2,MOD)
    ri=pow(fact[r],MOD-2,MOD)
    return fact[n]*nhri*ri


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    
    A.sort()
    maxsum=0
    for i in range(K-1,N):
        maxsum+=comb(i,K-1)*A[i]
        maxsum%=MOD
    
    A.sort(reverse=True)
    minsum=0
    for i in range(K-1,N):
        minsum+=comb(i,K-1)*A[i]
        minsum%=MOD
        
    print((maxsum-minsum)%MOD)
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 88760
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,j,v;
    cin>>N;
    int A[N];
    for(int i=0;i<N;i++)cin>>A[i];
    for(int i=0;i<N;i++){
        j=i-1;
        v=A[i];
        while(j>=0&&A[j]>v){
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=v;
        for(int k=0;k<N;k++){
            cout<<A[k];
            if(k!=N-1)cout<<" ";
        }
        cout<<endl;
    }
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define readll(x) scanf("%I64d",&x)
#define mod 1000000007
#define eps 1e-6
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n,m;
bool v[N];
vvi g(N);
vi f,s;

void dfs(int i, vi &nodes){
    v[i] = 1;
    nodes.pb(i);
    for(int j : g[i]) if(!v[j]){
        dfs(j, nodes);
        return;
    }
}

int main(){
    read2i(n,m);
    lp(i,1,m){
        int a,b;
        read2i(a,b);
        g[a].pb(b);
        g[b].pb(a);
    }

    v[1] = 1;
    dfs(g[1][0], f);
    lp(i,1,sz(g[1])-1) if(!v[g[1][i]]){
        dfs(g[1][i], s);
        break;
    }

    println(1 + sz(f) + sz(s));
    while(sz(f)) printf("%d ",f.back()), f.pop_back();
    printf("1 ");
    for(int i : s) printf("%d ",i);
}

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//ios::sync_with_stdio(0);cin.tie(0);


Measured memory_bytes: 9720
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
class code{
private:
    int a;
public:
    void setValue(int n)
    {
        a=n;
        cout<<pow(a,3)<<endl;
    }
};
int main()
{
    int m;
    cin>>m;
    code s;
    s.setValue(m);
    std::cin.get();
}


Measured memory_bytes: 892
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);


int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    ll W,H,N; cin>>W>>H>>N;
    ll XM=0,Xm=W,YM=0,Ym=H;
    vector<ll> X(N);
    vector<ll> Y(N);
    vector<ll> A(N);
    rep(i,N){
        cin>>X[i]>>Y[i]>>A[i];
    }
    
    rep(i,N){
        if(A[i]==1){
            chmax(XM,X[i]);
        }
        if(A[i]==2){
            chmin(Xm,X[i]);
        }
        if(A[i]==3){
            chmax(YM,Y[i]);
        }
        if(A[i]==4){
            chmin(Ym,Y[i]);
        }
    }
    
    cout<<max(0ll,Xm-XM)*max(0ll,Ym-YM)<<endl;
}


Measured memory_bytes: 3616
#include<stdio.h>
int main(void)
{
	int a,b,c,d,x,y;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	x=a*b;
	y=c*d;
	if(x<=y){
		printf("%d\n",y);
	}
	else{
		printf("%d\n",x);
	}
		return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <list>
#define N 100000
using namespace std;
int n;
list<int> adj[N];
bool f[N] = {};
int g[N] = {};


void setGraphNum(int v, int i)
{
    g[v] = i;
    f[v] = true;
    list<int>::iterator itr = adj[v].begin();
    while (itr != adj[v].end())
    {
        if (!f[*itr])
            setGraphNum(*itr, i);
        itr++;
    }
}
void CalcGraphNum()
{
    int k = 1;
    for (int i = 0; i < n; i++)
    {
        if (g[i] == 0)
            setGraphNum(i, k++);
    }
}

int main()
{
    int m, u, v, q;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    CalcGraphNum();
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> u >> v;
        if (g[u] == g[v])
            printf("yes\n");
        else
            printf("no\n");
    }

    return 0;
}


Measured memory_bytes: 14412
#include<stdio.h>

typedef struct Card{
  char name;
  int number;
}card;

void bubbleSort(card [],int);
void selection(card [],int);
void phyouzi(card [],int);
int isStable(card [],card [],int);

int main(){
  card c1[100],c2[100];
  int i,n;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf(" %c%d",&c1[i].name,&c1[i].number);
    c2[i]=c1[i];
  }
  
  bubbleSort(c1,n);
  selection(c2,n);

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

    if(i==n-1){
      printf("%c%d",c1[i].name,c1[i].number);
    }
    else{
      printf("%c%d ",c1[i].name,c1[i].number);
    }

  }
  printf("\n");

  printf("Stable\n");
  
  for(i=0;i<n;i++){
    
    if(i==n-1){
      printf("%c%d",c2[i].name,c2[i].number);
    }
    else{
      printf("%c%d ",c2[i].name,c2[i].number);
    }
  }
  printf("\n");

  if(isStable(c1,c2,n)){
    printf("Stable\n");
  }
  else{
    printf("Not stable\n");
  }
  return 0;
}

void bubbleSort(card x[],int n){
  int i,j;
  card tmp;
  
  for(i=0;i<n;i++){
    for(j=n-1;j>=i+1;j--){
      if(x[j].number<x[j-1].number){
	tmp=x[j];
	x[j]=x[j-1];
	x[j-1]=tmp;
      }
    }
  }
}

void selection(card x[],int n){
  int i,j,minj;
  card tmp;
  
  for(i=0;i<n;i++){
    minj=i;
    for(j=i;j<n;j++){
      if(x[j].number<x[minj].number) minj=j;
    }
    tmp=x[i];
    x[i]=x[minj];
    x[minj]=tmp;
  }
}
void phyouzi(card x[],int n){
  int i;

  for(i=0;i<n;i++){
    if(i>0){
      printf(" ");
    }
    printf("%c%d",x[i].name,x[i].number);
  }
  printf("\n");
}

int isStable(card c1[],card c2[],int n){
  int i;
  for(i=0;i<n;i++){
    if(c1[i].name != c2[i].name)
      return 0;
  }
  return 1;
}




Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    ll you = 0, opponent = 0,time;
    cin >> time;
    repi(i,time,0){
        string y,o;
        cin >> y >> o;
        y>o?you+=3:y==o?you++,opponent++:opponent+=3;
    }
    cout << you << " " << opponent << endl;
    return 0;
}


Measured memory_bytes: 3236
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 2000000000000
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int c=0;
    for(int i=1;i<=n;++i)
    {
        if(i%2==0)
            continue;
        int co=0;
        for(int j=1;j<=i;++j)
        {
            if(i%j==0)
                ++co;
        }
        if(co==8)
            ++c;
    }
    cout<<c;
}

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

using namespace std;

int solve(const vector<string>& board, int K){
	const int H = board.size();
	const int W = board[0].size();
	queue<pair<int,int>> qu;
	vector<vector<int>> step(H, vector<int>(W, -1));
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(board[i][j] == 'S'){
				qu.emplace(i, j);
				step[i][j] = 0;
			}
		}
	}
	while(!qu.empty()){
		auto p = qu.front(); qu.pop();
		int h = p.first, w = p.second;
		if(h == 0 || h == H-1 || w == 0 || w == W-1) return 1;
		if(step[h][w] == K) continue;
		int dx[] = {-1, 0, 1, 0};
		int dy[] = {0, -1, 0, 1};
		for(int d=0;d<4;d++){
			int nh = h + dx[d], nw = w + dy[d];
			if(nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
			if(board[nh][nw] == '#') continue;
			if(step[nh][nw] != -1) continue;
			step[nh][nw] = step[h][w] + 1;
			qu.emplace(nh, nw);
		}
	}
	int res = 100000000;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(step[i][j] == -1) continue;
			res = min(res, (i+K-1)/K);
			res = min(res, (j+K-1)/K);
			res = min(res, (H-1-i+K-1)/K);
			res = min(res, (W-1-j+K-1)/K);
		}
	}
	return res + 1;
}

int main(){
	int H, W, K;
	while(cin >> H >> W >> K){
		vector<string> board(H);
		for(auto& s : board) cin >> s;
		cout << solve(board, K) << endl;
	}
}


Measured memory_bytes: 3584
#include<iostream>
#include<cstdio>

using namespace std;
#define Lens 500000
#define Max 2000000000

int A[Lens], L[Lens / 2+2], R[Lens / 2+2];
int N;
int sum = 0;

void merge(int A[], int N, int left, int right)
{
	//	cout <<left<<':'<< A[left] <<' '<<right<<':'<< A[right]<<' ';
	int mid = (left + right) / 2;
	int N1 = mid - left;
	int N2 = right - mid;
	for (int i = 0; i < N1; i++)
	{
		L[i] = A[left + i];
	}
	for (int i = 0; i < N2; i++)
	{
		R[i] = A[mid + i];
	}
	L[N1] = Max;
	R[N2] = Max;
	int tmp1 = 0, tmp2 = 0;
	for (int st = left; st < right; st++)
	{
	//	cout << left << ' ' << right << endl;
		if (L[tmp1] <= R[tmp2])
		{
			sum++;
	//		cout << A[st] << ' ' << L[tmp1] << endl;
			A[st] = L[tmp1++];
		}
		else
		{
			sum++;
	//		cout << A[st] << ' ' << R[tmp2] << endl;
			A[st] = R[tmp2++];
		}

	}
//	cout << endl;
}

void mergesort(int A[], int N, int left, int right)
{
	int mid = (left + right) / 2;

	if (right - left > 1)
	{
		mergesort(A, N, left, mid);
		mergesort(A, N, mid, right);
		merge(A, N, left, right);
	}

}


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

	mergesort(A, N, 0, N);
	for (int i = 0; i < N-1; i++)
	{
		cout << A[i] << ' ';
	}
	cout << A[N - 1] << endl;
	cout << sum << endl;
	return 0;
}


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

using namespace std;

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

int main()
{
    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r;
    REP(R) {
        int t;
        cin >> t;
        r.push_back(t);
    }
    int table[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            table[i][j] = 1e9;
        }
        table[i][i] = 0;
    }
    REP(M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        table[a][b] = c;
        table[b][a] = c;
    }
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                table[i][j] = min(table[i][j], table[i][k]+table[k][j]);
            }
        }
    }

    long long ans = 1e9;
    sort(r.begin(), r.end());
    do {
        long long d = 0;
        for (unsigned int i = 0; i < r.size() - 1; i++) {
            d += table[r[i]-1][r[i + 1]-1];
        }
        if (ans > d) {
            ans = d;
        }
    } while (next_permutation(r.begin(), r.end()));
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;
int dy[4] = { 1, 0, -1, 0 }, dx[4] = { 0, 1, 0, -1 };
const ll MOD = 1e9 + 7;
const ll INF = 1e9;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  rep(i, 3) {
    if (s[i] == s[i+1]){
      puts("Bad");
      return 0;
    }
  }
  puts("Good");
  return 0;
}


Measured memory_bytes: 764
<?php
$s = fgets(STDIN);
$t = fgets(STDIN);
$s_sp = str_split($s);
$t_sp = str_split($t);
$ans = 0;
for($i=0; $i<3; $i++) {
    if ($s_sp[$i] == $t_sp[$i]) {
        $ans++;
    }
}

echo $ans;

Measured memory_bytes: 4856
#include <iostream>

using namespace std;

typedef long long ll;
#define x first
#define y second
#define mp make_pair

ll x;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> x;
ll sol = (x / 500) * 1000;
x %= 500;
sol += (x / 5) * 5;
cout << sol << endl;

return 0;
}



Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d %d", $n, $l);
$m = $l + $n - 1;
$a = range($l, $m);
$x = array_sum($a);
if ($l > 0) {
	$x -= $a[0];
} elseif ($m < 0) {
	$x -= $a[$n-1];
}
echo $x;

Measured memory_bytes: 4604
#include <stdio.h>
#include <stdlib.h>
#define MAX 101
#define W -1
#define G -2
#define B -3

void DFS();
void visit(int);

int n,t;
int d[MAX],f[MAX],color[MAX];
int A[MAX][MAX];

int main(){
  int i,j,u,v,k;

  scanf("%d",&n);

 for(i=1 ; i<=n ; i++){
    for(j=1 ; j<=n ; j++){
      A[i][j]=0;
    }
  }

  for(i=0 ; i<n ; i++){
    scanf("%d %d",&u,&k);
    for(j=0 ; j<k ; j++){
      scanf("%d",&v);
      A[u][v]=1;
    }
  } 

  DFS();
  
  for(i=1 ; i<=n ; i++){
    printf("%d %d %d\n",i,d[i],f[i]);
  }
  
  return 0;
}

void DFS(){
  int i;
  for(i=1 ; i<=n ;i++){
    color[i]=W;
  }
  t = 0;
  for(i=1 ; i<=n ;i++){
    if(color[i]==W){
      visit(i);
    }
  }
}

void visit(int u){
  int i;

  color[u] = G;
  d[u] = ++t;

  for(i=1 ; i<=n ; i++){
    if(A[u][i]==0)continue;
    if(color[i]==W)visit(i);
  }
  color[u] = B;
  f[u] = ++t;
}

Measured memory_bytes: 640
S = input()
MOD = 10**9 + 7

M = 13
dp = [0] * M
dp[0] = 1

for s in S:
    newDp = [0] * M
    if s == '?':
        for s in range(10):
            for m in range(M):
                newDp[(m * 10 + s) % M] += dp[m]
    else:
        s = int(s)
        for m in range(M):
            newDp[(m * 10 + s) % M] += dp[m]
    dp = newDp
    for m in range(M):
        dp[m] %= MOD

print(newDp[5] % MOD)

Measured memory_bytes: 42860
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;
	b=min(b,2*a);
	c=min(c,2*b);
	d=min(d,2*c);
	e=4*e;
	ll ans=0;
	ans+=(e/8)*d;
	e=e%8;
ll dp[8]={0,a,b,a+b,c,c+a,c+b,c+a+b};
ans+=dp[e];
cout<<ans;
return 0;	
}

Measured memory_bytes: 256
n = gets.to_i
xs = gets.chop
xi = xs.to_i(2)
init_count = xs.count('1')
p_init_count = init_count + 1
m_init_count = init_count - 1
pxi = xi % p_init_count
mxi = xi % m_init_count if m_init_count > 0
ans = []
(n-1).downto(0) do |i|
  if xi[i].zero?
    t = (pxi + 2.pow(i,p_init_count)) % p_init_count
  else
    if m_init_count.zero?
      puts 0
      next
    end
    t = (mxi - 2.pow(i,m_init_count)) % m_init_count
  end
  c = 1
  until t == 0
    t %= t.to_s(2).count('1')
    c += 1
  end
  puts c
end

Measured memory_bytes: 14720
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x=0):x((x%mod+mod)%mod){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint comb(int a, int b){
	mint c=1;
	rep(i, b) c*=(a-i);
	mint d=1;
	for(int i=1; i<=b; i++) d*=i;

	return c/d;
}

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

	mint ans=0;
	for(int k=1; k<=n/3; k++){
		if(k==1) ans+=1;
		else{
			int a=k-1, b=n-3*k;
			ans+=comb(a+b, a);
		}
	}

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


Measured memory_bytes: 3636
#include<stdio.h>
int main(void){
  int n;
  scanf("%d",&n);
  int a[n];
  long long y=0,z=0;
  long mod=1000000007;
  for(int i=0;i<n;i++){
	scanf("%d",&a[i]);
  }
  long long b=0,sum=0;
  for(int i=1;i<n;i++){
	b=(b+a[i-1])%mod;
    sum=(sum+a[i]*b)%mod;
  }
  printf("%lld",sum); 
  return 0;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

int main(void){
	int n, m;
	cin >> n >> m;

	int k, s;
	vector< vector<int> > v(m);
	REP(i, m){
		cin >> k;
		REP(j, k){
			cin >> s;
			v[i].push_back(s-1);
		}
	}

	vector<int> p(m);
	REP(i, m){
		cin >> p[i];
	}

	int ans = 0, flg;
	vector<bool> light(m);
	REP(i, 1 << n){
		REP(j, m) light[j] = 0;
		//cout << "***" << i << "***" << endl;
		REP(j, m){
			REP(k, v[j].size()){
				if(i&(1 << v[j][k])){
					light[j] = !light[j];
					//cout << k << "->" << j << ':' << light[j] << endl;
				}
			}
		}

		flg = 1;
		REP(j, m){
			if(light[j] != p[j]) flg = 0;
		}
		if(flg){
			//cout << "ok" << endl;
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
//using System.Numerics;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    Random rnd = new Random();
    Stopwatch sw = new Stopwatch();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";
    readonly string ALFA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    int N;
    void solve()
    {
        N = cin.nextint;
        WriteLine($"ABC{N}");
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13264
import sys
sys.setrecursionlimit(10**7)
from collections import deque

n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > n:
    print("Impossible")
    exit()

e = [[] for i in range(n)]
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    e[x].append(y)
    e[y].append(x)

def dfs(x):
    l = []
    d[x] = 1
    l.append(a[x])
    q = deque([])
    q.append(x)
    while q:
        now = q.pop()
        for nex in e[now]:
            if d[nex] > 0:
                continue
            l.append(a[nex])
            d[nex] = 1
            q.append(nex)
    l.sort()
    ans = l[0]
    
    for i in l[1:]:
        h.append(i)
    return ans
count = 2*(n-m-1)
d = [-1]*n
ans = 0
h = []
for i in range(n):
    if d[i] < 0:
        ans += dfs(i)
        count -= 1
if count > 0:
    h.sort()
    ans += sum(h[:count])
print(ans)



Measured memory_bytes: 32932
import math
N,L = map(int,input().split())
r = []
total=0
abs_min = 100100100100
max_applepay=0
for i in range(1,N+1):
  r.append(L+i-1)
all_applepay=sum(r)
for i in range(N):
  for j in range(N):
    if j != i:
      total+=r[j]
  if abs(all_applepay-(total)) < abs_min:
    abs_min = abs(all_applepay-(total))
    max_applepay = total
  total=0
print(max_applepay)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
  int n;
  char s[300005];
  int east=0;
  int l[300005],r[300005];
  cin>>n;
  cin>>s;
  l[0]=0;
  r[n-1]=0;
  for(int i=1;i<n;i++){
    if(s[i-1]=='W')l[i]=l[i-1]+1;
    else l[i]=l[i-1];
  }
  for(int i=n-2;i>=0;i--){
    if(s[i+1]=='E')r[i]=r[i+1]+1;
    else r[i]=r[i+1];
  }
  int min=300000;
  for(int i=0;i<n;i++){
    if(r[i]+l[i]<min){
      min=r[i]+l[i];
    }
  }
  cout<<min<<"\n";
  return 0;
}


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

using namespace std;

int n, cnt;
char x[1005];

int main() {
	scanf("%s", x);
	n = strlen(x);
	for (int i = 2; i < n - 1; i++)
		cnt += x[i] == 'C';
	cnt *= x[0] == 'A';
	for (int i = 1; i < n; i++)
		if (x[i] != 'C' && x[i] <= 'Z')
			cnt = 0;
	printf(cnt == 1 ? "AC\n" : "WA\n");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////

int main(){
    ll a,b;cin>>a>>b;
    cout<<max(max(a+b,a-b),a*b)<<endl;
    
    return 0;
}


Measured memory_bytes: 256
N,W = gets.split().map(&:to_i)
r = [0] * (W+1)

N.times do
	v,w = gets.split().map(&:to_i)
	w.upto(W) do |ri|
		if r[ri] < r[ri-w]+v
			r[ri] = r[ri-w]+v
		end
	end
end

p r.max

Measured memory_bytes: 8744
import sys


class Node:
    __slots__ = ['prev', 'next', 'id', 'val']

    def __init__(self, prev_node, next_node, id, val):
        self.prev = prev_node
        self.next = next_node
        self.id = id
        self.val = val

    def __repr__(self):
        return f'{self.id},{self.val}'


class LinkedList:
    def __init__(self):
        begin_node = Node(None, None, 0, -sys.maxsize)
        end_node = Node(None, None, 1, sys.maxsize)
        begin_node.next = end_node
        end_node.prev = begin_node
        self.Nodes = {0: begin_node, 1: end_node}
        self.id = 2
        self.cursor = self.Nodes[1]

    def move(self, d):
        if d < 0:
            for i in range(abs(d)):
                self.cursor = self.cursor.prev
        elif d > 0:
            for i in range(abs(d)):
                self.cursor = self.cursor.next

    def print_all_node(self):
        out = ''
        while self.cursor.prev is not None:
            self.cursor = self.cursor.prev

        self.cursor = self.cursor.next
        while self.cursor.next is not None:
            out += f'{self.cursor.val}\n'
            self.cursor = self.cursor.next
        print(out, end='')

    def insert(self, val):
        tmp_node = Node(self.cursor.prev, self.cursor, self.id, val)
        self.cursor.prev.next = tmp_node
        self.cursor.prev = tmp_node
        self.Nodes[self.id] = tmp_node
        self.cursor = tmp_node
        self.id += 1

    def erase(self):
        self.cursor.prev.next = self.cursor.next
        self.cursor.next.prev = self.cursor.prev
        del self.Nodes[self.cursor.id]
        self.cursor = self.cursor.next


linkedlist = LinkedList()


nq = int(input())
lines = sys.stdin.readlines()
for i in range(nq):
    query, *arg = lines[i].split()
    #print(query,arg)
    if query == '0':  # insert x
        linkedlist.insert(arg[0])
    elif query == '1':  # move d
        linkedlist.move(int(arg[0]))
    elif query == '2':  # erase
        linkedlist.erase()
    else:
        raise AssertionError

linkedlist.print_all_node()


Measured memory_bytes: 136496
// D - Binomial Coefficients
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	int N; cin>>N;
	vector<int> A(N); rep(i, N) cin>>A[i];
	sort(A.begin(), A.end());
	int n = A[N-1], r = 0;
	int mindiff = INT_MAX;
	rep(i, N-1){
		int diff = abs((n+2-1)/2 - A[i]);// |⌈n/2⌉ - ai|
		if(mindiff > diff){ mindiff = diff; r = A[i]; }
		// if(mindiff >= diff){ mindiff = diff; r = A[i]; }

		// int diff = abs(n/2 - A[i]); // |⌊n/2⌋ - ai|
		// if(mindiff >= diff){ mindiff = diff; r = A[i]; }
	}
	cout<< n <<" "<< r <<endl;
}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(){
  int a,b;cin>>a>>b;
  if(abs(a)==abs(b)){
    if(a==b){
      cout << 0 << endl;
    }else{
      cout << 1 << endl;
    }
  }else if(abs(a) < abs(b)){
    if(b>a){
      if(a>-1){
        cout << b-a << endl;
      }else{
        cout << b+a+1 << endl;
      }
    }else{
      if(a>-1){
       	cout << (0-b)-a+1 << endl;
      }else{
        cout << (0-b)-(0-a)+2 << endl;
      }
    }
  }else{
    if(a>b){
      if(b==0){
        cout << 1 + a-b << endl;
      }else if(b>-1){
        cout << 2 + a-b << endl;
      }else{
        cout << 1 + a-(0-b) << endl;
      }
    }else{
      if(b==0){
        cout << b-a << endl;
      }else if(b>-1){
        cout << 1 + (0-a)-b << endl;
      }else{
        cout << b-a << endl;
      }
    }
  }
}

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> ac(n), wa(n);
	rep(i, m) {
		int p;
		string s;
		cin >> p >> s;
		p--;
		if (ac.at(p)) {
			continue;
		}
		else if (s == "AC") {
			ac.at(p)++;
		}
		else if (s == "WA") {
			wa.at(p)++;
		}
	}
	int AC = 0, WA = 0;
	rep(i, n) {
		AC += ac.at(i);
		if (ac.at(i)) {
			WA += wa.at(i);
		}
	}
	cout << AC << " " << WA << endl;
}

Measured memory_bytes: 1152
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18) + 1;
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int n, m;
vector<int> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    if(n<1200)return cout<<"ABC"<<"\n",0;
  	if(n<2800)return cout<<"ARC"<<"\n",0;
  cout<<"AGC"<<"\n",0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<map>
#include<numeric>
//#include <bits/stdc++.h>
#include<cstring>
#include<iostream>
#include<functional>
using namespace std;
int main() {

	int N;
	cin >> N;
	cout << "ABC" << N << endl;

	return 0;
}

Measured memory_bytes: 256
def solve():
    N = int(input())
    A = list(map(int, input().split()))

    y = sum(A)
    x = 0
    mn = float('inf')
    for i in range(N-1):
        x += A[i]
        y -= A[i]
        mn = min(mn, abs(x-y))
    
    print(mn)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 76752
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <bitset>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

ll n, m;
ll c;

ll lcm(ll m, ll n) {
	if(m == 0 || n == 0) return 0;
	return ((m / __gcd(m,n)) * n);
}

ll f(vector<ll> v) {
	int k = v.size();
	c = 0;
	ll ret = 0;
	rep(i, 1<<k) {
		ll x = 1;
		int cnt = 0;
		bool ch = false;
		rep(j, k) {
			if(i & (1<<j)) {
				x = lcm(x, v[j]);
				cnt++;
			}

			if(x > n) {
				ch = true;
				break;
			}
		}

		if(x == 1LL) continue;
		if(ch) continue;

		ll o = n / x, s;

		if(o % 2 == 0) {
			s = (o / 2) * (2 * x + (o - 1) * x);
		} else {
			s = o * (x + (o - 1) * x / 2);
		}

		if(cnt % 2 == 0) {
			ret -= s;
			c -= o;
		} else {
			ret += s;
			c += o;
		}
	}

	return ret;
}

int main() {
	while(cin >> n >> m) {
		if(n == 0 && m == 0) break;

		bool flag = false;
		vector<ll> v(m);
		rep(i, m) {
			cin >> v[i];
			if(v[i] == 1) {
				flag = true;
			}
		}

		if(flag) {
			cout << fixed;
			cout.precision(20);
			cout << 0.0 << endl;
			continue;
		}

		ll sum = n * (n + 1) / 2;
		ll ret = f(v);
		ll res = sum - ret;
		double cnt = n - c;

		cout << fixed;
		cout.precision(20);
		cout << res / cnt << endl;
	}

	return 0;
}

Measured memory_bytes: 1284
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

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

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    GI3(x,a,b);
    print((abs(x-a)<abs(x-b))?"A":"B");
    return 0;
}

Measured memory_bytes: 256
use std::io::stdin;
use std::collections::HashSet;

fn main(){
    let (n, m) = getpair();
    let mut foo: HashSet<usize> = HashSet::new();
    let mut bar: HashSet<usize> = HashSet::new();
    for _ in 0..m {
        let (a, b) = getpair();
        if a==1 {foo.insert(b);}
        if b==1 {foo.insert(a);}
        if a==n {bar.insert(b);}
        if b==n {bar.insert(a);}
    }

    let mut ans = false;

    for x in &foo {
        if bar.contains(x) {
            ans = true;
            break;
        }
    }

    println!("{}", if ans { "POSSIBLE" } else { "IMPOSSIBLE" });
}

#[allow(dead_code)]
fn getline() -> String {
    let mut s = String::new();
    match stdin().read_line(&mut s){
        Ok(_) => {s.trim().to_string()}
        Err(_) => String::new()
    }
}

#[allow(dead_code)]
fn getvec<T: std::str::FromStr>() -> Vec<T>{
    let line = getline();
    line.split_whitespace().filter_map(|x| x.parse().ok()).collect()
}

#[allow(dead_code)]
fn getpair() -> (usize, usize){
    let nm = getvec();
    (nm[0], nm[1])
}

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int curr = a[0]; int first = a[0];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if ((a[i] - curr) * (curr - first) >= 0) {
            curr = a[i];
        } else {
            ans++;
            curr = a[i], first = a[i];
        }
    }
    cout << ans + 1 << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#include<list>

const int LIMIT =((1<<16)+33);
std::list<int> hashTable[LIMIT];
int h1(char *str){
  int p,p1,num,result=0;
  char c;

  for(p=0;p<strlen(str);p++){
    c=str[p];
    num=0;
    if(c=='A')num=0;
    if(c=='C')num=1;
    if(c=='G')num=2;
    if(c=='T')num=3;
    p1=(p%8)*2;
    result=((num<<p1)^result);
  }
  return result%LIMIT;
}
int h2(char *str){
  int num,result=0,b=1;
  char c;
  for(int p=0;p<strlen(str);p++){
    c=str[p];
    num=1;
    if(c=='A')num=1;
    if(c=='C')num=2;
    if(c=='G')num=3;
    if(c=='T')num=4;
    result+=num*b;
    b*=5;
  }
  return result;
}

bool find(char *str){
  int H1=h1(str);
  int H2=h2(str);
  for(std::list<int>::iterator it=hashTable[H1].begin();it!=hashTable[H1].end();it++){
    if(H2==(*it))return true;
  }
  return false;
}

void insert(char *str){
  if(find(str)==false){
    hashTable[h1(str)].push_front(h2(str));
  }
}

int main(){
  int n;
  char str[14],com[10];
  scanf("%d",&n);
  while(n--){
    scanf("%s %s",com,str);
    if(com[0]=='i'){
      insert(str);
    }else{
      printf("%s\n",find(str)?"yes":"no");
    }
  }
}




Measured memory_bytes: 12320
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int MAX_GN = MAX_N * 2 + 2;
const int INF = 1 << 29;

/* typedef */

typedef vector<int> vi;

/* global variables */

int n, m, l;
int ps[MAX_N], ks[MAX_N], dists[MAX_N][MAX_N];
vi rnbrs[MAX_GN];
int minfs[MAX_GN], prvs[MAX_GN];
int caps[MAX_GN][MAX_GN], flows[MAX_GN][MAX_GN];

/* subroutines */

/* main */

int main() {
  for (;;) {
    cin >> n >> m >> l;
    if (cin.eof()) break;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) dists[i][j] = INF;
      dists[i][i] = 0;
    }
    
    for (int i = 0; i < m; i++) {
      int a, b, d;
      cin >> a >> b >> d;
      a--, b--;
      dists[a][b] = dists[b][a] = d;
    }

    for (int i = 0; i < n; i++) cin >> ps[i];
    for (int i = 0; i < n; i++) cin >> ks[i];

    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++) {
	  int d0 = dists[i][k] + dists[k][j];
	  if (dists[i][j] > d0) dists[i][j] = d0;
	}
    
    int gn = 2 * n + 2;
    int st = 2 * n, gl = 2 * n + 1;

    for (int i = 0; i < gn; i++) rnbrs[i].clear();

    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
	if (dists[i][j] < l) {
	  rnbrs[i].push_back(j + n);
	  rnbrs[j + n].push_back(i);
	  caps[i][j + n] = INF;
	  caps[j + n][i] = 0;
	}
    
    for (int i = 0; i < n; i++) {
      rnbrs[st].push_back(i);
      caps[st][i] = ps[i];
      caps[i][st] = 0;
      rnbrs[i + n].push_back(gl);
      caps[i + n][gl] = ks[i];
      caps[gl][i + n] = 0;
    }

    memset(flows, 0, sizeof(flows));

    int max_flow = 0;

    for(;;) {
      for (int i = 0; i < gn; i++) prvs[i] = -1;
      prvs[st] = st;
      minfs[st] = INF;

      queue<int> q;
      q.push(st);

      while (! q.empty()) {
	int ui = q.front();
	q.pop();

	if (ui == gl) break;

	vi& rnbru = rnbrs[ui];
	for (vi::iterator vit = rnbru.begin(); vit != rnbru.end(); vit++) {
	  int vi = *vit;
	  int vc = caps[ui][vi] - flows[ui][vi];
	  if (prvs[vi] < 0 && vc > 0) {
	    prvs[vi] = ui;
	    minfs[vi] = (minfs[ui] < vc) ? minfs[ui] : vc;
	    q.push(vi);
	  }
	}
      }

      if (prvs[gl] < 0) break;

      int min_flow = minfs[gl];
      
      for (int j = gl; j != st;) {
	int i = prvs[j];
	flows[i][j] += min_flow;
	flows[j][i] -= min_flow;
	j = i;
      }

      max_flow += min_flow;
    }

    cout << max_flow << endl;
  }

  return 0;
}

Measured memory_bytes: 1704
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N, T, A, H;

  std::cin >> N >> T >> A;

  long double dm = 1e+9;
  
  int im = -1;

  for (int i = 0; i < N; i ++) {
    std::cin >> H;

    long double t = T - H * 0.006L, d = std::abs(A - t);

    if (d < dm) {
      dm = d;
      im = i;
    }
  }

  std::cout << im + 1 << std::endl;

  return 0;
}


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

int main(){
  int n,k,a[50],sum=0;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i];
    sum+=a[i];
  }
  sort(a,a+n);
  for(int i=0;i<n-k;i++)
    sum-=a[i];
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

//#define rep(i, rep_m) for(int i = 0; i < (int)(rep_m); i++)

int main()
{
    int tmp,color[100001];
    int n,m=1;
    int i,j;
    
    scanf("%d",&n);
    
    scanf("%d",&tmp);
    color[0] = tmp;
    
    for(i=1;i<n;i++)
    {
        scanf("%d",&tmp);
        
        if(tmp <= color[m-1])
        {
            color[m] = tmp;
            m++;
        }
        else
        {
            for(j=0;j<m;j++)
            {
                if(tmp > color[j])
                {
                    color[j] = tmp;
                    break;
                }
            }
        }
    }
    
    printf("%d\n",m);
    
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
//#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> p;
const int inf=(1<<30);
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)
	

int main(){
	ll x;
	cin>>x;
	ll t=1;
	while(x>t*(t+1)/2)t++;
	cout<<t<<endl;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
using namespace std;
int main() {
	string s;
	cin >> s;
	int n = s.length();
	bool keyence = false;
	for (int i = 0; i <= 7; ++i) {
		if (s.substr(0, i) + s.substr(n - (7 - i)) == string("keyence")) {
			keyence = true;
		}
	}
	cout << (keyence ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 888