akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<map>
using namespace std;
#define ll long long
int main(){
	string s;
    cin >> s;
    if(s[0]!='A'){
    	cout << "WA";
    	return 0;
    }
    if(s[1]=='C'){
    	cout << "WA";
    	return 0;
    }
    if(s[s.size()-1]=='C'){
    	cout << "WA";
    	return 0;
    }
    int i;
    int count;
    for(i=1;i<s.size();i++){
    	if(!((s[i]>='a')&&(s[i]<='z'))){
    		if(s[i]!='C'){
    			cout << "WA";
    			return 0;
   			}else{
   				count+=1;
   			}
    	}
    }
		if(count!=1){
			cout << "WA";
    		return 0;
		}
	cout << "AC";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, sg[200007];
vector<int>e[200007];
int read()
{
	int num = 0;
	char c = getchar();
	while (c < '0' || c>'9')c = getchar();
	while (c >= '0' && c <= '9')num = num * 10 + c - '0', c = getchar();
	return num;
}
int dfs(int w, int f)
{
	for (int i = e[w].size() - 1; i >= 0; i--)
		if (e[w][i] != f)
			sg[w] ^= dfs(e[w][i], w) + 1;
	return sg[w];
}
int main()
{
	n = read();
	for (int i = 1; i < n; i++)
	{
		int a = read(), b = read();
		e[a].push_back(b);
		e[b].push_back(a);
	}
	cout << (dfs(1, 0) ? "Alice" : "Bob") << endl;
	return 0;
}

Measured memory_bytes: 14720
temp=input().split()
W=int(temp[0])
H=int(temp[1])
x=int(temp[2])
y=int(temp[3])

S=W*H/2
if W/2==x and H/2==y:
  w=int(1)
else:
  w=int(0)
  
print(S, w)

Measured memory_bytes: 38256
d=input().split()
s={'N':(1,5,2,3,0,4),'W':(2,1,5,0,4,3),'E':(3,1,0,5,4,2),'S':(4,0,2,3,5,1)}
for o in input():
 d=[d[i]for i in s[o]]
print(d[0])


Measured memory_bytes: 5568
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	int a=scan.nextInt();
	int b=scan.nextInt();
	int c=scan.nextInt();
	int d=scan.nextInt();
	int S=a<=c?c:a;
	int F=b<=d?b:d;
	System.out.println(S<F?F-S:0);
}
}

Measured memory_bytes: 25428
from collections import deque
N,M=map(int,input().split())
S=input()
j=N
ans=deque()
while j>0:
    for i in range(M,0,-1):

        if j-i==0:
            ans.appendleft(i)
            print(*ans)

        elif j-i<0:
            continue
        if S[j-i]=="0":
            ans.appendleft(i)
            j-=i
            break
        if i==1 and S[j-i]=="1":
            print(-1)
            exit()


Measured memory_bytes: 47180
#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;

int main(){
    int n;
    double sum,ave,a;
    while(1){
        cin>>n;
        if(n==0){
            break;
        }
        int s[n];
        sum=0;
        for(int i=0;i<n;i++){
            cin>>s[i];
            sum+=s[i];
        }
        ave=sum/n;
        a=0;
        for(int i=0;i<n;i++){
            a+=pow(s[i]-ave,2);
        }
        a=sqrt(a/n);
        printf("%.5f\n",a);
    }
    return 0;
}


Measured memory_bytes: 3220
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
#include<deque>
#include<map>
#include<queue>
#include<cmath>

typedef long long ll;

#define debug(x) cout << #x << '=' << x << endl;
#define debug_arr(a, n) for(ll i = 0; i < n; i++)cout << a[i] << ' '
#define inf 100000000000
#define loop(i,n) for(ll i = 0; i < n; i++)
#define graph vector<vector<ll>>
#define P pair<ll,ll>

using namespace std;

struct edge {
    int parent;
    int children;
    int distance;
};

struct node{
    int color = 0;
    bool isSearched = false;
    vector<edge> e;
};

edge revE(edge e){
    edge tmpE;
    tmpE.children = e.parent;
    tmpE.parent = e.children;
    tmpE.distance = e.distance;
    return tmpE;
}

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

    vector<node> nodes(n+1);

    queue<int> q;

    loop(i,n-1){
        edge tmpE;
        cin >> tmpE.parent >> tmpE.children >> tmpE.distance;

        nodes[tmpE.parent].e.push_back(tmpE);
        tmpE = revE(tmpE);
        nodes[tmpE.parent].e.push_back(tmpE);
    }

    q.push(1);

    while(!q.empty()){
        node tmpN = nodes[q.front()];
        q.pop();

        loop(i,tmpN.e.size()){
            edge tmpE = tmpN.e[i];

            nodes[tmpE.children].color = nodes[tmpE.parent].color ^ tmpE.distance % 2;

            if(! nodes[tmpE.children].isSearched){
                nodes[tmpE.children].isSearched = true;
                q.push(tmpE.children);
            }
        }
    }

    loop(i,n){
        cout << nodes[i+1].color << endl;
    }

    return 0;
}


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

int N,M,Q,a[100000],tree[1<<18],c[100001];
bool b[100001];
vector<int>v;
map<int,int>mp;

void add(int x,int t){
	x+=(1<<17);
	while(x){
		tree[x]+=t;
		x/=2;
	}
}

int calc(int p,int q,int l,int r,int k){
	if(r<p||q<l)return 0;
	if(p<=l&&r<=q)return tree[k];
	else{
		return (calc(p,q,l,(l+r)/2,k*2)+calc(p,q,(l+r)/2+1,r,k*2+1));
	}
}

int main(){
	cin>>N>>M>>Q;
	for(int i=0;i<Q;++i){
		cin>>a[i];
	}
	for(int i=Q-1;i>=0;--i){
		if(b[a[i]])continue;
		v.push_back(a[i]);
		b[a[i]]=true;
	}
	for(int i:v){
		add(i,1);
	}
	while(!v.empty()){
		if(calc(0,v.back(),0,(1<<17)-1,1)==v.back()){
			add(v.back(),-1);
			v.pop_back();
		}
		else{
			break;
		}
	}
	c[0]=N;
	for(int i=0;i<v.size();++i){
		mp[v[i]]=i;
	}
	for(int i=Q-1;i>=0;--i){
		if(mp.find(a[i])!=mp.end()){
			int t=mp[a[i]];
			if(c[t]){
				--c[t];
				++c[t+1];
			}
		}
	}
	if(c[v.size()]==N){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 7032
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int main(){
    int N, K;
    string S;
    cin >> N >> K;
    cin >> S;
    S[K-1] = S[K-1] - ('A'-'a');
    cout << S << endl;
    return 0;
}



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

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

int main(void){
	int i,j,n,count,flg;
	int p[12],tmp[12];

	while(cin>>n && n){
		rep(i,n) cin>>p[i];
		for(count=0;;count++){
			flg = 1;
			memset(tmp,0,sizeof(tmp));
			rep(i,n)rep(j,n)if(p[i]==p[j])tmp[j]++;
			rep(i,n)if(p[i]!=tmp[i]){flg=0;break;}
			if(flg) break;
			rep(i,n)p[i]=tmp[i];
		}
		cout<<count<<endl;
		rep(i,n-1)cout<<p[i]<<" ";
		cout<<p[n-1]<<endl;
	}

	return 0;
}

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

#define ll long long

#define all(a) (a).begin(),(a).end()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define output_s(a) printf("%s\n",(a).c_str())

//library----------------------------------------------


int main(){
    int n;cin>>n;
    int ans = pow(n,3);
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 9e18;
constexpr int inf = 1e9;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;
};

// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ---------------------------------------------------------------------------

int main(){
  int N,R;
  cin >> N >> R;
  if(N >= 10){
    cout << R << endl;
  }else{
    cout << R + (10-N)*100 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long N,M;
int main(){
	cin>>N>>M;
	long long arr[N];	
	long long hasil=0;
	for(long long i=0; i<N; i++){
		cin>>arr[i];
		hasil+=arr[i];
	}
	int den=4*M;
	if(hasil%den==0){
		hasil/=den;
	}else{
		hasil/=den;
		hasil++;
	}
	long long total=0;
	for(int i=0; i<N; i++){
		if(arr[i]>=hasil){
			total++;
		}
	}
	if(total<M){
		cout<<"No"<<'\n';
	}else{
		cout<<"Yes"<<'\n';
	}
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val)
{
    std::fill((T*)array, (T*)(array + N), val);
}

struct UnionFind {
    vector<int> d;
    UnionFind(int n = 0)
        : d(n, -1)
    {
    }
    int find(int x)
    {
        if (d[x] < 0)
            return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (d[x] > d[y])
            swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};

int main()
{
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        uf.unite(x, y);
    }

    set<int> s;
    for (int i = 0; i < N; i++) {
        s.insert(uf.find(i));
    }

    cout << s.size() << endl;
    return 0;
}

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

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define PI acos( -1.0 )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define se second
#define fr first
//#define c_b fflush(stdin);

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;

void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}

int msg() {
    srand( time( 0 ) ) ;
    vector < string > st = {
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!",
        "Go Go fight!"
    } ;
    cerr << st[ rand() % sz( st ) ] ;
    return 0 ;
}

void FastInputOutput() {
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}

set < int > in ;
int n , v ;

int main() {
  cin >> n ;
  while( n-- ){
    cin >> v ;
    in.insert( v ) ;
  }

  cout << sz( in ) ;

  return 0 ;
}


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

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

    vector<int> x(n);
    rep (i, n)
        cin >> x.at(i);

    sort(x.begin(), x.end(), greater<int>());

    int a = 0, b = 0;
    rep (i, n) {
        if (i % 2 == 0)
            a += x.at(i);
        else
            b += x.at(i);
    }

    cout << (a - b) << endl;
}


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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define mp make_pair
#define ll long long
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2097162
#define inf 1e9
#define MOD 1000000007

int main()
{

    string ss, a, b, kk, c, d;
    cin >> ss;
    ll n = ss.size();
    for(ll i = 0; i < (n-1)/2; i++) a.pb(ss[i]);
    for(ll i = ((n+3)/2)-1; i < n; i++) b.pb(ss[i]);
    c=  a, d=b, kk=ss;
    reverse(c.begin(),c.end());
    reverse(d.begin(),d.end());
    reverse(kk.begin(), kk.end());
    if(c==a && d==b && kk==ss) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 256
N = int(input())
SP = [list(map(str,input().split())) for _ in range(N)]
for i in range(N):
    SP[i][1] = int(SP[i][1])
for i in range(N):
    SP[i].append(i+1)
SP.sort()
for i in range(N**2):
    for i in range(N-1):
        if SP[i][0] == SP[i + 1][0] and SP[i][1] < SP[i+1][1]:
            A = SP[i]
            SP[i] = SP[i + 1]
            SP[i + 1] = A
for i in range(N):
    print(SP[i][2])


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

int main(){
  int n;
  cin >> n;
  bool y = false;
  for(int i=0; i<n; i++){
    char c;
    cin >> c;
    if(c == 'Y') y = true;
  }
  if(y){
    cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
def movea(a,b):
    if a==1 and a+1 == b:
        print('Borys')
        exit()    
    if a+1 != b: a += 1
    elif a >= 2: a-=1
    return a,b

def moveb(a,b):
    if b==n and b-1 == a:
        print('Alice')
        exit() 
    if b-1 != a: b -= 1
    elif b <= n-1: b+=1
    return a,b
    
while True:
    a,b=movea(a,b)
    a,b=moveb(a,b)

Measured memory_bytes: 3316
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        double bunbo = 0;
        int a = 1;
        while (a < k) {
            a *= 2;
            bunbo += 1;
        }
        double bunshi = 1;
        for (int i = 2; i < n + 1; i++) {
            int count = 0;
            int j = i;
            while (j < k) {
                j *= 2;
                count += 1;
            }
            bunshi += Math.pow(2, bunbo - count);
        }
        System.out.println(bunshi / (Math.pow(2, bunbo) * n));
    }
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dp[N];
vector<pair<int, int>> v;
vector<bool> vis(N);
void push(int node, vector<vector<int>> &edges){
	if(vis[node])
		return;
	vis[node] = true;
	for(auto child : edges[node])
		push(child, edges);
	v.push_back({v.size(), node});
}

int main(){
	int n, m, ans = 0;
	cin >> n >> m;
	vector<vector<int>> edges(n);
	for(int i = 0; i < m; ++i){
		int x, y;
		cin >> x >> y;
		--x; --y;
		edges[x].push_back(y);
	}
	for(int i = 0; i < n; ++i)
		push(i, edges);
	sort(begin(v), end(v));
	for(int i = 0; i < n; ++i){
		for(auto child : edges[v[i].second]){
			dp[v[i].second] = max(dp[v[i].second], 1 + dp[child]);
			ans = max(ans, dp[v[i].second]);
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 9716
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		ArrayList<String> s = nextCharArray();
		int fix = 753;
		int output = 1000000;
		for(int i = 0; i < s.size() - 2; i++){
			int check = Integer.parseInt(s.get(i) + s.get(i + 1) + s.get(i + 2));
			output = Math.min(output, Math.abs(fix - check));
		}
		myout(output);
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 37460
#include <bits/stdc++.h>
 
#define int long long
 
// loop
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 	// a ~ b-1	(ascending)
#define REP(i, n) FOR(i, 0, n)							// 0 ~ n-1
#define NREP(i, n) FOR(i, 1, n + 1)						// 1 ~ n
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)	// a ~ b	(descending)
#define RREP(i, n) RFOR(i, n, 0)						// n ~ 0
#define RNREP(i, n) RFOR(i, n, 1)						// n ~ 1
 
// container operation
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define ASORT(c) std::sort((c).begin(), (c).end())
#define DSORT(c) std::sort((c).begin(), (c).end(), std::greater<typeof((c).front())>())
#define SIZE(x) ((int)(x).size())
 
// debug
#define check(x) std::cout << #x << " = " << x << '\n'
 
// print
#define cout(x) std::cout << x << '\n'
 
// typedef
typedef std::vector<int> VI;
typedef std::vector<VI> VII;
typedef std::vector<bool> VB;
typedef std::vector<VB> VBB;
typedef std::vector<std::string> VS;

std::string yes = "Yes\n";
std::string no = "No\n";

void solve();

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

void solve() {
  int n, k;
  std::cin >> n >> k;
  VI h(n);
  REP(i, n) {
    std::cin >> h.at(i);
  }
  DSORT(h);
  int total = 0;
  REP(i, n) {
    if (i >= k) {
      total += h.at(i);
    }
  }
  cout(total);
}



Measured memory_bytes: 1792
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class ATheNumberOfEvenPairs {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int result = (n * (n - 1) / 2) + (m * (m - 1) / 2);
            out.println(result);
        }

    }
}



Measured memory_bytes: 22612
#include <bits/stdc++.h>
#define ll long long
#define INF INT_MAX 
#define mod 1000000007
using namespace std;
struct UnionFind{
    vector<int> par;
    UnionFind(int N) : par(N){
        for(int i=0;i<N;i++){
            par[i] = i;
        }
    }
    int root(int x){
        if(par[x]==x)return x;
        return par[x] = root(par[x]);
    }
    void unite(int x,int y){
        int rx = root(x);
        int ry = root(y);
        if(rx==ry) return;
        par[rx] = ry;
    }
    bool same(int x,int y){
        int rx = root(x);
        int ry = root(y);
        return rx==ry;
    }
};
int main(){
    ll N,M;
    cin >> N >> M;
    UnionFind tree(N+5);
    vector<int> p(N+5);
    int x,y;
    for(int i=0;i<N;i++){
        cin >> p[i];
    }
    for(int i=0;i<M;i++){
        cin >> x >> y;
        tree.unite(x,y);
    }
    int ans = 0;
    for(int i=0;i<N;i++){
        if(tree.same(p[i],i+1)){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1152
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
    read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
    match n {
        0 => a,
        _ => {
            a.push(read::<T>());
            read_n_logic(n - 1, a)
        }
    }
}
use std::cmp::{max, min};
use std::collections::VecDeque;

fn main() {
    let k: i64 = read();
    let mut vd: VecDeque<i64> = VecDeque::new();
    let mut cnt = 0;
    for i in 1..10 {
        vd.push_back(i);
    }
    let mut current = 0;

    for _ in 0..k {
        current = vd.pop_front().unwrap();
        if current % 10 != 0 {
            vd.push_back(current * 10 + (current % 10 - 1));
        }
        vd.push_back(current * 10 + (current % 10));
        if current % 10 != 9 {
            vd.push_back(current * 10 + (current % 10 + 1));
        }
    }

    println!("{}", current);
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=200005;
//i_am_noob
int ans=0;
string str1,str2;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> str1 >> str2;
	rep(3) ans+=(str1[i]==str2[i]);
	print1(ans);
	return 0;
}

Measured memory_bytes: 256
import sys

def allsc():
    n , x = map(int,input().split())
    if x==0 and n == 0:
      sys.exit()
    ans = 0
    for i in range(1,n):
        for j in range(i+1,n+1):
            k = x - i - j
            if i < j and j < k and k <= n:
                ans += 1
    print(ans)

while True:
    allsc()


Measured memory_bytes: 5600
n = int(input())
a = list(map(int, input().split()))
accu = [0]*3
ans = 1
mod = 10**9+7
for i in a:
    cnt = 0
    for j in range(3):
        if i==accu[j]:
            cnt += 1
            idx = j
    if cnt==0:
        print(0)
        exit(0)
    ans *= cnt
    ans %= mod
    accu[idx] += 1
print(ans)

Measured memory_bytes: 14056
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

using namespace std;

typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "[ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "]";

    return os;
}

ll pow_mod(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        p >>= 1;
    }

    return res;
}


ll mod_inv(ll a, ll m) {
    ll b = m, u = 0, v = 1;
    while(a) {
        ll t = b / a;
        swap(b -= t * a, a);
        swap(u -= t * v, v);
    }

    return (u % m + m) % m;
}

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


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

    int M = 1e5+1;
    int P[M];
    REP(i, M) P[i] = i;

    FOR(i, 2, M) {
        if (P[i] != i) continue;

        for (int j=i+i; j < M+1; j+=i) {
            P[j] = i;
        }
    }

    int S[M];
    S[1] = 0;
    for(int i = 3; i < M; i += 2) {
        int j = (i + 1) / 2;
        if(P[i] == i && P[j] == j) S[i] = S[i-2] + 1;
        else S[i] = S[i-2];
    }


    REP(i, Q) {
        int l, r;
        cin >> l >> r;

        cout << S[r] - S[max(1, l-2)] << endl;
    }

}


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

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<vector<int>> g(n);
  vector<int> from(n), to(n);
  for (int i = 0; i + 1 < n; i++) {
    cin >> from[i] >> to[i];
    from[i]--; to[i]--;
    g[from[i]].push_back(to[i]);
    g[to[i]].push_back(from[i]);
  }
  vector<int> depth(n);
  vector<int> size(n);
  vector<int> parent(n);
  function<void(int, int, int)> dfs = [&](int v, int pv, int d) {
    depth[v] = d;
    size[v] = 1;
    parent[v] = pv;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      dfs(u, v, d + 1);
      size[v] += size[u];
    }
  };
  int ans = n;
  if (k % 2 == 0) {
    for (int i = 0; i < n; i++) {
      dfs(i, -1, 0);
      int sum = 0;
      for (int j = 0; j < n; j++) {
        if (depth[j] == k / 2) {
          sum += size[j] - 1;
        }
      }
      ans = min(ans, sum);
    }
  } else {
    for (int i = 0; i + 1 < n; i++) {
      dfs(from[i], to[i], 0);
      dfs(to[i], from[i], 0);
      int sum = 0;
      for (int j = 0; j < n; j++) {
        if (depth[j] == (k - 1) / 2) {
          sum += size[j] - 1;
        }
      }
      ans = min(ans, sum);
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

class C {
	int N;
public:
	void solve()
	{
		int ans{ 0 };
		int a;
		for (int i{ 0 }; i < N; i++)
		{
			cin >> a;
			while (!(a & 1))
			{
				ans++;
				a >>= 1;
			}
		}

		cout << ans << endl;
	}

	C()
	{
		cin >> N;
	}
};


int main()
{
	C solution;
	solution.solve();

	return 0;
}

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

using namespace std;

string s;
int nx[200005][26];
int dp[200005], c[200005];

int main(void)
{
	cin >> s;
	s = "#" + s;
	
	for(int i = 0; i < 26; i++) nx[(int)s.size()-1][i] = s.size();
	for(int i = (int)s.size()-2; i >= 0; i--){
		for(int j = 0; j < 26; j++) nx[i][j] = nx[i+1][j];
		nx[i][s[i+1]-'a'] = i+1;
	}
	for(int i = (int)s.size()-1; i >= 0; i--){
		dp[i] = 1e9;
		for(int j = 0; j < 26; j++){
			if(dp[i] > dp[nx[i][j]]+1){
				dp[i] = dp[nx[i][j]]+1;
				c[i] = j;
			}
		}
	}
	
	int p = 0;
	while(p != s.size()){
		cout << (char)(c[p]+'a');
		p = nx[p][c[p]];
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 22464
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i >= 1; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> p;


int main() {
	int a, ans = 1;
	cin >> a;
	rep(i, a-2) {
		int k = i + 2;
		int j = 2;
		while (pow(k, j)<=a) {
			int power = pow(k, j);
			ans=max(ans,power);
			j++;
		}
	}
	cout << ans << endl;
	return 0;
}

//Ctrl+Aを使わない

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

int main() {
  // int A, H;
  // cin >> H >> A;
  // int ans = H / A;
  // if (H % A != 0) {
  //   cout << ans + 1 << endl;
  // } else {
  //   cout << ans << endl;
  // }

  // int H, N;
  // cin >> H >> N;
  // vector<int> A(N, 0);
  // for (int i; i < N; i++) {
  //   int val;
  //   cin >> val;
  //   A.at(i) = val;
  //   H = H - val;
  // }
  // if (H <= 0) {
  //   cout << "Yes" << endl;
  // } else {
  //   cout << "No" << endl;
  // }
  int N, K;
  cin >> N >> K;
  vector<long long> H(N, 0);
  long long ans = 0;
  for (int i; i < N; i++) {
    int val;
    cin >> val;
    H.at(i) = val;
  }
  sort(H.begin(), H.end(), std::greater<int>());
  if (N <= K) {
    cout << 0 << endl;
  } else{
    for (int i; i < K; i++){
      H.at(i) = 0;
    }
    ans = accumulate(H.begin(), H.end(), 0LL);
    cout << ans << endl;
  }
}

Measured memory_bytes: 1792
def gcd(a,b):
  if(a==0):
    return b
  return gcd(b%a,a)
def lcm(a,b):
  return int((a*b)/gcd(a,b))
a,b=(int(i) for i in input().split())
print(lcm(max(a,b),min(a,b)))

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
 
using namespace std;
 
//combinationを作る前処理
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}
 
const int MAX = 210000;
const int MOD = 1000000007;
 
 
 
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
 
long long com(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}


int main(){
  
  long long int H , W , A , B;
  
  cin >> H >> W >> A >> B;
  
  COMinit();
  
  long long int ans = 0;
  
  for(int i=0;i<W-B;i++){
    
    ans += (com(A-1+W-B-i-1,A-1)*com(H-A-1+B+i,H-A-1))%1000000007 ;
      ans %= 1000000007;
    
  }
  
  cout << ans << endl;
  
}
    


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  vector<int> v(9);
  rep(i,9)
    cin >> v.at(i);
  
  int n ;
  cin >> n ;
  
  rep(i,n){
    int c ;
    cin >> c ;
    rep(i,9){
      if(v.at(i) == c)
        v.at(i) = 0;
    }
  }
 
  
  string ans = "No";
  
  if(v.at(0) == 0 && v.at(1) == 0 && v.at(2) == 0)
    ans = "Yes";
  else if(v.at(3) == 0 && v.at(4) == 0 && v.at(5) == 0)
    ans = "Yes";
  else if(v.at(6) == 0 && v.at(7) == 0 && v.at(8) == 0)
    ans = "Yes";
   else if(v.at(0) == 0 && v.at(3) == 0 && v.at(6) == 0)
    ans = "Yes";
   else if(v.at(1) == 0 && v.at(4) == 0 && v.at(7) == 0)
    ans = "Yes";
  else if(v.at(2) == 0 && v.at(5) == 0 && v.at(8) == 0)
    ans = "Yes";
   else if(v.at(0) == 0 && v.at(4) == 0 && v.at(8) == 0)
    ans = "Yes";
   else if(v.at(2) == 0 && v.at(4) == 0 && v.at(6) == 0)
    ans = "Yes";
  
  cout << ans ;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vl A(N);
  ll len = 0;
  rep(i,N) {
    cin >> A[i];
    len += A[i];
  }
  int i = 0,j = N-1;
  ll a = 0,b = 0;
  while(i<N) {
    if(a+A[i] > len/2) break;
    a += A[i];
    i++;
  }
  while(j>=0) {
    if(b+A[j] > len/2) break;
    b += A[j];
    j--;
  }
  if(i != j) {
    cout << abs(b-a) << endl;
    return 0;
  }
  ll x = abs((a+A[i])-b);
  ll y = abs((b+A[i])-a);
  cout << min(x,y) << endl;
  return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(void){
  int n , k , q;
  scanf("%d %d %d",&n,&k,&q);

  int b , a[100001] = {0};
  for(int i = 0;i < q;i ++){
    scanf("%d",&b);
    a[b] ++;
  }
 
  

  for(int i = 1;i <= n;i ++){
    if((k - (q - a[i])) > 0){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }
  
  return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N,x,ans=0;
    cin>>N>>x;
    vector<int> a(N);
    for(int i=0;i<N;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    for(int i=0;i<N;i++){
        x-=a[i];
        if(N-1==i&&x!=0){
            cout<<ans;
            return 0;
        }else if(x>=0){
            ans++;
        }else{
            cout<<ans;
            return 0;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e5+10;
int x[maxn],y[maxn],t[maxn];
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
int main(){
	int i,j,k,m,n;
	n=read();
	for(i=1;i<=n;i++){
		t[i]=read();x[i]=read();y[i]=read();
	}
	for(i=1;i<=n;i++){
		int dis=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
		if((t[i]-t[i-1])%2!=dis%2 || dis>t[i]-t[i-1])return puts("No"),0;
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n) - 1; 0 <= i; --i)
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
using arr = vector<ll>;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 60;
constexpr int MAX = 100010;

long fac[MAX], inv[MAX], finv[MAX];
void init()
{
    fac[0] = inv[0] = finv[0] = 1;
    fac[1] = inv[1] = finv[1] = 1;
    for (int i = 2; i < MAX; ++i)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 区別できるnこの中からkこ選ぶときの組み合わせの総数
long C(int n, int k)
{
    if (n < 0 || k < 0 || n < k)
        return 0;
    return (fac[n] * finv[n - k] % MOD) * finv[k] % MOD;
}

ll n, k;

int main()
{
  cin >> n >> k;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];
  init();
  sort(a.rbegin(), a.rend());
  ll ans = 0;
  REP(i, n) {
    ans += C(n - i - 1, k - 1) * a[i] % MOD;
    ans %= MOD;
  }

  sort(a.begin(), a.end());
  REP(i, n) {
    ans = (ans + MOD - C(n - i - 1, k - 1) * a[i]) % MOD;
  }
  cout << ans;
  return 0;
}

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

int main()
{
    int N, H, W;
    cin >> N >> H >> W;
    vector<int> A(N), B(N);
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i] >> B[i];
        if (A[i] >= H && B[i] >= W)
        {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
    c = -1 if s == "?" else int(s)

    for j in range(10):
        if c != -1 and c != j:
            continue
        for r in range(13):
            dp[i + 1][(r * 10 + j) % 13] += dp[i][r]

    for r in range(13):
        dp[i + 1][r] = dp[i + 1][r] % MOD

print(dp[N][5])


Measured memory_bytes: 67440
S = int(input())
MOD = 10 ** 9
x1, y1, x2, y2 = 0, 0, MOD, 1
y3 = S // MOD
if S % MOD != 0:
  y3 += 1
x3 = x2 * y3 - S

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))

Measured memory_bytes: 3060
let pr x = print_endline @@ string_of_int x

let max (a : int) (b : int) =
  if a > b then a else b

let min (a : int) (b : int) =
  if a < b then a else b

let fold f init s =
  let rec iter i res =
    if i < 0 then res else iter (i - 1) (f res s.[i]) in
  iter (String.length s - 1) init

let solve seq =
  let len = String.length seq in
  let (_,_,res) = fold
                    (fun (cnt,pre,mv) x ->
                      if x != pre then
                        (cnt+1,x,min mv (max cnt (len - cnt)))
                      else (cnt+1,x,mv))
                    (0,seq.[0],len) seq in res

let () = input_line stdin
         |> solve
         |> pr

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl
#define YORN(f) cout<<((f)?"YES":"NO")<<endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define println(x) cout << x << endl
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if ((a * b) % 2 == 0) {
        println("Even");
    }
    else {
        println("Odd");
    }
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <set>
#include <map>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)

using namespace std;
typedef long long ll;

int main(){
    int N;
    ll M;
    cin>>N>>M;
    vector<pair<ll,ll> > vec;
    vec.reserve(N);
    rep(i,N){
        ll A,B;
        cin>>A>>B;
        vec.push_back(make_pair(A,B));
    }
    sort(vec.begin(),vec.end());
    ll ans;
    for(auto it:vec){
        if(M>it.second){
            ans += it.first*it.second;
            M-=it.second;
        }else{
            ans += it.first*M;
            break;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
import sys
f=lambda:map(int,sys.stdin.readline().split())
_,m=f()
d,t,c={},0,0
for p,y,i in sorted(list(f())+[i] for i in range(m)):
  if p>t: t,c=p,1
  else: c+=1
  d[i]=str(p).zfill(6)+str(c).zfill(6)
for _,v in sorted(d.items()): print(v)

Measured memory_bytes: 38096
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;

int main(void){
  int a,b;
  cin >> a >> b;
  int temp = b - a;
  int tower = 0;
  for(int i = 1; i < temp; i++){
    tower += i;
  }
  cout << tower - a << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    int[] b = new int[n];
    int[] c = new int[n-1];
    int sum = 0;

    for(int i = 0;i < n;i++) a[i] = sc.nextInt();
    for(int i = 0;i < n;i++) b[i] = sc.nextInt();
    for(int i = 0;i < n-1;i++) c[i] = sc.nextInt();

    int j = 0;

    for(int i = 0;i < n;i++){
      sum += b[a[i]-1];
      if(i == n-1) break;
      if(a[i]+1 == a[i+1]){
        sum += c[a[i]-1];
      }
    }

    System.out.println(sum);

  }

}


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

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)

signed main(){

	lli h,w;
	cin>>h>>w;

	char c;
	lli data[26]={0};
	priority_queue<lli> q;
	REP(i,0,h*w){
		cin>>c;
		data[c-'a']++;
	}
	REP(i,0,26) q.push(data[i]);

	priority_queue<lli> left;

	for(lli i=0;i<(h+1)/2;i++){
		for(lli j=0;j<(w+1)/2;j++){
			lli num=4;
			if(i==(h+1)/2-1 && h%2==1)num /= 2;
			if(j==(w+1)/2-1 && w%2==1)num /= 2;
			left.push(num);
		}
	}

	while(left.size()){
		lli leftNow = left.top();
		left.pop();

		lli dataNow = q.top();
		q.pop();
		if(leftNow>dataNow){
			/*途中で使いきれなくなったらアウト*/
			cout<<"No"<<endl;
			return 0;
		}
		dataNow -= leftNow;
		q.push(dataNow);
	}

	/*最後まで割り当てられればOK*/
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
# ABC169
# B Multiplication 2
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
x = 1
for i in A:
    if A[-1] == 0:
        print(0)
        exit()
    else:
        x = x * i
        if x > 10 ** 18:
            print(-1)
            exit()
print(x)

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

int main(){
	int n,m;	cin>>n>>m;
	vector<pair<int,int>>data(m);
	for(int i=0;i<m;i++){
		cin>>data[i].first>>data[i].second;
	}

	for(int i=0; i<pow(10,n); i++){
		int digit=0;
		int check=i;
		while(1){
			check/=10;	digit++;
			if(check==0)break;
		}
		if(digit!=n)continue;


		bool flag=true;
		for(int j=0;j<m;j++){
			int tmp=i;
			int s=data[j].first, c=data[j].second;
			// 左から数えてsケタ
			// => 右から数えてn-s+1ケタ
			s=n-s+1;

			while(s>1){
				--s;
				tmp/=10;
			}
			tmp%=10;
			if(tmp!=c){
				flag=false;
				break;
			}
		}

		if(flag){
			cout<<i<<endl;
			return 0;
		}
	}

	cout<<"-1"<<endl;
	return 0;
}


Measured memory_bytes: 512
import java.util.*;


public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int point = sc.nextInt();
        int distance = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < point; i++){
            double p = sc.nextInt();
            double q = sc.nextInt();
        if (distance >= (Math.sqrt(p * p + q * q))) {
            ans++;
        }
    }
        System.out.println(ans);        
    }
}

Measured memory_bytes: 48856
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Work work[] = new Work[n];
        for (int i = 0; i < n; i++) {
            int time = Integer.parseInt(sc.next());
            int limit = Integer.parseInt(sc.next());
            work[i] = new Work(time, limit);
        }
        sc.close();
        Arrays.sort(work, (x, y) -> x.limit - y.limit);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += work[i].time;
            if (ans > work[i].limit) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }

    static class Work {
        int time;
        int limit;

        Work(int time, int limit) {
            this.time = time;
            this.limit = limit;
        }
    }
}

Measured memory_bytes: 73692
N = gets.to_i - 1
S = N.times.map { gets.split.map(&:to_i) }
N.times do |i|
  x = (i ... N).inject(0) do |t, j|
    c,s,f = S[j]
    if t <= s
      s + c
    else
      ((t - s + f - 1) / f) * f + s + c
    end
  end
  puts x
end
puts 0


Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
//#include <stdio.h>

using namespace std;

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

    int H;
    int W;
    int h;
    int w;

    cin >> H >> W >> h >> w;

    cout << (H - h) * (W - w);
}

Measured memory_bytes: 888
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =[int(i) for i in range(size)]
        self.grp =size

    def find(self, x):
        if x==self.par[x]: return x

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def group_num(self):
        return self.grp



n,m=map(int,input().split())
uf=UnionFind(n)
ans=chk=0
for i in range(m):
    x,y,z=map(int,input().split())
    uf.unite(x-1,y-1)
print(uf.grp)

Measured memory_bytes: 79900
import java.util.Scanner;
class Main {

  public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
for(;;) {
	String str=sc.next();
	if(str.equals("0"))break;
	char[] ch= str.toCharArray();
	int sum=0;
	for(int i=0;i<ch.length;i++) {
		int num=Character.getNumericValue(ch[i]);
		sum+=num;

	}
System.out.println(sum);
}
sc.close();
  }


}


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

int main(){
    int x, n;
    set<int> p;
    cin >> x >> n;
    for(int i = 0; i < n; i++){
        int pi;
        cin >> pi;
        p.insert(pi);
    }

    int ans;
    for(int i = 0;; i++){
        int s = x - i;
        if (p.find(s) == p.end()){
            ans = s;
            break;
        }
        int t = x + i;
        if (p.find(t) == p.end()){
            ans = t;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedInputStream in = new BufferedInputStream(System.in);
             PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out))) {

            Scanner sc = new Scanner(in);

            // 11:47-

            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();
            long d = sc.nextLong();

            out.println(b - a + 1 - cnt(a, b, c) - cnt(a, b, d) + cnt(a, b, lcm(c, d)));

        }
    }

    private static long cnt(long a, long b, long c) {
        long consumed = (a - 1) % c;
        long rest = c - 1 - consumed;
        a += rest;
        return (b - a + 1 + c - 1) / c;
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    private static long gcd(long a, long b) {
        while (b > 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}


Measured memory_bytes: 22740