akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int ma = a[n - 1], res = a[0];
  for (int i = 0; i < n - 1; i++) {
    if (min(abs(a[i] - ma / 2), abs(a[i] - (ma + 1) / 2)) < min(abs(res - ma / 2), abs(res - (ma + 1) / 2))) {
      res = a[i];
    }
  }
  cout << ma << ' ' << res << '\n';
}

Measured memory_bytes: 640
// https://atcoder.jp/contests/abc087/tasks/arc090_b
#include <bits/stdc++.h>
using namespace std;

// https://ei1333.github.io/luzhiled/snippets/structure/union-find.html
template <typename T> struct WeightedUnionFind {
    vector<int> data;
    vector<T> ws;

    WeightedUnionFind() {}

    WeightedUnionFind(int sz) : data(sz, -1), ws(sz) {}

    int find(int k) {
        if (data[k] < 0)
            return k;
        auto par = find(data[k]);
        ws[k] += ws[data[k]];
        return data[k] = par;
    }

    T weight(int t) {
        find(t);
        return ws[t];
    }

    bool unite(int x, int y, T w) {
        w += weight(x);
        w -= weight(y);
        x = find(x), y = find(y);
        if (x == y)
            return false;
        if (data[x] > data[y]) {
            swap(x, y);
            w *= -1;
        }
        data[x] += data[y];
        data[y] = x;
        ws[y] = w;
        return true;
    }

    T diff(int x, int y) { return weight(y) - weight(x); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    WeightedUnionFind<int> T(n);
    bool ans = true;
    while (m--) {
        int l, r, d;
        cin >> l >> r >> d;
        --l;
        --r;
        if (!T.unite(l, r, d) && T.diff(l, r) != d) {
            ans = false;
            break;
        }
    }
    if (ans)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

Measured memory_bytes: 1024
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7

memo = [-1] * 2**N
memo[0] = 1

def dfs(bit_state, matched):
    if memo[bit_state] != -1:
        return memo[bit_state]
    r = 0
    for i in range(N):
        if bit_state & (1 << i) and A[matched][i]: # bitでi桁目の女性未マッチング かつ 男性がi桁目の女性に対し相性OK
            r += dfs(bit_state ^ (1 << i), matched+1) # i桁目の女性をマッチング済にして遷移
    r %= MOD
    memo[bit_state] = r
    return r

print(dfs(2**N-1, 0))

Measured memory_bytes: 63580
#include <iostream>

using namespace std;

int main()
{
  int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  
  cin >> n;
  
  cout << a[n-1] << endl;
}
  
  


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

using namespace std;

string str;
int n;

int calcM(int pos)
{
    stack <int> st;
    st.push(str[pos] - '0');
    for (int i = pos + 1; i < str.length(); i++){
        if (str[i] == '+'){
            continue;
        }
        else if (str[i] == '*'){
            int a = st.top(); st.pop();
            i++;
            a *= (str[i] - '0');
            st.push(a);
        }
        else {
            st.push(str[i] - '0');
        }
    }
    
    int ret = 0;
    for (int i = 0; !st.empty(); i++){
        ret += st.top();
        st.pop();
    }
    return ret;
}

int calcL(int pos)
{
    stack <int> st;
    st.push(str[pos] - '0');
    for (int i = pos + 1; i < str.length(); i++){
        if (str[i] == '+'){
            int a = st.top(); st.pop();
            i++;
            a += (str[i] - '0');
            st.push(a);
        }
        else if (str[i] == '*'){
            int a = st.top(); st.pop();
            i++;
            a *= (str[i] - '0');
            st.push(a);
        }
    }
    
    return st.top();
}

int main(void)
{
    cin >> str >> n;
    
    int retM = calcM(0);
    int retL = calcL(0);
    
    if (retM == n && retL != n){
        cout << "M" << endl;
    }
    else if (retM != n && retL == n){
        cout << "L" << endl;
    }
    else if (retM == n && retL == n){
        cout << "U" << endl;
    }
    else {
        cout << "I" << endl;
    }
    
    
    return 0;
    
}

Measured memory_bytes: 1208
/* ***********************************************
Author        :yang12138
Created Time  :2018/5/26 20:11:06
File Name     :B.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;

const int N=2e5+10;

int a[N];
ll s[N],x[N];

void solve(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",a+i),s[i]=s[i-1]^a[i],x[i]=x[i-1]+a[i];

	ll ans=0;
	for(int i=1;i<=n;i++){
		int l=i,r=n;
		while(l<r){
			int m=(l+r+1)>>1;
			if(x[m]-x[i-1]==(s[m]^s[i-1])) l=m;
			else r=m-1;
		}
		ans+=l-i+1;
	}
	cout<<ans<<endl;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	solve();
    
    return 0;
}


Measured memory_bytes: 4224
# D 
N,M = map(int, input().split())
a,b,c = [],[],[]
for _ in range(M):
    ai,bi,ci = map(int, input().split())
    a.append(ai-1)
    b.append(bi-1)
    c.append(ci)

dist = [[float('inf')]*N for _ in range(N)]
for i in range(M):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]
#print(dist)
for mid in range(N):
    for start in range(N):
        for end in range(N):
            dist[start][end] = min(dist[start][end],
                                   dist[start][mid] + dist[mid][end])

ans = 0
for ai,bi,ci in zip(a,b,c):
    if dist[ai][bi]!=ci:
        ans += 1
print(ans)

Measured memory_bytes: 3316
#include <iostream>

using namespace std;

int main(void)
{
	int r, g, b;

	cin >> r >> g >> b;

	b += r * 100 + g * 10;

	if (b % 4 == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
	return (0);

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define mod 1000000009
#define pi 2*acos(0)
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
using namespace std;


int main()
{

	io;
	
	int x; cin >> x;
	if (x)cout << 0;
	else cout << 1;
}



Measured memory_bytes: 3648
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int x = i;    
            if (x % 3 == 0) {
                System.out.print(" " + i);
                continue;
            }
            while (x > 0) {
                if (x % 10 == 3) {
                    System.out.print(" " + i);
                    break;
                }
            x /= 10;
            }
        }
        System.out.println("");
    }
}


Measured memory_bytes: 28736
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>


#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define f_cin(X) scanf("%f",&X)
#define l_cin2(X,Y) scanf("%ld %ld",&X,&Y)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  f_cout(X) printf("%g\n",X)
#define  i_cout2(X,Y) printf("%d %d\n",X,Y)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

typedef long long  ll;
#define rept(x, s, n) for (int x = s; x < n; x++)

#define Yes_RTN s_cout("Yes");return 0
#define No_RTN  s_cout("No");return 0
#define YES_RTN s_cout("YES");return 0
#define NO_RTN  s_cout("NO");return 0


int i_cins(int n, int* A);
int l_cins2(int n, long* A,long* B);
int s_dsort(const void* a, const void* b);
int s_asort(const void* a, const void* b);

int  _gcd(int a, int b);

int s_asorts(const void* a, const void* b);


int main(void) {
	int N,M,X,i;
	int A[100],l=0,r=0;

	i_cin(N); i_cin(M); i_cin(X);
	i_cins(M, A);
	
	for (i = 0; i < M; i++) {
		if (A[i] < X) l++;
		if (A[i] > X) r++;
	}
	if (r > l) i_cout(l);
	else i_cout(r);
	
	return 0;
}
	
//昇順
int s_asorts(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}	
int s_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int s_asort(const void* a, const void* b) {
	return(*(int*)a -*(int*)b);
}
int l_cins2(int n, long* a, long* b) {
	int i;
	rept(i, 0, n) {
		l_cin2(*(a + i), *(b + i));
	}
	return 0;
}
int i_cins(int n, int* a) {
	int i;
	for (i = 0; i < n; i++) {
		i_cin(*(a + i));
	}

	return 0;
}
int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
//using Graph = vector<vector<Edge>>;
using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;
const double PI = acos(-1.0);

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, 1, -1, 1, 0, -1};

static const int N = 100;
static const int INFTY = (1 << 21);

int n, M[N][N];
int d[N]; // 距離で訪問状態(color)を管理する

void bfs(int s)
{
  queue<int> q;
  q.push(s);
  for (int i = 0; i < n; i++)
    d[i] = INFTY;
  d[s] = 0;
  int u;
  while (!q.empty())
  {
    u = q.front(), q.pop();
    for (int v = 0; v < n; v++)
    {
      if (M[u][v] == 0)
        continue;
      if (d[v] != INFTY)
        continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  for (int i = 0; i < n; i++)
  {
    cout << i + 1 << " " << ((d[i] == INFTY) ? (-1) : d[i]) << endl;
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int u, k, v;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
      M[i][j] = 0;
  }

  for (int i = 0; i < n; i++)
  {
    cin >> u >> k;
    u--;
    for (int j = 0; j < k; j++)
    {
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }

  bfs(0);

  return 0;
}



Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define __gnu_pbds::gp_hash_table unordered_map;
#define int long long int
#define pb push_back

signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int a,b;
cin>>a>>b;
cout<<6-a-b;



}

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

int main() {
    string S;
    cin >> S;

    int cnt = 0, length = S.size();
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j <= length; j++) {
            bool count = true;
            for (int k = i; k < j; k++) {
                if (S.at(k) != 'A' && S.at(k) != 'T' && S.at(k) != 'G' && S.at(k) != 'C') count = false;
            }
            if (count) cnt = max(cnt, j - i);
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3592
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

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

    vector<pair<long long, long long>> left(N), right(N);
    int left_divider = 1, right_divider = N - 1;
    long long diff, prev_diff, p, q, r, s;
    for (int i = 2; i < N - 1; i++) {
        p = S[left_divider];
        q = S[i] - S[left_divider];
        diff = abs(q - p);
        while (1) {
            if (i - left_divider < 2) {
                break;
            }
            prev_diff = diff;
            left_divider += 1;
            p = S[left_divider];
            q = S[i] - S[left_divider];
            diff = abs(q - p);
            if (diff >= prev_diff) {
                left_divider -= 1;
                break;
            }
        }
        p = S[left_divider];
        q = S[i] - S[left_divider];
        left[i] = {p, q};
    }

    diff = 0;
    for (int i = N - 2; i > 1; i--) {
        r = S[right_divider] - S[i];
        s = S[N] - S[right_divider];
        diff = abs(s - r);
        while (1) {
            if (right_divider - i < 2) {
                break;
            }
            prev_diff = diff;
            right_divider -= 1;
            r = S[right_divider] - S[i];
            s = S[N] - S[right_divider];
            diff = abs(s - r);
            if (diff >= prev_diff) {
                right_divider += 1;
                break;
            }
        }
        r = S[right_divider] - S[i];
        s = S[N] - S[right_divider];
        right[i] = {r, s};
    }

    long long ans = 1e18;
    long long Max, Min;
    for (int i = 2; i < N - 1; i++) {
        Max = max(max(left[i].first, left[i].second),
                  max(right[i].first, right[i].second));
        Min = min(min(left[i].first, left[i].second),
                  min(right[i].first, right[i].second));
        ans = min(ans, Max - Min);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9600
fn main() {
    let mut inputs = Vec::new();    
    loop {
        let s = {
            let mut s = String::new(); 
            std::io::stdin().read_line(&mut s).unwrap();
            s.trim_right().to_string()
        };

        let tokens = s.split(" ")
            .map(|num| num.parse().unwrap())
            .collect::<Vec<i32>>();

        if tokens[0] == 0 && tokens[1] == 0 { break; }
        inputs.push((tokens[0], tokens[1]));
    }

    for i in 0..inputs.len() {
        if inputs[i].0 < inputs[i].1 {
            println!("{} {}", inputs[i].0, inputs[i].1);
        } else {
            println!("{} {}", inputs[i].1, inputs[i].0);
        }
    }
}


Measured memory_bytes: 5044
#include <iostream>
#include <utility>

using namespace std;

const int N = 300;

int n;
int pixel[N][N];
int hsum[N + 1][N + 1];
int vsum[N + 1][N + 1];

// yoko
int hRangeSum(int row, int s, int t) {
    return hsum[row][t + 1] - hsum[row][s];
}

// tate
int vRangeSum(int col, int s, int t) {
    return vsum[col][t + 1] - vsum[col][s];
}

int main() {

    int ans = -30000000;

    cin >> n;

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

    for(int i = 0; i < n; ++i) {
        vsum[i][0] = 0;
        hsum[i][0] = 0;
        for(int j = 1; j <= n; ++j) {
            hsum[i][j] = hsum[i][j - 1] + pixel[i][j - 1];
            vsum[i][j] = vsum[i][j - 1] + pixel[j - 1][i];
        }
    }

    for(int i = 0; i < n; ++i) {
        for(int j = i; j < n; ++j) {
            ans = max(ans, hRangeSum(i, i, j));
            if(i == j) continue;
            int max_vsum = vRangeSum(0, i, j);
            for(int k = 1; k < n; ++k) {
                int vsum = vRangeSum(k, i, j);
                ans = max(ans, max(max_vsum + vsum, vsum));
                max_vsum = max(max_vsum + pixel[i][k] + pixel[j][k], vsum);
            }
        }
    } 

    cout << ans << endl;

}

Measured memory_bytes: 4128
s = input()
n = len(s) # 文字列の長さを取得しておく

res = 0 # 条件になければ0
for i in range(n): # Sの部分文字列を全探索するループ：重複を許す（i==jの時は1文字の部分文字列になる）が入替を許さないループ
    for j in range(i, n):
        sub = s[i: j+1] # i文字目からからj文字目までの部分文字列

        flg = True
        for c in sub: # Python的for文
            if(c not in ['A', 'G', 'C', 'T']): flg = False # こちらも、in はこういう時便利です

        if(flg): res = max(res, len(sub)) # ACGT文字列の長さnumの最大値を保持する

print(res)

Measured memory_bytes: 3064
n,l=map(int,input().split())
A=[int(i) for i in input().split()]
length,knot=A[0]+A[1],1
for i in range(n-2):
  if A[i+1]+A[i+2]>length:
    length=A[i+1]+A[i+2]
    knot=i+2
if length<l:
  print("Impossible")
else:
  print("Possible")
  for i in range(1,knot):
    print(i)
  for i in range(knot,n):
    print(n+knot-i-1)

Measured memory_bytes: 14060
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chkmax(T& a,T b){return a<b?a=b,1:0;}
template<class T> inline bool chkmin(T& a,T b){return a>b?a=b,1:0;}
template<typename T> inline T& read(T& x){
    static char c; bool flag=0;
    while(!isdigit(c=getchar())) if(c=='-') flag=1;
    for(x=c-'0';isdigit(c=getchar());(x*=10)+=c-'0');
    if(flag) x=-x;
    return x;
}
int x,y,z;
multiset<string> s;
int main(){
#ifdef xffyjq
    freopen("exec.in","r",stdin);
    freopen("exec.out","w",stdout);
#endif
    read(x); read(y); read(z);
    for(int i=1;i<=x;i++) s.insert("a");
    for(int i=1;i<=y;i++) s.insert("b");
    for(int i=1;i<=z;i++) s.insert("c");
    for(int i=1;i<x+y+z;i++){
        auto it1=s.begin(),it2=s.end(); --it2;
        s.insert(*it1+*it2);
        s.erase(it1); s.erase(it2);
    }
    cout<<*s.begin()<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator >(const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, int cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

/*--------------------template--------------------*/
pair<int, Edges> prim(Graph g)
{
	vector<bool> used(g.size());
	Edges res;
	int sum = 0;

	priority_queue<Edge, vector<Edge>, greater<Edge>> que;
	que.push(Edge{ -1, 0, 0 });

	while(!que.empty())
	{
		Edge e = que.top(); que.pop();
		if(used[e.to]) continue;
		if(e.from >= 0) res.push_back(e);
		sum += e.cost;
		used[e.to] = true;
		for(Edge i : g[e.to])
		{
			if(!used[i.to]) que.push(i);
		}
	}
	return make_pair(sum, res);
}

int main()
{
	int v, e;
	cin >> v >> e;
	Graph g(v);
	REP(i, e)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add_edge(g, a, b, c);
		add_edge(g, b, a, c);
	}
	auto ans = prim(g);
	cout << ans.first << endl;
	return 0;
}

Measured memory_bytes: 9272
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include<algorithm>
#define pf printf
#define sf scanf
#define wh while
#define db double
#define LL long long
#define _USE_MATH_DEFINES
#define re(i,a,b) for(int i=a;i<b;i++)
#define rev(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

int main()
{
    int t,a,b,c;
    cin>>t;
    wh(t--){
        sf("%d%d%d",&a,&b,&c);
        if((a*a==b*b+c*c)||(b*b==a*a+c*c)||(c*c==a*a+b*b))pf("YES\n");
        else pf("NO\n");
    }
    return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector <int> p(n, 0);
    vector <int> s(n, 0);
    p[0] = a[0];
    for (int i = 1; i < n; i++) {
        p[i] = __gcd(p[i - 1], a[i]);
    }
    s[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        s[i] = __gcd(s[i + 1], a[i]);
    }
    int ans = 0;
    ans = max(ans, s[1]);
    ans = max(ans, p[n - 2]);
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, __gcd(p[i - 1], s[i + 1]));
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 1408
H,W=map(int,input().split())
MAP=[input() for i in range(H)]

ANS=[["#"]*(W+2) for i in range(H+2)]

for i in range(H):
    for j in range(W):
        ANS[i+1][j+1]=MAP[i][j]

for i in range(H+2):
    print("".join(ANS[i]))


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

int main(){
    string s;
    cin >> s;
    int t=0;
    for(int i=0;i<s.size();i++){
        if(!(s[i]>='a'&&s[i]<='z')) t++;
    }
    if(s[0]=='A'&&t==2){
        int cnt=0;
        for(int i=2;i<s.size()-1;i++){
            if(s[i]=='C') cnt++;
        }
        if(cnt==1){
            cout << "AC" << endl;
            return 0;
        }
    }
    cout << "WA" << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static final int MODULUS = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        System.out.println(solve(N, M));

        sc.close();
    }

    static int solve(int N, int M) {
        int result = 1;
        List<Integer> exponents = buildExponents(M);
        for (int exponent : exponents) {
            result = multiplyMod(result, computeWayNum(N, exponent));
        }

        return result;
    }

    static int computeWayNum(int N, int count) {
        int[] wayNums = new int[count + 1];
        wayNums[0] = 1;

        for (int i = 0; i < N; ++i) {
            int[] nextWayNums = new int[count + 1];
            for (int j = 0; j <= count; ++j) {
                for (int k = j; k <= count; ++k) {
                    nextWayNums[k] = addMod(nextWayNums[k], wayNums[j]);
                }
            }

            wayNums = nextWayNums;
        }

        return wayNums[count];
    }

    static int addMod(int x, int y) {
        return (x + y) % MODULUS;
    }

    static int multiplyMod(int x, int y) {
        return (int) ((long) x * y % MODULUS);
    }

    static List<Integer> buildExponents(int M) {
        List<Integer> exponents = new ArrayList<>();
        int current = M;
        for (int i = 2; i * i <= current; ++i) {
            int exponent = 0;
            while (current % i == 0) {
                ++exponent;
                current /= i;
            }

            if (exponent != 0) {
                exponents.add(exponent);
            }
        }
        if (current != 1) {
            exponents.add(1);
        }

        return exponents;
    }
}


Measured memory_bytes: 52680
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

using namespace std;

int gcd(int n, int m) {
    if (n == 0)
        return m;
    return gcd(m % n, n);
}

int bit_count(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

int main() {
    int n;
    cin >> n;
    cout << 180 * (n-2) << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		//String t = sc.next();
		//String g = sc.next();
		//long n = sc.nextLong();
		//long m = sc.nextLong();
		//long k = sc.nextLong();
		//long l = sc.nextLong();
		long count=0;

		for(int i=0;i<=3;i++) {
			if(s.substring(i,i+1).equals("+")) {
				count++;
			}else {
				count--;
			}
		}
		/*if(n<=8 && m<=8) {
			System.out.println("Yay!");
		}else{
			System.out.println(":(");
		}*/
		//System.out.println((int)Math.ceil((n+m)/2.0));
		System.out.println(count);
	}
}




Measured memory_bytes: 21716
import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    String str = sc.next();
    char c[] = new char[n];
    int sum = 0;
    c = str.toCharArray();
    char ch = c[0];
    for(int i = 1; i < n; i++) {
      if(c[i] != ch) {
        ch = c[i];
        sum++;
      }
    }
    
    System.out.println(sum+1);
  }
}

Measured memory_bytes: 26016
#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N;
vector<ll> A,B;
void input(){
    fast_io();
    cin >> N;
    A = fetch_vec<ll>(N);
    B = fetch_vec<ll>(N);
}

int solve(){
    ll AS,BS;
    AS = accumulate(A.begin(),A.end(),0LL);
    BS = accumulate(B.begin(),B.end(),0LL);
    if(AS<BS) {cout << -1 << endl; return 0;}
    vector<ll> C;
    ll ans = 0;
    ll need = 0;
    for (int i = 0; i < N; i++)
    {
        C.push_back(A[i]-B[i]);
        if(A[i]<B[i]) {
            ans++;
            need += B[i]-A[i];
        }
        
    }
    sort(C.begin(),C.end(),[](ll a,ll b){return a>b;});
    DBG(C)
    DBG(need)
    for (int i = 0; i < N; i++)
    {
        if(need<=0) break;
        if(C[i]<=0) break;
        need-=C[i];
        ans++;
    }
    cout << ans << endl;
    return 0;
}   

int main()
{
    input();
    solve();
    return 0;
}

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

long long m;
long long d;
long long mi = 1;
long long di = 1;
long long ans;

int main()
{
	cin >> m >> d;
	di = 1;
	mi = 1;
	for(int i = 2; i <= m; i++) mi = (mi*i)%1000000007;
	for(int i = 0 ; i <= d - 1 ; i ++)
	{
		di = (di*(d-i))%1000000007;
	}
	if(m == d)
	{
		ans = (mi *di *2) % 1000000007;
	}
	else if(d - m == 1)
	{
		ans = (mi * di) % (1000000007);
	}
	else if(m - d == 1)
	{
		ans = (mi * di) % (1000000007);
	}
	else
	{
		ans = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = 0
cnt = 0
for i, a in enumerate(A):
    if i == 0:
        ans += a
        cnt += 1
    else:
        if n-1 - cnt >= 2:
            ans += a*2
            cnt += 2
        else:
            ans += a
            cnt += 1
    if cnt == n-1:
        break
print(ans)

Measured memory_bytes: 105272
#include "bits/stdc++.h"
using namespace std;


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = pow(2, 62);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


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




/* main */


signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s = raw_input();


    int cnt = 0;

    int ans = 0;
    for(int i = s.size() - 1; i > -1; i--){
        if(s[i] == 'B'){
            ans += s.size() - 1 - i - cnt;
            cnt++;
        }
    }
    print(ans);


    



    





    


    

}

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

int main(void){
    string S;
    cin >> S;
    int N;
    N = S.size();
    string str;
    for(int i=0; i<N; i++){
        str += "x";
    }
    cout << str << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define f first
#define s second

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.in", "r", stdin);
        //freopen("output.out", "w", stdout);
	int n, k;
	cin >> n >> k;
	int s[n];
	int dp[n];
	for(int i = 0; i < n; i++){
		cin >> s[i];
		dp[i] = INT_MAX;
	}
	dp[0] = 0;
	dp[1] = abs(s[1] - s[0]);
	for(int i = 2; i < n; i++){
		for(int p = 1; p <= k && i >= p; p++){
			dp[i] = min(dp[i], (dp[i - p] + abs(s[i - p] - s[i])));
		}
	}
	cout << dp[n - 1] << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
    int N;
    cin>>N;
    vector<int> vec(N);
    for (int i=0; i<N; i++) {
        cin>>vec[i];
    }
    long long x=0,y=0,m=0,kol=1;
    sort(vec.begin(), vec.end() );

    for (int i=1; i<N; i++)  {
        if (vec[i]!=vec[i-1]) {
            if (kol>=4) {
                if (vec[i-1]>m) m=vec[i-1];
            }

            if (kol>=2) {
                if (vec[i-1]>x) {
                    y=x;
                    x=vec[i-1];
                }
                else {
                    if (vec[i-1]>y) {
                        y=vec[i-1];
                    }
                }

            }
            kol=1;
        }
        else {
            kol++;
        }
    }

    if (kol>=4) {
        if (vec[N-1]>m) m=vec[N-1];
    }
    if (kol>=2) {
        if (vec[N-1]>x) {
            y=x;
            x=vec[N-1];
        }
        else {
            if (vec[N-1]>y) {
                y=vec[N-1];
            }
        }
    }
    long long v=x*y,w=m*m;
    cout<<max(v, w);
    return 0;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

using ld = long double;
using P = complex<ld>;
constexpr ld EPS = 1e-10;
ld cross(const P &a, const P &b) { return a.real() * b.imag() - a.imag() * b.real(); }
template <class iter>
std::pair<P, ld> min_ball(iter left, iter right, int seed = 1333) {
	const int n = right - left;

	assert(n >= 1);
	if (n == 1) {
		return { *left, ld(0) };
	}

	std::mt19937 mt(seed);
	std::shuffle(left, right, mt);
	// std::random_shuffle(left, right);	// simple but deprecated
	
	iter ps = left;
	using circle = std::pair<P, ld>;

	auto make_circle_3 = [](const P &a, const P &b, const P &c) -> circle {
		ld A = std::norm(b - c), B = std::norm(c - a), C = std::norm(a - b), S = cross(b - a, c - a);
		P p = (A * (B + C - A) * a + B * (C + A - B) * b + C * (A + B - C) * c) / (4 * S * S);
		ld r2 = std::norm(p - a);
		return { p, r2 };
	};

	auto make_circle_2 = [](const P &a, const P &b) -> circle {
		P c = (a + b) / (ld)2;
		ld r2 = std::norm(a - c);
		return { c, r2 };
	};

	auto in_circle = [](const P &a, const circle &c) -> bool {
		return std::norm(a - c.first) <= c.second + EPS;
	};

	circle c = make_circle_2(ps[0], ps[1]);

	// MiniDisc
	for (int i = 2; i < n; ++i) {
		if (in_circle(ps[i], c)) { continue; }
		// MiniDiscWithPoint
		c = make_circle_2(ps[0], ps[i]);
		for (int j = 1; j < i; ++j) {
			if (in_circle(ps[j], c)) { continue; }
			// MiniDiscWith2Points
			c = make_circle_2(ps[i], ps[j]);
			for (int k = 0; k < j; ++k) {
				if (in_circle(ps[k], c)) { continue; }
				c = make_circle_3(ps[i], ps[j], ps[k]);
			}
		}
	}
	return c;
}

int main() {
	int N;
	cin >> N;
	vector<complex<long double>> points;
	for (int i = 0; i < N; ++i) {
		int x, y;
		cin >> x >> y;
		points.emplace_back(x, y);
	}

	auto res = min_ball(points.begin(), points.end());
	cout.precision(15);
	cout << fixed << sqrt(res.second) << endl;

	return 0;
}


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

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		
		while(true) {
			int N=in.nextInt(),n=200,s=200,e=200,w=200;
			if(N==0)break;
			int pos[][]=new int[200][2];
			for(int i=0;i<200;i++) {
				pos[i][0]=-1;pos[i][1]=-1;
			}
			pos[0][0]=200;pos[0][1]=200;
			
			for(int i=1;i<N;i++) {
				int a=in.nextInt(),d=in.nextInt();
				int y=pos[a][0],x=pos[a][1];
				
				switch(d) {
				case 0:
					pos[i][0]=y;
					pos[i][1]=x-1;
					if(x-1<w)w=x-1;
					break;
					
				case 1:
					pos[i][0]=y+1;
					pos[i][1]=x;
					if(y+1>s)s=y+1;
					break;
					
				case 2:
					pos[i][0]=y;
					pos[i][1]=x+1;
					if(x+1>e)e=x+1;
					break;
					
				case 3:
					pos[i][0]=y-1;
					pos[i][1]=x;
					if(y-1<n)n=y-1;
					break;
					
				}
			}

			System.out.println((e-w+1)+" "+(s-n+1));
		}
	}

}



Measured memory_bytes: 41540
# 入力
N, x = map(int, input().split())
a = list(map(int, input().split()))

dp = [[0 for _ in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i] = a[i]
    for k in range(1, N):
        j = (i + k) % N
        dp[i][j] = min(dp[i][(j - 1) % N], a[j])

# 変色回数を0からN-1まで決め打ちして解を求める
ans = min(
    sum(dp[i][(i + k) % N] for i in range(N)) + k * x
    for k in range(N)
)

# 出力
print(ans)


Measured memory_bytes: 77532
import java.util.Scanner;
class Main{
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			int[] a = new int[n];
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			int q = sc.nextInt();

			for(int i = 0; i < q; i++) {
				int target = sc.nextInt();
				System.out.println(lowerBound(a, target) +" "+ upperBound(a, target));
			}
		}
	}
	public static int search(int[] refNums, int target) {
		int head = 0;
		int foot = refNums.length - 1;
		int result = -1;
		int mid = 0;
		while(head <= foot) {
			mid = (head + foot) / 2;
			if(refNums[mid] == target) {
				result = mid;
				break;
			}
			else if(refNums[mid] < target) {
				head = mid + 1;
			}
			else {
				foot = mid - 1;
			}
		}
		return result<0?mid:result;
	}
	public static int lowerBound(int[] refNums, int target) {
		int i = search(refNums, target);
		if(refNums[i]==target) {
			for(;i>=0&& refNums[i]==target;i--);
			i++;
		}
		else {
			for(;i < refNums.length && refNums[i]<=target;i++);
		}
		return i;
	}
	public static int upperBound(int[] refNums, int target) {
		int i = search(refNums, target);
		for(;i < refNums.length && refNums[i]<=target;i++);
		return i;
	}
}


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

int main(){
  ll n,m;cin >> n >> m;
  vector<ll> h(n);
  rep(i,n) cin >> h.at(i);
  vector<vector<ll>> v(n);
  rep(i,m){
    ll a,b;cin >> a >> b;
    --a;--b;
    v.at(a).push_back(b);
    v.at(b).push_back(a);
  }
  ll ans = 0;
  rep(i,n){
    ll mx = -1;
    rep(j,v.at(i).size()){
      mx = max(mx,h.at(v.at(i).at(j)));
    }
    if( v.at(i).size() == 0 || mx < h.at(i)){
      ++ans;
    }
  }

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

Measured memory_bytes: 9828
n, k = map(int, input().split())
mod = 10 ** 9 + 7

from collections import deque
a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

plus_flg = False
if plus >= k:
    plus_flg = True
for i in range(plus+1):
    if (k - i) % 2 == 0 and (k - i) // 2 <= minus // 2:
        plus_flg = True
        break
#plus可能
if plus_flg:
    ans = 1
    cnt = 0 
    
    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
            else:
                ans *= que.pop()
                ans *= que.pop()
                ans %= mod
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



#zero
elif zero > 0:
    print(0)

#minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)

Measured memory_bytes: 32244
#include <iostream>

using namespace std;
int H; int N; int arr[100000]; int temp;

int main()
{
    cin >> H;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> temp;
        H -= temp;
    }

    if (H <= 0)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

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

#define int long long
using namespace std;

int N, A, B;
int P,ans;
int C[10];

signed main()
{
	cin >> N >> A >> B;
	for (int i = 0; i < N; i++) {
		cin >> P;
		if (P <= A) {
			C[1]++;
		}
		else if (P <= B) {
			C[2]++;
		}
		else {
			C[3]++;
		}
	}
	ans = C[1];
	for (int i = 1; i <= 3; i++) {
		if (C[i] < ans) {
			ans = C[i];
		}
	}
	cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N = int(input())
X = []
for _ in range(N):
    a, b = map(int, input().split())
    X.append((a,b))

X = sorted(X, key = lambda x:x[1])
t = 0
for i in range(N):
    t += X[i][0]
    if t > X[i][1]:
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 69724
#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){
	while(true){
		string s;
		getline(cin, s);
		if(s == "."){ break; }
		stack<char> stk;
		bool success = true;
		for(int i = 0; i < s.size(); ++i){
			char c = s[i];
			if(c == '(' || c == '['){
				stk.push(c);
			}else if(c == ')'){
				if(stk.size() > 0 && stk.top() == '('){
					stk.pop();
				}else{
					success = false;
					break;
				}
			}else if(c == ']'){
				if(stk.size() > 0 && stk.top() == '['){
					stk.pop();
				}else{
					success = false;
					break;
				}
			}
		}
		if(success && stk.size() == 0){
			cout << "yes" << endl;
		}else{
			cout << "no" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 904
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int n, color[99999], k;
vector<pair<int, int>> g[100000];

void dfs(int v, int p, int pc) {
	int c = 0;
	RF(e, g[v]) {
		if(e.FI == p) { continue; }
		if(c == pc) { c++; }
		color[e.SE] = c++;
		setmax(k, c);
	}
	RF(e, g[v]) {
		if(e.FI == p) { continue; }
		dfs(e.FI, v, color[e.SE]);
	}
}

int main() {
	cin >> n;
	inc(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].EB(b, i);
		g[b].EB(a, i);
	}
	
	dfs(0, -1, -1);
	
	cout << k << endl;
	inc(i, n - 1) { cout << color[i] + 1 << "\n"; }
	
	return 0;
}


Measured memory_bytes: 7424
import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

b_cn = [0] * n

for i, val in enumerate(b):
    index = bisect.bisect_right(c, val)
    b_cn[i] = n - index

b_rui = [0] * (n + 1)

for i in range(n):
    b_rui[i+1] = b_rui[i] + b_cn[i]

ret = 0

for item in a:
    index = bisect.bisect_right(b, item)
    ret += b_rui[-1] - b_rui[index]

print(ret)


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

int main(){
    int n;
    cin >> n;
    int n_copy=n,s=0;
    while(n_copy > 0){
        s += n_copy%10;
        n_copy /= 10;
    }
    string ans = "Yes";
    if(n%s != 0){
        ans = "No";
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,p[100],i,j,a;
main(){
  for(cin>>n;i<n;cin>>p[i++]);
  for(sort(p,p+n);!a;++j)n-j<=p[j]&&(a=n-j);
  cout<<a<<endl;
}

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

using namespace std;


int main()
{
	int N; 
	long long A,min=10000000000,max=0;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A;
		if (A > max)
			max = A;
		if (A < min)
			min = A;
	}

	cout << max - min << endl;

	return 0;
}


Measured memory_bytes: 256
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using ll=long long;
const ll MOD=1e9+7;
const int INF=1<<30;

int dp[3010][3010];

int main(){
  string s,t;
  cin >> s >> t;
  rep(i,s.size()){
    rep(j,t.size()){
      if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;
      chmax(dp[i+1][j+1],dp[i+1][j]);//chmax忘れ
      chmax(dp[i+1][j+1],dp[i][j+1]);//chmax忘れ
    }
  }
  string ans;
  int i=s.size();
  int j=t.size();
  while(i>0&&j>0){
    if(dp[i][j]==dp[i][j-1]){
      j--;
    }
    else if(dp[i][j]==dp[i-1][j]){
      i--;
    }
    else{
      ans=t[j-1]+ans;
      i--;
      j--;
    }
  }
  cout << ans << endl;
}

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

int main() {
    int n ;
    cin >> n ;
    ll ans = 1 ;
    rep(i,n){
        ans *= i + 1 ;
        ans %= (ll) 1e9 + 7 ;
    }
    cout << ans << endl;
}
    


Measured memory_bytes: 256
import Control.Monad
import Data.Array.IO

main = do

  [n,m,q] <- map read . words <$> getLine
  
  arr <- newArray ((1,1),(n,n)) 0 :: IO (IOUArray (Int,Int) Int)
  carr <- newArray ((1,1),(n,n)) 0 :: IO (IOUArray (Int,Int) Int)
  
  replicateM_ m $ do
    [l, r] <- map read . words <$> getLine
    acc <- readArray arr (l, r)
    writeArray arr (l, r) (acc+1)

  forM_ [1..n] $ \i -> do
    writeArray carr (i, 1) =<< readArray arr (i, 1)
    forM_ [2..n] $ \j -> do
      a <- readArray arr (i,j)
      s <- readArray carr (i,j-1)
      writeArray carr (i, j) (a+s)

  replicateM_ q $ do
    [p, q] <- map read . words <$> getLine
    print . sum =<< forM [p..q] (\l -> do
      ciq <- readArray carr (l,q)
      cip1 <- case p of
        1 -> return 0
        _ -> readArray carr (l,p-1)
      return (ciq - cip1))

Measured memory_bytes: 5884
#include <bits/stdc++.h>
#define lsb(x) ((x) & -(x))
using namespace std;


int main()
{
	string s;
	cin >> s;

	long long ans = 0, nr = 0;

	for (auto i : s) {
		if (i == 'B')
			nr++;
		else
			ans += nr;
	}

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 1152
class Trees():
    def __init__(self):
        self.nodes = {}
    def add_nodes(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)
    def add_child(self, id, child_id):
        self.add_nodes(child_id)
        self.nodes[id].add_child_id(self.nodes[child_id])
        
class Node():
    def __init__(self, id):
        self.node = id
        self.parent = None
        self.depth = 0
        self.nodetype = 'root'
        self.children = []
    
    def add_child_id(self, child):
        child.parent = self
        self.children.append(child)
        child.update_depth()
        self.update_nodetype()
        child.update_nodetype()
    
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()

    
    def update_nodetype(self):
        if self.depth == 0:
            self.nodetype = 'root'
        elif len(self.children) > 0:
            self.nodetype = 'internal node'
        else:
            self.nodetype = 'leaf'
    
    def __str__(self):
        parent = self.parent.node if self.parent else -1
        children = ', '.join([str(node.node) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.node, parent, 
                                                                   self.depth, self.nodetype, children)
    

tree = Trees()

n = int(input())

for i in range(n):
    a = list(map(int,input().split()))
    tree.add_nodes(a[0])
    for child in a[2:]:
        tree.add_child(id=a[0], child_id=child)

for id in range(n):
    print(f"{tree.nodes[id]}")


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

class UnionFind {
private:
  int n;
  vector<int> a;
public:
  UnionFind(int n) : n(n), a(n, -1) {}
  int find(int x) {return a[x] < 0 ? x : (a[x] = find(a[x]));}
  bool same(int x, int y) {return find(x) == find(y);}
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (a[x] > a[y]) swap(x, y);
    a[x] += a[y];
    a[y] = x;
    --n;
  }
  int size() {return n;}
  int size(int x) {return -a[find(x)];}
};

int main(){
    
    int n,m;
    cin>>n>>m;
    
    // input
    int a[m], b[m];
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    
    int ans = 0;
    for(int i=0; i<m; i++){
        UnionFind uf(n);
        // cout << uf.size() << endl;
        for(int j=0;j<m; j++){
          if(i!=j){ uf.unite(a[j],b[j]); }
        }
        if( !uf.same(a[i],b[i]) ){ ans++; }
      
        
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256