akhauriyash/Code-Regression huggingface dataset:
//agc044_a.cpp
//Sat May 23 19:53:48 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000000000000000

using namespace std;
using ll=long long;
typedef pair<int,int> P;
ll n,a,b,c,d;
map<ll,ll> dp;
ll dlimit;

ll scoresearch(ll score){
	if (score == 0){
		return 0;
	}else if (score == 1){
		return d;
	}
	ll ans = LLINF;
	ll tmpans;

	//2で着地
	ll baisu = score/2;
	auto itr = dp.find(baisu);
	if (itr != dp.end()){
		tmpans = abs(score-baisu*2)*d+a+dp[baisu];
	}else {
		tmpans = abs(score-baisu*2)*d+a+scoresearch(baisu);
	}
	ans = min(ans,tmpans);
	if (score%2!=0){
		baisu++;
		itr = dp.find(baisu);
		if (itr != dp.end()){
			tmpans = abs(score-baisu*2)*d+a+dp[baisu];
		}else {
			tmpans = abs(score-baisu*2)*d+a+scoresearch(baisu);
		}		
	}
	ans = min(ans,tmpans);

	//3で着地
	baisu = score/3;
	itr = dp.find(baisu);
	if (itr != dp.end()){
		tmpans = abs(score-baisu*3)*d+b+dp[baisu];
	}else {
		tmpans = abs(score-baisu*3)*d+b+scoresearch(baisu);
	}
	ans = min(ans,tmpans);
	if (score%3!=0){
		baisu++;
		itr = dp.find(baisu);
		if (itr != dp.end()){
			tmpans = abs(score-baisu*3)*d+b+dp[baisu];
		}else {
			tmpans = abs(score-baisu*3)*d+b+scoresearch(baisu);
		}
	}
	ans = min(ans,tmpans);

	//5で着地
	baisu = score/5;
	itr = dp.find(baisu);
	if (itr != dp.end()){
		tmpans = abs(score-baisu*5)*d+c+dp[baisu];
	}else {
		tmpans = abs(score-baisu*5)*d+c+scoresearch(baisu);
	}
	ans = min(ans,tmpans);
	if (score%5!=0){
		baisu++;
		itr = dp.find(baisu);
		if (itr != dp.end()){
			tmpans = abs(score-baisu*5)*d+c+dp[baisu];
		}else {
			tmpans = abs(score-baisu*5)*d+c+scoresearch(baisu);
		}
	}
	ans = min(ans,tmpans);

	//+-1だけで着地
	if (score<=dlimit){
		tmpans = score*d;
	}
	ans = min(ans,tmpans);


	dp[score] = ans;
	return ans;
}


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

	for (int zzz=0;zzz<t;zzz++){
		cin >> n >> a >> b >> c >> d;
		ll ans = LLINF;
		dlimit = LLINF/d;
		dp.clear();
		dp[0] = 0;
		dp[1] = d;
		ans = scoresearch(n);
		cout << ans << endl;
	}
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 4420
import math

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

array = [[0 for i in range(10)] for j in range(10)]

for i in range(N):
    x = list(map(int, input().split()))
    for j in range(0, D):
        array[i][j] = x[j];
sum_dis = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        dis = 0
        for k in range(D):
            dis += (array[i][k] - array[j][k])**2
        dis = math.sqrt(dis)
        if(dis.is_integer()): sum_dis += 1
print(sum_dis)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){
  int a,b,c=-1,d=0,e=INT_MAX;
  cin>>a;
  lp(i,a){
    cin>>b;
    if(b<=e)c++;
    else{
      d=max(c,d);
      c=0;
    }
    e=b;
  }
  d=max(c,d);
  cout<<d;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back

using ll = long long;
using db = double;
using pii = pair<int, int>;
using vi = vector<int>;

ll n, m;
bool judge(ll x) {
    ll tmp = n;
    while(tmp % x == 0)
        tmp /= x;
    return tmp % x == 1;
}
signed main(){
    scanf("%lld", &n);
    if(n == 2) return puts("1"), 0;
    m = n - 1;
    int cnt = 2;
    for(ll i = 2; i * i <= m; i++)
        if(i * i == m) cnt++;
        else if(m % i == 0) cnt += 2;
    for(ll i = 2; i*i <= n; i++)
        if(i * i == n) cnt += judge(i);
        else if(n % i == 0)
            cnt += judge(i), cnt += judge(n / i);
    printf("%d\n", cnt);
    fprintf(stderr, "time=%.4f\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
    /* 取模直接除，爆零两行泪
     * 不开ll见祖宗
     */
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

ll ans=1;
const int MAX = 510000;//階乗の配列数
const int MOD = 1000000007;

int k;
vector<int> to[100005];
  vector<int> deg(100005);
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long pr(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[n-k] % MOD;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

void dfs(int v, int p=-1) {
  if(p==-1){
    ans*=pr(k, deg[v]+1);
    ans%=MOD;
  } else {
    ans*=pr(k-2, deg[v]-1);
    ans%=MOD;
  }
  for (int u : to[v]) {
    if (u == p) continue;
    dfs(u,v);
  }
}

int main(){
  //ABC138D

  int n;
  cin >> n >> k;
  rep(i,n-1) {
      int a, b;
      cin >> a >> b;
      --a; --b;
      to[a].push_back(b);
      to[b].push_back(a);
      deg[a]++;deg[b]++;
    }
    COMinit();
    dfs(0, -1);
    cout << ans << endl;
  return 0;
}


Measured memory_bytes: 24552
import math
x=0
y=0
d=90
cos=lambda x:round(math.cos(math.radians(x)),10)
sin=lambda x:round(math.sin(math.radians(x)),10)

while True:
    try:h,r=[int(i) for i in input().split(",")]
    except:break
    if h==0 and r==0:break
    x+=h*cos(d)
    y+=h*sin(d)
    d+=-r
print("{0}\n{1}".format(int(x),int(y)))


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

using namespace __gnu_pbds; 
using namespace __gnu_cxx;
using namespace std;

typedef long long ll;

#define eb emplace_back
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}
template<typename T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update >;
template<typename T> using MinPriorityQueue = priority_queue <T, vector <T>, greater <T> >;
template<typename T> void done(T ans) {cout << ans << "\n"; exit(0);}

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);

clock_t time_p=clock();
void printTime(){
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}


ll mod=1e9+7;
const int N = 1e5 + 5;
bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

int32_t main(){
    io();
    ll h, w;
    cin >> h >> w;
    ll k = h * w;
    if(h == 1 || w == 1) {
        cout << "1";
    }
    else if(k % 2) {
        cout << (k/2)+1;
    }
    else    cout << k/2;


}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;

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

    cin >> N;

    ll ans = LLINF;
    for(ll i = 1; i <= 1000010; ++i) {
        ll div = N / i;
        if(N % i == 0) {
            ans = min(ans, div - 1 + i - 1);
        }
    }

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

    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
using namespace std;
int main() {
    char a[10];
    const char *check = "1";
    cin >> a;
    int ans = 0;
    for(int i = 0; i < 10; i++){
        if(a[i] == *check){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int q = sc.nextInt();
		for(int i=0;i<q;i++) {
			int c = sc.nextInt();
			int a = sc.nextInt();
			int n = sc.nextInt();
			int max = 0;
			int zmax = Math.min(Math.min(c, a), n);
			for(int z=0;z<=zmax;z++) {
				int xupper = Math.min((c - z) / 2, a - z);
				for(int x=xupper;x>=xupper-2;x--) {
					if (x < 0) {
						break;
					}
					int kupper = (c + 2 * z + x) / 3;
					int klower = (z + x);
					if (klower <= kupper) {
						max = Math.max(max,kupper);
					}
				}
			}
			System.out.println(max);
		}
	}

}

Measured memory_bytes: 20888
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n;
    std::cin >> n;
    std::vector<std::tuple<std::string, int, int>> v;
    for (int i = 1; i <= n; i++) {
        std::string s;
        int p;
        std::cin >> s >> p;
        v.emplace_back(s, -p, i);
    }
    std::sort(v.begin(), v.end());
    for (const auto &e : v) std::cout << std::get<2>(e) << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
  
typedef long long ll; 
typedef pair<ll, ll> pll;
typedef vector<ll> vl; 
typedef vector<vl> vvl; 
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
#define MOD 1000000007  
#define FOR(a, b, c) for (ll(a) = (b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (ll(a) = (b); (a) <= (c); ++(a)) 

#define REP(i, n) FOR(i, 0, n) 
#define REPN(i, n) FORN(i, 1, n) 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back 
#define ALL(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz 
#define SIZE(v) (int)v.size() 
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v)) 
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) 
#define TC(t) while (t--) 

int main()
{
    fast;
    ll i,j,k,m,n,q,r,c,x;
    cin>>i>>j>>k>>r>>c;
    ll ans=0;
    if((i+j) >= 2*k){
        x = min(r,c);
        ans += x*2*k; r -= x; c -= x;
    }
    if(r){
        if(r*i >= 2*k*r){
            ans += 2*k*r;
        }
        else
            ans += r*i;
    }
    if(c){
        if(c*j >= 2*k*c){
            ans += 2*k*c;
        }
        else
            ans += c*j;
    }
    cout<<ans;
}	

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

int main(){
    int n;
    cin >> n;
    queue<int> q[n];
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            int k;
            cin >> k;
            --k;
            q[i].push(k);
        }
    }
    
    vector<pair<int, int> > vq;
    auto append_fn = [&](int i){
        if(q[i].size() == 0) return;
        int j = q[i].front();
        if(q[j].size() == 0) return;
        if(q[j].front() == i){
            if(i > j) swap(i, j);
            vq.push_back({i, j});
        }
    };
    
    for(int i=0; i<n; i++) append_fn(i);
    int day = 0;
    
    while(!vq.empty()){
        ++day;
        sort(vq.begin(), vq.end());
        vq.erase(unique(vq.begin(), vq.end()), vq.end());
        
        vector<pair<int, int> > vq2;
        swap(vq, vq2);
        
        for(auto match: vq2){
            int i, j;
            tie(i, j) = match;
            q[i].pop();
            q[j].pop();
        }
        
        for(auto match: vq2){
            int i, j;
            tie(i,j) = match;
            append_fn(i);
            append_fn(j);
        }
    }
    
    for(int i=0; i<n; i++){
        if(q[i].size() > 0){ cout << -1 << endl; return 0;}
    }
    cout << day << endl;
    return 0;
}

Measured memory_bytes: 4736
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <sstream>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 1LL << 60;
constexpr int inf = 1 << 30;

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

    if (N % 2) cout << 0 << endl;
    else {
        sort(d.begin(), d.end());
        cout << (d[N / 2] - d[N / 2 - 1]) << endl;
    }
    return 0;
}

Measured memory_bytes: 888
# 与えられた数値の桁数と桁値の総和を計算する.
def calc_digit_sum(num):
    digits = sums = 0
    while num > 0:
        digits += 1
        sums += num % 10
        num //= 10
    return digits, sums


length = len(input())
print("x" * length)

Measured memory_bytes: 61888
college = Array.new(4).map { Array.new(3).map { ['', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] } }

input = []

gets.to_i.times{ input << gets.split(' ').map(&:to_i) }

input.each do |e|
  b, f, r, v = e
  college[b - 1][f - 1][r] += v
end

college.each_with_index do |ary, i|
  puts ary.map { |e| e.join(' ') }.join("\n")
  break if college.size - 1 == i
  puts '#' * 20
end

Measured memory_bytes: 8716
#include "bits/stdc++.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define REPS(i, n) for (int i = 1; i <= (n); i++)
#define RREPS(i, n) for (int i = (n); i > 0; i--)
#define mp make_pair
#define pb(a) push_back(a)
typedef long long ll;

int main() {
  int N,X;
  cin >> N >> X;
  int mi = 1e9;
  REP(i,N){
    int m;
    cin >> m;
    X -= m;
    mi = min(mi,m);
  }
  int ans = N + X/mi;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
from collections import Counter

input = sys.stdin.readline


def main():
    S = input().rstrip()
    T = input().rstrip()

    c_S = Counter(S)
    c_T = Counter(T)
    count_S = list(c_S.values())
    count_T = list(c_T.values())
    count_S.sort()
    count_T.sort()
    is_same = True
    for s, t in zip(count_S, count_T):
        if s != t:
            is_same = False
            break

    ans = "Yes" if is_same else "No"
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9640
#include<bits/stdc++.h>
using namespace std;	
int a[100005];
int f[100005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	   scanf("%d",&a[i]);	
	int ok=1;	
	for(int i=1;i<=n;++i)
		   f[a[i]]++;
	if(n%2==0)
	{
		for(int i=0;i<n;++i)
		   if(f[i]!=0&&f[i]!=2) ok=0; 
	}
	else 
	{
		int t=1;
		for(int i=0;i<n;++i)
		{
			if(f[i]==1&&i==0) 
			{
				if(t==1)
				   t=0;
				else ok=0;
			}
			else  
			   if(f[i]!=0&&f[i]!=2) ok=0;
		} 
	}
	if(ok==0) cout<<0<<endl;
	else 
	{
		int k=1;
		for(int i=1;i<=n/2;++i)
		   k*=2,k%=1000000007;
		cout<<k<<endl; 
	}
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
# define ll int64_t
# define str string
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

ll lcm(ll a,ll b){
   return a/gcd(a,b)*b;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin>>n;
    rrep(i,9){
        if(n%i==0 && n/i<=9){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
while true
  n, x = gets.split(" ").map{|str| str.to_i}
  break if n==0&&x==0

  cnt = 0
  for i in 1..n
    for j in i+1..n
      for k in j+1..n
        cnt += 1 if i+j+k == x
      end
    end
  end
  puts cnt

end

Measured memory_bytes: 8772
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		BigInteger ans = new BigInteger("1");
		BigInteger max = new BigInteger((long) Math.pow(10, 18) + "");
		int flag = 0;
		String eatEmpty = sc.nextLine();
		String input = sc.nextLine();
		String tempInput = " " + input + " ";
		if (tempInput.contains(" 0 ")) {
			flag = 1;
			System.out.println(0);
		} else {
			String nums[] = input.split(" ");
//			System.out.println(Arrays.toString(nums));
			while (--N >= 0) {
				if (flag == 0 && max.compareTo(ans) >= 0) {
					BigInteger a = new BigInteger(nums[N]);
					ans = ans.multiply(a);
				} else if (flag == 0) {
					flag = 1;
					break;
				}
			}
			System.out.println((flag == 1 || max.compareTo(ans) < 0) ? -1 : ans);
		}
		sc.close();
	}
}


Measured memory_bytes: 70532
n=io.read("*n","*l")
a={}
l={}
r={}
for i=1,n do
    a[i]=io.read("*n")
    if not l[i+a[i]] then
        l[i+a[i]]=1
    else
        l[i+a[i]]=l[i+a[i]]+1
    end
    if not r[i-a[i]] then
        r[i-a[i]]=1
    else
        r[i-a[i]]=r[i-a[i]]+1
    end
end

combination=0
for i,_ in pairs(l) do
    if r[i] then
        combination=combination+l[i]*r[i]
    end
end
print(combination)

Measured memory_bytes: 20748
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
int c=(a+b)/2;
int d=(a+b+1)/2;
if(c>=d)cout<<c;
else cout<<d;
return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if (a < b && b < c){
    printf("Yes\n");
  }else if(a < b && c < b){
    printf("No\n");
  }else if(a == b && b < c){
    printf("No\n");
  }else if(a ==b && b == c){
    printf("No\n");
  }else if(a > b && b < c){
    printf("No\n");
      }return 0;
}
     



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
/*
整数かはできない
2^nをpopで割ったあまりを出しておくとか
N^2の処理はできない
N以下にはなる。1回のしょりで。
Nまでの値を全うめしておくとか

*/

int loop(ll n, ll pop){
  int count=0;
  while(n){
    pop=__builtin_popcount(n);
    n%=pop;
    count++;
  }
  return (count);
}
int main(){
  ll N,pop=0; cin>>N;
  string X; cin>>X;
  rep(i,N) if(X[i]=='1') pop++;
//printf("pop:%d\n",pop);
  vector<ll> P(200010,1),M(200010,1);
  rep(i,N+1){
    P[i]%=(pop+1);
    P[i+1]=P[i]*2;
    if (pop==1) M[i]=0;
    else{
      M[i]%=(pop-1);
      M[i+1]=M[i]*2;
//printf("%d,",M[i]);
    }
  }
  ll p=0,m=0;
  rep(i,N) if(X[N-1-i]=='1') p+=P[i];
  rep(i,N) if(X[N-1-i]=='1') m+=M[i];
//printf("p:%d,m:%d\n",p,m);
  for(ll i=N-1; i>=0; i--){
    ll ans=0;
    if(X[N-1-i]=='0'){
      ll pp=p+P[i];
      pp%=pop+1;
//printf("i:%d, pp:%d\n",i,pp);
      ans++;
      ans+=loop(pp, pop+1);
    }
    else{
      if(pop==1){
        cout<<0<<endl;
        continue;
      }
      ll mm=m-M[i]+(pop-1);
      mm%=pop-1;
      ans++;
//printf("i:%d, mm:%d\n",i,mm);
      ans+=loop(mm, pop-1);
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 6812
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
int ABS(int a) {if(a<0) a = -a; return a;}
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数の個数*/int divisor_number(int n){auto p = prime_factor(n); int res = 1; for(auto x:p)res*=(x.second+1); return res;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int a,b,c; cin >> a >> b >> c;
    YN((100*a+10*b+c)%4==0);

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back

signed main(){
    int n,d;
    cin>>n>>d;
    vector<int> f(n), t(n);
    rep(i,n){
        cin>>t[i]>>f[i];
        f[i]--;
    }
    
    int nowt = 0, nowf = 0, num = 0;
    
    int sum = 0;
    rep(i,n){
        if(abs(f[i]-nowf)>t[i]-nowt){
            cout<<-1<<endl;
            return 0;
        }
        if(f[i]+nowf<=t[i]-nowt){
            sum += num*nowf;
            num = 1;
            nowt = t[i];
            nowf = f[i];
        }else{
            if(num+1>d){
                cout<<-1<<endl;
                return 0;
            }
            sum += (t[i]-nowt)*num;
            num ++;
            nowt = t[i];
            nowf = f[i];
        }
    }
    sum += num*nowf;
    cout<<sum<<endl;
}

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

int main () {
  long  x;
  cin >> x;
  long a = x/11, b = x%11;
  if (b == 0) cout << 2*a << endl;
  else if (b <= 6) cout << 2*a + 1 << endl;
  else cout << 2*a +2 << endl;
}
  

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        var sc = new Scanner();
        string s = sc.next();
        int fir = int.Parse(s.Substring(0, 2));
        int sec = int.Parse(s.Substring(2, 2));
        if (1 <= fir && fir <= 12)
        {
            if (1 <= sec && sec <= 12)
            {
                Console.WriteLine("AMBIGUOUS");
            }
            else
            {
                Console.WriteLine("MMYY");
            }
        }
        else
        {
            if (1 <= sec && sec <= 12)
            {
                Console.WriteLine("YYMM");
            }
            else
            {
                Console.WriteLine("NA");
            }
        }
    }
}

// chokudai's Scanner
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 11092
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n)  { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x)         { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};
int wa[3][3]{
	{0,1,2},
	{1,1,2},
	{2,2,2}
};
int se[3][3]{
	{0,0,0},
	{0,1,1},
	{0,1,2}
};
int calc(string& s, int &idx);
int brac(string& s, int &idx);
int number(string& s, int &idx);
int calc(string& s, int &idx) {
	int val1 = brac(s, idx);
	while (s[idx] == '*' || s[idx] == '+') {
		idx++;
		if (s[idx - 1] == '+') {
			int val2 = brac(s, idx);
			val1 = wa[val1][val2];
		}
		else {
			int val2 = brac(s, idx);
			val1 = se[val1][val2];
		}
	}
	return val1;
}
int brac(string& s, int &idx) {
	int re = 0;
	while (s[idx] == '-') {
		re++;
		idx++;
	}
	if (isdigit(s[idx])) {
		int val = number(s, idx);
		if (re % 2 == 0)
			return val;
		else {
			if (re % 2 == 1)
				if (val == 0)
					val = 2;
				else if (val == 2)
					val = 0;
			return val;
		}
	}
	idx++;
	int val=calc(s, idx);
	idx++;
	if (re % 2 == 1)
		if (val == 0)
			val = 2;
		else if (val == 2)
			val = 0;
	return val;
	return val;
}
int number(string& s, int &idx) {
	int val = s[idx] - '0';
	idx++;
	
	return val;
}
int main() {
	string s;
	while (cin >> s,s!=".") {
		int ans = 0;
		REP(i,3) {
			REP(j,3) {
				REP(k,3) {
					string s2 = s;
					replace(s2.begin(), s2.end(), 'P',(char)('0'+i) );
					replace(s2.begin(), s2.end(), 'Q', (char)('0' + j));
					replace(s2.begin(), s2.end(), 'R', (char)('0' + k));
					int num = 0;
					if (calc(s2,num) == 2)
						ans++;
				}
			}
		}
		cout <<ans<< endl;
	}
}

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

int main(){
    int a, b;
    cin>>a>>b;
    if (a >= 13){
        cout<<b;
    } else if (a <= 5){
        cout<<0;
    } else{
        cout<<b/2<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    ll s;
    cin >> s;

    ll x1 = 0, y1 = 0;
    ll x2 = 1000000000, y2 = 1;
    ll x3 = (x2 - s % x2) % x2;
    ll y3 = (s + x3) / x2;

    cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;

}


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

using namespace std;

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

    if(X == 3 || X == 5 || X == 7)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=2e5;
const int inf=1e9;
long modpow(long x,int n,long p){
	int i = 0;long res = 1;
	while(n >= (1<<i)){
		if(n & (1<<i)) (res *= x) %= p;
		i++;
		x = (x * x) % p;
	}return res;
}
int main(){
	string L; cin>>L;
	long ans = 0,res = 1;
	rep(i,0,L.size()){
		if(L[i] == '1'){
			(ans += (res * modpow(3, L.size() - i - 1, mod)) % mod) %= mod;
			(res *= 2) %= mod;
        }
	}cout<<(ans + res) % mod<<endl;
}

Measured memory_bytes: 512
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<ll(n); i++)

int main(){
    unsigned long long A;
    float B;
    int b;

    cin >> A >> B;
    
    b = static_cast<int>(B * 100 + 0.5);

    cout << (A * b )/ 100 << endl;

    return 0;
}


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

int main() {
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a.rbegin(),a.rend());
  long long kotae=0;
  for(int i=0;i<k;i++){
    kotae+=a[i];
  }
  cout<<kotae<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int N, A[100000];
    int nega_num = 0, min_num = 1000000000;
    unsigned long int ans = 0;
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%d", &A[i]);
        if(A[i] < 0){
            nega_num++;
            A[i] *= -1;
        }
        if(A[i] < min_num){
            min_num = A[i];
        }
        ans += A[i];
    }
    if(nega_num % 2 == 1){
        ans -= min_num * 2;
    }
    printf("%lu\n", ans);
    return 0;
}

Measured memory_bytes: 512
from collections import deque
h, w, k = map(int, raw_input().split())
A = [raw_input() for i in xrange(h)]
sx = sy = 0
for i in xrange(h):
    idx = A[i].find('S')
    if idx != -1:
        sx = idx; sy = i
        break

deq = deque()
deq.append((0, (sx, sy)))

used = set([(sx, sy)])
dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while deq:
    cost, [x, y] = deq.popleft()
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h:
            nkey = (nx, ny)
            if A[ny][nx] != '#' and nkey not in used:
                used.add(nkey)
                if cost + 1 < k:
                    deq.append((cost+1, nkey))
ans = 10**18
for x, y in used:
    dx = min(x, w-1-x)
    dy = min(y, h-1-y)
    ans = min(ans, min(dx, dy))
print (ans+k-1)/k + 1


Measured memory_bytes: 146836
#include <stdio.h>
#define MAX 101

int main(void){
	int h,w;
	int i,j;
	int px,py;
	int end;
	int history[MAX][MAX];
	char field[MAX][MAX];
	while(1){
		scanf("%d%d",&h,&w);
		if(h == 0 && w == 0){
			break;
		}
		for(i = 0; i < h; i++){
			scanf("%s",field[i]);
		}
		for(i = 0; i < h; i++){
			for(j = 0; j < w; j++){
				history[i][j] = 0;
			}
		}
		end = 0;
		px = 0; 
		py = 0;
		history[0][0] = 1;
		while(1){
			switch(field[py][px]){
				case '<':
					px--;
					break;
				case 'v':
					py++;
					break;
				case '^':
					py--;
					break;
				case '>':
					px++;
					break;
				case '.':
					end = 1;
					break;
			}
			if(end){break;}
			if(history[py][px]){
				end = -1;
				break;
			}
			history[py][px] = 1;
		}
		if(end == 1){
			printf("%d %d\n",px,py);
		}else if(end == -1){
			puts("LOOP");
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

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

	Int N;
	cin >> N;

	vector<long double> v(N);
	for (Int i = 0; i < N; i++) {
		cin >> v[i];
	}

	sort(v.begin(), v.end());

	for (Int i = 0; i < N-1; i++) {
		v[i + 1] = (long double)(v[i] + v[i + 1]) / 2.0;
	}

	printf("%.6Lf", v[N - 1]);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
string str, ans;
int main(){
	cin >> str;
	cin >> str;
	int cnt = 0;
	ans = str;
	for (int i = 0; i < str.size(); i++){
		if (str[i] == '('){
			++cnt;
		}
		else{
			--cnt;
			if (cnt < 0)ans.insert(ans.begin(), '('), ++cnt;
		}
	}
	while (cnt){
		--cnt; ans.push_back(')');
	}
	cout << ans;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef  unsigned long long int ull;
typedef pair<ll,ll> P;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
struct mint{
    using ull=unsigned long long int;
    ull v;
    mint(ll vv=0){s(vv%mod+mod);}
    mint& s(ull vv){
        v=vv<mod?vv:vv-mod;
        return *this;
    }
    //オーバーロード
    mint operator-()const{return mint()-*this;}//符号反転
    mint&operator+=(const mint&val){return s(v+val.v);}
    mint&operator-=(const mint&val){return s(v+mod-val.v);}
    mint&operator*=(const mint&val){
        v=ull(v)*val.v%mod;
        return *this;
    }
    mint&operator/=(const mint&val){return *this*=val.inv();}
    mint operator+(const mint&val){return mint(*this)+=val;}
    mint operator-(const mint&val){return mint(*this)-=val;}
    mint operator*(const mint&val){return mint(*this)*=val;}
    mint operator/(const mint&val){return mint(*this)/=val;}
    mint pow(int n)const{
        mint res(1),x(*this);
        while(n){
            if(n&1)res*=x;
            x*=x;
            n>>=1;
        }
        return res;
    }
    mint inv()const{return pow(mod-2);}
    //拡張ユークリッドの互除法
    /* mint inv()const{
        int x,y;
        int g=extgcd(v,mod,x,y);
        assert(g==1);
        if(x<0)x+=mod;
        return mint(x);
    }*/
    friend ostream& operator<<(ostream&os,const mint&val){
        return os<<val.v;
    }//出力
    bool operator<(const mint&val)const{return v<val.v;}
    bool operator==(const mint&val)const{return v==val.v;}
    bool operator>(const mint&val)const{return v>val.v;}
};
const ll MAX = 2000010;//設定
mint fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void init(){
    fac[0] = fac[1] = 1;
    for(int i=1;i<MAX;i++)fac[i]=fac[i-1]*i;
    finv[MAX-1]=fac[MAX-1].inv();
    for(int i=MAX-2;i>=0;i--)finv[i]=finv[i+1]*(i+1);
    for(int i=MAX-2;i>=1;i--)inv[i]=finv[i]+fac[i-1];
}
//階乗
mint factor(ll n,ll k){
  if (n<k) return 0;
  if (n<0 || k<0) return 0;
  return fac[n]*finv[k];
}
// 二項係数計算
mint COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[k] * finv[n - k];
}
int main(){
ll n,a,b;
init();
cin>>n>>a>>b;
mint ans=0;
ans=mint(2).pow(n)-mint(1);
mint res=1;
mint d=mint(n);
for(int i=0;i<a;i++){
	res*=d;
	d-=1;
}
for(int i=1;i<=a;i++){
	res/=mint(i);
}
ans-=res;
res=1;
d=mint(n);
for(int i=0;i<b;i++){
	res*=d;
	d-=1;
}
for(int i=1;i<=b;i++){
	res/=mint(i);
}
cout<<ans-res<<endl;
}

Measured memory_bytes: 47104
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    S = list(readline().decode('utf-8').strip() for _ in range(H))
    dp = [[INF] * (W) for _ in range(H)]
    if S[0][0]=='#':
        dp[0][0]=1
    else:
        dp[0][0]=0
    for i in range(H):
        for j in range(W):
            if i != H-1:
                if S[i][j]=='.' and S[i+1][j]=='#':
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            if j != W-1:
                if S[i][j]=='.' and S[i][j+1]=='#':
                    dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
                else:
                    dp[i][j+1] = min(dp[i][j+1],dp[i][j])


    print(dp[H-1][W-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let m: usize = sc.read();
    if m % 2 == 1 {
        println!("-1");
        return;
    }
    let mut graph = vec![vec![]; n];
    let mut edges = vec![];
    for i in 0..m {
        let x = sc.read::<usize>() - 1;
        let y = sc.read::<usize>() - 1;
        graph[x].push((y, i));
        graph[y].push((x, i));
        edges.push((x, y));
    }

    let mut used = vec![false; m];
    let mut tree = vec![vec![]; n];
    let mut vis = vec![false; n];
    vis[0] = true;
    dfs(0, &graph, &mut used, &mut vis, &mut tree);
    let mut ans = vec![vec![]; n];
    for (v, e) in graph.into_iter().enumerate() {
        for (u, edge_id) in e.into_iter() {
            if used[edge_id] {
                continue;
            }
            used[edge_id] = true;
            ans[v].push(u);
        }
    }

    ans_dfs(0, &tree, &mut ans);

    for from in 0..n {
        for &to in ans[from].iter() {
            println!("{} {}", from + 1, to + 1);
        }
    }
}

fn ans_dfs(v: usize, tree: &Vec<Vec<usize>>, graph: &mut Vec<Vec<usize>>) {
    for &next in tree[v].iter() {
        ans_dfs(next, tree, graph);
        if graph[next].len() % 2 == 0 {
            graph[v].push(next);
        } else {
            graph[next].push(v);
        }
    }
}

fn dfs(
    v: usize,
    graph: &Vec<Vec<(usize, usize)>>,
    used: &mut Vec<bool>,
    vis: &mut Vec<bool>,
    tree: &mut Vec<Vec<usize>>,
) {
    for &(next, edge_id) in graph[v].iter() {
        if used[edge_id] {
            continue;
        }
        if vis[next] {
            continue;
        }
        vis[next] = true;
        used[edge_id] = true;
        tree[v].push(next);
        dfs(next, graph, used, vis, tree);
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 1e5 + 7 , mod = 1e9 + 7 ; 
const int inf = N ; 
// How interesting!

int n ;

int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ;
       // freopen("in.in" , "r" , stdin) ; 
        ll ans = -1e18 ; 
        ll a , b, c , d; 
        cin >> a >> b >> c >> d ;
        ans = max(ans , a * c ) ; 
        ans = max(ans , b * d) ; 
        ans = max(ans , a * d) ; 
        ans = max(ans , b * c) ; 
        cout<< ans ; 

        return 0 ; 
}

Measured memory_bytes: 3656
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <complex>
#include <numeric>
#include <string.h>
#include <random>
#include <cmath>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

string str;
int cl[500010], cr[500001];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> str;
    int si = str.size();
    rep(i,str.size()) {
        if (i) cl[i] = cl[i-1];
        else cl[i] = 0;
        if (str[i] == '<') {
            cl[i]++;
        } else {
            cl[i] = 0;
        }
    }
    for (int i = si-1; i >= 0; i--) {
        cr[i] = cr[i+1];
        if (str[i] == '>') cr[i]++;
        else cr[i] = 0;
    }
    ll ans = 0;
    rep(i,si+1) {
        int now = 0;
        now = cr[i];
        if (i != 0) {
            now = max(now, cl[i-1]);
        }
        ans += now;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4764
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

constexpr int MOD = 1000000007;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;

int main() {
    int N, x;
    cin >> N >> x;

    int z = x - N;

    if (2*abs(z)+3 > 2*N-1) {
        cout << "No" << endl;
    } else if (z > 0) {
        cout << "Yes" << endl;
        for (int j = 2*N-1; j >= N+z+2; --j) {
            cout << j << endl;
        }
        for (int j = N-1; j >= N-(z+1); --j) {
            cout << j << endl;
        }
        cout << N+z << endl;
        cout << N+z+1 << endl;
        for (int j = N+z-1; j >= N; --j) {
            cout << j << endl;
        }
        for (int j = N-(z+2); j >= 1; --j) {
            cout << j << endl;
        }
    } else {
        z = abs(z);
        const int a = 2*N;
        cout << "Yes" << endl;
        for (int j = 2*N-1; j >= N+z+2; --j) {
            cout << a-j << endl;
        }
        for (int j = N-1; j >= N-(z+1); --j) {
            cout << a-j << endl;
        }
        cout << a-(N+z) << endl;
        cout << a-(N+z+1) << endl;
        for (int j = N+z-1; j >= N; --j) {
            cout << a-j << endl;
        }
        for (int j = N-(z+2); j >= 1; --j) {
            cout << a-j << endl;
        }
    }



    return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>
#include <math.h>

using namespace std;

#define INT_MAX 100001
#define MOD 1000000007

int main(){
    int a[INT_MAX] = {0}; //dp table
    int a_e;
    int N,M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++){
        scanf("%d", &(a_e));
        if (a[a_e-1] == -1 || (a_e < 100000 && a[a_e+1] == -1) || a_e == N){
            printf("0\r\n");
            fflush(stdout);
            return 0;
        }
        a[a_e] = -1;
    }
    a[0] = 1;
    // solve by dp
    for(int i = 1; i <= N; i++){
        if (a[i] != -1){
            if (i > 1){
                if (a[i-1] == -1){
                    a[i] = a[i-2];
                }else if(a[i-2] == -1){
                    a[i] = a[i-1];
                }else{
                    a[i] = (a[i-1]+a[i-2]) % MOD;
                }
            }else{
                a[i] = 1;
            }
            /* 
            if(a[i+1] != -1){ 
                a[i+1] = a[i]+1 % MOD;
            }
            if(i < N-1 && a[i+2] != -1){ 
                if (a[i+1] != -1) a[i+2] = a[i]+1 % MOD;
                else a[i+2] = a[i];
            }*/
        }
        // printf("%d ", a[i]);
    }
    printf("%d\r\n", a[N]);
    fflush(stdout);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

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

//------------------------------------------------
int main(){
  ll a,b;
  vector<ll> n;
  cin>>a;
  b=1;
  n.assign(a,0);
  rep(i,0,a) {
    cin>>n.at(i);
  }
    sort(n.begin(),n.end());
  rep(i,1,a){
    if(n.at(i)==n.at(i-1)) {
      b=0;
      break;
    }
  }
if(b) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    int n;
    ll d;
    cin >> n >> d;
    For(i,0,n){
        ll x,y;
        cin >> x >> y;
        if(x*x + y*y <= d*d) ans++;
    }
    cout << ans << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Measured memory_bytes: 3628