akhauriyash/Code-Regression huggingface dataset:
program back_and_forth
  implicit none
  integer :: x(2), y(2), dx, dy
  read(*,*) x(1), y(1), x(2), y(2)
  dx = x(2) - x(1)
  dy = y(2) - y(1)
  call out(dx, 'R')
  call out(dy, 'U')
  call out(dx, 'L')
  call out(dy + 1, 'D')
  call out(dx + 1, 'R')
  call out(dy + 1, 'U')
  call out(1, 'L')
  call out(1, 'U')
  call out(dx + 1, 'L')
  call out(dy + 1, 'D')
  call out(1, 'R')
  write(*,*)
contains
  subroutine out(n, c)
    integer, intent(in) :: n
    character(1) :: c
    integer :: i
    do i = 1, n
      write(*,'(a)',advance='no') c
    end do
  end
end program back_and_forth

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

using namespace std;

using int64 = long long;

template<typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}

template<typename T>
struct SquareMatrix {
 private:
  vector<vector<T>> matrix;
 public:
  const vector<vector<T>>& Value() { return matrix; }
  SquareMatrix(vector<vector<T>>& in_matrix) : matrix(in_matrix) {}
  SquareMatrix<T> operator*(SquareMatrix<T> o) {
    int n = matrix.size();
    vector<vector<T>> result(n, vector<T>(n));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          result[i][j] += matrix[i][k] * o.matrix[k][j];
        }
      }
    }
    return SquareMatrix(result);
  }
  vector<T> operator*(vector<T> o) {
    int n = matrix.size();
    vector<T> result(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        result[i] += matrix[i][j] * o[j];
      }
    }
    return result;
  }
  // TODO: Rewrite it without a recursion.
  SquareMatrix<T> Power(int64 p) {
    int n = matrix.size();
    if (p == 0) {
      vector<vector<T>> result(n, vector<T>(n));
      for (int i = 0; i < n; i++) result[i][i] = 1;
      return result;
    } else if (p % 2 == 1) {
      return *this * Power(p - 1);
    } else {
      auto m = Power(p / 2);
      return m * m;
    }
  }
};

constexpr int64 P = 1000000007;

// Verified: ABC133E, ABC132D, ABC130E
struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 input_x) : x(input_x) {}
  FiniteField() : x(0) {}
  int64 Value() { return x; }
  inline FiniteField operator+(FiniteField o) {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

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

  int n;
  int64 k;
  cin >> n >> k;
  vector<vector<FiniteField>> mat = Make2DVector<FiniteField>(n, n, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int v;
      cin >> v;
      mat[j][i] = v;
    }
  }

  SquareMatrix<FiniteField> mat_c(mat);
  auto powered_mat_c = mat_c.Power(k);
  auto powered_mat = powered_mat_c.Value();
  FiniteField ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans += powered_mat[i][j];
    }
  }
  cout << ans.Value() << endl;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.nextLine();
		String S = sc.nextLine();
		
		if (N % 2 == 1) {
			System.out.println("No");
			return;
		}
		
		int M = N/2;
		String S1 = S.substring(0,M);
		String S2 = S.substring(M,N);
		
		if (S1.equals(S2))
			System.out.println("Yes");
		else
			System.out.println("No");
	}

}


Measured memory_bytes: 21972
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif 

const ll MOD = 1e9 + 7;
string C[4] = { "A","G","C","T" };
int N;
//ll ans = 0;
vector<map<string, ll>> dp;
ll dfs(int n, int i, string res) {
    if (n>=3) {
        string s = res.substr(n-3,3);
        if (s == "AGC" || s == "GAC" || s == "ACG") {
            return 0;
        }
    }
    if (n>=4) {
        string s = res.substr(n-4,4);
        if ((s[0] == 'A' && s[2] == 'G' && s[3]=='C') ||
            (s[0] == 'A' && s[1] == 'G' && s[3]=='C')) {
            return 0;
        }
    }


    if (n >= N) {
        //ans += 1;
        //ans %= MOD;
        return 1;
    }

    if (n>=4) {
        string s = res.substr(n-4,4);
        if (dp[n].count(s) > 0) return dp[n][s];
    }

    ll ret = 0;
    for(int j=0; j<4; j++) {
        ret += dfs(n + 1, j, res+C[j]);
        ret %= MOD;
    }

    if (n>=4) {
        string s = res.substr(n-4,4);
        dp[n][s] = ret;
    }

    return ret;
}

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

    cin >> N;
    
    ll ans = 0;
    dp = vector<map<string,ll>>(N+2);
    for(int i=0; i<4; i++) {
        ans += dfs(1, i, C[i]);
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2688
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define findmax(a,b) (a)>(b)?(a):(b)
#define findmin(a,b) (a)<(b)?(a):(b)
#define inout freopen("in.txt","r",stdin);freopen("out.txt","w",stdout)
#define swap(a,b) (a)+=(b);(b)=(a)-(b);(a)-=(b)
#define quicksort(a,n) qsort(a,n,sizeof(a[0]),cmp)
#define inputarr(a,n) for(int i=0;i<n;i++){scanf("%d",&a[i]);}
#define printarr(a,n) for(int i=0;i<n;i++){printf("%d ",a[i]);}puts("");
int cmp(const void *a,const void *b){return *(int *)a - *(int *)b;}

int main() {

	//inout;

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


}

Measured memory_bytes: 1728
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();    
        int N, M;
        {int[] a = r.ii(); N = a[0]; M = a[1];}
        int[][] swc = new int[M][];
        for(int i = 0; i < M; i++)
            swc[i] = r.ii();
        int[] p = r.ii();
        int ans = 0;
        for(int i = 0; i < Math.pow(2, N); i++){
            String swcS = String.format("%0" +N+ "d", Int(Integer.toBinaryString(i)));
            int num = 0;
            for(int j = 0; j < M; j++){
                int t = 0;
                for(int k = 0; k < swc[j][0]; k++){
                    if(swcS.charAt(swc[j][k+1]-1) == '1')
                        t++;
                }
                if(t%2 == p[j])
                    num++;
                else
                    break;
            }
            if(num == M)
                ans++;
        }
        println(ans);
    }

    static void print(Object o){
        System.out.print(o.toString());
    }

    static void println(Object o){
        System.out.println(o.toString());
    }

    static int Int(String s){
        return Integer.parseInt(s);
    }

    static long Long(String s){
        return Long.parseLong(s);
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }

        String s() throws IOException{
            return readLine();
        }

        String[] ss() throws IOException{
            return s().split(" ");
        }

        int i() throws IOException{
            return Int(s());
        }

        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }

        long l() throws IOException{
            return Long(s());
        }

        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}


Measured memory_bytes: 24860
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
mod=10**9+7
def do():
    n=INT()
    A=LIST()
    B=[0]*(n)
    B[0]=sum(A[1:])
    ans=0

    for i in range(1,n):
        B[i]=(B[i-1]-A[i])%mod

    for i in range(n-1):
        ans+=(A[i]*B[i])%mod
        ans=ans%mod

    print(ans)

    

    
if __name__=='__main__':
    do()

Measured memory_bytes: 31292
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
int d[maxn], a[maxn], b[maxn];

int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    for(int i = 0; i < n; i++)cin>>b[i];
    for(int i = 0; i < n; i++)d[i] = b[i] - a[i];
    sort(d, d + n);
    ll cnt = 0, cnt1 = 0, cnt0 = 0;
    for(int i = n - 1; i >= 0; i--){
        if(d[i] <= 0)break;
        cnt += d[i] / 2;
        d[i] %= 2;
        if(d[i] == 0)cnt0++;
        else cnt1++;
    }
    for(int i = 0; i < n; i++){
        if(d[i] >= 0)break;
        cnt += d[i];
    }
    if(cnt >= 0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

int main() {
  int ans=0;
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int x100=0;
  int x50=0;
  for (int i=0; i<=(X/500); i++) {
    if (i>A) continue;
    x100=X-(500*i);
    if (x100 == 0) {
      ans++;
      continue;
    }
    for (int j=0; j<=(x100/100); j++) {
      if (j>B) continue;
      x50=x100-(100*j);
      if (x50 == 0) {
        ans++;
        continue;
      }
      for (int k=0; k<=(x50/50); k++) {
        if (k>C) continue;
        if (x50-(50*k) == 0) ans++;
      }
    }
  }
  cout << ans << endl;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  int a, p;
  cin >> a >> p;
  cout << (a * 3 + p) / 2 << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n],b[n];
    long long int add_1 = 0,add_2 = 0;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    for(int i = 0;i < n;i++)
    {
        cin >> b[i];
        if(a[i] > b[i])
        {
            add_1 += a[i] - b[i];
        }
        else
        {
            add_2 += (b[i] - a[i]) / 2;
        }
    }
    if(add_1 <= add_2)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
    
    return 0;
}

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

int main() {

	int n, a[100010] = {};
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int man;
		cin >> man;
		a[man - 1] = i;
	}
	for (int i = 0; i < n; i++){
		cout << a[i];
		if (i != n - 1) {
			cout << " ";
		}
	}
	cout << endl;

	return 0;
}

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

void genA(int m,vector<int>&A){
	for(int i=A.size()-1;i>=0;--i){
		if(A.at(i)>=m)continue;
		for(int j=i,val=A.at(i)+1;j<A.size();++j){
			A.at(j)=val;
		}
		break;
	}
}

int comb(int n,int m){
	int res=1;
	for(int i=0,base=m+n-1,lim=min(base,base-n);i<lim;++i){
		res*=base-i;
		res/=i+1;
	}
	return res;
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m,q; cin>>n>>m>>q;
	vector<int>a(q),b(q),c(q),d(q);
	for(int i=0;i<q;++i){
		cin>>a.at(i)>>b.at(i)>>c.at(i)>>d.at(i);
		--a.at(i),--b.at(i);
	}
	vector<int>A(n,1); A.back()=0;
	int ans=0;
	for(int i=0,lim=comb(n,m);i<lim;++i){
		genA(m,A);
		int tans=0;
		for(int j=0;j<q;++j){
			if(A.at(b.at(j))-A.at(a.at(j))==c.at(j))tans+=d.at(j);
		}
		ans=max(ans,tans);
	}
	cout<<ans<<"\n"s;
}


Measured memory_bytes: 3604
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意



a = int(input())
#b = [int(i) for i in readline().split()]
s = input()

if a >= 3200:
    print(s)
else:
    print("red")



















Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>

int main()
{
    long H,W,A,B;
    std::cin >> H >> W >> A >> B;
    for(long i=0; i<H; i++){
        for(long j=0; j<W; j++){
            if(i<B){
                if(j<A){
                    std::cout << 1;
                }else{
                    std::cout << 0;
                }
            }else{
                if(j<A){
                    std::cout << 0;
                }else{
                    std::cout << 1;
                }
            }
        }
        std::cout << std::endl;
    }
    return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A[4][4];
  int ans[4][4];
  for(int i=1; i<4; i++){
    for(int j=1; j<4; j++){
      cin >> A[i][j];
      ans[i][j] =0;
    }
  }
  int N;
  cin >> N;
  int b[N];
  for(int i=1; i<N+1; i++){
    cin >> b[i];
  }
  for(int i=1; i<N+1; i++){
    for(int h=1; h<4; h++){
      for(int j=1; j<4; j++){
        if(b[i] == A[h][j]){
          ans[h][j] = 1;
        }
      }
    }
  }
  for(int i=1; i<4; i++){
    if(ans[i][1] + ans[i][2] + ans[i][3] == 3){
      cout << "Yes" << endl;
      return 0;;
    }else if(ans[1][i] + ans[2][i] + ans[3][i] == 3){
      cout << "Yes" << endl;
      return 0;
    }else if(ans[1][1] + ans[2][2] + ans[3][3] == 3 || ans[1][3] + ans[2][2] + ans[3][1] == 3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}


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

const int MaxN = 100;
char s[MaxN+5]; int k,len;

int main(){
	cin >> s >> k;
	len = strlen(s);
	long long ans = 0;
	int head, tail;
	for(int i=0, j; i<len; i=j){
		for(j=i; j<len; ++j)
			if(s[j] != s[i])
				break;
		ans += (j-i)>>1;
		if(not i) head = j-i;
		if(j == len) tail = j-i;
	}
	if(head == len and tail == len)
		ans = 1ll*k*len>>1;
	else{
		ans = ans*k;
		if(s[0] == s[len-1] and head/2+tail/2 < (head+tail)/2)
			ans += k-1;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int A,B,C,X,Y;
int min(){
    if(X>Y)return Y;
    else return X;
}
int max(){
    if(X>Y)return X;
    else return Y;
}
int price(){
    if(max()==X)return A;
    else return B;
}


int main(){
    cin>>A>>B>>C>>X>>Y;
    int sum=0;
    if(A+B>=2*C){
        sum+=2*C*min();
        if((max()-min())*price()>=2*C*(max()-min())) sum+=2*C*(max()-min());
        else sum+=(max()-min())*price();
    }
    else{
        sum+=(A+B)*min();
        if((max()-min())*price()>=2*C*(max()-min())) sum+=2*C*(max()-min());
        else sum+=(max()-min())*price();

    }
    cout<<sum;
}

Measured memory_bytes: 256
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    A, B = l_inpl()
    print(max([A+B, A-B, A*B]))
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 4336
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n=int(input())
    XYI=[0]*n
    for i in range(n):
        x,y=map(int,input().split())
        XYI[i]=(x,y,i)

    # Kruskal に使う可能性のある辺だけをグラフに追加する
    E=[]
    XYI.sort()
    for i in range(n-1):
        x0,y0,u=XYI[i]
        x1,y1,v=XYI[i+1]
        E.append((u,v,x1-x0))
    XYI.sort(lambda x:x[1])
    for i in range(n-1):
        x0,y0,u=XYI[i]
        x1,y1,v=XYI[i+1]
        E.append((u,v,y1-y0))

    # Kruskal method
    E.sort(lambda x:x[2])
    uf=UnionFind(n)
    ans=0
    for u,v,w in E:
        if(uf.unite(u,v)):
            ans+=w
    print(ans)
resolve()

Measured memory_bytes: 113432
console.log((args=>{
  const [N,M] = args.trim().split` `.map(v=>parseInt(v));
  if ( N * 2 <= M ) return `${N + Math.floor((M-2*N)/4)}`;
  else return `${Math.floor(M/2)}`;
})(require('fs').readFileSync('/dev/stdin', 'utf8')));


Measured memory_bytes: 29384
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <time.h>
#define all(c) ((c).begin(),(c).end())
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n)
#define vsort(v) sort(v.begin(),v.end())
#define vvsort(v) sort(v.begin(),v.end(),greater<int>())
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
//---------------------------------------------------------------------------------------------//



int main() {
	int n;
	while (cin >> n) {
		ll sum = 0;
		int now = n;
		while (now < 600) {
			sum += now*now*n;
			now += n;
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 3092
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

using ll = long long;

//constant
const ll MOD = 1e+9 + 7;
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// view vector
template<typename T> void view(T e) { std::cout << e << std::endl; }
template<typename T> void view(const std::vector<T>& v) { for (const auto& e : v) { std::cout << e << " "; } std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

// ***************************************

vector<vector<pair<int, int>>> tree{};
vector<int> color{};


void dfs(int V) {
    for (auto& pr : tree[V]) {
        if (color[pr.first] == -1) {
            color[pr.first] = pr.second % 2 == 0 ? color[V] : 1 - color[V];
            dfs(pr.first);
        }
    }

    return;
}


int main(void) {

    ll N;
    cin >> N;

    REP(i, N) {
        vector<pair<int, int>> vec;
        tree.push_back(vec);
        color.push_back(-1);
    }
    color[0] = 0;

    int u, v, w;
    REP(i, N - 1) {
        cin >> u >> v >> w;
        pair<int, int> p1{ v-1, w }, p2{ u-1, w };
        tree[u - 1].push_back(p1);
        tree[v - 1].push_back(p2);
    }

    dfs(0);

    for (auto& c : color) {
        cout << c << endl;
    }

    return 0;
}

Measured memory_bytes: 8208
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////
template<typename T>
struct edge {
  int to, from;T cost;
  edge(int to) : from(-1), to(to), cost(-1) {}
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};
template<typename T>
using edges = vector<edge<T>>;
template<typename T>
using graph = vector<edges<T>>;
template<typename T>
using matrix = vector<vector<T>>;

template<typename T>
bool compByCost(const edge<T>& left, const edge<T>& right){
  return left.cost < right.cost; 
}

template<typename T>
vector<vector<T>> warshall(matrix<T> &g){
  vector<vector<T>> dist(g.size());
  rep(i,g.size()){
    dist[i].resize(g.size());
    rep(j,g.size())dist[i][j] = (i == j ? 0 : g[i][j]);
  }
  rep(k,g.size()){
    rep(i,g.size()){
      rep(j,g.size()){
        if(dist[i][k] == INF || dist[k][j] == INF)continue;
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  return dist;
}

#define warshall warshall<int>// matの初期化でINFを詰めておく



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

int n,t[110],v[110],s[110];
signed main(){
  cin>>n;rep(i,n)cin>>t[i];rep(i,n)cin>>v[i];
  rep(i,110)s[i] = INF;
  s[0] = s[n] = 0;
  rep(i,n+1){
    chmin(s[i], v[i]);
    repd(j,i+1,n+1){
      chmin(s[j], v[j-1]);
      chmin(s[j], s[j-1]+t[j-1]);
    }
    for(int j = i-1;j >= 0;j--){
      chmin(s[j], v[j]);
      chmin(s[j], s[j+1]+t[j]);
    }
  }
  double ret = 0;
  rep(i,n){
    double ans = 0;
    double a = v[i] - s[i], b = v[i] - s[i+1], c = a+b;
    if(c <= (double)t[i]){
      ans += a*a*0.5 + a*(double)s[i];
      ans += (double)(t[i] - a - b)*(double)v[i];
      ans += b*b*0.5 + b*(double)s[i+1];
    }else{
      double top = 0.5*(double)(t[i] + s[i] + s[i+1]);
      ans += 0.5*(double)(top-s[i])*(double)(top - s[i]);
      ans += 0.5*(double)(top-s[i+1])*(double)(top - s[i+1]);
      ans += (double)(top-s[i])*(double)s[i];
      ans += (double)(top-s[i+1])*(double)s[i+1];
    }
    ret += ans;
  }
  cout << fixed << ret << endl;
}


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

using namespace std;
int n;
int main() {
	cin>>n;
	long long sum=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int k=1;k<=n;k++)
	sum+=__gcd(__gcd(i,j),k);
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3636
/* به نام یزدان */
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100 * 1000 + 5;
int n, h[MAX_N][5], dp[MAX_N][5];

void read_input() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			cin >> h[i][j];
}

void solve() {
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 3; k++)
				if (j != k)
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + h[i][j]);
}

void print_output() {
	int ans = 0;
	for (int i = 0; i < 3; i++)
		ans = max(ans, dp[n][i]);
	cout << ans;
}

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


Measured memory_bytes: 4224
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <numeric>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600
#define long long long

int main(){
  int n;
  string str;
  cin>>n>>str;
  int x=0;
  int ans=0;
  rep(i,n){
    if(str[i]=='I') x++;
    else x--;
    ans = max(ans, x);
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long gcd(long long m, long long n) {
    if (n == 0) return abs(m);

    return gcd(n, m % n);
}

int main() {
    long long A, B;
    cin >> A >> B;

    long long gcbOfAB = gcd(A, B);
    long long ans = 1;

    for (long long i = 2; i * i < gcbOfAB; ++i) {
        if (gcbOfAB % i == 0) {
            ans++;
            while (gcbOfAB % i == 0) gcbOfAB /= i;
        }
    }
    if (gcbOfAB != 1) ans++;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <atcoder/fenwicktree>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
//#define _GLIBCXX_DEBUG

using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll mod = 1e9+7;
void chmod(ll &M){
  if(M >= mod) M %= mod;
  else if(M < 0){
     M += (abs(M)/mod + 1)*mod;
    M %= mod;
}
}
ll modpow(ll x, ll n){
   if(n==0) return 1;
  ll res=modpow(x, n/2);
 if(n%2==0) return res*res%mod;
else return res*res%mod*x%mod;
}
int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };
long long GCD(long long a, long long b) {
  if (b == 0) return a;
  else return GCD(b, a % b);
}

using namespace std;
int main()
{
    int H, N;
    cin >> H >> N;
    int sum = 0;
    rep(i, N) {
        int a;
        cin >> a;
        sum += a;
    }
    if (H <= sum) cout << "Yes" << "\n";
    else  cout << "No" <<  "\n";
}


Measured memory_bytes: 3580
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

const i32 mod = 1000003;

i32 mod_pow (i32 r, i32 n) {
  i32 t = 1;
  i32 s = r;
  while (n > 0) {
    if (n & 1) t = (i64) t * s % mod;
    s = (i64) s * s % mod;
    n >>= 1;
  }
  return t;
}

i32 *inverse = NULL;
i32 inv (i32 a) {
  return inverse[a];
}

i32 *fact = NULL;
i32 *iFact = NULL;
void init_fact (const i32 n) {
  inverse = (i32 *) calloc (n + 1, sizeof (i32));
  fact = (i32 *) calloc (n + 1, sizeof (i32));
  iFact = (i32 *) calloc (n + 1, sizeof (i32));
  fact[0] = fact[1] = iFact[0] = iFact[1] = inverse[1] = 1;
  for (i32 i = 2; i <= n; ++i) {
    inverse[i] = (i64) (mod - mod / i) * inverse[mod % i] % mod;
    fact[i] = (i64) i * fact[i - 1] % mod;
    iFact[i] = (i64) inverse[i] * iFact[i - 1] % mod;
  }
}

i32 calc (i32 x, i32 d, i32 n) {
  if (d == 0) return mod_pow (x, n % (mod - 1));
  if (x == 0) return 0;
  i32 y = (i64) x * inv (d) % mod;
  if (y + n - 1 >= mod) return 0;
  return (i64) fact[y + n - 1] * iFact[y - 1] * mod_pow (d, n % (mod - 1)) % mod;
}

static void print_int(i64 n){if(n<0){putchar('-');n=-n;}if(n==0){putchar('0');return;}int s[20],len=0;while(n>0){s[len++]=n%10+'0';n/=10;}while(len>0){putchar(s[--len]);}}
static i64 read_int(void){int prev='\0';int c=getchar();while(!('0'<=c && c<='9')){prev=c;c=getchar();}i64 res=0;while('0'<=c && c<='9'){res=10*res+c-'0';c=getchar();}return prev=='-'?-res:res;}

void run (void) {
  i32 q;
  scanf ("%" SCNi32, &q);
  init_fact (mod - 1);
  for (i32 i = 0; i < q; ++i) {
    i32 x = read_int();
    i32 d = read_int();
    i32 n = read_int();
    print_int (calc (x, d, n));
    putchar ('\n');
  }
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 12544
/**
 *  author: MOOONI
 *  hackers are welcome!
**/
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a < 0) {
    a += md;
  }
  a %= md;
} 

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> fact(n + 1);
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = mul(fact[i - 1], i);
  }
  vector<int> inv_fact(n + 1);
  inv_fact[n] = inv(fact[n]);
  for (int i = n - 1; i >= 0; i--) {
    inv_fact[i] = mul(inv_fact[i + 1], i + 1);
  }
  auto C = [&](int n, int k) {
    if (k < 0 || k > n) {
      return 0;
    }
    return mul(fact[n], mul(inv_fact[k], inv_fact[n - k]));
  };
  int ans = 0;
  for (int i = 0; i <= k; i++) {
    add(ans, mul(C(n - 1, i), mul(m, power(m - 1, n - i - 1))));
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 4768
#include<bits/stdc++.h>
using namespace std;
int main(){
  long K,N;cin>>K>>N;
  vector<long>A(N);for(long i=0;i<N;i++)cin>>A[i];
  long d=A[0]-(A[N-1]-K);
  for(long i=0;i<N-1;i++)d=max(d,A[i+1]-A[i]);
  cout<<K-d;
}


/*


*/

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int up = 1e5 + 5;
bool visited[up];
vector<int>g[up];

void dfs(int node) {
    visited[node] = true;
    for(int to : g[node]) {
        if(!visited[to]) {
            dfs(to);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    int n, m, u, v;
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int res = -1;
    for(int i = 1; i <= n; ++i) {
        if(!visited[i]) {
            dfs(i);
            res++;
        }
    }
    cout << res << '\n';
    return 0;
}

Measured memory_bytes: 9664
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

bool bad[15];

bool isBad(int n) {
    while (n) {
        if (bad[n % 10])
            return true;
        n /= 10;
    }
    return false;
}

int main() {
    #ifdef LOCAL
    assert(freopen("c.in", "r", stdin));
    #else
    #endif
    int n, k;
    cin >> n >> k;
    forn (i, k) {
        int bad;
        cin >> bad;
        ::bad[bad] = true;
    }
    while (isBad(n))
        ++n;
    cout << n << '\n';
}


Measured memory_bytes: 256
n, m = gets.chomp.split(' ').map(&:to_i)
xs = gets.chomp.split(' ').map(&:to_i).sort
diffs = xs.each_cons(2).map.with_index{|a, i| {i: i + 1, d: (a[1] - a[0]).abs} }.sort{|a, b| b[:d] - a[:d] }
splitter = diffs.take(n - 1).map{|h| h[:i]}.sort
splitted = ([0] + splitter + [xs.length]).each_cons(2).map{|x| xs[x[0]..(x[1]-1)] }
puts splitted.map{|a| a.last - a.first}.reduce(:+)


Measured memory_bytes: 44136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
vector<ll> prime_factorize(ll x){
    vector<ll> res;
    ll y=x;

    for(ll i=2; i*i<=x; i++){
        while(y%i==0){
            y/=i;
            res.push_back(i);
        }
    }
    if(y>1) res.push_back(y);

    return res;
}


int main(){
    ll n; cin>>n;
    vector<ll> res=prime_factorize(n);
    cout<<n<<':';
    for(ll i: res) cout<<' '<<i;
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll a = 1; a < n; a++)
    {
        ans += (n - 1) / a;
    }
    cout << ans << endl;
}

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

class UnionFind {
private:
        vector<int>par;
    public:
        UnionFind(int n) {
            for (int i = 0; i < n; i++) par.push_back(-1);
        }
        int root(int x) {
            if (par[x] < 0) return x;
            else return par[x] = root(par[x]);
        }
        bool same(int x, int y) { return root(x) == root(y);}
        void unite(int x, int y) {
            x = root(x), y = root(y);
            if (x == y) return;
            if (par[x] > par[y]) swap(x, y);
            par[x] += par[y];
            par[y] = x;
            return;
        }
        int size(int x) { return -par[root(x)];}
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uf.unite(a, b);
    }
    set<int>se;
    rep(i, n) {
        se.insert(uf.root(i));
    }
    cout << se.size() - 1 << endl;
    return 0;
}


Measured memory_bytes: 7580
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string a,b;
int dp[3005][3004];
vector<char> res;

inline int maks(int a, int b){
	return a>b?a:b;
}

int main(){

	cin>>a>>b;
	a = "$" + a;
	b = "%" + b;

	for(unsigned i=1;i<a.size();i++){
		for(unsigned j=1;j<b.size();j++){
			if(a[i] == b[j])
				dp[i][j] = 1+dp[i-1][j-1];
			else
				dp[i][j] = maks(dp[i-1][j], dp[i][j-1]);
		}
	}
	int i=a.size()-1, j=b.size()-1;
	//if(a[i] == b[j])res.push_back(a[i]);
	while(i>=1 && j>=1){
		if(a[i] == b[j]){
			res.push_back(a[i]);
			i--; j--;
		}
		else if(dp[i-1][j] > dp[i][j-1]){
			i--;
		}
		else{
			j--;
		}
	}
	for(int i=res.size()-1;i>=0;i--){
		cout<<res[i];
	}
}


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

using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

bool pallan(string s){
    ll i=0,j=s.size()-1;
    while(i<j){
        if(s[i]!=s[j])
            return false;
        i++;
        j--;
    }
    return true;
}
unordered_map<ll,ll> dp;
ll find(ll n){
    if(n==1){
        return 1;
    }
    if(dp[n]!=0)
        return dp[n];
        
    dp[n] = find(n/2)+find(n/2)+1;
    return dp[n];
    
}

int main() {
    fio;
    
    ll n;cin>>n;//>>m;

    cout<<find(n);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define mod 1000000007
const int INF=(1LL<<60)-1;
bool isPowerOfTwo (int x) {
  return x && (!(x&(x-1))); 
}
int32_t main(){
    SPEED;
    int n;
    cin >> n;
    int a = 0, b = 0, c = 0, d = 0;
    while(n--){
        string s;
        cin >> s;
        if(s == "AC") a++;
        if(s == "WA") b++;
        if(s == "TLE") c++;
        if(s == "RE") d++;
    }
    cout << "AC x " << a << endl;
    cout << "WA x " << b << endl;
    cout << "TLE x " << c << endl;
    cout << "RE x " << d << endl;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

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

    int N, M; cin >> N >> M;
    int maxX = 0; int minY = 1000;
    cin >> maxX >> minY;

    F0R(i, N) {
        int a; cin >> a; maxX = max(maxX, a);
    }

    F0R(i, M) {
        int a; cin >> a; minY = min(minY, a);
    }

    cout << (maxX < minY ? "No War" : "War") << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 256
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, a, b = ns()

    h = [ni() for _ in range(n)]

    upper = 10 ** 9
    lower = 0

    while upper - lower > 1:
        mid = (upper + lower) // 2
        cnt = 0
        for hi in h:
            cnt += int(math.ceil(max(0, hi - b * mid) / (a - b)))
        if cnt <= mid:
            upper = mid
        else:
            lower = mid
    print(upper)


if __name__ == '__main__':
    main()


Measured memory_bytes: 13264
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
  int x,y;
  cin >> x >> y;
  int m = (y-2*x);
  if((y-2*x) % 2 != 0) NO;
  else if(0 <= (m/2) && m/2 <= x) YES;
  else NO;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    vector<int> cs(60, 0); // 立っているビットの個数を記録する
    for (int i = 0; i < n; i++)
    {
        ll a;
        cin >> a;
        bitset<60> bs(a);
        for (int j = 0; j < 60; j++)
        {
            if (bs.test(j))
            {
                ++cs[j];
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < 60; i++)
    {
        ll tmp = pow(2, i);
        tmp %= MOD;
        tmp *= cs[i];
        tmp %= MOD;
        tmp *= (n - cs[i]);
        tmp %= MOD;
        ans += tmp;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
};

Measured memory_bytes: 4036
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        ans = 1
        mod = 10 ** 9 + 7
        for i in range(2, N + 1):
            ans = (ans * i) % mod
        print(ans % (10 ** 9 + 7))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Measured memory_bytes: 38384
#include<iostream> //cinなど
#include<string> //文字列
#include<algorithm> //sort など
#include<math.h> //paw(冪乗など)
#include<set> // 集合
#include<map> //写像
#include<stdio.h> //printf
#include<stack>

using namespace std;
int main(){
  int A,B;
  cin>>A>>B;
  if(A==1){
    A = A + 13;
  }
  if(B==1){
    B = B + 13;
  }
  if(A>B){
    cout<<"Alice"<<endl;
  }else if(A==B){
    cout<<"Draw"<<endl;
  }else{
    cout<<"Bob"<<endl;
  }
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> //ライブラリ全読み込み
using namespace std; //std:を省略できる

int main(){
    int W,H,x,y,r,isOvered;
    cin >> W >> H >> x >> y >> r;
    x-r>=0 && y-r>=0 && x+r<=W && y+r<=H ? cout <<"Yes"<< endl:cout <<"No"<< endl;
    return 0;
}


Measured memory_bytes: 3116
#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    hn = [int(input()) for i in range(n)]
    hn = sorted(hn)
    mi = 9999999999
    for i in range(n - k + 1):
        di = hn[i + k - 1] - hn[i]
        mi = min(di, mi)
    print(mi)

main()


Measured memory_bytes: 8280
using namespace std;

#include <iostream>
#include <cmath>
int main(
){
    int     N = 0;
    int     M = 0;
    std::cin >> N >> M;
    int     A[N] = {0};
    int     n = 0;
    int     Sum = 0;
    for(n = 0; n<N; n++){
        std::cin >> A[n];
        Sum +=A[n];
    }
    int Cnt = 0;
    double  Line = (double)Sum/(4*M);
    for(n = 0; n< N; n++){
        if(A[n] < (double)Sum/(4*M)){
            Cnt ++;
        }
    }
    Cnt = N - Cnt;
    // std::cout << Cnt << " " << M << " " << Sum << std::endl;
    std::string ans;
    if(M <= Cnt){
        ans = "Yes";
    }else{
        ans = "No";
    }
    std::cout << ans << std::endl;
    return 0;
    
}


Measured memory_bytes: 256
n, k = map(int, input().split())

count = 0
for b in range(k+1, n+1):
    candidate = (n // b) * (b - k)
    mod = n % b
    if mod >= k:
        add = mod - k + 1
        if k == 0:
            add -= 1
        candidate += add
    count += candidate

print(count)

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

int main()
{
  int a, b, c, x;
  cin >> a >> b >> c >> x;
  int res = 0, total = 0;
  for (int i = 0; i <= a; i++)
  {
    for (int j = 0; j <= b; j++)
    {
      for (int k = 0; k <= c; k++)
      {
        total = 500 * i + 100 * j + 50 * k;
        if (total == x)
          res++;
      }
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
/// author: Mr.Hakimov

#include <bits/stdc++.h>
#include <chrono>

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define Pb pop_back
#define Pf pop_front
#define all(x) (x).begin(), (x).end()
#define fin(s) freopen(s, "r", stdin);
#define fout(s) freopen(s, "w", stdout);

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

typedef long long ll;
typedef long double ld;

int TN = 1;

void solve() {
	int n;
	cin >> n;
	
	cout << n / 2 + (n % 2 != 0);
}

int main() {
    auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    /// =========================================
    /// fin("input.txt"); fout("output.txt");
    /// fin("file.in"); fout("file.out");
    /// cin >> TN;
    /// =========================================

    while (TN--) {
        solve();
    }

    auto finish = chrono::steady_clock::now();
    auto elapsed_ms = chrono::duration_cast<chrono::milliseconds>(finish - start);
    cerr << endl << "Time: " << elapsed_ms.count() << " ms\n";

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

#define MAX_N 100100
#define MAX_LOG_N 20
int N, root;
vector<int> g[MAX_N];
int depth[MAX_N];
int par[MAX_N][MAX_LOG_N];

void dfs(int v, int p, int d)
{
	par[v][0] = p;
	depth[v] = d;
	for (int i = 0; i < g[v].size(); i++)
	{
		if (g[v][i] == p)continue;
		dfs(g[v][i], v, d + 1);
	}
}

void fill_table()
{
	for (int i = 0; i < 19; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (par[j][i] == -1)par[j][i + 1] = -1;
			else par[j][i + 1] = par[par[j][i]][i];
		}
	}
}

int lca(int u, int v)
{
	if (depth[u] > depth[v])swap(u, v);
	for (int i = 19; i >= 0; i--)
	{
		if (((depth[v] - depth[u]) >> i) & 1)v = par[v][i];
	}
	if (u == v)return u;
	for (int i = 19; i >= 0; i--)
	{
		if (par[u][i] != par[v][i])
		{
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

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

	rep(i, N) {
		int k;
		cin >> k;
		rep(j, k) {
			int c;
			cin >> c;
			g[i].push_back(c);
		}
	}
	root = 0;
	dfs(root, -1, 0);
	fill_table();

	cin >> q;
	rep(i, q) {
		int u, v;
		cin >> u >> v;
		cout << lca(u, v) << endl;
	}
	return 0;
}

Measured memory_bytes: 21372
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main() {
	char a[N + 1];
	f(i, N + 1)a[i] = 0;
	int n, k;
	int x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%s", a);
	if (a[0] == a[1])v = false;
	if (a[1] == a[2])v = false;
	if (a[2] == a[3])v = false;
	if (v)printf("Good\n");
	else printf("Bad\n");


	return 0;
}

Measured memory_bytes: 384