akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<utility>
#include<queue>
#include<functional>
#include<algorithm>
#include<cstring>
#include<vector>
#include<climits>
#include<map>
using namespace std;
#define FOR(i,n) for(int i=0;i<(int)n;i++)
#define FORI(i,k,n) for(int i=k;i<(int)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define INF (2<<25)
typedef pair<int,int> pii;
typedef vector<int> vi;

int main()
{
	while(true)
	{
		string a[3];
		cin>>a[0];
		if(a[0]=="0")break;
		cin>>a[1]>>a[2];
		bool isdraw=true;
		bool end=false;
		FOR(i,3)
		{
			bool equal[2]={1,1};
			if(end)break;
			FOR(j,3)
			{
				if(a[i][j]!=a[i][0])equal[0]=false;
				if(a[j][i]!=a[0][i])equal[1]=false;
			}
			FOR(j,2)
			{
				if(equal[j]&&a[(j?0:i)][j?i:0]!='+')
				{
					isdraw=false;
					cout<<a[(j?0:i)][j?i:0]<<endl;
					end=true;
					break;
				}
			}
		}
		bool equal[2]={1,1};
		FOR(i,3)
		{
			if(a[i][i]!=a[0][0])equal[0]=false;
			if(a[i][2-i]!=a[0][2])equal[1]=false;
		}
		FOR(j,2)
		{
			if(end)break;
			if(equal[j]&&a[(j?0:0)][j?2:0]!='+')
			{
				isdraw=false;
				cout<<a[(j?0:0)][j?2:0]<<endl;
				end=true;
				break;
			}
		}
		if(isdraw)cout<<"NA"<<endl;
	}
}

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

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

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main(int argc, char const *argv[]) {
  int n; cin >> n;
  vector<ll> a(n); REP(i,n) cin >> a[i];
  vector<ll> _abs(n);
  ll counter = 0;
  REP(i,n) {
    if (a[i] < 0) {
      counter++;
    }
    _abs[i] = abs(a[i]);
  }

  sort(ALL(_abs));
  ll ans = 0;
  if (counter % 2) {
    REP(i,n) ans += _abs[i];
    ans -= 2 * _abs[0];
  } else {
    REP(i,n) ans += _abs[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define ll long long
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mt make_tuple
#define eb emplace_back
using namespace std;
const int N=1e5+5;
const ll inf=3e18;

void solve(){
    ll x;
    ll in=100;
    ll cnt=0;
    cin>>x;
    while(in<x){
        in=in/100+in;
        cnt++;
    }
    cout<<cnt<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll t,p;
    t=1;
    //cin>>t;
    for(p=1;p<=t;p++){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define maxn 200005
#define MOD 1000000007
#define INF 10000000000

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

void solve(){

    string s, s1, s2, s3;
    cin >> s;
    s1 = s;
    reverse(s.begin(), s.end());
    s2 = s.substr(0, (s.length()-1)/2);
    s3 = s2; //cout << s3 << " ";
    reverse(s2.begin(), s2.end());
    if(s == s1 && s2 == s3){
        cout << "Yes\n";
    }
    else cout << "No\n";
}

int main()
{
    fast();
    int t= 1;
    while(t--){
        solve();
    }
}


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

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vi;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define nl cout<<'\n'
#define pb push_back
#define all(s) s.begin(),s.end()
#define bs binary_search

#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a)*(b)/(__gcd((a),(b)))

const int Mod=1e9+7;
#define sum(a,b) (((a)%Mod)+((b)%Mod))%Mod
#define sub(a,b) (((a)%Mod)-((b)%Mod))%Mod
#define mul(a,b) (((a)%Mod)*((b)%Mod))%Mod
#define digit(x) floor((log10(x))+1)


#define count1(x) __builtin_popcount(x)

#define dbg(x) cout << #x <<":"<<x<<endl;

bool isPowerOfTwo (int x)  
{  
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));  
} 

ll pow(ll x, ll y, ll mod)
{
	int ans=1;
	while(y)
	{
		if(y&1)
			ans=(ans*x)%mod;
		y/=2;
		x=(x*x)%mod;
	}
	return ans;
}

int main()
{
	fast;
	ll a;
	cin >> a;
	cout << a+a*a+a*a*a << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define int long long
#define mod 1000000007
#define fi first
#define se second
#define be begin()
#define en end()
#define re reverse
#define Set setprecision
#define NO cout<<"NO\n"
#define YES cout<<"YES\n"
#define No cout<<"No\n"
#define Yes cout<<"Yes\n"
const int INFi=2147483647;
const long long INFl=9223372036854775807LL;
template<typename T> T abs(T a,T b){
    return max(a,b)-min(a,b);
}
template<typename T> T lcm(T a,T b){//最小公倍数
    return (a*b)/gcd(a,b);
}
int gcd(int a,int b){//最大公約数
    int c=a%b;
    while(true){
	if(c==0) break;
	a=b;
	b=c;
	c=a%b;
    }
    return b;
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[3][3]={};
    bool A[3][3]={};
    int n,b;
    for(int i=0;i<3;i++){
	for(int j=0;j<3;j++) cin>>a[i][j];
    }
    cin>>n;
    for(int i=0;i<n;i++){
	cin>>b;
	for(int j=0;j<3;j++){
	    for(int k=0;k<3;k++){
		if(a[j][k]==b) A[j][k]=true;
	    }
	}
    }
    int c=0;
    for(int i=0;i<3;i++){
	c=0;
	for(int j=1;j<3;j++){
	    if(A[i][j]==1&&A[i][j-1]==A[i][j]) c++;
	}
	if(c==2){
	    Yes;
	    return 0;
	}
    }
    for(int j=0;j<3;j++){
	c=0;
	for(int i=1;i<3;i++){
	    if(A[i][j]==1&&A[i-1][j]==A[i][j]) c++;
	}
	if(c==2){
	    Yes;
	    return 0;
	}
    }
    //cout<<A[1][1]<<" "<<A[0][0]<<" "<<A[2][2]<<"\n";
    if(A[1][1]==true){
	if(A[0][0]==true){
	    if(A[2][2]==true){
		cout<<"Yes\n";
		return 0;
	    }
	}
    }
    if(A[1][1]==true){
	if(A[0][2]==true){
	    if(A[2][0]==true){
		Yes;
		return 0;
	    }
	}
    }
    No;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
    
    
int main(){
    string s;
    cin>>s;
    if ((s[2]==s[3])&&s[4]==s[5])
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef complex<double> P;

const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

const int sz = 20;



int main(){
  int n;
  double r, theta;
  double g[sz + 1][sz][sz];
 
  cin >> n;
  cin >> r >> theta;
  
  vector<P> pts(n);
  REP(i, n) cin >> pts[i].real() >> pts[i].imag();
    
  fill(&g[0][0][0], &g[0][0][0] + (sz + 1) * sz * sz, INF);
  
  REP(i, n + 1)REP(j, n)REP(k, n)if(j != k){
    if(i == n){
      g[i][j][k] = abs(pts[j] - pts[k]);
    }else{
      double ang = arg(pts[j] - pts[i]) - arg(pts[k] - pts[j]);
      while(ang > M_PI) ang -= M_PI * 2;
      while(ang < -M_PI) ang += M_PI * 2;
      ang *= 180 / M_PI;
      if(abs(ang) < theta + EPS) g[i][j][k] = abs(pts[j] - pts[k]);
    }
  }
  
  double dp[2][sz+1][sz];
  int count = -1;
  bool update = true;

  fill(&dp[0][0][0], &dp[0][0][0] + 2 * (sz + 1) * sz, INF);
  
  dp[0][n][0] = 0.0;
  while(update){
    update = false;
    int cur = ++count % 2;
    int nxt = 1 - cur;
    fill(&dp[nxt][0][0], &dp[nxt][0][0] + (sz + 1) * sz, INF);
    
    
    REP(j, n)REP(k, n){
      REP(i, n + 1){
        dp[nxt][j][k] = min(dp[nxt][j][k], dp[cur][i][j] + g[i][j][k]);
      }
      if(dp[nxt][j][k] < r + EPS){
        update = true;
      }
    }
  }
  
  cout << count << endl;
  
  return 0;
}
  

Measured memory_bytes: 1396
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<random>
using namespace std;

int main(){
    int n,k,h[100000], c[100000];
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> h[i];
    }
    c[0] = 0;
    c[1] = abs(h[1] - h[0]);
    int m(2147483647),buf;
    for(int i=2;i<n;i++){
        m = 2147483647;
        if(i < k){
            for(int j=1;j <= i;j++){//i-j段めから
                buf = c[i-j] + abs(h[i-j] - h[i]);
                m = min(m,buf);
            }
            c[i] = m;
        }else{
            for(int j=1;j <= k;j++){
                buf = c[i-j] + abs(h[i-j] - h[i]);
                m = min(m,buf);
            }
            c[i] = m;
        }
        
    }
    cout << c[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
#include <complex>
using namespace std;
typedef pair<int,int> P;

int main(){
    int n,i;
    while(cin>>n&&n){
        vector<P> ra;
        for(i=0;i<n;i++){
            int id,m1,m2,m3,m4,s1,s2,s3,s4;
            cin>>id>>m1>>s1>>m2>>s2>>m3>>s3>>m4>>s4;
            int t=(m1+m2+m3+m4)*60+s1+s2+s3+s4;
            P p(t,id);
            ra.push_back(p);
        }
        sort(ra.begin(),ra.end());
        cout<<ra[0].second<<endl;
        cout<<ra[1].second<<endl;
        cout<<ra[ra.size()-2].second<<endl;
    }
    return 0;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;


long long int n,cnt=0,ans=0,a[ohara],b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin>>n;
      rep(i,3*n)cin>>a[i];
      sort(a,a+3*n);
      reverse(a,a+3*n);
      ans=a[1];
      cnt=3;
      n--;
      while(1){
        ans+=a[cnt];
        cnt+=2;
        n--;
        if(n==0)break;
      }
      Cout(ans);
     

       
return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 666666;
int n,s;
ll x[N],cnt[N],res;
ll Abs(ll x){return x>0?x:-x;}
ll solve(int l, int r){
	if(s>x[r]){res+=Abs(s-x[l]);return x[l];}
	if(s<x[l]){res+=Abs(x[r]-s);return x[r];}
	if(l==r){res+=Abs(s-x[l]);return x[l];}
	if(cnt[l]>=cnt[r]){
		cnt[l]+=cnt[r];ll t=solve(l,r-1);res+=x[r]-t;return x[r];
	}
	else{
		cnt[r]+=cnt[l];ll t=solve(l+1,r);res+=t-x[l];return x[l];
	}
}
int main() {
	read(n);read(s);rep(i,1,n)scanf("%lld%lld",&x[i],&cnt[i]);
	solve(1,n);cout<<res;
	return 0;
}


Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
const long long MOD = 1e9+7;
bool judge(int a[],int b[],int n){
    rep(i,n) if(a[i]!=b[i]) return false;
    return true;
}
int main(){
    int n;
    cin >> n;
    int a[n];
    int p[n],q[n];
    rep(i,n) cin >> p[i];
    rep(i,n) cin >> q[i];
    rep(i,n) a[i]=i+1;
    long pp,qq;
    long cnt = 0;
    do{
        cnt++;
        if(judge(a,p,n)) pp = cnt;
        if(judge(a,q,n)) qq = cnt;
    }while(next_permutation(a,a+n));
    //cout << pp << " " << qq << endl;
    cout << abs(pp-qq) << endl;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::io::{stdin, Read, StdinLock};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BinaryHeap, VecDeque};
#[allow(unused_imports)]
use std::vec::Vec;

#[allow(dead_code)]
const INF: i32 = 1000_000_000;
#[allow(dead_code)]
const INFLL: i64 = 1000_000_000_000_000_000;
#[allow(dead_code)]
const EPS: f64 = 1.0e-10;
#[allow(dead_code)]
const MOD: i32 = 1000_000_007;
#[allow(dead_code)]
const MODLL: i64 = 1000_000_007;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner {cin: cin}
    }
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
                    .skip_while(|c| c.is_whitespace())
                    .take_while(|c| !c.is_whitespace())
                    .collect::<String>();
        token.parse::<T>().ok()
    }
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}



fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n: usize = sc.read();
    let mut a: Vec<usize> = vec![0; n];
    for i in 0..n {
        a[i] = sc.read();
    }
    a.sort();
    a.reverse();

    let mut alice = 0;
    let mut bob = 0;
    for i in 0..n {
        if i & 1 > 0 {
            bob += a[i];
        } else {
            alice += a[i];
        }
    }
    println!("{}", alice - bob);
}

Measured memory_bytes: 4476
def solve():
    N = int(input())
    P = list(map(int, input().split()))
    ret = 0
    for i in range(N-1):
        if P[i] == i+1:
            P[i],P[i+1] = P[i+1],P[i]
            ret += 1
        
    ret += int(P[-1] == N)
    print(ret)
    
solve()

Measured memory_bytes: 14008
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(A,B) << " " ;
    if(A+B <= N)cout << 0 << endl;
    else cout << A+B-N << endl;
}

Measured memory_bytes: 256
import static java.util.Arrays.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	void solve() {
		double xa1,  ya1,  xa2,  ya2,  xb1,  yb1,  xb2,  yb2;
		xa1=sc.nextDouble();ya1=sc.nextDouble();xa2=sc.nextDouble();ya2=sc.nextDouble();xb1=sc.nextDouble();yb1=sc.nextDouble();xb2=sc.nextDouble();yb2=sc.nextDouble();
		out.println(overlap(xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2) ? "YES":"NO");
	}

	boolean overlap(double xa1,double ya1,double xa2,double ya2,double xb1,double yb1,double xb2,double yb2) {
		if (xa1 > xb2 || xb1 > xa2) return false;
		if (yb2 < ya1 || ya2 < yb1) return false;
		return true;
	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}

Measured memory_bytes: 17036
#include <stdio.h>

int n,q;

int main(){
int s[100000],t[50000];
 int i,j,left, mid,right;
 int count =0;
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
  
  scanf("%d",&q);
  
  for(i=0;i<q;i++){
    scanf("%d",&t[i]);
  }

for(i=0;i<q;i++){
    left=0;
    right=n;
 while(left<right){
   mid=(left+right)/2;
   if(s[mid]==t[i]){
       count++;
       break;
   }  
   else if(t[i] < s[mid]) right=mid;
   else left=mid+1;
 }
}
  
  printf("%d\n",count);

  return 0;
}

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

template <typename T>
void insertion_sort(vector<T> & A, int g);

template <typename T>
void shell_sort(vector<T> & A);

int cnt = 0;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> A(n);
    for (auto & ai : A) cin >> ai;
    shell_sort(A);
    return 0;
}

template <typename T>
void insertion_sort(vector<T> & A, int g){
    for (int i = g; i != A.size(); ++i){
        auto v = A[i];
        auto j = i - g;
        while (j >= 0 and A[j] > v){
            A[j+g] = A[j];
            j -= g;
            ++cnt;
        }
        A[j+g] = v;
    }
}


template <typename T>
void shell_sort(vector<T> & A){
    cnt = 0;
    vector<int> G;
    for (int gi = 1; gi <= A.size(); gi = 3 * gi + 1) G.push_back(gi);
    reverse(G.begin(), G.end());
    for (auto gi: G) insertion_sort(A, gi);

    cout << G.size() << endl;
    cout << G[0];
    for (auto it=G.begin()+1; it!=G.end(); ++it) cout << ' ' << *it;
    cout << endl;
    cout << cnt << endl;
    for (auto ai : A) cout << ai << endl;
}

Measured memory_bytes: 6700
#include <bits/stdc++.h>
using namespace std;
using P = complex<double>;
const double PI = acos(-1.0);
namespace std{bool operator<(const P& a, const P& b){
  return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
}}
double inP(const P& p, const P& q){ return real(conj(p)*q); } //dot
double outP(const P& p, const P& q){ return imag(conj(p)*q); } //cross
int ccw(P a, P b, P c)
{
    b -= a;
    c -= a;
    if(outP(b,c) > 0) return +1; //counter clockwise
    if(outP(b,c) < 0) return -1; //clockwise
    if(inP(b,c) < 0) return +2; //c-a-b on line
    if(norm(b) < norm(c)) return -2; //a-b-c on line
    return 0;
}
vector<P> convex_hull(vector<P> &ps)
{
    int n = ps.size();
    int k = 0;
    sort(ps.begin(), ps.end());
    vector<P> qs(n*2);
    for(int i = 0; i < n; i++)
    {
        while(k > 1 && ccw(qs[k-2], qs[k-1], ps[i]) <= 0) k--;
        qs[k++] = ps[i];
    }
    for(int i = n-2, t = k; i >= 0; i--)
    {
        while(k > t && ccw(qs[k-2], qs[k-1], ps[i]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}

int main()
{
    int n;
    cin >> n;
    vector<P> ps;
    map<vector<int>, int> rem;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        ps.push_back(P(x, y));
        rem[{x, y}] = i;
    }
    vector<P> qs = convex_hull(ps);
    vector<double> ans(n);
    int m = qs.size();
    for(int i = 0; i < m; i++)
    {
        int x = qs[i].real();
        int y = qs[i].imag();
        double xprev = qs[(i-1+m)%m].real();
        double yprev = qs[(i-1+m)%m].imag();
        double xnext = real(qs[(i+1+m)%m]);
        double ynext = imag(qs[(i+1+m)%m]);
        double r1 = atan2(yprev-y, xprev-x);
        double r2 = atan2(ynext-y, xnext-x);
        double arg = r1 - r2;
        if(arg < 0) arg += 2*PI;
        double targ = PI - arg;
        int num = rem[{x, y}];
        ans[num] = targ / (2*PI);
    }
    for(int i = 0; i < n; i++)
    {
        printf("%.10f\n", ans[i]);
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;

int main()
{
  int n, m, k;
  cin >> n >> m >> k;
  vector<string> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];
  vector<vi> d(n, vi(m, -1));
  vector<ii> q;
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (v[i][j] == 'S') {
    q.push_back(make_pair(i, j));
    d[i][j] = 0;
    v[i][j] = '.';
  }
  for (int i = 0; i < q.size(); ++i) {
    int x = q[i].first;
    int y = q[i].second;
    if (x == 0 || x == n - 1 || y == 0 || y == m - 1) {
      if (d[x][y] <= k) {
        cout << 1 << endl;
        return 0;
      } else {
        continue;
      }
    }
    for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy) if (dx * dx + dy * dy == 1) {
      int xx = x + dx;
      int yy = y + dy;
      if (d[xx][yy] != -1) continue;
      if (v[xx][yy] != '.') continue;
      d[xx][yy] = d[x][y] + 1;
      q.push_back(make_pair(xx, yy));
    }
  }
  int result = 1000;
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
    if (d[i][j] > k || d[i][j] == -1) continue;
    int dist = min(min(i, j), min(n - 1 - i, m - 1 - j));
    int cur = 1 + dist / k + (dist % k ? 1 : 0);
    result = min(result, cur);
  }
  cout << result << endl;
    
  return 0;
}


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

int main()
{
    string s;
    long long k;
    int o = 0;
    cin>>s>>k;
    for(int i=0; i<s.size(); i++)
    {
        if(s[i] == '1') o++;
        else break;
    }
    if(k <= o) cout<<1<<endl;
    else cout<<s[o]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

void shortestPathSimple(const vector<vector<int> >& edges, int start, vector<int>& dist)
{
    int n = edges.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;
    queue<int> q;
    q.push(start);

    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(unsigned i=0; i<edges[v].size(); ++i){
            int u = edges[v][i];
            if(dist[u] == INT_MAX){
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}

template <class T>
class EdgeBase
{
public:
    int to;
    T cost;
    EdgeBase(){};
    EdgeBase(int to0, T cost0){to = to0; cost = cost0;}
};
typedef EdgeBase<int> Edge;

template<class T>
void shortestPath(const vector<vector<EdgeBase<T> > >& edges, int start, vector<T>& dist)
{
    const T INF = numeric_limits<T>::max();
    const T EPS = static_cast<T>(1.0e-10);

    dist.assign(edges.size(), INF);
    dist[start] = 0;
    priority_queue<pair<T,int>, vector<pair<T,int> >, greater<pair<T,int> > > q;
    q.push(make_pair(0, start));

    while(!q.empty()){
        pair<T, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first - EPS)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            EdgeBase<T> e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to] - EPS){
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> c(n+1), r(n+1);
    for(int i=1; i<=n; ++i)
        cin >> c[i] >> r[i];

    vector<vector<int> > edges1(n+1);
    for(int i=0; i<k; ++i){
        int a, b;
        cin >> a >> b;
        edges1[a].push_back(b);
        edges1[b].push_back(a);
    }

    vector<vector<Edge> > edges2(n+1);
    for(int i=1; i<=n; ++i){
        vector<int> dist;
        shortestPathSimple(edges1, i, dist);
        for(int j=1; j<=n; ++j){
            if(dist[j] <= r[i])
                edges2[i].push_back(Edge(j, c[i]));
        }
    }

    vector<int> dist;
    shortestPath(edges2, 1, dist);
    cout << dist[n] << endl;

    return 0;
}

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

int main(){
  int K,N;

  cin >> N >> K;

  vector<int> A(N);

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

  int cnt=1;

  N=N-K;

  cnt+=N/(K-1);

  if(N%(K-1) != 0){
    cnt+=1;
  }

  cout << cnt << endl;
}


Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2")  //Enable AVX*/

using namespace std;

using ll = long long;

#define mp make_pair

const int p = 998244353;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

/*const int N = 1000000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}*/


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

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

    map<ll, int> cnt;
    ll ans = 0;
    cnt[0] = 1;
    ll cur = 0;
    for (int i = 0; i<n; i++)
    {
        cur+=a[i];
        ans+=cnt[cur];
        cnt[cur]++;
    }
    cout<<ans;



}


Measured memory_bytes: 13568
/*https://atcoder.jp/contests/abc131/tasks/abc131_c*/

import java.util.*;
import java.awt.*;

class Main{
 
    private static Scanner sc = new Scanner(System.in);
    

    public static long gcd(long a,long b){
        if(b==0){
            return a;
        }else{
            return gcd(b,a%b);
        }
    }
    public static long lcm(long a,long b){
        return a/gcd(a,b)*b;
    }
    public static long divi(long l,long a,long b){
        long res = l;
        res -= l/a;
        res -= l/b;
        res += l/lcm(a,b);
        return res;
    }
    public static void main(String[] args) {
        String s = sc.next();
        String s1 = sc.next();
        String s2 = sc.next();
        String s3 = sc.next();

        long a = Long.parseLong(s); 
        long b = Long.parseLong(s1);
        long c = Long.parseLong(s2);
        long d = Long.parseLong(s3);
        //char[] code = s.toCharArray();
        long ans = divi(b,c,d)-divi(a-1,c,d);
        
        System.out.println(ans); }
}


Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int a;
	cin >> a;
	string s;
	cin >> s;
	if (a >= 3200) {
		cout << s << endl;
	} else {
		cout << "red" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 1e12

#define PB push_back
#define PF push_front
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vpi vector<pii>
#define vll vector<ll>
#define vpl vector<pll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pr_d(x) cout << fixed << setprecision(15) << x << endl
#define ud(c, x) distance(c.begin(), upper_bound(all(c), x))
#define ld(c, x) distance(c.begin(), lower_bound(all(c), x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep3(i, n) for (int i = (n - 1); i >= 0; --i)
#define rep4(i, a, b) for (int i = (a); i > (b); --i)
#define pb push_back
#define out(x) cout << x << "\n"
bool odd(int i) { return i % 2; }

#define all(v) v.begin(), v.end()
#define size(x) int(x.size())

int gcd(int a, int b) { return __gcd(a, b); }
int lcm(int a, int b) { return a * (b / gcd(a, b)); }
void Yes_No(bool f) {
  if (f)
    printf("Yes\n");
  else
    printf("No\n");
}

void deb_p(pii p) { printf("pair = %d %d\n", p.fi, p.se); }
void deb_i(int i) { printf("i = %d\n", i); }
void deb_v(vector<int> v) {
  printf("v = ");
  for (auto i : v) printf("%d ", i);
  printf("\n");
}
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
//-------------------ここから回答する-----------------------

void solve(void) {
  int n;
  cin >> n;
  out(800 * n - n / 15 * 200);
}
int main(void) { solve(); }

Measured memory_bytes: 3552
dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

def get_child(M, i, j, h, w, vis):
    child = []
    for k in range(4):
        x = i + dr[k]
        y = j + dc[k]
        if 0<= x< h and 0 <= y < w and (x, y) not in vis and M[x][y]!='#':
            child.append((x, y))

    return child

def bfs(M, i, j, h, w):
    vis = {(i, j): True}
    li = [(i, j, 0)]
    mx = 0
    while li:
        tp = li.pop(0)
        mx = max(mx, tp[2])
        ch = get_child(M, tp[0], tp[1], h, w, vis)
        vis.update( {}.fromkeys(ch, True) )
        
        ch = [(t[0], t[1], tp[2]+1) for t in ch]
        li.extend(ch)

    return mx
        
        
def solve(M, h, w):
    ans = 0
    for r in range(h):
        for c in range(w):
            if M[r][c]=='.':
                ## start bfs from this point
                depth = bfs(M, r, c, h, w)
                ans = max(ans, depth)
    print(ans)
h, w = map(int, input().split())
Mat = []
for row in range(h):
    Mat.append(input())


solve(Mat, h, w)


Measured memory_bytes: 3064
money = gets.split(' ')[0]
dlike = gets.split(' ').map(&:to_i)

def check_money(money, dlike)
    dlike.each{ |d|
        if money.include?(d.to_s)
            return true
        end
    }
    return false
end
pay = 0
while check_money(money, dlike) do
    pay = money.to_i + 1;
    money = pay.to_s
end
puts money

Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
#define MAX 2147483647

int n,N,q,a[1000000];

void init(int n){
  N = 1;
  while(true){
    if(N >= n) return;
    N *= 2;
  }
}

void add(int id,int x){
  id += N-1;
  a[id] += x;

  while(id>0){
    id=(id-1)/2;
    a[id] = a[id*2+1] + a[id*2+2];
  }
}

int getSum(int search_l,int search_r,int id,int tree_l,int tree_r){
  if(search_r < tree_l || tree_r < search_l) return 0;
  if(search_l <= tree_l && tree_r <= search_r) return a[id];
  else{
    int vl = getSum(search_l,search_r,id*2+1,tree_l,(tree_l+tree_r)/2);
    int vr = getSum(search_l,search_r,id*2+2,(tree_l+tree_r)/2+1,tree_r);
    return vl+vr;
  }
}

int main(){
  scanf("%d %d",&n,&q);
  init(n);
  for(int i=0;i<2*N-1;i++) a[i] = 0;

  int x,y,com;
  for(int i=0;i<q;i++){
    scanf("%d %d %d",&com,&x,&y);
    if(com == 0){
      add(x-1,y);
    }
    else{
      printf("%d\n",getSum(x-1,y-1,0,0,N-1));
    }
  }
  return 0;
}



Measured memory_bytes: 4244
#include <iostream>
#include <string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	string out;
	for(int i = 0; i < s.length(); i++){
		switch (s[i]){
			case '0':
				out += '0';
				break;
			case '1':
				out += '1';
				break;
			case 'B':
				if(!out.empty()) out.erase(out.end() - 1);
				break;
		}
	}
	cout << out << endl;
	return 0;
}


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

int main(){
int n,k;
cin >> n>>k;
vector<ll> h(n);
rep(i,n) cin >> h[i];

ll count =0;
sort(h.begin(), h.end());
for(int i=0;i<n-k;++i){

  count += h[i];
}
cout << count;
}

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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  string S;
  cin >> S;
  ll K;
  cin >> K;

  ll l = S.length();
  if (l == 1 || K == 1) {
    cout << S.at(0) << endl;
    return 0;
  }

  for (ll i = 0; i < K; ++i) {
    if (S.at(i) != '1') {
      cout << S.at(i) << endl;
      return 0;
    }
  }
  cout << 1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
const double pi = 3.141592653589793238462643383279;
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
 
//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-10;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


//ここから編集

bool dp[10010];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int N;
  cin >> N;
  vector<int> w(N);
  int sum = 0;
  REP(i,N) cin >> w[i], sum += w[i];
  
  int ans = INT_MAX;
  int t = 0;
  for(int i=0; i<N; i++){
    t += w[i];
    ans = min(ans, abs(t-(sum-t)));
  }
  cout << ans << endl;

  return 0;
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
ll LCM(int a, int b){
    return a*b/gcd(a,b);
}
int counterBit(int x){
    if(x==0)return 0;
    return counterBit(x>>1)+(x&1);
}
int main(void)
{
    int x,n;
    cin>>x>>n;
    vector<int> a(n);
    rep(i,0,n)cin>>a[i];
    sort(a.begin(),a.end());
    
    if(n==0){cout<<x<<endl; return 0;}
    int num1=INF,num2=INF;
    int plus=x;int minus=x;
    while(1){
        if(num1==INF){
            rep(i,0,n){
                if(plus==a[i]){num1=INF;break;}
                num1=plus;
            }
            plus++;
        }
        if(num2==INF){
            rep(i,0,n){
                if(minus==a[i]){num2=INF;break;}
                num2=minus;
            }
            minus--;
        }
        if(num1!=INF && num2 !=INF)break;
    }
    cout<<(abs(x-num1)<abs(x-num2)?num1:num2)<<endl;
    return 0;
}

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

int main () {
	
	int i=0, j=0, c=0, tam=0, tam2=0;
	string s="";

	cin >> s;

	

	i=0; j=s.length()-1;

	while (i<s.length() && j>=0 && i<j) {

		//cout << i << " " << j << endl;
		//cout << s[i] << " " << s[j] << endl;

		if (s[i] != s[j]) {

			if (s[i] == 'x' || s[j] == 'x') {
				c++;
				if (s[i] == 'x') i++;
				else j--;
			}
			else c = -1;

		}
		else {i++; j--;}

		if (c==-1) break;
	}

	printf("%d\n", c);

	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

#define MAX 100000

typedef struct{
  int p;
  int l_child;
  int r_sibling;
} node;

  int depth[MAX];
  node T[MAX];

void getDepth(int,int);

int main(){
  int c,i,j,k,n,r,id,prec;
    
  scanf("%d",&n);

  for(i=0;i<n;i++) T[i].p=T[i].l_child=T[i].r_sibling=-1;

  for(i=0;i<n;i++){
    scanf("%d%d",&id,&k);
    for(j=0;j<k;j++){
      scanf("%d",&c);
      if(j==0) T[id].l_child=c;
      else T[prec].r_sibling=c;
      prec=c;
      T[c].p=id;
    }
  }

  for(i=0;i<n;i++){
    if(T[i].p==-1)r=i;
  }

  getDepth(r,0);

  for(i=0;i<n;i++){
    printf("node %d: parent = %d, depth = %d, ",i,T[i].p,depth[i]);
    if(T[i].p==-1){
      printf("root, [");
      for( j=T[i].l_child; j!=-1; j=T[j].r_sibling){
	printf("%d",j);
	if(T[j].r_sibling!=-1) printf(", ");
      }
      printf("]\n");
    }

    else if(T[i].l_child!=-1){
      printf("internal node, [");
      for( j=T[i].l_child; j!=-1; j=T[j].r_sibling){
	printf("%d",j);
	if(T[j].r_sibling!=-1) printf(", ");
      }
      printf("]\n");
    }

    else printf("leaf, []\n");
  }

  return 0;
}

void getDepth(int u,int p){
  depth[u]=p;
  if(T[u].r_sibling!=-1) getDepth(T[u].r_sibling,p);
  if(T[u].l_child!=-1) getDepth(T[u].l_child,p+1);
}



Measured memory_bytes: 6380
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const int MAX_V = 100005;
const ll INF = 1000000000000000000;

vector<pll> to_yen[MAX_V];
vector<pll> to_snuke[MAX_V];


int main()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    --s, --t;

    rep(i, 0, m)
    {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        --u, --v;

        to_yen[u].emplace_back(v, a);
        to_yen[v].emplace_back(u, a);
        to_snuke[u].emplace_back(v, b);
        to_snuke[v].emplace_back(u, b);
    }

    vector<ll> cost_yen(n, INF);

    // dijkstra for yen
    {
        priority_queue<pll, vector<pll>, greater<pll>> que;
        que.push(make_pair(0, s));

        while (que.size() > 0)
        {
            ll cost, now;
            tie(cost, now) = que.top();
            que.pop();

            if (cost_yen[now] != INF) continue;
            cost_yen[now] = cost;
            
            for (auto next: to_yen[now])
                que.push(make_pair(next.second + cost, next.first));
        }
    }

    vector<ll> cost_snuke(n, INF);

    // dijkstra for snuke
    {
        priority_queue<pll, vector<pll>, greater<pll>> que;
        que.push(make_pair(0, t));

        while (que.size() > 0)
        {
            ll cost, now;
            tie(cost, now) = que.top();
            que.pop();

            if (cost_snuke[now] != INF) continue;
            cost_snuke[now] = cost;
            
            for (auto next: to_snuke[now])
                que.push(make_pair(next.second + cost, next.first));
        }
    }

    priority_queue<pll, vector<pll>, greater<pll>> cand;
    rep(i, 0, n)
        // cout << cost_yen[i] << ' ' << cost_snuke[i] << endl;
        cand.push(
            make_pair(
                cost_yen[i] + cost_snuke[i], i));

    vector<ll> ans(n);
    int i = 0;
    while (i < n)
    {
        ll cost, city;
        tie(cost, city) = cand.top();
        cand.pop();

        while (i <= city)
        {
            ans[i] = cost;
            ++i;
        }
    }

    rep(i, 0, n)
        printf("%lld\n", 1000000000000000 - ans[i]);
    //     // psrintf("%lld\n", ans[i]);

    return 0;
}

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

int main(int argc, char const *argv[]) {
    long long n, a, b;
    cin >> n >> a >> b;

    long long x = n / (a+b);
    long long y = (n % (a+b) > a)?a:(n % (a+b));
    long long ans = x * a + y;

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


Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<iomanip>

using namespace std;
int main(void) {
	
	int n;
	int h[100];
	int i;
	
	int a=1;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> h[i];
	}
	int max = h[0];

	for (i = 1; i < n; i++) {
		if (max <= h[i]) {
			max = h[i];
			a++;
		}
			
	}

	cout << a;
	return 0;
}

Measured memory_bytes: 256
H, W, K = gets.split(' ').map(&:to_i)
MOD = 10 ** 9 + 7

dp = Array.new(H + 1){Array.new(W + 2, 0)}
dp[0][1] = 1
lines = []

[0, 1].repeated_permutation(W - 1) do |line|
  valid = true
  0.upto(W - 2) do |i|
    valid = false if line[i] == 1 && line[i + 1] == 1
  end
  lines.push([0] + line + [0]) if valid
end

1.upto(H) do |h|
  lines.each do |line|
    1.upto(W) do |j|
      if line[j - 1] == 1
        dp[h][j] += dp[h - 1][j - 1]
      elsif line[j] == 1
        dp[h][j] += dp[h - 1][j + 1]
      else
        dp[h][j] += dp[h - 1][j]
      end
      dp[h][j] %= MOD
    end
  end
end

puts dp[H][K]

Measured memory_bytes: 1788
program test
	implicit none
    integer::a,b,N,ans,i,x,y
    read*,N,a,b
    ans=0
    do i=1,N
    	x=i
        y=0
    	do while(x>0)
        	y=mod(x,10)+y
        	x=x/10
        end do
        if(y>=a .and. b>=y)then
        	ans=ans+i
        end if
    end do
    print*,ans
end program test

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inlien inline
#define retrun return
#define cpnst const
typedef long double ld;
int a[111],n,c;
ld dp[555][555];
inline int min(int x,int y)
{return(x<y)?x:y;}
inline int max(int x,int y)
{return(x>y)?x:y;}
int main()
{
	scanf("%d%d",&n,&c);
	register int i,ii,S;
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	ld fac=0,pwd=1;
	for(i=1;i<n;i++)pwd*=c;
	std::sort(a+1,a+n+1);
	ld ans=0;
	do
	{
		memset(dp,0,sizeof(dp)),
		fac++,dp[a[n]*n][0]=1;
		for(i=1;i<=n*c;i++)
		{
			int v=i%n;
			if(!v)continue;
			for(ii=i;ii<=n*c;ii++)
				for(S=0;S<(1<<(n-1));S++)
				{
					if(S&(1<<(v-1)))continue;
					int to=min(n*c,max(ii,i+n*a[v]));
					dp[to][S|(1<<(v-1))]+=dp[ii][S];
				}
		}ans+=dp[n*c][(1<<(n-1))-1]/pwd;
	}while(std::next_permutation(a+1,a+n));
	printf("%.15Lf\n",ans/fac);
}
/*
Giving the world a better yourself is giving yourself a better world. 
*/

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
int main() {
  string a,b;
  cin >> a >> b;
  int num = stoi(a + b);
  int count = 0;
  for(int i = 1; i <= num; i++){
    if(num % i == 0) count++;
  }
  if(count % 2 !=0){
    cout << "Yes" << endl;
  }
  else cout << "No" << endl;

    return 0;
}

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

int main()
{
  long long a,b,c;
  scanf("%lld%lld%lld",&a,&b,&c);
  printf("%lld\n",min((a%2)*b*c,min((b%2)*a*c,(c%2)*a*b)));
  return 0;
}


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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

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

  set<long> p;

  for (long i = 0; i < n; i++) {
    long tmp;
    cin >> tmp;
    p.insert(tmp);
  }

  long i = 0;
  while (true) {
    if (p.count(x - i) == 0) {
      cout << x - i << endl;
      return 0;
    }
    if (p.count(x + i) == 0) {
      cout << x + i << endl;
      return 0;
    }

    i++;
  }
}


Measured memory_bytes: 3568
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
すべてのiに対して
「a_iが最小値となる区間はいくつあるか?」を考える.
a_iより左側でa_iより小さいもののうち最もa_iに近いものをa_l
a_iより右側でa_iより小さいもののうち最もa_iに近いものをa_rとする.
最小値がa_iとなる区間は左側がl+1,l+2,...,i
                    　右側がi,i+1,...,r-1となる区間
⇒(i-l+1)x(r-i+1)個の区間でa_iが最小値をとる
すべてのiに対してこの個数を求める.
"""

n = I()
a = LI()
lst = [0]*(n+1)

for i in range(n):
    lst[a[i]] = i

l = [0]*n #各iに対して,a_iより左側でa_iより小さいもののうち最もa_iに近いもののindex
r = [0]*n #各iに対して,a_iより右側でa_iより小さいもののうち最もa_iに近いもののindex
ans = 0

#大きい値から見ていく
for x in range(1,n+1)[::-1]:
    #調べている数 := x
    #xの位置 := i
    i = lst[x]

    #iが右端でないかつ,iの右隣が自分(x)より大きい場合
    if i+1 < n and a[i+1] > x:
        #r[i+1] := iより右側でxより小さいもののうち最もiに近いもののindex
        #  ⇒ i <= j < r[i+1] に関してa[j]はx以上である.
        R = r[i+1]
    else:
        #右隣がいないまたは右隣が自分(x)より小さい場合
        R = i
    
    #iが左端でないかつ,iの左隣が自分(x)より大きい場合
    if i-1 >= 0 and a[i-1] > x:
        #l[i-1] := iより左側でxより小さいもののうち最もiに近いもののindex
        #  ⇒ l[i-1] < j <= i に関してa[j]はx以上である.
        L = l[i-1]
    else:
        #左隣がいないまたは左隣が自分(x)より小さい場合
        L = i
    
    # L < j < Rに関してa[j]はx以上であることが分かっている.
    # ⇒Rの位置から見て左側の区間はLまで
    # ⇒Lの位置から見て右側の区間はRまで
    l[R] = L
    r[L] = R
    ans += (i-L+1)*(R-i+1)*x
print(ans)
    

Measured memory_bytes: 71888
#include<stdio.h>
#include<ctype.h>
#include<math.h>
main(){
  double a=0;
  double b=0;
  double c=0;
  double d=0;
  double i=0;
  double k=0;
  double l=0;
  double j=0;
  scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
  if(a<c){
    i=c-a;
  }
  else if(a>c){
    i=a-c;
  }
  if(b<d){
    j=d-b;
  }
  else if(b>d){
    j=b-d;
  }
  k=(i*i)+(j*j);
  if(k!=0&&i==0){
    l=j;
  }
  else if(k!=0&&j==0){
    l=i;
  }
  else if(k!=0){
    l=sqrt(k);
  }
  else{
    l=0;
  }
  printf("%lf\n",l);
  return 0;
}

Measured memory_bytes: 656