akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define rep(i,j,n)   for(int i=j;i<n;i++)
#define scn(a)       scanf("%lld",&a)
#define scns(a,b)    scanf("%lld %lld",&a,&b)
#define print(a)     printf("%lld",a)
#define tc           ll t; scn(t); while(t--)
#define vec          vector<int>
#define pb           push_back    
#define pairs        pair<int,int>
#define f            first
#define s            second
#define all(v)       v.begin(),v.end()
#define srt(v)       sort(v.rbegin(),v.rend())
#define mem(a,b)     memset(a,b,sizeof(a))
#define nl           printf("\n")
#define maxx         1000010
#define inf          INT_MAX
#define zer          INT_MIN
ll mod=1e6+3,a,b,n,ans;

int main()
{
    scn(n);
    scns(a,b);
   
    if(a>b)
    swap(a,b);
   
    ll low=min(a-1,n-b);
    ll diff=b-a;
   
    if(diff%2)
    {
       ans=low+1;
       ans+=(diff-1)/2;
    }
    else
    ans=diff/2;
    
    print(ans);
}

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

using namespace std;


int main(){

int E,Y;

cin>>E>>Y;

if(E==0){

if(Y>=1989&&Y<=2016)cout<<"H"<<Y-1988<<endl;
if(Y>=1926&&Y<=1988)cout<<"S"<<Y-1925<<endl;
if(Y>=1912&&Y<=1925)cout<<"T"<<Y-1911<<endl;
if(Y>=1868&&Y<=1911)cout<<"M"<<Y-1867<<endl;

}
else{
if(E==1)cout<<Y+1867<<endl;
if(E==2)cout<<Y+1911<<endl;
if(E==3)cout<<Y+1925<<endl;
if(E==4)cout<<Y+1988<<endl;
}
return 0;
}


Measured memory_bytes: 3092
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

a,b,c = iim()

if c <= a+b :
    print(b+c)
else:
    print(a+2*b+1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string W;
    cin >> W;
    if (W.at(0) == 'S'){
        cout << "Cloudy" << endl;
    }

    if (W.at(0) == 'C'){
        cout << "Rainy" << endl;
    }

    if (W.at(0) == 'R'){
        cout << "Sunny" << endl;
    }
}

Measured memory_bytes: 256
def dfs(grid, start, wall, w, h):
    dxy = [(0,1), (0,-1), (1,0), (-1,0)]
    for i in range(1,h+1):
        for j in range(1,w+1):
            if grid[i][j] == '.':
                continue
            if sum([grid[i+dy][j+dx] == wall  for dx,dy in dxy]) == 0:
                return False
    return True

h,w = map(int, input().split())
wall = '.'
edges = [wall] * (w+2)
grid = [edges]
for i in range(h):
    s = input()
    grid.append([wall] + list(s) + [wall])
grid.append(edges)
print('Yes' if dfs(grid, [0,0], '#', w, h) else 'No')



Measured memory_bytes: 3064
#include<stdio.h>

int main(){

int N,M,C;
int calc;
int ans=0;
scanf("%d%d%d",&N,&M,&C);
int A[N][M];
int B[M];
for (int i = 0; i < M; i++)
{
  scanf("%d",&B[i]);
}
for (int i = 0; i < N; i++)
{
  for (int j = 0; j < M; j++)
  {
    scanf("%d",&A[i][j]);
  }
}

for (int i = 0; i < N; i++)
{
  for (int j = 0; j < M; j++)
  {
    calc += A[i][j]*B[j]; 
  }
  if((calc + C) > 0) ans++;
  calc =0;
}

printf("%d",ans);

return 0;
}

Measured memory_bytes: 256
// ------------------------------------
// Date:2018/ 2/28
// Problem:ABC 054 OneCardPoker a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

int main()
{
  int A, B;
  string output;
  cin >> A >> B;
  if (A == B) {
    output = "Draw";
  } else if (A == 1) {
    output = "Alice";
  } else if (B == 1) {
    output = "Bob";
  } else if (A > B) {
    output = "Alice";
  } else {
    output = "Bob";
  }
  cout << output << endl;
  return 0;
}



Measured memory_bytes: 256
from itertools import product

N=int(input())
A=[0]*N
L=[0]*N                    #1なら正直者、0なら真偽不明
R=[ [] for _ in range(N)]    #証言内容
for i in range(N):
  A[i]=int(input())  #証言の個数
  for j in range(A[i]):
    a,b=map(int,input().split())
    R[i].append([a,b])    
#print(R)

pro=product([0,1],repeat=N)
maxi=0
for pat in pro:
  T=[[] for _ in range(N)]
  for i,man in enumerate(pat):
    if man==1:
      for c in R[i]:
        T[c[0]-1].append(c[1])
  #print(sum(pat),pat,T)
  check=True
  for j,test in enumerate(T):
    for num in test:
      if num!=pat[j]:
        check=False
  if check:
    maxi=max(maxi,sum(pat))
    
print(maxi)

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);

    int k;
    cin >> k;
    int a,b;
    cin >> a >> b;
    bool flg=false;
    REAP(i,a,b+1){
       if(i%k==0){
           flg=true;
           break;
       }
    }
    if(flg)cout << "OK\n";
    else cout << "NG\n";
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
int M = 1e9+7;
 
int main() {
   
    //Fast IO crap
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	
   	int a;
   	cin >> a;
   	int ans = a + (a * a) + (a * a * a);
   	cout << ans;
    return 0;
}


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

int main(void){
    
    int N,M,Q;
    cin >> N >> M >> Q;
    
    int a[Q],b[Q],c[Q],d[Q];
    
    for(int i = 0; i < Q ; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    queue<vector<int>> que;
    
    for(int i = 0; i < M;i++){
        vector<int> vec;
        vec.push_back(i);
        que.push(vec);
    }
    
    vector<int> tmp;
    vector<int> pre;
    queue<vector<int>> queq;
    while(que.size()){
        
        tmp = que.front();
        //cout << tmp.size()<<endl;
        que.pop();
        // cout << "########################"<<endl;
        // cout  <<"size:"<< tmp.size() << endl;
        // cout  <<"M:"<< M << endl;
        // cout << "########################"<<endl;
        if(tmp.size()==N){
            queq.push(tmp);
            continue;
        }
        //cout << tmp[tmp.size()-1] << endl;
        for(int i = tmp[tmp.size()-1]; i < M;i++ ){
            
            pre = tmp;
            pre.push_back(i);
            // for(auto p:pre)cout << p;
            // cout << endl;
            que.push(pre);
            
        }
        //cout << que.size() << endl;
    }
    
    vector<int> calc;
    int ans = 0;
    int sum = 0;
    //cout << queq.size()<<endl;
    while (!queq.empty()) {
        calc = queq.front();
        queq.pop();
        sum = 0;
        for(int i = 0;i< Q;i++){
            //cout << calc[b[i]] <<" "<< calc[a[i]] <<" "<< c[i]<<endl;
            if(calc[b[i]] - calc[a[i]] == c[i])sum += d[i];
        }
        ans = max(sum,ans);
    }
    
    cout << ans << endl;
    
    
    
}

Measured memory_bytes: 10248
#include<stdio.h>
int main(){
  int a,b,k;
  int i;
  scanf("%d%d%d",&a,&b,&k);
  for(i=0;i<k;i++){
    if(i%2==0){
      a/=2;
      b+=a;
    }else{
      b/=2;
      a+=b;
    }
  }
  printf("%d %d\n",a,b);
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
char a[150][150];
int b[150][150],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>a[i][j];
            if(a[i][j]=='#')
            {   
				b[i-1][j-1]++;
                b[i-1][j]++;
                b[i-1][j+1]++;
                b[i][j-1]++;
                b[i][j+1]++;
                b[i+1][j-1]++;
                b[i+1][j]++;
                b[i+1][j+1]++;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(a[i][j]=='#')
            	cout<<"#";
            else 
            	cout<<b[i][j];
        }
        cout<<""<<endl;
    }
    return 0;
}

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

typedef long long ll;
typedef long double ld;
#define size(a) int((a).size())
#define present(c, x) (c.find(x) != c.end()) 
#define printArray(arr) for (int i = 0; i<size(arr); i++) cout << arr[i] << " ";cout << '\n'
#define printVerdict(verdict) cout << (verdict ? "YES": "NO") << '\n'
#define printDecimal(d) printf("%.9f\n", d)
#define inrange(val, start, end) (val >= start && val <= end)

const ll inf = 0x3f3f3f3f;

template <class T1, class T2, class T3> 
void printTuple(tuple<T1, T2, T3> t) {cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << '\n';}
template <class T1, class T2>
void printPair(pair<T1, T2> p) {cout << p.first << " " << p.second << '\n';}

vector<int> dp(1e5+1, 0);
map<int, vector<int>> graph;
bool visited[100001];

void dfs(int curr) {
	visited[curr] = true;
	for (int parent : graph[curr]) {
		if (!visited[parent]) dfs(parent);
		dp[curr] = max(dp[curr], dp[parent] + 1); 
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> n >> m;
	
	for (int i = 0; i<m; i++) {
		int x,y; cin >> x >> y;
		graph[y].push_back(x);
	}
	for (int i = 1; i<=n; i++) {
		if (!visited[i]) dfs(i);
	}
	int ret = dp[1];
	for (int i = 2; i<=n; i++) {
		ret = max(ret, dp[i]);
	}
	cout << ret << '\n';
}



Measured memory_bytes: 23732
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long
const double pi = acos(-1.0);

int n;

int main() {
#ifdef LOCAL
  auto start_clock = clock();
  freopen("in", "r", stdin);
#endif
  scanf("%d", &n);
  vector<int> a(n + 1, 0);
  for (int i = 1; i * i <= n; i++) {
    for (int j = 1; j * j <= n; j++) {
      for (int k = 1; k * k <= n; k++) {
        int w = i * i + j * j + k * k + i * j + i * k + j * k;
        if (w <= n) {
          a[w] += 1;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    printf("%d\n", a[i]);
  }



#ifdef LOCAL
 auto end_clock = clock();
 cout << "Time:" << (end_clock - start_clock) / CLOCKS_PER_SEC << endl;
#endif
  return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define M 1000000007
#define int long long
#define sz(c) (int)c.size()
#define first first
#define ll long long 
#define second second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define N 1000005
#define U 998244353
#define bs binary_search
#define endl '\n'
#define FILEIO     firsteopen("input.txt","r",stdin); firsteopen("output.txt","w", stdout);
using namespace std;
#define PI 3.1415926535
int po(int n, int exp){
    int prod=1;
    rep(i,0,exp)
        prod*=n;
    return prod;
}
int lcm(int a, int b){
    int g = __gcd(a,b);
    return (a/g)*b;
}
map<int,int> primeFactors(int n)  
{   
    map<int,int> ans;
    while (n % 2 == 0)  
    {  
        ans[2]++;
        n = n/2;  
    }  
    for (int i = 3; i <= sqrt(n); i = i + 2)  
    {    
        while (n % i == 0)  
        {  
            ans[i]++;
            n = n/i;  
        }  
    }  
    if (n > 2)  
        ans[n]++;
    return ans;
}
int gcd(int a, int b, int &x, int &y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd(b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int TESTS=1;
    // cin>>TESTS;
    while(TESTS--)
    {
        int n,x;
        cin>>n>>x;
        int cum[n]={};
        rep(i,0,n){
            int t;
            cin>>t;
            if(i==0) cum[i] = t;
            else cum[i] = cum[i-1]+t;
        }
        // rep(i,0,n) cout<<cum[i]<<" ";
        // cout<<endl;
        cout<<upper_bound(cum,cum+n,x)-cum+1;
    }
}   

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define INF 100000000000
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using P = pair<int, int>;

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}


int main()
{
    int a, b, m;
    cin >> a >>b >> m;
    vector<int> arra(a), arrb(b);
    rep(i,a) cin >> arra[i];
    rep(i,b) cin >> arrb[i];

    int discount[m][3];
    rep(i,m) {
        rep(j,3) {
            cin >> discount[i][j];
        }
    }
    
    vector<int> tmpv;
    tmpv = arra;
    int ans = 0;
    sort(tmpv.begin(), tmpv.end());
    ans += tmpv[0];
    tmpv = arrb;
    sort(tmpv.begin(), tmpv.end());
    ans += tmpv[0];

    rep(i,m) {
        int tmp = arra[discount[i][0]-1] + arrb[discount[i][1]-1] - discount[i][2];
        ans = min(tmp, ans) ;
    }

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


Measured memory_bytes: 2560
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int top, S[1000];

void push(int x) {
    S[++top] = x;
}

int pop() {
    top--;
    return S[top + 1];
}

int main() {
    int a, b;
    top = 0;
    char s[100];
    
    while (scanf("%s", s) != EOF) {
        if (s[0] == '+') {
            a = pop();
            b = pop();
            push(a + b);
        } else if (s[0] == '-') {
            b = pop();
            a = pop();
            push(a - b);
        } else if (s[0] == '*') {
            a = pop();
            b = pop();
            push(a * b);
        } else {
            push(atoi(s));
        }
    }
    
    printf("%d\n", pop());

    return 0;
}


Measured memory_bytes: 2140
#include<stdio.h>
#include<stdlib.h>

int main(void)
{
    int N;
    int A[100] = {0};
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
    {
        scanf("%d", &A[i]);
    }

    for (int j = 0; j < N; j++)
    {
        if (A[j] % 2 == 0)
        {
            if ((A[j]%3 != 0) && (A[j]%5 != 0))
            {
                printf("DENIED");
                exit(0);
            }
            
        }
        
    }
    
    printf("APPROVED");
    
    return 0;
}

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

using namespace std;

int N[100001];
bool visited[100001];

bool bfs(vector<vector<int>> &graph, int n){
    queue<vector<int>> qu;
    qu.push({1, 1});
    visited[1] = true;
    int cnt = 0;
    while(!qu.empty()){
        vector<int> node = qu.front();
        qu.pop();
        cnt++;
        N[node[0]] = node[1];
        for(int child : graph[node[0]]){
            if(!visited[child]){
                visited[child] = true;
                qu.push({child, node[0]});
            }
        }
    }
    return cnt == n;    
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n+1);
    for(int i=0; i<m; i++){
        int a, b;
        cin >>a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    bool found = bfs(graph, n);
    if(found){
        cout << "Yes" << '\n';
        for(int i=2; i<=n; i++)
            cout << N[i] << '\n';
    }
    else
        cout << "No";
    return 0;
}


Measured memory_bytes: 15296
N = int(input())
D = list(map(int, input().split()))

if D[0] != 0:
    print(0)
    exit()

c = {}
for i in D:
    c.setdefault(i, 0)
    c[i] += 1

if c[0] != 1:
    print(0)
    exit()

result = 1
for i in range(1, max(D) + 1):
    if i not in c:
        print(0)
        exit()
    result *= pow(c[i - 1], c[i], 998244353)
    result %= 998244353
print(result)

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

typedef long long ll;
ll h, w;
ll ans = 1e10;
int main()
{
    cin >> h >> w;
    for (ll i = 0; i < h; i++)
    {
        ll a = (h - i) / 2 * w;
        ll mx = max(w * i, max(a, (h - i) * w - a));
        ll mn = min(w * i, min(a, (h - i) * w - a));
        ans = min(ans, mx - mn);
        a = w / 2 * (h - i);
        mx = max(w * i, max(a, (h - i) * w - a));
        mn = min(w * i, min(a, (h - i) * w - a));
        ans = min(ans, mx - mn);
    }
    swap(h, w);
    for (ll i = 0; i < h; i++)
    {
        ll a = (h - i) / 2 * w;
        ll mx = max(w * i, max(a, (h - i) * w - a));
        ll mn = min(w * i, min(a, (h - i) * w - a));
        ans = min(ans, mx - mn);
        a = w / 2 * (h - i);
        mx = max(w * i, max(a, (h - i) * w - a));
        mn = min(w * i, min(a, (h - i) * w - a));
        ans = min(ans, mx - mn);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())

G = [['.'] * (W + 2)]
for _ in range(H):
    tmp = ['.'] + list(input()) + ['.']
    G.append(tmp)

tmp = ['.'] * (W + 2)
G.append(tmp)

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if G[i][j] == '#':
            flag = False
            for dx, dy in move:
                if G[i + dx][j + dy] == '#':
                    flag = True
                    break
            if not flag:
                print ('No')
                exit()

print ('Yes')

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

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

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))
#define INF (1<<28)
#define pb push_back
#define fs first
#define sc second

const char dx[]={0,1,0,-1},dy[]={1,0,-1,0};
template<class T>
ostream &operator<<(ostream &out, const vector<T> &v){
	out << "{";
	rep(i,v.size()) out << v[i] << ", " ;
	return out << "}" << endl;
}
template<class S,class T>
ostream &operator<<(ostream &out, const pair<S,T> p){
	return out << "(" << p.fs << ", " << p.sc << ")";
}

int main(){
	int n;
	cin >> n;
	vi a(n);
	ll sum=0;
	rep(i,n){
		cin >> a[i];
		sum += a[i];
	}
	ll ans = 0, t = 0, m = (1ll<<40);
	rep(i,n-1){
		t += a[i];
		ll tmp = abs(sum - 2*t);
		if(tmp < m) {
			ans = i;
			m = tmp;
		}
	}
	cout << m << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int ll
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;

signed main(){
	FASTIO
	int h, w, m;
	cin >> h >> w >> m;
	map<int, set<int> > mp;
	int r[h] = {0}, c[w] = {0};
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		mp[x].insert(y);
		r[x-1]++;
		c[y-1]++;
	}
	int mx = *max_element(r, r + h);
	vector<int> rw, cl;
	for(int i = 0; i < h; i++){
		if(r[i] == mx)
			rw.push_back(i+1);
	}
	int ans = mx;
	mx = *max_element(c, c + w);
	ans += mx;
	ans--;
	for(int i = 0; i < w; i++){
		if(c[i] == mx)
			cl.push_back(i+1);
	}
	bool f = true;
	for(int i = 0; i < rw.size() && f; i++){
		for(int j = 0; j < cl.size(); j++){
			if(mp[rw[i]].find(cl[j]) == mp[rw[i]].end()){
				ans++;
				f = false;
				break;
			}
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 58472
N = int(input())
S = input()

wh = [0] * (N+1)
bl = [0] * (N+1)

for i in range(N):
    if S[i] == "#":
        bl[i+1] = bl[i] + 1
    else:
        bl[i+1] = bl[i]
        
    if S[N-1-i] == ".":
        wh[N-1-i] = wh[N-i] + 1
    else:
        wh[N-1-i] = wh[N-i]
        


ans = 1145141919810

for i in range(N+1):
    if bl[i] + wh[i] < ans:
        ans = bl[i] + wh[i]
        
print(ans)

Measured memory_bytes: 12804
N, M = map(int, input().split())
py = sorted([list(map(int, input().split()))+[i] for i in range(M)], key=lambda x:x[1])
count = [1] * N
ans = [None] * M

for i in range(M):
  p, y, num = py[i]
  ans[num] = "{:0>6}{:0>6}".format(p, count[p-1])
  count[p-1] += 1

for i in range(M):
  print(ans[i])

Measured memory_bytes: 32520
#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define REP(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<ll> vl;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
template <class T> inline void chmax(T &a, T b) { a < b ? a = b : a; };
template <class T> inline void chmin(T &a, T b) { a > b ? a = b : a; };

int main() {
    int r, g, b, n, res;
    cin >> r >> g >> b >> n;
    rep(i, 3001) rep(j, 3001) {
        if(0 <= n - r * i - g * j && (n - r * i - g * j) % b == 0) {
            res++;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int> 
#define pdd pair<ld, ld> 
#define mp make_pair
#define pb push_back
#define reset(x,v) memset(x,v,sizeof(x))
#define mod 1000000007
using namespace std;
int n, a, b, c;
ll solve(ll l[], int i, ll a1, ll b1, ll c1){
    if(i == n){
        if(a1 == 0 || b1 == 0 || c1 == 0)
        return INT_MAX;
        return abs(a-a1) + abs(b-b1) + abs(c-c1);
    }
    ll ans = solve(l, i + 1, a1, b1, c1);
    ans = min(ans , (a1?10:0) + solve(l, i + 1, a1 + l[i], b1, c1));
    ans = min(ans , (b1?10:0) + solve(l, i + 1, a1, b1 + l[i], c1));
    ans = min(ans , (c1?10:0) + solve(l, i + 1, a1, b1, c1 + l[i]));
    return ans;
}
int main(){
    FASTIO
    cin >> n >> a >> b >> c;
    ll l[n];
    rep(i, 0, n)
    cin >> l[i];
    cout << solve(l, 0, 0, 0, 0);
    return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N;
  cin >> N;

  vector<PII> xs(N);
  REP(i,N){
	char c;
	cin >> c >> xs[i].FF;
	xs[i].SS = c == 'y';
  }

  function<int(int,int,int)> dfs = [&](int l, int r, int ub){
	if(l >= r) return 0;
	int res = 0;
	int h = -1, k = -1, n = 0, m = 0;
	for(int i=l;i<r;++i){
	  if(xs[i].FF >= ub) continue;
	  if(xs[i].SS == 0){
		++n;
		if(h < xs[i].FF){
		  h = xs[i].FF;
		  k = i;
		}
	  }
	  else ++m;
	}
	if(n == 0 || m == 0){
	  return m? 1: 0;
	}

	int lg = 0, rg = 0;
	FOR(i,l,k){
	  if(xs[i].SS && h < xs[i].FF && xs[i].FF < ub){
		++lg;
		break;
	  }
	}
	FOR(i,k+1,r){
	  if(xs[i].SS && h < xs[i].FF && xs[i].FF < ub){
		++rg;
		break;
	  }
	}
	if(lg && rg){
	  res += min(dfs(l, k, h+1) + dfs(k+1, r, h+1) + 1,
				 dfs(l, k, ub) + dfs(k+1, r, ub));
	}
	else{
	  res += dfs(l, k, ub) + dfs(k+1, r, ub);
	}

	return res;
  };

  cout << dfs(0, N, 1e9) << endl;

  return 0;
}

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



long long p = 5e9;

long long isprime(long long n){
	for( long long i = 2 ; i * i <= n ; i++ ){
		if( n % i == 0 ) return 0;
	}
	return 1;
}

inline long long mul(long long a,long long b){
	long long res = 0;
	while( b ){
		if(b&1){
			res += a;
			if( res >= p ) res -= p;
		}
		a *= 2;
		if( a >= p ) a -= p;
		b >>= 1;
	}
	return res;
}

inline long long bpow(long long a,long long b){
	long long res = 1;
	while( b ){
		if(b&1){
			res = mul(res,a);
			res %= p;
		}
		a = mul(a,a);
		b >>= 1;
	}
	return res;
}


int main(){
	while( !isprime(p) ) p++;

	int N;
	cin >> N;
	long long X = 0;
	for(int i = 0 ; i < N ; i++){
		long long op,Y;
		scanf("%lld %lld",&op,&Y);
		Y=(Y+p)%p;
		if( op == 1 ){ //+
			X = X + Y;
			X %= p;
		}else if( op == 2 ){ //-
			X = X - Y;
			X %= p;
		}else if( op == 3 ){ //*
			X = mul(X,Y);
		}else{ // /
			X = mul(X,bpow(Y,p-2));
		}
		X = (X+p) % p;
	}
	if( X < (1ll<<31) ){
		cout << X << endl;
	}else{
		cout << X-p << endl;
	}
}

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

void readtxt()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

int main() {
	//readtxt();
	int k;
	int a, b;
	cin >> k;
	cin >> a >> b;
	int flag = 0;
	for(int i = a; i<=b; i++)
	{
		if(i%k==0)
		{
			flag = 1;
			cout << "OK" << endl;
			break;
		}
	}
	if(flag==0)
	{
		cout << "NG" << endl;
	}
    
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
using R = double;
using Data = pair < ll, vector <ll>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 60;
struct edge { ll from; ll to; ll cost; };
typedef tuple<ll, ll, ll>T;
typedef pair<ll, ll>pll;
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2

int N, M;
vector<ll>e[101010];
vector<ll>dp[101010];
ll ans[101010];

ll dfs(ll p, ll v) {
	ll ret = 1;
	rep(i, 0, e[v].size()) {
		if (e[v][i] != p) {
			dp[v][i] = dfs(v,e[v][i]);
			(ret *= (dp[v][i] + 1)) %= M;
		}
	}
	return ret;
}
void dfs2(ll p,ll v, ll mul) {
	ll sz = e[v].size();
	rep(i, 0, sz) {
		if (e[v][i] == p) {
			dp[v][i] = mul;
			break;
		}
	}

	vector<ll>L(sz), R(sz);
	rep(i,0,sz)R[i] = ((L[i] = (dp[v][i] + 1)) %= MOD);
	rep(i, 1, sz)(L[i] *= L[i-1])%=M;
	rrep(i,sz-2,0)(R[i] *= R[i + 1])%=M;
	rep(i, 0, sz) {
		if (e[v][i] == p)continue;
		ll add_c = 1;
		if (i != 0)(add_c *= L[i-1]) %= M;
		if (i != sz - 1)(add_c *= R[i + 1]) %= M;
		dfs2(v, e[v][i], add_c);
	}
}


int main(){
	cin >> N >> M;
	rep(i, 0, N - 1) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		e[x].pb(y);
		e[y].pb(x);
	}
	rep(i, 0, N)dp[i].resize(e[i].size());
	dfs(-1, 0);
	dfs2(-1,0,0);

	rep(i, 0, N) {
		ll ans = 1;
		fore(x, dp[i])(ans *= (x + 1))%=M;
		cout << ans << endl;
	}
	
	
	return 0;
}



Measured memory_bytes: 22528
W,H,N=map(int,input().split())
xl=0
xh=W
yl=0
yh=H
allblack=False
for _ in range(N):
    x,y,a = map(int,input().split())
    if a==1:
        xl=max(xl,x)
    elif a==2:
        xh=min(xh,x)
    elif a==3:
        yl=max(yl,y)
    else:
        yh=min(yh,y)
    if xl>=xh or yl>=yh:
        allblack=True
        break
print(0 if allblack else (xh-xl)*(yh-yl))

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> L(N);
  for(int i = 0; i < N; i++) {
    cin >> L.at(i);
  }
  int n = 1;
  int D = 0;
  for(int i = 0; i < N; i++) {
    D += L.at(i);
    if(D > X) {
      break;
    }
    n++;
  }
  cout << n << endl;
}

Measured memory_bytes: 256
//templates
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <sstream>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define sort_key(struct_name,key_name) [](const struct_name &x, const struct_name &y){return x.key_name < y.key_name;}
#define pb(x) push_back(x)
typedef long long ll;
const ll MOD = 1e9 + 7;
using namespace std;

//main
ll GCD(ll a, ll b);
ll GCD(ll a);

int main(){
    int N; cin >> N;
    vector<ll> A(N), gcdL{0}, gcdR{0}, ans(N);
    rep(i,N) cin >> A[i];
    vector<ll> B = A;
    reverse(ALL(B));
    rep(i,N-1){
        gcdL.pb(GCD(gcdL[i],A[i]));
        gcdR.pb(GCD(gcdR[i],B[i]));
    }
    reverse(ALL(gcdR));
    rep(i,N) ans[i] = GCD(gcdL[i],gcdR[i]);
    cout << *max_element(ALL(ans)) << endl;

}

ll GCD(ll a, ll b){
    ll r, temp;
    if(a == 0) return b;
    else if (b == 0) return a;
    else{
        if(a<b){
            temp = a;
            a = b;
            b = temp;
        }
        r =  a%b;
        while(r!=0){
            a = b;
            b = r;
            r = a%b;
        }
        return b;
    }
}



Measured memory_bytes: 4340
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    ll A[N]; F0R(i, N) cin >> A[i];
    F0R(i, N) {
        if (A[i] == 0) {
            cout << 0 << nl; return 0;
        }
    }
    ld L = 0;
    F0R(i, N) {
        L += log10(A[i]);
    }
    if (L > 18.1) {
        cout << -1 << nl; return 0;
    }
    ll ans = 1; F0R(i, N) ans *= A[i];
    if (ans > 1000000000000000000) {
        cout << -1 << nl; return 0;
    }
    cout << ans << nl;
	
	return 0;
}

Measured memory_bytes: 4608
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<iso646.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>

#define FOR(counter,initial_value,condition) for(int counter = initial_value; counter < condition;counter++)

int main()
{
	int x, a, b;
	std::string condition;
	std::cin >> x >> a >> b;
	if (b - a > x) condition = "dangerous";
	else if (b > a) condition = "safe";
	else condition = "delicious";
	std::cout << condition << std::endl;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;
int a[200006];
int ans[200006];
signed main() {
	int n; cin >> n;
	rep(i, n)cin >> a[i];
	for (int i = n; i > 0; i--) {
		int cnt = 0;
		for (int j = i+i; j <= n; j += i) {
			cnt += ans[j];
		}
		cnt &= 1;
		if (a[i-1] != cnt)ans[i] = 1;
	}
	vector<int>V;
	rep(i, n)if (ans[i + 1])V.push_back(i + 1);
	cout << V.size() << endl;
	rep(i, V.size()) {
		if (i)cout << ' '; cout << V[i];
	}cout << endl;
}

Measured memory_bytes: 4852
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,y;
  cin>>n>>y;
  for(int i=y/10000;i>=0;i--){
    for(int j=0;j<=n-i;j++){
      int k=n-i-j;
      if(i*10000+j*5000+k*1000==y){
        cout<<i<<" "<<j<<" "<<k;
        return 0;
      }
    }
  }
  cout<<"-1 -1 -1";
}

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

const int mo = 1e9 + 7;
const int N = 1e5 + 10;

int n, k, ans;
int L[N], R[N], val[N], pos[N], cnt, sum[2][N]; //dp[i][j]前i位, a[i]值为L[i] ~ R[i]

int main() {
	scanf("%d%d", &k, &n);
	for(int l = 1, r; l <= k; l = r + 1) {
		r = k / (k / l);
		L[++ cnt] = l; R[cnt] = r; val[cnt] = k / l;
	}
//	printf("cnt = %d\n", cnt);
	for(int i = 1; i <= cnt; i ++) {
		sum[0][i] = 1;
		pos[i] = upper_bound(L + 1, L + cnt + 1, val[i]) - L - 1;
	}
	int cur = 1;
	for(int i = 1; i <= n; i ++, cur ^= 1) {
		for(int j = 1; j <= cnt; j ++) {
			sum[cur][j] = (sum[cur][j - 1] + sum[cur ^ 1][pos[j]] * 1ll * (R[j] - L[j] + 1) % mo) % mo;
		}
	}
	printf("%d\n", sum[cur ^ 1][cnt]);
	return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

bool check(char c){
    if(c == 'A' || c == 'G' || c == 'C' || c == 'T') return true;
    else return false;
}

int main(){
    string s; cin >> s;
    s += '8'+ s + '8';
    
    bool flg = false;
    int ans = 0;

    int tmp = 0;
    for(int i=0; i<s.size(); i++){
        if(flg == false && check(s[i])){
            flg = true;
            tmp++;
        }
        else if(flg == true && check(s[i])){
            tmp++;
        }
        else if(flg == true && !check(s[i])){
            flg = false;
            ans = max(ans, tmp);
            tmp = 0;
        }
    }

    cout << ans << endl;
    
}

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

int main () {

    int n;
    cin >> n;

    int p[n];
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        if ((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i+1] < p[i] && p[i] < p[i-1])) {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
	int a,b=0,c,d,e,f;
	char op;
	for(;;)
	 {
	cin>>a>>op>>b;
	if(op=='+'){
		 cout<<a+b<<endl;
	 }
	 else if(op=='-'){
		 cout<<a-b<<endl;
	 }
	 else if(op=='*'){
		 cout<<a*b<<endl;
	 }
	 else if(op=='/'){
		 cout<<a/b<<endl;
	 }
	 else if(op=='?'){
	 
	break;
	 }
	}
	return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define qwq(x) cerr<<" #"<<#x<<" = "<<x<<endl;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
 
template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=1000005;
int ans[N],c[N],f[N];
pii p[N];
int n,x;

int main(){
	read(n);
	rep(i,1,n){
		read(x);
		f[x]=i;
		c[i]=i-1;
		p[i]=mp(x,i);
	}
	sort(p+1,p+n+1);
	rep(i,1,n*n)
		if(!f[i]){
			int t=lower_bound(p+1,p+n+1,mp(i,0))-p;
			int k=0;
			rep(j,t,n)
				if(c[p[j].se]){
					k=p[j].se;break;
				}
			if(!k)rep(j,1,n)if(c[j]){
				k=j;break;
			}
			if(!k){
				puts("No");
				return 0;
			}
			ans[i]=k;
			c[k]--;
		}
		else{
			if(c[f[i]]){
				puts("No");
				return 0;
			}
			ans[i]=f[i];
			c[f[i]]=n-f[i];
		}
	puts("Yes");
	rep(i,1,n*n)printf("%d ",ans[i]);
	puts("");
	return 0;
}


Measured memory_bytes: 11392
#include <bits/stdc++.h>
#define assem99 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define endll '\n'
#define sz(a) (int)(a).size()
#define RWFile freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
int dx[] = { 0, -1, 0, 1, -1, 1, -1, 1 };
int dy[] = { -1, 0, 1, 0, 1, -1, -1, 1 };
const int MOD = 1e8, N = 2e6 + 5, oo = 1e9;
const double pi = acos(-1);
using namespace std;

bool prime[N];
vector<int> primes;
int arr[N];
void sieve(int n) {
    memset(prime, 1, sizeof prime);
    for (int p = 2; p * p <= n; p++)
    {
        if(prime[p])
        {
            for(int i = p * p; i <= n; i += p) prime[i] = 0;
        }
    }
    for(int i = 2; i < n; i++) if(prime[i]) primes.push_back(i);
}

map<int, vector<int>> mp;
void getPrimes(int n, int i)
{
    while (n % 2 == 0)
    {
        mp[i].push_back(2);
        n /= 2;
    }
    for (int i = 3; i <= sqrt(n); i += 2)
    {
        while (n % i == 0)
        {
            mp[i].push_back(i);
            n /= i;
        }
    }
    if (n > 2) mp[i].push_back(n);
}

int main()
{
    assem99
    int n, k; cin>>n>>k;
    for(int i = 0; i < n; i++)
    {
        int a; cin>>a;
        arr[a]++;
    }
    ll ans = 0;
    sort(arr, arr + n, greater<int>());
    for(int i = k; i < N; i++) ans += arr[i];
    cout<<ans;

    return 0;
}

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

const ll MOD = 1000000007;

struct mint {
    ll x;  // cout << ans.x << endl; で出力する
    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 {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= 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 {
        mint res(*this);
        return res /= a;
    }
};

struct Sieve {
    int n;
    vector<int> f, primes;
    Sieve(int n = 1) : n(n), f(n + 1) {
        f[0] = f[1] = -1;
        for (ll i = 2; i <= n; ++i) {
            if (f[i]) continue;
            primes.push_back(i);
            f[i] = i;
            for (ll j = i * i; j <= n; j += i) {
                if (!f[j]) f[j] = i;
            }
        }
    }
    bool isPrime(int x) {
        return f[x] == x;
    }
    vector<int> factorList(int x) {
        vector<int> res;
        while (x != 1) {
            res.push_back(f[x]);
            x /= f[x];
        }
        return res;
    }
    vector<pair<int, int>> factor(int x) {
        vector<int> fl = factorList(x);
        if (fl.size() == 0) return {};
        vector<pair<int, int>> res(1, pair<int, int>(fl[0], 0));
        for (int p : fl) {
            if (res.back().first == p) {
                res.back().second++;
            } else {
                res.emplace_back(p, 1);
            }
        }
        return res;
    }
};

int main() {
    Sieve sieve(1e6);
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    
    map<int,int> mp;
    rep(i,N){
        int a = A[i];
        for(auto e:sieve.factor(a)){
            mp[e.first] = max(mp[e.first],e.second);
        }
    }
    mint lcm = 1;
    for(auto e:mp){
        mint a = e.first;
        lcm*=a.pow(e.second);
    }

    mint ans = 0;
    rep(i,N){
        ans += (lcm/A[i]);
    }
    cout << ans.x << endl;
}

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

int main(){
    int N, M;
    cin >> N >> M;
    pair<int,bool> boxs[100000] = {};

    for(int i = 0; i < N; i++){
        boxs[i].first = 1;
        if(i == 0) boxs[i].second = true;
        else boxs[i].second = false;
    }

    for(int i = 0; i < M; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        if(boxs[a].second){
            boxs[b].second = true;
        }

        boxs[a].first -= 1;
        boxs[b].first += 1;

        if(boxs[a].first == 0) boxs[a].second = false; 
    }

    int cnt = 0;
    for(int i = 0; i < N; i++){
        if(boxs[i].second) cnt++;
    }

    cout << cnt << endl;

}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#include <fstream>

typedef long long int ll;
using namespace std;

int main()
{

    //freopen("14","r",stdin);
    //freopen("sparse.out","w",stdout);
    int x,a,b;
    scanf("%d%d%d",&x,&a,&b);
    if(abs(a-x)<abs(b-x)){
        printf("A");
    }else printf("B");
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0; i<(int)(n); ++i)
#define REP(i,m,n) for(ll i=(ll)(m); i<(ll)(n); ++i)
#define F first
#define S second
const double PI=acos(-1);
//fixed<<setprecision(11)<<

int main(){
  int x,a;cin>>x>>a;
  if(x>=a) cout<<10<<endl;
  else cout<<0<<endl;
return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <map>
#include <vector>

using namespace std;


int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> k(M);
    vector<vector<int>> s(M);
    for (int i = 0; i < M; i++) {
        cin >> k[i];
        s[i].resize(k[i]);
        for (int j = 0; j < k[i]; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> p(M);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }

    int pow_N = 1;
    for (int i = 0; i < N; i++) {
        pow_N *= 2;
    }

    int count = 0;
    for (int i = 0; i < pow_N; i++) {
        bool fail = false;
        for (int j = 0; j < M; j++) {
            int sw_sum = 0;
            for (int k = 0; k < s[j].size(); k++) {
                int sw = s[j][k]-1;
                if (i & (1 << sw)) {
                    sw_sum++;
                }
            }
            if ((sw_sum % 2) != p[j]) {
                fail = true;
                break;
            }

        }
        if (!fail) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <time.h>
#include <bitset>
using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

bitset<4000001> b;
int main(){
	int n;
	cin >> n;
	b.set(0);
	rep(i,n){
		int a;
		cin >> a;
		b |= (b<<a);
		b.set(a);
	}
	int m = b.count();
	//cerr << m << endl;
	int k = m/2+1;
	//cerr << k << endl;
	int c = 0;
	for(int i=0;i<=4000000;i++){
		if(b[i])c++;
		if(c==k){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1912
n, y = map(int,input().split())
count = 0

def check():
    for man in range(n):
        for gosen in range(n):
            if n-man-gosen > 0:
                if y == 10000*man + 5000*gosen + 1000*(n-man-gosen):
                    return man, gosen , n-man-gosen
    return -1, -1, -1

if  n == y//10000:
    print(y//10000, 0, 0)
elif  n == y//5000:
    print(0, y//5000, 0)
elif  n == y//1000:
    print(0, 0, y//1000)
else:
    i, j, k = check()
    print(i, j, k)



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

using namespace std;

int main(){
  int k;
  string s;
  cin >> k >> s;
  if ( k < s.length()){
    for (int i = 0; i < k ; i++){
      cout << s.at(i);
    }
    cout << "..." << endl;
  }
  else{
    cout << s << endl;
  }
  
  
}


Measured memory_bytes: 3612
n, y = map(int, input().split())

flg = True
for a in range(0, n + 1):
  for b in range(0, n + 1 - a):
    c = n - a - b
    if a * 10000 + b * 5000 + c * 1000 == y:
      print(a, b, c, sep=' ')
      flg = False
      break
  if not flg:
      break
if flg:
  print(-1, -1, -1, sep=' ')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }



signed main(){

    int N, A, B; cin >> N >> A >> B;
    string S; cin >> S;
    int c1 = 0, c2 = 0;
    REP(i, N){
        if(S[i] == 'a'){
            if(c1 < A + B){
                cout << "Yes" << endl;
                c1++;
            }
            else cout << "No" << endl;
        }else if(S[i] == 'b'){
            if(c1 < A + B && c2 < B){
                cout << "Yes" << endl;
                c1++;
                c2++;
            }
            else cout << "No" << endl;
        }else cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<int> num(n);
  for (int i = 0; i < n; i++) cin >> num[i];
  sort(num.begin(), num.end());
  int half = num[n-1]/2;
  int ans = 1000000000;
  for (int i = 0; i < n-1; i++) {
    if (abs(half - num[i]) <= abs(half - ans)) ans = num[i];
  }
  cout << num[n-1] << " " << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if (a+b>c+d){
    cout << "Left" <<endl;
  }
  else if (a+b==c+d){
    cout << "Balanced" <<endl;
  }
  else {
    cout << "Right" <<endl;
  }
}

Measured memory_bytes: 256