akhauriyash/Code-Regression huggingface dataset:
/**
* Think twice, code once.
* 1.integer overflow(maybe even long long overflow : (a+b >= c) -> (a >= c-b)
* 2.runtime error
* 3.boundary condition
* ---------------------------------------------------------------------------------------
* Author : zzy
* Date : 2020-03-19-19.11.19 Thursday
*/
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = (int)1e6+1000;
int n, W, w[110], v[110], dp[maxn];
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    ms(dp, INF);
    dp[0] = 0;
    cin >> n >> W;
    for1(i, n) cin >> w[i] >> v[i];
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = sum; j >= 0; --j) {
            if (dp[j] != INF) {
                dp[j+v[i]] = min(dp[j+v[i]], dp[j]+w[i]);
            }
        }
        sum += v[i];
    }
    int ans = 0;
    for (int i = sum; i >= 0; --i) {
        if (dp[i] <= W) {
            ans = i;
            break;
        }
    }
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 4224
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	int N, Q;
	scanf("%d%d", &N, &Q);

	struct rw { 
		int s, t, x; 
		rw(int s = 0, int t = 0, int x = 0) :s(s), t(t), x(x) {}
	};
	rw RW[200000];
	for (int i = 0; i < N; i++) {
		int s, t, x;
		scanf("%d%d%d", &s, &t, &x);
		RW[i] = { s, t, x };
	}
	sort(RW, RW+N, [](auto &l, auto &r) { return (l.s - l.x) < (r.s - r.x); });

	int idx = 0;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	for (int i = 0; i < Q; i++) {

		int d;
		scanf("%d", &d);

		while (idx < N && RW[idx].s - RW[idx].x <= d) {
			pq.emplace(RW[idx].x, RW[idx].t - RW[idx].x);
			idx++;
		}
		while (!pq.empty() && pq.top().second <= d) pq.pop();

		printf("%d\n", (pq.empty() ? -1 : pq.top().first));

	}

	return 0;
}


Measured memory_bytes: 5232
N = int(input())
a = list(map(int, input().split()))
r = 'APPROVED'
for i in range(N):
  if a[i] % 2 ==0:
    if a[i] % 3 != 0 and a[i] % 5 != 0:
      r = 'DENIED'
      break
print(r)

Measured memory_bytes: 2940
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n, i, j, a, b;
    b=100;
    int w[110];
    int sum = 0;
    int temp = 0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>w[i];
        sum+=w[i];
    }
    for(i=0;i<n-1;i++)
    {
        temp += w[i];
        if(temp+w[i+1] >= (sum/2+sum%2))
        {
            a=abs(sum-2*temp);
            b=abs(2*(temp+w[i+1]) - sum);
            if(a<b)
            {
                cout<<a;
            }
            else
            {
                cout<<b;
            }
            break;
        }
    }
    return 0;
}


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

using namespace std;

#define int long long

const int N = 505, INF = INT_MAX;
struct Edge {
  int u, v, cap, fl;
  Edge(int _u, int _v, int _cap, int _fl) : u(_u), v(_v), cap(_cap), fl(_fl) {}
};
vector <int> ad[N];
int pre[N];
vector <Edge> e;
void add(int u, int v, int c) {
  e.push_back({u, v, c, c}); ad[u].push_back(e.size() - 1);
  e.push_back({v, u, c, c}); ad[v].push_back(e.size() - 1);
}
bool bfs(int src, int sink) {
  memset(pre, -1, sizeof(pre));
  pre[src] = -2;
  queue <int> q;
  q.push(src);
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    if(u == sink) return 1;
    for(auto &i : ad[u]) {
      if(e[i].cap > 0 && pre[e[i].v] == -1) {
        pre[e[i].v] = i;
        q.push(e[i].v);
      }
    }
  }
  return 0;
}
int flowie(int src, int sink) {
  int flow = 0;
  while(bfs(src, sink)) {
    int d = INT_MAX;
    vector <int> node;
    int v = sink;
    do {
      d = min(d, e[pre[v]].cap);
      node.push_back(pre[v]);
      v = e[pre[v]].u;
    }while(v != src);
    for(auto &i : node) e[i].cap -= d, e[i ^ 1].cap += d;
    flow += d;
  }
  if(flow >= INF) return -1;
  else return flow;
}
int n, m, st, en;
char a[N][N];
main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> m >> n;
  st = m + n + 1;
  en = st + 1;
  for(int i = 1; i <= m; ++i) {
    for(int j = 1; j <= n; ++j) {
      char x;
      cin >> x;
      if(x == 'S') {
        add(st, i, INF);
        add(st, j + m, INF);
      }
      else if(x == 'T') add(i, en, INF), add(j + m, en, INF);
      else if(x == 'o') add(i, j + m, 1);
    }
  }
  cout << flowie(st, en);
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lf;

ll A[5];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    for (ll i = 0; i < 5; i++) {
        cin >> A[i];
    }
    sort(A, A+5);
    ll ans = 1e9;
    do {
        ll cur = 0;
        for (ll i = 0; i < 5; i++) {
            cur += A[i];
            if (i < 4) {
                while (cur % 10 != 0) {
                    cur++;
                }
            }
        }
        ans = min(ans, cur);
    } while (next_permutation(A, A+5));
    cout << ans << "\n";
}

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

long long pow2(int x){
    if(x==0) return 1;
    return (2*pow2(x-1))%1000000007;
}

int main(){
    int N;
    cin >> N;
    int *cnt=new int[100000];
    for(int i=0;i<100000;i++) cnt[i]=0;

    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        cnt[a]++;
    }

    if(N%2!=0){
        if(cnt[0]!=1){
            cout << "0" << endl;
            goto btm;
        }
        for(int i=2;i<=N-1;i+=2){
            if(cnt[i]!=2){
                cout << "0" << endl;
                goto btm;
            }
        }
    }else{
        for(int i=1;i<=N-1;i+=2){
            if(cnt[i]!=2){
                cout << "0" << endl;
                goto btm;
            }
        }
    }
    cout << pow2(N/2) << endl;

btm:
    delete[] cnt;
    return 0;
}

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

def solve():
    N = int(input())
    ans = 0
    for i in range(N):
        x, u = input().split()
        x = float(x)

        if u=="JPY":
            ans += x
        else:
            ans += x*380000
    print(ans)


if __name__ == "__main__":
    solve()


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


using namespace std;


int main()
{
  int n, a[100000], ans=0;

  cin >> n;
  for (int i=0; i<n; i++) cin >> a[i];

  sort(a, a+n);

  int i=0;
  while (i<n){
    int aa = a[i], j=i+1, cnt=1;
    while (i < n && aa == a[j]){
      cnt++;
      j++;
    }
    ans += cnt%2;
    i = j;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    S,T=input().split()
    ans=''
    for i in range(N*2):
        if i%2==0:
            ans+=S[i//2]
        else:
            ans+=T[i//2]
    print(ans)
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),x=sc.nextInt(),t=sc.nextInt();
        int sum=0;
        while(n>0){
            n = n-x;
            sum = sum + t;
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 35628
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

K = ri()
A, B = rl()

for i in range(A, B+1):
	if i % K == 0:
		print('OK')
		exit()
print('NG')


Measured memory_bytes: 62076
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = Integer.parseInt(in.next());
        int first = Integer.parseInt(in.next());
        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            pos.add(Integer.parseInt(in.next()) - first);
        }
        in.close();
        Collections.sort(pos);
        
        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < num-1; i++) {
            diff.add(pos.get(i + 1) - pos.get(i));
        }
        if (num == 1) diff.add(Math.abs(pos.get(0)));
        Collections.sort(diff);
        
        int min = diff.get(0);
        int divisor = 2;
        boolean isFound = num == 1;
        table:
        while (!isFound) {
        	for(int i = 0; i < num; i++) {
        		if ( pos.get(i) % min != 0 ) {
        			break;
        		}
        		if (i == num - 1) break table;
        	}
        	if (min % divisor == 0) {
        		min /= divisor;
        	} else {
        		boolean bool = true;
        		while (bool) {
	        		if (divisor == 2) {
	        			divisor++;
	        		} else {
	        			divisor += 2;
	        		}
	        		if (min % divisor == 0) {
	        			min /= divisor;
	        			bool = false;
	        		}
        		}
        	}
        }
        System.out.println(min);
    }
}


Measured memory_bytes: 47700
#include <bits/stdc++.h>
#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define popcount(n) __builtin_popcount(n)
#define popcountll(n) __builtin_popcountll(n)
#define long long long

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef vector<int> vi;
typedef vector<pair<int, int>> vii;

const double PI = acos(-1.0), EPS = 1e-9;
const int MAXN = 100005, MAXM = 102, Mod = 998244353, MAXLog = 20;

bool isValid(long m, long k, int n, vector<long> &a, vector<long> &f) {
    for (int i = 0; i < n; ++i) {
        if (a[i] * f[i] > m) {
            long tmp = m / f[i];
            k -= a[i] - tmp;
        }
    }
    return k >= 0;
}

int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "rt", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout
            << fixed;

    int n;
    long k;
    cin >> n >> k;
    vector<long> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<long> f(n);
    for (int i = 0; i < n; ++i)
        cin >> f[i];
    sort(f.rbegin(), f.rend());
    sort(a.begin(), a.end());

    long l = -1, r = 1e12 + 12;
    while (true) {
        long m = (l + r) / 2;
        if (m == l || m == r)
            break;
        if (isValid(m, k, n, a, f))
            r = m;
        else
            l = m;
    }

    cout << r << '\n';

    return 0;
}


Measured memory_bytes: 3456
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,k = na()
    As = [a-1 for a in na()]
    memo = [[0]] + [[] for _ in range(n-1)]#何回目にそこを訪れたか
    now = 0
    time = 0
    while k > 0:
        time += 1
        now = As[now]
        k -= 1
        if len(memo[now]) < 2:
            memo[now] += [time]
        if len(memo[now]) == 2:
            shortcut = memo[now][1] - memo[now][0]
            k %= shortcut
    print(now+1)
    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 118948
#include <bits/stdc++.h>
#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define popcount(n) __builtin_popcount(n)
#define popcountll(n) __builtin_popcountll(n)
#define long long long

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<int, int> ii;
typedef pair<int, long> ill;
typedef pair<long, int> lli;
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<pair<long, long>> vll;
typedef vector<ii> vii;
typedef vector<pair<ii, int>> viii;

const double PI = acos(-1.0), EPS = 1e-9;
const int MAXN = 100005, MAXM = 102, Mod = 998244353, MAXLog = 20;


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

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int n;
    cin >> n;
    vector<int> arr(n);
    ordered_set<pair<int, int>> st;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    for (int i = 0; i < n; ++i) {
        st.insert({arr[i], i});
    }
    long ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ans += st.order_of_key({arr[i] + arr[j], 2});
//            cout << ans << '\n';
            ans -= st.order_of_key({arr[j], j + 1});
//            cout << ans << '\n';
        }
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

typedef long long ll;

ll mod=1e9+7;

ll gcd(ll n,ll m){
  if(m==0) return n;
  else return gcd(m,n%m);
}

ll lcm(ll n,ll m){
  return n/gcd(n,m)*m;
}

string bit(ll n){
  string ans="";
  while(n>0){
    char c=n%2+'0';
    ans=c+ans;
    n/=2;
  }
  return ans;
}

ll order(ll n,ll p){
  ll ans=0;
  while(n%p==0){
    ans++;
    n/=p;
  }
  return ans;
}

bool is_prime(ll n){
  if(n==1) return false;
  else{
    bool ans=true;
    for(ll i=2;i*i<=n;i++){
      if(n%i==0) ans=false;
    }
    return ans;
  }
}

ll modinv(ll a){
  ll b=mod,u=1,v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  u%=mod;
  if(u<0) u+=mod;
  return u;
}
 
ll fac[300010];
 
void modfac(){
  fac[0]=1;
  for(ll i=1;i<300010;i++){
    fac[i]=(fac[i-1]*i)%mod;
  }
}

ll modcomb(ll n,ll k){
  if(n<k) return 0;
  else return ((fac[n]*modinv(fac[k]))%mod*modinv(fac[n-k]))%mod;
}

// 仮ライブラリ（？）

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


Measured memory_bytes: 256
import numpy as np

N = int(input())
res = np.zeros(N+1)

th = int(np.sqrt(N)) + 1
for x in range(1, th):
    for y in range(1, x + 1):
        for z in range(1, y + 1):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if n > N:
                continue
            if x == y and y == z:
                res[n] += 1
            elif x == y or y == z or z == x:
                res[n] += 3
            else:
                res[n] += 6
for i in range(1, N+1):
    print(int(res[i]))

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

int const N = 40;
ll dp[N][N][N][N];
char g[N][N + 1];
int n;

inline ll &gt(int a, int b, int c, int d){
	if (d >= n){
		d -= n;
		if (c >= n)c -= n;
	}
	if (b >= n)b -= n;
	if (c < a)swap(a, c), swap(b, d);
	assert(a < n && b < n && c < n && d < n && b >= a && c > b);
	return dp[a][b][c][d];
}

int main(){
	scanf("%d", &n);
	n <<= 1;
	f(i, 0, n)scanf("%s", g[i]);
	f(i, 0, n)f(j, i + 1, n)if (g[i][j] == '1')gt(i, i, j, j) = 1;
	for (int tl = 4; tl <= n; tl += 2)f(l, 1, tl)f(i, 0, n - l)f(k, i + l, n){
		int j = i + l - 1, w = k + tl - l - 1;
		if (w >= i + n)break;
		ll &c = gt(i, j, k, w);
		if (i != j)f(a, i, j - 1)f(b, a + 2, j + 1)c += gt(i, a, b, j) * gt(a + 1, b - 1, k, w);
		else f(a, k, w - 1)f(b, a + 2, w + 1)c += gt(k, a, b, w) * gt(i, j, a + 1, b - 1);
	}
	ll an = 0;
	f(i, 0, n)an += gt(i, i, i + 1, i + n - 1);
	printf("%lld\n", n == 1 ? an : an / n);
}

Measured memory_bytes: 18176
#include <iostream>

using namespace std;

template<typename T> T gcd(T x, T y){return y? gcd(y, x%y): x;}

class Frac{
public:
    int num, den;
    Frac():num(0), den(1){}
    Frac(const Frac &f):num(f.num), den(f.den){}
    Frac(int num_, int den_):num(num_), den(den_){}
    Frac& operator-=(const Frac &f){
        int g = gcd(den, f.den);
        Frac t((num * f.den - f.num * den) / g, den * f.den / g);
        g = gcd(t.num, t.den);
        num = t.num / g; den = t.den / g;
        return *this;
    }
};

inline Frac operator-(const Frac &lhs, const Frac &rhs){
    Frac t(lhs);
    t -= rhs;
    return t;
}

inline bool operator<(const Frac &lhs, const Frac &rhs){
    return lhs.num * rhs.den < rhs.num * lhs.den;
}

int solve(Frac rem, int lo, int hi, int n){
    if(rem.num == 0)return 1;
    if(n == 0)return 0;
    int res = 0;
    for(int d=lo; d<=hi; ++d){
        if(n * rem.den < rem.num * d)break;
        if(rem < Frac(1, d))continue;
        res += solve(rem - Frac(1, d), d, hi/d, n-1);
    }
    return res;
}

int main(){
    int p, q, a, n;
    while(cin >> p >> q >> a >> n, p|q|a|n)cout << solve(Frac(p, q), 1, a, n) << '\n';
    return 0;
}

Measured memory_bytes: 1156
#include <stdio.h>//13433156参考
#define M 1000000//定義
int last[M], previousRoad[M], go[M], ans[M], visited[M], stack[M];

int i, n, m, x, y, flag = 0, re, t, l = 0, r = 1;
//nは部屋
//mは通路
int main(){
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++)
    { //道を読み取る
        scanf("%d%d", &x, &y);
        previousRoad[i] = last[x];
        last[x] = i;//iこめの道
        go[i] = y;

        previousRoad[i + m] = last[y];
        last[y] = i + m;//i個目の道(数字がかぶらないように)
        go[i + m] = x;
    }

    stack[1] = 1;
    visited[1] = 1;//closedリスト的な
    while(l<r){
        l++;//今このふかさの層に存在するノードのうちlコメを調べている
        re = stack[l]; //qはスタックreは部屋番号

        t = last[re];//部屋１を最後に現れた道番号
        while(t){
            if(!visited[go[t]]){//go[t]でその道で行き着く部屋→訪れていない時のみ処理
                visited[go[t]] = 1;//ノード　（部屋）に訪れましたよ
                r++;//他の部屋があるよ
                stack[r] = go[t]; //で子供の部屋はここ
                ans[go[t]] = re; //部屋go[t]の親部屋はre
            }
            t = previousRoad[t];//この部屋が以前出現した別の道なければwhileを抜ける
        }
        //reへやに連なる子供を見おえた

    }
    for (i = 2; i <= n;i++){
        if(!visited[i])
            flag = 1;
    }
    if(flag)
        puts("No");
    else{
        puts("Yes");
        for (i = 2; i <= n; i++)
            printf("%d\n", ans[i]);
    }
}


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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 5010;
const LL mod = 1e9 + 7;
int N;
vector<int> V[MC];
int c[MC],parent[MC];
int g = -1;
LL fct[MC+1];
LL invfct[MC+1];
LL dp[2][MC];

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MC+1){
		fct[i] = fct[i-1] * i % mod;
	}
	LL x = fct[MC];
	invfct[MC] = 1;
	for(int i = mod - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MC] *= x) %= mod;
		(x *= x) %= mod;
	}
	repm(i,MC,0){
		invfct[i-1] = invfct[i] * i % mod;
	}
}

LL func(int x , int y){
	return fct[x] * fct[x] % mod * invfct[y] % mod * invfct[x-y] % mod * invfct[x-y] % mod;
}

void dfs(int p , int q){
	bool b = 1;
	c[q] = 1;
	parent[q] = p;
	for(auto u : V[q]){
		if(u == p) continue;
		dfs(q,u);
		if(c[u]*2 >= N) b = 0;
		c[q] += c[u];
	}
	if(b && c[q] * 2 > N) g = q;
}

int main(){
	build();
	cin >> N;
	repp(i,1,N){
		int x,y;
		cin >> x >> y;
		V[x].PB(y);
		V[y].PB(x);
	}
	dfs(-1,1);
	if(g<0) return cout << fct[N/2] * fct[N/2] % mod << endl , 0;
	repp(i,0,N-c[g]+1) dp[0][i] = func(N-c[g],i);
	int z = 0;
	for(auto u : V[g]){
		if(u == parent[g]) continue;
		fill(dp[!z],dp[!z]+MC,0);
		repp(i,0,N+1){
			repp(j,0,c[u]+1){
				if(i+j>=N) break;
				(dp[!z][i+j] += dp[z][i] * func(c[u],j)) %= mod;
			}
		}
		z = !z;
	}
	LL ans = 0;
	int sgn = 1;
	repp(i,0,N){
		(ans += sgn * dp[z][i] * fct[N-i]) %= mod;
		sgn *= -1;
	}
	if(ans<0) ans += mod;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 896
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long X = sc.nextLong();
      	double rate = 1.01;
      	long money = 100;
        int ans = 0;
        while(money < X){
          money *= rate;
          ans += 1;
        }
        	System.out.println(ans);
    }
}

Measured memory_bytes: 35804
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}


int main(void) {

	lli N;
	cin >> N;

	//4,7,8,,11,12,,14,15,16,,18,19,20,21,
	//1,2,3,5,9,13,17


	if (N > 17 || (N % 4 != 1 && N % 4!= 2 && N != 3)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(a) a.begin(), a.end()
typedef long long int ll;
using namespace std;

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

    int n, k;
    cin >> n >> k;

    int ans = 0;
    if (n % k != 0)
        ans = 1;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.*
import java.util.*

const val YES = "Yes"
const val NO = "No"
fun solve(c: Array<LongArray>){
    var trace = 0L
    var v = 0L
    for (i in 0..2){
        for(j in 0..2){
            if (i==j) trace += c[i][j]
            else v += c[i][j]
        }
    }
    if (v == 2*trace){
        println(YES)
    }else(println(NO))
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val c = Array<LongArray>(3.toInt()){ LongArray(3.toInt()) }
    for (i in 0 until 3.toInt()) {
        for (j in 0 until 3.toInt()) {
            c[i][j] = sc.next().toLong()
        }
    }
    solve(c)
}



Measured memory_bytes: 29612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;
int main(){
    string s;
    cin>>s;
    int ans = 0;
    rep(i,s.size()/2)if(s[i] != s[s.size()-1-i])ans++;
    cout<<ans<<endl;
}

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

int main() {
	string S;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		if (i % 2 == 0 && (S[i] == 'R' || S[i] == 'U' || S[i] == 'D')) {
			continue;
		}
		if (i % 2 == 1 && (S[i] == 'L' || S[i] == 'U' || S[i] == 'D')) {
			continue;
		}
		else {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        for(int i = 0;i < n;i++){
            s[i] = sc.next();
        }
        Map<Character,Integer> num = new HashMap<>();
        num = createMap(s[0]);
        for(String line : s){
            Map<Character,Integer> map = createMap(line);
            for(Character key : num.keySet()){
                if(map.get(key) == null){
                    num.put(key,0);
                    continue;
                }
                if(map.get(key) != null){
                    if(num.containsKey(key) && map.get(key) < num.get(key)){
                        num.put(key,map.get(key));
                    }
                }
            }
        }
        StringBuilder str = new StringBuilder();
        for(Character key : num.keySet()){
            for(int i = 0;i < num.get(key);i++){
                str.append(key);
            }
        }

        System.out.println(str);
    }
    public static Map<Character,Integer> createMap(String s){
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0;i < s.length();i++){
            if(map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),map.get(s.charAt(i))+1);
                continue;
            }
            map.put(s.charAt(i),1);
        }
        return map;
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
int ans[200001];
int main(){
    int n,x;
    cin>>n>>x;
    if(x==1 || x == 2*n-1)cout<<"No";
    else {
        cout<<"Yes"<<endl;
        ans[n]=x;
        if(x>=n){
          int pos;
          for(int i = 1;i<=2*n-1-x;++i){
            ans[n+i] = x+i;
            pos = n+i+1;
          }
          int val = 1;
          while(pos<=2*n-1){
            ans[pos]=val;
            pos++,val++;
          }
          for(int i=1;i<=n-1;++i){
            ans[i] = val;
            val++;
          }
          for(int i = 1;i<=2*n-1;++i){
            cout<<ans[i]<<endl;
          }
        }
        else {
            ans[n] = x;
            int pos;
            int val;
            for(int i = n +1 ; i<=2*n-1 ;++i){
                ans[i] = x + i - n;
                val = ans[i] + 1;
            }
            pos=1;
            while(val<=2*n-1){
                ans[pos]=val;
                val++;pos++;
            }
            val = 1;
            for(int i = pos ; i<n;++i){
                ans[i]=val;
                val++;
            }
        for(int i=1;i<=2*n-1;++i)cout<<ans[i]<<endl;
        }
    }
}


Measured memory_bytes: 2304
program time_gap
  implicit none
  integer :: n, d(50) = 0, p(0:12) = 0, m = 48, i, j
  logical :: t(0:47) = .true., f = .false.
  read(*,*) n
  read(*,*) d(1:n)
  p(0) = 1
  do i = 1, n
    p(d(i)) = p(d(i))+1
  end do
  if (p(0) > 1 .or. p(12) > 1 .or. any(p(1:11) > 2)) then
    write(*,'(i0)') 0
    stop
  end if
  t(0) = .false.
  if (p(12) == 1) t(12) = .false.
  do i = 1, 11
    if (p(i) == 0) cycle
    if (p(i) == 2) then
      t(i) = .false.
      t(24-i) = .false.
      cycle
    end if
    if (f) then
      t(i) = .false.
    else
      t(24-i) = .false.
    end if
    f = .not.f
  end do
  t(24:47) = t(0:23)
  i = 0
  j = 1
  do while (i < 24)
    do while (t(j))
      j = j+1
    end do
    m = min(m,j-i)
    i = j
    j = j+1
  end do
  write(*,'(i0)') m
end program time_gap

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MXN 2003

int n,k,ans=1000000000,cnt;
bool flag[MXN];



struct edge{
	int fm,
		to,
		next;
}e[2*MXN];
int tot,last[MXN];
void addEdge(int u, int v){
	tot++;
	e[tot].fm=u;
	e[tot].to=v;
	e[tot].next=last[u];
	last[u]=tot;
}




void dfsPoint(int fj, int fa, int t){
	if(t>k/2)
		return;
	else
		cnt++;
	for(int i=last[fj];i;i=e[i].next)
		if(e[i].to!=fa)
			dfsPoint(e[i].to,fj,t+1);
}
void dfsEdge(int fj, int fa, int t){
	if(t>k/2)
		return;
	else{
		if(flag[fj]){
			flag[fj]=0;
			cnt++;
		}
	}
	for(int i=last[fj];i;i=e[i].next)
		if(e[i].to!=fa)
			dfsEdge(e[i].to,fj,t+1);
}

int main(){


	scanf("%d%d",&n,&k);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		addEdge(u,v);
		addEdge(v,u);
	}
	

	if(!(k&1)){
		for(int i=1;i<=n;i++){
			cnt=0;
			dfsPoint(i,0,0);
			ans=std::min(ans,n-cnt);
		}
		printf("%d\n",ans);
	}
	else{
		for(int i=1;i<n;i++){
			cnt=0;
			for(int j=1;j<=n;j++)
				flag[j]=1;
			dfsEdge(e[i].fm,0,0);
			dfsEdge(e[i].to,0,0);
			ans=std::min(ans,n-cnt);
		}
		printf("%d\n",ans);
	}
	
	//system("pause");

	return 0;
}
/*

 */

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second

signed main(){
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int a,b,c,k;
	cin >> a >> b >> c >> k;
	while(b<=a){
		b*=2;
		k--;
	}
	while(c<=b){
		c*=2;
		k--;
	}
	if(k>=0){
		cout << "Yes";
	}
	else
		cout << "No";


	
	

	return 0;
}

Measured memory_bytes: 3616
import bisect

A, B, Q = map(int, input().split())
INF = 2 * (10 ** 10)

s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]


for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b-1], s[b]] : 
        for T in [t[d-1], t[d]] : 
            d1, d2 = abs(S-x) + abs(T-S), abs(T-x) + abs(S-T)
            res = min(res, d1, d2)
    print(res)

Measured memory_bytes: 14428
N = int(input())
H = list(map(int, input().split()))

index = 0
count = 0
can_see_sea = True
for h in H:
    can_see_sea = True
    for _h in H[0:index]:
        if h < _h:
            can_see_sea = False
            continue
    if can_see_sea:
        count = count + 1
    index = index + 1

print(str(count))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<string.h>
#define ll long long 
#include<vector>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int mod=1e9+7;
int n,m;
vector<int> adj[100005];
int dp[100005];
int long_dist(int node){
	if(dp[node]!=-1)
	return dp[node];
	int ans=0;
	for(auto i:adj[node]){
		ans=max(ans, 1+long_dist(i));
	}
	return dp[node]=ans;
}
int main(){
	IOS;
	
	cin>>n>>m;
	for(int i=0,x,y;i<m;i++){
		cin>>x>>y;
		adj[x].push_back(y);
	}
	memset(dp,-1,sizeof(dp));
	
	int bestans=0;
	for(int i=1;i<=n;i++)
{
	bestans=max(bestans,long_dist(i));
}
	cout<<bestans;
}

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

const int M = 998244353, N = 3005;
long long dp[N][N];

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

    int A, B, C, D;
    cin>>A>>B>>C>>D;

    dp[A][B] = 1;

    for (int i=A+1; i<=C; i++)  dp[i][B] = (B*dp[i-1][B])%M;
    for (int i=B+1; i<=D; i++)  dp[A][i] = (A*dp[A][i-1])%M;

    for (int i=A+1; i<=C; i++) {
        for (int j=B+1; j<=D; j++) {
            dp[i][j] = (dp[i-1][j]*j+dp[i][j-1]*i)%M;
            long long ww = (1LL*(i-1)*(j-1)*dp[i-1][j-1])%M;
            dp[i][j] = (dp[i][j]+M-ww)%M;
        }
    }
    cout<<dp[C][D]<<endl;
}


Measured memory_bytes: 73932
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) a.begin(),a.end()
 
// T := [T][T]... | num 
 
int solve(string s, int &i){
    vector<int> v;
    if(isdigit(s[i])){
        int num = 0;
        while(isdigit(s[i])){
            num = num*10 + s[i]-'0';
            i++;
        }
        return num+1;
    }
    while(s[i] == '['){
        i++; // [
        v.push_back(solve(s,i));
        i++; // ]
    }
 
    sort(all(v));
    int n = v.size(), sum = 0;
    rep(k,(n+1)/2){
        sum += v[k];
    }
    return sum;
}
 
int main(void){
    int T;
    cin>>T;
    rep(_,T){
        string s;
        cin>>s;
        int index = 0;
        cout<<(solve(s,index)+1)/2<<endl;
    }
    return 0;
}


Measured memory_bytes: 3292
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

#pragma GCC target ("avx")
struct Bitvector {
  using T = uint32_t;
  static constexpr int W = 32;
  static int popcnt(T x) { return __builtin_popcount(x); }

  const int n;
  V<T> b;
  V<> c;
  Bitvector(int n) : n(n), b(n / W + 1), c(n / W + 1) {}
  void set(int i) { b[i / W] |= (T)1 << i % W; }
  void build() { for (int i = 0; i < n / W; ++i) c[i + 1] = c[i] + popcnt(b[i]); }
  bool operator[](int i) const { return b[i / W] >> i % W & 1; }
  int rank(int i) const { return c[i / W] + popcnt(b[i / W] & ~(~(T)0 << i % W)); }
  int rank(bool v, int i) const { return v ? rank(i) : i - rank(i); }
};
template<class T> struct WaveletMatrix {
  const int n, h;
  V<Bitvector> b;
  V<> z;
  template<class Itr> WaveletMatrix(Itr first, Itr last) : n(distance(first, last)), h(__lg(2 * *max_element(first, last) + 1)), b(h, Bitvector(n)), z(h) {
    assert(*min_element(first, last) >= 0);
    V<T> a(first, last), na(n);
    for (int j = 0; j < h; ++j) {
      for (int i = 0; i < n; ++i) {
        if (a[i] >> h + ~j & 1) b[j].set(i);
        else ++z[j];
      }
      b[j].build();
      int p = 0, q = z[j];
      for (int i = 0; i < n; ++i) (b[j][i] ? na[q++] : na[p++]) = a[i];
      swap(a, na);
    }
  }
  T operator[](int i) const {
    T res = 0;
    for (int j = 0; j < h; ++j) {
      T v = b[j][i];
      res |= v << h + ~j;
      i = v * z[j] + b[j].rank(v, i);
    }
    return res;
  }
  int rank(int l, int r, T x) const {
    if (x < 0 or x >= (T)1 << h) return 0;
    for (int j = 0; j < h; ++j) {
      int v = x >> h + ~j & 1;
      l = v * z[j] + b[j].rank(v, l);
      r = v * z[j] + b[j].rank(v, r);
    }
    return r - l;
  }
  T kth(int l, int r, int k) const {
    assert(0 <= k and k < r - l);
    T res = 0;
    for (int j = 0; j < h; ++j) {
      int p = b[j].rank(0, l), q = b[j].rank(0, r);
      T v = k >= q - p;
      k -= v * (q - p);
      res |= v << h + ~j;
      l = v * z[j] + (v ? l - p : p);
      r = v * z[j] + (v ? r - q : q);
    }
    return res;
  }
  T rkth(int l, int r, int k) const { return kth(l, r, r - l + ~k); }
  int cnt(int l, int r, T x) const {
    if ((x = max<T>(x, 0)) >= (T)1 << h) return 0;
    int res = 0;
    for (int j = 0; j < h; ++j) {
      int p = b[j].rank(1, l), q = b[j].rank(1, r);
      int v = x >> h + ~j & 1;
      res += !v * (q - p);
      l = v * z[j] + (v ? p : l - p);
      r = v * z[j] + (v ? q : r - q);
    }
    return res + r - l;
  }
  int cnt(int l, int r, T x, T y) const { return cnt(l, r, x) - cnt(l, r, y); }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (auto&& e : a) cin >> e;
  WaveletMatrix<int> wm(begin(a), end(a));
  int q; cin >> q;
  while (q--) {
    int l, r, d; cin >> l >> r >> d, ++r;
    int c = wm.cnt(l, r, d);
    int res = 1e9;
    if (c) res = min(res, wm.rkth(l, r, c - 1) - d);
    if (c < r - l) res = min(res, d - wm.rkth(l, r, c));
    cout << res << '\n';
  }
}


Measured memory_bytes: 4400
#include <iostream>
 
using namespace std;
 
int main() {
    int N,K;
    int array[100000] = {};
    
    cin >> N >> K;
    for (int i=0; i<N; i++) {
        cin >> array[i];
    }
    
    int cnt = 0;
    for (int i=0; i<N; i++) {
        if (array[i] >= K) {
            // 乗れる
            cnt++;
        }
    }
 
    cout << cnt << endl;
 
    return 0;
}

Measured memory_bytes: 640
def check(string1, string2):
    for i in range(len(string1)):
        if not ((string1[i] == string2[i]) and (string1[i].isalpha() and string1[i] == string1[i].lower())):
            return "No"

    last_char = string2[len(string2) - 1]
    if (1 <= len(string1) <= 10) and (len(string2) == len(string1) + 1) and (
            last_char.isalpha() and last_char == last_char.lower()):
        return "Yes"
    else:
        return "No"


s = input()
t = input()

print(check(s, t))


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

int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i=0; i<n; i++) cin >> v[i];
  vector<int>od(100001,0), ev(100001,0);
  for (int i=0; i<n; i++){
    if (i%2==0) ev[v[i]]++;
    else od[v[i]]++;
  }
  int evfir=0, evsec=0, odfir=0, odsec=0;
  int evfirind=-1,evsecind=-1,odfirind=-1,odsecind=-1;
  for (int i=0; i<100001; i++){
    if (od[i] > odfir){
      odsec = odfir;
      odfir = od[i];
      odsecind = odfirind;
      odfirind = i;
    }
    else if (od[i] > odsec){
      odsec = od[i];
      odsecind = i;
    }
    if (ev[i] > evfir){
      evsec = evfir;
      evfir = ev[i];
      evsecind = evfirind;
      evfirind = i;
    }
    else if (ev[i] > evsec) evsec = ev[i];
  }
  int ans;
  if (odfirind != evfirind) ans = n-odfir-evfir;
  else if ((odsecind==-1)&&(evsecind==-1)) ans = n/2;
  else ans = min(n-odfir-evsec, n-odsec-evfir);
  cout << ans << endl;
}


Measured memory_bytes: 1408
import math
import collections
import itertools

def YesNo(Bool):
    if(Bool):
        print("Yes")
    else:
        print("No")
    return

def resolve():

    X,K,D=map(int,input().split())

    ans=0
    if(abs(X)-K*D<0):
        tmp=X//D
        if((K-tmp)%2==0):
            ans=abs(X-D*tmp)
        else:
            ans=abs(X-D*(tmp+1))
    else:
        ans=abs(X)-K*D

    print(ans)
resolve()


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

#define loop(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < n; ++i)
#define dump(a) cerr << #a << " = " << (a) << "(L:" << __LINE__ << ")" << endl

const long long MOD = 1000000007;

void solve(long long N, std::vector<long long> A, std::vector<long long> B) {
    vector<long long> mod_pow2(200001);
    mod_pow2[0] = 1;
    loop(i, 1, 200001) {
        mod_pow2[i] = mod_pow2[i - 1] * 2;
        mod_pow2[i] %= MOD;
    }

    int zeros = 0;
    map<pair<long long, long long>, pair<int, int>> groups;
    rep(i, N) {
        if (A[i] == 0 && B[i] == 0) {
            zeros++;
        } else {
            auto g = __gcd(abs(A[i]), abs(B[i]));
            auto a = A[i] / g;
            auto b = B[i] / g;
            int rot = 0;
            while (!(0 <= a && 0 < b)) {
                swap(a, b);
                b *= -1;
                rot++;
            }
            if (rot % 2 == 0) groups[make_pair(a, b)].first++;
            if (rot % 2 == 1) groups[make_pair(a, b)].second++;
        }
    }

    long long ans = 1;
    for (auto& g : groups) {
        auto a = g.second.first;
        auto b = g.second.second;
        // cerr << "(" << g.first.first << "," << g.first.second << ")";
        // cerr << a << " " << b << endl;
        ans *= 1 + mod_pow2[a] - 1 + mod_pow2[b] - 1;
        ans %= MOD;
    }
    ans += zeros - 1;
    cout << (ans + MOD) % MOD << endl;
}

int main() {
    long long N;
    scanf("%lld", &N);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
        scanf("%lld", &B[i]);
    }
    solve(N, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 20424
while True:
    N = int(input())
    if not N: break
    ans = float('inf')
    for c200 in range(N//200+1):
        for c300 in range(N//300+1):
            for c500 in range(N//500+1):
                if 200 * c200 + c300 * 300 + c500 * 500 == N:
                    ans = min(ans, 1520*(c200//5)+380*(c200%5)+1870*(c300//4)+550*(c300%4)+2244*(c500//3)+850*(c500%3))
    print(ans)

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

int main(){
  int i,j,k;
  int minj,cnt = 0;
  int tmp;
  int N;
  int A[100];

  if(scanf("%d",&N) > 100)
    exit(1);
  for(i = 0; i < N; i++){
    scanf("%d",&A[i]);
    if(A[i] < 0 || A[i] > 100)
      exit(2);
  }

  for(i = 0; i < N; i++){
    minj = i;
    for(j = i; j < N; j++){
      if(A[j] < A[minj]){
	minj = j;

      }
    }
    tmp = A[minj];
    A[minj] = A[i];
    A[i] = tmp;
    if(A[i] != A[minj])
      cnt++;
  }
  
  for(i = 0; i < N; i++){
    printf("%d",A[i]);
    if(i != N-1)
      printf(" ");
  }
  printf("\n%d\n",cnt);
  return 0;
}



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

int main()
{
	int A, B, C;
	cin >> A >> B >> C;
	
	if(A > B)
	{
		int temp = A;
		A = B;
		B = temp;
	}
	
	int ans = 0;
	for(int i = A; i <= B; ++i)
	{
		if(C % i == 0)
		{
			++ans;
		}
	}
	
	cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3100
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
#include<typeinfo>
using namespace std;

const double pi=4*atan(1.0);

constexpr long long mod=static_cast<long long>(1e9+7);

using cWeightEdges=vector<vector<pair<int,int>>>;
using cEdges=vector<vector<int>>;

int main() {
	int n,q;
	cin>>n>>q;
	int ini=pow(2,31)-1;
	vector<int> a(n,ini);
	int backet=sqrt(n);
	vector<int> b(n/backet+1,ini);
	

	while(q>0){
		--q;
		int Q,x,y;
		cin>>Q>>x>>y;
		if(Q==0){
			a[x]=y;
			int Min=INT_MAX;
			for(int i=(x/backet)*backet;i<(x/backet)*backet+backet;++i){
				Min=min(Min,a[i]);
			}
			b[x/backet]=Min;
		}
		else{
			int ans=INT_MAX;
			if(y-x+1>=2*backet){
				int i=x;
				if(x%backet){
					for(i=x;i<(x/backet)*backet+backet;++i){
						ans=min(ans,a[i]);
					}
				}
				for(int j=i/backet;j<y/backet;++j){
					ans=min(ans,b[j]);
				}
				if(y%backet==backet-1){
					ans=min(ans,b[y/backet]);
				}
				else{
					for(int j=(y/backet)*backet;j<=y;++j){
						ans=min(ans,a[j]);
					}
				}
			}
			else{
				ans=(*min_element(begin(a)+x,begin(a)+y+1));
			}
			cout<<ans<<"\n";
		}
	}
	
	//system("pause");
	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;cin >> n;
    int total;cin >> total;
    for(int i=0;i<=n;i++){
        for(int j=0;i+j<=n;j++){
            int k=n-i-j;
            if(10000*i+5000*j+1000*k==total){
                printf("%d %d %d\n",i,j,k);
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <list>
#include <chrono>
#include <thread>
#include <thread>
#include <fstream>

using namespace std;

//const bool debug = false;

#ifndef M_PI
    const double M_PI = acos(-1.0);
#endif // M_PI

#define y1 roman_kaban
#define rank oryshych_konb
#define ull unsigned long long
#define ll long long
const int mod = int(1e9) + 7;
//const int inf = 1e7;
//const long long infLL = 1e16;
//const int MX2 = 10100500; //  e7
//const long long INF = 1e18 + 0.5;
const int MX = 100500; //       e6

int a[MX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("/Users/ozzy/Documents/in.txt","r", stdin);
    for(int i = 0; i < 4; i++){
        cin >> a[i];
    }
    for(int i = 1; i < 4; i++){
        a[i] = min(a[i], 2 * a[i - 1]);
    }
    int n;
    cin >> n;
    long long ans = n / 2; ans *= a[3];
    if(n & 1) ans += a[2];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1020
package main

import (
	"fmt"
)

func main() {
	var a, b, c, d, e, k int
	fmt.Scan(&a)
	fmt.Scan(&b)
	fmt.Scan(&c)
	fmt.Scan(&d)
	fmt.Scan(&e)
	fmt.Scan(&k)
	ret := k < e-a
	if ret {
		fmt.Println(":(")
	} else {
		fmt.Println("Yay!")
	}
}

Measured memory_bytes: 512
//According to all known laws of aviation, there is no way that a bee should be able to fly.
//Its wings are too small to get its fat little body off the ground. The bee, of course, flies anyway.
//Because bees don't care what humans think is impossible.
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define mod 1000000007
using namespace std ;
using bigint = long long int ;
using vi = vector<int> ;
using vll = vector<long long int> ;

int main(){
    FAST_IO ;
    int N ; cin >> N ;
    bigint arr[N] , XOR = 0 ;
    for( int i = 0 ; i < N ; i++ ){
        cin >> arr[i] ;
        XOR ^= arr[i] ;
    }
    for( int i = 0 ; i < N ; i++ ){
        cout << (arr[i] ^ XOR) << " " ;
    }
    cout << endl ;
    return 0 ;
}


Measured memory_bytes: 5152
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    rep(i,n){
        cout << s.at(i) << t.at(i);
    }
    cout << endl;
}


Measured memory_bytes: 256
#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>;

const int MX=0;
int n,k,l,r;

void solve(void){
    cin>>n;
    priority_queue<P>a,b;
    ll ans=0;
    rep(i,n){
        cin>>k>>l>>r;
        if(l>r)a.emplace(P(k-1,l-r)),ans+=r;
        else b.emplace(P(n-k-1,r-l)),ans+=l;
    }
    int x=a.size(),y=b.size();
    priority_queue<int>q1,q2;
    for(int i=x-1; i>=0; --i){
        while(!a.empty()){
            if(a.top().first>=i){
                q1.emplace(a.top().second);
                a.pop();
            }
            else break;
        }
        if(!q1.empty()){
            ans+=q1.top();
            q1.pop();
        }
    }
    for(int i=y-1; i>=0; --i){
        while(!b.empty()){
            if(b.top().first>=i){
                q2.emplace(b.top().second);
                b.pop();
            }
            else break;
        }
        if(!q2.empty()){
            ans+=q2.top();
            q2.pop();
        }
    }
    cout<<ans<<endl;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 5844