akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

int n;
set< pair<ll, ll> > vis;
map< pair<ll, ll>, int> F;

int main(){
	ri(n);
	int ans = 1;
	int zeroes = 0;
	for(int i = 1; i <= n; i++){
		ll x, y;
		rll2(x, y);
		if(x < 0){
			x = -x;
			y = -y;
		}
		if(x == 0){
			if(y) y = 1;
		}
		if(y == 0){
			if(x) x = 1;
		}
		ll mcd = gcd(abs(x), abs(y));
		if(mcd){
			x /= mcd;
			y /= mcd;
		}
		if(mp(x, y) == mp(0LL, 0LL)){
			zeroes += 1;
		}
		else{
			F[mp(x, y)] += 1;
		}
	}
	for(auto e : F){
		ll x = e.first.first;
		ll y = e.first.second;
		if(vis.count(e.first)) continue;
		vis.emplace(e.first);
		ll nx = -y;
		ll ny = x;
		if(nx < 0){
			nx = -nx;
			ny = -ny;
		}
		if(nx == 0){
			if(ny) ny = 1;
		}
		if(ny == 0){
			if(nx) nx = 1;
		}
		int cur = add(pow_mod(2, e.second), add(pow_mod(2, F[mp(nx, ny)]), MOD - 1));
		ans = mul(ans, cur);
		vis.emplace(mp(nx, ny));
	}
	ans = add(ans, zeroes);
	ans = add(ans, MOD - 1);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 53556
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
const int mod = 1000000007;

int main() {
  int N;
  cin>>N;
  vector<int>A(N+2);
  int sum=0;
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  for(int i=1;i<=N+1;i++){
    sum+=abs(A[i]-A[i-1]);
  }
  for(int i=1;i<=N;i++){
    cout<<sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1])<<endl;
  }

  return 0;
}

Measured memory_bytes: 3792
import java.util.Scanner;

class Main{

    public static void main(String[] args){
    
      Scanner sc =new Scanner(System.in);

      while(true){
      int H=sc.nextInt();
      int W=sc.nextInt();
      
      if(H==0&&W==0) break;
          
          
      if(H<=2||W<=2) 
      for(int i=0;i<H;i++){
       for(int j=0;j<W;j++)
        System.out.print("#");
        System.out.print("\n");
      }
      
      else{
      for(int i=0;i<W;i++)
      System.out.print("#");
      System.out.print("\n");
      for(int i=1;i<H-1;i++){
      System.out.print("#");
      for(int j=1;j<W-1;j++)
      System.out.print(".");
      System.out.print("#");
      System.out.print("\n");
      }
      for(int i=0;i<W;i++)
      System.out.print("#");
      System.out.print("\n");
      }
      
      System.out.print("\n");
     
}
}

}


Measured memory_bytes: 37364
#include <iostream>

using namespace std;

int main(){
    
    int n, v[200005], ans[200005] = {0};
   
    cin >> n;

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

    for(int i = 1; i <= n; i++){
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 5160
#include <cstdio>
#include <vector>
#include <algorithm>

typedef struct Node {
    int id;
    int parent;
    int sibling;
    int child[2];
    int depth;
    int degree;
    int height;
} Node;

int count_depth_ret_height_iter(std::vector<Node> &nodes, int id, int depth){
    nodes[id].depth = depth;
    int h[2] = {0, 0};
    if(nodes[id].child[0] != -1) h[0] = count_depth_ret_height_iter(nodes, nodes[id].child[0], nodes[id].depth + 1);
    if(nodes[id].child[1] != -1) h[1] = count_depth_ret_height_iter(nodes, nodes[id].child[1], nodes[id].depth + 1);
    nodes[id].height = std::max(h[0], h[1]);
    return nodes[id].height + 1;
}

void count_depth_and_height(std::vector<Node> &nodes){
    int id = 0;
    for(auto &x: nodes){
        if(x.parent == -1){
            id = x.id;
            break;
        }
    }
    count_depth_ret_height_iter(nodes, id, 0);
}

int main(){
    int n;
    std::scanf("%d", &n);
    std::vector<Node> nodes;
    for(int i = 0; i < n; ++i){
        Node node;
        node.id = i;
        node.parent = - 1;
        node.sibling = - 1;
        node.child[0] = - 1;
        node.child[1] = - 1;
        node.depth = 0;
        node.degree = 0;
        node.height = 0;
        nodes.push_back(node);
    }

    for(int i = 0; i < n; ++i){
        int id;
        std::scanf("%d", &id);
        int c[2];
        std::scanf("%d", &c[0]);
        std::scanf("%d", &c[1]);
        nodes[id].id = id;
        nodes[id].child[0] = c[0];
	nodes[id].child[1] = c[1];
        if(c[0] != -1){
            nodes[c[0]].parent = id;
            nodes[c[0]].sibling = c[1];
            nodes[id].degree++;
        }
        if(c[1] != -1){
            nodes[c[1]].parent = id;
            nodes[c[1]].sibling = c[0];
            nodes[id].degree++;
	}
    }

    count_depth_and_height(nodes);

    for(int i = 0; i < n; ++i){
        std::printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",
                    nodes[i].id, nodes[i].parent, nodes[i].sibling,
                    nodes[i].degree, nodes[i].depth, nodes[i].height);
	if(nodes[i].depth == 0) std::printf("root\n");
        else if(nodes[i].height == 0) std::printf("leaf\n");
        else std::printf("internal node\n");
    }

    return 0;
}


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

import sys, math
sys.setrecursionlimit(300000)


def solve(A: int, B: int, H: int, M: int):
    m = 360 * (M / 60)
    h = 30 * H + 30 / 60 * M
    a = (m - h) % 360
    #b2=c2+a2−2cacosB …(B)
    ret = math.sqrt(A ** 2 + B ** 2 - 2 * A * B * math.cos(a / 180 * math.pi))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    H = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(A, B, H, M)

if __name__ == '__main__':
    main()


Measured memory_bytes: 62584
n = int(input())
i = 0
while i * (i+1) <= 2 * n:
  i += 1
  
num = []

for a in range(1,i+1):
  if a != i * (i+1) / 2 - n:
    num.append(a)
    
for _ in  num:
  print(_)
  

Measured memory_bytes: 3572
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def cookie(p1,p2):
	if p1 % 2 == 1:
		p1 -= 1
	p1 /= 2
	p2 += p1
	return p1,p2

a,b,k = map(int, input().split())
for i in range(k):
	if i % 2 == 0:
		a,b = cookie(a,b)
	else:
		b,a = cookie(b,a)
print("{} {}".format(int(a),int(b)))


Measured memory_bytes: 3060
def main():
    import sys
    import copy
    input = sys.stdin.readline
 
    n = int(input())
    a = [int(input()) for i in range(n)]
    b = []
    
    b = sorted(a)
    
    for i in a:
        if(i == b[-1]):
            print(b[-2])
        else:
            print(b[-1])
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 60496
#include<stdio.h>

#define MAX 251

int parent(int i){
  return i / 2;
}

int left(int i){
  return 2 * i;
}

int right(int i){
  return 2 * i + 1;
} 

int main(){
  int i,l,c[MAX];

  scanf("%d",&l);
  for(i = 1; i <= l; i++){
    scanf("%d",&c[i]);
  }

  for(i = 1; i <= l; i++){
    printf("node %d: key = %d, ",i,c[i]);
    if(i != 1)
      printf("parent key = %d, ",c[parent(i)]);
    if(l >= left(i))
      printf("left key = %d, ",c[left(i)]);
    if(l >= right(i))
      printf("right key = %d, ",c[right(i)]);
    printf("\n");
  }
  
  return 0;
}



Measured memory_bytes: 2112
n, m, c = (int(i) for i in input().split())
b_list = [int(i) for i in input().split()]
count = 0

for _ in range(n):
  a_list = [int(i) for i in input().split()]
  inner_product = 0
  for j in range(m):
    inner_product += a_list[j] * b_list[j]
  if inner_product + c > 0:
    count += 1

print(count)                                                                                                             

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
//#include <unordered_set>
#define mkp make_pair
#define err cout<<"here"<<endl
using namespace std;
const double EPS=1e-12;
typedef long long lon;
typedef unsigned long long ull;
typedef set<int>::iterator IT;
const lon SZ=100010,SSZ=30,APB=52,mod=97,one=1;
const lon INF=0x7FFFFFFF;
lon n,m;
struct nd{
	lon to,wt;
	nd(lon a=0,lon b=0):to(a),wt(b){}
};

void init()
{
	cin>>n>>m;
	string str;
	cin>>str;
	--m;
	if(str[m]>='A'&&str[m]<='Z')
	{
		str[m]+=32;
	}
	cout<<str<<endl;
}


void work()
{
	
}

void release()
{
	
}

int main()
{
	std::ios::sync_with_stdio(0);
	//freopen("d:\\1.txt","r",stdin);
	int casenum;
	//cin>>casenum;
	//cout<<casenum<<endl;
	//for(int time=1;time<=casenum;++time)
	//for(int time=1;cin>>n>>m;++time)
	{
		//cout<<"Case #"<<time<<": ";
		init();
		work();
		release();
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)

int main()
{
	ll n,m,ans=0;
	string s;

	cin >> n >> m;

	forll(i, 1, n)
		ans += i;

	forll(i, 1, m)
		ans += i;

	cout << ans << endl;
}

Measured memory_bytes: 256
x1,y1,x2,y2 = gets.chomp.split(" ").map(&:to_i)
xMove = x2 - x1
yMove = y2 - y1
x3 = x2 - yMove
y3 = y2 + xMove
x4 = x3 - xMove
y4 = y3 - yMove
puts "#{x3} #{y3} #{x4} #{y4}"

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int mod = 10000;
int n, k;
int p[111] = {0};
 
int dp[111][2][4];
 
int dfs(int i = 1, bool ff = false, int f = 0)
{
  int &ans = dp[i][ff][f];
 
  if (ans != -1) return ans;
  if (i == n + 1) {
    return 1;
  }
   
  if (p[i] != 0){
    if (ff && f == p[i]) return 0;
    ans = dfs(i + 1, f == p[i], p[i]);
    return ans %= mod;
  }
 
  ans = 0;
  for (int j = 1; j < 4; j++){
    if (ff && f == j) continue;
    ans += dfs(i + 1, f == j, j);
  }
 
  return ans %= mod;
}
 
main()
{
  memset(dp, -1, sizeof(dp));
 
  cin >> n >> k;
  for (int i = 0; i < k; i++){
    int a, b;
    cin >> a >> b;
    p[a] = b;
  }
 
  cout << dfs() << endl;
}

Measured memory_bytes: 3080
import sys
from functools import lru_cache
sys.setrecursionlimit(500000)
mod = 10**9+7
@lru_cache(maxsize=None)
def partition(n, k):  # 自然数 n を k 個の自然数の和で表す場合の数
    if n < 0 or n < k:
        return 0
    elif k == 1 or n == k:
        return 1
    else:
        return (partition(n-k, k) + partition(n-1, k-1)) % mod  # 1 を使わない場合と使う場合の和
n, k = map(int, input().split())
print(partition(n+k, k))



Measured memory_bytes: 151008
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main(){
    int p,r,t;
    cin >> p >> r >> t;
    vector<int> resources(r);
    for(int i=0; i<r; i++){
        cin >> resources[i];
    }
    vector<vector<int>> needs(p, vector<int>(r));
    for(int i=0; i<p; i++){
        for(int j=0; j<r; j++){
            cin >> needs[i][j];
        }
    }
    auto needs_def = needs;
    vector<pair<int,int>> log(t);
    for(int i=0; i<t; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        log[i] = {a, b};
    }

    int ok=-1, ng=t;
    int prevmid=-1;
    while(ok+1 < ng){
        int mid = (ok+ng)/2;
        for(int i=prevmid; i<mid; i++){
            needs[log[i+1].first][log[i+1].second]--;
            resources[log[i+1].second]--;
        }
        for(int i=prevmid; i>mid; i--){
            needs[log[i].first][log[i].second]++;
            resources[log[i].second]++;
        }
        prevmid = mid;

        auto rsc = resources;
        vector<bool> terminated(p, false);
        int endnum = 0;
        for(int i=0; i<p; i++){
            if(*max_element(needs[i].begin(), needs[i].end()) == 0){
                terminated[i] = true;
                for(int j=0; j<r; j++){
                    rsc[j] += needs_def[i][j];
                }
                endnum++;
            }
        }
        while(endnum < p){
            bool deadlock = true;
            for(int i=0; i<p; i++){
                if(terminated[i]) continue;
                bool ok = true;
                for(int j=0; j<r; j++){
                    if(rsc[j] < needs[i][j]) ok = false;
                }
                if(ok){
                    terminated[i] = true;
                    deadlock = false;
                    for(int j=0; j<r; j++){
                        rsc[j] += needs_def[i][j] -needs[i][j];
                    }
                    endnum++;
                }
            }
            if(deadlock) break;
        }
        if(endnum == p){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    if(ng == t){
        cout << -1 << endl;
    }else{
        cout << ng+1 << endl;
    }
    return 0;
}



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

void solve(long long N, vector<long long> a){
  long long sunuke = 0;
  long long araiguma = 0;
  vector<long long> sum;
  vector<long long> sumr;
  long long sumv = 0;
  long long sumvr = 0;
	for (long long i = 0; i < N - 1; i++) {
    sumv += a[i];
    sumvr += a[N - i - 1];
    sum.push_back(sumv);
    sumr.push_back(sumvr);
  }
  long long ans = 1LL << 60;;

	for (long long i = 0; i < N - 1; i++) {
    sunuke = sum[i];
    araiguma = sumr[N - i - 2];
    // cout<<sunuke<<","<<araiguma<< "|" <<abs(sunuke - araiguma) << endl;
    if (abs(sunuke - araiguma) < ans) {
      ans = abs(sunuke - araiguma);
    }
  }
  cout << ans << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> a(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, a);
	return 0;
}



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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;

int main()
{
    int W, H, x, y, r;

    cin >> W >> H >> x >> y >> r;

    if (x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H)
        OP("Yes")
    else
        OP("No")

    return 0;
}


Measured memory_bytes: 3100
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc119d
{
    class Program
    {
        static void Main(string[] args)
        {
            var NQ = ReadIntList();
            var N = NQ[0];
            var Q = NQ[1];
            var S = Console.ReadLine();
            //S.Insert(0, "-");
            var ans = new int[Q];
            var l = new int[Q];
            var r = new int[Q];
            var dp = new int[N + 1];
            dp[0] = 0;
            for (int i = 0; i < Q; i++)
            {
                var lr = ReadIntList();
                l[i] = lr[0];
                r[i] = lr[1];
            }
            for (int j = 1; j < N; j++)
            {
                if (S[j-1] == 'A' && S[j] == 'C')
                {
                    dp[j] = dp[j-1] + 1;
                }
                else
                {
                    dp[j] = dp[j-1];
                }
            }
            for (int i = 0; i < Q; i++)
            {
                Console.WriteLine(dp[r[i]-1] - dp[l[i]-1]);
            }
#if DEBUG
            Console.ReadKey();
#endif
        }

        private static List<int> ReadIntList() => Console.ReadLine().Split().Select(int.Parse).ToList();
    }
}


Measured memory_bytes: 18024
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner itr = new Scanner(System.in);
        int N = itr.nextInt();
        int K = itr.nextInt();
        int[] stone = new int[N];

        for (int i = 0; i < N; i++) {
            stone[i] = itr.nextInt();
        }

        int[] dp = new int[N];
        Arrays.fill(dp, Integer.MAX_VALUE);

        int res = backtrack(dp, N - 1, N, K, stone);

        System.out.println(res);
    }

    public static int backtrack(int[] dp, int index, int N, int K, int[] stone) {
        if (index <= 0) return 0;

        if (dp[index] != Integer.MAX_VALUE)
            return dp[index];

        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= K; i++) {
            if (index - i < 0) break;
            min = Math.min(min, backtrack(dp, index - i, N, K, stone) + Math.abs(stone[index] - stone[index - i]));
        }

        dp[index] = min;
        return dp[index];
    }
}


Measured memory_bytes: 62352
import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        //コード
        Scanner scanner = new Scanner(System.in);
        int N = Integer.valueOf(scanner.next());
        int M = Integer.valueOf(scanner.next());
        Integer WA_COUNT = 0;
        Integer AC_COUNT = 0;
        boolean[] AC = new boolean[N + 1];
        Integer[] WA = new Integer[N + 1];
        Arrays.fill(WA, 0);

        for (int i = 0; i < M; i++) {
            Integer P = Integer.parseInt(scanner.next());
            String S = scanner.next();

            if (AC[P]) continue;
            // まだACしていない問題でWAの場合は数える
            if ("WA".equals(S)) {
                WA[P]++;
            } else {
                // ACしたとき、この問題でのWAをペナルティとして数える
                AC[P] = true;
                AC_COUNT++;
                WA_COUNT += WA[P];
            }

        }
        System.out.println(AC_COUNT + " " + WA_COUNT);
    }
}


Measured memory_bytes: 57824
import sys

sys.setrecursionlimit(10**9)

n,m,k = map(int,input().split())

a = []
b = []
c = []
d = []
for _ in range(m):
	tmp = list(map(int,input().split()))
	a.append(tmp[0]-1)
	b.append(tmp[1]-1)
for _ in range(k):
	tmp = list(map(int,input().split()))
	c.append(tmp[0]-1)
	d.append(tmp[1]-1)

class UnionFind():
    def __init__(self, n):
        self.n = n
        #self.parents = -1 : 親が自分で子も自分(独立)
        #self.parents = n(>0) : 親が自分でなく頂点n
        #self.parents = n(<0) : 親が自分で、子が-n個(自分含める)
        self.parents = [-1] * n
    #自分の親を求める
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    #xとyを同じ親に属させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    #同じ親だったらTrue
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(n)
ans = []

for i in range(m):
	uf.union(a[i],b[i])

for i in range(n):
	ans.append(uf.size(i)-1) #-1してるのは、自分自身を除くため

for i in range(m):
	if uf.find(a[i]) == uf.find(b[i]):
		ans[a[i]] -= 1
		ans[b[i]] -= 1

for i in range(k):
	if uf.find(c[i]) == uf.find(d[i]):
		ans[c[i]] -= 1
		ans[d[i]] -= 1

for i in range(n):
	print(ans[i],end=" ")


Measured memory_bytes: 24484
#include <iostream>
#include <algorithm>
#include <vector>
#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;
int main()
{
  int n;cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int res=0;
  rep(i,n-2){
    vector<int> tmp(3);
    int a = p[i+1];
    rep(j,3) tmp[j] = p[i+j];
    sort(tmp.begin(), tmp.end());
    if(a==tmp[1]) res++;
  }
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
using namespace std;
int ans1,ans2;
int main(){
    long long n,num=1;
	cin>>n;
	for(long long i=n;i;i/=10){
      ans1+=i%10;
      num*=10;
    }
	num/=10;
	for(long long i=n/num*num-1;i;i/=10) ans2+=i%10;
    cout<<max(ans1,ans2)<<endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
F = [0,0,0]
for a in A:
    if a%4==0: F[2]+=1
    elif a%2==0: F[1]+=1
    else: F[0]+=1
ans = "Yes"
if F[0]==F[2]+1 and F[1]>0: ans="No"
if F[0]>F[2]+1: ans="No"
print(ans)

Measured memory_bytes: 15020
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
const int maxn = 5050;
using namespace std;
typedef long long ll;
ll dp[maxn][maxn];
int main()
{
	ll mod = 998244353;
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	dp[a][b]=1;
	for(int i=a+1;i<=c;i++)
	dp[i][b]=dp[i-1][b]*b%mod;
	for(int j=b+1;j<=d;j++)
	dp[a][j]=dp[a][j-1]*a%mod;
	for(int i=a+1;i<=c;i++){
		for(int j=b+1;j<=d;j++){
			ll q=dp[i-1][j]*j%mod;
			ll w=dp[i][j-1]*i%mod;
			ll e=dp[i-1][j-1]*(i-1)%mod;
			e=e*(j-1)%mod;
			if(q+w-e<0)
			dp[i][j]=(q+w+mod-e)%mod;
			else dp[i][j]=(q+w-e)%mod;
		}
	}
	/*for(int i=a;i<=c;i++){
		for(int j=b;j<=d;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	cout<<dp[c][d];
	return 0;
}

Measured memory_bytes: 85872
n=int(input())
s=[];ans=0
for i in range(n):
  a=int(input())
  if a%10!=0:
    s.append(a)
  ans+=a
s.sort()
if ans%10==0:
  if s:
    ans-=s[0]
  else:
    ans=0
print(ans)

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    string a, b;
    cin >> a >> b;
    ll N = (ll)stoi(a+b);

    bool f = false;
    REP(i,1,320) {
        if(i*i == N) {
            f = true;
            break;
        }
    }

    if(f) PR("Yes");
    else PR("No");

    return 0;
}

/*



*/

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << min(c, b / a) << endl;
}


Measured memory_bytes: 256
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
inf = 10 ** 9

def dfs(cur, a, b, c):
  if cur == N:
    if min(a, b, c) > 0:
      return abs(a - A) + abs(b - B) + abs(c - C) - 30 
    else:
      return inf
  else:  
    ret0 = dfs(cur + 1, a, b, c) 
    ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))


Measured memory_bytes: 3064
from collections import deque

H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
c = [[-1 for _ in range(W)] for _ in range(H)]

black=0
for tate in s:
  for yoko in tate:
    if yoko=="#":
      black += 1

def search(y,x,H,W,c,i):
  child=[]      
  if y<H-1:
    if s[y+1][x]=="." and c[y+1][x]==-1:
      c[y+1][x]=i
      child.append([y+1,x])
  if 0<y:
    if s[y-1][x]=="." and c[y-1][x]==-1:
      c[y-1][x]=i
      child.append([y-1,x])
  if 0<x:
    if s[y][x-1]=="." and c[y][x-1]==-1:
      c[y][x-1]=i
      child.append([y,x-1])
  if x<W-1:
    if s[y][x+1]=="." and c[y][x+1]==-1:
      c[y][x+1]=i
      child.append([y,x+1])
  return child

def dfs(y,x,c):
  visited=[[y,x]]
  c[y][x]=0
  i=1
  
  while visited:
    tmp=[]
    for a in visited:
      p=search(a[0],a[1],H,W,c,i)  #listが戻る
      tmp += p
    visited=tmp
    i += 1

dfs(0,0,c)
a=c[-1][-1]
if a==-1:
  print(-1)
else:
  print(H*W-black-a-1)

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

int main()
{
    int X;
    cin >> X;

    int a1;
    int a2;
    int b1;
    int b2;
    int c1;
    int c2;
    int d1;
    int d2;
    int e1;
    int e2;

    int happy1;
    int happy2;
    int allhappy;
    
    a1 = X/500;
    happy1 = a1 * 1000;
    a2 = X%500;

    e1 = a2/5;
    happy2 = e1 * 5;

    allhappy = happy1 + happy2;

    cout << allhappy << endl;

    return 0;
}
//Ctrl+Shift+Bでコンパイルと実行を行ってデバッグすること

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

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

	string ans = "hon";
	int amari = n % 10;
	if (amari == 3) {
		ans = "bon";
	} else if (amari == 0 || amari == 1 || amari == 6 || amari == 8) {
		ans = "pon";
	}

	cout << ans << endl;
}


Measured memory_bytes: 3636
from functools import partial
from itertools import islice, product


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(s):
    n, m, *xyz = map(int, s.split())
    return max([
        sum(
            sorted([x * sign_x + y * sign_y + z * sign_z for x, y, z in chunked(xyz, 3)],
                   reverse=True)[:m]) for sign_x, sign_y, sign_z in product([1, -1], repeat=3)
    ])


if __name__ == "__main__":
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 3916
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;



int main(){
  int X,A; cin >> X >> A;
  if(X < A) cout << 0 << endl;
  else cout << 10 << endl;
}
  


  


Measured memory_bytes: 256
#include <climits>
#include <cstring>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define f first
#define s second

#define MM INT_MAX/5
#define MIM INT_MIN/2

int di[] = { 1,-1,0,0 };
int dj[] = { 0,0,1,-1 };

#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 v vector
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize

#define MAX 3001
int dp[MAX][MAX];

int main()
{
	string A;
	string B;
	cin >> A >> B;

	//Calculating it
	for (int i = 0; i < A.size(); i++) {
		for (int j = 0; j < B.size(); j++) {
			if (A[i] == B[j])
				dp[i + 1][j + 1] = dp[i][j] + 1;
			else
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
		}
	}

	//Printing it out
	string lcs = "";
	int count = MAX - 1;
	int i = A.size()-1;
	int j = B.size()-1;
	while (i != -1 && j != -1)
	{
		if (A[i] == B[j])
		{
			lcs.push_back(A[i]);
			i--; j--;
		}
		else
		{
			if (dp[i][j + 1] > dp[i + 1][j])
				i--;
			else
				j--;
		}
	}
	reverse(lcs.begin(), lcs.end());
	cout << lcs;
}


Measured memory_bytes: 35456
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <limits>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include "math.h"
#include "assert.h"

using namespace std;

int inf = std::numeric_limits<int>().max();

#define BUFF ios::sync_with_stdio(false)
#define epsilon 1e-07
#define pi 2 * acos(0.0);
#define mod 1000000007   // 1e9+7
#define ll long long
#define cerr if(false)cerr
#define watch(x) cerr << #x << " = " << x << endl;

/*

	Segment Tree
		- utilizada para consultar e atualizar valores em intervalos de v[0..n).
		- operações: 
			- build - O(n lg n).
			- search - O(lg n) - consulta o valor mínimo contido no intervalo [0..n-1].
			- add - O(lg n) - atualiza o valor de v(i).

			- soma (nulo = 0), mínimo (nulo = inf), etc.

*/

void build_segment_tree(vector<int> & v, vector<int> & st, int nulo) {
	int n = v.size();
	int k = 1;

	while (pow(2, k) < n) k++;
	int ns = pow(2,k);
	st.resize(2*ns);

	for(int i=ns; i<2*ns; i++) {
		if (i - ns < n) st[i] = v[i-ns];
		else st[i] = nulo;
	}
 
	int start = ns;
	int delta = 2*ns;
	for(int pot=k; pot>=0; pot--) {
		for(int i=start; i<delta; i+=2) {
			st[i/2] = max(st[i], st[i+1]);
		}
		delta = start;
		start /= 2;
	}

}

int search(int i, int j, vector<int> & st) {
	int n = st.size() / 2;
	i += n;
	j += n;
	bool i_last = false;
	bool j_last = false;
	int t = 0;
	while (i <= j) {
		if (!i_last and (i % 2 == 1 or j_last)) {
			t = max(t, st[i]);
			i++;
		}
		if (!j_last and (j % 2 == 0 or i_last)) {
			t = max(t, st[j]);
			j--;
		}
		if (!i_last and i % 2 == 1) {
			i_last = true;
		}
		if (!j_last and j % 2 == 0) {
			j_last = true;
		}
		i = i / 2;
		j = j / 2;
	}
	return t;
}

void add(int x, int i, vector<int> & st) {
	int n = st.size() / 2;
	i += n;
	st[i] = x;
	int t = st[i];
	while (i >= 1) {
		st[i] = max(st[i], t);
		i /= 2;
	}
}

void show(vector<int> & st) {
	cout << st.size() << ": ";
	for(int i=0; i<st.size(); i++) {
		cout << st[i] << " ";
	}
	cout << endl;
}

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

	vector<int> v(n, 0);
	for(int i=0; i<n; i++) {
		cin >> v[i];
	}

	vector<int> w(300001, 0);
	vector<int> st;
	build_segment_tree(w, st, 0);

	for(int i=0; i<n; i++) {
		int a, b;
		a = max(0, v[i]-k);
		b = min(300001-1, v[i]+k);
		int t = search(a, b, st);
		add(t+1, v[i], st);
//		cout << v[i] << " ab: " << a << " " << b << ": " << search(a, b, st) << endl;
	}

//	add(10, 4, st);
//	add(-9, 1, st);
//	show(st);
	
	cout << search(0, 300001-1, st) << endl;

}


Measured memory_bytes: 9224
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//ll a[Max];
ll n,ans;
int A[20];
int x[20][20];
int y[20][20];
int count(int x){
	if(x==0)return 0;
	return count(x>>1)+(x&1);
}
void solve(){
	cin>>n;
	rep(i,1,n+1){
		cin>>A[i];
		rep(j,1,A[i]+1){
			cin>>x[i][j]>>y[i][j];
		}
	}
	for(int bits=1;bits<(1<<n);bits++){
		int ok = 1;
		for(int i=1;i<=n;i++){
			if(bits&(1<<(i-1))){
				for(int j=1;j<=A[i];j++){
					if((bits&(1<<(x[i][j]-1))?1:0)^y[i][j]){
						ok = 0;
					}
				//	if(bits>>(x[i][j]-1)&1^y[i][j])ok = 0;
				}
			}
		}
		if(ok)ans = max(ans,(ll)count(bits));
	}
	cout<<ans;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





Measured memory_bytes: 256
from bisect import bisect_left

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0
for i in range(q):
    l = 0
    r = n
    while r - l > 1:
        m = (r + l) // 2
        if S[m] >= T[i]:
            r = m
        else:
            l = m
    
    if l < n and S[l] == T[i]:
        ans += 1
    elif r < n and S[r] == T[i]:
        ans += 1
print(ans)


Measured memory_bytes: 16740
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

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

	int n;
	cin >> n;
	int LEN = 0;
	int S = 0;
	for (int i = 0; i < n; i++) {
		int d, c;
		cin >> d >> c;
		LEN += c;
		S += d * c;
	}
	int VAL = (9 * LEN + S - 1);
	cout << VAL / 9 - 1 << endl;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main(){
    cin>>N>>A>>B;
    if((B - A)%2 == 0){
        cout<<(B - A)/2<<endl;
    }else{
        cout<<min(((N - A) + (N - B) + 1)/2, ((A - 1) + (B -1) + 1)/2)<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>

using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()
// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class X> void DEBUG(X d, T e){if(DEBUG_OUT == false)return;std::cout <<d<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

  // vector<vector<vector<int> > > DP =  vector<vector<vector<int> > >(100001,vector<vector<int> >(2,vector<int>(2,0)));
void solve(void)
{
    int N,M;
    cin>>N>>M;
    cout<<(N+M)*(N+M-1)/2 -M*N<<endl;
    return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	int a, b;
	cin >> a >> b;

	println(6 - a - b);
}

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

ll n;

void input() {
    cin >> n;
}

void solve() {
    if(n % 2 == 0 ) {
        cout << ( n - 2) / 2 << endl;
    } else {
        cout << ( n - 1 ) / 2 << endl;
    }
}



int main() {
    input();
    solve();

}


Measured memory_bytes: 256
n=int(input())
s=list(map(int,input().split()))
q=int(input())
t=list(map(int,input().split()))
cnt=0

for i in range(q):
    l=0
    r=n
    while l<r:
        m=int((l+r)/2)
        if s[m]==t[i]:
            cnt+=1
            break
        elif t[i]<s[m]:
            r=m
        else:
            l=m+1
print(cnt)


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

#define lol long long
#define gcd(x,y) __gcd(x,y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed fixed<<setprecision(14)
using namespace std;
using pii=pair<int,int>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline lol abs(A &a) { return (a < 0 ? -a : a); }
const lol Mod=(1e9)+7;
const lol mod=998244353;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
lol n,m,k,r;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >>n>>k>>r;
  for(int i=k;i<=r;i++){
    if(i%n==0){
      cout <<"OK\n";
      return 0;
    }
  }
  cout <<"NG\n";
  return (0);
}


Measured memory_bytes: 3612
#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	bool find;
	int res,n,l,r;
	while (cin >> n >> l >> r||n,l,r) {
		vector<int> A(n);
		for (int i = 0; i < n; ++i) {
			cin >> A[i];
		}
		res = 0;
		for (int num = l; num < r+1; ++num) {
			find = false;
			for (int i = 0; !find && i < n; ++i) {
				if (num%A[i] == 0) {
					find = true;
					if (i%2 == 0) {
						++res;
					}
				}
			}
			if (!find && n%2 == 0) {
				++res;
			}
		}
		cout << res << endl;
	}
	return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define emp emplace

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int N = 100010;
vector<int> g[N];
int n;
int pd[N];

int solve(int u)
{
	if (pd[u] != -1)
		return pd[u];
	
	pd[u] = 0;
	for (int v : g[u])
		pd[u] = max(pd[u], 1 + solve(v));
	return pd[u];
}

int main()
{
	int m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		g[u].pb(v);
	}
	int ans = 0;
	memset(pd, -1, sizeof(pd));
	for (int u = 1; u <= n; u++)
		ans = max(ans, solve(u));
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 7424
#include<bits/stdc++.h>
using namespace std;
set<int> go[200005];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        go[x].insert(y);
    }
    for(set<int>::iterator it = go[1].begin();it != go[1].end();it++)
    {
        int num = *it;
        if(go[num].find(n) != go[num].end())
        {
            cout << "POSSIBLE";
            return 0;
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 18944
#include<bits/stdc++.h>
using namespace std;
string s[55];int t[55];
map<string,int> m;
int main(){
	int n;string x;
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>s[i]>>t[i],m[s[i]]=i;
	cin>>x;
	int st=m[x]+1,sum=0;
	for(int i=st;i<=n;++i)
		sum+=t[i];
	cout<<sum;
	return 0;
} 

Measured memory_bytes: 3620
import Data.Array.IO

type Value = Int
type Weight = Int
type Item = (Weight, Value)
type ItemList = [Item]
type Capacity = Int

main :: IO ()
main = do
  input <- getContents
  let nums = map ((\x -> (last x, head x)) . map (read :: String -> Int) . words) . lines $ input
      capacity = fst . head $ nums
      items = tail nums
  memo <- newArray ((0, 0), (capacity, length items)) (0 - 1) :: IO (IOUArray (Int, Int) Int)
  dp (capacity, items) memo
  putStrLn . show . last =<< getElems memo

memoize :: (Capacity, ItemList) -> IOUArray (Int, Int) Int -> IO Int
memoize (c, i) t = do
  v <- readArray t (c, length i)
  if v < 0
    then do
      dp (c, i) t
      return =<< readArray t (c, length i)
    else return v

dp :: (Capacity, ItemList) -> IOUArray (Int, Int) Int -> IO (IOUArray (Int, Int) Int)
dp (c, []) t = do
  writeArray t (c, 0) 0
  return t
dp (c, as@(i:is)) t
  | c < fst i = do
    v <- memoize (c, is) t
    writeArray t (c, length as) v
    return t
  | otherwise = do
    x <- memoize (c, is) t
    y <- memoize (c - fst i, is) t
    writeArray t (c, length as) (max x $ y + snd i)
    return t

Measured memory_bytes: 94884
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int get(int x)
{
	int ans = 0;
	while(x > 0)
	{
		ans += 1;
		x /= 10;
	}
	ans %= 2;
	return ans;
}

int32_t main()
{
	IOS;
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans += get(i);
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <cctype>
using namespace std;
string S;
size_t cur;
int expression();

int digit() {
    //  Digit := '0' | '1' | ... | '9'
    assert(isdigit(S[cur]));    // S[cur] が数字であることを確認
    int n = S[cur] - '0';       // '0' を 0 に変換
    cur = cur + 1;              // 一文字進める
    return n;
}

int number() {
    //  Number := Digit の繰り返し
    int n = digit();
    while (cur < S.size() && isdigit(S[cur])) {     // 次も数字が 1 文字先読み
        n = n * 10 + digit();
    }
    return n;
}

int factor() {
    //  Factor := '(' Expression ')' | Number
    if (S[cur] != '(') return number();
    cur += 1;
    int n = expression();
    assert(S[cur] == ')');
    cur += 1;
    return n;
}

int term() {
    //  Term := Factor { ('*'|'/') Factor }
    int a = factor();
    while (cur < S.size() && (S[cur] == '*' || S[cur] == '/')) {
        char op = S[cur++];
        int b = factor();
        if (op == '*') a *= b; else a /= b;
    }
    return a;
}

int expression() {
    //  Expression := Term { ('+'|'-') Term }
    int a = term();
    while (cur < S.size() && (S[cur] == '+' || S[cur] == '-')) {
        char op = S[cur++];
        int b = term();
        if (op == '+') a += b; else a -= b;
    }
    return a;
}

int parse() { return expression(); }

int main() {
    int n; cin >> n;
    while (n--) {
        cin >> S;
        cur = 0;
        S.resize(S.size() - 1);     // 最後の = を無視
        cout << expression() << endl;
    }
    return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define vi vector<int>
#define pcnt(n) __builtin_popcount(n)
const int MOD = 998244353;
const int INF = 1e18;
const double PI = acos(-1);

int dp[3010][3010];

int pw(int a, int x) {
    if (x == 0) return 1;
    int b = pw(a, x / 2);
    b = (b * b) % MOD;
    if (x % 2)
        return (a * b) % MOD;
    return b;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,A;
    cin >> n >> A;
    vi a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];

  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= A; ++j) {
      (dp[i+1][j] += 2*dp[i][j]) %= MOD;
      if (j >= a[i]) (dp[i+1][j] += dp[i][j-a[i]]) %= MOD;
    }
  }
  cout << dp[n][A]%MOD << endl;
}

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

def main():
    n , k = map( int , input().split() )
    A = [ 0 for i in range(n) ]
    for i in range(k):
        d = int(input())
        a = list( map( int , input().split() ) )
        for j in a:
            A[ j - 1 ] += 1

    ans = 0
    for i in A:
        if i == 0:
            ans += 1

    print(ans)

main()

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

using namespace std;

const int p[3] = {-1, 0, 1};

int n, f[15], t = 0, x = 0;
// t 位数
// x 个数 

void dfs(int dep) {
	if (dep > t) {
		x++;
		if (x == n) {
			for (int i = 1; i <= t; i++)
				cout << f[i];
			cout << endl;
			exit(0);
		}
		return;
	}
	for (int i = 0; i < 3; i++) {
		int y = f[dep - 1] + p[i];
		if (y >= 0 && y < 10) {
			f[dep] = y;
			dfs(dep + 1);
		}
	}
}

int main() {
	cin >> n;
	while (++t) {
		for (int i = 1; i <= 9; i++) {
			f[1] = i;
			dfs(2);
		}
	}
	
	return 0;
}

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

#define what_is(x)    cerr<<#x<<" is "<<x<<"\n";
#define rep(i,a,n)    for(int i=a; i<=n; ++i)
#define rep1(i,a,n)   for(int i=a; i>=n; --i)
#define pb            push_back
#define mp            make_pair
#define int           long long
#define fr            first
#define sc            second
#define vc            vector
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define rall(x)       (x).rbegin(),(x).rend()
#define M             1000000007
#define MM            998244353
#define PI            3.14159265358979
#define INF           1000000000000000

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mii;

int n,m,ans; string str;

int solve(){
    cin>>n>>str;
    if(n%2){
        cout<<"No";
        return 0;
    }
    string s=str.substr(0,n/2),t=str.substr(n/2,n/2);
    if(s==t) cout<<"Yes";
    else cout<<"No";
    return 0;
}

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

Measured memory_bytes: 256