akhauriyash/Code-Regression huggingface dataset:
#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 INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  string S,T;
  cin >> S >> T;
  int flag2 = 0;
  vector<string> A;
  REP(i,S.size()-T.size()+1){
    int flag=0;
    REP(j,T.size()){
      if(S.at(i+j)!='?'&&S.at(i+j)!=T.at(j)){
        flag=1;
      }     
    }
    if(flag==0){
      flag2=1;
      string U=S;
      REP(j,T.size()){
        U.at(i+j)=T.at(j);
      }
      A.push_back(U);
    }
  }
  if(flag2==0){
    cout << "UNRESTORABLE" << endl;
  }else{
    REP(i,A.size()){
      REP(j,A.at(i).size()){
        if(A.at(i).at(j)=='?'){
          A.at(i).at(j)='a';
        }
      }
    }
    sort(ALL(A));
    cout << A.at(0) << endl;
  }
}

Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

int main() {
  int H, W;
  scanf("%d %d", &H, &W);

  char alph[26]={};
  for (int i=0; i<H; ++i) {
    for (int j=0; j<W; ++j) {
      char ch;
      scanf(" %c", &ch);
      (++alph[ch-'a']) %= 4;
    }
  }

  int one, two;
  if (H % 2) {
    if (W % 2) {
      one = 1;
      two = H + W - 2;
    } else {
      one = 0;
      two = W;
    }
  } else {
    if (W % 2) {
      one = 0;
      two = H;
    } else {
      one = 0;
      two = 0;
    }
  }

  for (int i=0; i<26; ++i) {
    //fprintf(stderr, "%c: %d\n", 'a'+i, alph[i]);
    if (alph[i] % 2 == 1) {
      if (--one < 0)
        return !printf("No\n");

      alph[i] -= 1;
    }

    if (alph[i] == 2) {
      if ((two -= 2) < 0)
        return !printf("No\n");
    }
  }

  printf("Yes\n");
  return 0;
}


Measured memory_bytes: 128
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;

#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_end().to_owned()
}

const M: usize = 998244353;
fn main() {
    let (n, m, k) = read!(usize, usize, usize);
    let b = {
        let mut tmp = vec![0; k+1];
        tmp[0] = pow_mod(m-1, n-1-k, M);
        for i in 1..k+1 {
            tmp[i] = (tmp[i-1] * (m-1)) % M;
        }
        tmp
    };

    let c = {
        let mut tmp = vec![1; k+1];
        for i in 1..k+1 {
            tmp[i] = (((tmp[i-1] * (n-i)) % M) * pow_mod(i, M-2, M)) % M;
        }
        tmp
    };

    let ans_per_m = b.iter().rev().zip(c.iter()).fold(0usize, |acc, (eb, ec)| (acc + eb * ec) % M);
    println!("{}", (ans_per_m * m) % M);    
}

/// a.pow(b) mod m
fn pow_mod(a: usize, mut b: usize, m: usize) -> usize {
    let mut t = a;
    let mut ans = 1;
    while b != 0 {
        if (b & 1) != 0 {
            ans = (ans * t) % m;
        }
        b >>= 1;
        t = (t * t) % m;
    }
    ans
}

Measured memory_bytes: 5108
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  string S;
  
  int count;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> S;
    if(S == "Y"){
      count++;
    }
  }
  
  if(count > 0){
    cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
}
  
  

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n,m,X,Y; cin >> n >> m >> X >> Y;
    vector<int> x(n), y(m);
    int maxx = -100, miny = 100;
    rep(i,n) {
        cin >> x[i];
        maxx = max(maxx, x[i]);
    }
    rep(i,m) {
        cin >> y[i];
        miny = min(miny, y[i]);
    }
    for (int z = X+1; z <= Y; z++)
    {
       if (maxx < z && miny >= z)
       {
           cout << "No War\n";
           return 0;
       }
    }
    cout << "War\n";
    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)
typedef long long ll;
 
int main(void){
    int n;
    cin>>n;
    rep(i,n){
        ll a,b;
        cin>>a>>b;
        ll mul = a*b;
        if(mul == 4 && a!=2){
            cout<<1<<endl;
        }else{
            ll root = sqrt(mul);
            if(root*(root+1) < mul){
                cout<<root*2 - 1<<endl;    
            }else if(root*root == mul && a!=b){
                cout<<root*2 - 3<<endl;
            }else{
                cout<<root*2 - 2<<endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
/* ***********************************************
Author        :yang12138
Created Time  :2017/10/19 7:50:10
File Name     :D.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;

const int N = 55;
const ll INF=4e18+100;

pii a[N];
int x[N],y[N];

void solve(){
	int n,cnt;
	cin>>n>>cnt;
	for(int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
		x[i]=a[i].first;
	}
	sort(x+1,x+n+1);
	
	ll ans=INF;
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int tot=0;
			for(int k=1;k<=n;k++){
				if(a[k].first>=x[i] && a[k].first<=x[j]){
					y[++tot]=a[k].second;
				}
			}
			if(tot<cnt) continue;
			sort(y+1,y+tot+1);
			for(int k=1;k<=tot+1-cnt;k++){
				ans=min(ans,1LL*(x[j]-x[i])*(y[k+cnt-1]-y[k]));
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define vii vector<pair<int,int> >
#define vi vector<ll>
#define ll long long
#define rep(i,a,b) for(i=a;i<=b;i++)
#define inf 100000000000000000

using namespace std;

ll N,W;
ll w[101],v[101];
ll dp[100001][101];

ll f(ll x, int id)
{
    if(id==N) return 0;
    if(x<=0) return 0;
    if(dp[x][id]!=-1) return dp[x][id];
    if(x>=w[id])
    {
        dp[x][id]=max(v[id]+f(x-w[id],id+1),f(x,id+1));
    }
    else{
        dp[x][id]=f(x,id+1);
    }
    return dp[x][id];
}

int main()
{
    cin>>N>>W;
    for(int i=1;i<=W;i++)
    {
        for(int j=0;j<N;j++)
        {
            dp[i][j]=-1;
        }
    }
    for(int i=0;i<N;i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<f(W,0)<<endl;
    return 0;
}

Measured memory_bytes: 79104
import sys

H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]

hw.sort()

hcnt = [0] * (H+1)
wcnt = [0] * (W+1)

target = []
for i, j in hw:
    hcnt[i] += 1
    wcnt[j] += 1
    target.append([str(i) + " " + str(j),1])

d = dict(target)

hlist = []
hmax = -1
for i in range(1,H+1):
    if hmax < hcnt[i]:
        hlist = [i]
        hmax = hcnt[i]
    elif hmax == hcnt[i]:
        hlist.append(i)

wlist = []
wmax = -1
for i in range(1,W+1):
    if wmax < wcnt[i]:
        wlist = [i]
        wmax = wcnt[i]
    elif wmax == wcnt[i]:
        wlist.append(i)

if len(hlist) * len(wlist) > M:
    print(hmax + wmax)
    sys.exit()

idx = 0
for h in hlist:
    for w in wlist:
        while h > hw[idx][0] or w > hw[idx][1]:
            idx += 1
            if idx == M:
                print(hmax + wmax)
                sys.exit()                
            if h == hw[idx][0] and w == hw[idx][1]:
                break
        if h < hw[idx][0] or w < hw[idx][1]:
            print(hmax + wmax)
            sys.exit()
        
print(hmax + wmax - 1)


Measured memory_bytes: 148092
a=int(input())
b=int(input())
c=int(input())
x=int(input())
ans= 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      s = 500*i + 100*j + 50*k
      if s==x:
        ans+=1
print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    int n;
    bool s[200][200];
    char c;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c;
            s[i][j]=c=='1';
        }
    }
    int ans=-1;
    for(int i=0;i<n;i++){
        bool used[200];
        for(int j=0;j<n;j++)
            used[j]=false;
        vector<vector<int>>v{{i}};
        used[i]=true;
        int cnt=1;
        bool ok=true;
        while(cnt<n){
            vector<int>nv;
            for(int j=0;j<v.back().size();j++){
                for(int k=0;k<n;k++){
                    if(s[v.back()[j]][k]&&!used[k]){
                        nv.push_back(k);
                        used[k]=true;
                        cnt++;
                    }
                }
            }
            for(int j=0;j<nv.size();j++)
                for(int k=0;k<j;k++)
                    if(s[nv[j]][nv[k]])
                        ok=false;
            v.push_back(nv);
        }
        if(ok)
            ans=max(ans,(int)v.size());
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>

#define INF 10000

using namespace std;

short int moves[20000000];

int ID[8];

int ID_to_int(int id[8]){
	int ref = 0;
	for(int i = 0; i < 8; i++){
		ref *= 8;
		ref += id[i];
	}
	return ref;
}

void int_to_ID(int id[8], int num){
	int dummy = num;
	for(int i = 0; i < 8; i++){
		id[7 - i] = dummy % 8;
		dummy /= 8;
	}
	return;
}

int main(){
	
	for(int i = 0; i < 20000000; i++){
		moves[i] = INF;
	}
	
	for(int i = 0; i < 8; i++){
		ID[i] = i;
	}
	moves[ID_to_int(ID)] = 0;
	
	int count = 0;
	
	for(int loop = 0; loop < 20; loop++){
		count = 0;
		sort(ID, ID + 8);
		do{
			int i = ID_to_int(ID);
			//cout << i << " ";
			if(moves[i] < INF){
				
				count++;
				
				for(int j = 0; j < 8; j++){
					if(ID[j] == 0){
						swap(ID[j], ID[(j + 4) % 8]);
						moves[ID_to_int(ID)] = min(int(moves[ID_to_int(ID)]), moves[i] + 1);
						swap(ID[j], ID[(j + 4) % 8]);
						if(j % 4 != 0){
							swap(ID[j], ID[j - 1]);
							moves[ID_to_int(ID)] = min(int(moves[ID_to_int(ID)]), moves[i] + 1);
							swap(ID[j], ID[j - 1]);
						}
						if(j % 4 != 3){
							swap(ID[j], ID[j + 1]);
							moves[ID_to_int(ID)] = min(int(moves[ID_to_int(ID)]), moves[i] + 1);
							swap(ID[j], ID[j + 1]);
						}
					}
				}
			}
		}while(next_permutation(ID, ID + 8));
		//cout << count << endl;
	}
	
	while(true){
		
		for(int i = 0; i < 8; i++){
			cin >> ID[i];
		}
		
		if(cin.eof()){
			break;
		}
		
		cout << moves[ID_to_int(ID)] << endl;
		
	}
	return 0;
}

Measured memory_bytes: 42116
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int main(){
  vector<int> ar;
  int g[]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
  int n;
  while(cin >> n){
    for(int i=9;i>=0;i--){
      if(n>=g[i]){
	n -= g[i];
	ar.push_back( g[i] );
      }
    }
    for(int i=ar.size()-1;i>=0;i--){
      if(i != 0)cout << ar[i] << ' ';
      else cout << ar[i] << endl;
    }
    ar.clear();
  }
}

Measured memory_bytes: 1216
//58
#include<iostream>
#include<cmath>
#include<iomanip>

using namespace std;

int main(){
  for(double q;cin>>q,q!=-1;){
    double x=q/2;
    while(q!=0&&!(fabs(x*x*x-q)<0.00001*q)){
      x=x-(x*x*x-q)/3/x/x;
    }
    cout<<fixed<<setprecision(6)<<x<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,r;
    cin>>n>>r;
    double log1=log10(n);
    double log12=log10(r);
    int temp=log1/log12;
    int ans=temp+1;
    cout<<ans;
    return 0;
}







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

const int N = 1000 + 10;
ll a[N], b[N * N], sum[N];

int x;

bool cmp(ll a, ll b) { return ((a >> x) & 1) > ((b >> x) & 1); }

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    int nn = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
        {
            b[nn++] = sum[j] - sum[i - 1];
            // cout<<b[nn - 1]<<" ";
        }
    // cout<< endl;
    // cout<<nn<<endl;
    ll ans = 0;
    for (x = 50; x >= 0; x--)
    {
        sort(b, b + nn, cmp);

        int cnt = 0;
        for (int i = 0; i < nn; i++)
            if ((b[i] >> x) & 1)
                cnt++;

        if (cnt < k)
            ans <<= 1;
        else
        {
            ans <<= 1;
            ans++;
            nn = cnt;
        }
    }
    printf("%lld", ans);
}

Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,x,ans,cnt[200005],s;
string st;
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>x;
		cnt[x]++;
	}
	for (i=0;i<=200000;i++)
	{
		s=0;
		if (i) s+=cnt[i-1];
		ans=max(ans,s+cnt[i]+cnt[i+1]);
	}
	cout<<ans;
	return 0;
}

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

int main() {
  int N;
  int ans = 0;  
  int temp = 0;
  
  cin >> N;

  vector<int> score(N);
  
  for(int i=0;i<N;i++)
  {
    cin >> score[i];
  }
  
  for(int i=0;i<N;i++)
  {
    for(int j = N-1;j>i;j--)
    {
      if(score[j] < score[j-1])
      {
        temp = score[j];
        score[j] = score[j-1];
        score[j-1] = temp;
      }     
    }
  } 
  
    for(int i= N-1;i>=0;i--)
    {
      if(i%2 == 0)
   		{
      	ans = ans + score[i];
    	}
    	else
    	{
      	ans = ans - score[i];
    	}
    }
  cout << abs(ans) << endl;

}


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

#define REP(i,n) for(int i = 0; i < n; i++)
#define MOD 1000000007

int main(int argc, char const *argv[]) {
  int x,y;
  cin >> x >> y;
  bool fugox = true;
  bool fugoy = true;
  if(x < 0) fugox = false;
  if(y <= 0) fugoy = false;
  int absx = abs(x);
  int absy = abs(y);
  if(fugox && fugoy){//両方正
    if(y - x >= 0){
      cout << y-x << endl;
    }else{
      cout << x-y+2 << endl;
    }
  }else if(fugox && !fugoy){
    if(absy >= absx){
      cout << absy-absx+1 << endl;
    }else{
      cout << absx-absy+1 << endl;
    }
  }else if(!fugox && fugoy){
    if(absy >= absx){
      cout << absy-absx+1 << endl;
    }else{
      cout << absx-absy+1 << endl;
    }
  }else{//両方負
    if(absy > absx){
      cout << absy-absx+2 << endl;
    }else{
      cout << absx-absy << endl;
    }
  }
}


Measured memory_bytes: 888
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=a-1;i>=n;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=5e5+10,oo=0x3f3f3f3f,MOD=1e9+7;
const double PI = acos(-1);

void solve(){
    ll a,b,x;
    cin>>a>>b>>x;
    cout<<b/x-a/x+(a%x==0)<<Endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();

}


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

typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define SYAMU(a) memset(a,0,sizeof(a))

const ll MOD = 1e9 + 7;
const int M = 200009;
int h,w,a,b;
ll f[M];
ll inv[M];

void init() {
    SYAMU(f); SYAMU(inv);
}

// ari114
ll mod_pow(ll x, ll n) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

ll nCk(ll n, ll k) {
    return f[n] * inv[k] % MOD * inv[n-k] % MOD;
}

int main() {
    while(cin>>h>>w>>a>>b) {
        init();
        f[0] = inv[0] = 1;
        for(int i=1; i<=h+w; i++) {
            f[i] = i * f[i-1] % MOD;
            inv[i] = mod_pow(f[i], MOD-2);
        }

        ll ans = 0;
        rep(i, h-a) {
            ans = (ans + nCk(b-1+i, i) * nCk(w-b-1 + h-1-i, w-b-1)) % MOD;
        }

        cout << ans % MOD << "\n";
    }

    return 0;
}

Measured memory_bytes: 3328
# 2020年6月17日

# 修行という概念がない場合、消化コストを大から小に並べて食べにくさを小から大に並べて順にマッチングさせれば良い。
# そうでない状態から2つを交換したときに最大値が下がる方向にしか行かないため。

# 修行をするなら最大値を引き下げるところに修行をするのが最適なので、
# 無修行状態の結果を優先度付きキューに入れる→K回最大値を取り出してコストを引いて再投入→を繰り返す。
# 本当か? やってるうちに最適な組み合わせが変わらないか? →変わらない。食べにくさを昇順に並べたときに消化コストが降順になるのが最善手なので。
# あとKが大きいのでこれだと間に合わない。

# 決め打ち二分探索か?
# あ、それだわ。

n, k = map(int, input().split())
people = list(map(int, input().split()))
foods = list(map(int, input().split()))

# 食べにくさは昇順（小から大）、人間は降順（大から小）
foods.sort()
people.sort(reverse=True)

def is_valid(time):
    # k回以下の修行で実現可能か

    n_train = 0
    for i in range(n):
        if foods[i] * people[i] <= time:
            pass
        else:
            n_train += people[i] - time // foods[i]
    
    return n_train <= k


time_ok = 2 * 10 ** 12
time_ng = -1  # 計算上、is_valid(-1) = Trueになることはあるが、二分探索の方法から言ってこれで正しいはず

while (abs(time_ok - time_ng > 1)):
    mid = (time_ok + time_ng) // 2
    if is_valid(mid):
        time_ok = mid
    else:
        time_ng = mid

print(time_ok)


Measured memory_bytes: 113552
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long
   // #define ll unsigned long long
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    #define be begin()
    #define en end()
    #define le length()
    #define all(x) (x).begin(), (x).end()
    #define rep(i, n) for (ll i = 0; i < n; i++)
    #define repo(i, n) for (ll i = 1; i <= n; i++)
    #define fastIO                        \
        ios_base::sync_with_stdio(false); \
        cin.tie(NULL);                    \
        cout.tie(NULL)
    #define eps 1e-6
    #define pi 3.141592653589793
    #define c(a) cout << a << "\n";
    #define ao(a)        \
        for (auto i : a) \
            cout << i << " ";
    #define endl '\n'        
    typedef vector<int> vii;
    typedef vector<ll> vll;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    const int MOD = 1e9 + 7;
    const int INF = 1e9;
    const int N = 1e6 + 6;

    ll powmod(ll a, ll b, ll mod)
    {
        ll res = 1;
        a %= mod;
        for (; b; b >>= 1)
        {
            if (b & 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
        }
        return res;
    }

    ll gcd(ll a, ll b)
    {
        while (b > 0)
        {
            ll t = a % b;
            a = b, b = t;
        }
        return a;
    }

    ll lcm(ll a, ll b)
    {
        return (a / gcd(a, b)) * b;
    }

    ll is_prime(ll n)
    {
        if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
            return 0;
        for (ll i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
            if (n % i == 0)
                return 0;
        return 1;
    }
    // long long bit[1000005], a[1000005];
    // ll N1 = 200005;

    // void update(int x, int del)
    // {
    //     for (; x <= N1; x += x & -x)
    //     {
    //         bit[x] += del;
    //     }
    // }

    // int query(int x)
    // {
    //     int sum = 0;
    //     for (; x > 0; x -= x & -x)
    //     {
    //         sum += bit[x];
    //     }
    //     return sum;
    // }
    /*************************************************************************************************************/
    int main(){
      ll n;
      cin>>n;
      vector<pair<string,ll>> v;
      rep(i,n){
          string s;
          ll x;
          cin>>s>>x;
          v.pb(mp(s,x));
      }
      string s1;
      cin>>s1;
      ll ans=0,l=0;
      rep(i,n){
          if(l==1) ans+=v[i].se;
          if(v[i].fi==s1) l=1;
          
      }
      c(ans)
        return 0;
    }
        



 

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.StringTokenizer;

public class Main  implements Runnable {
	int[][] ta = new int[16][4096];
	int ptr = 0;
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 64 * 1024 * 1024).start();
    }

    public void run() {
    	FastScanner sc = new FastScanner(System.in);
    	//int[] ar = new int[3];
    	//ar[0]=Integer.parseInt(sc.next());
    	//Arrays.parallelSort(ar);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		//long a = Long.parseLong(sc.next());
		//String s = sc.next();
		//String str = sc.next();
		//char c[] = str.toCharArray();
		//char a[][] = new char[n];
		//ArrayList<Str_4> lists = new ArrayList<Str_4>();
		//lists = new ArrayList;
		PrintWriter out = new PrintWriter(System.out);
		//int[] ra = new int[r];
		//ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
		if(a - b > c)
		{
			out.println(0);
		}
		else
		{
			out.println(c-a+b);
		}
		
		//out.println(a[5]);
		out.flush();
    }

    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
        public FastScanner(String in) {
        	StringReader sr = new StringReader(in);
            reader = new BufferedReader(new BufferedReader(sr));
            tokenizer = null;
        }
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long nextInt() {
            return Integer.parseInt(next());
        }

    }
}

Measured memory_bytes: 25044
#include <stdio.h>
int main(void) {
	int m, f, r, mf;

	while (1) {
		scanf("%d %d %d", &m, &f, &r);
		if (m < 0 && f < 0 && r < 0)
			break;
		mf = m + f;
		if (m < 0 || f < 0 || mf < 30)
			puts("F");
		else if (mf >= 80)
			puts("A");
		else if (mf >= 65)
			puts("B");
		else if (mf >= 50 || r >= 50)
			puts("C");
		else
			puts("D");
	}
	return 0;
}

Measured memory_bytes: 584
/*================================================================
*   Copyright (C) 2019 Sangfor Ltd. All rights reserved.
*
*   创 建 者： badcw
*   创建日期： 2020/1/26
*
================================================================*/
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn = 1e3+50;
const int mod = 1e9+7;
ll qp(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

template <class T>
inline bool scan(T& ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0; // EOF
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}

//template <class T>
//inline void out(T x) {
//    if (x > 9) out(x / 10);
//    putchar(x % 10 + '0');
//}

int main(int argc, char* argv[]) {
    ll s;
    int n;
    cin >> s >> n;
    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        sum += x;
    }
    puts(sum >= s ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef vector <int> vi;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f|=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=1000005,mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int n;
int Fac[N],Inv[N];
void prework(){
	int n=N-1;
	for (int i=Fac[0]=1;i<=n;i++)
		Fac[i]=(LL)Fac[i-1]*i%mod;
	Inv[n]=Pow(Fac[n],mod-2);
	Fod(i,n,1)
		Inv[i-1]=(LL)Inv[i]*i%mod;
}
int C(int n,int m){
	if (m>n||m<0)
		return 0;
	return (LL)Fac[n]*Inv[m]%mod*Inv[n-m]%mod;
}
int a[N];
int main(){
	prework();
	n=read();
	For(i,1,n-1)
		a[i]=(LL)Fac[i]*Fac[n-1-i]%mod*C(i-1,n-i-1)%mod;
	int ans=0;
	Fod(i,n-1,1){
		Del(a[i],a[i-1]);
		Add(ans,(LL)a[i]*i%mod);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 11904
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>

using namespace std;
int main(){
    
    int N,K;
    set<int> snuck;
    cin >> N >> K;
    int d;
    int num;
    while(K--){
        cin >> d;
        for(int i =0;i<d;i++)
        {
            cin >> num;
            snuck.insert(num);
        }
        
    }
    cout << N - snuck.size() << "\n";
    
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
int main()
{
    char ch;
    int counter[26] = {};
    while (cin >> ch)
    {
        if (isalpha(ch))
        {
            if (islower(ch)){
                counter[ch - 'a']++;
            }
            else if (isupper(ch)){
                counter[ch - 'A']++;
            }
        }
    }
    for (int i = 0; i < 26; i++)
    {
        printf("%C : %d\n", i+'a', counter[i]);
    }
    
    return 0;
}


Measured memory_bytes: 3144
#include<iostream>
using namespace std;
int main(){
    int a,b,min=1000000,max=-1000000;
    long long s=0;
    cin >>a;
    for(int i=0;i<a;i++){
        cin >>b;
        if(b>max)
            max=b;
        if(b<min)
            min=b;
        s+=b;
    }
    cout  <<min<<" "<<max<<" "<<s<<endl;
    return 0;
}

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

int main(){
	string s;
	cin >> s;
	int a = 0, z = s.size() - 1;
	while (s.at(a) != 'A') a++;
	while (s.at(z) != 'Z') z--;
	cout << z - a + 1 << endl;
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
     cin>>s;

       int A_s=0,B_s=0;

        for(int i=0;i<=2;i++)
        {
           if(s[i]=='A')
            A_s++;

            else
            B_s++;
        }
       if(A_s > 0 && B_s > 0)
         cout<<"Yes";

         else
         cout<<"No";
}


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

#define inRange(x, a, b) a <= x && x < b
typedef long long ll;

int dx[9] = {-1,-1,-1,0,0,1,1,1};
int dy[9] = {1,0,-1,1,-1,1,0,-1};

int main(){
    int h, w, n, a, b;

    cin >> h >> w >> n;

    map<pair<int,int>, int> m;
    
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        a--;
        b--;
        for(int j = 0; j < 9; j++){
            int na = a + dx[j];
            int nb = b + dy[j];
            if(inRange(na, 1, h-1) && inRange(nb, 1, w-1)){
                m[{na,nb}]++;
            }
        }
    }

    ll cnt[10] = {};
    for(auto x : m){
        cnt[x.second]++;
    }

    cnt[0] = ll(h-2) * (w-2) - accumulate(cnt, cnt+10, 0ll);

    for(ll x : cnt)    cout << x << endl;
    
    return 0;
}

Measured memory_bytes: 56448
#include <bits/stdc++.h>
using namespace std;
template<class T> struct rge { T b, e; };
template<class T> rge<T> range(T i, T j) { return rge<T>{i, j}; }
struct debug {
#ifdef LOCAL
	~debug(){cerr<<endl;}
	template<class T> debug& operator<<(T x){cerr<<boolalpha<<x; return *this;}
	template<class B, class C> debug& operator<<(pair<B, C> x){return *this<<"("<<x.first<<", "<<x.second<<")";}
	template<class T> debug& operator<<(rge<T> x){*this<<"[";for(auto it=x.b;it!=x.e;it++){*this<<", "+2*(it==x.b)<<*it;}return *this<<"]";}
	template<class T> debug& operator<<(vector<T> x){ return *this<<range(x.begin(),x.end());}
#else
	template<class T> debug& operator <<(const T&){return *this;}
#endif
};
#define nav(...) << "[ " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " ] "
using ll = long long;


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

    int n, m;
    cin >> n >> m;
    if(n % 2 == 1) {
        for(int i = 0; i < m; i++) {
            int a = i+1, b = n - i;
            cout << a << ' ' << b << '\n';
        }
    }
    else {
        int odd = (m+1)/2;
        for(int i = 1; i <= odd; i++) {
            cout << i << ' ' << n-i+1 << '\n';
        }
        for(int i = odd+1; i <= m; i++) {
            cout << i << ' ' << n-i << '\n';
        }
    }
}


Measured memory_bytes: 3664
import numpy as np

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

MOD = 10 ** 9 + 7

dp = np.zeros((N + 1, K + 1), dtype=np.int64)
dp[0][0] = 1
for i in range(1, N + 1):
    S = np.cumsum(dp[i - 1]) % MOD
    dp[i][:A[i - 1] + 1] = S[:A[i - 1] + 1] % MOD
    dp[i][A[i - 1] + 1:K + 1] = (S[A[i - 1] + 1:K + 1] - S[:K - A[i - 1]]) % MOD
print(dp[N][K])


Measured memory_bytes: 92968
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define all(n) n.begin(),n.end()
#define yn(x) cout << (x ? "Yes":"No") << endl;

int main() {
  int n;
  cin >> n;
  vector<int>d(n);
  rep(i,n) cin >> d[i];
  int sum = 0, sum1 = 0;
  rep(i,n) rep(j,n){
    sum += d[i]*d[j];
  }
  rep(i,n) sum1 += d[i]*d[i];
  cout << (sum-sum1)/2 << endl;
  return 0;
}


Measured memory_bytes: 256
import sys

def get_revstr(s):
    s_len = len(s)
    
    if s_len == 1:
        return s
    else:
        return s[-1] + get_revstr(s[:-1])
    
def main():
    s = sys.stdin.readline().strip()
    rev_s = get_revstr(s)
    print(rev_s)

if __name__ == '__main__':
    main()
    

Measured memory_bytes: 7568
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    size_t n;
    string s, t;
    cin >> n >> s >> t;
    size_t i = 0;
    for ( ; i < n; i++)
        if (s.substr(i) == t.substr(0, n-i))
            break;
    cout << n + i << '\n';
    return 0;
}

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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define dump_1(x1) cerr << #x1 << ": " << x1 << endl
#define dump_2(x1, x2) \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define dump_3(x1, x2, x3)                                                \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << endl
#define dump_4(x1, x2, x3, x4)                                            \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << endl
#define dump_5(x1, x2, x3, x4, x5)                                        \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define dump(...) \
  CHOOSE((__VA_ARGS__, dump_5, dump_4, dump_3, dump_2, dump_1, ~))(__VA_ARGS__)
#define check(s) cerr << s << endl

#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 all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using namespace std;

using ll = long long;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

void solve(std::string S, std::string T) {
  ll a = 0;
  for (int i = 0; i <= sz(S) - sz(T); i++) {
    ll cnt = 0;
    rep(j, sz(T)) {
      if (S.at(i + j) == T.at(j)) cnt++;
    }
    a = max(a, cnt);
  }

  cout << sz(T) - a << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  std::string S;
  std::cin >> S;
  std::string T;
  std::cin >> T;
  solve(S, T);
  return 0;
}


Measured memory_bytes: 3660
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 998244353;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dp[2][90010] = {};
ll dp2[2][90010] = {};
ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1) res = res * x % MOD;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll a[310];
    rep(i,0,N) cin >> a[i];
    dp[0][0] = 1;
    ll sum = 0;
    rep(i,0,N) sum += a[i];
    ll cur = 0, nxt = 1;
    rep(i,0,N){
        rep(j,0,300*N+1){
            dp[nxt][j] = 0;
        }
        rep(j,0,300 * N + 1){
            if(j - a[i] >= 0) (dp[nxt][j] += dp[cur][j - a[i]]) %= MOD;
            (dp[nxt][j] += 2 * dp[cur][j]) %= MOD;
        }
        cur ^= 1;
        nxt ^= 1;
    }

    dp2[0][0] = 1;
    cur = 0, nxt = 1;
    rep(i,0,N){
        rep(j,0,300*N+1){
            dp2[nxt][j] = 0;
        }
        rep(j,0,300*N+1){
            if(j - a[i] >= 0) (dp2[nxt][j] += dp2[cur][j - a[i]]) %= MOD;
            (dp2[nxt][j] += dp2[cur][j]) %= MOD;
        }
        cur ^= 1;
        nxt ^= 1;
    }

    ll ans = 0;
    rep(i,(sum+1)/2, sum+1){
        (ans += dp[cur][i]) %= MOD;
    }
    if(sum % 2 == 0){
        ans -= dp2[cur][sum/2];
        ans = (ans + MOD) % MOD;
    }
    ans *= 3;
    ans %= MOD;

    ans = (power(3,N) - ans + MOD) % MOD;
    print(ans);

}

Measured memory_bytes: 3072
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
using namespace std;

int gcd(int a, int b) {

    if(a < b)   swap(a, b);
    if(b == 0)  return a; 

    return gcd(a % b, b);
}

int main() {

    int a, b;
    while(cin >> a >> b) {

        cout << gcd(a, b) << endl;
    }
    return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        // 標準入力からデータを読み込む準備
        Scanner sc = new Scanner(System.in);
        // 最初の文字の固まりを整数値と想定して読み込む
        int x = sc.nextInt();
        int answer = x*x*x /* ここを変えて3乗しよう！ */;
        System.out.println(answer);
        sc.close();
    }
}


Measured memory_bytes: 26144
#include <iostream>

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n, f;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> f;
        int count = 0;
        int r = n-1, l = 0;
        int mid;
        while (true) {
            mid = (r+l) / 2;
            if (r < l) break;
            count++;
            if (a[mid] == f) {
                 break;
            }
            if (r == l) break;
            if (a[mid] < f) {
                l = mid+1;
            }
            if (a[mid] > f) {
                r = mid-1;
            } 
        }
        cout << count << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n; cin >> n;
	
	if(n == 3 or n == 5 or n == 7) printf("YES\n");
	else printf("NO\n");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
using namespace std;
// type alias
typedef long long LL;
typedef vector < int > VI;
typedef unordered_map < int, int > MAPII;
typedef unordered_set < int > SETI;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// minmax
#define SMAX(a,b) a = max(a,b)
#define SMIN(a,b) a = min(a,b)
// debug cerr
#define TRACE true
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }

/*
 
 8/25/2018
 
 15:00-15:20 analysis
 15:35 submit and got 1WA
 
 */

// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG x.cpp && ./a.out
//const int MAX_N=1e5+1;
int N;
//LL A[MAX_N];

const string s0="Vacant", s1="Male", s2="Female";
unordered_map<string,int> T={
  {s0,0},{s1,1},{s2,2}
};

string S;

int cnt=0;
int fetch(int i) {
  ++cnt;
  assert(cnt<=20);
  cout<<i<<endl;
  cout.flush();
  string s; cin>>s;
  return T[s];

//  return S[i]-'0';
}

void solve() {
  int l=0,r=N;
  int x=fetch(0);
  if(x==0) return;
  
  while(abs(r-l)>1) {
    int mid=(l+r)/2;
    int xmid=fetch(mid);

    bool par=abs(mid-l-1)%2;
    
//    dump4(l,r,mid,xmid);
//    dump4(l,r,par,x);
    
    if(xmid==0) return;
    
    if((par&&x==xmid)||(!par&&x!=xmid)) {
      l=mid;
      x=xmid;
    } else {
      r=mid+1;
    }
    if(l>r) swap(l,r);
  }

  x=fetch(l);
  assert(x==0);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  cin>>N;
  //cin>>S;
  //N=SZ(S);
  
  solve();
  return 0;
}


Measured memory_bytes: 852
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		sc.close();
		int[] a = new int[1000001];
		int[] b = new int[1000001];
		a[0] = s;
		b[s]++;
		for(int i = 1; i < a.length; i++) {
			int t = a[i - 1];
			if(t % 2 == 0) {
				a[i] = t / 2;
				//System.out.println(a[i]);
				b[a[i]]++;
				if(b[a[i]] == 2) {
					System.out.println(i + 1);
					System.exit(0);
				}
			}else {
				a[i] = 3 * t + 1;
				b[a[i]]++;
				if(b[a[i]] == 2) {
					System.out.println(i + 1);
					System.exit(0);
				}
			}

		}
	}
}

Measured memory_bytes: 31316
#include <stdio.h>

void swap(unsigned long *n1, unsigned long *n2)
{
	unsigned long temp = *n1;
  *n1 = *n2;
  *n2 = temp;
}

unsigned long cal_gcd(unsigned long n1, unsigned long n2)
{
	unsigned long rem;
  while (1) {
		rem = n2 % n1;
    if (rem == 0) {
      break;
    }
    n2 = rem;
    swap(&n1, &n2);
  }

  return n1;
}

unsigned long cal_lcm(unsigned long n1, unsigned long n2)
{
  unsigned long tmp;
  int i = 1;
  while (1) {
		tmp = n2 * i;
    if (tmp % n1 == 0) {
      break;
    }
    i++;
  }

  return tmp;
}

int main()
{
	unsigned long a, b;
  unsigned long gcd, lcm;

  while (scanf("%ld %ld", &a, &b) != EOF) {
    if (a > b) {
      swap(&a, &b);
    }
    gcd = cal_gcd(a, b);
    lcm = cal_lcm(a, b);

    printf("%ld %ld\n", gcd, lcm);
  }

  return 0;
}

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

long gcd(long a, long b) {

  if (b == 0) {
    return a;
  }

  return gcd(b, a % b);

}

long lcm(long a, long b) {

  return a / gcd(a, b) * b;

}

int main() {

  long A, B, C, D;
  cin >> A >> B >> C >> D;

  long lcm_ = lcm(C, D);

  long A1 = A / C;
  long B1 = B / C;
  long AB1 = B1 - A1;
  if (A % C == 0) {
    AB1++;
  }

  long A2 = A / D;
  long B2 = B / D;
  long AB2 = B2 - A2;
  if (A % D == 0) {
    AB2++;
  }

  long A3 = A / lcm_;
  long B3 = B / lcm_;
  long AB3 = B3 - A3;
  if (A % lcm_ == 0) {
    AB3++;
  }

  long AB = AB1 + AB2 - AB3;
  
  cout << B - A + 1 - AB << endl;

}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var inputs = new List<string>();

            string input = Console.ReadLine();
            String[] temp = input.Split(' ');
            int A = int.Parse(temp[0]);
            int P = int.Parse(temp[1]);

            int ans = (3 * A + P) / 2;


            Console.WriteLine(ans);

            return;
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)

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

struct Query{
	int type;
	int a,b;
	bool operator<(const Query&c)const{
		return b-a<c.b-c.a;
	}
};
struct Segtree{
	vector<int>dat,lazy;
	int size=1;
	Segtree(int x){
		while(size<x)size*=2;
		dat.resize(size*2-1,0);
		lazy.resize(size*2-1,0);
	}
	void eval(int k,int l,int r){
		dat[k]+=lazy[k];
		if(r-l>1){
			lazy[k*2+1]+=lazy[k];
			lazy[k*2+2]+=lazy[k];
		}
		lazy[k]=0;
	}
	void update(int a,int b,int x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]+=x;
			eval(k,l,r);
			return;
		}
		update(a,b,x,k*2+1,l,(l+r)/2);
		update(a,b,x,k*2+2,(l+r)/2,r);
	}
	int query(int a,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r-l==1)return dat[k];
		if(a<(l+r)/2)return query(a,k*2+1,l,(l+r)/2);
		return query(a,k*2+2,(l+r)/2,r);
	}
};
int N,M;
signed main() {
	cin>>N>>M;
	vector<Query>query;
	REP(i,M+1)query.push_back({true,0,i});
	rep(i,N){
		int l,r;cin>>l>>r;
		query.push_back({false,l,r+1});
	}
	sort(all(query));
	Segtree segtree(M+1);
	int cnt=0;
	rep(i,N+M){
		if(!query[i].type){
			segtree.update(query[i].a,query[i].b,1);
			cnt++;
		}else {
			int j=0,ans=0;
			while(j<=M){
				ans+=segtree.query(j);
				j+=query[i].b;
			}
			cout<<ans+N-cnt<<endl;
		}
	}
}


Measured memory_bytes: 16360
s=int(input())
a=[s]
count=1
while True:
    if a[count-1]%2==0:
        a.append(a[count-1]//2)
    else:
        a.append(3*a[count-1]+1)
    count+=1
    if len(set(a))!=count:
        print(count)
        break

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
 
  if (A+B>C+D) {
    cout << "Left" << endl;
  }else if (A+B<C+D) {
    cout << "Right" << endl;
  }else{
    cout << "Balanced" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll  long long
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
#define f(i,n)   for(int i=0;i<n;i++)
#define INF 1e9+5
#define LINF 1e18L+5;
using namespace std;
/************************BELIAL**********DEVIL*********BELIAL***********DEVIL*************************/
int main()
{

	FAST_IO
	ll n, w;

	cin >> n >> w;
	ll wt[n], val[n],sum=0;
	f(i, n)
	{
		cin >> wt[i] >> val[i];
        sum+=val[i];
 
	}
	
	ll dp[n + 1][1000 * n + 1];
//memset(dp,INF,sizeof(dp));
	for (int i = 0; i <= n; i++)
	{
		ll j;
		for ( j = 0; j <= sum; j++)
		{
			dp[i][j] = LINF;
		}

	   dp[i][0]=0;
	}

	ll ans = -LINF;
	for (ll i = 1; i <= n; i++)
	{
		ll j;
		for ( j = 0; j <= sum; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= val[i - 1])
				dp[i][j] = min(dp[i][j], dp[i - 1][j - val[i - 1]] + wt[i - 1]);
			if (i == n)
			{
				if (dp[i][j] <= w)
				{
					ans = (ll)max(ans, j);

				}

			}

		}


	}


	cout << ans;


}

Measured memory_bytes: 79232