akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict


def resolve():
    n = int(input())
    v = list(map(int, input().split()))
    d_o = defaultdict(int)
    d_e = defaultdict(int)
    for i in range(n):
        if i % 2:
            d_o[v[i]] += 1
        else:
            d_e[v[i]] += 1
    d_e[0] = 0
    d_o[0] = 0
    de = sorted(d_e.items(), key=lambda x: -x[1])
    do = sorted(d_o.items(), key=lambda x: -x[1])
    if de[0][0] != do[0][0]:
        print(n - de[0][1] - do[0][1])
    else:
        p01 = de[0][1] + do[1][1]
        p10 = de[1][1] + do[0][1]
        print(n - max(p01, p10))


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 65388
#ifdef _WIN32
#define DEBUG	1
#endif

#define _CRT_SECURE_NO_WARNINGS
#define MATH_PI 3.14159265358979323846264338327950288419716939
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;

#ifdef DEBUG
#include "include.h"
#else
inline void wait(){}
inline void dout(const char *arg, ...){}
#endif

//template<typename T>inline void swap(T a, T b){T t = a; a = b; b = t;}

#define CLIP(ptr, min, max) {if((min)<=(max)){if(ptr<(min)){ptr=(min);}if(ptr>(max)){ptr=(max);}}}
#define max(a, b) a > b ? a : b;
#define min(a, b) a > b ? b : a;
#define Sin(deg) sin((deg)*MATH_PI/180)
#define Cos(deg) cos((deg)*MATH_PI/180)
#define Tan(deg) tan((deg)*MATH_PI/180)
#define Rad(deg) ((deg)*MATH_PI/180)
#define ff(param, num) for(int param=0 ; param<num ; ++param)
#define fi(num) for(int i=0 ; i<num ; ++i)
#define fj(num) for(int j=0 ; j<num ; ++j)
#define fk(num) for(int k=0 ; k<num ; ++k)
#define fl(num) for(int l=0 ; l<num ; ++l)
#define fn(num) for(int n=0 ; n<num ; ++n)
#define ffr(param, num) for(int param=num-1 ; param>=0 ; --param)
#define fir(num) for(int i=num-1 ; i>=0 ; --i)
#define fjr(num) for(int j=num-1 ; j>=0 ; --j)
#define fkr(num) for(int k=num-1 ; k>=0 ; --k)
#define flr(num) for(int l=num-1 ; l>=0 ; --l)
#define fnr(num) for(int n=num-1 ; n>=0 ; --n)
#define gi(p) Scanf("%d", p)
#define gi2(p1, p2) Scanf2("%d %d", p1, p2)
#define gi3(p1, p2, p3) Scanf3("%d %d %d", p1, p2, p3)
#define gi4(p1, p2, p3, p4) Scanf4("%d %d %d %d", p1, p2, p3, p4)
#define gll(p) Scanf("%lld", p)
#define gll2(p1, p2) Scanf2("%lld %lld", p1, p2)
#define gll3(p1, p2, p3) Scanf3("%lld %lld %lld", p1, p2, p3)
#define gll4(p1, p2, p3, p4) Scanf4("%lld %lld %lld %lld", p1, p2, p3, p4)
#define gf(p) Scanf("%f", p)
#define gf2(p1, p2) Scanf2("%f %f", p1, p2)
#define gf3(p1, p2, p3) Scanf3("%f %f %f", p1, p2, p3)
#define gf4(p1, p2, p3, p4) Scanf4("%f %f %f %f", p1, p2, p3, p4)
#ifdef DEBUG
#define gc(buf) fscanf(local_in.fp, "%s", buf)
#define Scanf(expr, p) fscanf(local_in.fp, expr, &p)
#define Scanf2(expr, p1, p2) fscanf(local_in.fp, expr, &p1, &p2)
#define Scanf3(expr, p1, p2, p3) fscanf(local_in.fp, expr, &p1, &p2, &p3)
#define Scanf4(expr, p1, p2, p3, p4) fscanf(local_in.fp, expr, &p1, &p2, &p3, &p4)
#else
#define gc(buf) Scanf("%s", buf)
#define Scanf(expr, p) scanf(expr, &p)
#define Scanf2(expr, p1, p2) scanf(expr, &p1, &p2)
#define Scanf3(expr, p1, p2, p3) scanf(expr, &p1, &p2, &p3)
#define Scanf4(expr, p1, p2, p3, p4) scanf(expr, &p1, &p2, &p3, &p4)
#endif
#define ans(p) cout << p << endl;
int EuclideanAlgorithm(int N, int *array){
	fn(N - 1) {
		while (true) {
			if (array[n] % array[n + 1] == 0 || array[n + 1] % array[n] == 0) {
				array[n + 1] = min(array[n], array[n + 1]);
				break;
			}
			if (array[n] > array[n + 1]) {
				array[n] %= array[n + 1];
			}
			else {
				array[n + 1] %= array[n];
			}
		}
	}
	return array[N - 1];
}

signed main() {

	int ii, jj, kk, ll;
	int N;
	int ret = 0;
	int flag = 0;
	char cbuf[8192];

	gi(N);
	int life[100000];
	fn(N){
		gi(life[n]);
	}

	int *p[2];

	ret = EuclideanAlgorithm(N, life);
	ans(ret);

	wait();

	return 0;
}

Measured memory_bytes: 640
//
// Created by tac on 2016/10/12.
//

#include <cstdlib>
#include <iostream>

int main() {
    int h, w;
    while (true) {
        std::cin >> h >> w;
        if (h <= 0 && w <= 0) {
            break;
        }
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if ((i % 2 == 0 && j % 2 == 0) || (i % 2 ==1 && j %2 == 1)) {
                    std::cout << "#";
                } else {
                    std::cout << ".";
                }
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;
    }
    return EXIT_SUCCESS;
}

Measured memory_bytes: 3056
import sys
import math
input = sys.stdin.readline
a = [int(x) for x in input().split()]
N = min(a)
M = max(a)
if N + 1 < M:
    print(0)
    sys.exit()
if N != M:
    print(math.factorial(N) * math.factorial(M) % (7 + 10 ** 9))
else:
    print(2 * math.factorial(N) * math.factorial(M) % (7 + 10 ** 9))


Measured memory_bytes: 5184
#include <bits/stdc++.h>
const int mod=998244353;
#define Rint register int
#define C(n,m) (n<m?0:1ll*fac[n]*invfac[n-m]%mod*invfac[m]%mod)
using namespace std;
int T,n,m,p,k,dp[3][100010],sg[100010],ans=0,ksm_18[100010];
bool vis[1010];
struct edge{
	int to,link,w;
};
struct graph{
	int head[100010],o;
	edge e[2000010];
	void clear(){
		memset(head,0,sizeof(head));
		o=0;
	}
	void add_edge(int u,int v){
		e[++o].to=v,e[o].link=head[u],head[u]=o;
		e[++o].to=u,e[o].link=head[v],head[v]=o;
	}
}g[3];
int main(){
	scanf("%d",&n);
	ksm_18[0]=1,ksm_18[1]=(1000000000000000000ll)%mod;
	for(int i=2;i<=n;i++) ksm_18[i]=1ll*ksm_18[i-1]*ksm_18[1]%mod; 
	for(int t=0;t<3;t++){
		scanf("%d",&m);
		for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),g[t].add_edge(u,v);
		for(int u=n;u>=1;u--){
			sg[u]=0;
			for(int i=g[t].head[u];i;i=g[t].e[i].link) if(g[t].e[i].to>u) vis[sg[g[t].e[i].to]]=true;
			while(vis[sg[u]]) sg[u]++;
//			cout<<sg[u]<<" ";
			dp[t][sg[u]]=(dp[t][sg[u]]+ksm_18[u])%mod;
			for(int i=g[t].head[u];i;i=g[t].e[i].link) if(g[t].e[i].to>u) vis[sg[g[t].e[i].to]]=false;
		}
//		cout<<"\n";
	}
	for(int i=0;i<=1000;i++) for(int j=0;j<=1000;j++) ans=(ans+1ll*dp[0][i]*dp[1][j]%mod*dp[2][i^j])%mod;
	printf("%d\n",ans);
}


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

int main(){
    
    int N;cin>>N;
    vector<int> A(N);
    int cnt=0;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(A[i]%2) cnt++;
    }
    if(cnt%2) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}


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

int main() {
  string s;
  cin >> s;
  
  if (s == "Sunny"){
    cout << "Cloudy" << endl;
  }
  if (s == "Cloudy"){
    cout << "Rainy" << endl;
  }
  if (s == "Rainy"){
    cout << "Sunny" << endl;
  }
}



Measured memory_bytes: 3624
#include <utility>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#define ll long long
#define rep(i,rept) for (ll i = 0; i < rept; i++)
#define Yes(b) std::cout<< (b ? "Yes" : "No")<<std::endl
#define YES(b) std::cout<< (b ? "YES" : "NO")<<std::endl
using namespace std;

int main() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	cout << a[2] - a[0];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
vector<vector<P> > G;
Int getMin(const vector<Int> &A){
  Int res = INF;
  for(Int a:A) Min(res, a);
  return res;
}

Int calc(vector<Int> A,vector<Int> B){
  {
    Int num = -getMin(B) + 1;
    for(Int &a:A) a -= num;
    for(Int &b:B) b += num;
  }
  {
    Int num = -getMin(A) + 1;
    for(Int &a:A) a += num;
    for(Int &b:B) b -= num;
  }
  
  Int a = getMin(A);
  Int b = getMin(B);
  if(a <= 0 || b <= 0) return 0;
  return b;
}

Int solve(){
  Int n = G.size();
  vector<Int> A(n,INF), B(n,INF);
  vector<Int> used(n,0);
  Int flag = 1;
  function<void(Int,Int,Int)> dfs = [&](Int pos, Int col,Int s){
    if(used[pos] >> col & 1){
      flag &= (col == 0?A[pos]:B[pos]) == s;
      return;
    }

      
    used[pos] |= 1<<col;
    if(col == 0){
      if(A[pos] != INF) flag &= A[pos] == s;
      A[pos] = s;
    }
    if(col == 1){
      if(B[pos] != INF) flag &= B[pos] == s;
      B[pos] = s;
    };
    for(auto p:G[pos]) {
      dfs(p.first, !col, p.second - s);
	
    }
  };

  dfs(0, 0, 1);
  for(Int i=0;i<n;i++){
    if(A[i] == INF || B[i] == INF) continue;
    if((A[i] - B[i])%2) return 0;
  }
    
  if(flag == 0) return 0;
  Int res = calc(A, B);
  if(B[0] != INF) return min(1LL, res);
  return res;
}

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int n,m;
  cin>>n>>m;

  G.resize(n);
  for(Int i=0;i<m;i++){
    Int u, v, s;
    cin>>u>>v>>s; u--, v--;
    G[u].push_back(P(v, s));
    G[v].push_back(P(u, s));
  }
  
  Int ans = solve();
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 23040
#include <time.h>

#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <bitset>

using namespace std;
const int64_t INF=10000000000000000;

int main(){
	int64_t n;
	cin>>n;
	vector<int64_t> a;
	a.reserve(n);
	for(int64_t i1=0;i1<n;i1++){
		int64_t temp;
		cin>>temp;
		a.push_back(temp);
	}
	int64_t min_num=*min_element(a.begin(),a.end());
	int64_t max_num=*max_element(a.begin(),a.end());
	bool possible=false;
	if(min_num==max_num){
		if(min_num==n-1){
			possible=true;
		}else if(min_num<=n/2){
			possible=true;
		}
	}else if(max_num==min_num+1){
		size_t n_count=count(a.begin(),a.end(),min_num);
		if(n_count<min_num+1&&(min_num+1-n_count)<=(n-n_count)/2){
			possible=true;
		}
	}
	if(possible){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Edge{
	int u, v, next;
} edge[500050];

struct Point{
	int p, dis;
};

int n, m, cnt = 0;
int head[200050], vis[200050];

void addedge(int u, int v){
	edge[cnt].u = u;
	edge[cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

void bfs(){
	queue<Point> q;
	q.push({1, 0});
	vis[1] = 0;
	while (!q.empty()){
		Point p = q.front();
		q.pop();
		for (int i = head[p.p]; i != -1; i = edge[i].next){
			if (vis[edge[i].v] == -1){
				vis[edge[i].v] = p.p;
				q.push({edge[i].v, p.dis + 1});
			}
		}
	}
	return ;
}

int main(){
	scanf("%d %d", &n, &m);
	memset(head, -1, sizeof(head));
	memset(vis, -1, sizeof(vis));
	for (int i = 1; i <= m; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	bfs();
	bool flag = 1;
	for (int i = 1; i <= n; i++){
		if (vis[i] == -1){
			flag = 0; break;
		}
	}
	if (flag){
		puts("Yes");
		for (int i = 2; i <= n; i++){
			printf("%d\n", vis[i]);
		}
	}
	else{
		puts("No");
	}
	return 0;
}


Measured memory_bytes: 9748
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const ll INF=0x3fffffffffffffffll;

ll n;

inline ll min(ll a,ll b){return a<b?a:b;}

inline ll get_phi(ll x)
{
    ll res=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
        {
            res-=res/i;
            while(x%i==0)x/=i;
        }
    if(x>1)res-=res/x;
    return res;
}

ll qmi(ll k,ll mod)
{
    ll res=1,a=10;
    while(k)
    {
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res%mod;
}

int main()
{
    scanf("%lld",&n);
    if(n%2&&n%5)
    {
        if(n%7==0)n/=7;
        n*=9;
        ll phi=get_phi(n),res=INF;
        for(ll i=1;i<=phi/i;i++)
            if(phi%i==0)
            {
                if(qmi(i,n)==1)res=min(res,i);
                else if(qmi(phi/i,n)==1)res=min(res,phi/i);
            }
        printf("%lld\n",res);
    }
    else puts("-1");
    return 0;
}

Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	if (s == "abc" || s == "acb" || s == "bac" || s == "bca" || s == "cab" || s == "cba") {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 384
#define _GLIBCXX_DEBUG
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;



int main() {
  long long x, m = 100; cin >> x;
  int i;
  for(i = 0; m < x; i++){
    m += m/100;
  }
  cout << i << endl;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x>>y;
	cout<<(x+y/2)<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#define INF 2e9
#define rep(i,n,m) for(int i=n;i<m;i++)

using namespace std;

int main()
{
	int x, y;
	cin >> x >> y;
	
	if (y % 2 == 1)
	{
		cout << "No" << endl;
		return 0;
	}
	if (2 * x - y / 2 >= 0 && -x + y / 2 >= 0)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
//using namespace __gnu_pbds;
using namespace std;
typedef long long  L;

#define max_(x, y) (((x) > (y)) ? (x) : (y))
#define min_(x, y) (((x) < (y)) ? (x) : (y))
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Mx 200001
#define inf 1e15
const L MOD = 1e9+7;
const double pi = 2 * acos (0.0);

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/


//typedef tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

L a1,a2,a3,a,b,b1,b2,b3,c,c1,c2,c3,d,d1,d2,d3,d4,d5,e1,e2,e3,f,h,k,l,m,n,m1,m2,n1,n2,o,p,p1,p2,p3,p4,
q,q1,q2,q3,q4,r,s,t,u,v,x,y,z,sum,mx=-inf,mn=inf,flg,flg1,flg2,id1,id2,id3,id4,lim;

int main()
{
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    c1=c/b;
    if(c%b)c1++;
    c2=(a/d);
    if(a%d)c2++;
    if(c1<=c2){
        printf("Yes\n");
    }else printf("No\n");
    return 0;
}

/// empty() lld lld push_back() top() pop() insert() upper_bound() lower_bound() memset() max() min() scanf continue


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

typedef pair <int, int> ii;

struct pos {
    vector <int> seq;
    pos(int n = 0) {
        seq.resize(n + 1);
        for (int i = 1; i <= n; i++)
            seq[i] = i;
    }
};

pos Inverse(const pos &a)
{
    pos res(a.seq.size() - 1);
    for (int i = 1; i < a.seq.size(); i++)
        res.seq[a.seq[i]] = i;
    return res;
}

pos Multiply(const pos &a, const pos &b)
{
    pos c(b.seq.size() - 1);
    for (int i = 1; i < b.seq.size(); i++)
        c.seq[i] = a.seq[b.seq[i]];
    return c;
}

int main()
{
    int n, k; scanf("%d %d", &n, &k);
    pos p(n), q(n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &p.seq[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &q.seq[i]);
    pos res;
    if (k == 1) res = p;
    else if (k == 2) res = q;
    else if (k == 3) res = Multiply(q, Inverse(p));
    else {
        pos beg(n), mid(n);
        if (k % 3 == 2) {
            pos A = Multiply(q, Inverse(p));
            pos B = Multiply(Inverse(q), p);
            pos C = Multiply(A, B);
            int tims = (k - 2) / 6;
            while (tims) {
                if (tims & 1) beg = Multiply(beg, C);
                tims >>= 1; C = Multiply(C, C);
            }
            if (k % 6 == 5) beg = Multiply(beg, A);
        } else {
            pos A = Multiply(Inverse(p), Inverse(q));
            pos B = Multiply(p, q);
            pos C = Multiply(A, B);
            beg = q;
            int tims = (k - 4) / 6;
            while (tims) {
                if (tims & 1) beg = Multiply(beg, C);
                tims >>= 1; C = Multiply(C, C);
            }
            if (k % 6 == 3 || k % 6 == 1) beg = Multiply(beg, A);
        }
        if (k % 6 == 0)
            mid = Multiply(Multiply(Inverse(p), Inverse(q)), Multiply(p, p));
        else if (k % 6 == 1)
            mid = p;
        else if (k % 6 == 2)
            mid = q;
        else if (k % 6 == 3)
            mid = Multiply(Multiply(p, q), Multiply(Inverse(p), Inverse(p)));
        else if (k % 6 == 4)
            mid = Inverse(p);
        else if (k % 6 == 5)
            mid = Inverse(q);
        res = Multiply(Multiply(beg, mid), Inverse(beg));
    }
    for (int i = 1; i < res.seq.size(); i++)
        printf("%d%c", res.seq[i], i + 1 < res.seq.size()? ' ': '\n');
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define pub push_back
#define sec second
#define fir first

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	if(n < 1200)cout << "ABC" << endl;
	else if(n < 2800)cout << "ARC" << endl;
	else cout << "AGC" << endl;
	return 0;
}

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

using namespace std;

const int K = 26;

void count_char(int *a, string s) {
    for (int i = 0; i < K; i ++) {
        a[i] = 0;
    }
    for (int i = 0; i < s.size(); i ++) {
        a[s[i] - 'a'] ++;
    }
}

int main() {
    int n;
    string S[50];
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> S[i];
    }
    int count[K];
    for (int i = 0; i < K; i ++) {
        count[i] = 999999;
    }
    for (int i = 0; i < n; i ++) {
        int count2[K];
        count_char(count2, S[i]);
        for (int j = 0; j < K; j ++) {
            if (count2[j] < count[j]) {
                count[j] = count2[j];
            }
        }
    }
    for (int i = 0; i < K; i ++) {
        for (int j = 0; j < count[i]; j ++) {
            cout << (char)('a' + i);
        }
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define sz size()
#define SMX 2000000

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

//Combination MOD
const ll MOD = 1e9 + 7;
vector<ll> fac(SMX);
vector<ll> fac_inv(SMX);

ll mpow(ll x, ll n){
    if(n < 0)return 0;
    ll ans = 1;
    while(n != 0){
        if(n & 1)ans = ans * x % MOD;
        x = x * x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0 || b < 0)return 0;

    ll tmp = fac_inv[a - b] * fac_inv[b] % MOD;
    return tmp * fac[a] % MOD;
}

void preComb(){
    fac[0] = 1;
    fac_inv[0] = 1;
    for(ll i = 0; i < SMX; i++){
        fac[i + 1] = fac[i] * (i + 1) % MOD;
        fac_inv[i + 1] = fac_inv[i] * mpow(i + 1, MOD - 2) % MOD;
    }
}

int main(){
    ll x, y;
    cin >> x >> y;
    if((x + y) % 3 != 0){
        cout << 0 << endl;
        return 0;
    }

    int n= (x + y) / 3;
    x -= n;y -= n;
    preComb();
    ll res = comb(x + y, y) % MOD;
    if(res < 0)res += MOD;
    cout << res << endl;
}

Measured memory_bytes: 34260
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {
  static Scanner sc = new Scanner(System.in);
  public static void main(String[] args) {
    int n = sc.nextInt();
    int k = sc.nextInt();
    for(int i = 0; i < k; i++) {
      int x = sc.nextInt()-1;
      int y = sc.nextInt()-1;
      int z = n-x-1;
      int w = n-y-1;
      int m = min(min(x,y),min(z,w));
      System.out.println(m%3+1);
    }
  }
}

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

int main() {

    int a, b;
    scanf("%d%d", &a, &b);

    if (a > 9 || b > 9) {
        printf("-1");
    } else{
        printf("%d", a * b);
    }
    return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int M=1100000;
int dp[M][2],n;
string s;
int zhuan(char c) {
	return c-'0';
}
int main(){
	cin >> s;
	n = s.size() - 1;
	memset ( dp , 0x3f ,sizeof dp);
	dp[ 0 ][ 0 ] = 0;dp[ 0 ][ 1 ] = 1 ;
	for (int i = 0 ; i <= n ; i ++){
		int num = zhuan ( s[ i ] );
		dp[ i + 1 ][ 0 ] = min ( dp[ i ][ 0 ] + num , dp[ i ][ 1 ] + ( 10 - num ) ); 
		dp[ i + 1 ][ 1 ] = min ( dp[ i ][ 0 ] + num + 1, dp [ i ][ 1 ] + ( 10 - num - 1 ) ); 
	}
	int ans = dp [ n + 1 ][ 0 ];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12920
S=input()
slist=[]
for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        slist.append(S[i:j])
ma=0
for s in slist:
    flag = True
    for w in s:
        if w not in ['A','C','G','T']:
            flag = False
    if flag:
        ma = max(ma, len(s))
print(ma)

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

int main(){
  string S;
  int K;
  cin >> S >> K;
  int N=S.size();
  vector<int> sa(N);
  for(int i=0; i<N; i++){
    sa[i]=('z'-S[i]+1)%26;
  }
  for(int i=0; i<N; i++){
    if(sa[i]<=K){
      K-=sa[i];
      S[i]='a';
    }
  }
  S[N-1]=(S[N-1]-'a'+K)%26+'a';
  cout << S << endl;
  return 0;
}

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

int N,inf = 1e9;
int T[17][17];
int dp[1<<17];

int main(){
    while(true){
        cin >> N;
        if(N==0) break;
        for(int i=0;i<N;i++){
            for(int j=0;j<=N;j++){
                cin >> T[i][j];
            }
        }
        for(int S=0;S<(1<<N);S++){
            dp[S] = inf;
        }
        dp[0] = 0;
        for(int S=0;S<(1<<N)-1;S++){
            for(int i=0;i<N;i++){
                if(S&(1<<i)) continue;
                int c = T[i][0];
                for(int j=1;j<=N;j++) if(S&(1<<(j-1))) c = min(T[i][j],c);
                dp[S|(1<<i)] = min(dp[S|(1<<i)],dp[S]+c);
            }
        }
        cout << dp[(1<<N)-1] << endl;
    }
}


Measured memory_bytes: 3312
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(0);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  int N;
  cin >> N;
  vi V(N + 1), W(N + 1);
  rep(i, 0, N) cin >> V[i + 1] >> W[i + 1];

  int M = min(1LL << 9, N);
  vvi dp(M + 1, vi(100005));
  auto dfs = [&](auto &self, int v) -> void {
    if (v > M) return;
    if (v == 1) {
      rep(i, 0, 100005) {
        if (i >= W[v]) chmax(dp[v][i], V[v]);
      }
    } else {
      rep(i, 0, 100005) {
        chmax(dp[v][i], dp[v / 2][i]);
        if (i - W[v] >= 0) chmax(dp[v][i], dp[v / 2][i - W[v]] + V[v]);
      }
    }
    self(self, v * 2 + 0);
    self(self, v * 2 + 1);
  };
  dfs(dfs, 1);

  int Q;
  cin >> Q;
  rep(i, 0, Q) {
    int v, l;
    cin >> v >> l;
    int ans = 0;
    auto dfs2 = [&](auto &self, int v, int vs, int ws) -> void {
      if (v <= M) {
        if (l >= ws) chmax(ans, dp[v][l - ws] + vs);
      } else {
        self(self, v / 2, vs, ws);
        self(self, v / 2, vs + V[v], ws + W[v]);
      }
    };
    dfs2(dfs2, v, 0, 0);
    cout << ans << endl;
  }
  return (0 ^ _ ^ 0);
}



Measured memory_bytes: 410252
#include <cstdio>

#define swap(a,b) a^=b^=a^=b
int main(){
    int a=0,b=0,c=0,getin;
    for(int i=0;i<10;i++){
        scanf("%d",&getin);
        if(getin>c) c=getin;
        if(getin>b) swap(b,c);
        if(getin>a) swap(a,b);
    }
    printf("%d\n%d\n%d\n",a,b,c);
    return 0;
}

Measured memory_bytes: 1032
import math
 
# Input the amount of money Takahashi paid
N = int(input())
 
# Find nearest integer price more than or equal to X/1.08
X = math.ceil(N / 1.08)
 
# Check if the "taxed price" is equal to N yen
if math.floor(X * 1.08) == N:
	print(X)
else:
	print(":(")

Measured memory_bytes: 38632
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
typedef pair<int, int>P;
typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll MOD = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 5000100;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)
//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//組み合わせの余りを求める
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX_N; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll dp[101010];

//union-find木について
ll par[101010];
ll rank2[101010];

void init(ll n) {
	rep(i, n) {
		par[i] = i;
		rank2[i] = 0;
	}
}

ll find(ll x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

void unite(ll x, ll y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rank2[x] < rank2[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rank2[x] == rank2[y]) {
			rank2[x]++;
		}
	}
}

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

//long longしか使わない
//素数は1より大きい
int main() {
	ll n;
	cin >> n;
	vector<ll>a(n), b(n);
	rep(i, n) {
		cin >> a[i] >> b[i];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	if (n % 2 != 0) {
		ll res = b[n / 2] - a[n / 2] + 1;
		cout << res << endl;
	}
	else {
		ll res2 = ((b[n / 2] + b[n / 2 - 1]) - (a[n / 2] + a[n / 2 - 1])) + 1;
		cout << res2 << endl;
	}
	return 0;
}


Measured memory_bytes: 6304
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define per(i,n) for(int i=n-1;i>=0;++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)
#define per1(i,n) for(int i=n; i>=1; --i)
#define debug cout << "line : " << __LINE__ << " debug" << endl
#define Dcout(N) cout << setprecision(20) << N << endl
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF 1e8
#define MOD 1000000007
typedef long long ll;


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

    int k,a,b; cin >> k >>  a >> b;
    for(int i=a;i<=b;i++){
        if(i%k==0){
            cout << "OK" << endl;
            return 0;
        }
    }

    cout << "NG" << endl;


    return 0;
}


Measured memory_bytes: 3652
#include<iostream>

using namespace std;

int num;
int n,m;
int in;
long double per;
long double sum,sump,now;

int main(){

  cin >> num;
  for(int i = 0; i < num; i++){
    cin >> n >> m;
    sum = 0,sump = 0;
    for(int j = 0; j < m; j++){
      cin >> in >> per;
      sum += in * per; 
      sump += per;
    }
    now = max(now,sum/sump);
  }
  sum = sump = 0;
  cin >> n >> m;
  for(int i = 0; i < m; i++){
    cin >> in >> per;
    sum += in*per;
    sump += per;
  }
  if(now - sum/sump > 0.0000001) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 29;
 
int main() {
	string a, b;
	cin >> a >> b;
	int A = a.size(), B = b.size();
	if (A > B) {
		cout << "GREATER" << endl;
		return 0;
	}
	if (A < B) {
		cout << "LESS" << endl;
		return 0;
	}
	rep(i, A) {
		int A = int(a[i]), B = int(b[i]);
		if (A > B) {
			cout << "GREATER" << endl;
			return 0;
		}
		if (A < B) {
			cout << "LESS" << endl;
			return 0;
		}
	}
	cout << "EQUAL" << endl;
	return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> d(N);
    rep(i, N) cin >> d[i];

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

    int mid = N / 2;

    cout << (d[mid] - d[mid - 1]) << endl;

    return 0;
}

Measured memory_bytes: 640
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))

n,q=input_list()
s=input()
l=len(s)
left=[0 for _ in range(l)]
for i in range(1,l):
    left[i]=left[i-1]
    if s[i-1]+s[i]=="AC":
        left[i]+=1
total=left[-1]
right=[0 for _ in range(l)]
for i in range(1,l):
    ii=l-i-1
    right[ii]=right[ii+1]
    if s[ii]+s[ii+1]=="AC":
        right[ii]+=1

for _ in range(q):
    l,r=input_list()
    ri=right[r-1]
    le=left[l-1]
    print(total-le-ri)




Measured memory_bytes: 17996
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+10;
const double inf=1e9;
typedef long long ll;
typedef pair<int,int>pr;
const ll mod=1e9+7;
ll _pow(ll  a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1)
            ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){
    if(!b) return a;
    else return gcd(b,a%b);
}
int a[maxn];
int main(){
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ll n;
  cin>>n;
  cout<<(n-2)*(n-1)/2+n-1<<endl;
  return 0;
}


Measured memory_bytes: 256
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n = input().strip()
print('Yes' if '7' in n else 'No')
#print('No')
#print()


Measured memory_bytes: 9056
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    a, b, c = map(int, input().split())

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


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 2940
import sys

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


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


def main():
    N, M = map(int, readline().split())
    AB = [[int(s) - 1 for s in line.split()] for line in readlines()]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, (a, b) in enumerate(AB):
            if i == j:
                continue
            uf.union(a, b)
        if uf.group_count() > 1:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 40944
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> G(N, vector<int>());
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    ll res = 0;
    ll over = 0;
    for(int i = N - 1; i >= 0; i--) {
        over += N - i;
        int cnt = 0;
        for(auto nv : G[i]) {
            if(nv > i) {
                over -= N - nv;
            }
        }
        res += over;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 15004
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			String[] array = br.readLine().split(" ");
			int N = Integer.parseInt(array[0]);
			int C = Integer.parseInt(array[1]);

			int[] channels = new int[N];
			int[] starts = new int[N];
			int[] ends = new int[N];
			for (int i = 0; i < N; i++) {
				String[] tmp = br.readLine().split(" ");

				starts[i] = Integer.parseInt(tmp[0]);
				ends[i] = Integer.parseInt(tmp[1]);
				channels[i] = Integer.parseInt(tmp[2]);
			}
			final int[] table = new int[2 * 100_001];
			final boolean[] tmp = new boolean[2 * 100_001];
			boolean updated = false;
			for (int channel = 1; channel <= C; channel++) {
				if (updated) {
					for (int i = 0; i < tmp.length; i++) {
						tmp[i] = false;
					}
					updated = false;
				}

				for (int index = 0; index < N; index++) {
					if (channels[index] == channel) {
						for (int i = starts[index] * 2 - 1; i <= ends[index] * 2; i++) {
							tmp[i] = true;
						}
						updated = true;
					}
				}

				for (int i = 0; i < table.length; i++) {
					if (tmp[i]) {
						table[i]++;
					}
				}
			}

			System.out.println(Arrays.stream(table).max().getAsInt());
		}
	}
}


Measured memory_bytes: 48288
def GCD(a, b):
    if(a % b == 0):
        return(b)
    return(GCD(b, a % b))

N = int(input())
ret = 0
if(N < 2):
    ret = GCD(2, N)
else:
    ret = GCD(N, 2)
print(2 * N // ret)

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

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

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/12  Problem: ABC 081 D / Link: http://abc081.contest.atcoder.jp/tasks/abc081_d  ----- */


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

	LL N;
	cin >> N;
	vector<LL> a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
	}
	vector<PLL> ans;
	int mxidx = max_element(ALL(a)) - a.begin();
	int mnidx = min_element(ALL(a)) - a.begin();
	if (abs(a[mxidx]) >= abs(a[mnidx])) {
		FOR(i, 0, N) {
			if (i == mxidx)continue;
			ans.push_back(PLL(mxidx, i));
		}
		FOR(i, 0, N - 1) {
			ans.push_back(PLL(i, i + 1));
		}
	}
	else {
		FOR(i, 0, N) {
			if (i == mnidx)continue;
			ans.push_back(PLL(mnidx, i));
		}
		FORR(i, N - 1, 0) {
			ans.push_back(PLL(i, i - 1));
		}
	}



	cout << SZ(ans) << endl;
	for (auto it : ans) {
		cout << it.first+1 << " " << it.second+1 << endl;
	}

	return 0;
}


Measured memory_bytes: 256
r,c=map(int,input().split())
m=[[int(_) for _ in input().split()] for i in range(r)]
for i in range(r):m[i].append(sum(m[i]))
m.append([sum([m[i][j] for i in range(r)]) for j in range(c+1)])
[print(*m[i]) for i in range(r+1)]

Measured memory_bytes: 6248
def mov(xy,N):
    Box_red = set([1])
    Box = [1 for _ in range(N)]

    for i in range(len(xy)):
        Box[xy[i][0]-1] -= 1
        Box[xy[i][1]-1] += 1
        if xy[i][0] in Box_red:
            Box_red.add(xy[i][1])
        if Box[xy[i][0]-1] == 0:
            Box_red.discard(xy[i][0])

    return len(Box_red)

def main():
    N,M = map(int,input().split())
    xy = [list(map(int,input().split())) for _ in range(M)]
    ans = mov(xy,N)
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 36956
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int n, m, x;
int c[15];
int a[15][15];

int dfs(int v, int cost, vint &skill) {
    if (v == n) {
        bool ok = true;
        rep(i,skill.size()) {
            if (skill[i] < x) ok = false;
        }
        if (ok) return cost;
        else return inf;
    }
    int res_pos, res_neg;
    res_neg = dfs(v+1,cost,skill);
    vint skill_add = skill;
    rep(i,skill.size()) skill_add[i] += a[v][i];
    res_pos = dfs(v+1,cost+c[v],skill_add);
    return min(res_neg,res_pos);
}

int main() {
    cin >> n >> m >> x;
    rep(i,n) {
        cin >> c[i];
        rep(j,m) cin >> a[i][j];
    }
    vint skill(m,0);
    if (dfs(0,0,skill) == inf) cout << -1 << endl;
    else cout << dfs(0,0,skill) << endl;
}

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

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        # set_val
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        # built
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])
 
    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])
 
    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res
 

seg=SegTree([0]*300001,0,max)

n,k=map(int,input().split())
a=[int(input()) for i in range(n)]

for i in a:
    l=max(0,i-k)
    r=min(300000,i+k)

    pin=seg.query(l,r+1)+1
    seg.update(i,pin)


print(seg.query(0,300001))


Measured memory_bytes: 127588
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200003],fsum[200003],bsum[200003],ans=-2e18,sum,su;
signed main()
{
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)
		scanf("%lld",&a[i]);
	fsum[1]=a[1],fsum[2]=a[2],bsum[n]=a[n],bsum[n-1]=a[n-1];
	for(int i=3; i<=n; i++)
		fsum[i]=fsum[i-2]+a[i];
	for(int i=n-2; i>=1; i--)
		bsum[i]=bsum[i+2]+a[i];
	sum=fsum[n];
	if(n%2==0)
	{
		ans=max(fsum[n-1],fsum[n]);
		for(int i=1; i<=n; i+=2)
			ans=max(ans,fsum[i]+bsum[i+3]);
		cout<<ans;
		return 0;
	}
	for(int i=1; i<=n; i++)
		if(i%2==0)
			su+=a[i];
		else
			su=max(su-a[i],-a[i]),ans=max(ans,sum+su);
	cout<<ans;
	return 0;
}


Measured memory_bytes: 8404
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;

int dis[210],ary[110];
int main(){
	int N;
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>ary[i];
	}
	for(int i=0;i<=200;i++){
		dis[i]=i*i;
	}
	int res=INF,sum=0;
	for(int i=-100;i<=100;i++){
		sum=0;
		for(int j=1;j<=N;j++){
			sum+=dis[abs(i-ary[j])];
		}
		res=min(res,sum);
	}

	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef		long long       ll;
typedef         long double      dl;
#define		pb              push_back
#define		PB              pop_back
#define		nn              "\n"
#define     O_O             ios_base::sync_with_stdio(false); cin.tie(NULL)
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define		ss              ' '
#define         arrsize(a)      (sizeof(a)/sizeof(a[0]))
//#define       arrsize(a)      (sizeof(a)/sizeof(*a))
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
#define		pi              acos(-1.0)
typedef        pair <int, int>   pii;
typedef       pair <ll, ll>      pll;
typedef      vector< pair <ll, ll> >      vpll;
typedef		vector<ll>      vll;
typedef		map<string,ll>      msl;
typedef		map<ll,ll>      mll;
#define MAX 1000005


int main()
{
 //O_O ;
  ll a,b,n;
  cin>>a>>b>>n;
ll ans=min(n,a);
n-=ans;
a-=ans;
ans=min(n,b);
b-=ans;
cout<<a<<" "<<b;
    return 0;
}


Measured memory_bytes: 256