akhauriyash/Code-Regression huggingface dataset:
N,M = map(int,input().split())
p = [int(i) for i in input().split()]
xy = []

for _ in range(M):
    xy.append(list(map(int,input().split())))

par = [0 for _ in range(N+1)]
rank = [0 for _ in range(N+1)]

def init(n):
    for i in range(n):
        par[i] = i
        rank[i] = 0
def find(x):
    if par[x] ==x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def same(x,y):
    return True if find(x) == find(y) else False

init(N+1)
for x,y in xy:
    unite(x,y)
count = 0
for i in p:
    if same(i,p[i-1]):
        count += 1
print(count)

Measured memory_bytes: 36092
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = []

    for _ in range(n):
        A.append(input_int())
    for a in A:
        if a % 2 == 1:
            print("first")
            return

    print("second")

    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 76904
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int counter[200006];
int main(){
	int i;
	int n, k;
	int tmp, tmp2;
	int types=0;
	int ans=0;
	
	scanf("%d %d", &n, &k);
	memset(counter, 127, sizeof(counter));
	for(i=1; i<=n; i++){
		scanf("%d", &tmp);
		if(counter[tmp]>=10000000)
			counter[tmp]=0;
		types+=!counter[tmp];
		counter[tmp]++;
	}
	
	sort(counter+1, counter+1+n);
	
	for(i=1; i<=types-k; i++)
		ans+=counter[i];
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 896
import java.util.Scanner;

//Sleeping Time
public class Main{

	int K, R, L;
	double P, E, T;
	double ans = 0;
	double EPS = 1e-12;
	
	void dfs(double l, double r, double p, int k){
		if(l+EPS>T+E||r<T-E+EPS)return;
		if(T-E<l+EPS&&r<T+E+EPS){
			ans += p;
			return;
		}
		double h = (l+r)/2;
		if(k==K){
			if(T-E<h+EPS&&h<T+E+EPS)ans+=p;
			return;
		}
		if(h+EPS>T){
			dfs(l, h, p*(1-P), k+1);
			dfs(h, r, p*P, k+1);
		}
		else{
			dfs(h, r, p*(1-P), k+1);
			dfs(l, h, p*P, k+1);
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		K = sc.nextInt();
		R = sc.nextInt();
		L = sc.nextInt();
		P = sc.nextDouble();
		E = sc.nextDouble();
		T = sc.nextDouble();
		dfs(R, L, 1.0, 0);
		System.out.printf("%.7f\n", ans);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

int main(){
  int n;
  cin>>n;
  int a[2][n];
  vector<int> vec1(n+1,0),vec2(n+1,0);
  for(int i=0;i<2;++i){
    for(int j=0;j<n;++j){
      cin >> a[i][j];
      if(i==0){
        vec1[j+1]=vec1[j]+a[i][j];
      }else{
        vec2[j+1]=vec2[j]+a[i][j];
      }
    }
  }
  vector<int> ans(n);
  int b,c;
  int d,e;
  b=0;
  e=n;
  int cal=0;
  for(int i=0;i<n;++i){
    c=i+1;
    d=i;
    ans[i]=(vec1[c]-vec1[b])+(vec2[e]-vec2[d]);
    cal=max(cal,ans[i]);
  }
  cout << cal << endl;

}


Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL N;
LL u[200000],v[200000];

LL ans = 0;

void solve(){
	LL numof_point = ((N*(2*N+1)*(N+1))/6LL + N*(N+1)/2LL)/2LL;
	LL numof_edge = 0;
	for(int i=0;i<N-1;i++){
		numof_edge += min(u[i],v[i])*(N-max(u[i],v[i])+1LL);
	}
	ans = numof_point - numof_edge;
}

int main(){
    cin >> N;
    for(int i=0;i<N-1;i++) cin >> u[i] >> v[i];

    solve();

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

Measured memory_bytes: 6316
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner jk = new Scanner(System.in);
		int n = jk.nextInt();
		int[] arr = new int[n];
		for (int i=0; i<n; i++)
		{
			arr[i] = jk.nextInt();
		}
		Arrays.sort(arr);
		double ans = (arr[0]+arr[1])/2.0;
		for (int i=2; i<n; i++)
		{
			ans = (ans+arr[i])/2.0;
		}
		System.out.println(ans);
		
	}

}


Measured memory_bytes: 21716
#include <stdio.h>

void main()
{
  int n, i, a, b, hypo;

  for (scanf("%d", &n); n > 0; n--) {
    scanf("%d %d %d", &a, &b, &hypo);

    if (a > hypo) {
      i = hypo; hypo = a; a = i;
    } 
    if (b > hypo) {
      i = hypo; hypo = b; b = i;
    }

    if (a*a + b*b == hypo*hypo) {
      printf("YES\n");
    } else {
      printf("NO\n");
    }
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define substr(s,f,t) (s.substr(f-1,t-f+1))
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;cin>>n;
  string s1,s2,s3;
  cin>>s1>>s2>>s3;
  int ans=0;
  int a12=0,a23=0,a31=0;
  for(int i=0;i<n;i++){
    if(s1[i]==s2[i]&&s2[i]==s3[i]){
    }else if(s1[i]==s2[i]){
      ans++;
    }else if(s2[i]==s3[i]){
      ans++;
    }else if(s3[i]==s1[i]){
      ans++;
    }else{
      ans+=2;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use nalgebra::{min, max};

#[fastout]
fn main() {
    input! {
    x: usize,
    y: usize
    }
    let ans = x + y / 2;
    println!("{}", ans);
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  double a,b;
  cin>>a>>b;
  double c = 1.0/(1.0/a + 1.0/b);
  printf("%.12lf\n",c);
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[100010];
int main(){
    int n, r;
    while(cin>>n>>r){
    	int ans=0;
    	if(n>=10){
    		ans=r;
    	}
    	else{
    		ans=r+100*(10-n);
    	}
    	cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 256
N, W = map(int, input().split())
v = [0 for i in range(N)]
w = [0 for i in range(N)]
for i in range(N):
    v[i], w[i] = map(int, input().split())

vaw = [0 for i in range(W+1)]
for i in range(len(v)):
    for k in range(len(vaw)):
        j = len(vaw) - k - 1
        if vaw[j] != 0 and j+w[i]<=W:
            vaw[j+w[i]] = max(vaw[j+w[i]], vaw[j]+v[i])

    vaw[w[i]] = max(vaw[w[i]], v[i])

print(max(vaw))


Measured memory_bytes: 5928
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			int a = s.nextInt();
			int b = s.nextInt();
			int g = gcd(a, b);
			int l = lcm(a, b, g);
			System.out.println(g + " " + l);
		}
	}
	static int gcd(int a, int b) {
		int x = Math.max(a, b);
		int y = Math.min(a, b);
		int temp;
		while (y != 0) {
			temp = x % y;
			x = y;
			y = temp;
		}
		return x;
	}
	static int lcm(int a, int b, int g) {
		return a / g * b;
	}
}



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

#define LIVE (0)
#define DEAD (1)

int md[1000];

int fizzbuzz(int n)
{
	if (n % 15 == 0){
		return (-3);
	}
	if (n % 3 == 0){
		return (-1);
	}
	if (n % 5 == 0){
		return (-2);
	}
	return (n);
}

void inc_no(int *no, int m)
{
	do {
		(*no)++;
		if (*no >= m){
			*no = 0;
		}
	} while (md[*no] == DEAD);
}

int main(void)
{
	int n, m;
	int nd;
	char data[20];
	int i;
	int no;
    int remain;
    int out_flag;
	
	while (1){
		scanf("%d%d", &m, &n);
		if (n == 0 && m == 0){
			break;
		}
		for (i = 0; i < 1000; i++){
			md[i] = LIVE;
		}

		no = 0;
        remain = m;
		for (i = 1; i <= n; i++){
			scanf("%s", data);
			if (strcmp(data, "Fizz") == 0){
				nd = -1;
			}
			else if (strcmp(data, "Buzz") == 0){
				nd = -2;
			}
			else if (strcmp(data, "FizzBuzz") == 0){
				nd = -3;
			}
			else {
				nd = atoi(data);
			}
			if (nd != fizzbuzz(i)){
				md[no] = DEAD;
                if (--remain == 1){
              		for (i++; i <= n; i++){
			            scanf("%s", data);
            		}
                    break;
                }
			}
			inc_no(&no, m);
		}
        out_flag = 0;
		for (i = 0; i < m; i++){
			if (md[i] == LIVE){
                if (out_flag == 1){
                    printf(" ");
                }
				printf("%d", i + 1);
                out_flag = 1;
			}
		}
		printf("\n");
	}

	return (0);
}

Measured memory_bytes: 612
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int main(){
  string s;
  cin >> s;
  cout << s.substr(0, 4) + " " + s.substr(4, 8) << endl;
}


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

#define ll          long long
#define mp	    make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;


void solve(){
	int n, tem;
	cin>>n;
	set<int>s;
	int size = 0;
	s.insert(n);
	while(s.size() != size){
		if(n % 2)
		tem = 3 * n + 1;
		else
		tem = n / 2;
		size = s.size();
		s.insert(tem);
		n = tem;
	}
	cout << s.size() + 1 << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
     t =1;
//     cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sct(tc) scanf("%lld",&tc)
#define scl(n) scanf("%lld",&n)
#define scll(n,m) scanf("%lld%lld",&n,&m)
#define scs(ch) scanf("%s", ch)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
int main()
{
	ll k,r;
	scanf("%lld",&k);
	r=k%10;
	if(r==2||r==4||r==5||r==7||r==9)
	cout << "hon"<<"\n";
	else if(r==0||r==1||r==6||r==8)
	cout <<"pon" <<"\n";
	else
	cout <<"bon"<<"\n";
}

Measured memory_bytes: 3808
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,n2,k;
	int l[50];
	cin>>n>>k;
	n2=n;
	for(int i=0;i<n;i++)cin>>l[i];
	sort(l,l+n);
	int sum=0;
	for(int j=n-1;j>=0&&k>0;j--){
		sum+=l[j];
		k--;
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void fu(int x,int y,char f);
char ma[105][105];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int w,h;
int main(void){
  int ans;
  while(1){
    scanf("%d %d",&w,&h);
    if(w==0 && h==0) break;
    ans=0;
    for(int i=0;i<w;i++) scanf("%s",ma[i]);

    for(int i=0;i<w;i++){
      for(int j=0;j<h;j++){
	if(ma[i][j]!='!'){
	  fu(i,j,ma[i][j]);
	  ans++;
	}
      }
    }
    printf("%d\n",ans);
  }
}

void fu(int x,int y,char f){
  ma[x][y]='!';
  for(int i=0;i<4;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(0<=nx && nx<w && 0<=ny && ny<h){
      if(ma[nx][ny]==f) fu(nx,ny,f);
    }
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define make_unique(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define Sort(vec) sort(vec.begin(),vec.end())
#define RSort(vec) sort(vec.rbegin(),vec.rend())
#define endl "\n"
#define tr1(i) cout<<i<<endl;
#define tr2(i,j) cout<<i<<" "<<j<<endl;
#define tr3(i,j,k) cout<<i<<" "<<j<<" "<<k<<endl;
#define vvi vector<vector<int> > 
#define vvl vector<vector<ll> >
#define all(st) st.begin(),st.end()
#define vpl vector<pair<ll,ll> >
#define vpi vector<pair<int,int> >
#define pi pair<int,int>
#define pl pair<ll,ll>
#define al vector<list<int> >
#define vs vector<string>
#define vb vector<bool>
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define repit(st) for(auto it=st.begin();it!=st.end();it++)
#define cs(ans); cout<<setprecision(20)<<fixed<<ans<<endl;
#define ull unsigned long long int
#define eb emplace_back
#define pb push_back
#define ll long long int
#define minf -(1e18)
#define inf 1e18
#define f first
#define se second
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds; 
ll mi(ll n,ll m){ll pw=n%m;ll ex=m-2;ll ans=1;while(ex){if(ex&1) ans = ans*pw%m;pw = pw*pw%m;ex>>=1;}return ans%mod;}
ll pw(ll a,ll n){ll pw=a;ll ex=n;ll ans=1;while(ex){if(ex&1) ans = ans*pw;pw = pw*pw;ex>>=1;}return ans;}
ll pwm(ll a,ll n){ll pw=a%mod;ll ex=n;ll ans=1;while(ex){if(ex&1) ans = ans*pw%mod;pw = pw*pw%mod;ex>>=1;}return ans%mod;}
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }
template<typename T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//st.order_of_key(num)->number of elements < num
//st.find_by_order(i)->iterator of ith element in sorted order starting from zero
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll Abs(ll x){return x>0?x:(-x);}
ll Ceil(ll a,ll b){return a/b+(a%b!=0);}
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define mkp make_pair
//#define int long long int
//Binary_Search->dp->greedy
//auto check = [&](ll x){};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int X[]={2,1,-1,-2,-2,-1,1,2}; 
int Y[]={1,2,2,1,-1,-2,-2,-1}; 
struct comp{
	bool operator()(const pair<int,int>&a,const pair<int,int>&b) const {
		if(a.first>b.first) return true;
		if(a.first<b.first) return false; 
		if(a.second<b.second) return true;
		return false;
	}
};	
void solve(){
	
	int s,w;
	cin>>s>>w;
	if(s<=w) cout<<"unsafe"<<endl;
	else cout<<"safe"<<endl;
	
		
}
int32_t main(){
int t=1;
//scanf("%d",&t);
while(t--){
	solve();
}
return 0;
}    


Measured memory_bytes: 3596
package main

import "fmt"

func main() {
	var n, m int

	fmt.Scan(&n)
	blue := make([]string, n)
	for i := range blue {
		fmt.Scan(&blue[i])
	}

	fmt.Scan(&m)
	red := make([]string, m)
	for i := range red {
		fmt.Scan(&red[i])
	}

	ans := 0
	for i := 0; i < n; i++ {
		count := 0
		for j := 0; j < n; j++ {
			if blue[i] == blue[j] {
				count++
			}
		}
		for j := 0; j < m; j++ {
			if blue[i] == red[j] {
				count--
			}
		}
		ans = max(ans, count)
	}

	fmt.Println(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
using namespace std;
using MIte = multimap<vector<long>, int>::iterator;

int main() {
	long P, Q, R;
	cin >> P >> Q >> R;

	long a = P + Q + R - max({ P, Q, R });


	cout << a << endl;


	return 0;
}

Measured memory_bytes: 256
def main():
    n,k = map(int,input().split())
    hts = list(map(int,input().split()))
    
    dp = [float('inf')]*n
    dp[0] = 0
    dp[1] = abs(hts[1]-hts[0])

    for i in range(2,min(k,n)):
        ans = dp[i]
        for j in range(i,0,-1):
            ans = min(ans,dp[i-j]+abs(hts[i]-hts[i-j]))

        dp[i] = ans

    for i in range(k,n):
        ans = dp[i]
        for j in range(k,0,-1):
            ans = min(ans,dp[i-j]+abs(hts[i]-hts[i-j]))

        dp[i] = ans

    #print(dp)

    print(dp[-1])

main()


Measured memory_bytes: 54112
import sys,math
input = sys.stdin.buffer.readline

mod = 1000000007
n = int(input())

ab = []
ang = dict()
rev = dict()
dg = 10**20
zero = 0

for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        if 1 in ang:
            ang[1] += 1
        else:
            ang[1] = 1
    elif b == 0:
        if 1 in rev:
            rev[1] += 1
        else:
            rev[1] = 1
    elif a*b > 0:
        if a < 0 and b < 0:
            a,b = -a,-b
        g = math.gcd(a,b)
        a,b = a//g,b//g

        if a*dg + b in ang:
            ang[a*dg + b] += 1
        else:
            ang[a*dg + b] = 1
    else:
        a,b = abs(a),abs(b)
        g = math.gcd(a,b)
        a,b = a//g,b//g

        if b*dg + a in rev:
            rev[b*dg + a] += 1
        else:
            rev[b*dg + a] = 1

rest = n - zero

res = 1

for e in ang:
    if e in rev:
        res = res*(pow(2,ang[e],mod) + pow(2,rev[e],mod) - 1)%mod
        rest -= ang[e] + rev[e]

res = res*pow(2,rest,mod)%mod - 1 + zero

print(res%mod)


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<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 Size(n) (n).size()

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//long long int kaizyo(long long int hh){
  //  cmp=1;
    //while(hh>1){
      //  cmp=(cmp*hh)%MOD;
        //hh--;
    //}
    //return cmp;
//}

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

//visited=vector<vector<bool>>(10,vector<bool>(10,false));アを全部falseに


long long int n,cnt=0,ans=0,a,b,c,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;

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

       cin >>n>>m;
       if(n>=m/2){
           Cout(m/2);
       }
       else{
       ans+=n;
       Cout(ans+(m-2*n)/4);
       }
       
return 0;
}


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

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> q;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<llint> make_divisors(llint x){
	vector<llint> div;
	for(llint i=1;i*i<=x;i++){
		if(x%i==0){
			div.push_back(i);
			if(x/i!=i)div.push_back(x/i);
		}
	}
	return div;
}

void solve(){
	llint n;
	cin >> n;
	llint ans=0;
	for(int i=1;i<=n;i+=2){
		vector<llint>div=make_divisors(i);
		if(div.size()==8)ans++;
	}
	cout << ans << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
cities=[list(map(int,input().split()))+[i] for i in range(m)]
i=0
pre_pref=0

res=['' for _ in range(m)]
for idx,city in enumerate(sorted(cities)):
    if pre_pref!=city[0]:
        i=0
        pre_pref=city[0]
    i+=1
    res[city[2]]='{:06}{:06}'.format(city[0],i)
print('\n'.join(res))

Measured memory_bytes: 34304
#include<stdio.h>
int main(){
  int a,b,k,n;
  while(scanf("%d %d",&a,&b)!=EOF){
    a=a+b;
    for(k=1,n=1;k<=1000000;k=k*10,n++){
      if(a/k>0 && a/k<10){
	printf("%d\n",n);
      }
    }
  }
  return (0);
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;


void divisor(vector<ll>& ret, ll n) {
  for(ll i = 1;i < ll(sqrt(n)+1); i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
}

void factorize(map<ll,ll>& fac, ll a){
    for(ll i = 2;i < ll(sqrt(a)+1);i++){
        while(a % i == 0){
            a /= i;
            fac[i]++;
        }
    }
    if(a > 1)fac[a]++;
}

int main(){
    vector<ll> ret;
    ll N;cin>>N;
    divisor(ret, N);
    set<ll> ans;
    
    for(int i = 1;i < ret.size();i++){
        ll d = ret[i];
        ll l = N;
        while(l % d == 0)l /= d;
        if((l - 1) % d == 0)ans.insert(d);
    }
    vector<ll> ret2;
    divisor(ret2, N-1);
    // cout<<ret2.size()<<endl;
    for(int i = 1;i < ret2.size();i++){

        ans.insert(ret2[i]);
    }
    cout<<ans.size()<<endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define fine cout<<"fine"<<endl;
#define ll long long int
#define pb push_back
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
const ll inf=(ll)2e18;
const int mod=1e9+7;
bool overflow(ll a,ll b){
    if (a <= (inf+b-1)/b) return false;
    return true;
}
int main(){
FASTIO;
int h,n;
cin>>h>>n;
int x,i,sum=0;
for(i=0;i<n;i++){
    cin>>x;
    sum+=x;
}
if(sum>=h)
    cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    ll H,W,K;
    cin >> H >> W >> K;
    vector<string> C(H);
    REP(i,H)cin >> C[i];
    ll ans = 0;
    REP(i,1LL << H){
        vector<bool> whe(H);
        ll be = i;
        REP(l,H){
            if(be %2 == 1)whe[l] = 1;
            be/=2;
        }
        REP(l,1LL << W){
            vector<bool> whi(W);
            ll ba = l;
            REP(a,W){
                if(ba %2 == 1)whi[a] = 1;
                ba/=2;
            }
            ll count = 0;
            REP(a,H){
                REP(b,W){
                    if(whe[a]||whi[b])continue;
                    if(C[a][b] == '#')count++;
                    if(count > K)break;
                }
            }
            if(count == K)ans++;
        }
    }
    cout << ans << "\n";
}

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

int main()
{
  char s[100000]={};
  
  scanf("%s",s);
  
  int i;
  char j='a';
  char ans='a';
  int l=strlen(s);

  for(j='a';j<='z';j++)
  {
    for(i=0;i<l;i++)
    {
      if(s[i]==j)
      {
        ans=j+1;
        break;
      }
    }
    if(ans==j)
    {
    printf("%c\n",ans);
    return 0;
    }
  }
        
  
  if('z'<ans)
  {
    printf("None\n");
  }
  return 0;
  
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

    string s;cin>>s;
    for(int i=0;i<(int)s.length()-1;i++){
        if(s[i]=='A'&&s[i+1]=='C'){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}


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

using namespace std;
using ll = long long;

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

const int mod = 1000000007;

ll modpow(ll x, ll n) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    return modpow((x % mod) * (x % mod), n / 2);
  } else {
    return (x % mod) * (modpow((x % mod) * (x % mod), n / 2) % mod);
  }
}

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

  vector<ll> d(k + 1);

  for (int i = 1; i <= k; ++i) d[i] = modpow(k / i, n);

  for (int i = k; i >= 1; --i) {
    for (int j = 2 * i; j <= k; j += i) {
      d[i] -= d[j];
      d[i] = (d[i] + mod) % mod;
    }
  }

  ll ans = 0;
  for (int i = 1; i <= k; ++i) {
    ans += i * d[i];
    ans %= mod;
  }

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3988
#include<bits/stdc++.h>
using namespace std;
int a[100005];
char ch[20];
map<string, int>m;
map<string, int>::iterator it;
int main(void)
{
	int o;
	long long sum = 0;
	cin >> o;
	for (int i = 0; i < o; i++)
	{

		cin >> ch;

		sort(ch, ch + 10);

		ch[10] = '\0';

		if (!m.count(ch))

		{

			m[ch] = 0;

		}

		m[ch] += 1;

	}

	for (it = m.begin(); it != m.end(); it++)

	{

		int k = it->second;

		for (int i = 0; i < k; i++)

		{

			sum += i;

		}

	}

	cout << sum << endl;

	return 0;

}

Measured memory_bytes: 11136
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;

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 (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const int INF = 0x3fffffff;


int cost[305][605][305];
int dp[305][305];

int main(){
	int H, W;
	char c[305][305];

	cin >> H >> W;
	rep(i,H) rep(j,W) cin >> c[i][j];

	Fill( cost, 0 );
	rep(i,W-1) rep(j,2*H+1) rep(k,H){
		int d = j - H;
		if( 0 <= k+d && k+d < H ){
			cost[i][j][k+1] = cost[i][j][k] + (c[k+d][i] == c[k][i+1]);
		}else{
			cost[i][j][k+1] = cost[i][j][k];
		}
		//cout << "cost\t" << i << " " << j << " " << k+1 << "\t" << cost[i][j][k+1] << endl;
	}

	ll ans = 0;
	rep(i,W-1){
		Fill( dp, INF );
		dp[0][0] = 0;
		rep(j,H+1) rep(k,H+1){
			int dd = H-j+k;
			int cs = cost[i][dd][H-k] - cost[i][dd][0];
			//cout << j << " " << k << " " << cs << "\t" << dp[j][k] << endl;
			chmin( dp[j][k+1], dp[j][k] + cs );
			chmin( dp[j+1][k], dp[j][k] + cs );
		}
		//cout << "dp i=" << i << "\t" << dp[H][H] << endl;
		ans += dp[H][H];
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 220544
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


int main() {
  string ns;
  cin >> ns;
  int n = ns.size();

  ns += '0';
  vi v;
  rep(i, n) v.push_back(ns[i] - '0');
  reverse(v.begin(), v.end());

  int dp[n+2][2];
  dp[0][0] = 0; dp[0][1] = 11;
  rep(i, n+1){
    dp[i+1][0] = min(dp[i][0] + v[i], dp[i][1] + v[i] + 1);
    dp[i+1][1] = min(dp[i][0] + (10 - v[i]), dp[i][1] + (10 - v[i] - 1));
  }
  cout << dp[n+1][0] << endl;
  return 0;
}

Measured memory_bytes: 13560
#include <bits/stdc++.h>//toINFandByd
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define endl "\n"
using namespace std;
typedef long long ll;

void solve(){
    string s,t;
    cin >> s >> t;
    int ans = 0;
    int n = s.length();
    forn(i,n){
        if(s[i]!=t[i]){
            ans++;
        }
    }
    cout << ans << endl;
}   

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
    //     freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 3792
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<iostream>
#include<bitset>
#include<climits>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int s,e;
        cin>>s>>e;
        int cnt=0;
        while(s<e){
            int to=1;
            while(true){
                int next=to*2;
                if(s%next)break;
                if(s+next>e)break;
                to=next;
            }
            s+=to;
            cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
fun main(arr:Array<String>) {
    val (length, ryokinCount, pos) = readLine()!!.split(" ").map { it.toInt() }
    val ryokinList = readLine()!!.split(" ").map { it.toInt() }
    val ans = Math.min(ryokinList.count { it < pos }, ryokinList.count { it > pos })
    println(ans)
}


Measured memory_bytes: 37860
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MAX_N (1 << 17)


void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{
    ll aa;
    ll bb;
}frequent;

int main(void){
    char s[500005];
    ll n,ans=0;
    scanf("%s",s);
    n=strlen(s);
    ll r=0,now=0;
    rep(i,0,n){
        if(s[i]=='<'){
            if(r==0){
                ans+=now;
                // l++;
                now++;
            }else{
                ans+=now;
                if(now<0) r++;
                ans-=r*(now-0);
                r=0;
                // l++;
                now=1;
            }
        }else{
            // if(l==0){
                
                ans+=now;
                r++;
                now--;
            // }else{

            // }
        }
    }
    if(s[n-1]=='<'){
        ans+=now;
    }else{
        ans+=now;
        if(now<0) r++;
        ans-=r*(now-0);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define p(s) cout << (s) << endl
#define p2(s,t) cout << (s) << " " << (t) << endl 
#define ALL(v) (v).begin(), (v).end()
typedef long long ll;
using namespace std;

static const ll mod  = 1e9 + 7;
static const ll inf  = 1e18;

static const int White = 0;
static const int Gray = 1;
static const int Black = 2;

void pvector(vector<int> A){
    cout << "[vector]";
    for(int i = 0; i < A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

string replace_with_str (string str, string str_from, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(str_from, pos), pos != string::npos) {
        str.replace(pos, str_from.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main(){
    string S, T, ans;
    cin >> S >> T;
    bool can = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] == T[0] || S[i] == '?'){
            bool same = 1;
            for(int j = 0; j < T.size(); j++){
                if(i + j >= S.size()){
                    same = false;
                    break;
                }
                if(!(S[i+j] == T[j] || S[i+j] == '?')){
                    same = false;
                    break;
                }
            }
            if(same){
                string s1 = S;
                s1.replace(i, T.size(), T);
                replace(s1.begin(), s1.end(), '?', 'a');
                ans = s1;
                can = true;
            }
        }
    }
    if(can) p(ans);
    else p("UNRESTORABLE");
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define m_p make_pair
#define sz(x) (int)x.size()
#define out(x) cerr<<#x<<" = "<<x<<" "
#define outln(x) cerr<<#x<<" = "<<x<<endl
#define outarr(x,l,r) cerr<<#x"["<<l<<"-"<<r<<"] = "; for (int _i=l;_i<=r;++_i) cerr<<x[_i]<<" ";cerr<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
#define gc() getchar()
//char buf[1<<23],*p1=buf,*p2=buf;
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <class T> void read(T &x)
{
    x=0; char c=gc(); int flag=0;
    while (c<'0'||c>'9') flag|=(c=='-'),c=gc();
    while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=gc();
    if (flag) x=-x;
}
template <class T> T _max(T a,T b){return a>b ? a : b;}
template <class T> T _min(T a,T b){return a<b ? a : b;}
template <class T> bool checkmax(T &a,T b){return b>a ? a=b,1 : 0;}
template <class T> bool checkmin(T &a,T b){return b<a ? a=b,1 : 0;}
const int N=400005;
#define int long long
int n,q;
int ans[N],x;
int top=1;
int a[N],tmp[N];
void init()
{
    read(n); read(q);
    top=1; a[1]=n;
}

void run(ll x)
{
    while (top&&a[top]>=x) --top;
    a[++top]=x;
}

void solve()
{
    if (q==0)
    {
        for (int i=1;i<=n;++i)
        {
            printf("1\n");
        }
        return;
    }
    for (int rnd=1;rnd<=q;++rnd)
    {
        read(x);
        run(x);
    }
    //outarr(a,1,top);
    tmp[top]=1;
    for (int i=top;i>=2;--i)
    {
        ll now=a[i];
        tmp[i-1]+=now/a[i-1]*tmp[i];
        now%=a[i-1];
        while (now>=a[1])
        {
            int q=upper_bound(a+1,a+top+1,now)-a-1;
            tmp[q]+=now/a[q]*tmp[i];
            now%=a[q];
        }
        ans[now]+=tmp[i];
    }
    ans[a[1]]+=tmp[1];
    for (int i=n-1;i>=1;--i)
    {
        ans[i]+=ans[i+1];
    }
    for (int i=1;i<=n;++i)
    {
        printf("%lld\n",ans[i]);
    }
}

#undef int
int main()
{
    init();
    solve();
    return 0;
}


Measured memory_bytes: 6116
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define lb(s,x) (lower_bound(all(s),x)-s.begin())
#define ub(s,x) (upper_bound(all(s),x)-s.begin())
#define uniq(a) a.erase(unique(all(a)),a.end())
#define bit(k) (1LL<<(k))
// const int INF = 1e9;

#define debug(x) cerr<<(#x)<<": "<<(x)<<endl
template<class T,class U>
ostream& operator<<(ostream& o, const pair<T,U> &p){
    o<<"("<<p.first<<", "<<p.second<<")";
    return o;
}
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }

vector<vector<int>> g;
vector<int> st[3];

void coloring(int cur, int pre, bool col){
    // col = 0 or 1
    st[col].push_back(cur);
    for(int to : g[cur]) {
        if (to == pre) continue;
        coloring(to, cur, !col);
    }
}

int main(void){
    int n;
    cin >> n;
    g.resize(n);
    rep(i,n-1){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    coloring(0, -1, true);

    if (st[0].size() < st[1].size()) {
        swap(st[0], st[1]);
    }

    if ((int)st[1].size() < (n+1)/3) {
        swap(st[1], st[2]);
        rep(i,(n+1)/3){
            st[1].push_back(st[0].back());
            st[0].pop_back();
        }
    }
    while((int)st[0].size() > (n+2)/3) {
        st[2].push_back(st[0].back());
        st[0].pop_back();
    }
    while((int)st[1].size() > (n+1)/3) {
        st[2].push_back(st[1].back());
        st[1].pop_back();
    }
    vector<int> p(n);
    rep(col, 3){
        rep(i, st[col].size()){
            p[st[col][i]] = i*3 + col + 1;
        }
    }
    rep(i,n){
        cout << p[i] << (i < n-1 ? " " : "\n");
    }
    return 0;
}


Measured memory_bytes: 20724
#![allow(unused_imports)]
#![allow(unused_macros)]
// use proconio::input;
use std::cmp::{Ordering::*, Reverse};
use std::collections::{BTreeMap, BTreeSet};
use std::io::{self, BufWriter, Write};
use std::str::{self, SplitAsciiWhitespace};

// I have no idea what I'm doing

macro_rules! answer {
    ($out:ident, $ans:expr) => {
        writeln!($out, "{}", $ans)
    };
}

fn main() -> Result<(), io::Error> {
    let (stdin, stdout) = (io::stdin(), io::stdout());
    let mut scan = UnsafeScanner::new(stdin.lock());
    let mut out = BufWriter::new(stdout.lock());

    let a: usize = scan.token();
    let b: usize = scan.token();

    let sa = (0..b).map(|_| a as u8 + b'0').map(|x| x as char).collect::<String>();
    let sb = (0..a).map(|_| b as u8 + b'0').map(|x| x as char).collect::<String>();

    answer!(out, if sa < sb { sa } else { sb })
}

///////////////////////////////////////////////////////////////////////////////////////////////////

/// Mostly copied from https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs
/// Same API as Scanner but nearly twice as fast, using horribly unsafe dark arts
/// **REQUIRES** Rust 1.34 or higher
pub struct UnsafeScanner<R> {
    reader: R,
    buf_str: Vec<u8>,
    buf_iter: SplitAsciiWhitespace<'static>,
}

impl<R: io::BufRead> UnsafeScanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buf_str: vec![],
            buf_iter: "".split_ascii_whitespace(),
        }
    }

    /// This function should be marked unsafe, but noone has time for that in a
    /// programming contest. Use at your own risk!
    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buf_iter.next() {
                return token.parse().ok().expect("Failed parse [Scanner]");
            }
            self.buf_str.clear();
            self.reader
                .read_until(b'\n', &mut self.buf_str)
                .expect("Failed read");
            self.buf_iter = unsafe {
                let slice = str::from_utf8_unchecked(&self.buf_str);
                std::mem::transmute(slice.split_ascii_whitespace())
            }
        }
    }

    pub fn pair<T: str::FromStr>(&mut self) -> (T, T) {
        (self.token(), self.token())
    }
}

// aka #![feature(bool_to_option)]
trait BoolThen {
    fn then_<T>(self, f: impl FnOnce() -> T) -> Option<T>;
}

impl BoolThen for bool {
    fn then_<T>(self, f: impl FnOnce() -> T) -> Option<T> {
        if self {
            Some(f())
        } else {
            None
        }
    }
}

trait BoolToYes {
    fn yes(self) -> &'static str;
}

impl BoolToYes for bool {
    fn yes(self) -> &'static str {
        match self {
            true => "Yes",
            false => "No",
        }
    }
}


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

void MAIN() {
    int n, l;
    scanf("%d%d", &n, &l);
    std::vector<int> arr(n);
    for(int &now: arr) {
        scanf("%d", &now);
    }
    int idx = -1;
    for(int i = 0; i < n - 1; ++ i) {
        if(arr[i] + arr[i + 1] >= l) {
            idx = i;
            break;
        }
    }
    if(idx == -1) {
        puts("Impossible");
    } else {
        puts("Possible");
        for(int i = 0; i < idx; ++ i) {
            printf("%d ", i + 1);
        }
        for(int i = n - 1; i > idx + 1; -- i) {
            printf("%d ", i);
        }
        printf("%d\n", idx + 1);
    }
}

int main() {
    MAIN();
    return 0;
}


Measured memory_bytes: 1152
#pragma GCC optimize("Ofast")
#include <cstring>
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    ll R;
    float s;

    cin >> R;

    s = 2 * R * M_PI;

    cout << s;

}

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

int main()
{
  vector<string> s(3);
  vector<int> n(3, 0);
  int now_s = 0;

  cin >> s[0] >> s[1] >> s[2];
  while (n[now_s] != s[now_s].size())
  {
    n[now_s]++;
    now_s = s[now_s][n[now_s] - 1] - 'a';
  }
  cout << (char)(now_s + 'A') << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
char moji[21]={'\0'};
int i,j,t,f;

scanf("%s",moji);
for(i=0;moji[i]!='\0';i++){
}
t=i;
for(j=0;j<t/2;j++){
f=moji[j];
moji[j]=moji[i-1];
moji[i-1]=f;
i--;
}
printf("%s\n",moji);

return 0;
}

Measured memory_bytes: 524
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
#define MOD 1000000007
using namespace std;

char str[100005];

int main(int argc, char* argv[])
{
    scanf("%s", str);

    long n=strlen(str);
    long count[2]={0};
    long i;
    for(i=0; i<n; i++) {
        count[str[i]-'0']++;
    }
    printf("%ld\n", MIN(count[0],count[1])*2);

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
int main()
{
	string S;
	long long K;
	cin >> S;
	cin >> K;

	long long G = 5000000000000000;

	int ans = 0;
	for(int i=0;i<S.size();i++){
		int base = S[i] - '0';
		K -= (long long)pow((long long)base, G-1);
		if(K<=0){
			ans = base;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

ll N;
map<string, ll> M;
signed main(){
    string a, a1, a2;
    ll b1, b2;
    cin >> a1 >> a2;
    cin >> b1 >> b2;
    M[a1]+=b1;
    M[a2]+=b2;
    cin >> a;
    M[a]--;
    cout << M[a1] << " " << M[a2] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define int long long

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using P = std::pair<int, int>;
using ll = long long;
using ld = double;

using bint = boost::multiprecision::cpp_int;


template<typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

const int MOD = 1e9 + 7;

template<typename T>
class Union_Find {
  private:
	vector<T> t, s;

  public:
	explicit Union_Find(T max_length) {
		for (int i = 0; i < max_length + 1; ++i) {
			t.push_back(i);
			s.push_back(1);
		}
	}

	void Union(T x, T y) {
		if (same(x, y)) return;
		T tx = Find(x), ty = Find(y);
		if (s[tx] < s[ty]) {
			s[ty] += s[tx];
			t[tx] = ty;
		}
		else if (s[tx] > s[ty]) {
			s[tx] += s[ty];
			t[ty] = tx;
		}
		else if (tx > ty) {
			t[tx] = ty;
			s[ty] += s[tx];
		}
		else {
			t[ty] = tx;
			s[tx] += s[ty];
		}
	}
	T Find(T n) {
		if (t[n] == n)
			return n;
		else
			return t[n] = Find(t[n]);
	}

	bool same(T x, T y) {
		return Find(x) == Find(y);
	}

	T get_Size(size_t a) const {
		return s[a];
	}
};

// https://twitter.com/vane11ope ←フォローしましょう
// (ノ)>◡<(ヾ)ﾓﾁﾓﾁ
signed main(signed argc, char* argv[]) {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int n,q;
    cin>>n>>q;
    Union_Find<int> tree(n);
    rep(i,q){
        int t,u,v;
        cin>>t>>u>>v;
        if(t){
            cout<<tree.same(u,v)<<endl;
        }
        else tree.Union(u,v);
    }
}


Measured memory_bytes: 6404
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
   public static void main(String args[])
   {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int k=sc.nextInt();
       int a[]=new int[n];
       for(int i=0;i<n;i++)a[i]=sc.nextInt();
       int dp[]=new int[n];
       dp[0]=0;
       dp[1]=Math.abs(a[1]-a[0]);
       for(int i=2;i<n;i++)
       {dp[i]=Integer.MAX_VALUE;
           for(int j=Math.max(0,i-k);j<i;j++)
           {
               dp[i]=Math.min(dp[i],dp[j]+Math.abs(a[i]-a[j]));
           }
       }
       System.out.println(dp[n-1]);
       }
       
   }

Measured memory_bytes: 50824