akhauriyash/Code-Regression huggingface dataset:
h, w = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)
d = gets.split.map(&:to_i)
s = []
s << [-1] * (w + 4)
s << [-1] * (w + 4)
h.times do
  s << [-1] * 2 + gets.chomp.chars.map { _1 == '#' ? -1 : 0 } + [-1] * 2
end
s << [-1] * (w + 4)
s << [-1] * (w + 4)
u = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2],
    [-1, -2], [-1, -1], [-1, 1], [-1, 2],
    [0, -2], [0, 2],
    [1, -2], [1, -1], [1, 1], [1, 2],
    [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
  ]
que = []
que << [c[0] + 1, c[1] + 1]
s[c[0] + 1][c[1] + 1] = 1
while que.size > 0
  h = {}
  while que.size > 0
    y, x = que.shift
    cnt = s[y][x]
    if s[y + 1][x] == 0
      s[y + 1][x] = cnt
      que << [y + 1, x]
    elsif s[y + 1][x] == -1
      h[[y, x]] = 1
    end
    if s[y - 1][x] == 0
      s[y - 1][x] = cnt
      que << [y - 1, x]
    elsif s[y - 1][x] == -1
      h[[y, x]] = 1
    end
    if s[y][x + 1] == 0
      s[y][x + 1] = cnt
      que << [y, x + 1]
    elsif s[y][x + 1] == -1
      h[[y, x]] = 1
    end
    if s[y][x - 1] == 0
      s[y][x - 1] = cnt
      que << [y, x - 1]
    elsif s[y][x - 1] == -1
      h[[y, x]] = 1
    end
  end
  h.keys.each do |k|
    y, x = k
    cnt = s[y][x]
    u.each do |j, i|
      if s[y + j][x + i] == 0
        s[y + j][x + i] = cnt + 1
        que << [y + j, x + i]
      end
    end
  end
end
puts s[d[0] + 1][d[1] + 1] - 1

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

using namespace std;

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

    priority_queue<long long> pq;
    long long a;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        pq.push(a);
    }

    for (int i = 0; i < m; ++i) {
        a = pq.top() / 2;
        pq.pop();
        pq.push(a);
    }

    long long ans = 0;
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }

    cout << ans << endl;
    return 0;
}

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

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

int helper(vector<int>& arr, int n){
	unordered_set<int> s; 
    int max_ele = INT_MIN; 
    for (int i = 0; i < n; i++) { 
        s.insert(arr[i]); 
        max_ele = max(max_ele, arr[i]); 
    } 
    unordered_set<int> res; 
    for (int i = 0; i < n; i++) { 
        if (arr[i] != 0) { 
            for (int j = arr[i] * 2; j <= max_ele; j += arr[i]) { 
                if (s.find(j) != s.end()) 
                    res.insert(j); 
            } 
        } 
    } 
    unordered_map<int, int> mp; 
    for (int i = 0; i < n; i++) 
        mp[arr[i]]++; 
    unordered_map<int, int>::iterator it; 
    vector<int> ans; 
    for (it = mp.begin(); it != mp.end(); it++) { 
        if (it->second >= 2) { 
            if (res.find(it->first) == res.end()) { 
                int val = it->second;  
                while (val--) 
                    ans.push_back(it->first); 
            } 
        } 
  
        if (res.find(it->first) != res.end()) { 
            int val = it->second; 
            while (val--) 
                ans.push_back(it->first); 
        } 
    } 
    return ans.size();
}

int main()  
{ 
    FAST_INP;
    int t; 
    cin >> t;
    vector<int> arr(t);
    for(int i=0;i<t;i++) cin >> arr[i];
    cout << ( t - helper(arr,t) )  << endl;
    return 0;
} 

Measured memory_bytes: 30500
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000000000000;
const int MOD=1000000007;

int N,Q;
string S;
char T[200010],D[200010];

signed main(){
	cin>>N>>Q>>S;
	REP(i,Q){
		cin>>T[i]>>D[i];
	}
	int ok=-1,ng=N;
	while(abs(ok-ng)>1){
		bool flag=false;
		int mid=(ok+ng)/2;
		int now=mid;
		REP(i,Q){
			if(T[i]==S[now]){
				if(D[i]=='R'){
					now++;
				}
				else{
					now--;
				}
				if(now<0){
					flag=true;
					break;
				}
				if(N<=now){
					flag=false;
					break;
				}
			}
		}
		if(flag==true){
			ok=mid;
		}
		else{
			ng=mid;
		}
	}
	int E=ok+1;
	ok=N,ng=-1;
	while(abs(ok-ng)>1){
		int mid=(ok+ng)/2;
		bool flag=false;
		int now=mid;
		REP(i,Q){
			if(T[i]==S[now]){
				if(D[i]=='R'){
					now++;
				}
				else{
					now--;
				}
				if(N<=now){
					flag=true;
					break;
				}
				if(now<0){
					flag=false;
					break;
				}
			}
		}
		if(flag==true){
			ok=mid;
		}
		else{
			ng=mid;
		}
	}
	int F=ok;
	cout<<N-min(N,E+(N-F))<<endl;
	return 0;
}


Measured memory_bytes: 900
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#define lli long long int
int main(){
  lli i,j,n,sum=0;
  cin>>n;
  lli a[n+1],b[n];
  for(i=0;i<n+1;i++){
    cin>>a[i];
  }
  for(i=0;i<n;i++)
    cin>>b[i];
  lli fa=min(a[0],b[0]);
  lli fb=min(a[1],b[0]-fa);
  sum=fa+fb;
  for(i=1;i<n;i++){
    fa=min(a[i]-fb,b[i]);
    //a[i+1]=a[i+1]-fa;
    fb=min(a[i+1],b[i]-fa);
    sum=sum+fa+fb;
  }
  cout<<sum;
  return 0;
}

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

#define fr(i, n)    for(int i=0; i<(int)n; ++i)
#define rfr(i, n)   for(int i=(int)n-1; i>=0; --i)
#define foor(i,a,n) for(int i=a; i<=(int)n; ++i)
#define rfoor(i,n,a)for(int i=(int)n; i>=a; --i)
#define foru(it, v) for(auto it : v)
#define si(n)       scanf("%d", &n)
#define si2(n,m)    scanf("%d%d", &n, &m)
#define si3(n,m,l)  scanf("%d%d%d", &n, &m, &l)
#define sl(n)       scanf("%lld", &n)
#define sl2(n,m)    scanf("%lld%lld", &n, &m)
#define sl3(n,m,l)  scanf("%lld%lld%lld", &n, &m, &l)
#define sd(n)       scanf("%lf", &n)
#define sld(n)      scanf("%Lf", &n)
#define sc(n)       scanf(" %c", &n)
#define sstr(n)     scanf("%s", n)
#define pi(n)       printf("%d\n", n)
#define pis(n)      printf("%d ", n)
#define pi2(n,m)    printf("%d %d\n", n, m)
#define pi3(n,m,l)  printf("%d %d %d\n", n, m, l)
#define pl(n)       printf("%lld\n", n)
#define pls(n)      printf("%lld ", n)
#define pl2(n,m)    printf("%lld %lld\n", n, m)
#define pl3(n,m,l)  printf("%lld %lld %lld\n", n, m, l)
#define pc(n)       printf("%c", n)
#define pstr(n)     printf("%s\n", n)
#define pstr2(n, m) printf("%s %s\n", n, m)
#define ff          first
#define ss          second
#define all(v)      v.begin(), v.end()
#define rall(v)     v.rbegin(), v.rend()
#define sz(v)       (int)v.size()
#define pub         push_back
#define pob         pop_back()
#define mmst(a, n)  memset(a, n, sizeof a);
#define ppcnt(n)    __builtin_popcountll(n);
#define leadingZ(n) __builtin_clz(n)
#define trailingZ(n)__builtin_ctz(n)
#define OO          0x3f3f3f3f
#define OOLL        0x3f3f3f3f3f3f3f3f
#define MOD         1000000007
#define EPS         0.000000001
#define ndl         "\n"
#define fastin      ios::sync_with_stdio(false); cin.tie(nullptr);
#define infile      freopen("input.txt", "r", stdin);
#define outfile     freopen("output.txt", "w", stdout);
#define PNO         printf("NO\n")
#define PYES        printf("YES\n")
#define pno         printf("No\n")
#define pyes        printf("Yes\n")
#define pln         printf("\n")

//#define row         vector<long long>
//#define matrix      vector<row>
//#define ROWS(v)     (v).size()
//#define COLS(v)     (v)[0].size()

#define DBG1(x)     cerr<<#x<<":"<<(x)<<'\n';
#define DBG2(x, y)  cerr<<#x<<":"<<(x)<<"  "<<#y<<":"<<(y)<<'\n';
#define DBG3(x,y,z) cerr<<#x<<":"<<(x)<<"  "<<#y<<":"<<(y)<<"  "<<#z<<":"<<(z)<<'\n';

using namespace std;

typedef long long lld;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vii;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<long long , long long>> vpll;
typedef complex<double> point;

const int N = 1e5 + 9;

int t, id, n, m, x, y, k, c, xx, yy, ans;
//int a[N], f[N], cu[N], b[N];
vii v, adj[N];
bool fl, ok;
lld res, tot, sum;
char ch;
//string s, z;
char s[N], z[N];

set<pii> st;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //fastin;
    si2(n, k);
    sstr(s);
    for(int i = 0; s[i+1]; ++i) ans += s[i] == s[i+1];
    ans = min(ans+(k<<1), n-1);
    pi(ans);
    return 0;
}


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

int main() {
    int N, M;
    cin >> N >> M;
    int A[M];
    for (int i=0; i<M; i++) {
        cin >> A[i];
    }

    int work_days = 0;
    for (int i=0; i<M; i++) {
        work_days += A[i];
    }
    if (work_days <= N) {
        cout << N-work_days << endl;
    } else {
        cout << -1 << endl;
    }



    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
const int MAX = 1000000010;
const ll MOD = 1000000007;
const double PI = acos(-1);

int main() {
    int n; cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];

    if (n % 2 == 0) {
        for (int i = n - 1; i >= 1; i = i - 2) {
            cout << A[i] << " ";
        }
        for (int i = 0; i < n; i = i + 2) {
            cout << A[i] << " ";
        }
        cout << endl;
    } else {
        for (int i = n - 1; i >= 0; i = i - 2) {
            cout << A[i] << " ";
        }
        for (int i = 1; i < n; i = i + 2) {
            cout << A[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 4040
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int cnt=0;
	for(int i=s.size()/2-1;i>=0;i--){
		for(int k=0;k<i;k++){
			if(s[k]==s[k+i]){
				cnt++;
			}
		}
		if(cnt==i){
			cout<<i*2<<endl;
			break;
		}
		cnt=0;
	}
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	ll x;
 	cin>>x;
 	ll sum=100;
 	for(ll i=1;i<1e6;i++)
 	{
 		ll in = sum/100;
 		sum+=in;
 		if(sum>=x)
 		{
 			cout<<i<<endl;
 			return 0;
 		}
 	}
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep_r(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vp vector<pii>
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define INF 1e9
#define LLINF 1e18
#define PI (acos(-1))
#define MOD 1e9+7

//Pn = a + (a-1)(n-1)
int main(){
	int a, b;
	cin >> a >> b;
	
	rep(i, 100){
		if(b <= a + (a - 1)*(i - 1)){
			cout << i << endl;
			return 0;
		}
	}

}
		

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

li_n = list(range(1 , n + 1))
for _ in range(k):
    d = int(input())
    li_a = list(map(int, input().split()))
    for a in li_a:
        if a in li_n:
            li_n.remove(a)
print(len(li_n))


Measured memory_bytes: 9168
import heapq
x,y,z,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True);B.sort(reverse=True);C.sort(reverse=True)
hq=[]
heapq.heappush(hq,(-(A[0]+B[0]+C[0]),0,0,0))
searched={(0,0,0)}
a,b,c=0,0,0
D=((1,0,0),(0,1,0),(0,0,1))
for _ in range(k):
    abc,a,b,c=heapq.heappop(hq)
    print(-abc)
    for dx,dy,dz in D:
        if not (a+dx,b+dy,c+dz) in searched:
            if a+dx<x and b+dy<y and c+dz<z:
                heapq.heappush(hq,(-(A[a+dx]+B[b+dy]+C[c+dz]),a+dx,b+dy,c+dz))
                searched.add((a+dx,b+dy,c+dz))

Measured memory_bytes: 5236
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#include <atcoder/modint>
#include <atcoder/lazysegtree>

using mint = atcoder::modint998244353;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

const mint TEN = 10;
vector<mint> P10;
const mint inv9 = mint(9).inv();

struct S {
   mint val;
   int len;
};

S merge(S l, S r) {
   return S {l.val * P10[r.len] + r.val, l.len + r.len};
}

S e() {
   return S {mint(0), 0};
}

using F = int;

// (f o g)(x) = f(g(x))
F composition(F f, F g) {
   return f >= 0 ? f : g;
}

S mapping(F f , S x) {
   if (f >= 0)
      return S { (P10[x.len] - 1) * inv9 * f, x.len };
   else
      return x;
}

F id() {
   return -1;
};

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int N, Q;
   cin >> N >> Q;

   P10.assign(N+2, mint(0));
   P10[0] = mint(1);
   FOR(n, 1, N+1)
      P10[n] = P10[n-1] * 10;

   vector<S> ones(N, S {mint(1), 1});
   atcoder::lazy_segtree<S, merge, e, F, mapping, composition, id> ST(ones);

   FOR(q, 1, Q) {
      int L, R, D;
      cin >> L >> R >> D;
      --L, --R;
      ST.apply(L, R+1, D);
      S res = ST.all_prod();
      cout << res.val.val() << '\n';
   }

   return 0;
}


Measured memory_bytes: 10572
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;

	char buf[L], *S , *T, c;

	char getchar() {
		if(__builtin_expect(S == T, 0)) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}

	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}

	unsigned inpu()
	{
		unsigned x = 0; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar());
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x;
	}

	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}

	char B[45], *outs=B+40, *outr=B+40;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;

		if(!a)*--outs = '0';
		else
			while(a)
				*--outs = (a % 10) + 48, a /= 10;

		if(x)
			*--outs = x;

		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inpu;
using io :: inp_ll;

using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll px, py;
	ll d = exgcd(b, a%b, px, py);
	x = py;
	y = px-a/b*py;
	return d;
}

template<class T>
inline void freshmin(T &a, const T &b)
{
	if (a > b) a = b;
}

template<class T>
inline void freshmax(T &a, const T &b)
{
	if (a < b) a = b;
}

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

ll calc(ll a, ll b, ll d)
{
	return b/d-(a-1)/d;
}

int main()
{
	
	ll a, b;
	int c, d;
	cin >> a >> b >> c >> d;
	ll e = __gcd(c, d);
	e = (ll)c/e*d;
	cout << (b-a+1)-(calc(a, b, c)+calc(a, b, d)-calc(a, b, e)) << endl;
	
	return 0;
}


Measured memory_bytes: 256
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

pub fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        x.abs()
    } else {
        gcd(y, x % y)
    }
}

fn main() {
    let N = read!(usize);
    let T = read![i64; N];

    let mut x = 1;
    for &t in &T {
        x = x / gcd(x, t) * t;
    }

    println!("{}", x)
}


Measured memory_bytes: 4352
import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}
auto readDoubles() {
	return array(map!(to!double)(readln().strip().split()));
}

void main() {
	while(!stdin.eof()) {
		auto t = readDoubles();
		if(t.length != 2) {
			break;
		}
		if(t[0] < 35.5 && t[1] < 71) {
			writeln("AAA");
			continue;
		}
		if(t[0] < 37.5 && t[1] < 77) {
			writeln("AA");
			continue;
		}
		if(t[0] < 40 && t[1] < 83) {
			writeln("A");
			continue;
		}
		if(t[0] < 43 && t[1] < 89) {
			writeln("B");
			continue;
		}
		if(t[0] < 50 && t[1] < 105) {
			writeln("C");
			continue;
		}
		if(t[0] < 55 && t[1] < 116) {
			writeln("D");
			continue;
		}
		if(t[0] < 70 && t[1] < 148) {
			writeln("E");
			continue;
		}
		writeln("NA");
	}
}

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

int main() {
	int a, b, c;
	int count = 0;
	cin >> a >> b >> c;
	for (int i = a; i <= b; i++) {
		if (c % i == 0)
			count++;
	}
	cout << count << endl;
	return 0;
}


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

int main() {
  string s;
  cin >> s;
  int r = 0, t = 0;
  for (auto e : s) {
    if (e == 'A' || e == 'C' || e == 'G' || e == 'T') {
      t++;
      r = max(r, t);
    } else {
      t = 0;
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c; cin >> a >> b >> c;
    cout << (c-b==b-a ? "YES" : "NO");
    cout << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

ll INF = (1ll << 32);
double EPS = 1e-4;

ll MOD = 1000000007;

int isPrime(ll x) {
  for (ll i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}

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

  unordered_map<ll, ll> m;
  for (ll i = 2; i <= N; i++) {
    ll j = 2;
    ll k = i;
    while (true) {
      if (k == 1) {
        break;
      }
      if (k % j == 0) {
        m[j] += 1;
        k /= j;
        continue;
      }
      j++;
      while (!isPrime(j)) {
        j++;
      }
    }
  }

  vi v;
  for (auto p: m) {
    v.push_back(p.second);
  }

  ll ans = 0;
  for (ll i: v) {
    if (i >= 74) {
      ans++;
    }
  }

  for (ll i = 0; i < v.size(); i++) {
    for (ll j = 0; j < v.size(); j++) {
      if (i != j) {
        if (v[i] >= 2 && v[j] >= 24) {
          ans += 1;
        }
        if (v[i] >= 4 && v[j] >= 14) {
          ans += 1;
        }
      }
    }
  }

  for (ll i = 0; i < v.size(); i++) {
    for (ll j = 0; j < v.size(); j++) {
      for (ll k = j + 1; k < v.size(); k++) {
        if ((i - j) * (j - k) * (k - i)) {
          if (v[i] >= 2 && v[j] >= 4 && v[k] >= 4) {
            ans += 1;
          }
        }
      }
    }
  }

  cout << ans << endl;
}

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

int main() {
    int n;
  int a[100];
  string t;
  cin >> n;
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }

  for(int i=0;i<n;i++){
      if(a[i]%2 ==1){t="APPROVED";}
      else{
          if(a[i]%3==0){t="APPROVED";}
          else if(a[i]%5==0){t="APPROVED";}
          else {
              t="DENIED";
              break;
          }
      }

  }
  cout << t << endl;
}

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

#define mod 1000000007

using namespace std;
typedef long long ll; 
 
int main(void){
	
	int N, D;
	double count = 0, len1;
	
	cin >> N >> D;
	
	double X[D][N];
	
	for(int i=0; i<N; i++){
		for(int j=0; j<D; j++)
			cin >> X[j][i];
	}
	
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			len1 = 0;
			for(int k=0; k<D; k++){
				len1 += (X[k][i] - X[k][j]) * (X[k][i] - X[k][j]);
			}
			if((int)(sqrt(len1)) == sqrt(len1))
				count++;
		}
	}
	
	
	cout << count;
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  
  int A[100], flag = 1, j, N, sort, i = 0, n = 0, minj;

  scanf("%d", &N);
  for(j = 0;j < N;j++){
    scanf("%d", &A[j]);
  }

  for(i = 0;i <= N - 1;i++){
    minj = i;
    for(j = i;j <= N - 1;j++){
      if(A[j] < A[minj])
	minj = j;      
    }
    if(A[i] != A[minj]) n++;
    sort = A[i];
    A[i] = A[minj];
    A[minj] = sort;
  }

  for(j = 0;j < N;j++){
    if(j) printf(" ");
    printf("%d",A[j]);
  }
  printf("\n%d\n",n);

  return 0;
}
	

			      
    



Measured memory_bytes: 2144
from collections import deque

def main():

    grid = []
    h,w = 0,0
    y = [1,0,-1,0]
    x = [0,1,0,-1]
    inf = 11
    gy,gx = 0,0
    ans = inf

    def inside(i,j):
        return 0<=i and i<h and 0<=j and j<w 

    def dfs(cy,cx,count):
        nonlocal ans
        if 10<count:return inf
        if ans<=count:return inf
        res = inf
        for i in range(4):
            ny = cy+y[i]
            nx = cx+x[i]
            if not inside(ny,nx):continue
            if grid[ny][nx] == 1:continue
            while True:
                if ny==gy and nx==gx:
                    ans = min(ans,count+1)
                    return count+1
                if not inside(ny+y[i],nx+x[i]):break
                if grid[ny+y[i]][nx+x[i]] == 1:break
                ny += y[i]
                nx += x[i]
            if not inside(ny+y[i],nx+x[i]):continue
            grid[ny+y[i]][nx+x[i]] = 0
            res = min(res,dfs(ny,nx,count+1))
            grid[ny+y[i]][nx+x[i]] = 1
        return res

    while True:
        w,h = map(int,input().split())
        if h == 0:break
        grid = []
        ans = inf
        for _ in range(h):
            grid.append(list(map(int,input().split())))
        sy,sx = 0,0
        for i in range(h):
            for j in range(w):
                if grid[i][j] == 2:
                    grid[i][j] = 0
                    sy,sx = i,j
                if grid[i][j] == 3:
                    grid[i][j] = 0
                    gy,gx = i,j
        res = dfs(sy,sx,0)
        if res == inf:res = -1
        print(res)


if __name__ == '__main__':
    main()



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

int v[100005], c[100005];
int main(){
 	int n;
 	cin>>n;
 	for(int i=1;i<=n;i++) cin>>v[i];
 	for(int i=1;i<=n;i++) cin>>c[i];
 	vector< int > vc;
    for(int i=1;i<=n;i++) vc.push_back(v[i]-c[i]);
    sort(vc.rbegin(), vc.rend());
    int mx=0, sum=0;
    for(int i=0;i<vc.size();i++){
        sum+=vc[i];
        mx=max(mx, sum);
    }
    cout<<mx<<endl;
 }

Measured memory_bytes: 256
#include <stdio.h>   
char c[256];   
void clear() {  
 int i; for (i = 0; i < 256; i++) c[i] = 0; }  
 int main() {  
 int n;  
 char f, t;  
 while (1) {    
 scanf("%d\n", &n);   
  if (!n) break;       
    clear();   
  while (n--) {    
   scanf("%c %c\n", &f, &t);    
   c[f] = t;    
 }        
   scanf("%d\n", &n);   
  while (n--) {    
   scanf("%c\n", &f);   
    if (c[f]) printf("%c", c[f]);    
   else printf("%c", f);  
   }   
  printf("\n");  
 }  
 return 0; 
} 

Measured memory_bytes: 1004
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  vint d(N);
  repeat(i,N){
    cin>>d[i];
  }
  sort(d.begin(),d.end());
  d.erase(unique(d.begin(),d.end()),d.end());
  cout << d.size()<<endl;
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

def floor_sum(n, m, a, b):
    ret = 0
    while True:
        if a >= m:
            ret += (a // m) * (n - 1) * n // 2
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        if a * n + b < m:
            return ret
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        ret += (n - (x_max + a - 1) // a) * y_max
        n = y_max
        m, a, b = a, m, -x_max % a


input = sys.stdin.buffer.readline

T = int(input())
for _t in range(T):
    N, M, A, B = map(int, input().split())
    print(floor_sum(N, M, A, B))


Measured memory_bytes: 70468
n = int(input())
a = list(map(int, input().split()))
d1 = []
d2 = []
d1.append(a[0])
d2.append(a[-1])

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


g = a[0]
for i in range(1, n - 1):
    g = gcd(g, a[i])
    d1.append(g)

g = a[-1]
for i in range(n - 2, 0, -1):
    g = gcd(g, a[i])
    d2.append(g)

d2 = d2[::-1]
d1 = [0] + d1
d2.append(0)
num = 0
for i in range(n):
    num = max(num, gcd(d1[i], d2[i]))
print(num)


Measured memory_bytes: 14052
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 2e5 + 5;
int n;
char tmp[maxn];
string s;

int read() {
  if (scanf("%s", tmp) < 1) {
    return false;
  }
  s = tmp;
  n = sz(s);
  return true;
}

const int sigma = 26;
int msk[maxn];
int dp[maxn];

void solve() {
  msk[0] = 0;
  for (int i = 0; i < n; i++) {
    msk[i + 1] = (msk[i] ^ (1 << (s[i] - 'a')));
  }
  map<int, int> lst;
  dp[0] = 0;
  lst[msk[0]] = 0;
  for (int i = 0; i < n; i++) {
    auto &cur = dp[i + 1];
    cur = inf;
    int x = msk[i + 1];
    if (__builtin_popcount(x) <= 1) {
      cur = 1;
    } else {
      for (int bit = 0; bit <= sigma; bit++) {
        int y = x;
        if (bit < sigma) {
          y ^= (1 << bit);
        }
        auto it = lst.find(y);
        if (it != lst.end()) {
          cur = min(cur, dp[it->second] + 1);
        }
      }
    }
    lst[x] = i + 1;
  }
  printf("%d\n", dp[n]);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


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

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

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

  int D = 0;

  for(int i=0; i<N-1; i++){
    D = max(D, d[i]);

    if(D<10){
      cout << "no" << endl;
      return 0;
    }
    D -= 10;
  }

  D = 0;
  for(int i=N-1; i>0; i--){
    D = max(D, d[i]);

    if(D<10){
      cout << "no" << endl;
      return 0;
    }
    D -= 10;
  }
  cout << "yes" << endl;
  return 0;
}


Measured memory_bytes: 4272
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int main() {
  string s;
  cin >> s;
  ll ans = 0;
  for(int mask = 0; mask < (1<<(s.length() -1)); mask++){
      ll num = s[0] - '0';
      for(int i=0; i<s.length() -1; i++){
          if(mask & (1 << i)){
              ans += num;
              num = 0;
          }
          num = num * 10 + (s[i+1] - '0');
      }
      ans += num;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	long long int n, x;
	scanf("%lld%lld", &n, &x);
	long long int i;
	long long int sum[55];
	sum[0] = 1;
	for (i = 1; i <= n; i++)
		sum[i] = 2 * sum[i - 1] + 3;
	long long int p[55];
	p[0] = 1;
	for (i = 1; i <= n; i++)
		p[i] = 2 * p[i - 1] + 1;
	long long int ans = 0;
	i = n;
	while (x > 0)
	{
		if (sum[i] > x)
		{
			i--;
			x--;
			continue;
		}
		if (sum[i] <= x)
		{
			ans += p[i];
			x -= sum[i];
		}
		if (x > 0)
		{
			x--;
			ans++;
		}
		if (sum[i] <= x)
		{
			ans += p[i];
			x -= sum[i];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=1;i<=n;i++)
using namespace std;
const ll INF = 1001001001001;
bool visit[303][303];

int nap(int a,int b,int c){
    int ans = 0;
    repp(i,c/a){
        repp(j,c/b){
            if(a*i+b*j <= c && ans <= a*i+b*j) ans = a*i+b*j;
        }
    }
    return ans;
}
int main(){
    int a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;
    double max = 0;
    int ans1=0,ans2=0;
    //1,2 *30
    for(int i=0;i<=(f/a)+1;i++){
        for(int j=0;j<=(f/b)+1;j++){
            int res = f-100*(a*i+b*j);
            int sug = 0;
            if(res<=0) continue;
            else{
                for(int q=0;q<=res/c;q++){
                    for(int w=0;w<=res/d;w++){
                        if(c*q+d*w <= res && sug <= c*q+d*w && c*q+d*w <= (i*a+j*b)*e) sug = c*q+d*w;
                    }
                }
                if( max <= (double)sug/(sug+(a*i+b*j)*100) ){
                    max = (double)sug/(sug+(a*i+b*j)*100);
                    ans1 = sug+(a*i+b*j)*100;
                    ans2 = sug;
                }
            }
        }
    }
    cout << ans1 << " " << ans2 << endl;
}


Measured memory_bytes: 256
use std::io;


fn read_line() -> String {
    let mut line = String::new();

    io::stdin().read_line(&mut line)
        .expect("Failed to read line");
    return line;
}
fn to_i(s: &str) -> i64 {
    return s.trim().parse()
        .expect("Please type a number!");
}
fn read_nums() -> Vec<i64>
{
    let line = read_line();
    let items: Vec<&str> = line.split(' ').collect();

    let mut nums: Vec<i64> = Vec::new();

    for item in items {
        nums.push(to_i(item));
    }
    return nums;
}


fn main() {
    //println!("start");
    let rdx = read_nums();
    let r = rdx[0];
    let d = rdx[1];
    let x = rdx[2];

    let mut ret = x;
    
    
    for i in 0..10 {

        ret = r * ret - d;
        println!("{}", ret);
    }
}   

Measured memory_bytes: 4352
def main():
    N, A, B = (int(i) for i in input().split())
    if (N == 1 and A != B) or (B - A < 0):
        print(0)
    elif N == 1:
        print(1)
    else:
        print((N-2)*B - (N-2)*A + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
import sys
N = int(input())

alphabets = [chr(ord('a') + x) for x in range(10)]

def dfs(S, i):
    if len(S) == N:
        yield ''.join(S)
        return
    for j in range(i):
        for w in dfs(S + [alphabets[j]], i):
            yield w
    for w in dfs(S + [alphabets[i]], i + 1):
        yield w

for w in dfs([],0):
    print(w)


Measured memory_bytes: 4384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

    int main(){
      int n;
      int a[3];
      cin >> n >> a[2] >> a[1] >> a[0];
      int l[n];
      rep(i,n)cin >> l[i];
      int ans=inf;
      int m=pow(4,n);
      rep(i,m){
        int subans=0;
        int length[3]={};
        int temp=i;
        int cnt=0;
       while(cnt<n){
         if(temp%4!=3){
           if(length[temp%4]!=0)subans+=10;
           length[temp%4]+=l[cnt];
         }
         cnt++;
         temp/=4;
       }
        sort(length,length+3);
        rep(j,3){
          subans+=abs(length[j]-a[j]);
        }
        if(length[0]*length[1]*length[2]>0){
          ans=min(ans,subans);
        }
      }
      cout << ans << endl;
      return 0;}

Measured memory_bytes: 512
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

const int MAX_N = 2e5+10;
int dp[MAX_N][2];

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

int main(){
    rep(i, MAX_N) rep(j, 2) dp[i][j] = INF;
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(s[0]=='#') {
        dp[0][1] = 0;
        dp[0][0] = 1;
    }
    else {
        dp[0][0] = 0;
        dp[0][1] = 1;
    }
    REP(i, 1, n) {
        if(s[i] == '#') {
            chmin(dp[i][1], dp[i-1][1]);
            chmin(dp[i][1], dp[i-1][0]);

            // chmin(dp[i][0], dp[i-1][1]+1);
            chmin(dp[i][0], dp[i-1][0]+1);
        }
        else {
            chmin(dp[i][0], dp[i-1][0]);
            // chmin(dp[i][0], dp[i-1][1]);

            chmin(dp[i][1], dp[i-1][0]+1);
            chmin(dp[i][1], dp[i-1][1]+1);
        }
    }
    cout << min(dp[n-1][0], dp[n-1][1]) << endl;
    return 0;
}

Measured memory_bytes: 2180
from collections import deque, defaultdict

def search(g, v):
  visited = [False] * len(g)
  visited[v] = True
  ans = [False] * len(g) 
  
  q = deque([v])
  ans[v] = False
  while q:
    s = q.popleft()
    for t,w in g[s]:
      if not visited[t]:
        q.append(t)
        ans[t] = ans[s]^(True if w%2==1 else False)
        visited[t] = True
  return ans

N = int(input())
g = {i:[] for i in range(N)}
for i in range(N-1):
    u,v,w = map(int, input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))
print("\n".join(["1" if i else "0" for i in search(g,0)]))

Measured memory_bytes: 48484
#include <bits/stdc++.h>
using namespace std ;
#define N 100010
long long int n,t,a[N];
long long int mmax(long long int a,long long b){
	return a > b ? a : b;
} 
int main() {
    scanf("%lld%lld",&n,&t);
    for(long long int i=1;i<=n;i++) scanf("%lld",&a[i]);
	unsigned long long int ans = 0,mx = 0,tot = 0 ;
    for(long long int i = n ; i  ; i -- ) {
        mx = mmax(a[i],mx);
        ans = mmax(mx - a[i],ans);
    }
    mx = 0;
    for(long long int i = n;i;i--) {
        mx = mmax(a[i],mx);
        if(mx - a[i] == ans) tot++;
    }
    printf("%lld\n",tot);
    return 0 ;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const ll mod = 1e9+7;


int n,m;

int main(){
  // freopen("input.txt","r",stdin);
  cin>>n>>m;
  if(n >= 10) cout<<m<<endl;
  else cout<<m+(100*(10-n))<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
using namespace std;
const int mod=1000000007;
typedef long long ll;
typedef pair<int,int> P;
//mint
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint operator-() const { return mint(0) - *this;}
  mint operator~() const { return mint(1) / *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint& operator/=(const mint& a){ (x*=a.pow(mod-2).x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  mint operator/(const mint& a)const{ return mint(*this) /= a;}
  mint pow(ll t) const {
    if(!t) return 1;
    mint res = pow(t/2);
    res *= res;
    return (t&1)?res*x:res;
  }
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
mint ex(mint x, ll t) { return x.pow(t);}
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
typedef vector<mint> vm;
struct comb {
  vm f, g;
  comb(){}
  comb(int mx):f(mx+1),g(mx+1) {
    f[0] = 1;
    rep(i,1,mx) f[i] = f[i-1]*i;
    g[mx] = f[mx].pow(mod-2);
    for(int i=mx;i>0;i--) g[i-1] = g[i]*i;
  }
  mint c(int a, int b) {
    if (a < b) return 0;
    return f[a]*g[b]*g[a-b];
  }
} c(3e6);
//c.c(a,b)=>aCb


int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    mint ans = 0;
    rep(i,0,n-1)cin >> a[i];
    rep(i,0,60){
        int a1 = 0;
        rep(j,0,n-1){
            a1 += (a[j]%2);
            a[j] = a[j] >> 1;
        }
        //vecprint(a);
        mint p = 1;
        int ii = i;
        while(ii){
            p = p * 2;
            ii--;
        }
        ans = ans + (mint)a1*(n-a1)*p;//%mod?

    }

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 49408
#include <bits/stdc++.h>
//#include <atcoder/all>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = -INF;
    chmax(ans, a * c);
    chmax(ans, a * d);
    chmax(ans, b * c);
    chmax(ans, b * d);
    cout << ans << endl;
    return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int a, b;
  cin >> a >> b;
  int maxnum = max(a, b);
  int minnum = min(a, b);
  int maxnumzwei = max(maxnum - 1, minnum);
  cout << maxnum + maxnumzwei << endl;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(dead_code)]

use std::thread;
use std::io::{ self, Read };
use std::fmt;
use std::iter::Iterator;
use std::cmp::*;
use std::collections::*;
use std::str::*;
use std::mem::*;

#[derive(Default)]
struct Input {
    buf: Vec<String>
}

impl Input {
    fn new() -> Input {
        Input { buf: Vec::new() }
    }

    fn read<T: FromStr>(&mut self) -> T 
    where <T as FromStr>::Err: fmt::Debug {
        self.next().unwrap().parse::<T>().unwrap()
    }

    fn read_2<T: FromStr, U: FromStr>(&mut self) -> (T, U)
    where <T as FromStr>::Err: fmt::Debug,
          <U as FromStr>::Err: fmt::Debug {
        (self.read(), self.read())
    }

    fn read_3<T: FromStr, U: FromStr, V: FromStr>(&mut self) -> (T, U, V)
    where <T as FromStr>::Err: fmt::Debug,
          <U as FromStr>::Err: fmt::Debug,
          <V as FromStr>::Err: fmt::Debug {
        (self.read(), self.read(), self.read())
    }
    fn read_bytes(&mut self) -> Vec<u8> {
        self.next().unwrap().into_bytes()
    }

    fn read_n<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where <T as FromStr>::Err: fmt::Debug {
        let mut v = Vec::new();
        for _ in 0..n { v.push(self.read::<T>()); }
        v
    }
}

impl Iterator for Input {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        while self.buf.is_empty() {
            let mut s = String::new();
            let _res = io::stdin().read_line(&mut s);
            self.buf = s.split_whitespace().map(|s| s.to_owned()).collect::<Vec<_>>();
            self.buf.reverse();
        }
        self.buf.pop()
    }
}

fn run() {
    let mut ip = Input::new();
    let n = ip.read();
    let k = ip.read();
    let a: Vec<i64> = ip.read_n(n);
    let mut sa = vec![0; n + 1];
    for i in 1..n + 1 {
        sa[i] = sa[i - 1] + a[i - 1];
    }
    let mut b = vec![];
    for l in 0..n {
        for r in l + 1..n + 1 {
            b.push(sa[r] - sa[l]);
        }
    }
    let mut y = 0;
    for d in (0..50).rev() {
        let mut cnt = 0i64;
        let bit = 1i64 << d;
        for x in &b {
            cnt += (x >> d) & 1i64;
        }
        if cnt >= k {
            y |= bit;
            let mut new_b = vec![];
            for &x in &b {
                if x & bit > 0 {
                    new_b.push(x);
                }
            }
            b = new_b;
        }
    }
    println!("{}", y);
}

fn main() {
    let _ = thread::Builder::new()
        .stack_size(10 * 1024 * 1024)
        .spawn(run).unwrap()
        .join();
}

Measured memory_bytes: 14448
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i if i % 2 != 0 else 2 for i in range(maxA+1)]
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] != i:
            continue
        p = i * 2
        while p <= maxA:
            if prime[p] == p:
                prime[p] = i
            p += i

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)

    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    # print(prime)
    for An in A:
        if An == 1:
            continue
        # print('An = {}'.format(An))
        not_pairwise_coprime = False
        while prime[An] != An:
            # print('prime[An]={}, f[prime[An]]={}'.format(prime[An], f[prime[An]]))
            if f[prime[An]]:
                not_pairwise_coprime = True
                break
            f[prime[An]] = True
            prime_An = prime[An]
            while An % prime_An == 0:
                An //= prime_An
        else:
            if An != 1:
                if f[An]:
                    not_pairwise_coprime = True
                else:
                    f[An] = True
        if not_pairwise_coprime:
            break
        # print(f)
    else:
        print('pairwise coprime')
        return
    if setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Measured memory_bytes: 222268