akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <numeric>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

//#define DEBUG

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;
#else
#define PRINT(A)
#endif

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
    ll N; cin >> N;
    ll sum = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            for(int k = 1; k <= N; k++){
                sum += euclidean_gcd(euclidean_gcd(i,j),k);
            }
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		if (A % 2 == 0) {
			System.out.println(A);
			return;
		}
		System.out.println(A * 2);

	}

}

Measured memory_bytes: 20948
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));

function main(){
  var n = next();
  return (1000-n%1000)%1000;
}

Measured memory_bytes: 29688
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<=(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 文字変換　
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned Euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return Euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int digit_sum(int n) {
  int sum=n%10;
  while(n!=0) {
    n/=10;
    sum+=n%10;
  }
  return sum;
}

vpll PrimeFactorization(ll n) {
  vpll res;
  for (ll i=2; i*i<=n; i++) {
    if(n%i!=0) continue;
    ll ex=0;
    while(n%i==0) {
      ex++;
      n/=i;
    }
    res.push_back(pll(i,ex));
  }
  if(n!=1) res.push_back(pll(n,1));
  return res;
}

int main() {
  char s[100001];
  cin >> s;
  int n=strlen(s);
  string ans="";
  REP(i,n) {
    if(i%2==0) ans+=s[i];
  }
  cout << ans << endl;
  return 0;
}


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

int main(void)
{
	int N, M; cin >> N >> M;
	vector<int> counter(M, 0);
	for (int i = 0; i < N; i++) {
		int K; cin >> K;
		for (int j = 0; j < K; j++) {
			int tmp_A; cin >> tmp_A;
			counter[tmp_A-1]++;
		}
	}
	int ans = 0;
	for (int i = 0; i < counter.size(); i++) {
		if (counter[i] == N)ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n=int(raw_input())
m1,m2=0,0
i1=-1
for i in xrange(n):
    m=int(raw_input())
    if m>m1:
        m2,m1=m1,m
        i1=i
    elif m>m2:
        m2=m
for i in xrange(n):
    if i==i1:
        print m2
    else:
        print m1

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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector <vector <int>> k(10),k2(10);
    string s2;
    rep(i,n){
        s2=s[i];
        k[stoi(s2)].push_back(i);
    }

    int a,b,c,lo,d,ans;
    ans=0;

    
    rep(i,10){
        rep(j,10){
            rep(l,10){
                //cout << i << j << l << endl;
                d=0;
                k2=k;
                lo=k2[i].size();
                if(lo==0){
                    d=-1;
                }
                else{
                a=k2[i][0];
                }
                lo=k2[l].size();
                if(lo==0){
                    d=-1;
                }
                else{
                    c=k2[l][lo-1];
                }
                lo=k2[j].size();
                if(lo==0){
                    d=-1;
                }
                //cout << lo << endl;
                if(d==0){
                rep(e,lo){
                    if(k2[j][e]>a and k2[j][e]<c){
                        //cout << i << j << l << endl;
                        break;
                    }
                    if(e==lo-1){
                        d=-1;
                    }
                }
                }
                if(d==0){
                    ++ans;
                }

            }
        }
    }

    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 640
// agrawal117
//chahatagrawal117 
#include<bits/stdc++.h>
#define mod 1000000007
#define endl '\n'
typedef  long long int ll ; 
using namespace std;
#define MAX 1002
int main()
{
  ll a, b; cin>>a>>b;
  if(a==1 || b==1) cout<<1<<endl;
  else {ll val= a*b;
  val/=2;
  if((a*b)%2!=0) val++; 
  cout<<val<<endl; }

}

Measured memory_bytes: 256
import std.stdio, std.string, std.array, std.conv;

void main() {
    while (true) {
        string[] tmp = readln.chomp.split;
        int a = tmp[0].to!int, b = tmp[2].to!int;
        string op = tmp[1];
        if (op == "+") {
            writeln(a + b);
        } else if (op == "-") {
            writeln(a - b);
        } else if (op == "*") {
            writeln(a * b);
        } else if (op == "/") {
            writeln(a / b);
        } else {
            break;
        }
    }
}


Measured memory_bytes: 2476
#include<bits/stdc++.h>
using namespace std;
inline void io()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
}
int main()
{
    io();
    int a, b=3;
    map<int, int>m;
    while (b--)
    {
        cin >> a;
        m[a]++;
    }
    cout << (m[5] == 2 && m[7] == 1 ? "YES\n" : "NO\n");
    return 0;
}

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

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

    cout << n*n*n << endl;

    return 0;
}


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

#define REP(i,n) for(int i=0;i<n;i++)
#define llong long long

using namespace std;

int main(){

	char c[3][3];

	REP(i, 3) {
		REP(j, 3) {
			cin >> c[i][j];
		}
	}

	cout << c[0][0] << c[1][1] << c[2][2] << endl;

  return 0;
}


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

int main() {
  long long a,b,c,k;cin>>a>>b>>c>>k;
  long long ans=0;
  if(k<a){
    ans=k; 
  }else if(a+b>=k){
    ans=a;
  }else{
    ans=a-(k-a-b);
  }
  cout <<ans<<endl;
}


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

int main(){
  int n;  cin >> n;
  vector<pair<int, int>> xy(n);
  for(int i=0; i<n; i++){
    int x, y;  cin >> x >> y;
    xy[i].first = x, xy[i].second = y;
  }
  vector<int> a(n);
  for(int i=0; i<n; i++)  a[i] = i;

  int cnt = 0;
  double sum = 0;
  do{
    for(int i=1; i<n; i++)
      sum += sqrt(pow(xy[a[i-1]].first-xy[a[i]].first, 2)+pow(xy[a[i-1]].second-xy[a[i]].second, 2));
    cnt++;
  }while(next_permutation(a.begin(), a.end()));

  printf("%.10lf\n", sum/cnt);

  return 0;
}


Measured memory_bytes: 3820
from functools import reduce
import fractions
N = int(input())
* A, = map(int, input().split())
mod = 10**9+7


def gcd(a, b):
    return int(fractions.gcd(a, b))


def lcm(a, b):
    return a*b//gcd(a, b)


LCM = reduce(lcm, A)

ans = 0
for a in A:
    ans += LCM * pow(a, mod - 2, mod) % mod
print(ans % mod)


Measured memory_bytes: 6068
#include <iostream>

#define MAX(a,b) a > b ? a : b
#define MIN(a,b) a < b ? a : b
using namespace std;

int main(){
  int n; cin>>n;
  int x;
  int min;
  int profit = -1000000000;
  cin>>x;
  min = x;

  for(int i=1;i<n;i++){
    cin>>x;
    profit = MAX(profit,x-min);
    min = MIN(min,x);
  }
  cout<<profit<<endl;
}

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

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

signed main(){
    int s,c;
    cin>>s>>c;

    int ans=0;
    int t=min(s,c/2);
    ans+=t;
    s-=t;c-=t*2;
    cout<<ans+c/4<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAX = 111111;
int a[MAX],b[MAX],c[MAX],dp[MAX][3];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 3; j++){
      if(i == 0)
      {
        if(j == 0)
          dp[i][j] = a[i];

        else if(j == 1)
          dp[i][j] = b[i];

        else
          dp[i][j] = c[i];
      }
      else{
        for(int k = 0; k < 3; k++){
          if(j == k)
            continue;
          if(j == 0) dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i]);
          else if(j == 1) dp[i][j] = max(dp[i][j], dp[i - 1][k] + b[i]);
          else dp[i][j] = max(dp[i][j], dp[i - 1][k] + c[i]);
        }
      }
    }
  }
  int ans = 0;
  ans = max(ans, dp[n - 1][0]);
  ans = max(ans, dp[n - 1][1]);
  ans = max(ans, dp[n - 1][2]);
  cout << ans;
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(1e1 + 5);


int a[MAX_N];

ll ans;

ll calc() {
  ll tmp = 0;

  for (int i = 0; i < 5; ++i) {
    tmp += a[i];
    if (i == 4) break;
    while (tmp % 10 != 0) {
      tmp += 1;
    }
  }

  return tmp;
}

int main(void) {
  // Here your code !

  for (int i = 0; i < 5; ++i) {
    scanf("%d", &(a[i]));
  }

  ans = INF;

  do {
    ll tmp = calc();
    ans = min(ans, tmp);
  } while (next_permutation(a, a + 5));

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

  return 0;
}


Measured memory_bytes: 256
# -- coding:utf-8 --
n,m,c=map(int,input().split())
B = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(n)]

count = 0

for ii in range(n):
    temp = [0] * m
    for jj in range(m):
        temp[jj] = A[ii][jj]*B[jj]
    if sum(temp) + c > 0:
        count += 1
print(count)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)

using namespace std;
typedef pair<llint, llint> P;

llint h, w;
char c[105][105];
bool used[105][105];
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

void bfs()
{
	queue<P> Q;
	Q.push(P(0, 0));
	used[0][0] = true;
	
	int x, y;
	while(Q.size()){
		x = Q.front().first, y = Q.front().second;
		Q.pop();
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
			if(c[nx][ny] == '#') continue;
			if(used[nx][ny]) continue;
			Q.push(P(nx, ny));
			used[nx][ny] = true;
		}
	}
}


int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> h >> w;
	for(int y = 0; y < h; y++){
		for(int x = 0; x < w; x++){
			cin >> c[x][y];
		}
	}
	
	for(int y = 0; y < h; y++){
		for(int x = 0; x < w; x++){
			if(x%4 == 1){
				if(c[x][y] != '3') c[x][y] = '#';
			}
			if(x%4 == 3){
				if(c[x][y] != '4') c[x][y] = '#';
			}
			if(y%4 == 1){
				if(c[x][y] != '2') c[x][y] = '#';
			}
			if(y%4 == 3){
				if(c[x][y] != '5') c[x][y] = '#';
			}
			if(x%2 == 0 && y%2 == 0){
				if((x/2+y/2)%2){
					if(c[x][y] != '1') c[x][y] = '#';
				}
				else{
					if(c[x][y] != '6') c[x][y] = '#';
				}
			}
		}
	}
	
	bfs();
	
	if(used[w-1][h-1]) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}


Measured memory_bytes: 3236
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

long long GCD(long long a, long long b) {
    if(b == 0)
        return a;
    else
        return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}

int main() {
    int N;
    cin >> N;
    set<int> se;
    rep(i, 0, N) {
        int a;
        cin>>a;
        se.insert(a);
    }
    if(se.size() == N) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
#include <math.h>
#define uint unsigned long long
#define ll long long
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define ept 1e-9

using namespace std;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline ll read1()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}

int main()
{
	int n = read();
	int k = read();
    ll ans = 0;
	rep(x, k, n - 1)
	{
        int t = n - x;
        for (int b = x + 1; b <= n;)
        {
            int Next = 0;
            if (t / b) Next = t / (t / b);
            else Next = n;
            ans += 1ll * (Next - b + 1) * ((t / b) + (x > 0));
            b = Next + 1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = [input() for i in range(n)]
judge = ['AC', 'WA', 'TLE', 'RE']
count = [0, 0, 0, 0]
for x in s:
    for i in range(4):
        if x==judge[i]: count[i] += 1

for i in range(4):
    print("{} x {}".format(judge[i], count[i]))
    



Measured memory_bytes: 16148
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
S[0] = A[0]

for i in range(1,N):
    S[i] = S[i-1]+A[i]

ans = float("inf")
for i in range(N-1):
    snuke = S[i]
    arai = S[N-1]-S[i]
    tmp = abs(arai - snuke)
    ans = min(ans,tmp)
print(ans)

Measured memory_bytes: 76880
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll h, n, s = 0;
    cin >> h >> n;
    vector<ll> a(n);
    for (ll &e : a)
        cin >> e, s += e;
    cout << (s < h ? "No" : "Yes");
    return 0;
}


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

int main() {
  int n;
  string s;
  cin>>n>>s;
  if(n%2==0){
    bool ans=true;
    for(int i=0;i<n/2;i++){
      if(s.at(i)!=s.at(n/2+i))
        ans=false;
    }
    if(ans)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 1000000

int main()
{
  int i,n,data[N+1];
  int p,l,r;

  scanf("%d",&n);

  for(i=1; i<=n; i++)
    scanf("%d",&data[i]);

  for(i=1; i<=n; i++){
    printf("node %d: key = %d, ",i,data[i]);

    p = i/2;
    l = i*2;
    r = i*2+1;

    if(p >= 1)
      printf("parent key = %d, ",data[p]);

    if(l <= n)
      printf("left key = %d, ",data[l]);

    if(r <= n)
      printf("right key = %d, ",data[r]);

    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 2104
function main(arg) {
	arg = arg.trim().split("\n")
	var N = Number(arg[0])
	var v = arg[1].split(" ").map(Number)
	var c = arg[2].split(" ").map(Number)
	var result = 0
	for (var i = 0;i < v.length; i ++) {
		var t = v[i] - c[i]
		if (t >= 0) {
			result += t
		}
	}
	console.log(result)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x, n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair< int, int > P;
typedef pair< int, P > PP;

//-------------------------------------------------

int d, n;

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

	cin >> d >> n;
	if (n == 100) n = 101;
	cout << n;
	REP(i, d) cout << "00";
	cout << endl;

	return 0;
}



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


int main(){
    int n; cin >> n;
    vector<int> v(n),c(n);
    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    for(int i=0;i<n;i++){
        cin >> c[i];
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        if(v[i]-c[i] > 0){
            ans += v[i]-c[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int n, m, A[20];

int solve(int p, int sum){
  int res;
  if(sum == 0)
    return 1;
  if(p >= n)
    return 0;
  res = solve(p+1, sum) || solve(p+1, sum - A[p]);
  return res;
}

int main(void){
  int i, q, goal;
  scanf("%d", &n);
  for(i=0;i<n;i++)
    scanf("%d", &A[i]);
  scanf("%d", &q);
  for(i=0;i<q;i++){
    scanf("%d", &goal);
    if(solve(0, goal))
      printf("yes\n");
    else
      printf("no\n");
  }
  return 0;
}

Measured memory_bytes: 1808
#include <iostream>
using namespace std;
int main(void){
    //入力
    int n,d,ans;
    cin >> n >> d;
    ans=n/(2*d+1)+1;
    if(n%(2*d+1)==0){
        ans-=1;
    }
    cout << ans << endl;
    return 0;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a1[200005],an[200005];
int main()
{
	std::ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		if(a==1) a1[b]=1;
		if(b==n) an[a]=1;
	}
	for(int i=1;i<=m;i++)
	{
		if(a1[i]&&an[i])
		{
			cout<<"POSSIBLE"<<endl;
			return 0;
		}
	}
	cout<<"IMPOSSIBLE"<<endl;
	return 0;
}


Measured memory_bytes: 1792
import numpy as np

N, K = map(int, input().split(' '))
h = np.array(list(map(int, input().split(' '))))
dp = np.zeros(len(h), dtype=int)
for i in range(1, len(h)):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[-1])

Measured memory_bytes: 22836
n, m = map(int, input().split())

a = []
for i in range(m):
    a.append(int(input()))
a = set(a)

dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

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

int main() {

  int K, S;
  cin >> K >> S;

  int answer = 0;

  for (int X = 0; X <= K; X++) {
    for (int Y = 0; Y <= K; Y++) {
      int Z = S - Y - X;
      if (Z <= K && 0 <= Z) {
        answer++;
      }
    }
  }

  cout << answer << endl;

}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int N,A,B;
  int max=0,min=0;
  scanf("%d %d %d",&N,&A,&B);
  if( A >= B){
  	max = B;
  }else{
  	max = A;
  }

  if(A+B <= N){
  	min = 0;
  }else{
  	min = A+B-N;
  }

  printf("%d %d\n",max,min);

  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
int main()
{
        int a,b,c;
        while(scanf("%d",&a)!=EOF)
        {
                scanf(" %d",&b);
                c=a+b;
                int cnt,i;
                i=1;
                for(cnt=0;;cnt++)
                {       
                        if(c/i==0)break;
                        i=i*10;
                }
                printf("%d\n",cnt);
        }
        
        return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f
using namespace std;
#define mod 1000000000+7
ll a[200005],sum[200005];
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        ans+=(a[i]%1000000007)*((sum[n]-sum[i])%1000000007);
        ans%=1000000007;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6716
#include <iostream>
using namespace std;
int main(void){
    
    int n,i;
    int x[101];
    
    cin  >>  n;
    for(i=0;i<n;i++)cin >> x[i];
    
    cout << x[n-1];
    for(i=n-2;i>=0;i--)cout << " " << x[i];
    
    cout << endl;
    
    return 0;
    
}


Measured memory_bytes: 3116
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;
TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM K, TNM V> using umap = unordered_map<K, V>;
TPL<TNM K, TNM V> using uset = unordered_set<K, V>;

TPL<class T> inline void OUT(const T &x) { cout << x << "\n"; }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

TPL<TNM V, TNM H> void resize(vector<V>& v, const H h) { v.resize(h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& v, const H& h, const T ... t) { v.resize(h); for (auto& _v : v) resize(_v, t ...); }
TPL<TNM V, TNM T> void fill(V& x, const T& val) { x = val; }
TPL<TNM V, TNM T> void fill(vector<V>& vec, const T& val) { for (auto& v : vec) fill(v, val); }
TPL<TNM T> inline void UNIQUE(vector<T>& vec) {	sort(ALL(vec)); vec.erase(unique(ALL(vec)), vec.end()); }

int main(void) {
	string S; int K;
	cin >> S >> K;
	int N = S.size();
	vector<string> dict;
	dict.reserve(N*K);
	REP(i, N) {
		REP(j, K) {
			dict.emplace_back(S.substr(i, j + 1));
		}
	}
	UNIQUE(dict);
	OUT(dict[K - 1]);
	return 0;
}

Measured memory_bytes: 1664
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def can_make(div):
    mods = []
    for a in A:
        mods.append(a % div)

    mods.sort()
    left = 0
    right = len(mods) - 1
    k = K
    while left <= right and k >= 0:
        while left < len(mods) and mods[left] % div == 0:
            left += 1
        while right >= 0 and mods[right] % div == 0:
            right -= 1
        if right < left:
            return True

        m = div - mods[right]
        if mods[left] >= m:
            mods[left] -= m
            mods[right] = 0
            right -= 1
            k -= m
        else:
            mods[right] += mods[left]
            k -= mods[left]
            mods[left] = 0
            left += 1
    return k >= 0


N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

# 答えは絶対 A の合計の約数になる
divs = get_divisors(sum(A))
for div in sorted(divs, reverse=True):
    if can_make(div):
        print(div)
        exit()
assert False


Measured memory_bytes: 42844
// ConsoleApplication1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>

using namespace std;

int main()
{
	int A, B;
	cin >> A >> B;
	if (A < B) {
		int hold = A;
		A = B;
		B = hold;
	}

	int ans;
	if (A-B>0)
	{
		ans = 2 * A - 1;
	}
	else
	{
		ans = A + B;
	}
    cout << ans << endl; 
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


Measured memory_bytes: 256
import sys

#UnionFine　ネットの解答

def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

def union(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)

    if x != y:
        #xとyの属している集合が異なる場合
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def same(x,y,par):
    return find(x,par) == find(y,par)

input = sys.stdin.readline
n, k, l = map(int, input().split())    
apar = []
bpar = []
arank = [0]*n
brank = [0]*n

for i in range(n):
    apar.append(i)
    bpar.append(i)


for i in range(k):
    p,q = map(int, input().split())
    union(p-1,q-1,apar,arank)

for i in range(l):
    p,q = map(int, input().split())
    union(p-1,q-1,bpar,brank)

num = []
d = {}
for i in range(n):
    num.append(find(i,apar)+find(i,bpar)*10**6)
    if num[-1] in d:
        d[num[-1]] += 1
    else:
        d[num[-1]] = 1

res = ''
for i in range(n):
    if i != 0:
        res += ' '

    res += str(d[num[i]])

print(res)

Measured memory_bytes: 41996
N, K = map(int, input().split())
xs = list(map(int, input().split()))
xs.append(xs[-1])
ans = float('inf')
anses = []
for i in range(N-K+1):
    tmp = (abs(xs[i+K-1] - xs[i]))
    if xs[i]*xs[i+K-1] < 0 or xs[i] > 0 or xs[i+K-1] < 0: 
        tmp += min(abs(xs[i]), abs(xs[i+K-1]))
    anses.append(tmp)
    if ans > tmp:
        ans = tmp
print(ans)


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

using namespace std;

#define FAST_IO ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define endl "\n"
typedef long long ll;
 
int main(){ 
	
	FAST_IO;
   
	int n;
	cin>>n;

	int a[n],b[n],c[n];
	for(int i=0; i<n; i++){
		cin>>a[i]>>b[i]>>c[i];
	}

	int dp[n][3];
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];

	for(int i=1; i<n; i++){
		dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i];
		dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + b[i];
		dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + c[i];
	}

	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}
 

Measured memory_bytes: 2560
s=input()
s1=int(s[0]+s[1])
s2=int(s[2]+s[3])

if  1<=s1<=12:
    if  1<=s2<=12:
        print('AMBIGUOUS')
    else :
        print('MMYY')

else:
    if  1<=s2<=12:
        print('YYMM')
    else:
        print('NA')


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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;  // 2次元配列
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
//    cout << fixed << setprecision(15);

    /**
     * 左右から何個とるかを全探索。　負の要素をすべて返却するとしてよく、
     * そうしたときにk回以内で負の要素をすべて返却しきる方法を全探索する
     */
    i32 n, k; cin >> n >> k;
    vi v(n); rep(i,n) cin >> v[i];
    vi csum(n+1), csum_nega(n+1);
    rep(i,n) csum[i+1] += csum[i] + v[i];  // 累積和
    rep(i,n) csum_nega[i+1] += csum_nega[i] + (v[i] < 0 ? 1 : 0);  // count negative element

    minheap<i32> hp, init;
    i32 ans = -inf, tmp;
    for(i32 l = 0; l <= min(n,k); ++l) {
        for(i32 r = 0; r <= min(n,k); ++r) {
            if(l + r > min(n,k)) continue;
            tmp = csum[l] - csum[0] + csum[n] - csum[n-r];  // 取り合えず、和。
            i32 del = k - (l+r);
            chmax(del, 0);
            hp = init;
            for(i32 i = 0; i < l; ++i) if(v[i] < 0) hp.push(v[i]);
            for(i32 i = n-r; i < n; ++i) if(v[i] < 0) hp.push(v[i]);
            rep(i, del) if(hp.size()) {
                tmp -= hp.top();
                hp.pop();
            }
            chmax(ans , tmp);
        }
    }

    cout << ans << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main() {
  string N; cin >> N;
  int num[4] = {0}; for (int i; i<4; i++) num[i] = N[i]-'0'; 
  // for (auto i : num) cout << i; cout << endl;

  int result = 0;
  for (int bit=0; bit<(1<<3); bit++) {
    int sum = num[0];
    for (int i=0; i<3; i++) {
      if ( bit & (1<<i) ) sum += num[i+1];
      else sum -= num[i+1];
    }
    if (sum == 7) {
      result = bit;
      break;
    }
  }

  string op;
  cout << num[0];
  for (int i=0; i<3; i++) {
    if ( result & (1<<i) ) op = "+"; else op = "-";
    cout << op << num[i+1];
  }
  cout << "=7" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
char b;
cin>>b;
if(b=='A')
cout<<"T";
else if(b=='C')
cout<<"G";

else if(b=='T')
cout<<"A";
else if(b=='G')
cout<<"C";


return 0;  
}

Measured memory_bytes: 3576
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 1

typedef long long ll;

const double PI = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(),a.end(),greater<>());
    int sum = 0;
    for(int i = 0; i < k; i++){
        sum += a[i];
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<ll> dp(2);
  dp[1] = numeric_limits<ll>::min();
  function<void(ll&, ll)> relax = [&](ll& x, ll y) {
    if (y > x) x = y;
  };
  while (n--) {
    int a;
    cin >> a;
    vector<ll> newDp(2, numeric_limits<ll>::min());
    relax(newDp[0], dp[0] + a / 2);
    if (a > 1)
      relax(newDp[0], dp[1] + (a - 1) / 2 + 1);
    if (a > 1)
      relax(newDp[1], dp[0] + (a - 1) / 2);
    if (a > 2)
      relax(newDp[1], dp[1] + (a - 2) / 2 + 1);
    dp = newDp;
  }
  cout << dp[0];

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef pair<ll, ll> PLL;

#define REP(i, j) for(int i=0;i<j;i++)
#define FOR(i, b, e) for(int i=b; i<=e; i++)
#define FORD(i, b, e) for(int i=b; i>=e; i--)
#define SIZE(x) ((int)x.size())
#define LAST(x) (x[SIZE(x)-1])
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sp ' '
#define ent '\n'

ll dp[100005];
ll n, u, v, w;

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

    cin >> n >> u;

    REP(i, u+1){
        dp[i] = INT_MIN;
    }

    dp[0]=0;

    REP(i, n){
        cin >> w >> v;
        for(int j=u-w;j>=0;j--){
            if(dp[j]!=INT_MIN)dp[j+w] = max(dp[j]+v, dp[j+w]);
        }
    }
    ll maxi = 0;
    REP(i, u+1)maxi = max(maxi, dp[i]);
    cout << maxi;

    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
int dp[1001];
using namespace std;
int main(){
	for (int i = 1; i < 1001; i++){
		int k = i;
		for (int j = i + 1; j < 1001; j++){
			k += j;
			if (k>1000)break;
			dp[k]++;
		}
	}
	while (1){
		int n;
		cin >> n;
		if (n == 0)return 0;
		cout << dp[n] << endl;

	}
	return 0;

}

Measured memory_bytes: 1164
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math

N,M=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for m in range(M)]

data=[[] for i in range(N+1)]
ittenai=set()

for x,y in xy:
    data[x].append(y)
    data[y].append(x)
    ittenai.add(x)
    ittenai.add(y)
#print(ittenai)
count=len([i for i in range(N) if not i+1 in ittenai and p[i]==i+1])
while ittenai:
    stack=[ittenai.pop()]
    idxlst=set([stack[0]])
    while stack:
        idx=stack.pop()
        for i in data[idx]:

            if not i in idxlst:
                idxlst.add(i)
                stack.append(i)
                ittenai.remove(i)
    idxlst=list(idxlst)
    numlst=set([p[i-1] for i in idxlst])
    #print(idxlst,numlst)
    for i in idxlst:
        count+=i in numlst


print(count)


Measured memory_bytes: 107244
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # 尺取り法 '<=k'型
    # https://atcoder.jp/contests/abc032/tasks/abc032_c
    # s内のa_iについて、a_l * a_{l + 1} * ... * a_r <= kなるr - lの最大値を求める。
    n= int(input())
    s = list(map(int,input().split()))
    
    r, ans, tmp = 0, 0, 0
    for l in range(n):
        # 1. rを1個進められるなら進める
        while r < n and tmp ^ s[r]==tmp+s[r]:
            tmp ^= s[r]
            r += 1

        # 2. breakした状態でrは条件を満たす最大なので、何かする。
        #ans = max(ans, r - l)  # 本問では最大値を更新
        ans += r - l # (l, r)の組の個数をカウント

        # 3. lをインクリする準備
        if l == r:  # 区間でないなら区間にする
            r += 1
        else:
            # 左端を右に1つずらすので。それに合わせて値（ここでは積）も変える。
            # rは変える必要がない。
            tmp ^= s[l]
            
        # 解なし（ansが更新されないままになっている時）を考慮する場合はここに付記
        # cf. https://qiita.com/drken/items/ecd1a472d3a0e7db8dce#%E5%95%8F%E9%A1%8C-2poj-3061-subsequence
    print(ans)
    
    
resolve()

Measured memory_bytes: 101880
#include <iostream>
using namespace std;
int w, h, m[50][50], dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1}, dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
void dfs(int x, int y)
{
	int i, nx, ny;
	m[y][x] = 0;
	for (i = 0; i < 8; i++)
	{
		if (0 <= (nx = x+dx[i]) && nx < w && 0 <= (ny = y+dy[i]) && ny < h)
			if (m[ny][nx])
				dfs(nx, ny);
	}
}
int main()
{
	int n, i, j;
	while (cin >> w >> h)
	{
		if (w == 0 && h == 0) break;
		for (i = 0; i < h; i++)
			for (j = 0; j < w; j++)
				cin >> m[i][j];
		for (i = n = 0; i < h; i++)
			for (j = 0; j < w; j++)
				if (m[i][j])
					n++, dfs(j, i);
		cout << n << endl;
	}
}

Measured memory_bytes: 0
use std::io::*;
use std::str::FromStr;
use std::collections::VecDeque;

fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut g: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut rev_g: Vec<Vec<usize>> = vec![Vec::new(); n];
    for _ in 0..n+m-1 {
        let a = read::<usize>()-1;
        let b = read::<usize>()-1;
        g[a].push(b);
        rev_g[b].push(a);
    }
    let mut que: VecDeque<usize> = VecDeque::new();
    let mut root = 0;
    let mut cnt: Vec<usize> = vec![0; n];
    for i in 0..n {
        cnt[i] += rev_g[i].len();
        if rev_g[i].is_empty() {
            root = i;
        }
    }
    let mut ans: Vec<usize> = vec![0; n];
    que.push_back(root);
    while let Some(q) = que.pop_front() {
        for i in &g[q] {
            if cnt[*i] > 1 {
                cnt[*i] -= 1;
            } else {
                ans[*i] = q+1;
                que.push_back(*i);
            }
        }
    }
    for i in 0..n {
        println!("{}", ans[i]);
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 21244
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  vector<Int> t(n);
  for(Int i=0;i<n;i++) cin>>t[i];
  Int ans=n;
  priority_queue<Int,vector<Int>,greater<Int> > pq;
  for(Int i=1;i<n;i++) pq.emplace(t[i]-t[i-1]-1);
  for(Int i=0;i<n-k;i++){
    ans+=pq.top();
    pq.pop();
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 4724
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long llong;
const int INF = 1 << 20;
const int MOD = 1e9 + 7;

int main() {
   int n, m;
   cin >> n >> m;
   map<int, int> a;
   rep(i, m) {
      int A;
      cin >> A;
      a[A]++;
   }

   vector<int> ans(n + 1);
   ans[0] = 1;
   for (int i = 1; i <= n; i++) {
      if (a[i])
         continue;
      if (i == 1)
         ans[i] = ans[0];
      else
         ans[i] = ans[i - 1] + ans[i - 2];
      ans[i] %= MOD;
   }
   cout << ans[n] << endl;
   return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int N, X; cin >> N >> X;
    int ans = 1, d = 0;
    rep(i, N) {
        int L; cin >> L;
        d += L;
        if (d <= X) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
import numpy as np

N,MOD = map(int,input().split())

"""
余事象を調べる。包除の原理を使う。
A[n] = （1,2,...,n）が1杯以下、他は何でも良い
B[n,l] : (1,2,...,n) をlグループに分ける方法の個数
A[n]
・0杯のグループあり
・なし
"""

B = np.zeros((N+1,N+1), dtype=np.int64)
B[0,0] = 1
for n in range(1,N+1):
    # 1番を単独で使う
    B[n,1:] = B[n-1,:-1]
    # 1番をどこかに混ぜてもらう
    B[n,1:] += B[n-1,1:] * np.arange(1,N+1) % MOD
    B[n] %= MOD

# 2^{kl}
pow_2 = np.ones((N+1,N+1), dtype=np.int64)
for n in range(1,N+1):
    pow_2[1,n] = 2 * pow_2[1,n-1] % MOD
for n in range(2,N+1):
    pow_2[n] = pow_2[n-1] * pow_2[1] % MOD

A = np.zeros(N+1, dtype=np.int64)
for n in range(N+1):
    A[n] = (pow(2,pow(2,N-n,MOD-1),MOD) * B[n,1:] % MOD * (pow_2[N-n,1:] + pow_2[N-n,:-1] * np.arange(1,N+1) % MOD) % MOD).sum() % MOD

comb = np.zeros((N+1,N+1),dtype = np.int64)
comb[:,0] = 1
for n in range(1,N+1):
    comb[n,1:] = (comb[n-1,1:] + comb[n-1,:-1]) % MOD

A[::2] *= (-1)
A *= comb[N]
A %= MOD
answer = pow(2,pow(2,N,MOD-1),MOD) - A.sum()
answer %= MOD
print(answer)



Measured memory_bytes: 223556
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

void Main()
{
	std::int64_t min = std::numeric_limits<std::int64_t>::max();
	int N;
	std::cin >> N;
	bool isodd = false;
	std::int64_t sum = 0;
	for (auto i : boost::irange(0, N))
	{
		std::int64_t v;
		std::cin >> v;
		if (v < std::int64_t())
		{
			isodd = !isodd;
		}
		sum += std::abs(v);
		min = std::min(min, std::abs(v));
	}
	std::cout << sum - (isodd ? 2 * min : std::int64_t()) << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 256
def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = [[0 for i in range(LT + 1)] for j in range(LS + 1)]
  L = [[0 for i in range(LT)] for j in range(LS)]
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j]
      b = DP[i][j+1]
      if max(a, b) == a:
        DP[i+1][j+1] = a
        L[i][j] = 1
      else:
        DP[i+1][j+1] = b
        L[i][j] = 2
        a = b
      if s[i] == t[j]:
        c = DP[i][j] + 1
        if max(a, c) == c:
          DP[i+1][j+1] = c
          L[i][j] = 3       
        
  Ans = ""
  j = LS - 1
  k = LT - 1
  x = DP[LS][LT]
  for i in range(x, 0, -1):
    while True:
      if L[j][k] == 3:
        Ans += t[k]
        j -= 1
        k -= 1
        break
      elif L[j][k] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()


Measured memory_bytes: 192008
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll N, K;
vector<ll> A;

int main(){
    cin >> N >> K;
    cin.ignore();
    for(int i = 0; i < N; i++){
        ll tmp;
        cin >> tmp;
        A.push_back(tmp);
    }

    queue <ll> q;
    for(int i = K; i < N; i++){
        if(A[i] > A[i - K]){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 5364
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    ll K;
    cin >> K;
    cin >> a >> b;
    rep(i,a,b+1){
        if(i % K == 0){
            print("OK");
            return 0;
        }
    }
    print("NG");


    
    

}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

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

int N;
int A[111111],B[111111];

signed main(){
    cin>>N;
    rep(i,N)cin>>A[i]>>B[i];

    int ans=min(accumulate(A,A+N,0ll),accumulate(B,B+N,0ll));

    rep(i,N)if(A[i]>B[i])swap(A[i],B[i]);

    if(*max_element(A,A+N)>=*min_element(B,B+N)){
        vint v;
        rep(i,N)v.pb(A[i]);
        rep(i,N)v.pb(B[i]);
        sort(all(v));
        chmin(ans,accumulate(v.begin(),v.begin()+N,0ll));
    }

    vpint va,vb;
    rep(i,N){
        va.pb(pint(A[i],i));
        vb.pb(pint(B[i],i));
    }
    sort(all(va));sort(all(vb));
    reverse(all(va));
    int tmp=1001001001001001001ll;
    rep(i,2)rep(j,2){
        if(va[i].se==vb[j].se)continue;
        chmin(tmp,vb[j].fi-va[i].fi);
    }
    chmin(ans,accumulate(A,A+N,0ll)+tmp);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6740
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
s = []
mod = 998244353

dp = [0]*(n+1)
dpsum = [0]*(n+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2,n+1):
    for j in lr:
        l, r = j
        li = i-r
        ri = i-l
        if ri < 0:
            continue
        li = max(1,li)
        dp[i] += dpsum[ri]-dpsum[li-1]
        dp[i] %= mod
    dpsum[i] = dpsum[i-1]+dp[i]

print(dp[n])

Measured memory_bytes: 27944
x = int(input())
A=[a**5 for a in range(500)]
for b in range(10000):
    tmp=x+b**5
    if tmp in A:
        print(A.index(tmp),b)
        exit()
    tmp=x-b**5
    if tmp in A:
        print(A.index(tmp),-b)
        exit()

Measured memory_bytes: 62028
attrs = Array.new
while line = $stdin.gets
  attrs << line.chomp.split
end

A = attrs[0][0].to_i
B = attrs[0][1].to_i
H = attrs[0][2].to_i
M = attrs[0][3].to_i

x1 = H * 30 + M * 0.5
x2 = M * 6
if x1 > x2 then
  x = x1 - x2
else
  x = x2 - x1
end
x = 360 - x if x > 180
y2 = A**2 + B**2 - 2 * A * B * Math.cos(x* Math::PI / 180)
puts "#{Math.sqrt(y2)}"

Measured memory_bytes: 14716
#include "algorithm"
#include "iostream"
#include "vector"
using namespace std;
typedef long long ll;

int main() {
  ll N;
  cin >> N;
  vector<ll> d(N);
  for (int i = 0; i < N; i++) cin >> d[i];

  ll res = 0;

  for (ll i = 0; i < N; i++) {
    for (ll j = i + 1; j < N; j++) {
      res += d[i] * d[j];
    }
  }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
int main(){
  set<pair<pair<int,int>,int> >t;
  int n,a[3],sum=0;
  cin>>n;
  while(n--){
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    if(t.count(mk(mk(a[0],a[1]),a[2])))sum++;
    t.insert(mk(mk(a[0],a[1]),a[2]));
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 3148