akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,c;cin >> n >> c;
	vector<vector<int>> d(c,vector<int>(c));
	rep(i,c) rep(j,c) cin >> d[i][j];
	vector<vector<int>> m(n,vector<int>(n));
	rep(i,n) rep(j,n){
		cin >> m[i][j];
		m[i][j]--;
	}
	vector<vector<pii>> a(3,vector<pii>(c));
	rep(i,3){
		rep(j,c){
			a[i][j]=mp(0,j);
		}
	}
	rep(i,c){
		rep(j,n){
			rep(k,n){
				a[(j+k)%3][i].first+=d[m[j][k]][i];
			}
		}
	}
	rep(i,3){
		sort(a[i].begin(),a[i].end());
	}
	int ans=1000000000;
	rep(i,3){
		rep(j,3){
			rep(k,3){
				if(a[0][i].second==a[1][j].second || a[1][j].second==a[2][k].second || a[0][i].second==a[2][k].second) continue;
				ans=min(ans,a[0][i].first+a[1][j].first+a[2][k].first);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1280
import java.util.Scanner;
import java.util.Stack;

public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		
		while(sc.hasNext()){
			Stack<Double> stack = new Stack<Double>();
			String[] str = sc.nextLine().split(" ");

			for(String s : str){
				if(s.equals("+")){
					double d2 = stack.pop();
					double d1 = stack.pop();
					stack.push(d1 + d2);
				}else if(s.equals("-")){
					double d2 = stack.pop();
					double d1 = stack.pop();
					stack.push(d1 - d2);
				}else if(s.equals("*")){
					double d2 = stack.pop();
					double d1 = stack.pop();
					stack.push(d1 * d2);
				}else if(s.equals("/")){
					double d2 = stack.pop();
					double d1 = stack.pop();
					stack.push(d1 / d2);
				}else{
					stack.push(Double.parseDouble(s));
				}
			}
			
			System.out.println(stack.pop());
		}
		
	}
	
}

Measured memory_bytes: 12000
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

class Program
{
    static void Main(string[] args)
    {
        var ABCXY = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int A = ABCXY[0], B = ABCXY[1], C = ABCXY[2], X = ABCXY[3], Y = ABCXY[4];
        bool flgA = C * 2 < A, flgB = C * 2 < B, flgHalf = C < (A + B) / 2.0;
        if (flgA && flgB)
        {
            Console.WriteLine(C * Math.Max(X, Y) * 2);
        }
        else if (flgA)
        {
            Console.WriteLine(C * 2 * X + B * Math.Max(0, Y - X));
        }
        else if (flgB)
        {
            Console.WriteLine(C * 2 * Y + A * Math.Max(0, X - Y));
        }
        else if (flgHalf)
        {
            Console.WriteLine(C * 2 * Math.Min(X, Y) + (X > Y ? A : B) * Math.Abs(X - Y));
        }
        else
        {
            Console.WriteLine(A * X + B * Y);
        }
    }
}

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

ll N, A, B, C;
vector<char> V;
vector<string> S;

void dfs(ll idx, ll a, ll b, ll c) {
    if (idx == N) {
        cout << "Yes" << endl;
        for (auto &x : V) {
            cout << x << endl;
        }
        exit(0);
    }
    if (S.at(idx) == "AB") {
        if (b) {
            V.at(idx) = 'A';
            dfs(idx + 1, a + 1, b - 1, c);
        }
        if (a) {
            V.at(idx) = 'B';
            dfs(idx + 1, a - 1, b + 1, c);
        }
    } else if (S.at(idx) == "AC") {
        if (c) {
            V.at(idx) = 'A';
            dfs(idx + 1, a + 1, b, c - 1);
        }
        if (a) {
            V.at(idx) = 'C';
            dfs(idx + 1, a - 1, b, c + 1);
        }
    } else {
        if (c) {
            V.at(idx) = 'B';
            dfs(idx + 1, a, b + 1, c - 1);
        }
        if (b) {
            V.at(idx) = 'C';
            dfs(idx + 1, a, b - 1, c + 1);
        }
    }
}

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

    cin >> N >> A >> B >> C;
    S.resize(N);
    for (auto &x : S) {
        cin >> x;
    }
    V.resize(N);
    dfs(0, A, B, C);
    cout << "No" << endl;

    return 0;
}

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

int main()
{
	//初期条件
	int N, i, a = 0, b = 0, kuro = 0, siro = 0, Ans = 200000, sub;
	string S;
	cin >> N >> S;
	for (i = 0; i < N; i++) {
		if (S[i] == '.')
			siro += 1;
		if (S[i] == '#')
			kuro += 1;
	}

	Ans = siro;
	i = 0;
	while (i < N) {
		while (S[i] == '.') {
			a += 1;
			i += 1;
		}
		sub = b + siro - a;
		if (Ans > sub)
			Ans = sub;
		while (S[i] == '#') {
			b += 1;
			i += 1;
		}
		sub = b + siro - a;
		if (Ans > sub)
			Ans = sub;
	}
	cout << Ans;

		return 0;
}

Measured memory_bytes: 640
n = gets.chop.to_i
t = []
i=0
n.times do
  line = gets.strip.split.map(&:to_i)
  t << line.shift
end 
m=t
a=[m.max]
j= (m - a).max 
maxxx=m.max
istwo=1
if m.length-((m-a).length)==1
  istwo=0
end
if istwo==1
  m.each do |num|
    p maxxx
  end
else
  m.each do |num|
    if num==maxxx
      p j
    else
      p maxxx
    end
  end
end

Measured memory_bytes: 6780
#include<stdio.h>

int main()
{
	int a , b;
	scanf( "%d %d" , &a , &b);
	if(a<b)
	{
		printf("a < b\n");
	}
	else if(a>b)
	{
		printf("a > b\n");
	}
	else
	{
		printf("a == b\n");
	}
	
	return 0;
} 


Measured memory_bytes: 2692
#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
using namespace std;
int n,m;
string s[20];
int swaped[20];
int used[20];
int ans = 0;
bool check()
{
	memset(used,0,sizeof used);
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(used[i]||used[j]||i==j) continue;
			int cur=1;
			for(int k=0;k<n;k++){
				if(s[swaped[k]][i]!=s[k][j]){
					cur=0;
					break;
				}
			}
			if(cur){
				used[i]=used[j]=1;
			}
		}
	}
	int cnt=0,to=0;
	for(int i=0;i<m;i++){
		if(!used[i]){
			cnt++;to=i;
		}
	}
	if(cnt>=2||(m%2==0&&cnt)){
		return false;
	}
	if(!cnt) return true;
	for(int i=0;i<n;i++){
		if(s[swaped[i]][to]!=s[i][to]){
			return false;
		}
	}
	return true;
}


void dfs(int now,bool ji)
{
	if(now==(n+1)/2){
		if(check()){
			ans=1;
		}
		return;
	}
	for(int i=now;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(swaped[i]==-1&&swaped[j]==-1){
				swaped[i]=j;
				swaped[j]=i;
				dfs(now+1,ji);
				swaped[i]=-1;
				swaped[j]=-1;
			}
		}
		if(ji&&swaped[i]==-1){
			swaped[i]=i;
			dfs(now+1,false);
			swaped[i]=-1;
		}
	}

}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		cin>>s[i];
		swaped[i]=-1;
	}
	if(n&1){
		dfs(0,true);
	}else{
		dfs(0,false);
	}
	if(ans) printf("YES\n");
	else printf("NO\n");
}

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

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

  scanf("%d",&n);

  matrix = malloc((n+1) * sizeof(int *));
  for(i=0;i<n+1;i++) matrix[i] = malloc((n+1) * sizeof(int));

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

  free(matrix);

  return 0;
}

Measured memory_bytes: 636
# -*- coding: utf-8 -*-

# Tenka1 Programmer Beginner Contest
# Problem B

if __name__ == '__main__':
    n = int(input())
    worst_rank = -1
    worst_score = float('inf')

    # See:
    # https://beta.atcoder.jp/contests/tenka1-2017-beginner/submissions/1637273
    for i in range(n):
        ai, bi = list(map(int, input().split()))
        worst_rank = max(worst_rank, ai)
        worst_score = min(worst_score, bi)

    print(worst_rank + worst_score)


Measured memory_bytes: 3060
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    a, b = map(int, readline().split())
    
    s1 = str(a) * b
    s2 = str(b) * a
    if s1 < s2:
        print(s1)
    else:
        print(s2)
        
    
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61832
N = int(input())
x1 = int(N/(1.08))
x2 = x1+1
x3 = x1-1
if int(x1*1.08) == N:
    print(x1)
elif int(x2*1.08) == N:
    print(x2)
elif int(x3*1.08) == N:
    print(x3)
else:
    print(':(')

Measured memory_bytes: 38384
using System;
namespace inonoa{
    class INo{
        static void Main(){
            string[] n_k = Console.ReadLine().Split();
            int n = int.Parse(n_k[0]);
            int k = int.Parse(n_k[1]);
            string[] sa = Console.ReadLine().Split();
            int[] a = new int[n];
            int[] kosuu = new int[n];
            int syurui = 0;
            for(int i=0;i<n;i++){
                a[i] = int.Parse(sa[i]);
                if(kosuu[a[i]-1]==0){syurui ++;}
                kosuu[a[i]-1] += 1;
            }
            if(syurui<=k){Console.WriteLine(0);return;}
            int ans = 0;
            for(int i=1;i<n+1;i++){
                for(int j=0;j<n;j++){
                    if(kosuu[j]==i){
                        ans += i;
                        syurui -= 1;
                        if(syurui==k){Console.WriteLine(ans);return;}
                    }
                }
            }

        }
    }
}

Measured memory_bytes: 32092
// I think of what the world could be, A vision of the one I see, A million dreams is all it's gonna take

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 2010;

int memo[4][6 * maxn];

int& f(int n, int k){
    return memo[n&3][k + 3 * maxn];
}

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

    int n, m;
    cin >> n >> m;
    f(0, 0) = 1;
    for(int i = 1; i <= 3*n; i++){
	for(int j = -i; j <= i; j++){
	    f(i, j) = 0;
	    int num = 1;
	    for(int k = 1; k <= min(3, i); k++){
		f(i, j) = (1ll * f(i, j) + 1ll * num * f(i-k, j - (k == 1) + (k == 2))) % m;
		num = 1ll * num * (i-k) % m;
	    }
	}
    }
    int ans = 0;
    for(int i = 0; i <= 3*n; i++){
	ans = (ans + f(3*n, i)) % m;
    }
    return cout << ans << endl, 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include<utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);

inline ll LCM(ll a,ll b){
	int g=__gcd(a,b);
	return g?(a/g*b):0;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout<<fixed;
	ll n,m;
	while(cin>>n>>m){
		ll ans1=__gcd(n,m);
		ll ans2=LCM(n,m);
		cout<<ans1<<" "<<ans2<<endl;
	}
	return 0;
}

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

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

  ll ans;
  ll n = 1, m = 1, x = 1;
  while(1) {
    ans = m;
    m += x;
    n++;
    if(n == 9) {
      x *= 10;
      n = 0;
    }
    if(m > N) break;
  }

  ll t = 0;
  while(ans > 0) {
    t += ans % 10;
    ans /= 10;
  }
  cout << t << endl;
}


Measured memory_bytes: 256
import math

N = int(input())

if N == 0:
    print(0)
    exit()

s = ''
n = N
while n:
    p = math.ceil(n/-2)
    q = n - (p * -2)
    s += str(q)
    n = (n - q)//(-2)

print(s[::-1])


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

int main(){
    int N;
    cin >> N;
    vector<vector<int>> A(2, vector<int>(N));
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> A[i][j];
        }
        
    }
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        int now = 0;
        for (int j = 0; j < N; j++)
        {
            if (j <= i)
            {
                now += A[0][j];
            }
            if (j >= i)
            {
                now += A[1][j];
            }
        }
        ans = max(ans, now);
    }
      
    cout << ans << endl;
    return 0;
}

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

using namespace std;

typedef pair<int, int> P;

int N;
string s[1000000 + 10];
int need[1000000 + 10], delta[1000000 + 10];

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

	int total = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < s[i].size(); j++) {
			if (s[i][j] == '(') {
				total++;
				delta[i]++;
			}
			else {
				total--;
				delta[i]--;
			}
			need[i] = max(need[i], -delta[i]);
		}
	}
	if (total != 0) {
		cout << "No" << endl;
		return 0;
	}

	vector<P> inc, dec;
	for (int i = 0; i < N; i++) {
		if (delta[i] >= 0) {
			inc.push_back(make_pair(need[i], delta[i]));
		}
		else {
			dec.push_back(make_pair(need[i] + delta[i], -delta[i]));
		}
	}
	
	sort(inc.begin(), inc.end());

	sort(dec.begin(), dec.end());

	int depth = 0;
	for (int i = 0; i < inc.size(); i++) {
		if (inc[i].first > depth) {
			cout << "No" << endl;
			return 0;
		}
		depth += inc[i].second;
	}
	int depth2 = 0;
	for (int i = 0; i < dec.size(); i++) {
		if (dec[i].first > depth2) {
			cout << "No" << endl;
			return 0;
		}
		depth2 += dec[i].second;
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 50176
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <limits>
#include <random>
#include <utility>
#include <vector>

namespace procon {
  class UnionFind {
  private:
    struct nodeinfo {
      int par;
      int rank;
      nodeinfo(int par) : par(par), rank(0) {}
    };
    std::vector<nodeinfo> node;

  public:
    UnionFind(int n) : node() {
      node.reserve(n);
      for (int i = 0; i < n; ++i) {
	node.push_back(nodeinfo(i));
      }
    }
    int root(int x) {
      if (node[x].par == x) {
	return x;
      }
      return node[x].par = root(node[x].par);
    }
    void unite(int x, int y) {
      x = root(x);
      y = root(y);
      if (x == y) {
	return;
      }
      if (node[x].rank < node[y].rank) {
	node[x].par = y;
      } else {
	node[y].par = x;
	if (node[x].rank == node[y].rank) {
	  ++node[x].rank;
	}
      }
    }
    bool is_same_set(int x, int y) { return root(x) == root(y); }
  };
}

int main(void) {
  int log_size;
  int n_query;
  int seed;
  std::cin >> log_size >> n_query >> seed;

  assert(0 <= log_size && log_size <= 30);
  assert(0 <= n_query);

  const int size = 1 << log_size;
  const int mask = size - 1;
  uint64_t res = 123456789;

  std::mt19937 mt(seed);
  procon::UnionFind uf(size);
  while (n_query--) {
    const int com = mt() & 1;
    const int x = mt() & mask;
    const int y = mt() & mask;
    if (com) {
      res = res * 17 + (uf.is_same_set(x, y) ? 1 : 0);
    } else {
      uf.unite(x, y);
    }
  }
  std::cout << res << std::endl;
  return 0;
}



Measured memory_bytes: 11008
#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

int main()
{
	int a, b, c;
	a = 0, b = 0, c=0;

	scanf("%d %d %d", &a, &b, &c);
	if (a >= 0 && a <= 100 && b >= 0 && b <= 100 && c >= 0 && c <= 100) {
		if (b > a && c > b) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}

	return 0;
}


Measured memory_bytes: 2028
n,m=map(int,input().split())
ken=[1 for i in range(n+1)]
inf=[[] for i in range(m)]
def f(x):
    m=0
    while x>0:
        m+=1
        x=x//10
    return m

for i in range(m):
    p,y=map(int,input().split())
    inf[i].append(i+1)
    inf[i].append(p)
    inf[i].append(y)
inf=sorted(inf, key=lambda x: x[2])

for i in range(m):
    inf[i].append(ken[inf[i][1]])
    ken[inf[i][1]]+=1
inf=sorted(inf)


for i in range(m):
    ans=""
    p=inf[i][1]
    y=inf[i][3]
    for j in range(6-f(p)):
        ans+="0"
    ans=ans+str(p)
    
    for j in range(6-f(y)):
        ans=ans+"0"
    ans=ans+str(y)
    print(ans)
    
    
    
    
    



    
        
        
        
          


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

void findNum(string &s,int a,int b,int &A,int &B){
  int cnt=0;
  for(int i=a;i<b;i++){
    if(s[i]=='(')cnt++;
    if(s[i]==')')cnt--;
    if(cnt==0&&s[i]=='[')A=i;
    if(cnt==0&&s[i]==']')B=i+1;
  }
}

int getNum(string &s,int a,int b){
  int num=0;
  for(int i=a+1;i<b-1;i++)
    num=num*10+(s[i]-'0');
  return num;
}

void solve(string &s,string &t,int a,int b,int l,int r){
  if(a==b||l==r)return;
  int A,B,L,R;
  findNum(s,a,b,A,B);
  findNum(t,l,r,L,R);
  int snum=getNum(s,A,B);
  int tnum=getNum(t,L,R);
  
  cout<<'(';
  solve(s,t,a+1,A-1,l+1,L-1);
  cout<<')';
    
  cout<<'['<<snum+tnum<<']';

  cout<<'(';
  solve(s,t,B+1,b-1,R+1,r-1);
  cout<<')';
}

int main(){
  string s,t;
  cin>>s>>t;
  solve(s,t,0,s.size(),0,t.size());
  cout<<endl;
  return 0;
}

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

int main()
{
	int n;
	cin>>n;
	int x;
	cin>>x;
	int a[n+1];
	int t=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]>=x) t++;
	}
	cout<<t<<endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<queue>

using namespace std;

const int offset=100;

int memo[200][200];

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

int main(){
	int t,n;

	while(cin>>t>>n,t||n){
		int sx,sy;
		int ans=1;
		queue<pair<int,int> > q;

		fill((int *)memo,(int *)(memo+200),-1);

		for(int i=0;i<n;i++){
			int x,y;
			cin>>x>>y;
			memo[y+offset][x+offset]=0;
		}

		cin>>sx>>sy;

		q.push(make_pair(sx,sy));
		memo[sy+offset][sx+offset]=0;

		while(!q.empty()){
			int x=q.front().first;
			int y=q.front().second;
			int turn=memo[y+offset][x+offset];

			q.pop();

			if(turn==t){
				continue;
			}

			for(int i=0;i<6;i++){
				int xx=x+dx[i];
				int yy=y+dy[i];

				if(memo[yy+offset][xx+offset]==-1){
					memo[yy+offset][xx+offset]=turn+1;
					q.push(make_pair(xx,yy));
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1376
#include <stdio.h>

#define MAX 1000

int read(char *d)
{
    int middle, last, retry;

    scanf("%d %d %d", &middle, &last, &retry);

    if(middle == -1 && last == -1 && retry == -1)
        return 0;

    if(middle == -1 || last == -1 || middle + last < 30)
        *d = 'F';
    else if(middle + last < 50 && retry < 50)
        *d = 'D';
    else if((middle + last < 50 && retry >= 50) || middle + last < 65)
        *d = 'C';
    else if(middle + last < 80)
        *d = 'B';
    else
        *d = 'A';
        
    return 1;
}

int main(void)
{
    int i;
    int idx = 0;
    char data[MAX] = {};

    while(read(&data[idx++]) != 0);

    for(i=0;i<idx-1;i++) {
        printf("%c\n", data[i]);
    }

    return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ull unsigned long long int 
#define pb push_back
#define xx first
#define yy second


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll t;
	t=1;
	while(t--)
	{
	    string n;
	    cin>>n;
	    ll siz=n.size();
	    ll sum=0;
	    for(ll i=0;i<siz;i++)
	        sum+=(n[i]-'0');
	    
	    cout<<(sum%9==0 ? "Yes" : "No");
	}
}

Measured memory_bytes: 3768
#include <iostream>
#include <vector>
#define MAX 100001 
using namespace std;
#include <algorithm>
#include <tuple>

typedef tuple<int,int,int> t;
typedef pair<int,int> p;

int color[MAX];
p parent[MAX];
int main(void){
  int N;
  cin >> N;
  vector<t> v;
  for(int i=0;i<N-1;i++){
    int a,b;
    cin >> a >> b;
    t tmp = make_tuple(a,b,i);
    v.push_back(tmp);
    color[i] = 0;
  }
  sort(v.begin(),v.end());
  //ノード1が先頭 親はナシ　親と枝の色もなし
  p init(0,0);
  parent[1] = init;
  //上から順にやっていく
  int num = 1;
  int former = 1;
  int max = 1;
  for(int i=0;i<N-1;i++){
    t cur = v[i]; // 親　子　番号
    int par = get<0>(cur);
    int chi = get<1>(cur);
    int eNum = get<2>(cur);
    //cout << par << chi << eNum << endl;
    // ひとつ前の親といまの親がちがう
    if(former != par){
      num = 1;
    }
    former = par;
    //cout << num << endl;
    for(int n=num;n<N;n++){
      //色番号が親の枝と違ったらok
      //cout << "p:" << par << "," << parent[par].second << endl;
      if(n != parent[par].second){
	color[eNum] = n;
	p tmp(par,n);
	parent[chi] = tmp;
	num = n + 1;
	//cout << "p:" << parent[par].second << ",n:" << n << endl;
	break;
      }
    }
  }
  for(int i=0;i<N-1;i++){
    int tmp = color[i];
    if(max < tmp)
      max = tmp;
  }
  cout << max << endl;
  for(int i=0;i<N-1;i++){
     cout << color[i] << endl;
  }
  
  return 0;
 }


Measured memory_bytes: 2932
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifdef EZZAT
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#else
#endif
}

int main() {
	run();
	int h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;
	m1 += h1 * 60;
	m2 += h2 * 60;
	cout << m2 - m1 - k << endl;
}


Measured memory_bytes: 3652
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <unordered_map>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;
using LL = long long;


int C[1000];
int main() {
	int n;
	cin >> n;
	string s[2];
	cin >> s[0] >> s[1];
	int i = 0;
	LL ans = 1;
	char memo;
	if (s[0][0] == s[0][1]) {
		ans *= 6;
		i = 2;
		memo = 'Y';
	}
	else {
		ans *= 3;
		i = 1;
		memo = 'X';
	}
	for (; i < n; i++) {
		if (s[0][i] == s[0][i + 1]) {
			if (memo == 'X')ans = ans * 2 % MOD;
			else ans = ans * 3 % MOD;
			memo = 'Y';
			i++;
		}
		else {
			if (memo == 'X') {
				ans = ans * 2 % MOD;
			}
			memo = 'X';
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    
    int min,max;
    min=10000;
    max=-1;
    int a;
    int N;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&a);
        if(min>a)min=a;
        if(max<a)max=a;
    }
    printf("%d",max-min);
    return 0;
}


Measured memory_bytes: 128
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
t,x,y = Line(N)

t0 = 0
x0 = 0
y0 = 0

for i in range(N):
    d = abs(x[i]-x0) + abs(y[i]-y0)
    a = t[i]-t0-d
    if a>=0 and a%2==0:
        t0 = t[i]
        x0 = x[i]
        y0 = y[i]
    else:
        print('No')
        exit()

print('Yes')

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int visited[2 * maxn + 100];
vector<int> g[2 * maxn + 100];

void dfs(int u) {
    visited[u] = true;
    for (auto x : g[u]) {
        if (!visited[x]) {
            dfs(x);
        }
    }
}

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

    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;

        for (int j = 0; j < k; j++) {
            int tp;
            cin >> tp;
            tp += maxn;
            g[i].push_back(tp);
            g[tp].push_back(i);
        }
    }
    dfs(0);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 10624
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        h: [i64; n]
    }

    let ans = h
        .into_iter()
        .scan(0, |max, x| {
            let r = x >= *max;
            *max = std::cmp::max(*max, x);
            Some(r)
        })
        .filter(|&x| x)
        .count();
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
#define pb push_back

int main()
{
    LL n, ans;
    cin >> n;

    if(n == 1)
    {
        cout << 1 << '\n';
        return 0;
    }

    vector <LL> v(100);

    v[0] = 2;
    v[1] = 1;
    for(int i = 2; i <=n; i++)
    {
        v[i] += v[i-1]+v[i-2];
        ans = v[i];
    }

    cout << ans << '\n';



    return 0;
}



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

using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if (a<b && b<c) {
        cout << "Yes" <<endl;
    }
    
    else{
        cout << "No" <<endl;
    }
    }


Measured memory_bytes: 3096
import math

A,B,C,D = map(int, input().split())

a = A - 1
bn = B - B//C - B//D + (B//((C*D)//math.gcd(C,D)))
an = a - a//C - a//D + (a//((C*D)//math.gcd(C,D)))
print(bn - an)

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

int main() {
  int A, B;
  cin >> A >> B;
  if(A>=10 || B>=10) {
    cout << -1 << endl;
    return 0;
  }else{
    cout << A * B << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#[macro_use]
mod reader {
    use std;
    macro_rules! read_line((  ) => {
                           {
                           let mut input = String :: new (  ) ; std :: io ::
                           stdin (  ) . read_line ( & mut input ) . unwrap (
                           ) ; input } } ;);
    pub fn read_to_vec<T: std::str::FromStr>() -> Vec<T> {
        read_line!().split_whitespace().map(|e|
                                                e.parse().ok().unwrap()).collect()
    }
}
#[macro_use]
mod misc {
    use std;
    #[macro_export]
    macro_rules! bind_from_vec((
                               $ ( $ variable : ident ) , + = $ vector : expr
                               ) => {
                               let mut v = $ vector . clone (  ) . into_iter (
                                ) ; $ (
                               let $ variable = v . next (  ) . unwrap (  ) ;
                               ) + } ;);
    pub trait ExVec {
        fn sort_rev(&mut self);
    }
    impl <T: Ord> ExVec for Vec<T> {
        fn sort_rev(&mut self) { self.sort_by(|x, y| y.cmp(x)); }
    }
}
use reader::*;
use misc::*;
fn main() {
    bind_from_vec!(alen , blen , clen , combi = read_to_vec :: < usize > (
                   ));
    let mut a: Vec<u64> = read_to_vec();
    let mut b: Vec<u64> = read_to_vec();
    let mut c: Vec<u64> = read_to_vec();
    a.sort_rev();
    b.sort_rev();
    c.sort_rev();
    let mut ans: Vec<_> = Vec::new();
    for (i, ai) in a.iter().enumerate() {
        for (j, bj) in b.iter().enumerate() {
            for (k, ck) in c.iter().enumerate() {
                if (i + 1) * (j + 1) * (k + 1) <= combi {
                    ans.push(ai + bj + ck);
                } else { break  }
            }
        }
    }
    ans.sort_rev();
    for i in 0..combi { println!("{}" , ans [ i ]); }
}


Measured memory_bytes: 6396
#include<bits/stdc++.h>
#define int long long int
#define endl "\n"
#define arrinp(v) for(auto &i:v) cin>>i;
#define arrout(v) for(auto &i:v) cout<<i<<" ";
#define newline cout<<endl;
using namespace std;
int isPossibleTriangle(int arr[],
                       int N)
{
    // If number of elements are
    // less than 3, then no
    // triangle is possible
    if (N < 3)
        return false;

    // first sort the array
    sort(arr, arr + N);

    // loop for all 3
    // consecutive triplets
    int count = 0;
    for (int i = 0; i < N - 2; i++)

        // If triplet satisfies
        // triangle condition, break
        if (arr[i] + arr[i + 1] > arr[i + 2])
            count++;
    return count;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    // cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    if(a[i]!=a[j] and a[j]!=a[k] and a[k]!=a[i] and a[i]+a[j]>a[k] and a[j]+a[k]>a[i] and a[i]+a[k]>a[j]){
                        count++;
                    }
                }
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

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

typedef long long ll;

#define REP(i, n) for(int i=0; i<(n); i++)
#define REPS(i, n) for(int i=0; i<=(n); i++)
#define FOR(i, a, b) for(int i=a; i<(b); i++)
#define FORS(i, a, b) for(int i=a; i<=(b); i++)
// for container x
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int main(){
    int N;
    string S;
    cin >> N >> S;
    int cnt = 0;
    REP(i, N-2){
        if (S[i]=='A' && S[i+1]=='B' && S[i+2]=='C') cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//    std::sort(a.begin(), a.end(), std::greater<int>() );
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/

int main()
{
    vector<long long int > a(3);
    rep(i, 3) cin >> a[i];
    SORT(a);
    if (a[2] % 2 == 0)
        cout << 0 << endl;
    else
        cout << a[0] * a[1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	int t = 0;
	int x,mx = 0;
	for(int i = 1;i<=n;i++){
		scanf("%d",&x);
		mx = max(mx,x);
		t = gcd(t,x);
	}
	if(k%t==0 && k<=mx) puts("POSSIBLE"); else puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define INF 1e9
#define All(x) (x).begin(),(x).end()
#define F first
#define S second
typedef long long ll;
using namespace std;

int main(void){
    ll N,A,B;
    cin>>N>>A>>B;
    if((B-A)%2==0){
        cout<<(B-A)/2<<endl;
    }else if(A<N-B+1){
        //cout<<"!"<<endl;
        ll ans=(A+B-1)/2;
        cout<<ans<<endl;
    }else{
        ll c=A;
        A=N-B+1;
        B=N-c+1;
        //cout<<A<<endl;
        //cout<<B<<endl;
        ll ans=(A+B-1)/2;
        cout<<ans<<endl;
    }
}

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,k,q;
  cin >> n >> k >> q;
  vector<int> y(n,0);
  rep(i,q){
    int w;
    cin >> w;
    y[w-1]++;
  }
  rep(i,n){
    if(y[i]>q-k)cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}  


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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1000000000
using namespace std;
typedef long long ll;
// typedef pair<ll,ll> p;

int h,w;
int r[2010][2010], l[2010][2010], u[2010][2010], d[2010][2010];
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
int main(){
  cin >> h >> w;
  vector<string> c(h);
  for(int i=0; i< h; i++) cin >> c[i];

   for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(c[i][j] == '#') {
                l[i][j] = 0;
            } else {
                if(j > 0) {
                    l[i][j] = l[i][j - 1] + 1;
                } else {
                    l[i][j] = 1;
                }
            }
        }
    }
  for(int i = 0; i < h; i++) {
    for(int j = w - 1; j >= 0; j--) {
        if(c[i][j] == '#') {
            r[i][j] = 0;
        } else {
            if(j < w - 1) {
                r[i][j] = r[i][j + 1] + 1;
            } else {
                r[i][j] = 1;
            }
        }
      }
  }
  for(int j = 0; j < w; j++) {
    for(int i = 0; i < h; i++) {
        if(c[i][j] == '#') {
            u[i][j] = 0;
        } else {
            if(i > 0) {
                u[i][j] = u[i - 1][j] + 1;
            } else {
                u[i][j] = 1;
            }
        }
    }
  }
  for(int j = 0; j < w; j++) {
    for(int i = h - 1; i >= 0; i--) {
        if(c[i][j] == '#') {
            d[i][j] = 0;
        } else {
            if(i < h - 1) {
                d[i][j] = d[i + 1][j] + 1;
            } else {
                d[i][j] = 1;
            }
        }
    }
  }

  int ans = 0;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(c[i][j] == '.') {
                chmax(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3);
            }
        }
    }
  cout << ans << endl;
}

Measured memory_bytes: 67456
// Input macro
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
    // テストコードをここにコピペする
r"3
2 5" => "9",

r"6
0 153 10 10 23" => "53"

}

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        n: i32,    // 問題に合わせて記述
        b: [i32; n-1]
    }
    // 問題を解くコード
    let mut a = vec![0; n as usize];
    for (i, val) in b.iter().enumerate() {
        if i == 0 {
            a[i] = *val;
            a[i+1] = *val;
        } else {
            if b[i-1] < b[i]{
                a[i+1] = *val;
            } else {
                a[i] = *val;
                a[i+1] = *val;
            }
        }

    }
    let sum: i32 = a.iter().sum();
    return sum.to_string();
}


Measured memory_bytes: 4352
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int ans=0;
    long long  a;
    cin>>a;
    if(a>=30)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;


}




Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int gcd(int a, int b) {
    if(b > a) return gcd(b, a);
    else if(b == 0) return a;
    else return gcd(b, a % b);
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int A[100010];
    rep(i, n) cin >> A[i];
    int G = A[0];
    rep(i, n) G = gcd(G, A[i]);
    cout << G << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

const int SET = 5;

void card_game()
{
	int n      = 0;
	int card_a = 0;
	int card_b = 0;
	
	static int point_a[SET] = {0};
	static int point_b[SET] = {0};
	
	static int set = 0;
	
	scanf("%d", &n);
	if(n == 0)
	{
		for(int i=0; i<set; i++)
		{
			printf("%d %d\n", point_a[i], point_b[i]);
		}
		
		return;
	}
	
	for(int i=0; i<n; i++)
	{
		scanf("%d %d", &card_a, &card_b);
		
		if(card_a > card_b)
		{
			point_a[set] += (card_a + card_b);
		}
		else if(card_b > card_a)
		{
			point_b[set] += (card_a + card_b);
		}
		else
		{
			point_a[set] += card_a;
			point_b[set] += card_b;
		}
	}
	
	set++;
	card_game();
}

int main(void)
{
	card_game();
}


Measured memory_bytes: 2720
n = int(input())
h = list(map(int, input().split()))
count = 0
tmp = 0
for i in range(n):
    n_i = i + 1
    if n_i >= n:
        tmp = max(tmp, count)
        break
    if h[i] >= h[i+1]:
        count += 1
    else:
        tmp = max(tmp, count)
        count = 0
print(tmp)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007

long long int gcdExtended(long long int a, long long int b, long long int *x, long long int *y); 
long long int modInverse(long long int a) 
{ 
    long long int x, y; 
    long long int g = gcdExtended(a, mod, &x, &y); 

        long long int res = (x%mod + mod) % mod; 
        return res; 
    
} 
  
long long int gcdExtended(long long int a, long long int b, long long int *x, long long int *y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    long long int x1, y1;  
    long long int gcd = gcdExtended(b%a, a, &x1, &y1); 
  
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
}
int main(){
    int n,m;
    cin >> n >> m;
    int f[m+1]={0};
    f[0] = 1;
    for(int i=1; i<=m; i++){
        f[i] = (f[i-1] * (long long int)i) % mod;
    }
    int d = 1;
    long long int sum = 0;
    for(int k=0;k<=n;k++){
        // nCk
        long long int a = (((f[n]*modInverse(f[k]))%mod)*modInverse(f[n-k]))%mod;
        long long int b = (f[m]*modInverse(f[m-k]))%mod;
        long long int c = (f[m-k]*modInverse(f[m-n]))%mod;
        long long int ans = (((a*b)%mod)*((c*c)%mod))%mod;
        sum = ((sum + d*ans )%mod+ mod)%mod;
        d = d * -1;
    }
    cout << sum;
    return 0;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD 998244353ll

ll moddiv(ll a,ll b){
    a %= MOD;
    b %= MOD;
    for(ll m=MOD-2;m>0;m/=2){
        if(m&1){
            a=a*b%MOD;
        }
        b=b*b%MOD;
    }
    return a;
}


ll powl(ll a,ll b){
    if(b==0)
        return 1;
    ll c = powl(a * a % MOD, b / 2);
    if(b&1)
        return c * a % MOD;
    return c;
}

ll N,M, K;
ll Fa[505050];
ll ans;
ll i, j, k;
int main(){
    scanf("%lld%lld%lld", &N,&M, &K);
    Fa[0] = 1;
    fornum(i,0,N){
        Fa[i + 1] = Fa[i] * (i + 1) % MOD;
    }

    fornum(i,0,K+1){
        k = N - 1 - i;
        (ans += M * powl(M - 1, k) % MOD * moddiv(Fa[N-1], Fa[N-1 - k] * Fa[k])) %= MOD;
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 5376
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define int long long int
using namespace std;

void desperate_optimization(bool submitting=true,int precision=10)
{
  if(!submitting) return;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.setf(ios::showpoint);
  cout.precision(precision);
}
vector<int> adjList[100005];
int memo[100005];
int dpfunction(int node)
{
  if(memo[node]!=-1) return memo[node];
  int answer=1;
  for(auto itr:adjList[node]) answer=max(answer,1+dpfunction(itr));
  return memo[node]=answer;
}

int32_t main()
{
  desperate_optimization(true);
  int n,m;
  memset(memo,-1,sizeof(memo));
  cin>>n>>m;
  for(int i=0;i<m;i++)
  {
    int x,y;
    cin>>x>>y;
    adjList[y].push_back(x);
  }
  int answer=0;
  for(int i=1;i<=n;i++) answer=max(answer,dpfunction(i));
  cout<<answer-1;
  return 0;
}


Measured memory_bytes: 10112
#include<stdio.h>
int main(void){
	int n;
	int a;
	int flg = 1;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &a);
		if(a%2==0){
			if(a%3!=0 && a%5!=0){
				flg = 0;
			}
		}
	}
	if(flg == 1){
		printf("APPROVED\n");
	}
	else{
		printf("DENIED\n");
	}
	return 0;
}


Measured memory_bytes: 128
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

# t = int(input())
# for _ in range(t):
# n, m = map(int, input().split())
# nums = list(map(int, stdin.readline().split()))
s = input()
t = input()

count = 0
for i, j in zip(s, t):
    if i!=j:
        count += 1

print(count)

Measured memory_bytes: 79152
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 1000005
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD=1e9+7;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
int R,C;
bool check(int x,int y,int a,int b){
	bool hoge = false,piyo = false,ret =false;
	if(x==R||x==0)hoge = true;
	if(a==R||a==0)piyo = true;
	if(y==C||y==0)hoge = true;
	if(b==C||b==0)piyo = true;
	if(hoge&&piyo)ret=true;
	return ret;
}
int calc(int a,int b){
	int ret=0;
	if(a==0)ret=b;
	if(a==R)ret=2*C+R-b;
	if(b==0)ret=2*(R+C)-a;
	if(b==C)ret=a+C;
	return ret;
}
int main(){
	int N;
	cin>>R>>C>>N;
	vector<pair<pii, pii> > data;
	rep(i,N){
		int x,y,a,b;
		cin>>x>>y>>a>>b;
		if(check(x,y,a,b)){
			data.pb(mp(mp(x,y),mp(a,b)));
		}
	}
	bool ans=true;
	vector<pii> hoge;
	rep(i,data.size()){
		int a=data[i].first.first,b=data[i].first.second,c=data[i].second.first,d=data[i].second.second;
		hoge.pb(mp(calc(a,b),i));
		hoge.pb(mp(calc(c,d),i));
	}
	sort(hoge.begin(),hoge.end());
	vi nums;
	rep(i,hoge.size()){
		nums.pb(hoge[i].second);
	}
	stack<int> s;
	bool used[114514];
	rep(i,114514)used[i]=false;
	rep(i,nums.size()){
		int x=nums[i];
		if(!used[x]){
			s.push(x);
			used[x]=true;
		}else{
			if(x!=s.top()){
				ans=false;
			}
			s.pop();
		}
	}
	if(ans)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

Measured memory_bytes: 5360