akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
	int N, W;
	cin >> N >> W;
	int M = N * 1000;
	vector<ll> dp(M + 1, 1e15);
	dp[0] = 0;
	for (int i = 0; i < N; i++) {
		int w, v;
		cin >> w >> v;
		for (int j = M; j >= v; j--) {
			dp[j] = min(dp[j], dp[j - v] + w);
		}
	}
	int res = 0;
	for (int i = 0; i <= M; i++) {
		if (dp[i] <= W) {
			res = i;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
#define N 305
#define mod 1000000007
int n,m,f[N][N][N],ans;vector<pii> a[N];
void upd(int &x,int y){x+=y;x-=x>=mod?mod:0;}
bool check(int i,int j,int k,int nw){
	for (auto x:a[nw]){
		int tmp=(i>=x.fi)+(j>=x.fi)+(k>=x.fi);
		if (tmp!=x.se) return 0;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	rep (i,1,m){
		int l,r,x;scanf("%d%d%d",&l,&r,&x);
		a[r].push_back(pii(l,x));
	}
	f[0][0][0]=1;
	rep (i,0,n) rep (j,0,n) rep (k,0,n) if (f[i][j][k]){
		int nw=max(i,max(j,k));
		if (!check(i,j,k,nw)){f[i][j][k]=0;continue;}
		if (nw==n) upd(ans,f[i][j][k]);
		nw++;
		upd(f[nw][j][k],f[i][j][k]);
		upd(f[i][nw][k],f[i][j][k]);
		upd(f[i][j][nw],f[i][j][k]);
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 110848
#include<iostream>
#include<string>

using namespace std;

int main(){
	string s;
	cin >> s;
	int counter=0;
	if(s[0]=='1') ++counter;
	if(s[1]=='1') ++counter;
	if(s[2]=='1') ++counter;
	cout << counter << endl;
	return 0;
}


Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <regex>

using namespace std;

//conversion
//------------------------------------------
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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//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 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,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1000000007;

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
	bool ret = true;
	if (x < 2) {
		ret = false;
	}
	for (LL i = 2; i <= sqrt(x); i++) {
		if (x%i == 0) {
			ret = false;
		}
	}
	return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

int main(int argc, char const* argv[])
{
	string s;
	cin >> s;
	regex r(".*(\\d)\\1{2}.*");
	if (regex_match(s.begin(),s.end(),r)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include <iomanip>
#include<map>
#include <random>
#include<type_traits>
#include<stack>
#include <sstream> 
#include <limits>
#include <numeric>
#include<string.h>
#include<set>
using namespace std;
#define ll long long int
#define all(v) begin(v), end(v)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
//typedef vector<int> V;
//typedef vector<V> VV;
//typedef vector<VV> VVV;
using namespace std;

int main() {
	string s;
	int c = 0;
	cin >> s;
	for (int i = 1; i < 4; i++) {
		if (s[i] == s[i - 1])c++;
	}
	if(c==0)cout<<"Good" <<endl;
	else cout << "Bad" << endl;
	return 0;
}




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

int main() {
  int N;
  cin >> N;
  vector<int> W(N);
  rep(i, N) cin >> W[i];
  int ans = 100000000;
  rep(i, N) {
    int a=0, b=0;
    rep(j, i) {
      a += W[j];
    }
    for (int j = i; j < N; j++) {
      b += W[j];
    }
    ans = min(ans, abs(a-b));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        q: usize,
        ab: [(usize, usize); q],
    }
    for &(mut ai, mut bi) in &ab {
        if ai > bi {
            std::mem::swap(&mut ai, &mut bi);
        }
        if ai == bi {
            println!("{}", ai + bi - 2);
        } else if ai + 1 == bi {
            println!("{}", ai + bi - 3);
        } else {
            let mut c = ((ai as f64).sqrt() * (bi as f64).sqrt()) as usize;
            if c * c == ai * bi {
                c -= 1;
            }

            if c * (c + 1) >= ai * bi {
                println!("{}", 2 * c - 2);
            } else {
                println!("{}", 2 * c - 1);
            }
        }
    }
}


Measured memory_bytes: 2156
S = input()
N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = 3*a+b, 3*b+c, 3*c+d, 3*d
  elif x == "A":
    a += b
  elif x == "B":
    b += c
  elif x == "C":
    c += d
  a %= mod; b %= mod; c %= mod; d %= mod
print(a)

Measured memory_bytes: 3188
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <fstream>
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <numeric>
#include <sstream>
#include <list>
#include <map>

#define rep(i,p,n) for(int i=(int)p;i<(int)n;i++)
#define repp(i,p,n) for(int i=(int)p;i>=(int)n;i--)
#define Sort(x) sort(x.begin(),x.end());
#define ll long long 
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi <vector<vector<vector<int>>> 
#define vc vector<char> 
#define vvc vector<vector<char>>
#define vvvc vector<vector<vector<char>>> 

using namespace std;

int main() {
	int n;
	cin >> n;
	vi v(n);
	rep(i, 0, n)scanf("%d", &v[i]);

	Sort(v);
	cout << v[v.size() - 1] - v[0] << endl;
	


	return 0;
}


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

int main() {
  int n, m;
  cin >> n >> m;
  
  int i, j;
  vector<vector<int>> a(n, vector<int>(2)), c(m, vector<int>(2));
  for(i = 0; i < n; i++){
    cin >> a.at(i).at(0) >> a.at(i).at(1);
  }
  for(i = 0; i < m; i++){
    cin >> c.at(i).at(0) >> c.at(i).at(1);
  }
  
  int keep, d = 1000000000;
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      if(abs(a.at(i).at(0) - c.at(j).at(0)) + abs(a.at(i).at(1) - c.at(j).at(1)) < d){
        d = abs(a.at(i).at(0) - c.at(j).at(0)) + abs(a.at(i).at(1) - c.at(j).at(1));
        keep = j;
      }
    }
  cout << keep + 1 << endl;
  keep = -1;
  d = 1000000000;
  }
}

Measured memory_bytes: 256
sets = readlines
sets.each{|line|
    h,w = line.split.map(&:to_i)
    
    break if (h == 0) && (w == 0)
    
    h.times{|n|
        w.times{|m|
            if (n == 0) || (n == (h-1))
                print '#' 
            elsif
                if (m == 0) || (m == (w-1))
                    print '#'
                else
                    print '.'
                end
            end
        }
        puts #new line
    }
    puts #new line
}


Measured memory_bytes: 6884
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  int n, m;
  cin >> n >> m;
  vector<int> x(n);
  rep(i, n) cin >> x[i];

  map<int, int> cnt;
  rep(i, n) cnt[x[i]]++;
  map<int, int> res;
  int ans = 0;
  rep(i, n) {
    ans += cnt[x[i]] / 2;
    res[x[i] % m] += cnt[x[i]] % 2;
    cnt[x[i]] = 0;
  }
  rep(i, n) cnt[x[i] % m]++;
  ans += res[0] / 2;
  FOR(i, 1, m / 2 + 1) {
    if (i == m - i) {
      ans += res[i] / 2;
      break;
    }
    int now = min(cnt[i], cnt[m - i]);
    ans += now;
    if (res[i] < now) {
      ans -= (now - res[i] + 1) / 2;
    }
    if (res[m - i] < now) {
      ans -= (now - res[m - i] + 1) / 2;
    }
  }
  cout << ans << endl;
  



  
  return 0;
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
//using Graph = vector<vector<int>>;
using P =pair<int,int>;
//int dy[4] = {-1,0,1,0};
//int dx[4] = {0,-1,0,1};

/*
bool dfs(vector<vector<P>> &data, vector<long long> &d, queue<int> &temp)
{
    while(!temp.empty())
    {
    int i= temp.front();
    temp.pop();
    for(int j=0;j<data[i].size();j++)
    {
        if(d[data[i][j].first] == LONG_LONG_MAX)
        {
            d[data[i][j].first] = d[i] + data[i][j].second;
            temp.push(data[i][j].first);
            
        }
        else if(d[data[i][j].first] != d[i] + data[i][j].second)
        {
            return false;
            break;
        }
    }
    }
    return true;
}


int main()
{
    int N,M;
    cin >>N >> M;
    
    vector<vector<P>> data(N);
    for(int i=0;i<M;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        
        data[a-1].push_back(make_pair(b-1,c));
        data[b-1].push_back(make_pair(a-1,-c));
    }
    
    vector<long long> d(N,LONG_LONG_MAX);
    bool nouse = false;
    if(data[0].size() != 0) d[0] = 0;
    else nouse = true;
    
    bool ok = true;
    
    int k=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<data[i].size();j++)
        {
            if(nouse)
            {
                d[i] = 0;
                nouse = false;
                k=i;
                break;
            }
        }
    }
    
    /*
            }
            if(d[data[i][j].first] == LONG_LONG_MAX)
            {
                d[data[i][j].first] = d[i] + data[i][j].second;
            }
            else if(d[data[i][j].first] != d[i] + data[i][j].second)
            {
                ok = false;
                break;
            }
        }
        if(!ok)
        {
            break;
        }
 
    
    
    queue<int> temp;
    temp.push(k);
    if(dfs(data,d,temp)) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}
*/





int main()
{
    string s;
    long long k;
    cin >> s;
    cin >> k;
    int t = (int)s.size();
    vector<int> data(t);
    
    for(int i = 0;i<t-1;i++)
    {
        data[i] = (123 - s[i])%26;
    }
    for(int i = 0;i<t-1;i++)
    {
        if(data[i] < k+1)
        {
            s[i] = 'a';
            k -= data[i];
        }
    }
    
    k %= 26;
    
    
    
    if(s[t-1] + k > 122)
    {
        s[t-1] -= 26-k;
    }
    else
    {
        s[t-1] += k;
    }
    
    cout << s << endl;
    
    return 0;
}




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

int main() {
  int N; cin >> N;
  vector<int> a(N); for (int i = 0; i < N; i++) cin >> a[i];
  sort(a.begin(), a.end(), greater<int>());
  int ali = 0, bob = 0;
  for (int i = 0; i < N; i+=2) {
    ali += a[i];
    if (i < N-1) bob += a[i+1];
  }
  cout << ali - bob << endl;
}

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

int main() {
  int A,B,C,K;
  cin >> A >> B >> C >> K;
  if(K <= A) cout << K << endl;
  else if (A < K && K < (A + B)) cout << A << endl;
  else if (B <= K) cout << 2*A - K + B << endl;
}


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

int main() {
  int a , b , c , d;
  cin >> a >> b >> c >> d ;
  cout <<  ((abs(c - a)<=d ) || (abs(c-b)<=d && abs(b-a)<=d) ?
         "Yes" : "No" )
    << endl;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
int C[101010];
const ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=1;
	C[0]=3;
	FOR(i,N) {
		cin>>x;
		ret=ret*C[x]%mo;
		C[x]--;
		C[x+1]++;
		
	}
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main(){
  ll n;
  cin>>n;
  n*=3;
  vector<ll> A(n);
  for(int i=0;i<n;i++)cin>>A[i];
  sort(A.begin(),A.end(),greater<ll>());
  
  ll res=0;
  int l=0,r = n-1;
  while(l<r){
    res+=A[l+1];
    l+=2;
    r--;
  }
  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 2560
S = input()

g_cnt, p_cnt = 0, 0
ans = 0
for s in S:
    if p_cnt < g_cnt:
        if s == "g":
            p_cnt += 1
            ans += 1
        elif s == "p":
            p_cnt += 1
    else:
        if s == "g":
            g_cnt += 1
        elif s == "p":
            g_cnt += 1
            ans -= 1
print(ans)

Measured memory_bytes: 9228
# coding: utf-8
class Case01

  def initialize
  end

  def show
    p self.instance_variables
        .map{ |sym| [sym, self.instance_variable_get(sym)] }
        .to_h
  end
  
  # 実行する
  def execute
    read
    solve
    output
  end

  # 読込
  def read
    @x, @a, @b = gets.chomp.split.map(&:to_i)
  end

  # 回答
  def solve
    @delicious = (@b - @a <= 0)
    @safe = (@b - @a <= @x)
  end
  
  # 出力
  def output
    if @delicious then
      puts 'delicious'
    elsif @safe then
      puts 'safe'
    else
      puts 'dangerous'
    end
  end

end

Case01.new.execute if $0 == __FILE__



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

#define MP make_pair
#define PB push_back
#define ALL(x)  (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define RANGEBOX(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define RANGE(x, l, r) ((l) <= (x) && (x) <= (r))
#define rep(i, N)  for (int i = 0; i < (int)(N); i++)
#define rrep(i, N) for (int i = N - 1; i >= 0; i--)
#define REP(i, init, N)  for (int i = (init); i < (int)(N); i++)
#define RREP(i, N, last) for (int i = (init - 1); i >= last; i--)
#define PB push_back

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVi;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int    INF  = 0x3f3f3f3f;
const LL     INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;

int main(){
	ios::sync_with_stdio(false);
    int a,b,h;
    cin>>a>>b>>h;
    cout<<(a+b)*h/2<<endl;


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MOD 1000000007
//N==4 M==3
int main()
{
	int i, n, m;
	scanf("%d%d", &n, &m);//長さ、1の個数

	long a[110000], ans = 0;
	for (i = 1; i < m; i++)
	{
		a[i] = 0;
	}
	a[0] = a[m] = 1; //a[0]=1, a[1]=0, a[2]=0, a[3]=1

	for (i = m; i <= n; i++)
	{
		ans = (ans * 2 + a[i]) % MOD;//ans = a[3]==1⇒ans = 1 * 2 + a[4] == 3⇐最終的なans
		a[i + 1] = (a[i] * 2 - a[i - m] + MOD) % MOD;// a[4] = a[3] * 2 - a[3 - 3] ==1
	}

	printf("%ld\n", ans);
}





Measured memory_bytes: 2580
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>

using namespace std;
int main(void){
    int D;
    cin>>D;
    if(D==22){cout<<"Christmas Eve Eve Eve";}
    if(D==23){cout<<"Christmas Eve Eve";}
    if(D==24){cout<<"Christmas Eve";}
    if(D==25){cout<<"Christmas";}
    return 0;
}


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

int main(){
  int n;
  cin>>n;
  long long a,b,c,d;
  int count=0;
  vector<long long> st;
  lp(i,n){
    cin>>d>>b>>c;
    a=b*10000+c*100000000+d;
    int check=0;
    for(int j=0;j<st.size();j++){
      if(st[j]==a){
	check=1;
	break;
      }
    }
    if(check==1) count++;
    if(check==0){
      st.push_back(a);
      a=b*10000+d*100000000+c;
      st.push_back(a);
      a=c*10000+b*100000000+d;
      st.push_back(a);
      a=c*10000+d*100000000+b;
      st.push_back(a);
      a=d*10000+c*100000000+b;
      st.push_back(a);
      a=d*10000+b*100000000+c;
      st.push_back(a);
    }
  }
  cout<<count<<endl;
  return 0;
}



Measured memory_bytes: 3248
N = int(input())

a = [int(i) for i in input().split()]
v=0
x=[]
j=0
for i in range(N):
  if a[i] %2 ==0:
    x.append(a[i])
    j +=1

    
for i in range(j):
  if x[i] %3 ==0 or x[i] %5 ==0:
    v += 1

if v == j:
  print("APPROVED")
else:
  print("DENIED")





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

double eps = 1e-10;

class Point {
public:
	double x, y;
	
	Point(double x = 0, double y = 0) : x(x), y(y) {}
	
	Point operator + (const Point& p) {
		return Point(x + p.x, y + p.y);
	}
	Point operator - (const Point& p) {
		return Point(x - p.x, y - p.y);
	}
	Point operator * (const double& a) {
		return Point(x * a, y * a);
	}
	Point operator / (const double& a) {
		return Point(x / a, y / a);
	}
	
	bool operator < (const Point& p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator == (const Point& p) const {
		return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
	}
	
	double abs() {
		return sqrt(norm());
	}
	double norm() {
		return x * x + y * y;
	}
	
};

class Circle {
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0) : c(c), r(r) {}
};

int main() {
	int n;
	cin >> n;
	double x1, y1, r1, x2, y2, r2;
	for(int i = 0; i < n; ++i){
		cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		Circle c1 = Circle(Point(x1, y1), r1);
		Circle c2 = Circle(Point(x2, y2), r2);
		double minr = min(c1.r, c2.r);
		double maxr = max(c1.r, c2.r);
		double dr = maxr - minr;
		
		if(pow(c2.c.x - c1.c.x, 2.0) + pow(c2.c.y - c1.c.y, 2.0) < pow(dr, 2.0)){
			if(c1.r > c2.r)
				cout << "2" << endl;
			else
				cout << "-2" << endl;
		}
		else if(pow(c2.c.x - c1.c.x, 2.0) + pow(c2.c.y - c1.c.y, 2.0) <= pow(c1.r + c2.r, 2.0)){
			cout << "1" << endl;
		}
		else{
			cout << "0" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1236
/* 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);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String ans ="Yay!";
		if(a>8||b>8){
			ans = ":(";
		}System.out.print(ans);
		
	}
}

Measured memory_bytes: 22612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

#define lpsbd(i, s, b, d) for(size_t i = (s); i < (b); i+=(d))
#define lpsb(i, s, b) for(size_t i = (s); i < (b); i++)
#define lpn(i, n) for(size_t i = 0; i < (n); i++)
#define fa(i, x) for(auto &i: x)
#define vcd(t, n, d) vector<t>(n, d)
#define vc(t, n) vector<t>(n)
#define all(x) (x).begin(), (x).end()

using namespace std;

using ll = long long;

ll s[51], p[51];

ll pinn(int n, ll x)
{
    if (!x) return 0;
    if (!n) return x;
    if (x >= s[n] - 1) return p[n];
    x--;
    if (x <= s[n-1]) return pinn(n-1, x);
    x-=s[n-1];
    if (x == 1) return 1 + p[n-1];
    x--;
    if (x <= s[n-1]) return pinn(n-1, x) + 1 + p[n-1];
    return p[n];
}

int main(void)
{
    int N;
    ll X;
    cin >> N >> X;
    s[0] = p[0] = 1;
    lpn(i, 50)
    {
        s[i+1] = s[i] * 2 + 3;
        p[i+1] = p[i] * 2 + 1;
    }
    cout << pinn(N, X) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <string>
using namespace std;
#define N 100009
#define ll long long

int main(){
    int n,k;
    cin>>n>>k;
    int data[n];
    int count=0;
    for (int i=0; i<n; i++){
        cin>>data[i];
        if (data[i]>=k) count++;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 768
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <random>
#include <cmath>
#include <chrono>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
using LL = long long;
#define eps 1e-8
#define fi first
#define se second
#define eb emplace_back
#define close std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define CASET int ___T; scanf("%d", &___T); for(int __CS=1;__CS<=___T;__CS++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
mt19937 dlsrand(random_device{}());
mt19937 mrand(std::chrono::system_clock::now().time_since_epoch().count()); 
int rnd(int x) { return mrand() % x;}
LL bin(LL x, LL n, LL MOD) {LL ret = MOD != 1;for (x %= MOD; n; n >>= 1, x = x * x % MOD)if (n & 1) ret = ret * x % MOD;return ret;}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
const double PI = acos(-1.0);
constexpr int maxn = 1e6+10;
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9+7;
int dp[maxn],a[maxn];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 2; i <= n; i++){
        if(i >= 3){
            dp[i] = min(dp[i-2]+abs(a[i]-a[i-2]),abs(a[i]-a[i-1])+dp[i-1]);
        }else {
            dp[i] = abs(a[i]-a[i-1])+dp[i];
        }
    }
    cout << dp[n] <<endl;
}

Measured memory_bytes: 4736
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1000000007;
const int MAX_V = 201;
ll dp[2][4];
int now = 0;
int t[3];
ll p2[32];
void Powersoftwo() {
	int n;
	cin >> n;
	ll a[200010];
	for (size_t i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	p2[0] = 2;
	for (size_t i = 1; i < 32; i++)
	{
		p2[i] = p2[i - 1] * 2;
	}
	ll res = 0;

	for (int i = 31; i >= 0; i--)
	{
		for (int k= 0,j = n - 1; k < n; k++)
		{
			if (a[k] != -1) {
				while (k < j && (a[j] == -1 || a[k] + a[j] > p2[i])) j--;
				if (k < j && a[j] != -1 && a[k] + a[j] == p2[i]) {
					res++;
					a[k] = a[j] = -1;
				}
				
			}
		}
	}
	cout << res << endl;
}
int main() {
	Powersoftwo();
	return 0;
}



Measured memory_bytes: 1792
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())

    mod = N % 1000
    if mod == 0:
        return 0
    else:
        return 1000 - mod


def main():
    print(solve())


if __name__ == "__main__":
    main()


Measured memory_bytes: 9148
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	cin >> N;
	auto s = to_string(N);
	if (equal(s.begin(), s.end(), s.rbegin())) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
long long fac(ll a){
    long long ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
int main(){
    ll n;cin >> n;
    ll a = (n+1)/2;
    cout << a << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define fo(i,n) for(int i=0;i<n;i++)
#define rfo(i,n) for(int i=n-1;i>=0;i--)
#define Fo(i,q,n) for(int i=q;i<n;i++)
#define rFo(i,q,n) for(int i=n-1;i>=q;i--)
#define fO(i,n,k) for(int i=0;i<n;i+=k)
#define FO(i,q,n,k) for(int i=q;i<n;i+=k)
#define zero(a,n) memset(a,0,sizeof(a[0])*n)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl "\n"
#define Endl "\n"
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
using namespace std;
const int MOD=1000000007;
void print(){cout <<endl;}
template <typename T, typename... Types> 
void print(T var1, Types... var2){cout << var1 << " " ;print(var2...) ;}
//ceil of a/b
template <typename T>
T fceil(T a,T b){return (T)(a+b-1)/b;}
//const int N=2e5;
//int arr[N+1];

 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t=1;
	//cin>>t;
	while(t--){
		string n;
		cin>>n;
		int sum=0;
		for(int i=0;i<(int)n.size();i++){
			sum+= n[i]-'0';	
		}
		if(sum%9==0){
			cout<<"Yes"<<endl;	
		}
		else{cout<<"No"<<endl;}			
	}
	return 0;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 1; i < (int)(n); i++)
using ll = long long;
using pll = pair<ll,ll>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vstr = vector<string>;
const ll MOD=1000000007;
vll dx{0,1,0,-1};
vll dy{1,0,-1,0};

int main()
{
    int N;
    cin>>N;
    int res=0;
    for(int c=1;c<N;c++){
        int ab = N - c;
        for(int a=1;a*a<=ab;a++)
        {
            if(ab%a==0){
                res++; 
                if(ab/a!=a){
                    res++;
                }
            }
        }
    }
    cout<<res;
    return 0;
}

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

def main():
    N,M=map(int,input().split())
    a,b=[0]*M,[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
    a_argsorted=np.argsort(a)
    a_max=0
    b_min=INF
    ans=1
    for i in a_argsorted:
        a_max=a[i]
        b_min=min(b_min,b[i])
        if a_max>=b_min:
            ans+=1
            b_min=b[i]
    print(ans)

if __name__ == '__main__':
    main()


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


using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 1010;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}



// Main Code
char ans[100][100];

int main()
{
	int a, b;
	cin>>a>>b;
	a--;b--;
	for(int i=0; i<50; i+= 2)
	{
		for(int j=0; j <50; j+=2)
		{
			if(a <= 0)
				{i = 50; j = 50;break;}
			ans[i][j] = '.';
			a--;
		}
	}
	for(int i=99; i>=50; i-= 2)
	{
		for(int j=0; j <50; j+=2)
		{
			if(b <= 0)
				{i = 50; j = 50;break;}
			ans[i][j] = '#';
			b--;
			
		}
	}
	cout<<100<<" "<<100<<endl;
	rep(i, 0, 50){
		rep(j, 0, 100){
			if(ans[i][j] == '.')
				cout<<ans[i][j];
			else
				cout<<'#';
		}
		cout<<endl;
	}
	rep(i, 50, 100){
		rep(j, 0, 100){
			if(ans[i][j] == '#')
				cout<<ans[i][j];
			else
				cout<<'.';
		}
		cout<<endl;
	}
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, k, s int
	fmt.Scan(&n)
	fmt.Scan(&k)
	fmt.Scan(&s)

	// S=10**9のとき
	// A1からAKを10**9とし、残りを1で埋めればよい
	// S/=10**9のとき
	// 左側でK通り作ったら、右側はS+1で埋めればよい
	// 左側でK通り作るにはどうすればいいか
	// A1からAKをSにすればOK?
	if s == int(math.Pow(10, 9)) {
		for i := 0; i < k; i++ {
			fmt.Print(s)
			fmt.Print(" ")
		}
		for i := 0; i < n-k-1; i++ {
			fmt.Print(1)
			fmt.Print(" ")
		}
		if n > k {
			fmt.Println(1)
		}
	} else {
		for i := 0; i < k; i++ {
			fmt.Print(s)
			fmt.Print(" ")
		}
		for i := 0; i < n-k-1; i++ {
			fmt.Print(s + 1)
			fmt.Print(" ")
		}
		if n > k {
			fmt.Println(s + 1)
		}
	}
}

func scanNums(len int) (nums []int) {
	var num int
	var i int
	for i = 0; i < len; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	return
}


Measured memory_bytes: 3968
/*
                                                                                                                                               
8b        d8                           888888888888                                             88b           d88                  ad88888ba   
 Y8,    ,8P                                 88                                        ,d        888b         d888                 d8"     "8b  
  Y8,  ,8P                                  88                                        88        88`8b       d8'88                 ""      a8P  
   "8aa8"  ,adPPYba,   88       88          88  8b,dPPYba,  88       88  ,adPPYba,  MM88MMM     88 `8b     d8' 88   ,adPPYba,          ,a8P"   
    `88'  a8"     "8a  88       88          88  88P'   "Y8  88       88  I8[    ""    88        88  `8b   d8'  88  a8P_____88         d8"      
     88   8b       d8  88       88          88  88          88       88   `"Y8ba,     88        88   `8b d8'   88  8PP"""""""         ""       
     88   "8a,   ,a8"  "8a,   ,a88          88  88          "8a,   ,a88  aa    ]8I    88,       88    `888'    88  "8b,   ,aa         aa       
     88    `"YbbdP"'    `"YbbdP'Y8          88  88           `"YbbdP'Y8  `"YbbdP"'    "Y888     88     `8'     88   `"Ybbd8"'         88       
                                                                                                                                               
*/
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int n, k;
long long C[2005][2005];

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

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

	for (int i = 0; i <= 2000; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) C[i][j] = 1;
			else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}

	cin >> n >> k;

	int B = k;
	int R = n - k;
	for (int i = 1; i <= k; i++) {
		cout << (C[R + 1][i] * C[B - 1][B - i]) % MOD << '\n';
	}

	return 0;
} 

Measured memory_bytes: 30208
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> a(n);
    for(size_t i = 0; i < n; i++) {
        a[i] = s[i] - '0';
    }
    vector<int> rui(n + 1, 0);
    for(size_t i = 0; i < n; i++) {
        rui[i + 1] = rui[i] + a[i];
    }
    int k = n + 1;
    while(k--) {
        if(rui[k] - rui[n - k] == 0 || rui[k] - rui[n - k] == 2 * k - n) {
            cout << k << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define mod 1000000007
using namespace std;
vector<int> v;
signed main(){
	int n,ans=1;
	cin>>n;
	for(int i=2;i<=n;i++){
		for(int j=0;j!=v.size()&&v[j]*v[j]<=i;j++){
			if(i%v[j]==0) goto loop;
		}
		v.push_back(i);
		loop:;
	}
	f(i,v.size()){
		int x=0,z=n/v[i];
		while(z){
			x+=z;
			z/=v[i];
		}
		ans=ans*(x+1)%mod;
	}
	cout<<ans<<endl;
	return 0;
}


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

int n,k;
int numi, x;
int a1, a2;

int main(){
    while(cin>>n>>k){
        for(int i=0; i<n; i++){
            cin>>x;
            if(x==1){
                numi = i+1;
            }
        }

        if((numi-1)%(k-1) == 0){
            a1 = (numi-1)/(k-1);
            if((n-numi)%(k-1) == 0){
                a2 = (n-numi)/(k-1);
            }
            else{
                a2 = (n-numi)/(k-1)+1;
            }
        }
        else if((n-numi)%(k-1) == 0){
            a2 = (n-numi)/(k-1);
            if((numi-1)%(k-1) == 0){
                a1 = (numi-1)/(k-1);
            }
            else {
                a1 = (numi-1)/(k-1)+1;
            }
        }
        else if((n-1)%(k-1)==0){
            a1 = (n-1)/(k-1);
            a2 = 0;
        }
        else {
            a1 = (n-1)/(k-1)+1;
            a2 = 0;
        }


        cout<<a1+a2<<endl;
    }
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;/*10^12*/
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}

////////////////////////////////////////


int main(){
    int n,x,y,z;cin>>n>>x>>y>>z;
    int s=x+y+z;
    ll dp[n][1<<s];memset(dp,0,sizeof(dp));
    rep(i,0,9)dp[0][(1<<i)%(1<<s)]++;
    vector<ll>eli;
    rep(j,0,(1<<s)-1){
        if((j>>(z-1))&1){
            if((j>>(y+z-1))&1){
                if((j>>(x+y+z-1))&1)eli.pb(j);
            }
        }
    }
   // cout<<"eli:";for(auto x:eli)cout<<x<<" ";cout<<endl;
    rep(i,0,n-2){
        rep(j,0,(1<<s)-1){
            rep(k,1,10){
                dp[i+1][((j<<k)+(1<<(k-1)))%(1<<s)]=mod(dp[i+1][((j<<k)+(1<<(k-1)))%(1<<s)]+dp[i][j]);
            }
        }
        for(auto x:eli)dp[i+1][x]=0;
    }
   /* rep(i,0,n-1){
        cout<<i<<":";
        rep(j,0,(1<<s)-1){
            cout<<dp[i][j]<<" ";
        }cout<<endl;
    }*/
    ll ans=0;
    rep(j,0,(1<<s)-1){
        ans=mod(ans+dp[n-1][j]);
    }
    ll sum=1;
    for(int i=1;i<=n;i++)sum=mod(sum*10);
   // cout<<sum<<endl;
    cout<<mod(sum-ans)<<endl;
    return 0;
}


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

int main(){
    int a, b;
    while(true){
        cin >> a >> b;
        if(a == 0 && b == 0) break;
        if(a > b){
            int tmp;
            tmp = a;
            a = b;
            b = tmp;
        }
        cout  << a << " " << b << endl;
    }
    return 0;
}


Measured memory_bytes: 3020
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <iomanip>

using namespace std;
using ll = long long;

#define endl "\n"
#define pb push_back

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

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

	double t, x;
	cin >> t >> x;
	cout << fixed << setprecision(3) << (t / x) << endl;
}


Measured memory_bytes: 256
def factrize(x):
    # 試し割りによるxの素因数分解
    f = {}
    tmp = x
    i = 2
    while i**2 <= tmp:
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp = tmp // i
        if cnt > 0:
            f[i] = cnt
        i += 1
    if tmp != 1 or f == {}:
        f[tmp] = 1
    return f


n = map(int, input().split())
*A, = map(int, input().split())
A = [factrize(a) for a in A]
F = {}
for f in A:
    for p in f:
        try:
            F[p] = max(F[p], f[p])
        except KeyError:
            F[p] = f[p]
ans = 1
for p in F:
    ans *= p**F[p]
print(ans)



Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 200001;

int n, q, val[N], ans[N];
vector <int> v[N];

void dfs(int node, int pnode, int cur){
    cur += val[node];
    ans[node] = cur;
    for(auto &i : v[node]){
        if(i == pnode) continue;
        dfs(i, node, cur);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for(int i = 0 ; i < n - 1 ; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 0 ; i < q ; i++){
        int x, y;
        cin >> x >> y;
        val[x] += y;
    }
    dfs(1, 0, 0);
    for(int i = 1 ; i <= n ; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 24192
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);
		String s;
		s = scan.next();

		String strReverse;

		char[] moto = s.toCharArray();
		char[] reverse = new char[moto.length];
		int j = 0;

		for (int i = moto.length - 1; i >= 0; i--) {
			reverse[j] = moto[i];
			j++;

		}

		//①回文か確認
		strReverse = String.valueOf(reverse);

		if (!s.equals(strReverse)) {
			System.out.println("No");

			return;
		}

		//前半取得
		String zenhan = s.substring(0, (s.length() - 1) / 2);
		//前半の回文
		char[] zenhan_rev = new char[zenhan.length()];

		j = 0;
		for (int i = zenhan.length() - 1; i >= 0; i--) {
			zenhan_rev[j] = zenhan.charAt(i);
			j++;
		}
		String strZenhanRev = String.valueOf(zenhan_rev);
		if (!zenhan.equals(strZenhanRev)) {
			System.out.println("No");

			return;
		}

		//後半取得
		//前半取得
		zenhan = s.substring((s.length() + 3) / 2 - 1, s.length());
		//前半の回文
		zenhan_rev = new char[zenhan.length()];

		j = 0;
		for (int i = zenhan.length() - 1; i >= 0; i--) {
			zenhan_rev[j] = zenhan.charAt(i);
			j++;
		}
		strZenhanRev = String.valueOf(zenhan_rev);
		if (!zenhan.equals(strZenhanRev)) {
			System.out.println("No");

			return;
		}

		System.out.println("Yes");
		return;
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long int sum=0, n, i;
  cin >> n;
  for(i=1;i<=n;i++){
    if(i%3!=0 and i%5!=0 and i%15!=0)
      	sum+=i;
  }	
    cout << sum << endl;
  return 0;
}

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

using ll= long long;
#define double long double
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _set(x) __builtin_popcount(x)
#define _setl(x) __builtin_popcountll(x)
#define PI  3.14159265358979323846264338327950L
#define mod 1000000007LL

void debug(){
	cerr<<"]\n";
}
template<class H,class ... T> void debug(H h,T... t){
	cerr<<h;
	if(sizeof... (t)){
		cerr<<", ";
	}
	debug(t...);
}
#ifdef DEBUG
	#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", debug(__VA_ARGS__)
	#define dpv(...) cerr<< "["#__VA_ARGS__ " : ";for(int i: (__VA_ARGS__)){cerr<<i<<" ";}cerr<<"]\n"
#else
	#define dbg(...) 0
	#define dpv(...) 0
#endif

void solve(){
	int n;
	cin>>n;
	cout<<(n^1)<<"\n";
}


int32_t main(){
	IOS
	// freopen("input.txt","r",stdin);
	int _;
	// cin>>_;
	_=1;
	for(int i=1;i<=_;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}

/*
   check for overflows int long long
   correct mize of array
*/


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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

s, w  = MAP()

if s > w:
    print('safe')
else:
    print('unsafe')


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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string S; cin >> S;
  int XX = stoi(S.substr(0, 2));
  int YY = stoi(S.substr(2, 2));
  if(XX >= 13 || XX == 0){
    if(YY >= 1 && YY <= 12){
      cout << "YYMM" << endl;
    }else{
      cout << "NA" << endl;
    }
  }else{
    if(YY >= 1 && YY <= 12){
      cout << "AMBIGUOUS" << endl;
    }else{
      cout << "MMYY" << endl;
    }
  }
}

Measured memory_bytes: 256
import math

n = int(input())
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]

P_list = []
Q_list = []
for i in range(n):
    P_list.append(i+1)
    Q_list.append(i+1)

count_p = 1
count_q = 1
for i in range(n):
    p = P[i]
    ind = P_list.index(p)
    count_p += ind * math.factorial(n-i-1)
    P_list.pop(ind)
    
    q = Q[i]
    ind = Q_list.index(q)
    count_q += ind * math.factorial(n-i-1)
    Q_list.pop(ind)

print(abs(count_p-count_q))

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

int main() {
  int N,L;
  cin >> N >> L;
  vector<string> vec(N);
  for(int i = 0;i < N;i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  for(int j = 0;j < N;j++) {
    cout << vec.at(j);
  }
}

Measured memory_bytes: 256
n = int(input())
towns = []
for _ in range(n):
  towns.append([int(x) for x in input().split()])

import math
import itertools
patterns = list(itertools.permutations(range(n)))

length = 0
for pattern in patterns:
  for i in range(n-1):
    p = pattern[i]
    pp = pattern[i+1]
    length += math.sqrt((towns[p][0]-towns[pp][0])**2 + (towns[p][1]-towns[pp][1])**2)

print(length/len(patterns))




Measured memory_bytes: 8052
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H == 0 && W ==0) {
				break;
			}
			for(int i = 0 ; i < H ; i++) {
				for(int j = 0 ; j < W ; j++) {
					if(i == 0 || i == H -1 || j == 0 || j == W -1) {
						System.out.print("#");
					} else if(j > 0 || j < W){
						System.out.print(".");
					}
				}
				System.out.println();
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 34532
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int result1 = a*b;
		int result2 = 2*a + 2*b;
		System.out.println(result1 + " " + result2);
	}
}

Measured memory_bytes: 26292
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int> > adj[MAX]; //重み付き有効グラフの隣接リスト表現

void dijkstra(){
    priority_queue<pair<int, int> > PQ;
    int color[MAX];
    int d[MAX];
    for(int i=0; i<n; i++){
        d[i] = INFTY;
        color[i] = WHITE;
    }

    d[0] = 0;
    PQ.push(make_pair(0,0));
    color[0] = GRAY;

    while( !PQ.empty() ){
        pair<int, int> f = PQ.top(); PQ.pop();
        int u = f.second;

        color[u] = BLACK;

        //最小値を取り出し、それが最短でなければ無視
//        if( d[u] < f.first * (-1) ) continue;

        for(int j=0; j<adj[u].size(); j++){
            int v = adj[u][j].first;
            if(color[v] == BLACK) continue;
            if(d[v] > d[u] + adj[u][j].second){
                d[v] = d[u] + adj[u][j].second;
                //priority_queueはデフォルトでは大きい値を優先するため‐１をかける
                PQ.push(make_pair(d[v]*(-1), v));
                color[v] = GRAY;
            }
        }
    }

    for(int i=0; i<n; i++){
        cout << i << " " << (d[i] == INFTY ? -1 : d[i] ) << endl;
    }
}

int main(){
    int k, u, v, c;

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> u >> k;
        for(int j=0; j<k; j++){
            cin >> v >> c;
            adj[u].push_back(make_pair(v,c));
        }
    }

    dijkstra();

    return 0;
}


Measured memory_bytes: 8000