akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<queue>
#include<stack>
	

int main(){
	int n, m;
	bool isPossible= false;
	std::vector<int> depList;
	std::vector<int> arrList;

	std::cin>>n>>m;

	for(int i=0; i<m; i++){
		int tmp1, tmp2;
		std::cin>>tmp1>>tmp2;

		if(tmp1==1)
			depList.push_back(tmp2);

		if(tmp2==n)
			arrList.push_back(tmp1);
	}

	std::sort(depList.begin(), depList.end(), [](int x, int y){return x< y;});
	std::sort(arrList.begin(), arrList.end(), [](int x, int y){return x< y;});

	int i=0;
	int j=0;

	while(i<depList.size() && j<arrList.size()){
		if(depList[i]==arrList[j]){
			isPossible=true;
			break;
		}

		if(depList[i]< arrList[j])
			i++;

		if(depList[i]> arrList[j])
			j++;
	}

	if(isPossible)
		std::cout<<"POSSIBLE"<<std::endl;
	else
		std::cout<<"IMPOSSIBLE"<<std::endl;
	
	return 0;	
}


Measured memory_bytes: 1276
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

class Tree{
public:

    int N;
    vector<vector<int>> G;
    vector<int> taka;
    vector<int> aoki;
    int ans = 0;

    Tree(int n){
        N = n;
        G.resize(N);
        aoki.resize(N);
        taka.resize(N);
    }

    void make_edge(int s, int t){
        G[s].push_back(t);
        G[t].push_back(s);
    }

    void dfs_aoki(int n, int par){
        if(par == -1) aoki[n] = 0;

        for(int i = 0; i < (int)G[n].size(); i++){
            int nx = G[n][i];
            if(nx != par){
                aoki[nx] = aoki[n] + 1;
                dfs_aoki(nx, n);
            }
        }
    }

    void dfs_taka(int n, int par){
        if(par == -1) taka[n] = 0;

        for(int i = 0; i < (int)G[n].size(); i++){
            int nx = G[n][i];
            if(nx != par){
                taka[nx] = taka[n] + 1;
                dfs_taka(nx, n);
            }
        }
    }

    void dfs(int n, int par){
        if(taka[n] < aoki[n]){
            ans = max(ans, aoki[n] - 1);
        }

        for(int i = 0; i < (int)G[n].size(); i++){
            int nx = G[n][i];
            if(nx != par){
                dfs(nx, n);
            }
        }
    }

    int solve(int pt, int po){
        dfs_taka(pt, -1);
        dfs_aoki(po, -1);

        dfs(0, -1);
        return ans;
    }
};

int main(){
    int N, u, v;
    cin >> N >> u >> v;
    u--;
    v--;
    Tree tr = Tree(N);
    for(int i = 0; i < N - 1; i++){
        int a, b;
        cin >> a >> b;
        tr.make_edge(a - 1, b - 1);
    }

    cout << tr.solve(u, v) << endl;
    return 0;
}

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    lint x;
    cin >> x;

    for (lint a = -120; a <= 120; a++) {
        for (lint b = -120; b <= 120; b++) {
            if (a * a * a * a * a - b * b * b * b * b == x) {
                printf("%lld %lld\n", a, b);
                exit(0);
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3700
/*-----------------------------------------------,
|  __                                       __   |
| |  |--.-----.---.-.----.----.-----.-----.|  |_ |
| |  _  |  -__|  _  |  __|  __|  -__|  _  ||   _||
| |_____|_____|___._|____|____|_____|   __||____||
|                                   |__|         |
`-----------------------------------------------*/
#define DEBUG
#include<algorithm>
#include<array>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
typedef long long ll; using namespace std;
#define INF 1000000000000
#define MOD 10000007
#define REP(counter, limit) for (long long counter = 0; counter < limit; counter++)
int gcd(int a, int b) { if (a % b == 0) { return(b); } else { return(gcd(b, a % b)); } }
int lcm(int a, int b) { return a * b / gcd(a, b); }
bool primenum(int a) { if (a == 1) { return false; }if (a == 2) { return true; }if (a % 2 == 0) { return false; }for (int i = 3; i < sqrt(a) + 1; i += 2) { if (a != i) { if (a % i == 0) { return false; } } }return true; }
struct setupios{setupios(){cin.tie(0);ios::sync_with_stdio(0); /*cout<<fixed<<setprecision(20);*/};}setupios;
int main() {

  string o,e;
  cin>>o>>e;
  int i=0;
  while(true){
    if(i<o.size()){
      cout<<o[i];
    }
    if(i<e.size()){
      cout<<e[i];
    }
    i++;
    if(i >= o.size() and i >= e.size()){
      cout<<endl;
      return 0;
    }
  }

}


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

unsigned long long int gcd(unsigned long long int a, unsigned long long int b) {
	return (a%b) ? gcd(b, a%b) : b;
}

int main() {
	unsigned long long int a, b, c, d, ans = 0, g;
	cin >> a >> b >> c >> d;
	g = gcd(c, d);
	ans += ((b - a) + 1 + (a - 1) % c) / c;
	ans += ((b - a) + 1 + (a - 1) % d) / d;
	ans -= ((b - a) + 1 + (a - 1) % (c*d / g)) / (c*d / g);
	ans = b - a + 1 - ans;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstring>
#include <stack>
using namespace std;

int dfs(vector<bool> &visited, vector<vector<int> > &g, int node){
    visited[node] = true;
    int con = 1;
    for(int child : g[node]){
	if(visited[child])
	    continue;
	con += dfs(visited, g, child);
    }
    return con;
}

int main(){
    int n, m; cin>>n>>m;
    vector<vector<int> > g(n);
    int a, b;
    for(int i = 0; i<m; i++){
	cin>>a>>b;
	a--; b--;
	g[a].push_back(b);
	g[b].push_back(a);
    }
    
    vector<bool> visited(n, false);
    int gr = 0;
    for(int i = 0; i<n; i++){
	if(visited[i]){
	    continue;
	}
	gr = std::max(dfs(visited, g, i), gr);
    }
    cout<<gr<<'\n';
}


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

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

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

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

typedef pair<int, int> pii;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<long long int> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<long long int>> vvll;

int main() {
  int h, w;
  cin >> h >> w;

  vvc G(h+2, vc(w+2));
  rep(i, w+2) {
    G[0][i] = '#';
    G[h+1][i] = '#';
  }
  for(int i=1;i<=h;i++) {
    G[i][0] = '#';
    for(int j=1;j<=w;j++) {
      cin >> G[i][j];
    }
    G[i][w+1] = '#';
  }

  vvi row(h+2, vi(w+2));
  vvi column(h+2, vi(w+2));

  for(int i=1;i<=h;i++) {
    for(int j=1;j<=w;j++) {
      if(G[i][j] == '#') continue;
      if(G[i][j-1] == '#') {
        for(int k=j+1;k<w+2;k++) {
          if(G[i][k] == '#') {
            row[i][j] = k - j;
            break;
          }
        }
      } else row[i][j] = row[i][j-1];
    }
  }

  for(int i=1;i<=h;i++) {
    for(int j=1;j<=w;j++) {
      if(G[i][j] == '#') continue;
      if(G[i-1][j] == '#') {
        for(int k=i+1;k<h+2;k++) {
          if(G[k][j] == '#') {
            column[i][j] = k - i;
            break;
          }
        }
      } else column[i][j] = column[i-1][j];
    }
  }

  int max = 0;

  for(int i=1;i<=h;i++) {
    for(int j=1;j<=w;j++) {
      if(row[i][j] + column[i][j] - 1 > max) max = row[i][j] + column[i][j] - 1;
    }
  }

  cout << max << endl;
}

Measured memory_bytes: 35712
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<cstdio>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define MAX 100
using namespace std;
typedef long long ll;

/*
dp[day][hotel][number] := minimum
 */
int dp[MAX][MAX][MAX];
int path[MAX][MAX][MAX];
int N,D,p[MAX][MAX];
int debug[MAX];


int main()
{
  scanf("%d %d",&N,&D);
  rep(i,MAX)debug[i] = inf;
  rep(i,N)
    {
      rep(j,D)
	{
	  scanf("%d",&p[i][j]);
	  debug[j] = min(debug[j],p[i][j]); 
	}
      reverse(p[i],p[i]+D);
    }

  rep(i,MAX)rep(j,MAX)rep(k,MAX)
    {
      dp[i][j][k] = inf;
      path[i][j][k] = inf;
    }


  rep(i,N)dp[0][i][0] = 0;

  rep(day,D)
    {
      rep(hotel,N)
	{
	  rep(number,55)
	    {
	      if(dp[day][hotel][number] == inf)continue;
	      rep(next_hotel,N)
		{
		  int add = (hotel != next_hotel);
		  if(dp[day+1][next_hotel][number+add] > dp[day][hotel][number]+p[next_hotel][day])
		    {
		      dp[day+1][next_hotel][number+add] = dp[day][hotel][number]+p[next_hotel][day];
		      path[day+1][next_hotel][number+add] = hotel;
		    }
		  else if(dp[day+1][next_hotel][number+add] == dp[day][hotel][number]+p[next_hotel][day])
		    {
		      if(path[day+1][next_hotel][number+add] > hotel)path[day+1][next_hotel][number+add] = hotel;
		    }

		}
	    }
	}
    }

  int mincost,minnumber,minN;
  mincost = minnumber = minN = inf;

  int debug_i = 0;
  rep(i,D)debug_i += debug[i];

  rep(i,N)rep(j,55)
    {
      if(mincost >= dp[D][i][j])
	{
	  if(mincost == dp[D][i][j])
	    {
	      //cout << "in( mincost : " << mincost << ", minnumber : " << minnumber << ", minN " << minN << ") dp[" << D << "]["<< i << "][" << j << "] = " << dp[D][i][j] << endl;
	      if(minnumber >= j)
		{
		  if(minnumber == j)
		    {
		      if(minN > i)
			minN = i;
		    }
		  else
		    {
		      minnumber = j;
		      minN = i;
		    }
		}
	      //cout << "out( mincost : " << mincost << ", minnumber : " << minnumber << ", minN " << minN << ")" << endl;
	    }
	  else
	    {
	      mincost = dp[D][i][j];
	      minnumber = j;
	      minN = i;
	      //cout << "( mincost : " << mincost << ", minnumber : " << minnumber << ", minN " << minN << ")" << endl;
	    }
	}
    }

  //cout << "!!!( mincost : " << mincost << ", minnumber : " << minnumber << ", minN " << minN << ")" << endl;
  assert(mincost != inf);
  assert(minnumber != inf);
  cout << mincost << " " << minnumber << endl;
  vector<int> ph;
  int d,h,n;

  d = D,h = minN, n = minnumber;

  int diff = p[h][D-1];
  for(;d >= 0 && n >= 0;)
    {
      ph.push_back(h);

      int next_h = path[d][h][n];
      int next_n = n - (next_h != h);
      h = next_h;
      n = next_n;
      d--;
      diff += p[h][d-1];
      if(path[d][h][n] == inf)break;
    }
  //assert(diff >= mincost);
  //assert(diff == mincost);
  //reverse(ph.begin(),ph.end());
  assert(ph.size() == D);
  rep(i,ph.size())
    {
      cout << ph[i]+1 << endl;
      assert(ph[i]!=inf);
    }
  //assert(debug_i == mincost);
    
  return 0;
}

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

int ind;
int rmed[110];
vector<int> edge[110];
int dist[110], did[110];


void dfs(int par) {
    int a;
    cin >> a;
    if (a == 0) dfs(par);
    else if (a > 0) {
        int i = ++ind;
        rmed[i] = a;
        if (par == -1) {
            dist[i] = 0;
            did[0] = 1;
        }
        else {
            edge[par].push_back(i);
            edge[i].push_back(par);
            dist[i] = dist[par] + 1;
            did[dist[i]] = i;
            --rmed[par];
            --rmed[i];
        }
        while (rmed[i] > 0) {
            dfs(i);
        }
    }
    else {
        edge[par].push_back(did[dist[par] + a]);
        edge[did[dist[par] + a]].push_back(par);
        --rmed[par];
        --rmed[did[dist[par] + a]];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        ind = 0;
        for (int j = 0; j < 110; ++j) {
            rmed[j] = 0;
            dist[j] = -1;
            did[j] = -1;
            edge[j].clear();
        }
        dfs(-1);
        for (int j = 1; j < 110; ++j) {
            if (edge[j].size() == 0) break;
            sort(edge[j].begin(), edge[j].end());
            cout << j;
            for (int k : edge[j]) {
                cout << " " << k;
            }
            cout << "\n";
        }
    }

    return 0;
}

Measured memory_bytes: 3112
import math

x = int(input())

l = math.floor(math.log(abs(x), 5)) + 1000

s = [i**5 for i in range(l)]

a, b = [0,0]

for i in range(l):
    for j in range(l):
        if s[i] +s[j] == x:
            a, b = i, -j
            break
        elif s[i] - s[j] == x:
            a, b = i, j
            break

print(str(a) + " " + str(b))

Measured memory_bytes: 9216
### subroutines

def lower_bound(arr, key, i0 = 0, i1 = arr.length)
  lb = i0 - 1
  ub = i1

  while lb + 1 < ub
    m = (lb + ub) / 2
    if arr[m] <= key
      lb = m
    else
      ub = m
    end
  end
  lb
end

def div_three?(k)
  #puts "k=#{k}"
  for i in (0...$n)
    imax = i + $n
    #puts " i=#{i}, imax=#{imax}"
    i0 = lower_bound($asums, k + $asums[i] - 1, i, imax) + 1
    #puts "  i0=#{i0}"
    if i0 < imax
      i1 = lower_bound($asums, k + $asums[i0] - 1, i0, imax) + 1
      #puts "  i1=#{i1}"
      if i1 < imax &&
          $asums[imax] - $asums[i1] >= k
        return true
      end
    end
  end

  false
end

### main

$n = gets.strip.to_i

$ais = $n.times.map{gets.strip.to_i}
$ais += $ais
#p $ais

$asums = [0]
(1..(2 * $n)).each{|i| $asums[i] = $asums[i - 1] + $ais[i - 1]}
#p $asums

k0 = 0
k1 = $asums[$n] / 3

while k0 + 1 < k1
  km = (k0 + k1) / 2
  if div_three?(km)
    k0 = km
  else
    k1 = km
  end
end

puts k0

Measured memory_bytes: 10168
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
const int mod= 1e+9+7;

int main() {
    int N;
    cin>>N;
    vector<ll>a(N);
    vector<ll>c(N,0);
    vector<ll>d(N,0);
    rep(i,N){
        cin>>a[i];
        c[a[i]-1]++;
    }
    ll ans =0;
    rep(i,N){
        d[i]=c[i]*(c[i]-1)/2;
        ans +=d[i];
    }
    rep(i,N){
        cout<<ans-c[a[i]-1]+1<<endl;
    }
}


Measured memory_bytes: 7680
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n): #iから直接jのときと頂点kを経由した場合の比較
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
h,w=map(int,input().split())
field=[list(map(int,input().split())) for i in range(10)]
wall=[[int(i) for i in input().split()] for i in range(h)]
n=10

ans=0
d=warshall_floyd(field)
for i in wall:
    for j in i:
        if j==-1:
            pass
        else:
            ans+=d[j][1]
print(ans)

Measured memory_bytes: 40284
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    char c; cin >> c;
    char d = c + 1;
    cout << d << endl;
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int main(){
	vector<string> str;
	int count[1000]={0};
	//int length[1000]={0};
	string max_length="";

	string s;
	while(cin >> s){
		int i;
		bool find_flag = 1;
		for(i=0;i<str.size();i++){
			if(str[i]==s){
				count[i]++;
				find_flag = 0;
				break;
			}
		}
		if( find_flag ){
			str.push_back(s);
			if(s.size()>max_length.size()){
				max_length = s;
			}
		}
	}
	
	int max = 0;
	for(int i=0;i<str.size();i++){
		if(count[i]>count[max]){
			max=i;
		}
	}
	cout << str[max] << " " << max_length << endl;
	
	return 0;
}

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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    long A;
    string B;
    cin >> A >> B;
    int a, b;
    a = (B[0] - '0')*100;
    b = (B[2] - '0') * 10 + (B[3] - '0');
    long C =  a + b;
    long ans = A * C;
    ans = ans / 100;
    cout << ans << endl;
}

Measured memory_bytes: 3536
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<int, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

const int N = (int)1e5 + 9;

int main(){
    fastIO;
    int n;
    cin >> n;
    ll res = 0;
    ll sum = 0;
    ll x;
    for(int i = 0 ; i < n; i ++ ){
        cin >> x;
        if(x==0){
            res+=sum/2;
            sum=0;
        }
        else{
            sum += x;
        }
    }
    res+=sum/2;
    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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;
}

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define F first
//#define S second

typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1000000;
const int minf = -1000000;
const ll lnf = 1e12;
const ll mlnf = -1e12;
const double e = 1e-10;

void debug_vector(vector<int>& v)
{
    int n = v.size();
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}


//////////////////////
//// coding start ////
//////////////////////

// global variety
int N;
string S;

// function
long long second_condition(int locate);
void solve();

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

long long second_condition(int locate){
    int limit = min(locate, N-1 - locate);
    long long res = 0;
    for (int i = 1; i <= limit; i++){
        set<char> tmp;
        tmp.insert(S[locate]);
        tmp.insert(S[locate + i]);
        tmp.insert(S[locate - i]);
        if (tmp.size() == 3) res++;
    }
    return res;
}

void solve(){
    cin >> N;
    cin >> S;
    long long r, g, b;
    r = 0;
    g = 0;
    b = 0;
    for (int i = 0; i < N; i++){
        if (S[i] == 'R'){
            r++;
        }else if(S[i] == 'G'){
            g++;
        }else{
            b++;
        }
    }
    long long ans = r * g * b;
    for (int i = 1; i < N - 1; i++){
        ans -= second_condition(i);
    }

    printf("%lld\n", ans);
}



Measured memory_bytes: 3716
/*******************************************************************************/
//
//n????????´??°a_i(i=1,2,...n)?????\?????????????????????????°????????????§??????????¨????????±???????????????°??????
//
//Input  :1???????????´??°?????°n????????????????????????
//		  2?????????n????????´??°a_i????????????????????§?????????????????????
//Output :????°????????????§??????????¨????????????????????????§???????????????
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_4_D&lang=jp
/*******************************************************************************/

#include<stdio.h>

#define NUM_MAX 10000
#define NUM_MIN 0
#define VAL_MAX 1000000
#define VAL_MIN -1000000

int main()
{
	int n,a[NUM_MAX];
	char c;
	int min,max;
	long sum=0;
	
	if( scanf("%d%c", &n, &c)!=2 )
	{
		/* ERROR */
		return -1;
	}
	
	if((n<=NUM_MIN) || (n>NUM_MAX))
	{
		/* ERROR */
		return -1;
	}
	
	for(int i=0; i<n; i++)
	{
		if( scanf("%d ", &a[i])!=1 )
		{
			/* ERROR */
			return -1;
		}
		
		/* a,b?????¶?´? */
		if((a[i]>=VAL_MIN) && (a[i]<=VAL_MAX))
		{
			if(a[i]<min) min=a[i];
			if(a[i]>max) max=a[i];
			sum+=a[i];
		}
		else
		{
			/* ERROR */
			return -1;
		}
		
		if(i==0)
		{
			min=a[i];
			max=a[i];
		}
	}
	
	printf("%d %d %ld\n", min, max, sum);
	
	return 0;
}

Measured memory_bytes: 1820
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>
#include <sstream>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

/*
0のアスキー　"48"
*/

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) x.begin(),x.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))


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

    vector<ll> A(N),rui(N-1);

    ll res = 0;
    for(ll i = 0;i < N;i++){
        cin >> A.at(i);
        res += A.at(i);
    }

    ll ans = 0;

    for(ll i = 0;i < N-1;i++){
        res -= A.at(i);
        rui.at(i) = res;
        //cout << rui.at(i) << endl;
    }

    for(ll i = 0;i < N-1;i++){
        ans += ((A.at(i) % MOD) * (rui.at(i) % MOD)) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;

}





    

Measured memory_bytes: 6252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;} return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;} return false;
}

vector<ll> divisor(ll n){
    vector<ll> res;
    for (ll i=1;i*i<=n;++i) if (n%i==0){
        res.emplace_back(i);
        if (i!=n/i) res.emplace_back(n/i);
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<ll> cand=divisor(N);
    ll ans=0;
    for (ll x:cand){
        ll y=N/x-1;
        if (x<y) ans+=y;
    }
    cout << ans << '\n';
}

Measured memory_bytes: 384
#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn rec(n: i64, nums: &[i64], sum: i64) -> i64 {
    if let Some(&v) = nums.first() {
        rec(v, &nums[1..], n + sum) + rec(n * 10 + v, &nums[1..], sum)
    } else {
        n + sum
    }
}

fn main() {
    let s = scan!()
        .chars()
        .map(|c| i64::from(c.to_digit(10).unwrap()))
        .collect::<Vec<_>>();
    println!("{}", rec(s[0], &s[1..], 0));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define iterator IT
#define SIZ(V) V.size()
#define FS(a) fixed<<setprecision(a)
using namespace std;
namespace STARTER {
	int MAX(int a,int b) {return a>b?a:b;}
	int MIN(int a,int b) {return a<b?a:b;}
	int ABS(int a) {return a<0?-a:a;}
	int GCD(int a,int b) {return !b?a:GCD(b,a%b);}
	int LCM(int a,int b) {return a/GCD(a,b)*b;}
	int QSM(int a,int b,int p) {int ret=1;while (b) (b&1)&&(ret=ret*a%p),a=a*a%p,b>>=1;return ret;}
	int ROUND(double a) {return a+0.5;}
}
using STARTER::MAX;
using STARTER::MIN;
using STARTER::ABS;
using STARTER::GCD;
using STARTER::LCM;
using STARTER::QSM;
using STARTER::ROUND;
int main() {
	int x;cin>>x;
	int ans=x/500*1000;
	if (x%500) {
		int a=x%500;
		ans+=a/5*5;
	}
	cout<<ans<<'\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
template <class T = ll>
T IN(){T x;cin>>x;return (x);}
 
template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
    seco.resize(head);
    VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
    VECCIN(head);
    VT2(move(tail)...);
}
 
template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
    seco[head]=IN();
    VT3(head,move(tail)...);
}
 
#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc
 
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision; // cpp_int
 
#define P pair<ll,ll>
#define V vector<ll>
#define M map<ll,ll>
#define S set<ll>
 
#define pb(a) push_back(a)
#define mp make_pair
 
int main(){
    CIN(n);
    V dp(n+1,LINF);
    //dp[i]:i円引き出すための操作回数

    dp[0]=0;
    FOR(i,1,n+1){
        dp[i] = i;
        ll six = 6;
        while(i - six >= 0){
            dp[i] = min(dp[i-six] + 1,dp[i]);
            six *= 6;
        }
        ll nine = 9;
        while(i - nine >= 0){
            dp[i] = min(dp[i-nine] + 1,dp[i]);
            nine *= 9;
        }
    }
    COUT(dp[n]);

    return 0;
}

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

#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;
constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;
const long double PI = (acos(-1));
const ull MOD = 1000000007;


struct __INIT {
    __INIT() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __init;


int main() {
    double A, B, X;
    cin >> A >> B >> X;
    double theta;
    if(X >= A * A * B / 2.0){
        theta = atan(2 * (A * A * B - X) / (A * A * A));
    }else{
        theta = atan(A * B * B / (2 * X));
    }
    cout << theta * 180 / PI << endl;
}

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

int N;//limit value

int dfs(long long now, bool is3, bool is5, bool is7){
	if(now > N) return 0;//exceeded value limit?
	int count = is3 && is5 && is7? 1:0;//{3,5,7} all used -> +1
	count += dfs(now*10+3, true, is5, is7);
	count += dfs(now*10+5, is3, true, is7);
	count += dfs(now*10+7, is3, is5, true);
	return count;
}

int main(){
	cin>>N;
	cout<< dfs(0, false, false, false) <<endl;
}

Measured memory_bytes: 256
//Created by Kira

#include<bits/stdc++.h>
using namespace std;

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);
    

const int N = 1e7 + 1;

ll a[N];

int main(){
   IOS

    int n; cin>>n;
    
    for(int i = 2; i <= n; i++){
        a[i] = 2;
    }
    a[1] = 1;

    for(int i = 2; i <= n / 2; i++){
        for(int j = 2 * i; j <= n; j += i){
            a[j]++;
        }
    }

    ll ans = 0;
    for(ll k = 1; k <= n; k++){
        ans += k * a[k];
    }
    cout<<ans<<"\n";



}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
    if(b&1) res = res * a % mod;
        a = a * a % mod;
    b >>= 1;
    }

    return res;
}



Measured memory_bytes: 81720
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    vector<pair<int,int>> solve(int n, int K) {
        int N = (n - 1) * (n - 2) / 2;
        if (K > N) {
            return {};
        }


        vector<pair<int,int>> res;
        for (int i = 1; i < n; ++i) {
            res.emplace_back(0, i);
        }
        for (int i = 1; i < n && K < N; ++i) {
            for (int j = i + 1; j < n && K < N; ++j) {
                res.emplace_back(i, j);
                --N;
            }
        }
        return res;

    }
};

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

    int n;
    int k;
    cin >> n >> k;

    Solution sol;
    auto res = sol.solve(n, k);
    if (res.empty()) {
        cout << -1 << "\n";
    } else {
        cout << res.size() << "\n";
        for (auto& r : res) {
            cout << r.first + 1 << " " << r.second + 1 << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 384
# inputList = list(map(int, '''5
# 5 3 2 4 1'''.split()))
# N = inputList.pop(0)


def formatting(nums):
    for i in range(len(nums)):
        if i != len(nums) - 1:
            print(nums[i], end=' ')
        else:
            print(nums[i])


def bubbleSort(A, N):
    count = 0
    i = 0
    flag = 1
    while flag:
        flag = 0

        for j in range(N - 1, i, -1):
            if A[j] < A[j-1]:
                temp = A[j]
                A[j] = A[j-1]
                A[j-1] = temp
                count += 1
                flag = 1
        i += 1
    formatting(A)
    print(count)




N = int(input())
inputList = list(map(int, input().split()))

bubbleSort(inputList, N)



Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using plll=pair<ll,pll>;
using graph=vector<vector<int>>;
using wgraph=vector<vector<pll>>;

const ll MOD=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

void pushHeap(vector<ll>& h,int n){
  int i=h.size();
  h.push_back(n);
  while(i!=0 && h[(i-1)/2]<h[i]){
    swap(h[i],h[(i-1)/2]);
    i=(i-1)/2;
  }
  h[i]=n;
}

ll popHeap(vector<ll>& h){
  int n=h.size()-1;
  if(n==-1)return 0;
  ll i,ret=h[0];
  swap(h[0],h[n]);
  h.pop_back();
  for(i=0;i<n;){
    int j=2*i+1;
    if(j>=n)break;
    if(j!=n-1 && h[j]<h[j+1])j++;
    if(h[i]<h[j]){
      swap(h[i],h[j]);
    }
    i=j;
  }
  return ret;
}

int bis(vector<int> v,int key){
  int left=-1,right=v.size();
  while(abs1(right-left)>1){
    int mid=left+(right-left)/2;
    if(v[mid]<=key)left=mid;
    else right=mid;
  }
  return left;
}

int main(){
  int i,j,k,cnt=0;
  int a,b;
  cin>>a>>b;
  for(i=1;i<=3;i++){
    if(i!=a && i!=b){
      cout<<i<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import math


def solve(N: int):
    # X * 1.08 = N
    # X = N / 1.08

    for i in range(1, 50001):
        if N == math.floor(i * 1.08):
            print(i)
            return
    print(":(")


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == "__main__":
    main()


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

int main() {
    int n;
    cin >> n;
    int d[n];
    for(int i=0;i<n;i++)
        cin >> d[i];
    
    sort(d,d+n);

    
    cout << d[n/2]-d[n/2-1];
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int a[15];
int num=1,len;
long long ans=0;
string s;
int main()
{
	cin>>s;
	len=s.size();
	for(int i=0;i<len;i++)
		a[i+1]=(s[i]-'0');
	for(int i=1;i<len;i++)
		num*=2;
	for(int i=0;i<num;i++)
	{
		bool b[15]={0};
		int tmp=i;
		int k=1;
		while(tmp)
			b[k++]=tmp%2,tmp/=2;
		long long cn=0;
		for(int j=1;j<=len;j++)
		{
			cn=cn*10+a[j];
			if(b[j])
			{
				ans+=cn;
				cn=0;
			}
		}
		ans+=cn;
	}
	cout<<ans; 

	return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAX = (2e5)+1;
 
int n, p[MAX];
vector<int> res;
map<pii, pair<pii, pii> > pq;
 
struct segment_tree {
	int a[MAX], t[2*MAX];
	void build() {
		for(int i = 0; i < n; i++) t[i + n] = i;
		for(int i = n-1; i >= 1; i--) {
			if(a[t[i<<1]] < a[t[i<<1|1]]) t[i] = t[i<<1];
			else t[i] = t[i<<1|1];
		}
	}
	int query(int l, int r) {
		int ret = l;
		++r;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				if(a[t[l]] < a[ret]) ret = t[l];
				++l;
			}
			if(r & 1) {
				--r;
				if(a[t[r]] < a[ret]) ret = t[r];
			}
		}
		return ret;
	}
} st[2];
 
pii getxy(int l, int r) {
	int xi = st[l % 2].query(l, r);
	int yi = st[l % 2 ^ 1].query(xi+1, r);
	return make_pair(xi, yi);
}

pii getpxy(int l, int r) {
	pii res = getxy(l, r);
	return make_pair(p[res.first], p[res.second]);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	fill(st[0].a, st[0].a+n, INT_MAX);
	fill(st[1].a, st[1].a+n, INT_MAX);
	for(int i = 0; i < n; i++) cin >> p[i], st[i % 2].a[i] = p[i];
 
	st[0].build();
	st[1].build();
 
	pq[getpxy(0, n-1)] = make_pair(getxy(0, n-1), make_pair(0, n-1));
	for(int l, r, xi, yi; !pq.empty(); ) {
		tie(xi, yi) = pq.begin()->second.first;
		tie(l, r) = pq.begin()->second.second;
		assert(r-l % 2 > 0 && yi-xi % 2 > 0);
		pq.erase(pq.begin());
		res.push_back(p[xi]);
		res.push_back(p[yi]);
		if(xi+1 < yi-1) pq[getpxy(xi+1, yi-1)] = make_pair(getxy(xi+1, yi-1), make_pair(xi+1, yi-1));
		if(l < xi-1) pq[getpxy(l, xi-1)] = make_pair(getxy(l, xi-1), make_pair(l, xi-1));
		if(yi+1 < r) pq[getpxy(yi+1, r)] = make_pair(getxy(yi+1, r), make_pair(yi+1, r));
	}
	for(int i = 0; i < n; i++) cout << res[i] << ' ';
}


Measured memory_bytes: 10356
import java.util.*;

public class Main{
  
  public static void main(String[] args){
  
    Scanner sc = new Scanner(System.in);
    int x= sc.nextInt();
    
    int canBuy = x/100;
    int change = x%100 ;
    
    for(int i = 0; i < canBuy; i++){
      if(change >= 5){
        change -= 5;
      }else if(change >= 4){
        change -= 4;
      }else if(change >= 3){
        change -= 3;
      }else if(change >= 2){
        change -= 2;
      }else if(change >= 1){
        change -= 1;
      }
    }
    
    if(change == 0){
      System.out.println("1");
    }else{
      System.out.println("0");
    }
    
  }  
}

Measured memory_bytes: 35792
def d_coloring_edges_on_tree():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    # tree[a][b]: 頂点 a-b 間を結ぶ辺は何色で塗られているか
    tree = {i: dict() for i in range(N)}
    for a, b in Edges:
        tree[a - 1][b - 1] = -1
        tree[b - 1][a - 1] = -1

    k = max(len(tree[a]) for a in range(N))  # k (最大次数) 色で辺を塗れる
    used_color = [-1] * N
    used_color[0] = k - 1

    q = deque([0])
    while q:
        current = q.pop()
        color_current = used_color[current]  # ここで色は0オリジンとする
        for child in tree[current].keys():
            if used_color[child] != -1:
                continue  # もう塗っていた (current の親だった)
            color_current = (color_current + 1) % k
            tree[current][child] = color_current
            tree[child][current] = color_current
            used_color[child] = color_current
            q.appendleft(child)

    ans = [k] + [tree[a - 1][b - 1] + 1 for a, b in Edges]
    return ' '.join(map(str, ans))

print(d_coloring_edges_on_tree())

Measured memory_bytes: 76664
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	int m,f,r,x,i,flg;
	while(1){
		for(i=0;i<1;i++){
			cin>>m>>f>>r;
			x=m+f;
			flg=0;
			if(m==-1&&f==-1&&r==-1) break;
			if(m==-1) flg=1;
			if(f==-1) flg=1;
			if(x>=80) cout<<"A"<<endl;
			if(x>=65&&x<80) cout<<"B"<<endl;
			if(x>=50&&x<65) cout<<"C"<<endl;
			if(x<30) flg=1;
			if(flg==1){
				cout<<"F"<<endl;
				break;
			}
			if(x>=30&&x<50){
				if(r>=50) cout<<"C"<<endl;
				else cout<<"D"<<endl;
			}
		}
		if(m==-1&&f==-1&&r==-1) break;
	}
	return 0;
}



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

int main() {
  int r, g, b;
  cin >> r >> g >> b;

  int a = r * 100 + g * 10 + b;
  if(a % 4 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y == 0:
        return x
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z

L = [0 for _ in range(len(A))]
for i,a in enumerate(A[:-1]):
    L[i+1] = gcd(L[i],a)
R = [0 for _ in range(len(A))]
for i,a in enumerate(A[:0:-1]):
    R[i+1] = gcd(R[i],a)
R = R[::-1]

G = 0
for l,r in zip(L,R):
    g = gcd(l,r)
    if G < g:
        G = g

print(G)

Measured memory_bytes: 14524
"""
NTC here
"""
 
 
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1
 
 
def iin(): return int(input())


def lin(): return list(map(int, input().split()))


def main():
    n = iin()
    a = lin()
    sm = 0
    for i in range(0, n, 2):
        sm = sm^a[i]^a[i+1]
    a = [i^sm for i in a]
    print(*a)






    




                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

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

int main(){
    int h, n;
    cin >> h >> n;
    vector<int> a(n);
    rep(i, n){
        cin >> a.at(i);
    }
    string ans = "No";
    int total = 0;
    rep(i, n){
        total += a.at(i);
    }
    if(h <= total){
        ans = "Yes";
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
import java.util.*;
import java.io.*;

public class Main {
	static FastReader in = new FastReader();

	public static void main(String[] args) {
		solve();
	}

	static long MOD = (int) 1e9 + 7;
	
	static void solve() {
		int n = in.nextInt();
		int[] arr = in.readarr(n);
		
		long sum = 0;
		long[] psums = new long[n + 1];
		for(int i = 0; i < n; i++)
		{
			psums[i + 1] = arr[i] + psums[i];
			psums[i + 1] %= MOD;
		}


		for(int i = 0; i < n; i++)
		{
			boolean flag = false;
			if(psums[n] < psums[i + 1]) 
			{
				psums[n] += MOD;
				flag = true;
			}
			long curr = (psums[n] - psums[i + 1]) * arr[i];
			curr %= MOD;
			sum += curr;
			sum %= MOD;
			if(flag)
				psums[n] -= MOD;
			
		}
		System.out.println(sum);
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		int[] readarr(int abc) {
			int[] a = new int[abc];
			for (int i = 0; i < abc; i++)
				a[i] = nextInt();
			return a;
		}
	}
}





Measured memory_bytes: 54992
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	vector<int> ns(n+1);
	int t;
	for(t=1;t<=n;t++)
		scanf("%d",&ns[t]);
	ns[0] = -111;
	int s=0;
	int w=0;
	for(t=1;t<=n;t++)
	{
		if(ns[t] == t)
			s++;
		if(t>w+1 && ns[t-1]==t-1 && t==ns[t])
		{
			w = t;
			s--;
		}
	}
	printf("%d\n",s);
	return 0;
}

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

int main(){

  const int MAX = 21;
  int n, m;

  while(cin >> n){
    if(n == 0) break;

    vector<vector<bool> > p(MAX, vector<bool>(MAX, 0));
    int x, y;
    for(int i=0; i<n; i++){
      cin >> x >> y;
      p[x][y] = 1;
    }

    string v;
    int px,py;
    px = py = MAX/2;
    int g, cnt=0;
    cin >> m;
    for(int i=0; i<m; i++){
      cin >> v >> g;
      //N
      if(v == "N"){
	for(int j=1; j<=g; j++){
	  py++;
	  if(p[px][py]){
	    cnt++;
	    p[px][py] = 0;
	  }
	}
      }
      //E
      if(v == "E"){
	for(int j=1; j<=g; j++){
	  px++;
	  if(p[px][py]){
	    cnt++;
	    p[px][py] = 0;
	  }
	}
      }
      //S
      if(v == "S"){
	for(int j=1; j<=g; j++){
	  py--;
	  if(p[px][py]){
	    cnt++;
	    p[px][py] = 0;
	  }
	}
      }
      //W
      if(v == "W"){
	for(int j=1; j<=g; j++){
	  px--;
	  if(p[px][py]){
	    cnt++;
	    p[px][py] = 0;
	  }
	}
      }
    }
      if(cnt == n){
	cout << "Yes" << endl;
      }
      else{
	cout << "No" << endl;
      }
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main() {
    string a, b, c;
    cin >> a >> b >> c;

    if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256