akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

class Cube{
 public:
 int f[6];
 Cube(){}
  void roll_z(){roll(1,2,4,3);} //
  void roll_y(){roll(0,2,5,3);} // to W
  void roll_x(){roll(0,1,5,4);} // to N
  void roll( int i, int j, int k, int l){
   int t = f[i]; f[i]=f[j]; f[j]=f[k]; f[k]=f[l]; f[l]=t;
  }
};

bool eq(Cube c1, Cube c2){
  for(int i = 0; i < 6; i++)
      if (c1.f[i] != c2.f[i]) return false;
  return true;
}

bool equal (  Cube c1, Cube c2 ){
    for (int i=0; i < 6; i++){
        for (int j=0; j < 4; j++){
          if ( eq( c1, c2) ) return true;
             c1.roll_z();
          }
          if (i % 2 == 0 ) c1. roll_y();
          else c1.roll_x();
    }
    return false;
}

int main(){
   Cube c1, c2;

for (int i = 0; i <6; i++) cin >> c1.f[i];
for (int i = 0; i <6; i++) cin >> c2.f[i];

if  (equal(c1, c2) ) cout << "Yes" << endl;
else cout << "No" << endl;

return 0;
}


Measured memory_bytes: 3100
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

using namespace std;

const int MAX = 100000;
vector<int> E[MAX];

bool visited[MAX];

int t = 1;

int parent[MAX];
int prenum[MAX];
int lowest[MAX];
int NIL = 100001;

void dfs(int current, int prev) {

	visited[current] = true;
	prenum[current] = lowest[current] = t++;
	for (int i = 0; i < (int) E[current].size(); ++i) {

		int next = E[current][i];

//		cout << "current???" << current << ":next???" << next << endl;

		if (visited[next] == false) {
			parent[next] = current;
			dfs(next, current);
			lowest[current] = min(lowest[current], lowest[next]);
		} else if (next != prev) {
			lowest[current] = min(prenum[next], lowest[current]);
		}
//		cout << "current???" << current << ":lowest[current]???" << lowest[current] << endl;
	}
}

int main() {

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

	for (int i = 0; i < v; ++i) {
		visited[i] = false;
		parent[i] = prenum[i] = lowest[i] = NIL;
	}

	for (int i = 0; i < e; ++i) {
		int s, t;
		scanf("%d %d", &s, &t);

		E[s].push_back(t);
		E[t].push_back(s);
	}

	dfs(0, -1);

	set<int> ans;

	int np = 0;
	for (int i = 1; i < v; ++i) {
		int p = parent[i];
		if (p == 0) {
			np++;
		} else if (prenum[p] <= lowest[i]) {
			ans.insert(parent[i]);
		}
	}

	if (np > 1)
		ans.insert(0);

	for (set<int>::iterator it = ans.begin(); it != ans.end(); it++) {
		cout << *it << endl;
	}

	return 0;
}

Measured memory_bytes: 7020
import math
N,M = map(int,input().split())

if N == 1:
    print(M)
    exit()

m = math.floor(math.sqrt(M))
b = M == m * m
O = set([m]) if b else set()
for i in range(m - b,0,-1):
    if M % i == 0:
        O |= {i,M//i}

O = sorted(O)

# とりあえず計算量とか考えず実装してみる
# Oは照準にソートされている
# Oの要素から o <= M / N となる最大のo

a = M / N
left = 0
right = len(O)-1
while left + 1 != right:
    middle = (left + right)//2
    if O[middle] <= a:
        left = middle
    else:
        right = middle
    
print(O[left])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef int64_t Int;
#define dump(x) cout << (x) << '\n'
Int mod = 1e9+7;
//Int mod = 998244353; 
Int INF = 1e9+7;

int main() {    
    Int n, k;
    cin >> n >> k;
    dump(n - k + 1);
    return 0;  
}

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

for i in range(n+1):#黒くした行の数
    for j in range(m+1):#黒くした列の数
        #print(i,j,(m*i)+((n-i)*j)-(i*j))
        if (m*i)+((n-i)*j-(i*j))==k:
            print("Yes")
            exit()
print("No")


Measured memory_bytes: 2940
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    bool prime[1000005];
    memset(prime,true,sizeof(prime));
    prime[0] = prime[1] = false;
    for(ll i=2;i<=1000000;i++)
    {
    	if(prime[i])
    	{
    		for(ll j=2ll;i*j<=1000000;j++)
	    	{
	    		prime[i*j] = false;
	    	}
    	}
    }
    vl v;
    for(int i=0;i<=1000000;i++)
    {
    	if(prime[i])
    		v.eb(i);
    }
    ll count = 0ll;
    for(int i=0;i<v.size();i++)
    {
    	ll temp = 0ll;
    	while(n%v[i] == 0ll)
    	{
    		temp++;
    		n /= v[i];
    	}
    	ll j = 1ll;
    	while(j<=temp)
    	{
    		count++;
    		temp -= j;
    		j++;
    	}
    }
    if(n>1)
    	count++;
    cout << count << nl;
    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;


int main() {
  int A, B, K; cin >> A >> B >> K;
  rep(i,K) {
    if (i%2==0) {
      A /= 2;
      B += A;
    }
    else {
      B /= 2;
      A += B;
    }
  }
  cout << A << " " << B << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

lli n;

lli bitOnNum(lli num){
	lli cnt=0;
	for(lli i=0;i<n;i++){
		if(num & (1LL<<i))cnt++;
	}
	return cnt;
}


lli dp[1LL<<22]={0};
signed main(){

	cin>>n;
	vector<vector<lli>> p(n);
	REP(i,0,n)REP(j,0,n){
		lli tmp;
		cin>>tmp;
		if(tmp==1)p[i].push_back(j);
	}

	dp[0]=1;
	for(lli i=0;i<n;i++){
		for(lli j=0;j<= (1LL<<n) ;j++){
			if(bitOnNum(j)!=i)continue;
			for(lli k = 0;k<p[i].size();k++){
				lli onBit = (1LL<<p[i].at(k));
				if(j & onBit)continue;
				dp[j|onBit] += dp[j];
				dp[j|onBit] %= MOD;
			}
		}
	}
	cout<<dp[(1LL<<n)-1]<<endl;

	return 0;
}


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

using namespace std;

#define PB push_back
#define MP make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define RFOR(i, b, a) for (int i = b-1; i>=a; --i)
#define FILL(a, b) memset(a, b, sizeof a)
#define ALL(a) a.begin(), a.end()
#define SZ(a) ((int)a.size())

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 1000 * 1000 * 1000;
const LL LINF = 1LL * INF*INF;
const int MAX = 1e5;
const double PI = acos(-1.);
const double EPS = 1e-8;

int main()
{
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	if (SZ(s) == 3)
	{
		reverse(ALL(s));
	}

	cout << s;

	return 0;
}













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

#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main()
{   
    stack<int> st;
    string s;

    while (cin >> s && !cin.eof()) {
        int a, b;

        if (s[0] == '+') {
            b = st.top();
            st.pop();
            a = st.top();
            st.pop();

            st.push(a+b);
        }

        else if (s[0] == '-') {
            b = st.top();
            st.pop();
            a = st.top();
            st.pop();

            st.push(a-b);
        }

        else if (s[0] == '*') {
            b = st.top();
            st.pop();
            a = st.top();
            st.pop();

            st.push(a*b);
        }

        else {
            st.push(stoi(s));

        }
            
    }

    cout << st.top() << endl;

}


Measured memory_bytes: 3180
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = true;

int main(){

    int a, b;
    cin >> a >> b;

    if(a < b){
        cout << 0 << endl;
    }
    else{
        cout << 10 << endl;
    }

}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    S.append("R")
    N=len(S)
    R_count = 0
    L_count = 0
    ans = [0]*N
    Flag = False
    for i in range(N):
        if S[i] == "R":
            if Flag:
                if (R_count+L_count)%2 == 0:
                    ans[i-L_count-1]=(R_count+L_count)//2
                    ans[i-L_count]=(R_count+L_count)//2
                elif (max(R_count,L_count)-1)%2==0:
                    if R_count > L_count:
                        ans[i-L_count-1]=(R_count+L_count)//2+1
                        ans[i-L_count]=(R_count+L_count)//2
                    else:
                        ans[i-L_count-1]=(R_count+L_count)//2
                        ans[i-L_count]=(R_count+L_count)//2+1
                else:
                    if R_count > L_count:
                        ans[i-L_count-1]=(R_count+L_count)//2
                        ans[i-L_count]=(R_count+L_count)//2+1
                    else:
                        ans[i-L_count-1]=(R_count+L_count)//2+1
                        ans[i-L_count]=(R_count+L_count)//2
                R_count=0
                L_count=0
                Flag = False
            R_count += 1
        else:
            L_count += 1
            Flag = True
    print(*ans[:-1])
if __name__ == "__main__":
    main()

Measured memory_bytes: 52488
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long ans = 0;

        for(int a = 1; a < n; a++){
            for(int b = 1; a * b < n; b++){
                ans++;
            }
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 35688
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=200001 ;
int main()
{
   fast ;
   ll k ;
   cin>>k ;
   queue<ll>q ;
   for(ll i=1;i<10;i++)
   {
       q.push(i) ;
   }
   for(ll i=1;i<=k;i++)
   {
      if(i==k)
      {
          cout<<q.front() ;
          exit(0) ;
      }
      ll x=q.front() ;
      q.pop() ;

      if(x%10!=0)
      {
          q.push(10*x+(x%10)-1) ;
      }
      q.push(10*x+x%10) ;
      if(x%10!=9)
      {
          q.push(10*x+x%10+1) ;
      }
   }



}



Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define  endl '\n'
#define all(s) s.begin(),s.end()
#define lowbit(x) (x&-x)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define pb push_back
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int n,m,q,k;
int main()
{
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k<=a) cout<<k;
	else if(k<=a+b) cout<<a;
	else cout<<a-(k-a-b);
}


Measured memory_bytes: 3648
N, K = map(int, input().split())
A = list(map(int, input().split()))

if N == K:
    print(1)
elif N / 2 < K:
    print(2)
else:
    ans = 1
    num = 0
    num += K
    while num < N:
        num += K - 1
        ans += 1
    print(ans)



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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int a, b;

int main() {
	cin >> a >> b;
	
	     if(a + b == 15) { cout << "+" << endl; }
	else if(a * b == 15) { cout << "*" << endl; }
	else                 { cout << "x" << endl; }
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;
const int INF = pow(10, 8);
const ll LINF = ll(1e18);
struct edge{
  int to;
  int cost;
};
int main(){
  int v, e, r;cin>>v>>e>>r;
  vector<vector<edge> > graph(v, vector<edge>());
  vector<ll> dis(v, LINF);
  dis[r]=(ll)0;
  for(int i=0;i<e;i++){
    int s, t, d;cin>>s>>t>>d;
    edge ed = {t, d};
    graph[s].push_back(ed);
  }
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P((ll)0, r));
  while(que.size()){
    P p = que.top();que.pop();
    int x = p.second;
    if(dis[x] < p.first)continue;
    for(edge& ed:graph[x]){
      if(dis[ed.to] > dis[x]+(ll)ed.cost){
        dis[ed.to] = dis[x]+(ll)ed.cost;
        que.push(P(dis[ed.to], ed.to));
      }
    }
  }
  for(int i=0;i<v;i++){
    if(dis[i]==LINF)cout<<"INF"<<endl;
    else cout<<dis[i]<<endl;
  }
  return 0;
}



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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

    ll N; cin >> N;
    ll a[300005];
    ll sum = 0;

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

    ll l[300005]; memset(l,-1,sizeof(l));
    priority_queue<ll, vector<ll>, greater<ll> > lque;

    for (int i = 0;i < N*3;i++){
        if(lque.size() < N){
            l[i] = -1;
            lque.push(a[i]);
            sum += a[i];
            if(lque.size() == N) l[i] = sum;

        }else{
            if(lque.top() < a[i]){
                sum -= lque.top(); lque.pop();
                sum += a[i];
                lque.push(a[i]);
                l[i] = sum;
            }else{
                l[i] = sum;
            }
        }
    }

    ll r[300005]; memset(r,-1,sizeof(r));
    priority_queue<ll> rque;
    sum = 0;

    for (int i = N*3-1;i >= 0;i--){
        if(rque.size() < N){
            r[i] = -1;
            rque.push(a[i]);
            sum += a[i];
            if(rque.size() == N) r[i] = sum;
        }else{
            if(rque.top() > a[i]){
                sum -= rque.top(); rque.pop();
                sum += a[i];
                rque.push(a[i]);
                r[i] = sum;
            }else{
                r[i] = sum;
            }
        }
    }

    ll ans = LLONG_MIN;

    for (int i = 0;i < 3*N;i++){
        //cout << l[i] << " " << r[i+1] << endl;
        if(r[i+1] != -1 && l[i] != -1){
            ans = max(l[i]-r[i+1], ans);
        }
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 9588
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<complex>
#define lol(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;

int main(){
	string s;
	cin>>s;
	int cnt[3]={0};
	for(int i=0;i<s.size();i++){
		cnt[s[i]-'a']++;
	}
	int a=-1;
	a=max(a,abs(cnt[0]-cnt[1]));
	a=max(a,abs(cnt[2]-cnt[1]));
	a=max(a,abs(cnt[0]-cnt[2]));
	if(a<=1)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second
#define rep(i,n) for(int i=0;i<int(n);i++)
using namespace std;
vector<int> adj[100005];

vector<int> dist;
void dfs(int v, int d=0, int p=-1){
  dist[v] = d;
  for(int u: adj[v]){
    if(u==p) continue;
    dfs(u, d+1, v);
  }
}

vector<int> calcDist(int v){
  dist = vector<int>(100005,0);
  dfs(v);
  return dist;
}

int main(){
  int n,u,v;
  cin>>n>>u>>v;
  u--; v--;
  rep(i,n-1){
    int a, b;
    cin>>a>>b;
    a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  vector<int> distu = calcDist(u);
  vector<int> distv = calcDist(v);

  int mx = 0;
  rep(i,n) if(distu[i]<distv[i]) mx = max(mx,distv[i]);
  cout<<mx - 1<<endl;

  return 0;
}


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

int main() {
  int n;
  cin >> n;
  long long a[n+1];
  for (int i =1; i <= n; ++i) cin >> a[i];
  vector<long long> dp(n+1,0);
	dp[1] = 0;
	vector<long long> prefix(n+1);
	prefix[1] = a[1];
	for(int i=3;i<=n;i+=2){
		prefix[i] = prefix[i-2]+a[i];
	}
	for(int i=2;i<=n;i++){
		if(i&1){
			dp[i]=max(dp[i-1],dp[i-2]+a[i]);
		}else{
			dp[i] = a[i] + dp[i-2];
			dp[i] = max(dp[i],prefix[i-1]);
		}
	}
	cout<<dp[n];
  return 0;
}


Measured memory_bytes: 8004
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<list>
#include<iomanip>
#include<cstdio>
using namespace std;
#define ll long long






int main()
{
	ll n,x,t;
	cin>>n>>x>>t;
	ll num;
	if(n%x==0)
	{
		num=n/x;
	}
	else
	{
		num=(n/x)+1;
	}
	cout<<num*t<<"\n";
}

Measured memory_bytes: 3564
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static final int ALF = 26;

    Main() {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int[][] board = new int[H + 1][W + 1];
        for (int y = 0; y < H; y++) {
            char[] s = sc.next().toCharArray();
            for (int x = 0; x < W; x++) {
                board[y][x] = s[x];
            }
        }
        for (int y = 0; y < H; y++) {
            int cnt = 0;
            for (int x = 0; x < W; x++) {
                if (board[y][x] == '#')
                    cnt++;
            }
            board[y][W] = cnt;
        }
        for (int x = 0; x < W; x++) {
            int cnt = 0;
            for (int y = 0; y < H; y++) {
                if (board[y][x] == '#')
                    cnt++;
            }
            board[H][x] = cnt;
        }

        for (int y = 0; y < H; y++) {
            if (board[y][W] == 0)
                continue;
            for (int x = 0; x < W; x++) {
                if (board[H][x] == 0)
                    continue;
                System.out.print((char) board[y][x]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        new Main();
    }
}


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

const int N = 100005;

int n, d[N];
deque<int> q;

int main(){
    scanf("%d", &n);
    fill(d, d + n, N);
    d[1] = 1;
    q.push_back(1);
    while(true){
        int c = q.front();
        q.pop_front();
        if(!c){ printf("%d\n", d[c]); return 0; }
        int x = (c + 1) % n;
        int y = (c * 10) % n;
        if(d[x] > d[c] + 1){
            q.push_back(x);
            d[x] = d[c] + 1;
        }
        if(d[y] > d[c]){
            q.push_front(y);
            d[y] = d[c];
        }
    }
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,beet=0;
string s="";
random_device rnd;

string Query(vi a){
	beet++;
	assert(a.size()==n);
	cout<<'?';
	for(auto i:a) cout<<' '<<i+1;
	cout<<endl;
	if(s==""){
		string t;
		cin>>t;
		return t;
	}
	int t=0;
	for(auto i:a){
		if(s[i]=='R') t++;
		else t--;
	}
	return (t>0?"Red":"Blue");
}

void Answer(string t){
	cout<<"! "<<t<<endl;
//	assert(s==t);
//	cout<<"count : "<<beet<<endl;
}

int main(){
	cin>>n;
//	cin>>s;
	string res(2*n,'A');
	if(n==1){
		for(int i=0;i<2;i++) res[i]=Query(vi(1,i))[0];
		Answer(res);
		return 0;
	}
	vi a(n),b(2*n);
	int x,y;
	int l=0,r=n;
	for(int i=0;i<n;i++) a[i]=i;
	auto tmp=Query(a);
	while(r-l>1){
		int m=(l+r)/2;
		for(int i=0;i<n;i++) a[i]=m+i;
		if(Query(a)==tmp) l=m;
		else r=m;
	}
	for(int i=0;i<n;i++) a[i]=i+l;
	x=a[0];
	y=a[n-1]+1;
	for(int i=0;i<n-1;i++) a[i]=a[i+1];
	for(int i=0;i<n-1;i++) b[a[i]]++;
	for(int i=0;i<2*n;i++) if(!b[i]&&i!=x){
		a[n-1]=i;
		res[i]=Query(a)[0];
	}
	int I=0;
	for(int i=0;i<2*n;i++) if(!b[i]&&i!=x&&i!=y) a[I++]=i;
	for(int i=0;i<2*n;i++) if(b[i]||i==x){
		a[n-1]=i;
		res[i]=Query(a)[0];
	}
	Answer(res);
}

Measured memory_bytes: 724
#include <stdio.h>
#include <math.h>
//#define BUFSIZE 100

	int f(long int x, long int y);

	int main() {
		long int n, a, b;
		int min, r;
		scanf("%ld",&n);
		if(n<1 || n>10000000000){
			printf("error\n");
			return 1;
		}
		a = 1;
		b = n;
		double t = n;
		min = f(a,b);
		do{
			a++;
			if(n % a == 0){
				b = n / a;
				r = f(a,b);
				if(r < min) min = r;
			}
		}while(a < sqrt(t)); 
		/*while(a < sqrt(t)){
			do{
				a++;
			}while(n % a != 0);
			b = n / a;
			r = f(a,b);
			if(r < min) min = r;
		}*/
		printf("%d",min);
		return 0;
	}
	
	int f(long int x, long int y){
		/*char buf[BUFSIZE];
		if(x >= y) return sprintf(buf,"%ld",x);
		else return sprintf(buf,"%ld",y);*/
		int c = 0;
		if(x >= y){
			while(x>0){
				x = x / 10;
				c++;
			}
		}
		else{
			while(y>0){
				y = y / 10;
				c++;
			}
		}
		return c;
	}

Measured memory_bytes: 128
#include <stdio.h>

int main(){
    int a, b, c, tmp;

    // ??\???
    scanf("%d %d %d", &a, &b, &c);

    // a???b????????§????????´????????????
    if(a > b){
        tmp = a;
        a = b;
        b = tmp;
    }

    // a???c????????§????????´????????????(a???????°?????????????)
    if(a > c)  {
        tmp = c;
        c = a;
        a = tmp;
    }

    // b???c????????§????????´????????????(b???2??????????°?????????????
    // ??¨???????????¨????????¶??????c?????????????????§????????????(?????§???)
    if (b > c)  {
        tmp = c;
        c = b;
        b = tmp;
    }

    printf("%d %d %d\n", a, b, c);
    return 0;
}

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

int n,m,dp[5][10010];

int dfs(int now,int sy)
{
	if(now>3) return !sy;
	if(dp[now][sy]!=-1) return dp[now][sy];
	int i,res=0;
	for(i=0;i<=min(n,m);i++)
	{
		res+=dfs(now+1,sy-i);
	}
	return dp[now][sy]=res;
}

int main()
{
	int a,b;
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	cout<<dfs(1,m);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	long long x, y, a, b, c, sum = 0; 
	cin >> x >> y >> a >> b >> c;
	
	deque<long long> p(a), q(b), r(c);
	deque<long long> red(x), green(y);
	
	for (int i = 0; i < a; i++) cin >> p[i];
	for (int i = 0; i < b; i++) cin >> q[i];
	for (int i = 0; i < c; i++) cin >> r[i];
	
	sort(p.begin(), p.end(), greater<long long>());
	sort(q.begin(), q.end(), greater<long long>());
	sort(r.begin(), r.end(), greater<long long>());
	
	for (int i = 0; i < x; i++) red[i] = p[i];
	for (int i = 0; i < y; i++) green[i] = q[i];
	
	while (!r.empty()) {
		if (green.back() > red.back()) {
			if (r.front() > red.back()) {
				red.pop_back();
				red.push_front(r.front());
			}
		}
		else {
			if (r.front() > green.back()) {
				green.pop_back();
				green.push_front(r.front());
			}
		}
		
		r.pop_front();
	}
	
	for (int i = 0; i < x; i++) sum += red[i];
	for (int i = 0; i < y; i++) sum += green[i];
	
	cout << sum;
	
	return 0;
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
int flag[1001];
map<int,int>mp;
map<int,int>mp1;

int main()
{
    string s,s1;
    int c=0;
    cin>>s;
   if(s=="Sunny")
    cout<<"Cloudy"<<"\n";
   if(s=="Cloudy")
   cout<<"Rainy"<<"\n";
   if(s=="Rainy")
    cout<<"Sunny"<<"\n";

}


Measured memory_bytes: 256
a,b=map(int,input().split())
c=[]
for i in range(a):
  c+=[list(input())]
for i in range(a):
  for j in range(b):
    if c[i][j]=='.':
      d=0
      for k in range(i-1,i+2):
        for l in range(j-1,j+2):
          if 0<=k and k<a and 0<=l and l<b:
            d+=c[k][l]=='#'
      c[i][j]=str(d)
for i in c:
  print(''.join(i))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int i=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int i=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1'000'000'007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }


class mint {
    using u64 = std::uint_fast64_t;
    u64 x;

public:
    constexpr mint(const u64 x = 0) noexcept : x(x % MOD) {}
    constexpr u64 &value() noexcept { return x; }
    constexpr const u64 &value() const noexcept { return x; }
    constexpr mint operator+(const mint rhs) const noexcept { return mint(*this) += rhs; }
    constexpr mint operator-(const mint rhs) const noexcept { return mint(*this) -= rhs; }
    constexpr mint operator*(const mint rhs) const noexcept { return mint(*this) *= rhs; }
    constexpr mint operator/(const mint rhs) const noexcept { return mint(*this) /= rhs; }
    constexpr mint &operator+=(const mint rhs) noexcept {
        if((x += rhs.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr mint &operator-=(const mint rhs) noexcept {
        if((x += MOD - rhs.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr mint &operator*=(const mint rhs) noexcept {
        x = x * rhs.x % MOD;
        return *this;
    }
    constexpr mint &operator/=(mint rhs) noexcept {
        u64 exp = MOD - 2;
        while (exp) {
            if (exp % 2) *this *= rhs;
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
    bool operator==(const mint &rhs) const { return x == rhs.x; }
    bool operator!=(const mint &rhs) const { return x != rhs.x; }
    friend ostream& operator<<(ostream& os, const mint &m){
        return os << m.x;
    }
    friend istream &operator>>(istream &is, mint &m) {
        u64 x;
        is >> x;
        m = mint(x);
        return (is);
    }
};


mint fac[555555];

mint bipow(mint n, int k){
    if(k==0) return 1;
    if(k%2==0){
        mint tmp = bipow(n, k/2);
        return tmp * tmp;
    }else{
        return n * bipow(n, k-1);
    }
}

mint comb(int n, int k){
    mint a = fac[n];
    mint b = fac[k];
    mint c = fac[n-k];
    return a/(b*c);
}

mint perm(int n, int k){
    mint a = fac[n];
    mint b = fac[n-k];
    return a/b;
}

int main(){
    fac[0] = 1;
    for(int i=1; i<555555; i++)
        fac[i] = fac[i-1] * mint(i);

    int N, M;
    cin >> N >> M;

    mint ans;
    for(int n=0; n<=N; n++){
        mint tmp0 = perm(M-n, N-n);
        mint tmp = comb(N, n) * perm(M, n) * tmp0 * tmp0;
        if(n%2) ans -= tmp;
        else ans += tmp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7912
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
        Scanner sc = new Scanner(System.in);
		String First = "";
		
		while(sc.hasNext()){
			if(First==""){
				First = sc.nextLine();
			}else{
				String str = sc.nextLine();
				
				str = str.replaceAll("Hoshino", "Hoshina");
				System.out.println(str);
			}
		}
	}
}

Measured memory_bytes: 17400
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdint>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <functional>
#include <bitset>
#include <queue>

#include <boost/range/irange.hpp>
using boost::irange;

#include <boost/utility/string_ref.hpp>
using string_view = boost::string_ref;

#include <boost/function_output_iterator.hpp>

using namespace std;

template<class T>
constexpr T gcd(T m, T n)
{
    return n == 0 ? (m < 0 ? -m : m) : gcd(n, m % n);
}


int main()
{
    int n;;
    cin >> n;
    vector<int> as(n);
    for(auto& a : as) cin >> a;
    
    vector<int> gcd_r(n);
    vector<int> gcd_l(n);
    
    gcd_l[0] = as[0];
    gcd_r[n-1] = as[n-1];
    
    for(int i : irange(1, n))
    {
        gcd_l[i]     = gcd(gcd_l[i-1], as[i]);
        gcd_r[n-i-1] = gcd(gcd_r[n-i], as[n-i-1]);
    }
    
    int maxgcd = 0;
    
    maxgcd = max(maxgcd, gcd_r[1]);
    maxgcd = max(maxgcd, gcd_l[n-2]);
    
    for(int i : irange(1, n-1))
    {
        maxgcd = max(maxgcd, gcd(gcd_r[i+1], gcd_l[i-1]));
    }
    
    cout << maxgcd << '\n';
    
    return 0;
}


Measured memory_bytes: 1408
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	P = getlist()
	B = [0] * (N + 1)
	for i in range(N):
		B[i + 1] = B[i] + P[i]
	# print(B)
	ans = 0
	for i in range(N - K + 1):
		val = B[i + K] - B[i]
		ans = max(ans, val)

	ans = (ans + K) / 2
	print(ans)


if __name__ == '__main__':
	main()

Measured memory_bytes: 66800
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+3;
int ar[MAXN];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int N;
	cin >> N;
	for(int i=1;i<N;i++){
		int a;cin >> a;
		ar[a]++;
	}
	for(int i=1;i<=N;i++) cout << ar[i] << '\n';
}

Measured memory_bytes: 4396
n, *A = map(int, open(0).read().split())
a0 = A[0]
s = 0
for i in range(1, n):
    a1 = A[i]
    if a0 <= a1:
        a0 = a1
    else:
        s += a0 - a1
        a1 = a0
print(s)

Measured memory_bytes: 33188
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
count = 0
ans = []
for i in range(h):
    for j in range(w-1):
        if a[i][j] % 2 == 1:
            a[i][j+1] += 1
            a[i][j] -= 1
            count += 1
            ans.append([i+1, j+1, i+1, j+2])

for i in range(h-1):
    if a[i][w-1] % 2 == 1:
        a[i+1][w-1] += 1
        a[i][w-1] -= 1
        count += 1
        ans.append([i+1, w, i+2, w])
        
print(count)
for i in range(count):
    print(*ans[i])

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    Scd(N);

    vi p(N);

    int ans = 0;
    Rep(i,N){
        Scd(p[i]);
        if( p[i] != i+1 ) ans++;
    }

    printf ("%s\n", ans > 2 ? "NO" : "YES" );

    return 0;
}



Measured memory_bytes: 256
function main()
  local n = tonumber(io.read())
  local a = {}
  for i in string.gmatch(io.read(), "[^ ]+") do
    table.insert(a, tonumber(i))
  end

  local ans = 0
  local state = 0
  for i = 2, n do
    local diff = a[i] - a[i-1]
    if state > 0 then
      if diff < 0 then
        ans = ans + 1
        state = 0
      end
    elseif state < 0 then
      if diff > 0 then
        ans = ans + 1
        state = 0
      end
    else
      if diff > 0 then
        state = 1
      elseif diff < 0 then
        state = -1
      end
    end
  end
  print(ans + 1)
end

main()


Measured memory_bytes: 6064
#include <atcoder/segtree>
#include <cstdio>
#include <vector>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return max(a, b); }

int e() { return -1; }

int target;

bool f(int v) { return v < target; }

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

    segtree<int, op, e> seg(a);

    for (int i = 0; i < q; i++) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x, v;
            scanf("%d %d", &x, &v);
            x--;
            seg.set(x, v);
        } else if (t == 2) {
            int l, r;
            scanf("%d %d", &l, &r);
            l--;
            printf("%d\n", seg.prod(l, r));
        } else if (t == 3) {
            int p;
            scanf("%d %d", &p, &target);
            p--;
            printf("%d\n", seg.max_right<f>(p) + 1);
        }
    }
}

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

using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;

int main()
{
	std::ios_base::sync_with_stdio(0);
	
	u32 n;

	std::cin >> n;
  
  	u32 odd = 0;

	for(u32 i=1; i<=n; i++)
	{
		if(i%2 != 0) odd++;
	}
  
  	std::cout << (float(odd)/n) << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define hi cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define pf push_front
#define ins insert

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
unsigned XorShift(void){static unsigned x = 123456789;static unsigned y = 362436069;static unsigned z = 521288629;static unsigned w = 88675123;unsigned t;t = x ^ (x << 11);x = y; y = z; z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}
//}

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

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

struct FenwickTree{
	int n;
	vector<int>data;
	FenwickTree(int n=0):n(n){
		data.resize(n+1);
	}
	void add(int k,int x){
		for(k++;k<=n;k+=k&-k)data[k]+=x;
	}
	int sum(int k){
		int ret=0;
		for(k++;k;k-=k&-k)ret+=data[k];
		return ret;
	}
};

int n;
int a[111111],s[111111];

bool c(int x){
	rep(i,n){
		s[i+1]=s[i];
		a[i]<x?s[i+1]++:s[i+1]--;
	}
	vint v;
	rep(i,n+1)v.pb(s[i]);
	sort(all(v));
	rep(i,n+1)s[i]=lower_bound(all(v),s[i])-v.begin();
	int res=0;
	FenwickTree ft(n+1208);
	rep(i,n){
		ft.add(s[i],1);
		res+=ft.sum(s[i+1]-1);
	}
	return res<((n*(n+1)+4)/4);
}

main(){
	cin>>n;
	rep(i,n)cin>>a[i];
	int l=0,r=INT_MAX;
	while(r-l>1){
		int m=(l+r)/2;
		c(m)?l=m:r=m;
	}
	dump(l);
}

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

int main() {
  ll x, y, a, b, c; cin >> x >> y >> a >> b >> c;
  vector<int> p(a), q(b), r(c);
  rep(i, a) cin >> p[i];
  rep(i, b) cin >> q[i];
  rep(i, c) cin >> r[i];
  sort(p.rbegin(), p.rend());
  sort(q.rbegin(), q.rend());
  vector<ll> s;
  rep(i, x) s.push_back(p[i]);
  rep(i, y) s.push_back(q[i]);
  rep(i, c) s.push_back(r[i]);
  sort(s.rbegin(), s.rend());
  ll ans = 0;
  rep(i, x+y) ans += s[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 7664
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
typedef uint_fast16_t fint16;
typedef uint_fast32_t fint32;
typedef uint_fast64_t fint64;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define exists(x,m) m.find(x) != m.end()
#define umap unordered_map
#define uset unordered_set
#define pq priority_queue

const ll MOD = 1e9 + 7;

struct DSU {
	int n, num_components;
	vi parent;
	vi size;

	DSU(int num_elements)
	:n(num_elements), num_components(num_elements)
	{
		size = vi(n, 1);
		parent = vi(n, 0);
		rep(i, n) parent[i] = i;
	}

	int find(int x){
		if (parent[x] != x) {
			parent[x] = find(parent[x]);
		}
		return parent[x];
	}

	bool join(int x, int y) {
		int xs = find(x), ys = find(y);
		if (xs == ys) return false;
		if (size[xs] < size[ys]) swap(xs, ys);
		size[xs] += size[ys];
		parent[ys] = xs;
		num_components--;
		return true;
	}

};

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n, m; cin >> n >> m;
	DSU dsu = DSU(n);
	rep(i, m) {
		int u, v; cin >> u >> v;
		u--, v--;
		dsu.join(u, v);
	}
	cout << dsu.num_components-1;
}

Measured memory_bytes: 3924
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		solve();
	}

	public static void solve() {
  	Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		List<Integer> a = new ArrayList<>();
		for(int i = 0; i < n; i++) a.add(sc.nextInt());
		Collections.sort(a);
		out.println(a.get(n-1) - a.get(0));
		sc.close();
		out.flush();
	}
}

Measured memory_bytes: 21716
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end
def debug(k,v) puts "#{k}: #{v}" end
def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

#$stdin = File.open('input.txt')

n,d = gsmi
xys = Array.new(n){gsmi}
puts xys.count{|p,q| Math.sqrt(p**2+q**2) <= d }


Measured memory_bytes: 28332
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

ll maxop(ll n){
  for(int i=1;i<100;i++){
    if(i*(i+1)>2*n){
      return i-1;
      break;
    }
  }
}

int main(){
  ll n,ans=0; cin>>n;
  map<ll,ll> mp;
  ll q=n;
  for(ll i=2; i<=sqrt(q); i++){
    if(n%i==0){
      n/=i;
      mp[i]++;
      i-=1;
    }
    if(n==1){
      break;
    }
  }
  if(n!=1){
    mp[n]++;
  }
  for(auto p:mp){
    ans+=maxop(p.second);
  }
  cout<<ans;
}

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

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vi = vector<int>;
using vchar = vector<char>;
using vstr = vector<string>;
using pll =  pair<ll,ll>;

const ll mod = 1000000007;
const ll inf = 1000000000000000;

#define pi acos(-1)
#define pb push_back
#define test int TEST;cin>>TEST;while(TEST--)
#define vsort(xx) sort(xx.begin(),xx.end())
#define vrevsort(xx) sort(xx.rbegin(),xx.rend())


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);   
   ll ans=inf;
    ll n,m; cin>>n>>m;
    if (n>=3){
        if (n%3) ans=min(ans,m); else ans=0;
    }
    if (m>=3){
        if (m%3) ans=min(ans,n); else ans=0;
    }
    for (ll i=1;i<=n-1;i++){
        ll a=i*m;
        ll b=(m/2)*(n-i);
        ll c=(m-m/2)*(n-i);
        ans=min(ans,max({a,b,c})-min({a,b,c}));
    }
    for (ll i=1;i<=m-1;i++){
        ll a=i*n;
        ll b=(n/2)*(m-i);
        ll c=(n-n/2)*(m-i);
        ans=min(ans,max({a,b,c})-min({a,b,c}));
    }
    cout<<ans<<"\n";
   
   
    return 0;
}




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

const int MAXN = 200005;

int lc[MAXN], rc[MAXN], top = 0, root = 0;
int sg[MAXN];

int N;
long long L;
char str[MAXN];

void push(int &nd, const char *str)
{
	if (!nd) nd = ++top;
	if (*str == '\0') return; 
	push(*str == '0' ? lc[nd] : rc[nd], str+1);
}

long long cnt = 0;
inline long long lowbit(long long i)
{ return i&(-i); }

void dfs(int nd, long long dep)
{
	if (!nd) return;
	dfs(lc[nd], dep-1), dfs(rc[nd], dep-1);
	if ((!lc[nd] || !rc[nd]) && lc[nd]+rc[nd]) {
	        cnt ^= lowbit(dep);
	}
}

int main()
{
	scanf("%d%lld", &N, &L);
	for (int i = 1; i <= N; i++) {
		scanf("%s", str);
		push(root, str);
	}
	dfs(root, L);
	if (cnt != 0) cout << "Alice" << endl;
	else cout << "Bob" << endl;
	return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h> 
using namespace std;
 
int main() {
  int a,b;
  cin>>a>>b;
  if((a+b)%2==0) {
    cout<<(a+b)/2<<endl;
  }
  else {
    cout<<(a+b+1)/2<<endl;
  }
}

Measured memory_bytes: 256
/*
 * WelcomeToAtCoder.cpp
 *
 *  Created on: 2020/02/19
 *      Author: black
 */
#include <iostream>
#include <algorithm>
using namespace std;


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

	int c[500], s[500], f[500];

	for(int i = 1; i<n;++i){
		cin >> c[i] >> s[i] >> f[i];
	}

	int count;

	for(int i=1; i<n; ++i){
		count = s[i] + c[i];

		for(int j = i+1; j<n; ++j){
			if (count <= s[j]){
				count = s[j];
			}
			else {
				while(1){
					if (count%f[j]==0){
						break;
					}
					++count;
				}
			}
			count += c[j];
		}
		cout << count << endl;
	}
	cout << 0 << endl;

	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

/**
 * Swapping Bibs
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		line = br.readLine();

		int N, M;
		N = parseInt(line.substring(0, line.indexOf(' ')));
		M = parseInt(line.substring(line.indexOf(' ') + 1));
		int[] zs = new int[N];

		for (int i = 0; i < N; i++) {
			zs[i] = parseInt(br.readLine());
		}

		for (int k = 1; k <= M; k++) {
			for (int i = 0; i < N - 1; i++) {
				if (zs[i] % k > zs[i + 1] % k) {
					int tmp = zs[i];
					zs[i] = zs[i + 1];
					zs[i + 1] = tmp;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			System.out.println(zs[i]);
		}
	}
}

Measured memory_bytes: 24340
#include<bits/stdc++.h>
using namespace std;
    static const double pi = 3.141592653589793;
 typedef pair<int64_t,int64_t> P;


int main() {
int64_t a,b;
  cin>>a>>b;
  int64_t cost[a];
  for(int i=0;i<a;i++)
  {
  int64_t b;
  cin>>b;
    cost[i]=b;
  }
  int64_t dp[a];
  for(int i=0;i<a;i++) dp[i]=1000000000;
  dp[0]=0;
  dp[1]=abs(cost[1]-cost[0]);
  for(int j=2;j<a;j++)
  {
    
 for(int i=1;i<b+1;i++){
   if(j-i<0) break; 
   else dp[j]=min(dp[j],dp[j-i]+abs(cost[j]-cost[j-i]));
 } 
 }
  cout<<dp[a-1];
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	ll n,i,j;
	cin >> n;
	double a[n];
	
	for(i=1;i<=n;i++)
		cin >> a[i];
		
	double dp[n+1][n+1];
	dp[1][0]=(1-a[1]);
	dp[1][1]=a[1];
	for(i=2;i<n;i++)
		dp[1][i]=0;
		
	for(i=2;i<=n;i++)
	{
		dp[i][0]=dp[i-1][0]*(1-a[i]);
		for(j=1;j<i;j++)	
			dp[i][j]=dp[i-1][j]*(1-a[i])+dp[i-1][j-1]*a[i];
			
		dp[i][i]=dp[i-1][i-1]*a[i];
	}
	cout<<setprecision(12);
	double ans=0;
	ll w=n/2+1;
	for(i=w;i<=n;i++)
		ans+=dp[n][i];
		
	cout<<ans<<"\n";
}

Measured memory_bytes: 70400