akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define F first
#define S second
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
using ll = long long;
using pi = pair<int,int>;
int main()
{
  int n; cin >> n;
  string s; cin >> s;
  vector<int> wsum(n+1),rsum(n+1);
  wsum[0] = 0;
  rsum[0] = 0;
  rep(i,n) {
    if(s[i] == 'W') {
      wsum[i+1] = wsum[i] + 1;
      rsum[i+1] = rsum[i];
    }
    else {
      wsum[i+1] = wsum[i];
      rsum[i+1] = rsum[i] + 1;      
    }
  }

  int res = 1e+6;
  rep(i,n+1) {
    int tmp = max(wsum[i], rsum[n] - rsum[i]);
    chmin(res, tmp);
  }
  cout << res << "\n";
  
  return 0;
}


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

using namespace std;

int main(){
	int n, i=0, h;
	char s[100];
	cin >> n;
	while(i<n){
		cin >> s[i];
		i++;
	}
	i=0;
	if(n%2==0){
		if(n==2){
			if(s[0]==s[1]){
				cout << "Yes" << endl;
			}
			else{
				cout << "No" << endl;
			}
		}
		else{
			h = n/2;
			while(i<h){
				if(s[i]==s[h]){
					i++;
					h++;
					if(h==n-1){
						cout << "Yes" << endl;
						break;
					}
				}
				else{
					cout << "No" << endl;
					break;
				}
			}
		}
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

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; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353;
constexpr int MAX = 5000000;

int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	string s; cin >> s;
	int res = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s.substr(i, 3) == "ABC"s) res++;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, a;
  vector<int> r(100);
  cin >> n;
  a = n;
  for(int i=0;i<n;i++) {
    cin >> r.at(i);
  }
  for(int i=0;i<n;i++) {
    if (r.at(i) == 0) {
      continue;
    }
    for(int j=i+1;j<n;j++) {
      if(r.at(i) == r.at(j)) {
        a--;
        r.at(j) = 0;
      }
    }
  }
  cout << a << endl;
  return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod=1000000007;
const int INF=1e18;


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    cout<<(n*(n-1))/2 + (m*(m-1))/2<<'\n';
    
    return 0;
}

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

int main() {
	long long N, M;
	std::cin >> N >> M;
	std::vector<bool> flag(N, false);
	std::vector<long long> wa(N, 0);
	long long ac = 0;
	for (long long i = 0; i < M; i++) {
		long long p;
		std::string s;
		std::cin >> p >> s;
		p--;
		if (s == "AC" && !flag[p]) {
			flag[p] = true;
			ac++;
		}
		else if (s == "WA" && !flag[p]) {
			wa[p]++;
		}
	}
	long long w = 0;
	for (long long i = 0; i < N; i++) {
		w += flag[i] ? wa[i] : 0;
	}
	std::cout << ac << " " << w << std::endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}


ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

int main(){
  string s;cin>>s;
  if(s=="SUN") cout <<7<<endl;
  else if(s=="MON") cout <<6<<endl;
  else if(s=="TUE") cout <<5<<endl;
  else if(s=="WED") cout <<4<<endl;
  else if(s=="THU") cout <<3<<endl;
  else if(s=="FRI") cout <<2<<endl;
  else if(s=="SAT") cout <<1<<endl;
}
  


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}

//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
int main()
{
	ll x, k, d;
	cin >> x >> k >> d;
	x = abs(x);

	// k回移動して、原点をまたぐことが出来るか
	// またぐ時
	ll kai = x / d;
	kai = min(k,kai);
	k -= kai;
	x -= kai * d;
	if(k % 2 == 0){
		cout << x << endl;
	} else {
		cout << abs(x-d) << endl;
	}
}


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

int main()
{
	ll n, k;
	cin >> n >> k;
	vector<ll> arr(n + 1, 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	for (int i = k + 1; i <= n; i++)
	{
		if (arr[i] > arr[i - k])
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 4836
#include <bits/stdc++.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
// vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'


signed main() {
    fio();

    int n;
    cin >> n;
    ll sum = 0;
    vl a(n);
    ll ans = 0;
    rep (i, n) {
        cin >> a[i];
        ans += a[i] * sum % MOD;
        sum += a[i];
        sum %= MOD;
    }
    ans %= MOD;
    cout << ans << endl;
}

Measured memory_bytes: 4780
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
using namespace std;
#define ri register int
#define il inline
#define pb emplace_back
#define solid const auto &
#define enter putchar('\n')
#define Size(x) ((int)x.size())
#define mem(x,y) memset(x,y,sizeof(x))
#define gm int mid((l+r)>>1)
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<class T>il void in(T &x)
{
	x=0; char c=getchar(); bool f=0;
	while(!isdigit(c)) f|=(c=='-'),c=getchar();
	while(isdigit(c)) x=x*10+(c^'0'),c=getchar();
	f?x=-x:0;
}
template<class T>il void out(T x,const char c='\n')
{
	static short st[30]; short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(c);
}
template<class T>il void err(const T &x,const char c='\n') {cerr<<x<<c;}
template<class T,class ...Args>il void err(const T &x,const Args &...args) {err(x,' '),err(args...);}
const int md=998244353;
il int qpow(int a,int b) {int r=1; for(; b; b>>=1,a=(LL)a*a%md) if(b&1) r=(LL)r*a%md; return r;}
il int fit(const int x) {return x>=md?x-md:x;}
namespace i207M
{
const int N=1000005;
int fac[N],ifac[N];
void prework(int n)
{
	fac[0]=1;
	for(ri i=1;i<=n;++i) fac[i]=(LL)fac[i-1]*i%md;
	ifac[n]=qpow(fac[n],md-2);
	for(ri i=n;i>=1;--i) ifac[i-1]=(LL)ifac[i]*i%md;
}
il int C(int n,int m) {return (LL)fac[n]*ifac[m]%md*ifac[n-m]%md;}
int n,m;
signed main()
{
#ifdef M207
	freopen("in.in","r",stdin);
#endif
	in(n),in(m);
	if(n>m) swap(n,m);
	prework(n+m);
	int ans=0;
	for(ri i=1;i<=n;++i)
		ans=(ans+(LL)C(2*i,i)*C(n-i+m-i,n-i))%md;
	ans=(LL)ans*qpow(C(n+m,n),md-2)%md*(md+1)/2%md;
	ans=fit(ans+m);
	out(ans);
	return 0;
}
}
signed main()
{
	i207M::main();
	return 0;
}


Measured memory_bytes: 8064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=370;
const int M=30;

int D,ans,T,d,q;
int s[N][M],lst[M],c[M],t[N],cnt[N][M];

int calc(){
	int sum=0;
	for (int i=1;i<=26;i++) lst[i]=0;
	for (int i=1;i<=D;i++){
		sum+=s[i][t[i]];
		lst[t[i]]=i;
		for (int j=1;j<=26;j++) sum-=c[j]*(i-lst[j]);
	}
	return sum;
}

int argmx(int d){
	int id=1;
	for (int i=2;i<=26;i++)
		if (s[d][i]>s[d][id]) id=i;
	return id;
}

int main(){
	scanf("%d",&D);
	for (int i=1;i<=26;i++) scanf("%d",&c[i]);
	for (int i=1;i<=D;i++)
		for (int j=1;j<=26;j++) scanf("%d",&s[i][j]);
	for (int i=1;i<=D;i++) t[i]=argmx(i);
	for (int i=1;i<=D;i++) printf("%d\n",t[i]);
	return 0;
}

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

int main()
{
    int x, y;
    cin >> x >> y;
    int c=0;
    c = 4*x-y;
    c/=2;
    int d=y-2*x;
    d/=2;
    if(c>=0 and d>=0 and c+d==x) cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n,x,t,z=0;
    cin>>n>>x>>t;
    while(true){
        z+=t;
        if(n<=x){
            break;
        }
        n-=x;
    }
    cout<<z<<'\n';
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
vector<ull>hash,power;
void Roliha(string &s){
  ull B=1000000007;
  int sz=s.size();
  hash.assign(sz+1,0);
  power.assign(sz+1,0);
  power[0]=1;
  for(int i=0;i<sz;i++)power[i+1]=power[i]*B;
  for(int i=0;i<sz;i++)hash[i+1]=(hash[i]+s[i])*B;
}
ull get_hash(int l,int r){return hash[r]-hash[l]*power[r-l];}
int main(){
  int n,m,l=0,r=1;
  string s,t;
  cin>>n>>m>>s;
  set<ull>p;
  Roliha(s);
  while(m--){
    cin>>t;
    if(t[0]=='R')t[1]=='+'?r++:r--;
    else t[1]=='+'?l++:l--;
    p.insert(get_hash(l,r));
  }
  cout<<p.size()<<endl;
}

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

using namespace std;
const int MAX = 1000001;
bool prime[MAX];
int a,b;
vector<int> V;


void make(){
  fill(prime,prime+MAX,true);

  prime[0] = prime[1] = false;

  for(int i = 2; i*i < MAX; i++)
    if(prime[i])
      for(int j = 2; i*j < MAX; j++)
	prime[i*j] = false;

  for(int i = 2; i < MAX; i++)
    if(prime[i]) V.push_back(i);  
}

int solve(int n){

  int sum = 0,last;
  for(int i = 0; i < V.size(); i++){
    if(V[i] > n) break;
    if(n%V[i] == 0){
      sum += V[i];
      last = V[i];
    }
  }

  sum -= last;
  return last-sum;
}

int main(){

  make();
  while(cin >> a >> b && a+b){
    int ans_a = solve(a);
    int ans_b = solve(b);

    if(ans_a > ans_b) cout << "a" << endl;
    else cout << "b" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 2564
#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
#define ll long long
#define fr first
#define se second
#define fi(i,s,e,inc) for(auto i=s; i<e; i+=inc)
#define fie(i,s,e,inc) for(auto i=s; i<=e; i+=inc)
#define fd(i,s,e,dec) for(auto i=s; i>e; i-=dec)
#define fde(i,s,e,dec) for(auto i=s; i>=e; i-=dec)
#define umap tr1::unordered_map
#define nl cout<<"\n";
#define vt vector
#define pb push_back
#define pr(x) cout<<x;
#define ps(x) cout<<x<<" ";
#define sp cout<<" ";
#define mod 1000000007
#define all(x) x.begin(),x.end()
#define rev reverse
#define tc ll t; cin>>t; while(t--)
#define pq priority_queue
ll n;
ll a[100005][4],dp[100005][4];
ll solve(ll day, ll prev){
    if(day==n) return 0;

    if(dp[day][prev]!=-1) return dp[day][prev];

    ll mx=0;
    if(prev==0){
        mx = max(mx,a[day][1] + solve(day+1,1));
        mx = max(mx,a[day][2] + solve(day+1,2));
        mx = max(mx,a[day][3] + solve(day+1,3));
    }
    else if(prev==1){
        mx = max(mx,a[day][2] + solve(day+1,2));
        mx = max(mx,a[day][3] + solve(day+1,3));
    }
    else if(prev==2){
        mx = max(mx,a[day][1] + solve(day+1,1));
        mx = max(mx,a[day][3] + solve(day+1,3));
    }
    else if(prev==3){
        mx = max(mx,a[day][1] + solve(day+1,1));
        mx = max(mx,a[day][2] + solve(day+1,2));
    }

    return dp[day][prev] = mx;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    fi(i,0,n,1) cin>>a[i][1]>>a[i][2]>>a[i][3];
    memset(dp,-1,sizeof(dp));
    pr(solve(0,0)) nl
    return 0;
}


Measured memory_bytes: 12800
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////
int main(){

    int n;
    I(n);
    int ar[n+2];
    for(int i=1;i<=n;i++)I(ar[i]);

    sort(ar +1, ar+ n+ 1);


    int res =0;
    for(int i=1;i<=n;i++){
        for(int j = i+1;j<=n;j++){
            if(ar[i] == ar[j])continue;
            for(int k = j+1;k<=n;k++){
                if(ar[k] == ar[j] || ar[k] == ar[1])continue;
                if(ar[i] + ar[j] > ar[k])res++;
            }
        }
    }
    cout<<res<<Endl;
    return 0;
}

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

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

inline int addmod(lli x,lli y)
{
    return (x%mod + y%mod)%mod;
}
inline int submod(lli x,lli y)
{
    return (x%mod - y%mod + mod)%mod;
}
inline int mulmod(lli x,lli y)
{
    return (x%mod * y%mod)%mod;
}


inline int nextSubMask(int i, int mask)
{
    return (i-1)&mask;   /// returns next  submask
}

template<typename T>
void we_r_done(T mssg)
{
    cout<<mssg;
    exit(0);
}

void done(int x)
{
    cout<<"! "<<x;
    exit(0);
}
const int N = 1e5 + 6;
vector<int>tree[N];
int way[N]  , ans , n,k;

void dfs(int x , int p = -1){
    ans = mulmod(ans , way[x]);
    int cnt = 0;
    for(int u : tree[x]){
        if(p == u) continue;
        way[u] = k-1-(p != -1)-cnt;
        cnt++;
        dfs(u,x);
    }
}

int main()
{
    ///freopen("output.txt","w",stdout);
    //freopen("input.txt","r",stdin);
    FastIO;

    while(cin>>n>>k){
        for(int i=1; i<=n; i++){
            tree[i].clear();
            way[i] = 0;
        }
        for(int i=1,x,y; i<n; i++){
            cin>>x>>y;
            tree[x].pb(y);
            tree[y].pb(x);
        }

        ans = 1; way[1] = k;
        dfs(1,-1);
        cout<<ans<<endl;
    }
    return 0;
}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?
///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});


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

long k,n,mod=998244353;
vector<long> ans(2500);
vector<long> fac(10000);

long modpow(long modpow_x,long modpow_y) {
  long modpow_return=1;
  for(long i=1;i<=modpow_y;i*=2) {
    if(modpow_y/i%2==1) modpow_return=modpow_return*modpow_x%mod;
    modpow_x=modpow_x*modpow_x%mod;
  }
  return modpow_return;
}

long ncr(long a,long b) {
  return fac[a]*modpow(fac[b],mod-2)%mod*modpow(fac[a-b],mod-2)%mod;
}

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

  if(k==1) {
    cout << 0 << endl;
    return 0;
  }

  fac[0]=1;
  for(long i=1;i<fac.size();i++) fac[i]=fac[i-1]*i%mod;
  
  for(long i=0;i<min((k+1)/2,n/2);i++) {
    long x=ncr(k+n-3-i*2,k-1);
    if(i%2==0) for(long j=i;j<(k+1)/2;j++) ans[j]=(ans[j]+ncr(j+1,i+1)*x%mod)%mod;
    else for(long j=i;j<(k+1)/2;j++) ans[j]=(ans[j]+mod-ncr(j+1,i+1)*x%mod)%mod;
  }
  for(long i=0;i<(k+1)/2;i++) ans[i]=(ncr(k+n-1,k-1)+mod-ans[i])%mod;

  for(long i=0;i<2*k-1;i++) cout << ans[min(i,2*k-2-i)/2] << endl;
}

Measured memory_bytes: 3724
def main():
    L = int(input())
    n = 1
    while 2**n <= L:
        n += 1
    n -= 1
    ans = []
    for i in range(1, n+1):
        ans.append([i, i+1, 0])
        ans.append([i, i+1, 2**(i-1)])
    for i in reversed(range(1, n+1)):
        if L-2**(i-1) >= 2**n:
            ans.append([i, n+1, L-2**(i-1)])
            L -= 2**(i-1)
    print(n+1, len(ans))
    for u, v, w in ans:
        print(u, v, w)

if __name__ == "__main__":
    main()

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

int main(){
  int N,M,X[101],Y[101],capx,capy,y=0,x=0,flag = 0;
  cin >> N >> M >> capx >> capy;
  for(int i=0;i<N;i++)cin>>X[i];X[N] = capx;
  for(int i=0;i<M;i++)cin>>Y[i];Y[M] = capy;
  for(int i=-100;i<=100;i++){
    if (capx < i && i <= capy){
      for(int j=0;j<=N;j++){
        if (i > X[j]){
          x ++;
        }
      }
      for(int j=0;j<=M;j++){
        if (i <= Y[j]){
          y ++;
        }
      }
      //cout <<i<<" -> "<<x<<" : "<<y<<endl;
      if(x==N+1 and y==M+1){
        flag ++;
        break;
      }else{
        x = 0;y = 0;
      }
    }
  }
  if (flag == 0){
    cout << "War" <<endl;
  }else{
    cout << "No War" <<endl;
  }
}


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

using namespace std;

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    FOREACH(x, v) { cout << x << " "; }                                        \
    cout << "\n";

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, V, greater<ll>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;
const ll dx[] = {1, -1, 0, 0};
const ll dy[] = {0, 0, 1, -1};

ll N, M;
vector<map<ll, ll>> memo;
map<ll, ll> cnt;
VL p;

int main() {
    cin >> N >> M;
    memo.resize(M);
    REP(i, M) {
        LCIN(k);
        REP(j, k) { memo[i][IN() - 1]++; }
    }
    REP(i, M) p.emplace_back(IN());
    ll ans = 0;
    REP(i, 1 << N) {
        REP(j, N) {
            if(i >> j & 1) REP(k, M) if(memo[k][j]) cnt[k]++;
        }
        bool judge = true;
        REP(k, M) {
            if(cnt[k] % 2 != p[k]) judge = false;
        }
        if(judge) ans++;
        cnt.clear();
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
n, l = map(int, input().split())
count = 0
if l == 0:
    for i in range(1, n+1):
        count += i + l - 1

    print(count)

if l > 0:
    for i in range(2, n+1):
        count += i + l -1

    print(count)

if (l < 0) and (n > 1 - l):
    for i in range(1, n+1):
        count += i + l - 1

    print(count)
    
if (l < 0) and (n < 1 - l):
    for i in range(1, n):
        count += i + l - 1
        
    print(count)
    
if (l < 0) and (n == 1 - l):
    for i in range(1, n):
        count += i + l -1
        
    print(count)

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long a=sc.nextLong(),b=sc.nextLong(),c=sc.nextLong(),k=sc.nextLong();
    long res=0;
    if(k<=a) {
    	System.out.println(k);
    }else if(k<=a+b){
    	System.out.println(a);
    }else {
    	System.out.println(a-(k-a-b));
    }
  }
}


Measured memory_bytes: 35540
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=500000+10;
char s[maxn];
int a[maxn];
int i,j,k,l,t,n,m,num;
int main(){
	scanf("%s",s);
	n=strlen(s);
	reverse(s,s+n);
	fo(i,0,n-1) a[i]=s[i]-'0';
	t=i=0;
	while (i<n){
		t+=a[i]*9;
		a[i]=t%10;
		t/=10;
		if (t&&i==n-1) n++;
		i++;
	}
	fo(i,0,n-1) num+=a[i];
	fo(k,1,n*20){
		a[0]+=9;
		num+=9;
		//if (a[0]<10) continue;
		t=i=0;
		while (i<n){
			t+=a[i];
			num-=a[i];
			a[i]=t%10;
			num+=a[i];
			t/=10;
			if (!t) break;
			if (i==n-1) n++;
			i++;
		}
		/*l=(k-1)/9+1;
		if (!a[0]&&num>=k&&num<=l*9) break;*/
		if (num<=9*k) break;
	}
	printf("%d\n",k);
}

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

#define ll long long
#define ld long double
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
#define MOD 1000000007
#define INF LONG_LONG_MAX
#define NINF LONG_LONG_MIN
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

ll knapsack(vector<ll> &w,vector<ll> &v,vector<vector<ll>> &dp,ll i,ll k)
{
    if(i==-1)
        return 0;
    if(k<=0)
        return 0;
    if(dp[i][k]!=-1)
        return dp[i][k];

    if(w[i]>k) return dp[i][k] = knapsack(w,v,dp,i-1,k);

    return dp[i][k] = max(v[i]+knapsack(w,v,dp,i-1,k-w[i]), knapsack(w,v,dp,i-1,k));
}

int main(){

    IOS;

    ll t,n,k,m;
    t=1;
    while(t--)
    {
        cin >> n >> k;
        vector<ll> w(n);
        vector<ll> v(n);
        vector<vector<ll>> dp(n,vector<ll>(k+1,-1));
        for(ll i=0;i<n;i++)
        {
            cin >> w[i] >> v[i];
        }

        ll ans = knapsack(w,v,dp,n-1,k);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 79488
def main():
    N = int(input())
    A = list(map(int, input().split()))
    maxA = max(A)
    # C[a] = A内のaの個数
    C = {a: 0 for a in A}
    for a in A:
        C[a] += 1
    # D[a]=1: Aにaより小さいaの約数が存在する
    D = {a: 0 for a in A}
    for a in A:
        if C[a] > 0:
            t = 2
            while a * t <= maxA:
                D[a * t] = 1
                t += 1
    ans = 0
    for a in A:
        if C[a] == 1 and D[a] == 0:
            ans += 1
    print(ans)
main()


Measured memory_bytes: 104304
# https://atcoder.jp/contests/abc113/tasks/abc113_c
# C - ID

n, m = list(map(int, input().split()))
py_list = []

for _ in range(m):
    p, y = list(map(int, input().split()))
    py_list.append((p, y))

sorted_py_list = sorted(py_list, key=lambda x: (x[0], x[1]))

p_no = sorted_py_list[0][0]
y_index = 1
no_dict = {}

for i, py in enumerate(sorted_py_list):
    p, y = py

    if p != p_no:
        p_no = p
        y_index = 1

    no = str(p).zfill(6) + str(y_index).zfill(6)
    no_dict[(p, y)] = no
    y_index += 1

print_list = []

for p, y in py_list:
    print_list.append(no_dict[(p, y)])

ans = '\n'.join(print_list)
print(ans)


Measured memory_bytes: 40788
#define NOMINMAX
#define TEST_MODE true

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (a)-1; i >= (int)b; --i)
#define range(i, a, b, c) for (int i = a;             \
                                   c > 0 ? i < b : i > b; \
                                   i += c)
#define chmax(a, b) (a = (a) < (b) ? (b) : (a))
#define chmin(a, b) (a = (a) > (b) ? (b) : (a))
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define ifnot(a) if (not(a))
#define int long long

#ifdef LOCAL_ENV

#if TEST_MODE == true
const bool test = true;
#define dump(x) cerr << #x << " = " << (x) << " "
#define dumpl(x) dump(x) << endl
#else
const bool test = false;
#define dump(x) 
#define dumpl(x)
#endif

#else
const bool test = false;
#define dump(x) 
#define dumpl(x)
#endif

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
const int INF = (int)1 << 60;
const ll INFL = (ll)1 << 60;
ll mod_n = (int)1e9 + 7;
const double eps = 1e-10;
typedef long double Real;
// return -1, 0, 1
int sgn(const Real &r) { return (r > eps) - (r < -eps); }
int sgn(const Real &a, const Real &b) { return sgn(a - b); }

//.....................
const int MAX = (int)2e5 + 5;

vector<string> split(const string &str, char sep)
{
	vector<string> v;
	stringstream ss(str);
	string buffer;
	while (getline(ss, buffer, sep))
	{
		v.push_back(buffer);
	}
	return v;
}

template <class InputIterator>
int sum(InputIterator begin, InputIterator end)
{
	return accumulate(begin, end, 0ll);
}

template<typename T>
T gcd(T a, T b)
{
	T c;
	while (a != 0) {
		c = a; a = b%a;  b = c;
	}
	return b;
}

template<typename T>
T bit_count(T N) {
	T cnt = 0;
	while (N) {
		if (N & 1) cnt++;
		N >>= 1;
	}
	return cnt;
}

template<typename T>
void print_vec(ostream& ostream, vector<T> a) {
	rep(i, a.size() - 1) ostream << a[i] << " ";
	ostream << a.back() << endl;
}

template<class T>
T pow_n(T x, T n) {
	T res = 1;
	while (n > 0) {
		if (n & 1) res = res * x;
		x = x * x;
		n >>= 1;
	}
	return res;
}

class Solver {
public:
	int H, W;

	bool grid_ok(int y, int x) {
		return 0 <= y && y < H && 0 <= x && x < W;
	}

	int N, X;
	valarray<int> m;

	int ans() {		
		int a = X - m.sum();
		return N + a / m.min();
	}

	void solve() {
		cin >> N >> X;
		m.resize(N);
		rep(i, N) cin >> m[i];
		cout << ans() << endl;
	}

};

signed main()
{
	srand((unsigned int)time(NULL));
	cout << fixed << setprecision(20);
	auto ptr = new Solver();
	ptr->solve();
	delete ptr;
	//while (true) {
	//	if (cin.eof() == true) break;
	//	auto ptr = new Solver();
	//	ptr->solve();
	//	delete ptr;
	//}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n; cin >> n;
	set<ll> st;
	cin >> n;
	int t = n;
	REP(i, 100000)
	{
		st.insert(t);
		int tt;
		if (t % 2 == 0) tt = t / 2;
		else tt = 3 * t + 1;
		if (st.count(tt) == 0)
		{
			st.insert(tt);
			t = tt;
		}
		else
		{
			cout << i + 2 << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d", $target_count);
$heights = array_map("intval", explode(" ", trim(fgets(STDIN))));

$target_tmp = [0];
$prev = 0;
for ($i = 0; $i < count($heights); ++$i) {
    if ($heights[$i] != $prev) $target_tmp[] = $heights[$i];
    $prev = $heights[$i];
}
array_push($target_tmp, 0);
//メモリ解放
$heights = [];

$target = [0];
$prev = 0;
for ($i = 1; $i < count($target_tmp)-1; ++$i) {
    if (($prev < $target_tmp[$i] && $target_tmp[$i] > $target_tmp[$i+1]) || ($prev > $target_tmp[$i] && $target_tmp[$i] < $target_tmp[$i+1])) $target[] = $target_tmp[$i];
    
    $prev = $target_tmp[$i];

}
//メモリ解放
$target_tmp = [];

$mountain = [];
$valley = [];

for ($i = 0; $i < count($target); ++$i){
	if ($i%2 == 1) {
		$mountain[] = $target[$i];
	} else {
		$valley[] = $target[$i];
	}
}

sort ($target);
sort ($mountain);
sort ($valley);
array_push($target, 0);
array_push($mountain, 0);
array_push($valley, 0);

$ans = 0;
$max = 0;

if(count($target) == 1){
    echo $max, "\n";
	return ;
}

$m = 0;
$b = 0;

for ($i = 0; $i < count($target)-1; ++$i) {
    if ($mountain[$m] == $target[$i]) {
        ++$m;
        --$ans;
    } 
    if ($valley[$b] == $target[$i]) {
        ++$b;
        ++$ans;
    }
    
    if ($target[$i] < $target[$i+1]) {
        if ($ans > $max) $max = $ans;
    }

}


echo $max, "\n";



Measured memory_bytes: 40908
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1e18;
constexpr ll MOD = 1234567;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}

ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}

int main() {
    int K;
    cin >> K;
    int A,B;
    cin >> A >> B;
    bool ret = false;
    for(int i = 0;i < 2000;i++) {
        if(A <= K * i && K * i <= B) {
            ret = true;
        }
    }
    if(ret == true) {
        cout << "OK" << endl;
    }
    else {
        cout << "NG" << endl;
    }
}

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

#define EB emplace_back
#define int long long
#define F first
#define S second
#define N 500005
#define all(x) x.begin(),x.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

int32_t main(){
	IOS;
	int tt = 1; 
	//cin >> tt;
	while(tt--){
		int n; cin >> n;
		string s; cin >> s;
		int i = 0, j = n - 1;
		int cnt = 0;
		while(i < j){
			while(s[j] != 'R' && j >= 0) j--;
			while(s[i] != 'W' && i < n) i++;
			if(i >= j) break;
			//cout << i << " " << j << endl;
			swap(s[i], s[j]);
			cnt++;
		}	
		cout << cnt << endl;
	}
	return 0;
}


Measured memory_bytes: 3764
import math
N,K = map(int,input().split())
cnt = 0
for n in range(1,N+1):
    if K/n <= 1:
        x = 0
    elif abs((math.log(K)-math.log(n))//math.log(2)-(math.log(K)-math.log(n))/math.log(2))<=0.00001:
        x = (math.log(K)-math.log(n))//math.log(2)
    else:
        x = (math.log(K)-math.log(n))//math.log(2)+1
    cnt += (0.5)**x

print(cnt/N)

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

// UnionFind
struct UnionFind {
  vector<int> d;
  UnionFind(int n) : d(n, -1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  rep(i, m) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }

  UnionFind u = UnionFind(n);

  vector<ll> ans(m, 0);
  ans[m - 1] = (ll)n * (n - 1) / 2;
  for (int i = m - 1; i > 0; i--) {
    if (u.same(a[i], b[i])) {
      ans[i - 1] = ans[i];
    } else {
      ans[i - 1] = ans[i] - (ll)u.size(a[i]) * u.size(b[i]);
    }
    u.unite(a[i], b[i]);
  }

  rep(i, m) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main(){
	vector<string> week{"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
	string S;
	cin >> S;
	for(int i = 0; i < 7; i++)
		if(S == week.at(i))
			cout << 7-i << endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
char a[20];
int main()
{
	int ans=0;
	scanf("%s",a);
	int len=strlen(a);
	int h=0;
	for(int i=0;i<len;i++)
	{
		h+=a[i]-'0';
		ans=max(ans,h-1+9*(len-i-1));
	}
	ans=max(ans,h);
	printf("%d\n",ans);
}

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

using namespace std;
using Graph = vector<vector<int>>;

int main(void) {
    int n;
    cin >> n;
    vector<int> color(n, -1);
    color[0] = 0;
    Graph g(n), cost(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
        cost[a].push_back(l);
        cost[b].push_back(l);
    }
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < g[v].size(); ++i) {
            int u = g[v][i];
            int w = cost[v][i];
            if (color[u] != -1) continue;
            color[u] = (color[v] + w) % 2;
            q.push(u);
        }
    }
    for (auto ans : color) {
        cout << ans << endl;
    }
}

Measured memory_bytes: 11904
using System;
using System.Collections.Generic;
using System.Linq;

class B
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var a = read();
		var ps = Enumerable.Range(0, a[0]).Select(i => read()).ToArray();

		Console.WriteLine(Comb2(a[0]).Select(i => Math.Sqrt(Enumerable.Range(0, a[1]).Sum(k => Math.Pow(ps[i[0]][k] - ps[i[1]][k], 2)))).Count(d => d == (int)d));
	}

	static IEnumerable<int[]> Comb2(int n) { for (var i = 0; i < n; i++) for (var j = i + 1; j < n; j++) yield return new[] { i, j }; }
}


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

typedef long long int   ll;
#define cases           int t;cin>>t;while(t--)
#define FIO             ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl            "\n"
#define scan(n)         scanf("%d",&n)
#define PI              3.1415926535897932384626433832795
#define int             ll
#define loop0           for(int i=0;i<n;i++)
#define loop1           for(int i=1;i<=n;i++)
#define inpar0(ar)      for(int i=0;i<n;i++)cin>>ar[i];
#define inpar1(ar)      for(int i=1;i<=n;i++)cin>>ar[i];
#define showar0(ar)     for(int i=0;i<n;i++)cout<<ar[i]<<" ";
#define showar1(ar)     for(int i=1;i<=n;i++)cout<<ar[i]<<" ";
#define manu            cout<<(checkerCounter++)<<endl;
int checkerCounter = 1;
int mod=1000000007;
int maxn=200001;
int binpow(int a,int b,int mod){int res=1;while(b>0){if(b%2){res=(res*a)%mod;b--;}a=(a*a)%mod;b/=2;}return res%mod;}
bool isPrime(int n){if(n==1)return false;for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}

signed main(){
    string s;cin>>s;
    int n=s.size();
    for(int i=0;i<n;i++){
        if(s[i]=='?'){
            s[i]='D';
        }
    }
    cout<<s;
}


Measured memory_bytes: 3752
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int pre = s;
        boolean con = true;
        int ans = 1;
        boolean[] c = new boolean[1000000];
        c[s] = true;
        while(con){
            ans++;
            int b;
            if(pre %2 == 0){
                b = pre /2;
            }else{
                b = 3 * pre +1;
            }
            if(c[b]) break;
            else {
                c[b] = true;
                pre = b;
            }
        }

        System.out.println(ans);
        sc.close();
    }

}


Measured memory_bytes: 23892
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

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

	vector<int> s(w + 1);
	for (int i = 1; i <= w; ++i)
		s[i] = i;

	while (n--)
	{
		int a, b;
		scanf("%d,%d", &a, &b);

		swap(s[a], s[b]);
	}

	for (int i = 1; i <= w; ++i)
		cout << s[i] << endl;

	return 0;
}

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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define all(x) (x).begin(), (x).end()
#define rsort(x) sort((x).rbegin(), (x).rend())
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n, e) for (int i = (int)(n); i >= (int)(e); --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << (x) << '\n'; return 0;}while(0)

const int MOD = 1e9+7;
const int MAXN = 5e5+3;
const int INF = 1e9;

int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    //int ntest; cin >> ntest; while(ntest--)
    {
        int k,a,b; cin >> k >> a >> b;
        int i = b/k*k;
        if(i >= a && i <= b) cout << "OK\n";
        else cout << "NG\n";
    }

    return 0;
}


Measured memory_bytes: 3628
from collections import deque

H, W = [int(i) for i in input().split()]
A = [[i for i in input()] for j in range(H)]

q = deque()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            q.append((h, w))

dh = [1, -1, 0, 0]
dw = [0, 0, 1, -1]
ans = 0

while len(q):
    ans += 1
    n = len(q)
    for i in range(n):
        h, w = q.popleft()
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if A[nh][nw] == '.':
                A[nh][nw] = '#'
                q.append((nh, nw))

print(ans - 1)

Measured memory_bytes: 116188
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  string s;cin>>s;
  rep(bit,1<<3){
    int cnt=s[0]-'0';
    string t;
    t+=s[0];
    rep(i,3){
      if(bit&(1<<i)){
        cnt+=s[i+1]-'0';
        t+='+';
        t+=s[i+1];
      }
      else {
        cnt-=s[i+1]-'0';
        t+='-';
        t+=s[i+1];
      }
    }
    if(cnt==7){
      cout<<t<<"=7"<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3616
#include<iostream>
#include<cstdio>
using namespace std;
char z[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'}; 
void zhuan(int n,int m){//printf("n:%d m:%d",n,m);
    if(n==0)return;
    else{
        if(n>0||n%m==0){zhuan(n/m,m);printf("%c",z[n%m]);return;}
        else {zhuan(n/m+1,m);printf("%c",z[-m+n%m]); return;}
    }
}
int main(){
    int n,m;
    scanf("%d",&n); 
    if(n==0)return cout<<0<<endl,0;
    m=-2;
    zhuan(n,m);
    return 0;
}

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

int main(){
    int a,b,c;
    int tmp,tmp2,tmp3;
    cin >> a >> b >> c;
    tmp = a;
    tmp2 = b;
    tmp3 = c;
    a = tmp3;
    b = tmp;
    c = tmp2;
    cout << a <<" "<< b <<" "<< c << endl;
    return 0;

}

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

int main() {
  string S;
  cin >> S;
  int N = S.size();
  
  int count =0;
  
  for(int i=0; i<N; i++){
    if(S.at(i)=='1'){
      count ++;
    }
  }
  
  cout << min(count, N-count)*2 << endl;
}

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

int main(){
  string S,T;
  cin >> S >> T;
  int ans=T.size();
  
  for(int start=0;start<=S.size()-T.size();start++){
    int cnt=0;
    for(int i=0;i<T.size();i++){
      if(T[i]!=S[start+i]){
        cnt++;
      }
    }
    ans=min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  int K;
  cin >> K;
  int cnt = 0, now = 0;
  auto start = clock();
  while (++cnt) {
    now = (now * 10 + 7) % K;
    if (now == 0) return cout << cnt << "\n", 0;
    if ((double) (clock() - start) / CLOCKS_PER_SEC > 1.99) return cout << -1 << "\n", 0;
  }
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
static const int MAX=100000;
int s[MAX],t[MAX],c[MAX];
int sum[2*MAX+1],tt[2*MAX+1];
int N,C,max_sum;

void solve(){
    for(int i=1;i<=C;i++){
        for(int j=0;j<2*MAX+1;j++)tt[j]=0;
        for(int j=0;j<N;j++){
            if(c[j]==i){
                tt[s[j]*2-1]++;
                tt[t[j]*2]--;
            }
        }
        for(int j=1;j<=MAX*2;j++){
            tt[j]+=tt[j-1];
        }    
        for(int j=0;j<=MAX*2;j++){
            if(tt[j]>0)sum[j]++;
        }    
    }

    for(int i=0;i<MAX*2;i++){
        if(max_sum<sum[i])max_sum=sum[i];
    }
}
int main(){
    cin>>N>>C;
    for(int i=0;i<N;i++)
        cin>>s[i]>>t[i]>>c[i];
    solve();
    cout<<max_sum<<"\n";
    return 0;
}



Measured memory_bytes: 2944
N, C =gets.split.map(&:to_i)
xs = [[0, 0]]
ys = [[0, 0]]

right_res_list = []
left_res_list = []
right_res_max_list = []
left_res_max_list = []
res = 0
max = 0
N.times{|i|
  temp = gets.split.map(&:to_i)
  xs << temp
  ys << [C - temp[0], temp[1]]
  res += xs[i+1][1] - (xs[i+1][0] - xs[i][0])
  max = res > max ? res : max
  right_res_max_list << max
  right_res_list << res
}
ys.sort_by!{|i| i[0]}
res = 0
max = 0
N.times{|i|
  res += ys[i+1][1] - (ys[i+1][0] - ys[i][0])
  max = res > max ? res : max
  left_res_max_list << max
  left_res_list << res
}
max = 0
max = [max, right_res_list.max, left_res_list.max].max
(N-1).times{|i|
  temp1 = right_res_list[i] - xs[i+1][0] + left_res_max_list[(N-i-2)]
  temp2 = left_res_list[i] - ys[i+1][0] + right_res_max_list[(N-i-2)]
  max = temp1 > max ? temp1 :max
  max = temp2 > max ? temp2 :max
}
puts max




Measured memory_bytes: 21880