akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <string>
#include <ctime>
#include <vector>
#include <iterator>
#include <algorithm> // #include <iostream> // using namespace std; srand(time(NULL))
#include <iostream>

using namespace std;

std::vector<int> answer;

std::vector<int> compare (std::vector<int> n1, std::vector<int> n2){
    std::vector<int> compare_result;
    
    std::size_t n1_size = n1.size();
    std::size_t n2_size = n2.size();

    // n1について，n2におけるどの位置に値するかを記録しておくvector配列
    std::vector<int> n1_iterator(n1_size);

    bool forEnd = false;
    for(int i = 0; i < n1_size; i++){
        for(int j = 0; j < n2_size; j++){
            if(i ==0 && j == 0 && n1[n1_size - 1] <= n2[0]){
                n1_iterator[n1_size - 1] = 0;
                forEnd = true;
            }
            if(forEnd){
                break;  
            }
            if(n1[n1_size-1-i] <=n2[j]) {
                n1_iterator[n1_size-1-i] = j;
                break;
            }
            if(j == n2_size-1){
                n1_iterator[n1_size-1-i] = n2_size;
            }
        }
        if(forEnd){
            break;  
        }
    }

    // n1_which，n2_which：各々についてのiterator
    int n1_which = 0;
    int n2_which = 0;
    
    // n1_iteratorの末尾が0であるときに関して，n1_iteratorの全要素が0になるのでそれを代入する．
    if(n1_iterator[n1_size - 1] == 0){
        for(int j = 0; j <n1_size; j++){
            n1_iterator[j] = 0;
        }
    }

    while((n2_which <= n2_size - 1) || (n1_which <= n1_size - 1)){
        if(n1_which != n1_size) {
            if (n1_iterator[n1_which] > n2_which ){
                compare_result.push_back(n2[n2_which]);
                n2_which++;
            }
            else {
                compare_result.push_back(n1[n1_which]);
                n1_which++;
            }
        }
        else{
            compare_result.push_back(n2[n2_which]);
            n2_which++; 
        }
    }
    
    return compare_result;
}

std::vector<int> merge (std::vector<int> n){ // int merge (string *s, int N, std::vector<int> n){
    
    std::size_t n_size = n.size();
    if (n_size <= 2){
        if (n_size != 1) {
            if(n[0] > n[1]){
                int x = n[0];
                std::iter_swap(n.begin(),n.begin()+1);
            }
        } 
        return n;
    } else {
        std::vector<int> n1,n2;
        copy(n.begin(), std::next(n.begin(), (int) n_size/2),back_inserter(n1));
        int xx = n_size /2;
        copy(std::next(n.begin(), xx), n.end(), back_inserter(n2));
        // return n2;
        return compare(merge(n1), merge(n2));
    }
}

int main () { 
  
  int N;
  cin >> N;
  vector<int> X(N);
  vector<int> Y(N);
  int sub;
  int max, min;
  max = -1;
  min = -1;
  for (int i = 0; i < N; i++) {
    cin >> sub;
    X[i] = sub;
    Y[i] = sub;
  }
  sort(X.begin(),X.end());

  
  // これで整理されているので...
  int upper = 0;
  int bottom = 0;
  for (int i = 0; i < N; i++) {
    upper = X[N/2];
    bottom = X[N/2 - 1];
    if (bottom >= Y[i]) {
      cout << upper << endl;
    }
    else {
      if (upper == Y[i]) {
        cout << bottom << endl;  
      }
      else {
        cout << bottom << endl;  
      }
    }
  }
}


Measured memory_bytes: 3712
#include<iostream>
#include<vector>
#include<queue>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    int n;
  cin >>n;
  priority_queue<int> p;
  int a=0;
  for(int i=0;i<n;i++){
    cin >>a;
    p.push(a);
  }
  
  
  
  int maxs=1000000;
  int count=0;
  for(int i=0;i<n;i++){
    if (p.top() < maxs)count++;
    maxs = p.top();
    p.pop();
  }

    cout << count;
    
    return 0;
}


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

int main() {
    int n, c, cakes = 0;
    scanf("%d %d", &n, &c);
    rep(i,c) {
        int ck;
        scanf("%d", &ck);
        cakes += ck;
    }
    printf("%d\n", (cakes+n)/(n+1));
}


Measured memory_bytes: 3228
#include <stdio.h>

int n, A[50];

// 入力値の M から選んだ要素を引いていく再帰関数
int solve(int i, int m) {
    if (m == 0) return 1;
    if (i >= n) return 0;
    int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
    return res;
}

int main() {
    int q, M, i;

    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &A[i]);
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &M);
        if (solve(0, M)) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}


Measured memory_bytes: 2112
#include<iostream>
using namespace std;
int n,m;
int d[1001];
int c[1001];
int dp[1002][1001];
int dp_hiroudo(int i,int j){
  if(i==n){
    return 0;
  }else if(dp[i][j]==-1){
    dp[i][j]=min(dp_hiroudo(i+1,j+1)+d[i]*c[j],dp_hiroudo(i,j+1));
  }
  return dp[i][j];
}
int main(){
  cin >>n>>m;
  for(int i=0;i<n;i++)cin >>d[i];
  for(int i=0;i<m;i++)cin >>c[i];
  for(int i=0;i<1002;i++){
    for(int j=0;j<1001;j++){
      if(n-i>m-j)dp[i][j]=1000000000;
      else dp[i][j]=-1;
    }
  }
  dp_hiroudo(0,0);
  cout <<dp[0][0]<<endl;
  return 0;
}

Measured memory_bytes: 7056
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
using lint = int64_t;

int main() {
    const int mod = 1000000007;
    
    int H, W, K;
    cin >> H >> W >> K;
    --K;
    
    vector<int> S = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
    vector<vector<lint>> dp(H + 1, vector<lint>(W, 0));
    dp[0][0] = 1;
    rep(i, H) rep(j, W) {
        if (j - 1 >= 0) {
            dp[i + 1][j - 1] += dp[i][j] * S[j - 1] * S[W - j - 1];
            dp[i + 1][j - 1] %= mod;
        }
        dp[i + 1][j] += dp[i][j] * S[j] * S[W - j - 1];
        dp[i + 1][j] %= mod;
        if (j + 1 <= W - 1) {
            dp[i + 1][j + 1] += dp[i][j] * S[j] * S[W - j - 2];
            dp[i + 1][j + 1] %= mod;
        }
    }
    cout << dp[H][K] << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std ;
 int main(){
 int a,b,c;
 cin>>a>>b>>c;
 if(a==b&&b==c){
    cout<<1;

 }
  else if(a!=b&&b!=c&&a!=c){
    cout<<3;
 }
 else cout<<2;
 return 0;
 }

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int mount[10];
    int i, j, k, high, num = 0;
    for(i = 0; i < 10; i++){
        scanf("%d",&mount[i]);
    }
    for(j = 0; j < 3; j++){
        high = mount[0];
        for(k = 1; k < 10; k++){
            if(high < mount[k]){
                high = mount[k];
                num = k;
            }
        }
        printf("%d\n",high);
        mount[num] = 0;
    }
    return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int tyukan = sc.nextInt();
            int kimatsu = sc.nextInt();
            int saishi = sc.nextInt();
            if(tyukan == -1 && kimatsu == -1 && saishi == -1) break;
            int sum = tyukan+kimatsu;
            if(tyukan==-1 || kimatsu==-1 || sum<30) System.out.println("F");
            else if(sum>=80) System.out.println("A");
            else if(sum>=65) System.out.println("B");
            else if(sum>=50 || (sum>=30 && saishi>=50)) System.out.println("C");
            else System.out.println("D");
        }
        sc.close();
    }

}


Measured memory_bytes: 26340
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 105
int n;
int x1[MAXN],y1[MAXN],h1[MAXN];
int Abs(int x)
{
	if(x>=0) return x;
		return -x;
}
bool check(int h,int x,int y)
{
	for(int i=1;i<=n;i++)
		if(h1[i]!=max((h-abs(x1[i]-x)-abs(y1[i]-y)),0))
			return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	int t1,t2,t3;
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&x1[i],&y1[i],&h1[i]);
		if(h1[i]>0) t1=x1[i],t2=y1[i],t3=h1[i];
	}
	for(int x=0;x<=100;x++)
		for(int y=0;y<=100;y++)
		{
			int h=t3+abs(t1-x)+abs(t2-y);
			if(check(h,x,y))
			{
				printf("%d %d %d\n",x,y,h);
				return 0;
			}
		}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 100000;
const int mod = 998244353;

const int mn=1e5+5;
int n;
int cnt[mn];
int maxh=0;
ll powmod(ll base, ll times)
{
    ll res = 1;
    while (times > 0)
    {
        if (times&1) res = res * base % mod;
        base = base * base % mod;
        times >>= 1;
    }
    return res;
}
ll pre[maxN+10], inv[maxN+10];
void init()
{
    pre[0] = inv[0] = 1;
    for (ll i = 1; i <= maxN; i++)
        pre[i] = pre[i-1] * i % mod;
    inv[maxN] = powmod(pre[maxN], mod - 2);
    for (ll i = maxN; i > 1; i--)
        inv[i-1] = inv[i] * i % mod;
}
ll C(ll x, ll y)
{
    if (y > x) return 0;
    else return pre[x] * inv[y] % mod * inv[x-y] % mod;
}

void bye(){
    puts("0");
    exit(0);
}

int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int h;
        scanf("%d",&h);
        if (i==1&&h!=0) bye();
        if (i>1&&!h) bye();
        cnt[h]++;
        maxh=max(h,maxh);
    }
    ll ans=1;
    for(int i=1;i<=maxh;i++){
        ans=ans*powmod(cnt[i-1],cnt[i])%mod;
        if (cnt[i]==0) ans=0;
    }
    printf("%lld\n",ans);
    return 0;
}


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

vector< vector<int> > to;
vector<int> ans;

void dfs(int c,int p=-1){
  for(int u:to.at(c)){
    if(u==p){
      continue;
    }
    ans.at(u)+=ans.at(c);
    dfs(u,c);
  }
}
int main(){
  int n,q;
  cin >> n >> q;
  //v.resize(N);
  to.resize(n);
  for(int i=0;i<n-1;i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    to.at(a).push_back(b);
    to.at(b).push_back(a);
  }
  ans.resize(n);
  for(int i=0;i<q;i++){
    int p,x;
    cin >> p >> x;
    p--;
    ans.at(p)+=x;
  }
  dfs(0);
  for(int i=0;i<n;i++){
    cout << ans.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 26624
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
class R{
	public:
		int id;
		string name;
		int v;
		R(){};
		R(int a,string s,int b):id(a),name(s),v(b){};
		bool operator <(const R &r)const{
			return (name<r.name)||(name==r.name&&v>r.v);
		}
};
int main(){
	int n;
	cin>>n;
	vector<R> hoge(n);
	string s;
	int p;
	rep(i,n){
		cin>>s>>p;
		R tmp(i+1,s,p);
		hoge[i]=tmp;
	}
	sort(hoge.begin(),hoge.end());
	//reverse(hoge.begin(),hoge.end());
	rep(i,n){
		cout<<hoge[i].id<<endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define RREP(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

string s;

int main(){
    cin >> s;
    int n = s.size();
    RREP(i,n){
        
        if(i%2==0){
            bool flag = true;
            REP(j,i/2){
                if(s[j]!=s[j+i/2]){
                    flag = false;
                }
            }
            if(flag){
                put(i);
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define pii pair<ll,ll>
#define vi(x) vector<x>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;

signed main()
{
    fast;
  
    ll x;
    cin>>x;
    if(x>=400 and x<=599) cout<<"8";
    else if(x>=600 and x<=799) cout<<"7";
    else if(x>=800 and x<= 999) cout<<"6";
    else if(x>=1000 and x<=1199) cout<<"5";
    else if(x>=1200 and x<=1399) cout<<"4";
    else if(x>=1400 and x<=1599) cout<<"3";
    else if(x>=1600 and x<=1799) cout<<"2";
    else cout<<"1";
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
using ll=long long;
using namespace std;

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

    int L=N.size();

    vector<vector<ll>> dp1(L+1,vector<ll>(K+1,0));
    vector<vector<ll>> dp2(L+1,vector<ll>(K+1,0));

    dp1[0][0]=1;
    dp2[0][0]=1;
    for(int i=1;i<L+1;i++){
        dp1[i][0]=1;
        dp2[i][0]=1;
        int thisnum=(int)N[L-i]-'0';
        for(int j=1;j<K+1;j++){
            if(thisnum!=0){
                dp1[i][j]=dp2[i-1][j]+dp2[i-1][j-1]*(thisnum-1)+dp1[i-1][j-1];
            }else{
                dp1[i][j]=dp1[i-1][j];
            }
            dp2[i][j]=dp2[i-1][j]+dp2[i-1][j-1]*9;
        }
    }
    /*
    for(int i=0;i<L+1;i++){
        for(auto p:dp1[i]){
            cout<<p<<" ";
        }
        cout<<endl;
    }
    for(int i=0;i<L+1;i++){
        for(auto p:dp2[i]){
            cout<<p<<" ";
        }
        cout<<endl;
    }
    //*/

    cout<<dp1[L][K]<<endl;

    return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()



vector<vector<int>> G;
vector<int> ans;

void dfs(int cu,int p,int c){
    ans[cu]=c;
    //cout<<cu<<" "<<c<<endl;
    for(int v : G[cu]){
        if(v==p) continue;
        if(c==0) dfs(v,cu,1);
        else dfs(v,cu,0);
    }
}

int main(){
    int n;
    cin>>n;
    G.resize(3*n); 
    ans.resize(3*n);   
    int nxt=n;
    rep(i,n-1){
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        if(w%2==1){
            G[u].push_back(v);
            G[v].push_back(u);
        }
        else{
            G[u].push_back(nxt);
            G[nxt].push_back(u);
            G[v].push_back(nxt);
            G[nxt].push_back(v);
            nxt++;
        }
    }

    dfs(0,-1,0);
    rep(i,n) cout<<ans[i]<<endl;
}

 

Measured memory_bytes: 15872
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;
struct Combin{
	#define N 200005
	int fac[N],rv[N],facrv[N];
	Combin(){
		fac[0]=rv[1]=facrv[0]=1;
		for(int i=2;i<N;i++) rv[i]=((-(LL)(mod/i)*rv[mod%i]%mod)+mod)%mod;
		for(int i=1;i<N;i++) fac[i]=(LL)fac[i-1]*i%mod;
		for(int i=1;i<N;i++) facrv[i]=(LL)facrv[i-1]*rv[i]%mod;
	}
	int C(int r1,int n1){
		if(r1>n1) return 0;
		return fac[n1]*(LL)facrv[r1]%mod*facrv[n1-r1]%mod;
	}
	#undef N
}C;
int calc(int str,int stc,int enr,int enc){
	return C.C(enr-str,enr-str+enc-stc);
}
int main(){
	int h,w,a,b;
	cin>>h>>w>>a>>b;
	int ans=calc(1,1,h,w);
	for(int i=h-a+1,j=b;i<=h&&j>=1;i++,j--)
		ans=(ans-calc(1,1,i,j)*1LL*calc(i,j,h,w))%mod;
	cout<<(ans+mod)%mod<<endl;
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <map>
using namespace std;

struct node{
    int id,parent,depth;
    string type;
    vector<int> child; 
};

node u[110000];

void disp(node *v){
    cout << "node " << v->id << ": parent = " << v->parent
         << ", depth = " << v->depth << ", " << v->type
         << ", [";
    if(v->child.size() == 0) cout << ']' << endl;
    else{
        for(int i=0;i<v->child.size();i++){
            if(i) cout << ", ";
            cout << v->child.at(i);
        }
        cout << ']' << endl;
    }
}

int depth(node *v){
    if(v->parent == -1) return 0;
    return depth(&u[v->parent])+1;
}

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        u[i].parent=-1;
    }
    for(int i=0;i<n;i++){
        int m;
        cin >> m;
        u[m].id = m;
        int x;
        cin >> x;
        for(int j=0;j<x;j++){
            int y;
            cin >> y;
            u[m].child.push_back(y);
            u[y].parent = m;
        }
    }
    for(int i=0;i<n;i++){
        u[i].depth = depth(&u[i]);
        if(u[i].parent == -1) u[i].type = "root";
        else if(u[i].child.size() == 0) u[i].type = "leaf";
        else u[i].type = "internal node";
    }
    for(int i=0;i<n;i++){
        disp(&u[i]);
    }
}


Measured memory_bytes: 13860
import sys

def caesar(c):
  if c == "z":
    return "a"
  elif c == "Z":
    return "A"
  elif 65 <= ord(c) and ord(c) <= 122:
    return chr(ord(c)+1)
  else:
    return c

while True:
  text = sys.stdin.readline()
  if not text: break
  text = text.rstrip()
  while True:
    if "the" in text or "this" in text or "that" in text:
      print(text)
      break
    text = "".join(map(caesar, list(text)))

Measured memory_bytes: 6440
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define il inline
#define ri register
using namespace std;
struct point{
    point*next;int to;
}*t,*head[100001];
int ans;
int dep[100001],s[100001],
    u,v,rl,check,te[100001],
    round[100001],rt;
il int Abs(int);
il void read(int&),link(int,int);
void dfs1(int,int),dfs2(int,int),dfs3(int,int);
int main(){
    int n,m,i,j,k;read(n),read(m);
    for(i=1;i<=m;++i)read(j),read(k),link(j,k);
    s[0]=-1,dfs1(1,0);
    if(m==n-1){
        if(check)puts("-1"),exit(0);
        dfs2(1,0),printf("%d",ans);return 0;
    }
    else if(rl&1){
        if(check&1)puts("-1"),exit(0);
        check/=2,ans+=Abs(check);
        s[u]-=check,s[v]-=check,dfs2(1,0);
        printf("%d",ans);return 0;
    }
    else{
        if(check)puts("-1"),exit(0);
        te[u]=1,te[v]=-1,dfs3(1,0);
        round[++rt]=0,sort(round+1,round+rt+1);
        j=round[rt+1>>1];
        for(i=1;i<=rt;++i)ans+=Abs(round[i]-j);
        printf("%d",ans);
    }
    return 0;
}
void dfs3(int x,int pa){
    for(point*i(head[x]);i!=NULL;i=i->next)
        if(i->to!=pa)
            dfs3(i->to,x),s[x]+=s[i->to],
                te[x]+=te[i->to];
    if(te[x])round[++rt]=te[x]*s[x];
    else ans+=Abs(s[x]);
}
void dfs2(int x,int pa){
    for(point*i(head[x]);i!=NULL;i=i->next)
        if(i->to!=pa)
            dfs2(i->to,x),s[x]+=s[i->to];
    ans+=Abs(s[x]);
}
void dfs1(int x,int pa){
    dep[x]=dep[pa]+1,s[x]=~s[pa]+1,check+=s[x];
    for(point*i(head[x]);i!=NULL;i=i->next)
        if(i->to!=pa){
            if(dep[i->to])
                u=x,v=i->to,rl=Abs(dep[x]-dep[i->to])+1,
                    i->to=pa;
            else dfs1(i->to,x);
        }
}
il int Abs(int x){
    return x<0?~x+1:x;
}
il void link(int i,int j){
    t=new point,t->next=head[i],head[i]=t,t->to=j;
    t=new point,t->next=head[j],head[j]=t,t->to=i;
}
il void read(int&x){
    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}


Measured memory_bytes: 13568
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
using ll = long long;

int main(){
    int n;
    ll k;
    cin >> n >> k;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }

    ll ans,s1,s2;
    ans = s1 = s2 = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i] > a[j]){
                s1++;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i] < a[j]){
                s2++;
            }
        }
    }

    ans += s1*k%MOD;
    ans += s2*((k*(k-1)/2)%MOD);
    ans %= MOD;
    cout << ans << endl;
}


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

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

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

    sort(A.begin(), A.end());
    bool flag = true;
    if (N % 2 == 0) {
        for (int i = 1; i < N; i += 2) {
            if (cnt[i] != 2) {
                flag = false;
                break;
            }
        }
    }
    else if (N % 2 == 1) {
        for (int i = 0; i < N; i += 2) {
            if (i == 0 && cnt[i] != 1) {
                flag = false;
                break;
            }
            else if (i != 0 && cnt[i] != 2) {
                flag = false;
                break;
            }
        }
    }

    long long ans = 1;
    int amari = pow(10, 9) + 7;
    if (flag) {
        for (int i = 0; i < N / 2; i++) {
            ans *= 2;
            if (ans >= amari) {
                ans %= amari;
            }
        }
        cout << ans << endl;
    }
    else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, X;
  cin >> N >> X;
  int cnt = 0;
  int d = 0;
  if (d <= X) cnt++;
  FOR(i,0,N) {
    int L;
    cin >> L;
    d += L;
    if (d <= X) cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

#define len length()
#define sz size()
#define rep(i, n) for(int i = 0; i < n; i++)
#define srt(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define vi(a, n) vector<int> a(n)
#define vs(a, n) vector<string> a(n)
#define vc(a, n) vector<char> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)

int main(){
    int D, N;
    cin >> D >> N;
    if(N!=100) cout << int(pow(100, D)) * N << endl;
    else cout << int(pow(100, D)) * (N + 1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
using namespace std;
int fa[100010],p[100010],vis[100010];
int get(int x){return fa[x]==x?x:(fa[x]=get(fa[x]));}
struct pr{
	int x,y;
	pr(int a=0,int b=0){x=a;y=b;}
};
vector<pr>v[100010];
vector<pr>::iterator it;
int main(){
	int n,m,i,x,y,ans;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",p+i);
		fa[i]=i;
	}
	while(m--){
		scanf("%d%d",&x,&y);
		fa[get(x)]=get(y);
	}
	for(i=1;i<=n;i++)v[get(i)].push_back(pr(i,p[i]));
	ans=0;
	for(i=1;i<=n;i++){
		for(it=v[i].begin();it!=v[i].end();it++)vis[it->x]=i;
		for(it=v[i].begin();it!=v[i].end();it++){
			if(vis[it->y]==i)ans++;
		}
	}
	printf("%d",ans);
}

Measured memory_bytes: 6912
n, c = map(int, input().split())
T = 10**5+1
l = [[0]*c for _ in range(T)]

for _ in range(n):
    s, t, c_ = map(int, input().split())
    c_ -= 1
    for i in range(s-1, t):
        l[i][c_] = 1

ans = 0
for i in range(T):
    ans = max(ans, sum(l[i]))

print(ans)


Measured memory_bytes: 35060
import sys
import math
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
s=input()
t=input()
count=0
for i in range(len(s)):
    if s[i]==t[i]:
        continue
    else:
        count=count+1
print(count)


Measured memory_bytes: 67988
def gcd(x, y):
    if min(x, y) == 0:
        return max(x, y)
    else:
        return gcd(y,x%y)


a, b = [int(i) for i in input().split()]
c = gcd(a, b)

def d(x):
    i = 2
    e=[]
    while True:
        if x % i == 0:
            e.append(i)
            while x % i == 0:
                x //= i
        if i * i > x:
            break
        i+=1
    if x != 1:
        e.append(x)
    return e
print(len(d(c))+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<bool> dp(K+1, false);
    for (int i = 1; i <= K; i++) {
        for (int j = 0; j < N; j++) {
            if (i < A[j]) break;
            if (!dp[i-A[j]]) {
                dp[i] = true;
                break;
            }
        }
    }
    if (dp[K]) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
}

Measured memory_bytes: 3544
import java.util.Arrays;
import java.util.Scanner;

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

		int a[] = { sc.nextInt(), sc.nextInt(), sc.nextInt() };
		Arrays.sort(a);
		
		System.out.println((a[2] * 10 + a[1]) + (a[0]));
	}
}


Measured memory_bytes: 21844
// C - Lamps
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
	int N, K; cin>>N>>K;
	vi A(N); rep(i, N) cin>>A[i];
	vi B;
	rep(i, K){
		B = vi(N, 0);
		rep(j, N){
			int l = max(0, j-A[j]);
			int r = j + A[j] + 1;
			B[l]++;
			if(r <= N-1) B[r]--;
		}
		bool is_same = true;
		rep(j, N-1){
			B[j+1] += B[j];
			if(B[j+1] != N) is_same = false;
		}
		if(is_same) break;
		A = B;
	}
	rep(i, N) cout<< B[i] << (i+1==N? "\n":" ");
}


Measured memory_bytes: 5596
#include <stdio.h>
int main(void){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a+b<c)
    {
        printf("%d\n",a+2*b+1);
    }
    else
    {
        printf("%d\n",b+c);
    }
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <set>
#include <algorithm>

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)

int n,m;
vector<int> tmp[125252];
pii ranges[353531];   // sort by first, [left, right]
pii ranges2[353531];  // sort by second, [right, id]

int ans[125252];

const int B = 400;
const int C = 300;

// pointer struct
struct data{
  // id, position, in-iterator, out-iterator
  int id,pos,in,out;
};
data pts[C];
int cnt[353531];

int main(){
  // input
  scanf("%d%d",&n,&m);
  REP(i,n){
    int l,r;
    scanf("%d%d",&l,&r);
    ranges[i] = pii(l,r);
  }
  
  // d small
  FOR(d,1,min(B,m+1)){
    int tmp = 0;
    REP(i,n){
      int x = (ranges[i].first+d-1)/d;
      if(x*d<=ranges[i].second)tmp++;
    }
    ans[d]=tmp;
  }

  // d large
  // sort
  {
    REP(i,n)tmp[ranges[i].first].push_back(ranges[i].second);
    int it = 0;
    REP(i,m+1){
      for(int j : tmp[i]){
        ranges[it++] = pii(i,j);
      }
      tmp[i].clear();
    }
  }
  {
    REP(i,n)tmp[ranges[i].second].push_back(i);
    int it = 0;
    REP(i,m+1)for(int j : tmp[i]){
      ranges2[it++] = pii(i,j);
    }
  }

  // pointer init
  data yo;
  yo.id=0; yo.pos=0; yo.in=0; yo.out=0;
  set<int> S;
  int tmp = 0;
  FOR(i,1,m+1){
    yo.pos++;
    while(yo.in<n && ranges[yo.in].first==yo.pos){
      S.insert(yo.in);
      yo.in++;
    }
    while(yo.out<n && ranges2[yo.out].first<yo.pos){
      S.erase(S.find(ranges2[yo.out].second));
      yo.out++;
    }
    if(i%B==0){
      // pts
      pts[yo.id] = yo;
      yo.id++;
      for(int x : S){
        if(cnt[x]==0)tmp++;
        cnt[x]++;
      }
    }
  }

  int pts_len = yo.id;
  FOR(d,min(B,m+1),m+1){
    ans[d] = tmp;
    if(d==m)break;
    REP(i,pts_len){
      if(pts[i].pos > m)break;
      // step pts[i]
      pts[i].pos += i+1;
      while(pts[i].in<n && ranges[pts[i].in].first<=pts[i].pos){
        if(cnt[pts[i].in]==0)tmp++;
        cnt[pts[i].in]++;
        pts[i].in++;
      }
      while(pts[i].out<n && ranges2[pts[i].out].first<pts[i].pos){
        int id = ranges2[pts[i].out].second;
        cnt[id]--;
        if(cnt[id]==0)tmp--;
        pts[i].out++;
      }
    }
  }
  FOR(d,1,m+1)printf("%d\n",ans[d]);
  return 0;
}


Measured memory_bytes: 26880
use std::vec::Vec;
use std::collections::HashSet;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let s: Vec<char> = read::<String>().chars().collect();
    let mut hs = HashSet::new();
    for &c in &s {
        if hs.contains(&c) {
           println!("no");
           return
        } else {
           hs.insert(c);
        }
    }
    println!("yes");
}


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

using namespace std;

int main() {
    int n; cin >> n;
    string s; cin >> s;
    if (n % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }
    if (s.substr(0, n / 2) == s.substr(n/2 , n/2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	char s[3][11];

	scanf("%s %s %s", s[0], s[1], s[2]);

	printf("%c%c%c\n", s[0][0] ^ 32, s[1][0] ^ 32, s[2][0] ^ 32);

	return 0;
}


Measured memory_bytes: 128
n=int(input())
l=[None for i in range(n)]
for i in range(n):
    s=input().split()
    l[i]=[s[0],int(s[1]),i+1]
l=sorted(l,key=lambda l:(l[0],-l[1]),)
for i in range(n):
    print(l[i][2])

Measured memory_bytes: 38512
# A - 高橋君とホテルイージー

# 1軒のホテルがあります。 このホテルの宿泊費は、次のようになっています。

# 最初の K 泊までは、1 泊あたり X 円
# K+1 泊目以降は、1 泊あたり Y 円

# N = 高橋くんの宿泊日数
# K = 割引なしの宿泊日数
# X = 割引なしの宿泊料
# Y = 割引後の宿泊料


N = int(input())
K = int(input())
X = int(input())
Y = int(input())

if N <= K:
    print(N * X)
else:
    print(K * X + (N - K) * Y)


Measured memory_bytes: 9168
#include <stdio.h>
#include <string.h>

#define REP(i,n,m) for(i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int main(void){
	int i,j;
	int w,h;
	int left,right,ans;
	int t[17][17],dp[17][17];

	while(scanf("%d%d",&w,&h) && (w||h)){
		rep(i,17) rep(j,17) t[i][j] = dp[i][j] = 0;
		rep(i,w) if(t[0][i] != 1) dp[0][i] = 1;

		rep(i,h) rep(j,w) scanf("%d",&t[i][j]);

		rep(i,h) rep(j,w) {
			left = j-1;
			right = j+1;

			if(t[i][j] == 0){
				if(i == h - 1){
					dp[i+1][j] += dp[i][j];
				}
				else{
					if(left >= 0 && t[i+1][left] == 0){
						dp[i+1][left] += dp[i][j];
					}
					if(right < w && t[i+1][right] == 0){
						dp[i+1][right] += dp[i][j];
					}
					if(t[i+1][j] != 1){
						dp[i+1][j] += dp[i][j];
					}
				}
			}
			else if(t[i][j] == 2 && t[i+2][j] != 1){
				dp[i+2][j] += dp[i][j];
			}
		}

		ans = 0;
		rep(i,w) ans += dp[h+1][i] + dp[h][i];

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

	return 0;
}

Measured memory_bytes: 0
N = int(input())
L = list(map(int, input().split()))

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            b = [L[i], L[j], L[k]]
            b.sort()
            if b[0] == b[1]:
                continue
            if b[1] == b[2]:
                continue
            if b[0]+b[1] > b[2]:
                cnt += 1

print(cnt)

Measured memory_bytes: 9192
using System;

class Program
{
    static void Main(string[] args)
    {
        bool[] used = new bool[26];

        string input = Console.ReadLine();

        for(int i = 0; i < input.Length; i++)
        {
            if (used[input[i] - 'a'])
            {
                Console.WriteLine("no");
                break;
            }
            else used[input[i] - 'a'] = true;
            if (i == input.Length - 1)
            {
                Console.WriteLine("yes");
            }
        }
    }
}

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

int main(){
  int n,a,b,c,x;

  while(cin>>n>>a>>b>>c>>x&&n|a|b|c|x!=0){
    vector<int> y(n);

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

    int count=0;
    int flag=0;

    for(int i=0;i<n;i++){
      if(y[i]==x&&flag==0){
        flag++;
        continue;
      }
      else{
        while(true){
          x = (a*x + b) % c;
          count++;
          if(count > 10000) break;
          if(y[i]==x) break;
        }
      }
      flag++;
    }
    if(count <= 10000)
      cout << count << endl;
    else
      cout << -1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
// fahadmd16(IIEST Shibpur)
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;

#define ll long long
#define pb push_back
#define pf push_front
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define db double
#define pll pair<ll, ll>
#define ALL(a) (a).begin(),(a).end()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define forn(i, n) for (ll i = 0; i < n; i++)
#define forn1(i, n) for (ll i = 1; i < n; i++)
#define forab(i,a,b) for(ll i=a;i<b;i++)
#define clr(x) memset(x, 0, sizeof(x))
#define count_bit(x) __builtin_popcount(x)
#define endl "\n"
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
#define eps 1e-10
#define nedl endl
const ll sz = 1001;
const ll mod = 1e9 + 7;
typedef vector<ll> VL;
typedef vector<pll > VLL;
typedef vector<vector<ll> > VVL;

ll power(ll n, ll k, ll m) {
    ll ans = 1;
    while (k) {
        if (k & 1)ans = (ans * n) % m;
        k /= 2;
        n = (n * n) % m;
    }
    return ans;
}


int main() {
    IOS;

    ll T = 1; //cin >> T;
    while (T--) {
        ll n,m;cin>>n>>m;
        ll a[n],sum=0;
        forn(i,n){cin>>a[i];sum+=a[i];}
        sort(a,a+n,greater<ll>());
        ll xx=sum/(4*m);
        if(sum %(4*m) != 0)xx++;
        bool f=1;
        forn(i,m){
			if(a[i] < xx){
				f=0;
				break;
			}
		}
		if(f)cout<<"Yes\n";
		else cout<<"No\n";
		

		
		
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	int a,b;
	cin>>a>>b;
	if(a>=13){
		cout<<b<<endl;
	}else if(a>=6 && 12>=a){
		cout<<b/2<<endl;
	}else if(a<=5){
		cout<<0<<endl;
	}
	return 0;

}


Measured memory_bytes: 256
/* ex_6-2. nknm */

#include <stdio.h>
#include <string.h>

int main(void){
    
    int word_num, i;
    char imput[100];

    scanf("%s", imput);

    word_num = strlen(imput);

    printf("%c%d%c\n", imput[0], word_num - 2, imput[word_num - 1]);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  bool prime[60000];
  for(int i=0;i<60000;++i) prime[i] = true;
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<60000;++i) {
    if(!prime[i]) continue;
    for(int j=2;i*j<60000;++j) prime[i*j] = false;
  }
  int N;
  cin>>N;
  int num = 0;
  for(int i=0;i<60000;++i) {
    if(prime[i] && i%5==1) {
      cout<<i<<" ";
      num++;
    }
    if(num==N) break;
  }
}



Measured memory_bytes: 3668
#include <bits/stdc++.h>
#include <limits>
using namespace std;
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define lli long long int
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define um unordered_map
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define mem(data_structure, val) memset(data_structure, val, sizeof(data_structure))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define endl "\n"
const ll mod = 1e9+7;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef vector<int>		vi;
typedef vector<ll>		vll;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<vi>		vvi;
typedef vector<vll>		vvll;

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 
um<pii, int, hash_pair> map_with_pair{};
priority_queue <int, vector<int>, greater<int> > pq_desc; // decreasing order

bool cmp(lli a, lli b) {
	return a>b;
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	lli n;
	cin >> n;
	lli a[n];
	lli sort_a[n];
	fo(i, n) {
		cin >> a[i];
		sort_a[i] = a[i];
	}

	sort(sort_a, sort_a+n, cmp);

	fo(i, n) {
		if(sort_a[0] == a[i]) cout << sort_a[1] << endl;
		else cout << sort_a[0] << endl;
	}

	return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;

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

	ll N;
	cin >> N;
	vector<ll> a(N+1,0);
	ll ans = 0;
	FOR(i,1,N+1){
		cin >> a[i];
		if(a[i]<i)if(a[a[i]]==i)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int total = 0;
		if (n <= k) {
			for (int i = 0; i < n; i++) {
				total += x;
			}
			System.out.println(total);
		} else {
			for (int i = 0; i < k; i++) {
				total += x;
			}
			for (int i = k; i < n; i++) {
				total += y;
			}
			System.out.println(total);
		}
	}
}


Measured memory_bytes: 9552
# include <bits/stdc++.h>
# define FILE

using namespace std;

int main(){

    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    int n, k;
    cin >> n >> k;
    int r, s, p;
    cin >> r >> s >> p;
    string ss;
    cin >> ss;
    int dp[n][3] = {};
    for( int i = 0; i < n; i ++ ){
    	if( i >= k ){
    		dp[i][0] = dp[i][1] = dp[i][2] = max( {dp[i-k][0], dp[i-k][1], dp[i-k][2]} );
    	}
    	if( ss[i] == 'r' ){
    		if( i < k ){
    			dp[i][1] = p;
    		}
    		else{
    			dp[i][1] = max( dp[i-k][0], dp[i-k][2] ) + p;
    		}
    	}
    	if( ss[i] == 'p' ){
    		if( i < k ){
    			dp[i][2] = s;
    		}
    		else{
    			dp[i][2] = max( dp[i-k][0], dp[i-k][1] ) + s;
    		}
    	}
    	if( ss[i] == 's' ){
    		if( i < k ){
    			dp[i][0] = r;
    		}else{
    			dp[i][0] = max( dp[i-k][1], dp[i-k][2] ) + r;
    		}
    	}
    }
    int ans = 0;
    for( int i = n-1; i >= n-k; i -- )
    	ans += max( {dp[i][0], dp[i][1], dp[i][2]} );
    cout << ans;
    return 0;
}	




Measured memory_bytes: 1664
n=int(input())
t,a=map(int, input().split())
H=list(map(int, input().split()))
T=[0 for i in range(len(H))]
for i in range(len(H)):
    T[i]=abs(t-0.006*H[i]-a)
print(T.index(min(T))+1)

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

int main(int argc, char* argv[]) {
  using std::cin;
  using std::cout;
  using std::string;

  int n;
  cin >> n;

  double result = 0;

  for (int i = 0; i < n; i++) {
    double v;
    string currency;

    cin >> v;
    cin >> currency;

    if (currency == "BTC") {
      v *= 380000.0;
    }
    result += v;
  }

  cout << result;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, t; cin >> n >> t;
	double ans = 0;
	for (int i = 0; i < n; i++) {
		int x, h; cin >> x >> h;
		ans = max(ans, (double)(h*t) / x);
	}
	printf("%.10f\n", ans);
}


Measured memory_bytes: 3224
import scala.io.Source

object Main extends App {
  val List(nStr, xsStr) = Source.stdin.getLines().toList
  val n: Int = n.toInt
  val xs: List[Int] = xsStr.split(' ').map(_.toInt).toList
  
  val isDenied = xs.exists { x =>
    x % 2 == 0 && !(x % 3 == 0 || x % 5 == 0)
  }
  
  if (isDenied)
    println("DENIED")
  else
  	println("APPROVED")
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
using ll = long long;
constexpr ll INF = 1000000000;

using namespace std;

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	long long g = gcd(a, b);
	return a / g * b;
}

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

	vector<ll>t(n);
	rep(i, n)cin >> t[i];

	ll lc = t[0];
	for (ll i = 1; i < n; i++) {
		lc = lcm(lc, t[i]);
	}
	cout << lc << endl;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val X = readInputLine().toInt()
    
    if (X < 100) {
        println(0)
        return
    }

    if (X % 100 <= X / 100 * 5) {
        println(1)
    } else {
        println(0)
    }
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 33728
#include <iostream>

using namespace std;

int main()
{
    int x,y;
    cin>>x>>y;
    int a=x+y;
    int b=x-y;
    int c=x*y;
    if (a>=b & a>=c){
        cout<<a;
    }
    else if (b>=a & b>=c){
        cout<<b;
    }
    else{
        cout<<c;
    }

    return 0;
}



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

int n, m;

class DisjointSet{
  public:
    vector<int> rank, p;

    DisjointSet(){}
    DisjointSet(int size){
        rank.resize(size, 0);
        p.resize(size, 0);
        for(int i = 0; i < size; i++) makeSet(i);
    }

    void makeSet(int x){
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y){
        return findSet(x) == findSet(y);
    }
    
    bool unite(int x, int y){
        link(findSet(x), findSet(y));
    }

    void link(int x, int y){
        if(rank[x] > rank[y]){
            p[y] = x;
        }else{
            p[x] = y;
            if(rank[x] == rank[y]){
                rank[y]++;
            }
        }
    }

    int findSet(int x){
        if(x != p[x]){
            // path compression
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};

struct bridge{
    int from, to, cost;
    bridge(int f, int t, int c) : from(f), to(t), cost(c) {}
    bool operator<(const bridge other) const{
        return cost < other.cost;
    }
};

int main(){
    while(1){
        cin >> n >> m;
        if(n+m == 0)  break;

        DisjointSet uf(n);
        int a, b, c;
        vector<bridge> vb; 
        for(int i = 0; i < m; i++){
            cin >> a >> b >> c;
            vb.push_back(bridge(a,b,c));
        }

        sort(vb.begin(), vb.end());

        int ans = 0;
        for(bridge b : vb){
            if(uf.same(b.from, b.to))   continue;

            ans += b.cost;
            uf.unite(b.from, b.to);
        }

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


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

const static int MAX = 100000;

int n, A[MAX+1], L[MAX];

int lis(){
    L[0] = A[0];
    int length = 1;

    for(int i = 1; i < n; i++){
        if(L[length-1] < A[i]){
            L[length++] = A[i];
        }else{
            std::sort(L, L + length);
            auto j = std::lower_bound(L, L + length, A[i]);
            *j = A[i];
        }
    }
    
    return length;
}

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

    std::cout << lis() << std::endl;

    return 0;
}


Measured memory_bytes: 3924
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int h, w, f[100][100];
string s[100];
const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};

void dfs(int y,int x,char c){
	int i;
	f[y][x] = 1;
	for(i = 0;i < 4;i++){
		if(y + dy[i] >= 0 && y + dy[i] < h && x + dx[i] >= 0 && x + dx[i] < w && c == s[y + dy[i]][x + dx[i]] && !f[y + dy[i]][x + dx[i]]){
			dfs(y + dy[i],x + dx[i],c);
		}
	}
}


int main(void){
	int i, j, ans;
	while(1){
		cin >> h >> w;
		if(h == 0 && w == 0) break;
		ans = 0;
		scanf("%*c");
		for(i = 0;i < h;i++){
			getline(cin,s[i]);
			for(j = 0;j < w;j++)
				f[i][j] = 0;
		}
		for(i = 0;i < h;i++){
			for(j = 0;j < w;j++){
				if(!f[i][j]){
					dfs(i,j,s[i][j]);
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 2072
import java.util.*;
class Main{
    public static void main(String[] args){
	Scanner stdIn = new Scanner(System.in);
	char[][] C =new char[3][3];
	String[] S=new String[3];
	for(int i=0;i<3;i++){
	    S[i]=stdIn.next();
	}
	System.out.print(S[0].charAt(0));
	System.out.print(S[1].charAt(1));
	System.out.print(S[2].charAt(2));
	System.out.println();
    }
}


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

int main() {
  string s,t;
  cin >> s;
  t = s;
  int count=0;
  for(int i=0;i<s.size();i++){
  	s.at(i) = t.at(s.size()-1-i);
  }
  for(int i=0;i<s.size();i++){
  	if( s.at(i) != t.at(i) ){
      count++;
    }
  }
  cout << count/2 << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)


def dfs(u, c):
    color[u] = c
    for v in g[u]:
        if color[v] != -1:
            if color[v] == c:
                return False
        else:
            if not dfs(v, c ^ 1):
                return False
    return True


n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

flag = True
color = [-1] * n
for i in range(n):
    if color[i] == -1:
        if not dfs(i, 0):
            flag = False
            break
if flag:
    w = color.count(0)
    ans = w * (n - w) - m
else:
    ans = (n * (n - 1) // 2 - m)
print(ans)

Measured memory_bytes: 31060