akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[][] c = new char[H][W];
		int n = H * W;
		int[] d  = new int[n];
		for(int i = 0; i < H; i++) {
			String s = sc.next();
			for(int j = 0; j < W; j++) {
				c[i][j] = s.charAt(j);
				int idx = i * W + j;
				if(c[i][j] == '#') {
					d[idx] = 0;
				}else {
					d[idx] = 1;
				}
			}
		}
		sc.close();
		DisjointSet ds = new DisjointSet(n);
		// 右、左、下、上
		int[] dn = {1, -1, W, -W};
		int[] replace = {1, 0, 3, 2};;
		boolean[][] flag = new boolean[n][4];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 4; j++) {
				flag[i][j] = true;
			}
		}
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < 4; j++) {
//				int ni = i + dn[j];
//				if(ni >= 0 && ni < n) {
//					if(d[i] == d[ni]) continue;
//					if(!flag[i][j]) continue;
//					ds.unite(i, ni);
//					flag[i][j] = false;
//					flag[ni][replace[j]] = false;
//				}
//			}
//		}
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				if(i + 1 < H && c[i][j] != c[i + 1][j]) {
					ds.unite(W * i + j, W * (i + 1) + j);
				}
				if(j + 1 < W && c[i][j] != c[i][j + 1]) {
					ds.unite(W * i + j, W * i + j + 1);
				}
			}
		}
		long ans = 0;
		long[] b = new long[n];
		long[] w = new long[n];
		for(int i = 0; i < n; i++) {
			if(d[i] == 0) {
				b[ds.findSet(i)]++;
			}else {
				w[ds.findSet(i)]++;
			}
		}
		for(int i = 0; i < n; i++) {
			ans += b[i] * w[i];
		}
		System.out.println(ans);
	}
	static class DisjointSet {
        int[] p;
        int[] rank;
        int[] size;
        DisjointSet(){}
        DisjointSet(int size){
            this.rank = new int[size];
            this.p = new int[size];
            this.size = new int[size];
            for(int i = 0; i < size; i++) {
                makeSet(i);
            }
        }
        void makeSet(int x) {
            p[x] = x;
            rank[x] = 0;
            size[x] = 1;
        }
        boolean same(int x, int y) {
            return findSet(x) == findSet(y);
        }
        void unite(int x, int y) {
            link(findSet(x), findSet(y));
        }
        void link(int x, int y) {
            if(rank[x]  > rank[y]) {
                p[y] = x;
                size[x] = size[x] + size[y];
            }else if(rank[x] < rank[y]){
                p[x] = y;
                size[y] = size[x] + size[y];
            }else if(x != y) {
            	p[y] = x;
            	rank[x]++;
            	size[x] = size[x] + size[y];
            }
        }
        int findSet(int x) {
            if(x != p[x]) {
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
        int size(int x) {
        	if(x != p[x]) {
        		size[x] = size(findSet(x));
        	}
        	return size[x];
        }
    }
}


Measured memory_bytes: 37040
def solve():
    from math import acos
    from cmath import phase, rect, pi
    
    from sys import stdin
    file_input = stdin
    
    while True:
        n = int(file_input.readline())
        if n == 0:
            break
        
        C = (map(int, file_input.readline().split()) for i in range(n))
        P = []
        x, y, r1 = next(C)
        c1 = x + y * 1j
        P.append(c1)
        
        # calculation of cross points of circles
        for x, y, r2 in C:
            c2 = x + y * 1j
            
            base = c2 - c1
            d = abs(base)
            a = acos((r1 ** 2 + d ** 2 - r2 ** 2) / (2 * r1 * d))
            t = phase(base)
            cp1 = c1 + rect(r1, t + a)
            cp2 = c1 + rect(r1, t - a)
            
            P.append(cp1)
            P.append(cp2)
            
            c1, r1 = c2, r2
        
        # search path and calculation of its cost
        lim = 5000
        dist = [lim] * (2 * n)
        dist[0] = 0
        goal = c1
        g_idx = 2 * n - 1
        indices = ((i + (i % 2) + 1, i + (i % 2) + 2) for i in range(g_idx))
        
        for tpl_idx, cp, d in zip(indices, P, dist):
            j, k = tpl_idx
            s1 = None
            s2 = None
            p_s1 = None
            p_s2 = None
            for l, cp1, cp2 in zip(range(j, g_idx, 2), P[j::2], P[k::2]):
                t_s1 = cp1 - cp
                t_s2 = cp2 - cp
                if s1 is None or phase(s1 / t_s1) >= 0:
                    s1 = t_s1
                if s2 is None or phase(s2 / t_s2) <= 0:
                    s2 = t_s2
                if phase(s1 / s2) < 0:
                    break
                
                if p_s1 != s1:
                    dist[l] = min(dist[l], d + abs(s1))
                    p_s1 = s1
                if p_s2 != s2:
                    dist[l+1] = min(dist[l+1], d + abs(s2))
                    p_s2 = s2
            else:
                gs = goal - cp
                if (s1 is None and s2 is None) or \
                phase(s1 / gs) >= 0 and phase(s2 / gs) <= 0:
                    dist[g_idx] = min(dist[g_idx], d + abs(gs))
        
        print(dist[g_idx])

solve()


Measured memory_bytes: 5936
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        n, t = map(lambda x: int(x), line.split(" ", 2))
        showers = map(lambda x: int(x), raw_input().split(" "))

        water = 0
        stop = 0
        for shower in showers:
            if stop > shower:
                water -= (stop - shower)
            water += t
            stop = shower + t
        print(water)

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Measured memory_bytes: 20060
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N): #aを決定
    for j in range(i+1, N): #bを決定
        c = L[i] + L[j] #cの最大値を決定
        pos = bisect.bisect_left(L, c)
        res += max(0, pos-j-1)
print(res)

Measured memory_bytes: 43500
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  int n,m;
  cin>>n>>m;
  cout<<(1<<m)*((n-m)*100+1900*m)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RF(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define MIN3(a,b,c) (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c))
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN2(a,b) (a)<(b)?(a):(b)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
#define ull unsigned long long
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;
#define deb(x )     cerr << #x << " here "<< x << endl;
#define endl    "\n"
#define printCase() "Case #" << caseNum << ": "
inline bool is_palindrome(const string& s){ return std::equal(s.begin(), s.end(), s.rbegin()); }
const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
/*----------------------------------------------------------------------*/
 
const int N = 1e5+5;
int dp[N][3],vals[N][3];
 
int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
 
    int n;
    cin>>n;
 
    F(i, 0, n) {
    	F(j, 0, 3) {
    		cin>>vals[i][j];
    	}
    }
    memset(dp, -1, sizeof(dp));
    F(i, 0, 3) {
    	dp[0][i]=vals[0][i];
    }
 
    F(i, 1, n) {
    	F(j, 0, 3) {
    		int maxm = -1;
    		F(k, 0, 3) {
    			if(k == j) continue;
    			maxm = max(maxm, dp[i-1][k]);
    		}
    		dp[i][j]=maxm + vals[i][j];
    	}
    }
    cout<<max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
 
    return 0;
}/*
 
*/

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;
const int mxn=3003;
int a[mxn],b[mxn];
int dpl[mxn][mxn],dpr[mxn][mxn];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n,t; cin >> n >> t;
	for(int i=1; i<=n; i++)cin >> a[i] >> b[i];
	for(int i=1; i<=n; i++){
		for(int j=0; j<=t; j++){
			dpl[i][j] = max(dpl[i][j],dpl[i-1][j]);
			if(j>=a[i])dpl[i][j]=max(dpl[i][j],dpl[i-1][j-a[i]]+b[i]);
		}
	}
	for(int i=n; i>=1; i--){
		for(int j=0; j<=t; j++){
			dpr[i][j] = max(dpr[i][j],dpr[i+1][j]);
			if(j>=a[i])dpr[i][j]=max(dpr[i][j],dpr[i+1][j-a[i]]+b[i]);
		}
	}
	int ans = 0;
	for(int i=1; i<=n; i++){ // i being the last plate
		int now = b[i];
		for(int j=0; j<t; j++){
			now = max(now,b[i]+dpl[i-1][j]+dpr[i+1][t-1-j]);
		}
		ans = max(ans,now);
	}
	cout << ans << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 70784
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#include<vector>
#define INF INT_MAX
using namespace std;

int N;
string S;

int main(){
	cin >> N >> S;
	if (N == 1){
		cout << "No" << endl;
		return 0;
	}
	else if (N % 2 != 0){
		cout << "No" << endl;
		return 0;
	}
	for (int i = 0; i < N / 2; i++){
		if (S[i] != S[i + N / 2]){
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Set<Integer> ans = new HashSet<>();
    int lastAns;
    if (N == 3) {
      System.out.println("2 3 25");
    } else if (N==4) {
      System.out.println("2 3 5 20");
    } else if (N==5) {
      System.out.println("2 3 4 5 16");
    } else {
      ans.add(2);
      ans.add(3);
      int sum = 5;
      for (int i=4;;i++) {
        if (i%2==0 || i%3==0) {
          ans.add(i);
          sum += i;
          lastAns = i;
          if (ans.size() == N) {
            break;
          }
        }
      }
      if (sum % 6 == 0) {
        // do nothing
      } else if (sum % 6 == 2) {
        ans.remove(8);
        for (int i = lastAns+1;;i++) {
          if (i % 6 == 0) {
            ans.add(i);
            break;
          }
        }
      } else if (sum % 6 == 3) {
        ans.remove(9);
        for (int i = lastAns+1;;i++) {
          if (i % 6 == 0) {
            ans.add(i);
            break;
          }
        }
      } else {
        ans.remove(9);
        for (int i = lastAns+1;;i++) {
          if (i % 6 == 4) {
            ans.add(i);
            break;
          }
        }
      }
      for (Integer an : ans) {
        System.out.print(an + " ");
      }
    }
  }
}

Measured memory_bytes: 31428
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200001],n,ans;
map<ll,ll> mp;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    for(auto x:mp)ans+=x.second*(x.second-1)/2;
    for(int i=0;i<n;i++){
        cout<<ans-mp[a[i]]+1<<endl;
    }
}


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

int main(){
	int Max,Min,k;
	cin>>Max;
	Min=Max;
	for(int i=0;i!=4;++i){
		int tmp;
		cin>>tmp;
		Max=max(tmp,Max);
		Min=min(Min,tmp);
	}
	cin>>k;
	if(Max-Min<=k)cout<<"Yay!\n";
	else cout<<":(\n";
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

int main(){
    ll N;
    cin >> N;
    map<string, int> x;
    REP(i,N){
        string s;
        cin >> s;
        x[s]++;
    }

    printf("AC x %d\n", x["AC"]);
    printf("WA x %d\n", x["WA"]);
    printf("TLE x %d\n", x["TLE"]);
    printf("RE x %d\n", x["RE"]);
    return 0;
}


Measured memory_bytes: 3736
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val a: BigInt = BigInt(sc.next)
    val b: BigInt = BigInt(sc.next)
    if (a == b) println("EQUAL")
    else if (a > b) println("GREATER")
    else println("LESS")
  }
}


Measured memory_bytes: 25544
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <complex>
using namespace std;

#define INF_LL (ll)1e18
#define INF (int)1e9
#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(x) x.begin(),x.end()
#define fs first
#define sc second
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

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

	void unite(int x, int 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]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int N, M;
ll a[114514];
map<int, int> mp;
vector<vector<ll> > v;

bool cmp(const vector<ll>& v1, const vector<ll>& v2){
	return v1.size() == v2.size() ? v1[0] < v2[0] : v1.size() > v2.size();
}

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

	cin >> N >> M;
	Union_find uf(N);
	REP(i, N)
		cin >> a[i];
	REP(i, M){
		int x, y;
		cin >> x >> y;
		uf.unite(x, y);
	}
	REP(i, N){
		int p = uf.find(i);
		if(mp[p] == 0){
			v.push_back(vector<ll>());
			mp[p] = v.size();
			v[mp[p]-1].push_back(a[i]);
		}else{
			v[mp[p]-1].push_back(a[i]);
		}
	}
	if(v.size() == 1){
		cout << 0 << endl;
		return 0;
	}
	sort(all(v));
	int cnt1 = 0, cnt2 = 0, cnt3 = 0;
	ll res= 0;
	REP(i, v.size()){
		sort(all(v[i]));
		if(v[i].size() == 1){
			cnt1++;
			res += v[i][0];
		}else{
			cnt2+=v[i].size();
			cnt3++;
		}
	}
	if(cnt1 > cnt2-(cnt3-1)*2){
		cout << "Impossible" << endl;
		return 0;
	}
	priority_queue<ll, vector<ll>, greater<ll> > pq;
	REP(i, v.size()){
		if(v[i].size() == 1) continue;
		res += v[i][0];
		FOR(j, 1, v[i].size())
			pq.push(v[i][j]);
	}
	REP(i, cnt3-2+cnt1){
		if(pq.empty()){
			cout << "Impossible" << endl;
			return 0;
		}
		res += pq.top(); pq.pop();
	}
	cout << res << endl;
}


Measured memory_bytes: 12392
N = int(input())
h = list(map(int,input().split()))

dp = [0]*N
dp[1] = abs(h[0] - h[1])

for i in range(2,N):
    dp[i] = min(abs(h[i-2] - h[i]) + dp[i-2],abs(h[i-1] - h[i]) + dp[i-1])
print(dp[N-1])

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

using namespace std;

template <class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')
    cerr<<*sdbg++;
  cerr<<"="<<h<<","; 
  _dbg(sdbg+1, a...);
}

template<class T> ostream & operator<<(ostream & os, vector<T> V){
  os<<"[";
  for(auto vv: V) os << vv <<",";
  return os << "]";
}
template<class L, class R> ostream & operator <<(ostream & os, pair<L,R> P){
  return os <<"("<<P.first <<","<<P.second <<")";
}

#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int main() {
    
    int a, b;
    scanf("%d %d", &a, &b);
    printf(a <= b ? "unsafe\n": "safe\n");
    return 0;
}


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

int main(){
  int N,Q,tmp;
  vector<int> A(pow(10,5)+2,0);
  cin >> N;
  long long ans = 0;
  for(int i=0;i<N;i++){
    cin >> tmp;
    A.at(tmp) ++;
    ans += tmp;
  }
  
  int B,C;
  cin >> Q;
  for(int i=0;i<Q;i++){
    cin >> B >> C;
    A.at(C) += A.at(B);
    ans += (C-B)*A.at(B);
    A.at(B) = 0;
    cout << ans << endl;
  }
}

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

using namespace std;

int main(void){
    
    string number={};
    
    cin >> number;
    
    
    
    if(number[0] == number[1] && number[1] == number[2]){
        
        cout << "Yes" << endl;
        
    }else if(number[1] == number[2] && number[2] == number[3]){
        
        cout << "Yes" << endl;
        
    }else if(number[0] == number[1] && number[2] == number[3] && number[1] == number[2]){
        
        cout << "Yes" << endl;
        
    }else{
        
        cout << "No" << endl;
    
    }
    
    
    return 0;
    
}

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

int cmp(const void *x, const void *y) {
  return *(int *)x - *(int *)y;
}

int main() {
  int n;
  scanf("%d", &n);
  int d[n];
  for (size_t i = 0; i < n; i++) {
    scanf("%d", d+i);
  }
  qsort(d, n, sizeof(int), cmp);
  printf("%d\n", d[n/2] - d[n/2-1]);
  return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define PI (3.141592653589793)
using namespace std;

class Union_Find{
private:
    vector<int> par;
    vector<int> rank;
public:
    Union_Find(int n){
        rep(i,n){
            par.push_back(i);
            rank.push_back(0);
        }
    }
    int find(int x){
        if(par.at(x)==x) return x;
        else return par.at(x)=find(par.at(x));
    }
    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank.at(x)<rank.at(y)){
            par.at(x)=y;
        }else{
            par.at(y)=x;
            if(rank.at(x)==rank.at(y)) rank.at(x)++;
        }
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
};

signed main(){
    int n,k,l; cin>>n>>k>>l;
    Union_Find road(n),train(n);
    rep(i,k){
        int a,b; cin>>a>>b;
        road.unite(a-1, b-1);
    }
    rep(i,l){
        int a,b; cin>>a>>b;
        train.unite(a-1, b-1);
    }
    map<P,int> m;
    rep(i,n){
        m[P(road.find(i),train.find(i))]++;
    }
    rep(i,n-1){
        cout<<m[P(road.find(i),train.find(i))]<<' ';
    }
    cout<<m[P(road.find(n-1),train.find(n-1))]<<endl;
}

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


int B[ 500 ][ 500 ];

int main()
{
int i;
int j;
int N;
int a;
int k;
int iNew;
int A;

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

	cin >> N;

	k = N * 2;
	for( a = 1; a < 447; a++ )
	{
		if( a * ( a + 1 ) == k ) break;
	}

	if( a == 447 )
	{
		cout << "No" << endl;

		return 0;
	}

	for( k = 0; k < a; k++ )
	{
		B[ 0 ][ k ] = k + 1;
	}

	iNew = a + 1;
	A = 0;
	for( k = 1; k <= a; k++ )
	{
		for( i = 0; i < k; i++ )
		{
			B[ k ][ i ] = B[ i ][ A ];
		}

		A++;
		for( ; i < a; i++ )
		{
			B[ k ][ i ] = iNew;
			iNew++;
		}
	}

	cout << "Yes" << endl;
	cout << a + 1 << endl;

	for( k = 0; k <= a; k++ )
	{
		cout << a << " " << B[ k ][ 0 ];
		for( i = 1; i < a; i++ )
		{
			cout << " " << B[ k ][ i ];
		}

		cout << endl;
	}

	return 0;
}






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

def getH(x, cx, y, cy, h):
    return h + abs(x-cx) + abs(y-cy)

N = int(input())
conditions = []
for i in range(N):
    x,y,h = map(int, input().split())
    if h > 0:
        conditions.append([x,y,h])

num_cnd = len(conditions)
if num_cnd==1:
    print(conditions[0][0],conditions[0][1],conditions[0][2])
    exit(0)

for cx in range(101):
    for cy in range(101):
        cnt = 0
        h = 0
        for i,cnd in enumerate(conditions):
            h_tmp = getH(cnd[0], cx, cnd[1], cy, cnd[2])
            if h_tmp >= 1:
                if i==0:
                    h = h_tmp
                    cnt += 1
                elif h == h_tmp:
                    cnt += 1
                    if cnt == num_cnd:
                        print(cx,cy,h)
                        exit(0)
                else:
                    break
            else:
                break
        

print('No')

Measured memory_bytes: 9060
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int c[n];
  int num[n];
  for(int i=0;i<n;i++){
    cin>>c[i];
    num[i+1]=0;
    }

  for(int i=0;i<n;i++){
    if(c[i]<=n){num[c[i]]++;}
    }
  int ans=0;
  for(int i=1;i<=n;i++){
    if(num[i]>=i){
      ans+=i;
      }
    } 
  cout <<n-ans <<endl;
  return 0;
  }


Measured memory_bytes: 1152
a,b,c,d,e,f=map(int,input().split())
x=set()
y=set()
m=f//(100*a)
for i in range(m+1):
  for j in range(f//(100*b)+1):
    x1=i*100*a+j*100*b
    if x1<=f:
      x.add(x1)

m=int(f*(e/100))
for i in range(0,m+1,c):
  for j in range(0,m-i+1,d):
     y.add(i+j)
x.remove(0) 
z=[-1]
ans=[]
for i in x:
  for j in y:
    if i+j<=f and j*100/(i+j)<=e*100/(100+e):
      if j*100/(i+j)>max(z):
        z.append(j*100/(i+j))
        ans.append([i+j,j])
        
print(ans[-1][0],ans[-1][1])


Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<map>
using namespace std;
#define REP(m,n) for(int i=m;i<n;++i)
#define REPj(m,n) for(int j=m;j<n;++j)
#define ll long long
#define mp make_pair

int main() {
	int n;
	ll a, b, ans = 1;
	cin >> n;
	REP(0, n) {
		ll tmp, r = 1;
		cin >> tmp;
		a = max(ans, tmp);
		b = min(ans, tmp);
		while (r != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		ans = ans / a * tmp;
	}
	cout << ans << endl;
	return 0;
}

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

def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))

    dic = {}
    for t in a:
        if t in dic:
            dic[t] += 1
        else:
            dic[t] = 1
    dic = sorted(dic.items(), key=lambda x: -x[1])
    
    if len(dic) > K:
        ans = 0
        for i in range(K, len(dic)):
            ans += dic[i][1]
        print(ans)
    else:
        print(0)



if __name__ == "__main__":
    main()

Measured memory_bytes: 39152
#include <stdio.h>
     
    int main(void) {
      int n, temp, ans;
      int d[100] = {0};

      scanf("%d", &n);
      ans = n;

      for (int i=0; i<n; i++) {
          scanf("%d", &temp);
          if (d[temp-1] == 0) {
              d[temp-1] = 1;
          } else {
              ans -= 1;
          }
      }

      printf("%d\n", ans);

      return 0;
    }

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define repd(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i >= _##i; --i)
#define debug(x...) printf("["#x"]="),print(x);
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fcout cout<<setprecision(4)<<fixed
using namespace std;
typedef long long ll;
//======================================
namespace FastIO{
char print_f[105];void read() {}void print() {putchar('\n');}
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth){x = 0;char ch = getchar();ll f = 1;while (!isdigit(ch)){if (ch == '-')f *= -1;ch = getchar();}while (isdigit(ch)){x = x * 10 + ch - 48;ch = getchar();}x *= f;read(oth...);}
template <typename T, typename... T2>
inline void print(T x, T2... oth){ll p3=-1;if(x<0) putchar('-'),x=-x;do{print_f[++p3] = x%10 + 48;}while(x/=10);while(p3>=0) putchar(print_f[p3--]);if(sizeof...(T2)) putchar(' ');print(oth...);}} // namespace FastIO

using FastIO::print;
using FastIO::read;
//======================================
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn = 1e6+5;

int main() {
#ifndef ONLINE_JUDGE
    freopen("H:\\code\\in.in", "r", stdin);
    freopen("H:\\code\\out.out", "w", stdout);
    clock_t c1 = clock();
#endif
//**************************************
    string s;
    cin>>s;
    auto ch=s[s.size()-1];
    if(ch=='s') s+="es";
    else s+="s";
    cout<<s<<"\n";
//**************************************
    
#ifndef ONLINE_JUDGE
    cerr << "Time:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String a[] = new String[n];
		int dp[][] = new int[n][m];
		for (int i=0;i<n;i++) {
			a[i] = sc.next();
		}
		dp[0][0]= 1;
		for (int i=0;i<n;i++)
			for (int j=0;j<m;j++) {
				if (i==0 && j==0) continue;
				dp[i][j] = 0;
				if (i>0 && a[i-1].charAt(j)=='.') dp[i][j] =(dp[i][j] + dp[i-1][j])%1000000007;
				if (j>0 && a[i].charAt(j-1)=='.') dp[i][j] =(dp[i][j] + dp[i][j-1])%1000000007;
			}
		System.out.println(dp[n-1][m-1]);
		

	}
}


Measured memory_bytes: 33372
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int(i) = (n)-1; (i) >= 0; (i)--)
 
int mod=1e9+7;

struct modCalc{
	int mod;
	int n;
	vector<int> fact,invfact;

	modCalc(){};
	modCalc(int _mod,int _n){
		mod=_mod,n=_n;
		fact.resize(n+1,1);
		invfact.resize(n+1,1);
		for(int i=0;i<n;i++)fact[i+1]=fact[i]*(i+1)%mod;
		invfact[n]=modinv(fact[n]);
		for(int i=n;i>1;i--)invfact[i-1]=invfact[i]*i%mod;
	};

	int modpow(int x,int n){
		int ret=1;
		while(n>0){
			if(n&1)(ret*=x)%=mod;
			(x*=x)%=mod;
			n>>=1;
		}
		return ret;
	}

	int modinv(int x){
		return modpow(x,mod-2);
	}

	int nCm(int x,int y){
		if(y==0)return 1;
		else return fact[x]*invfact[y]%mod*invfact[x-y]%mod;
	}
	int nPm(int x,int y=-1){
		if(y==-1)y=x;
		return fact[x]*invfact[x-y]%mod;
	}
};



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

	modCalc md(mod,n*m);
	int combNum=md.nCm(n*m-2,k-2);
	int ret=0;
	for(int i=1;i<n;i++)(ret+=i*(n-i)*m*m)%=mod;
	for(int i=1;i<m;i++)(ret+=i*(m-i)*n*n)%=mod;
	cout<<ret*combNum%mod<<endl;

}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

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

    ll h, n;
    cin >> h >> n;

    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];

    vector<ll> dp(h+10001, INF);
    dp[0] = 0;

    rep(i, h+10001){
        rep(j, n){
            if(i-a[j] < 0) continue;
            dp[i] = min(dp[i-a[j]] + b[j], dp[i]);
            
        }
    }

    ll res = INF;
    for(int i = h; i < h+10001; ++i){
        res = min(res, dp[i]);
    }

    cout << res << endl;

    return 0;
}

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

#define vt          vector
#define sz(x)       int((x).size())
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

using ll = long long;
using pii = pair<int, int>;

void solve() {
    map<string, int> m{
        {"SUN", 7},
        {"MON", 6},
        {"TUE", 5},
        {"WED", 4},
        {"THU", 3},
        {"FRI", 2},
        {"SAT", 1}
    };

    string s;
    cin >> s;
    cout << m[s];
}

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

    int tcs = 1;
    for (int tc = 1; tc <= tcs; tc++) {
        // cout << "Case " << tc << ": ";
        solve();
    }
}


Measured memory_bytes: 3656
#include <stdio.h>
int main(void){
  int n,t[100],m,p[100],x[100],tt=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&t[i]);
    tt+=t[i];
  }
  scanf("%d",&m);
  for(int i=0;i<m;i++){
    scanf("%d %d",&p[i],&x[i]); 
    printf("%d\n",tt-t[p[i]-1]+x[i]);
  }
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

	int main(void){
		int a,b,c;

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

	if(1<=a<=100 && 1<=b<=100 && 1<=c<=100){

		if(b-a == c-b){
			printf("YES\n");

		}else if(b-a != c-b){
			printf("NO\n");

		}
	}else{
		printf("Error\n");

  	}
  }



		

Measured memory_bytes: 128
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 1e5 + 20 , B = 16 , MASK = (1 << B) ;
int n ;
int X[MASK] , dp[MASK] ;

int x[N] ;
vector <pii> g[N] ;

void pre () {
	vector <int> vec ;

	for (int mask = 1 ; mask < MASK ; mask ++) {
		for (int i = 0 ; i < B ; i ++) {
			if (mask >> i & 1) {
				X[mask] = X[mask ^ (1 << i)] ^ i ;
				break ;
			}
		}

		if (!X[mask]) dp[mask] = 1 , vec.push_back(mask) ;
	}

	for (int m1 : vec)
		for (int m2 : vec)
			if (m2 < m1 && (m1 & m2) == 0)
				dp[m1 | m2] = max(dp[m1 | m2] , dp[m1] + dp[m2]) ;
}

void dfs (int v , int par = -1) {
	for (auto ed : g[v]) {
		int u = ed.F , w = ed.S ;
		if (u == par) continue ;

		x[v] ^= w ;
		x[u] = w ;
		dfs(u , v) ;
	}
}

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

	pre() ;

	cin >> n ;
	for (int i = 0 , u , v , w ; i < n - 1 ; i ++) {
		cin >> u >> v >> w ;
		g[u].push_back({v , w}) ;
		g[v].push_back({u , w}) ;
	}

	dfs(0) ;

	int mask = 0 , cnt = 0 ;

	for (int i = 0 ; i < n ; i ++) {
		if (x[i] == 0) cnt ++ ;
		else if (mask >> x[i] & 1) mask ^= (1 << x[i]) , cnt ++ ;
		else mask ^= (1 << x[i]) ;
	}

	cout << n - cnt - dp[mask] << '\n' ;
}

Measured memory_bytes: 11136
#include <iostream>
#include <queue>
using namespace std;
int main(){

  priority_queue <int> a;
  int tmp1;
  string tmp2;

  while(cin>>tmp2,tmp2!="end"){
    if(tmp2[0]=='i'){
      cin>>tmp1;
      a.push(tmp1);
    }
    else{
      cout<<a.top()<<endl;
      a.pop();
    }
  }
  return 0;

}

Measured memory_bytes: 6940
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
using namespace std;

typedef long long ll;
#define rep1(i, n) for(int i = 1; i <=(ll)(n); i++)
#define rep0(i, n) for(int i = 0; i <=(ll)(n); i++)

int main(){
    ll n;
    cin >> n;
    ll count[(ll)(1e5+1)] = {0};
    ll sum = 0;
    rep0(i,n-1){
        ll tmp;
        cin >> tmp;
        sum += tmp;
        count[tmp]++;
    }
    ll q;
    cin >> q;
    
    rep1(i,q){
        ll b,c;
        cin >> b >> c;
        if(count[b] > 0){
            sum += count[b]*(c -b);
            count[c] += count[b];
            count[b] = 0;
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
typedef long long lint;
using namespace std;

//ただの辺
struct edge {
    using lint = long long int;
    int to;
    lint cost;
    //引数一つの時は距離1
    edge(int t, lint c = 1) : to(t), cost(c) {
    }
};

// 辺の長さを無視した距離
// depend:edge
vector<int> distance_nonweight(vector<vector<edge>> &g, int start) {
    vector<int> res(g.size(), INT_MAX);
    res[start] = 0;
    queue<int> bfs;
    bfs.push(start);
    while (!bfs.empty()) {
        int now = bfs.front();
        bfs.pop();
        for (auto e : g[now]) {
            int next = e.to;
            if (res[next] > res[now] + 1) {
                res[next] = res[now] + 1;
                bfs.push(next);
            }
        }
    }
    return res;
}

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

int main() {
    int n, u, v;
    cin >> n >> u >> v;
    u--, v--;
    vector<vector<edge>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> du = distance_nonweight(g, u);
    vector<int> dv = distance_nonweight(g, v);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (g[i].size() > 1 || du[i] >= dv[i]) continue;
        chmax(ans, dv[i] - 1);
    }
    cout << ans << endl;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }
void ans1(bool x){
  if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){
  if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){
  if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x, ll y, ll z){
  if(x) cout<<y<<endl;else cout<<z<<endl;}   


int main(){
  ll i, j;
  //ll n;
  //cin >> n;
  //ll a, b, c;
  //cin >> a >> b;
  string s; cin >> s;
  ll result = 0;
  bool judge = true;
  for(i=0;i<3;i++){
    result+=s[i]-'a';
  }
  ans1(result==3);

  /*
  vector<ll> a(n);
  for(i=0;i<n;i++)
    cin >> a[i];
  //for(i=0;<n;i++)
  */





  return 0;
}

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

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> H(N);
    rep(i,N) {
        cin >> H[i];
    }

    sort(H.begin(),H.end());
    ll atk = 0;
    rep(i,N-K) {
        atk += H[i];
    }

    cout << atk << endl;
}

Measured memory_bytes: 1792
import java.io.*;
import java.util.Arrays;

class Main{
	public static void main(String[] args)throws IOException{
		int[][][] dis = new int[4][3][10];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cnt = Integer.parseInt(br.readLine());
		for(int i=0; i<cnt; i++){
			String str[] = br.readLine().split(" ");
			int in[] = parseInts(str);
			dis[in[0]-1][in[1]-1][in[2]-1] = dis[in[0]-1][in[1]-1][in[2]-1] + in[3];
		}
		for(int b=0; b<4; b++){
			for(int f=0; f<3; f++){
				for(int r=0; r<10; r++){
					System.out.print(" " + dis[b][f][r]);
				}
				System.out.println();
			}
			if(b!=3)System.out.println("####################");
		}
	}
	static int[] parseInts(String[] s){
		int[] x = new int[s.length];
		for(int i=0; i<s.length; i++){
			x[i] = Integer.parseInt(s[i]);
		}
		return x;
	}
}

Measured memory_bytes: 19340
#include<cstdio>
#define MAX 10000
#define NIL -1
struct Node{int parent,left,right;};
Node T[MAX];
int n,D[MAX],H[MAX];
void setDepth(int u,int d){
 if(u==NIL)return;
 D[u]=d;
 setDepth(T[u].left,d+1);
 setDepth(T[u].right,d+1);
}
int setHeight(int u){
 int h1=0,h2=0;
 if(T[u].left!=NIL)h1=setHeight(T[u].left)+1;
 if(T[u].right!=NIL)h2=setHeight(T[u].right)+1;
 return H[u]=(h1>h2?h1:h2);
}
int getSibling(int u){
 if(T[u].parent==NIL)return NIL;
 if(T[T[u].parent].left!=u&&T[T[u].parent].left!=NIL)return T[T[u].parent].left;
 if(T[T[u].parent].right!=u&&T[T[u].parent].right!=NIL)return T[T[u].parent].right;
 return NIL;
}
void print(int u){
 printf("node %d: ",u);
 printf("parent = %d, ",T[u].parent);
 printf("sibling = %d, ",getSibling(u));
 int deg=0;
 if(T[u].left!=NIL)deg++;
 if(T[u].right!=NIL)deg++;
 printf("degree = %d, ",deg);
 printf("depth = %d, ",D[u]);
 printf("height = %d, ",H[u]);
 if(T[u].parent==NIL)printf("root\n");
 else if(T[u].left==NIL&&T[u].right==NIL)printf("leaf\n");
 else printf("internal node\n");
}
int main(){
 int v,l,r,root=0;
 scanf("%d",&n);
 for(int i=0;i<n;i++)T[i].parent=NIL;
 for(int i=0;i<n;i++){
  scanf("%d %d %d",&v,&l,&r);
  T[v].left=l;
  T[v].right=r;
  if(l!=NIL)T[l].parent=v;
  if(r!=NIL)T[r].parent=v;
 }
 for(int i=0;i<n;i++)if(T[i].parent==NIL)root=i;
 setDepth(root,0);
 setHeight(root);
 for(int i=0;i<n;i++)print(i);
 return 0;
}


Measured memory_bytes: 2672
import sys
input = sys.stdin.buffer.readline

import heapq

#点の数が10**5のオーダー以下で使える
#頂点sからの各頂点への最短距離を出力
def dijkstra(s, n, edge): #s:始点、n:頂点の数、edge:重み付き辺の配列（edge[i]:iから出る[重み、行き先]の配列)
    INF = 10**20
    d = [INF]*n # d[i]: sと点iとの距離
    used = [True]*n #Trueは未確定
    d[s] = 0 #初期条件
    used[s] = False # 初期条件
    edge_list = []
    for a, b in edge[s]:
        heapq.heappush(edge_list, a*(10**6)+b) #heapqの中に重みと辺の抱き合わせた情報を入れる
    while len(edge_list):
        min_edge = heapq.heappop(edge_list) #まだ使われていない頂点の中から最小の重みのものを取りだす
        if not used[min_edge%(10**6)]: # 確定していたらcontinue、確定していない時のみ以下の処理を行う
            continue
        v = min_edge%(10**6) #行き先の情報を復元
        d[v] = min_edge // (10**6) #重みの情報を復元し、sとvの最短距離d[v]を更新する
        used[v] = False
        for e in edge[v]:
            if used[e[1]]: #その行き先がまだ未確定の場合
                heapq.heappush(edge_list, (e[0]+d[v])*(10**6) + e[1])
        
    return d


n = int(input())

edge = [[] for _ in range(n)] # edge:重み付き辺の配列（edge[i]:iから出るtuple(重み、行き先)の配列)
for _ in range(n):
    x, y, *li = list(map(int, input().split()))
    for i in range(y):
        edge[x].append((li[2*i+1], li[2*i]))
        #edge[li[2*i]].append([li[2*i+1], x]) # 無向グラフのとき

d = dijkstra(0, n, edge)

for i in range(n):
    print(i, d[i])


Measured memory_bytes: 78168
while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
 
    result = 0
    for a in range(1, x // 3):
        for b in range(a + 1,  x // 2):
            c = x - a - b
            if b < c <= n:
                result += 1    
    print(result)

Measured memory_bytes: 7688
# include <bits/stdc++.h>
# define rr register
using namespace std;
const int N=200010,INF=0x3f3f3f3f;
string s[N];
map <string,int> Map;
string ans[N];
int n;
int cnt;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	n=read();
	int maxx=0;
	for(rr int i=1;i<=n;++i){
		cin>>s[i];
		++Map[s[i]];
		maxx=std::max(maxx,Map[s[i]]);
	}
	for(rr int i=1;i<=n;++i){
		if(Map[s[i]]==maxx){
			ans[++cnt]=s[i];
			Map[s[i]]=0;
		}
	}
	sort(ans+1,ans+1+cnt);
	for(rr int i=1;i<=cnt;++i){
		cout<<ans[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 28288
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main()
{
	int n;
	cin >> n;
	vector<P> v[100010];
	rep(i,n-1){
		int uu,vv,ww;
		cin >> uu >> vv >> ww;
		v[uu].emplace_back(vv,ww);
		v[vv].emplace_back(uu,ww);
	}

	vi flag(100010,INF);
	queue<P> que;
	que.push(make_pair(1,0)); flag[1] = 0;
	while(que.size()){
		P p = que.front();
		que.pop();
		for(auto x: v[p.first]){
			if(flag[x.first] == INF){
				if(x.second%2 == 0){
					flag[x.first] = p.second;
				}else{
					flag[x.first] = (p.second+1)%2;
				}
				que.push(make_pair(x.first,flag[x.first]));
			}
		}
	}
	
	for(int i = 1; i <= n; i++){
		cout << flag[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 6784
#include<bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define INF (ll)1e18
#define pii pair<ll,ll>
#define mod 1000000007 //998244353
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fb(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define PI 3.141592653589793238
#define pq priority_queue<ll>
#define pqr priority_queue<ll,vector<ll>,greater<ll>()>
using namespace std;
ll pow_mod(ll a,ll b)
{
	ll res=1;
	while(b!=0)
	{
		if(b&1)
		{
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
void solve()
{
   /*
     A red card with the integer A
     
     A green card with the integer B

     A blue card with the integer  C
   */
   
   // C>B>A
   
   ll a,b,c;
   cin>>a>>b>>c;
   
   ll k;
   cin>>k;
   
   ll mn=0;
   
   while(b<=a){
       b*=2;
       mn++;
   }
   
   while(c<=b){
       c*=2;
       mn++;
   }
   
   if(mn<=k){
       cout<<"Yes\n";
   }
   else
   cout<<"No\n";
   
   
}
int32_t main()
{    ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     
//Start from Here.

  ll t;
  t=1;
 // cin>>t;
  while(t--)
  solve();
  
//Good Bye!
    return 0;
}

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

int a, b, k;

int main()
{
    cin >> a >> b >> k;
    for (int i = a;; i--)
    {
        k -= (a % i == 0 && b % i == 0);
        if (k == 0)
        {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
  int n;
  cin>>n;
  int p[n];
  rep(i,n)cin>>p[i];
  int m=2*1000000;
  int ans=0;
  rep(i,n){
    m = min(p[i],m);
    if(m>=p[i])ans++;
  }
  cout<<ans<<endl;
}




Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {
     public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a =  N/100;
        int b = (N - 100 * a)/10;
        int c = N - 100 * a - 10 * b;
        
        //System.out.print("a=" + a + ",b=" + b + ",c= "+ c);
        
        if(a == 7 || b == 7|| c == 7){
            System.out.print("Yes");
        }else{
            System.out.print("No");
        }
     }
}

Measured memory_bytes: 27088
#include<stdio.h>

int main(void){
  int i,j;
  int a,b,c;
  int n;
  int flag;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    
    b = 0;
    c = 0;
    flag = 1;
    for(j=0;j<10;j++){
      scanf("%d",&a);
      if(b < a && c < a){
	if(b < c)c = a;
	else b = a;
      }else if(b < a){
	b = a;
      }else if(c < a){
	c = a;
      }else{
	flag = 0;
      }
    }

    if(flag)printf("YES\n");
    else printf("NO\n");
  }

  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 1000010
using namespace std;

int n,m,ans;
int f[maxn];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) 
	{
		int l,r;
		scanf("%d%d",&l,&r);
		f[l]+=1;
		f[r+1]-=1;
	}
	for(int i=1;i<=n;i++)
	{
		f[i]+=f[i-1];
		if(f[i]==m) ans++;
	} 
	printf("%d",ans);
	
	return 0;
}

Measured memory_bytes: 640
import numpy as np
n = int(input())
arr = list(map(int,input().split()))

odd = 0

for a in arr:
    if a < 0:
        odd += 1

if odd %2 == 0:
    print(np.sum(np.abs(arr)))
else:
    # print(np.sum(np.abs(arr)))
    # print(np.min(np.abs(arr)))
    print(np.sum(np.abs(arr))-2*np.min(np.abs(arr)))

Measured memory_bytes: 23272
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long a,b,k;
  cin>>a>>b>>k;
  if(a+b<=k){
    cout<<0<<" "<<0<<endl;
    return 0;
  }
  if(a>k){
    cout<<a-k<<" "<<b<<endl;
    return 0;
  }
  cout<<0<<" "<<a+b-k<<endl;
  
}

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

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

ll N, A, B, C;
vector<ll> L;

ll solve(ll i, ll a, ll b, ll c)
{
	if (i == N)
	{
		if (a == 0 || b == 0 || c == 0) return 1ll << 60;
		return abs(A-a) + abs(B-b) + abs(C-c);
	}
	ll res{1ll<<60};
	chmin(res, solve(i+1, a, b, c));
	chmin(res, solve(i+1, a+L[i], b, c) + (a == 0 ? 0 : 10));
	chmin(res, solve(i+1, a, b+L[i], c) + (b == 0 ? 0 : 10));
	chmin(res, solve(i+1, a, b, c+L[i]) + (c == 0 ? 0 : 10));
	
	return res;
	
}

int main(int argc, char **argv)
{
	cin >> N >> A >> B >> C;
	L.resize(N); for (int i = 0; i < N; ++i) cin >> L[i];

	std::cout << solve(0, 0, 0, 0) << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define IN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////
const ll p = 1000000007;
const ll NMAX = 510000;
ll fac[NMAX],finv[NMAX],inv[NMAX];
void combinit(){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	
	FORq(i,2,NMAX-1){
		fac[i] = fac[i-1] * i % p;
		inv[i] = p - inv[p%i] * (p / i) % p;
		finv[i] = finv[i-1] * inv[i] % p;
	}
}
long long comb(ll n,ll r){
	if (n<r) return 0;
	if (n < 0 || r < 0) return 0;
	return fac[n] * (finv[r] * finv[n-r] % p) % p;
}
int main(){
	combinit();
	ll H,W,A,B;
	cin >> H >> W >> A >> B;
	
	ll ans = 0;
	
	for(ll r = B;r<=W-1;r++){ //回数
		ll n1 = ((H-A-1)+r) % p;
		ll n2 = ((A-1) + (W-r-1)) % p;
		
		ll n1cr = comb(n1,r);
		ll n2cr = comb(n2,A-1);
		
		ans = (ans + ((n1cr * n2cr) % p) ) % p;
	}
	
	PRINTLLD(ans);
	return 0;
}



Measured memory_bytes: 12160
#include <bits/stdc++.h>
using namespace std;
#define loop(i,b,e) for(int i=b;i<=e;i++)
#define loop2(i,e,b) for(int i=e;i>=b;i--)
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5;
const ll mod = 1e9 + 7;
const int oo = 1e9;

int n;
ll t[N];
map<ll, int> sum;

int main() {
	scanf("%d",&n);
	loop(i, 1, n) {
		cin >> t[i];
		t[i] += t[i-1];
	}
	ll ans = 0;
	loop(i, 1, n) {
		if (t[i] == 0) ans++;
		if (sum[t[i]]) ans += sum[t[i]];
		sum[t[i]] ++;
	}
	cout << ans;
}

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

int main() {
    
    ll a, b, c, d;
    ll max = -1000000000000000001;

    cin >> a >> b >> c >> d;

    max = a*c;
    if(max < a*d) max = a*d;
    if(max < b*c) max = b*c;
    if(max < b*d) max = b*d;

    cout << max << endl;

    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
    ll n;cin>>n;
    ll ans=0;
    vector<ll> a(n);
    vector<ll> aa(2*100000+1,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
        aa[a[i]]+=1;
    }
    for(int i=1;i<2*100000+1;i++){
        ans+=aa[i]*(aa[i]-1)/2;
    }
    for(int i=0;i<n;i++){
        cout<<ans-(aa[a[i]]-1)<<endl;
    }
}

Measured memory_bytes: 5760
N=int(input())
A=[int(input()) for _ in range(N)]
AS=sorted(A)
# for i in range(N):
#     if AS[-1]==A[i]:
#         print(AS[-2])
#     else:
#         print(AS[-1])
for i in range(N):
    print(AS[-2] if AS[-1]==A[i] else AS[-1])

Measured memory_bytes: 14132