akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi atan(1.0)*4
#define pb push_back
#define in(x) insert(x)
#define fl(x,y) for(ll i=x;i<y;i++)
#define vi vector<long long>
#define vs  vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define fi first
#define se second
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
/*bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
LL bpow(LL a,LL b){if(b==0)return 1;LL r=bpow(a,b/2);if(b%2)return r*r*a;else return r*r;}
LL binpow(LL a,LL b){LL r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
LL binpow(LL a,LL b,LL m){a%=m;LL r=1;while(b>0){if(b&1) r=r*a%m;a=a*a%m; b>>=1;}return r;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
*/
//bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}

int main()
{
    ll a,b,x,z,w,c,d,t,n,k,p,q,r,y,yy,sum,ct=0,flag=0;
    string s,s1,s2,s3;
    char ch;
    map<ll,ll>mp,mpp;
    deque<ll>d1,d2,d3;
    vector<ll>v;
    set<ll>st;
    ct=0; flag=0;
    cin>>x>>y>>z;
    p=x+y; q=y+z; r=x+z;
    k=min(min(p,q),r);
    cout<<k<<endl;
}







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

using namespace std;

map<string,vector<string> > digToWord;
map<char,int> mci;
map<string,vector<string> > dp;

vector<string> dfs(string str){
  vector<string> res;
  if(str=="")return res;
  if(dp.find(str)!=dp.end())
    return dp[str];
  for(map<string,vector<string> >::iterator it=digToWord.begin();
      it!=digToWord.end();it++){
    if(str.size()>=it->first.size()&&str.substr(0,it->first.size())==it->first){
      vector<string> vv=dfs(str.substr(it->first.size()));
      if(vv.size()>=1&&vv[0]=="no")
	continue;
      else if(vv.size()==0){
	for(int j = 0; j < it->second.size(); j++)
	  res.push_back(it->second[j]);
      }
      else{
	for(int i = 0; i < vv.size(); i++){
	  for(int j = 0; j < it->second.size(); j++){
	    res.push_back(it->second[j]+' '+vv[i]);
	  }
	}
      }
    }
  }
  if(res.size()==0){
    res.push_back("no");
    return dp[str]=res;
  }
  return dp[str]=res;
}

int main(){
  mci['a']=mci['b']=mci['c']=2;
  mci['d']=mci['e']=mci['f']=3;
  mci['g']=mci['h']=mci['i']=4;
  mci['j']=mci['k']=mci['l']=5;
  mci['m']=mci['n']=mci['o']=6;
  mci['p']=mci['q']=mci['r']=mci['s']=7;
  mci['t']=mci['u']=mci['v']=8;
  mci['w']=mci['x']=mci['y']=mci['z']=9;
  int n;
  while(cin>>n&&n!=0){
    dp.clear();
    digToWord.clear();
    for(int i = 0; i < n; i++){
      string s;
      cin>>s;
      string dig;
      for(int j = 0; j < s.size(); j++)
	dig+=(char)(mci[s[j]]+'0');
      digToWord[dig].push_back(s);
    }
    string str;
    cin>>str;
    vector<string> res=dfs(str);
    if(!(res.size()>=1&&res[0]=="no"))
      for(int i = 0; i < res.size(); i++)
	cout<<res[i]+'.'<<endl;
    cout<<"--"<<endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int n,a[200],fl,cnt;

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

    while(fl == 0){
        for(int i = 0; i < n; i++){
            if(a[i]%2 == 1){
                fl++;
                break;
            }
            a[i] = a[i]/2;
        }
        cnt++;
    }
    cout << cnt-1 << endl;
}

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

using namespace std;

constexpr int INF = (1 << 29);

void move_cup(vector<vector<int>> &v,
              int from,
              int to)
{
    int p = v[from].back();
    v[from].pop_back();
    v[to].emplace_back(p);
}

void next_state(int &prev,
                int &curr,
                vector<vector<int>> &curr_cup)
{
    for (int i = 0; i < 3; i++) {
        int size = curr_cup[i].size();
        if (size == 0) {
            continue;
        }

        for (int di : {-1, 1}) {
            int next = i + di;
            if (next < 0 || next >= 3 || (curr == i && prev == next)) {
                continue;
            }

            int nsize = curr_cup[next].size();
            if (nsize == 0 ||
                curr_cup[i].back() > curr_cup[next].back()) {
                move_cup(curr_cup, i, next);
                prev = i; curr = next;
                return;
            }    
        }
    }
}

int solve(vector<vector<int>> curr_cup,
          const vector<vector<int>> &target)
{
    int res = 0;
    int prev = -1, curr = 0;
    while (curr_cup != target) {
        next_state(prev, curr, curr_cup);
        res++;
    }
    return res;
}

int main()
{
    int N, M;
    while (1) {
        cin >> N >> M;
        if (N == 0 && M == 0) {
            break;
        }
        
        vector<vector<int>> target(3);
        for (int i = 0; i < 3; i++) {
            int K;
            cin >> K;
            for (int j = 0; j < K; j++) {
                int x;
                cin >> x;
                target[i].emplace_back(--x);
            }
        }

        vector<vector<int>> curr_cup(3, vector<int>(0));
        for (int i = 0; i < N; i++) {
            curr_cup[0].emplace_back(i);
        }      

        int res = solve(curr_cup, target);
        swap(target[0], target[2]);
        res = min(res, solve(curr_cup, target));

        if (res <= M) {
            cout << res << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
int main()
{
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	int a[n+1];
	for(int i=1; i<=n; ++i)	cin>>a[i];
	for(int i=1; i<=n-k; ++i){
		if(a[i]<a[i+k])
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	 } 
	 return 0;
 }

Measured memory_bytes: 4436
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<functional>
using namespace std;
string S;
int main() {
	cin >> S;
	if (S[0] == S[2])cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int N, K;
    cin >> N >> K;

    if (K == 1) cout << 0 << endl;
    else {
        cout << N - K << endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,a,b) for(int i=int(a);i>int(b);--i)
using namespace std;
using ll = long long;

int main()
{
  int n;
  cin >> n;
  char c;
  while(cin >> c)
    cout << char('A'+(c-'A'+n)%26);
}


Measured memory_bytes: 256
n = int(input())
for _ in range(n):
  h, w = map(int, input().split())
  mp = [list(input()) for _ in range(h)]
  range_dic = {}
  keys = []
  for y in range(h):
    for x in range(w):
      c = mp[y][x]
      if c in range_dic:
        x1, x2, y1, y2 = range_dic[c]
        range_dic[c] = (min(x, x1), max(x, x2), min(y, y1), max(y, y2))
      else:
        range_dic[c] = (x, x, y, y)
        keys.append(c)
  
  while keys:
    tmp = keys[:]
    for key in keys:
      break_flag = False
      x1, x2, y1, y2 = range_dic[key]
      for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
          if not mp[y][x] in (key, "#"):
            break_flag = True
            break
        if break_flag:
          break
      else:
        for x in range(x1, x2 + 1):
          for y in range(y1, y2 + 1):
            mp[y][x] = "#"
        keys.remove(key)
    
    if tmp == keys:
      print("SUSPICIOUS")
      break
  
  else:
    print("SAFE")


Measured memory_bytes: 5624
//

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int a,v,b,w,t;cin>>a>>v>>b>>w>>t;
    if(abs(a-b)<=(v-w)*t)cout<<"YES"<<nnn;
    else cout<<"NO"<<nnn;
    return 0;
}

Measured memory_bytes: 3584
n, m = map(int, input().split())
D = list(map(int, input().split()))

INF = int(1e18)

# dp[i]: i円をDで支払うときの最小枚数
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    for d in D:
        if i - d >= 0:
            dp[i] = min(dp[i], dp[i - d] + 1)
        else:
            dp[i] = dp[i]

print(dp[n])


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

typedef long long ll;
//loop
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//STL
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

//const
#define MOD 1000000007 //10^9+7:合同式の法

//acronym
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

void Main() {
    string s;
    cin >> s;
    cout << s.at(0) << s.at(1) << s.at(2) << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Main();
	return 0;
}


Measured memory_bytes: 3596
using System;
using System.Collections.Generic;
using System.Linq;
using static Atcoder;
using System.Threading.Tasks;
using System.ComponentModel;

public class Hello
{
    private const long INF = 1000000007;
    public static void Main()
    {
        int[] HW = IntLine();
        int H = HW[0], W = HW[1];
        List<int>[] grid = new List<int>[H];
        for (int i = 0; i < H; i++) { grid[i] = IntLine().Select(v => v %= 2).ToList(); }
        int j = 0;
        bool flag = false;
        int[] memo = new int[2];
        List<int[]> ans = new List<int[]>();
        for (int i = 0; i < H; i++)
        {
            for (j = (i % 2 == 0 ? 0 : W - 1); j != (i % 2 == 0 ? W : -1); j += (i % 2 == 0 ? +1 : -1))
            {
                if (flag) { ans.Add(new int[4] { memo[0] + 1, memo[1] + 1, i + 1, j + 1 }); }
                if (!flag && grid[i][j] == 1) { flag = true; }
                else if (flag && grid[i][j] == 1) { flag = false; }
                memo = new int[2] { i, j };
            }
        }
        Console.WriteLine(ans.Count());
        foreach (var i in ans)
        {
            Console.WriteLine(String.Join(" ", i));
        }
    }
}

public class Atcoder
{
    public static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    public static long LCM(long a, long b)
    {
        long c = a * b;
        if (a < b) Swap(ref a, ref b);
        long d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return c / b;
    }
    public static long GCD(long a, long b)
    {
        if (a < b) Swap(ref a, ref b);
        long d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return b;
    }
    public static string StrReverce(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i < n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static string[] SpRead(char c)
    {
        return Console.ReadLine().Split(c);
    }
    public static string ToConvertBit(int N, int e)
    {
        string ret = "";
        int r = 0;
        while (N != 0)
        {
            r = N % e;
            ret += r.ToString();
            N -= r;
            N /= e;
        }
        ret = StrReverce(ret);
        return ret;
    }
    public static int IntRead()
    {
        return int.Parse(Console.ReadLine());
    }
    public static long LongRead()
    {
        return long.Parse(Console.ReadLine());
    }
    public static long[] LongLine()
    {
        return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
    }
    public static int[] IntLine()
    {
        return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    }
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int N;
  cin >> N;
  map<int, int> mp;
  rep(i, N) {
    int a;
    cin >> a;
    mp[a]++;
  }
  int even = 0;
  each(m, mp) {
    even += m.second % 2 == 0;
  }
  int ans = mp.size();
  if (even % 2 == 1) {
    ans--;
  }
  cout << ans << endl;
}


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


#define MAX 52
int n;
vector<int> v;
class SAT2 {
private:
	vector<vector<int> > v;
	vector<vector<int> > rev;
	int SIZE;
public:
	void resize(int n) {
		SIZE = n + 2;
		v.assign(SIZE * 2, vector<int>());
		rev = v;
	}
private:
	int get_id(int id, bool xor_id) {
		return id + (SIZE)*(int)(xor_id);
	}
public:
	void add_edge(int a, bool xor_a, int b, bool xor_b) {  //  a -->> b
		v[get_id(a, xor_a)].push_back(get_id(b, xor_b));
		rev[get_id(b, xor_b)].push_back(get_id(a, xor_a));
	}
private:
	vector<bool> used;
	vector<pair<int, int> > vis;
	inline void dfs(int b, int &ord) {
		used[b] = true;
		for (int i = 0; i < v[b].size(); i++) {
			if (used[v[b][i]] == false) {
				dfs(v[b][i], ord);
			}
		}
		vis.push_back(make_pair(ord, b));
		ord++;
	}
	vector<int> belong;
	inline void rdfs(int b, int &ord) {
		used[b] = false;
		belong[b] = ord;
		for (int i = 0; i < rev[b].size(); i++) {
			if (used[rev[b][i]]) {
				rdfs(rev[b][i], ord);
			}
		}
	}
public:
	bool can() {
		int n = v.size();
		int ord = 0;
		used.assign(n, false);
		vis.clear();
		for (int i = 0; i < n; i++) {
			if (used[i] == false) {
				dfs(i, ord);
			}
		}
		sort(vis.begin(), vis.end(), greater<pair<int, int> >());
		belong.resize(vis.size());
		for (int i = 0; i < n; i++) {
			if (used[vis[i].second]) {
				ord++;
				rdfs(vis[i].second, ord);
			}
		}
		for (int i = 0; i < SIZE; i++) {
			if (belong[i] == belong[i + SIZE]) {
				return false;
			}
		}
		return true;
	}
	
};
bool ok(int mid) {
	SAT2 sa;
	sa.resize(n * 2);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)continue;
			for (int k = 0; k < 2; k++) {
				int tim = v[i];
				if (k == 1) {
					tim = 24 - tim;
				}
				set<int> no;
				for (int kk = 0; kk < 2; kk++) {
					int tim2 = v[j];
					if (kk == 1) {
						tim2 = 24 - tim2;
					}
					int sa = tim - tim2;
					sa = abs(sa);
					sa = min(sa, 24 - sa);
					if (sa < mid) {
						no.insert(kk);
					}
				}
				if (no.size() == 2) {
					sa.add_edge(i, k, i,k^true);
				}
				if (no.size() == 1) {
					sa.add_edge(i, k, j, (*no.begin()) ^ true);
				}
			}
		}
	}
	if (sa.can()) {
		return true;
	}
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int d;
		scanf("%d", &d);
		v.push_back(d);
	}
	v.push_back(0);
	n++;
	int mint = 0;
	int maxt = 13;
	while (mint + 1 < maxt) {
		int mid = (mint + maxt) >> 1;
		if (ok(mid)) {
			mint = mid;
		}
		else {
			maxt = mid;
		}
	}
	if (ok(maxt)) {
		cout << maxt << endl;
	}
	else {
		cout << mint << endl;
	}

	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#define llint long long
#define inf ((llint)1e18)

using namespace std;

llint n;
llint a[300005], s[300005];
llint b[300005], bmax[300005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint x;
	for(int i = 1; i <= n; i++){
		cin >> x;
		a[x]++;
	}
	sort(a+1, a+n+1);
	reverse(a+1, a+n+1);
	
	for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
	for(int i = 1; i <= n+1; i++){
		if(a[i] > 0) b[i] = (n-s[i-1])/a[i] + i;
		else b[i] = inf;
	}
	for(int i = 1; i <= n+1; i++) bmax[i] = max(bmax[i-1], b[i]);
	
	llint ans;
	for(llint i = 1; i <= n; i++){
		
		llint ub = n+1, lb = 0, mid;
		while(ub-lb>1){
			mid = (ub+lb)/2;
			if(bmax[mid] > i) ub = mid;
			else lb = mid;
		}
		ans = (n - s[ub-1]) / (i - (ub-1));
		cout << ans << "\n";
	}
	flush(cout);
	
	return 0;
}

Measured memory_bytes: 10240
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
const int MOD = 1e9 + 7;
 
void add(int &a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
}
 
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
 
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
 
const int N = 105;
 
int fact[N+2];
int dp[N+2][2*N+2];
int ifact[N+2];
int n; 
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=mult(fact[i-1],i);
	for(int i=0;i<N;i++) ifact[i]=modpow(fact[i],MOD-2);
	cin>>n;
	dp[1][N] = dp[1][N-1] = 1;
	for(int i=1;i<=n;i++)
	{
		for(int k=0;k<=2*N+1;k++)
		{
			int v=dp[i][k];
			if(v==0) continue;
			for(int a=0;a+i<=n;a++) //# of positive
			{
				for(int b=0;b+a+i<=n;b++) //# of negative
				{
					if(a+b==0) continue;
					int V = mult(mult(v,ifact[a]),ifact[b]);
					int req = N - k;
					if(abs(a+b)>=abs(req)&&abs(a+b-req)%2==0)
					{
						add(dp[i+a+b][((a-b+k-N)>>1)+N], V);
					}
				}
			}
		}
	}
	int ans = mult(dp[n][N], fact[n]);
	cout<<ans<<'\n';
}

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

int face[6],new_face[6];
string s;

int main(){
  for(int i=0;i<6;i++){
	  cin>>face[i];
  }
  cin>>s;
  for(int i=0;i<6;++i){
	  new_face[i] = face[i];
  }
  for(int i=0;i<s.size();i++){
	if(s[i]=='S'){
		new_face[0]=face[4];
		new_face[1]=face[0];
		new_face[4]=face[5];
		new_face[5]=face[1];
	}else if(s[i]=='N'){
		new_face[0]=face[1];
		new_face[1]=face[5];
		new_face[4]=face[0];
		new_face[5]=face[4];
	}else if(s[i]=='E'){
		new_face[0]=face[3];
		new_face[2]=face[0];
		new_face[3]=face[5];
		new_face[5]=face[2];			
	}else if(s[i]=='W'){
		new_face[0]=face[2];
		new_face[2]=face[5];
		new_face[3]=face[0];
		new_face[5]=face[3];			
	}
	for(int j=0; j<6; ++j){
		face[j] = new_face[j];
	}
  }
  cout<<face[0]<<endl;
}



Measured memory_bytes: 3188
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int t = sc.nextInt();
        int ans = n/x*t;
        if(n%x != 0) ans += t;
        pw.println(ans);
        pw.flush();
    }

    static class GeekInteger {
        public static void save_sort(int[] array) {
            shuffle(array);
            Arrays.sort(array);
        }
 
        public static int[] shuffle(int[] array) {
            int n = array.length;
            Random random = new Random();
            for (int i = 0, j; i < n; i++) {
                j = i + random.nextInt(n - i);
                int randomElement = array[j];
                array[j] = array[i];
                array[i] = randomElement;
            }
            return array;
        }
 
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer 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 int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 25444
'use strict';
(function(stdin) { 
  var inputs = stdin.toString(0);
  var params = inputs.split('\n')[0].split(' ').map(Number);
  (function(a,b) {
    if (a < b){
        console.log('a < b')
    }else if (a > b){
        console.log('a > b')
    }if ( a == b) {
        console.log('a == b')
    }


}(params[0],params[1])); 
}(require('fs').readFileSync('/dev/stdin', 'utf8')));

Measured memory_bytes: 7376
//Switches

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int n,m;cin>>n>>m;
    vector<vector<int>>dq(m);
    rep(i,0,m){
        int c;cin>>c;
        rep(j,0,c){
            int t;cin>>t;
            dq[i].pb(t);
        }
    }
    vector<int>ko(m);
    rep(i,0,m)cin>>ko[i];
    int ans = 0;
    for(int bit = 0;bit<(1<<n);bit++){
        int on = 0;
        rep(i,0,m){
            int flag = 0;
            rep(j,0,dq[i].size()){
                if(bit&(1<<dq[i][j]-1)){
                    flag++;
                }
            }
            if(flag%2==ko[i])on++;
        }
        if(on==m)ans++;
    }
    cout<<ans<<nnn;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int a[] = new int[N+1];
    int cnt = 0;
    
    for(int i=1; i<=N; i++){
      a[i]=sc.nextInt();
      if(i%2==1 && a[i]%2==1){
        cnt++;
      }
    }
    System.out.println(cnt);
  }
}
    

Measured memory_bytes: 35632
#include<stdio.h>
#include<stdlib.h>
 
 
int main()
{  
  int n,i,j=0;
 
scanf("%d",&n);
for(i=0 ;i<n; i++)
{
   int a[n];
  scanf("%d",&a[i]);
  {
   if(a[i]!=i+1)
   {
       j++;
   }
  }
 
 
}
     if(j>2)
  {
    printf("NO\n");
  }
else
  {
    printf("YES\n");
  }
 
 
    return 0;
     getch();
}

Measured memory_bytes: 256
import math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]

maxH = max(H)
L=-1
R=math.ceil(maxH / B)

def binary_search(D,U):
    MID=(D+U)//2
    if(MID==D):
        print(U)
    else:
        if sum(math.ceil(max(h-B*MID,0)/(A-B))for h in H)<=MID:
            binary_search(D,MID)
        else:
            binary_search(MID,U)


binary_search(L,R)


   


Measured memory_bytes: 7856
import math

I = list(map(int,input().split()))

N = I[0]
K = I[1]
Q = I[2]
A = []

for i in range(Q):
    A.append(int(input()))


score = [0] * N

for i in range(Q):
    score[A[i]-1] += 1


for i  in range(N):
    if 0 <  K - (Q-score[i]):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 8632
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=100005;
 
int N;
vector<int> adj[MAXN];
int col[MAXN];
 
bool dfs(int u,int f)
{
    if(adj[u].size()==1U)
    {
        col[u]=0;
        return false;
    }
    int cnt[2]={0};
    for(int i=0;i<(int)adj[u].size();i++)
    {
        int v=adj[u][i];
        if(v==f)
            continue;
        if(dfs(v,u))
            return true;
        cnt[col[v]]++;
    }
    if(cnt[0]>=2)
        return true;
    else if(cnt[0])
        col[u]=1;
    else
        col[u]=0;
    return false;
}
 
int main()
{
    scanf("%d",&N);
    for(int i=1;i<N;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
	if(N&1)
		puts("First");
    else if(N==2)
        puts("Second");
    else
    {
        bool ans;
        for(int i=1;i<=N;i++)
            if(adj[i].size()>1U)
            {
                ans=dfs(i,0);
                break;
            }
        puts(ans?"First":"Second");
    }
 
    return 0;
}

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

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

ll get (ll n, ll val) {
  ll p = val;
  ll ret = 0;
  while (n / p) ret += n / p, p *= val;
  return ret;
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n;
  cin >> n;
  if (n % 2 == 0) cout << get(n / 2, 5) << '\n';
  else {
    ll two = get(n, 2);
    ll five = get(n, 5);
    ll k = (n - 1) / 2;
    two -= k + get(k, 2);
    five -= get(k, 5);
    cout << min(two, five) << '\n';
  }
  return (0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define pb push_back
#define mpr make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long
#define ld long double
#define all(arr) arr.begin(), arr.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define INF 1000000001
#define inf1 1000000000000000001
#define MOD 1000000007
#define pie 3.14159265358979323846264338327950L
#define N 100005
#define M 1e6+9
#define mid(l, r) l + (r - l) / 2
#define vec vector<int>
#define vecl vector<ll>
#define umap unordered_map<ll,ll>
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define endl "\n"
using namespace std;

int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};  
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
ll lcm(ll a, ll b) { return (a*b)/ gcd(a,b);}

ll n,k,a,b,c,d,x,y,z,m,l;
ll ans;
vecl arr(N);
ll dp[509][509];
ll pre[N];



void test_case() {

    
   cin>>n;

   map<string,int> mp;
   int cnt = 0;

   rep(i,n) {
       string s;
       cin>>s;
       
       mp[s]++;
       cnt = max(cnt, mp[s]);
   }

   for(auto it : mp) {
       if(it.second == cnt) {
           cout<<it.first<<endl;
       }
   }





}


int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(20);

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


    int t = 1;
    // cin >> t;
    while(t--)
    {   
        test_case();
    }
}


Measured memory_bytes: 19508
#include<iostream> 
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if (a < b){
        cout << "a < b" << endl;
    }else if (a > b){
        cout << "a > b" << endl;
    }else if (a==b){
        cout << "a == b" << endl;
    }
    return 0;
}


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

ans = 0
start_idx = [0] * N
for i, a in enumerate(A):
    if i+a < N:
        start_idx[i+a] += 1
    if i-a >= 0:
        ans += start_idx[i-a]

print(ans)


Measured memory_bytes: 92604
/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#pragma region macro
#include <bits/stdc++.h>
typedef long long int64;
using namespace std;
using P = pair<int64, int64>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const int64 INF = 1LL << 62;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
#define bn '\n'
template <typename T>
ostream& operator<<(ostream& os, const vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, pair<T,S> const&P){
    os << "(";
    os << P.first;
    os << " , ";
    os << P.second;
    os << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
    os<<endl;
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, map<T,S> const&M){
    for(auto e:M){
        os<<e;
    }
    os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
#pragma endregion
//fixed<<setprecision(10)<<ans<<endl;



int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int64>> DP(N+2,vector<int64>(3,-INF)); //飛ばした回数
    DP[0][0] = 0;
    DP[1][1] = 0;
    vector<int64> A(N);
    REP(i,N) cin >> A[i];

    REP(i,N){
        int idx = i + 2;
        REP(j,3){
            chmax(DP[idx][j], DP[idx-2][j] + A[i]);
            if(j) chmax(DP[idx][j], DP[idx-1][j-1]);
        }
    }

    auto ans = DP.back()[1 + (N&1)];
    cout << ans << endl;
}

Measured memory_bytes: 15568
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Here your code !
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String x = br.readLine();
        String X[]=x.split(" ");
        int a=Integer.parseInt(X[0]);
        int b=Integer.parseInt(X[1]);
        int c=Integer.parseInt(X[2]);
        int m=Math.max(a,b);
        m=Math.max(m,c);
        if((a+b+c-m)==m){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    int current = 0;
    int res = 1;

    for (int i = 0; i < n; ++i){
        int l;
        cin >> l;
        current += l;

        if(current <= x) res++;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var A, B int
	fmt.Scan(&A, &B)
	if A == 1 {
		A = 14
	}
	if B == 1 {
		B = 14
	}
	if A > B {
		fmt.Println("Alice")
	} else if A < B {
		fmt.Println("Bob")
	} else {
		fmt.Println("Draw")
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    if (a >= 10 || b >= 10){
        cout << "-1" << endl;
    }
    else {
        cout << a*b << endl;
    }
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

dp = [[[0 for _ in range(51)] for __ in range(2501)] for ___ in range(51)]

def main():
    N, A = LI()
    X = LI()
    dp[0][0][0] = 1
    # for i in range(51):
    #     dp[i][0][0] = 1

    for i in range(N):
        for j in range(2501):
            for k in range(N+1):
                if j - X[i] >= 0 and k - 1 >= 0:
                    dp[i+1][j][k] += dp[i][j-X[i]][k-1]
                dp[i+1][j][k] += dp[i][j][k]
    cnt = 0
    for k in range(1, N+1):
        cnt += dp[N][k*A][k]
    print(cnt)
main()



Measured memory_bytes: 134232
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;



signed main(){

    int A, V; cin >> A >> V;
    int B, W; cin >> B >> W;
    int T; cin >> T;

    if(W >= V){
        Out("NO");
    }else{
        int L = llabs(A - B), M = T * (V - W);
        Ans(L <= M, "YES", "NO");
    }

    return 0;
}


Measured memory_bytes: 3596
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
	string str1;
	string str2;
	int n;
	cin>>n;
	cin.ignore();
	getline(cin,str1);
	getline(cin,str2);
	long long ans = 0;
	char prev = ' ';
	for(int i=0;i<n;i++){
		if(i+1<n&&str1[i]==str1[i+1]){
			if(prev==' '){
				prev = 'Y';
				ans = 6;
			}
			else{
				if(prev=='X'){
					ans = (ans%1000000007)*2;
					ans = (ans%1000000007);
				}
				else{
					ans = (ans%1000000007)*3;
					ans = (ans%1000000007);
				}
				prev = 'Y';
			}
			i++;
		}
		else if(str1[i]==str2[i]){
			if(prev==' '){
				prev = 'X';
				ans = 3;
			}
			else{
				if(prev=='X'){
					ans = (ans%1000000007)*2;
					ans = (ans%1000000007);
				}
				else{
					ans = (ans%1000000007);
				}
				prev = 'X';
			}
		}
	}
	cout<<ans%1000000007<<endl;
}

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

vector<int> E[100000];
using P = pair<char,char>;//ope, X/Y
vector<P> V;

int dfs(int v, int pre, int x, int y, int val, bool ismax){//?????°???????????????????????????
    switch(V[v].first){
        case '&':
            val&=(V[v].second=='X'?x:y);
            break;
        case '|':
            val|=(V[v].second=='X'?x:y);
            break;
        case '^':
            val^=(V[v].second=='X'?x:y);
            break;
        default:
            val=0;
            break;
    }
    int ret;
    if(E[v].size()==1&&v){
        ret=val;
    }else{
        if(ismax){
            ret=-(1<<16);
            for(auto to:E[v]){
                if(to!=pre) ret=max(ret,dfs(to,v,x,y,val,!ismax));
            }
        }else{
            ret=(1<<16);
            for(auto to:E[v]){
                if(to!=pre) ret=min(ret,dfs(to,v,x,y,val,!ismax));
            }
        }
    }
    return ret;
}

int main(){
    int N,M;
    cin>>N>>M;
    V.emplace_back(' ','X');
    for(int i=1;i<N;i++){
        string o;
        cin>>o;
        V.emplace_back(o[3],o[4]);
    }
    for(int i=0;i<N-1;i++){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    int memo[16][16];//[x][y]
    for(int x=0;x<16;x++){
        for(int y=0;y<16;y++){
            memo[x][y]=dfs(0,-1,x,y,0,true);
            // cout<<memo[x][y]<<endl;
        }
    }
    for(int i=0;i<M;i++){
        int X,Y;
        cin>>X>>Y;
        //?????§????????¨A=(0,0),B=(0,1),C=(1,0),D=(1,1)???4??????????????????(A?????\?????????????????????????????????)
        int cnt=3,x=0,y=0;
        int A,B,C,D;
        A=B=C=D=-1;
        for(int j=15;j>=0;j--){
            bool bx,by;
            bx=X&(1<<j);
            by=Y&(1<<j);
            if(!bx&&!by){//A
                if(!~A){
                    A=cnt;
                    cnt--;
                }
            }else if(!bx&&by){//B
                if(!~B){
                    B=cnt;
                    y|=(1<<cnt);
                    cnt--;
                }
            }else if(bx&&!by){//C
                if(!~C){
                    C=cnt;
                    x|=(1<<cnt);
                    cnt--;
                }
            }else{//D
                if(!~D){
                    D=cnt;
                    x|=(1<<cnt);
                    y|=(1<<cnt);
                    cnt--;
                }
            }
        }
        A=!!(memo[x][y]&(1<<A));
        B=!!(memo[x][y]&(1<<B));
        C=!!(memo[x][y]&(1<<C));
        D=!!(memo[x][y]&(1<<D));
        int ans = 0;
        for(int j=0;j<16;j++){
            bool bx,by;
            bx=X&(1<<j);
            by=Y&(1<<j);
            if(!bx&&!by){//A
                ans|=(A<<j);
            }else if(!bx&&by){//B
                ans|=(B<<j);
            }else if(bx&&!by){//C
                ans|=(C<<j);
            }else{//D
                ans|=(D<<j);
            }
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 16432
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
typedef long long int ll;
int N, a[200001];

void solve()
{
    map<int, int> M;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        M[a[i]]++;
    }
    sort(a, a + N);
    int ret = 0;
    int pw = 1 << 30;
    for (int i = N - 1; i >= 0; i--)
    {
        if (M[a[i]])
        {
            M[a[i]]--;
            while (pw >= 2 && 2 * a[i] < pw)
                pw >>= 1;
            if (M.count(pw - a[i]) && M[pw - a[i]])
            {
                ret++;
                M[pw - a[i]]--;
            }
        }
    }
    cout << ret << endl;
}
int main()
{
    while (cin >> N)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 10368
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 2e5;
int n, m;
char col[maxn + 1];

vector<int> g[maxn * 4];

void Add(int u, int v) {
  char a = col[u], b = col[v];
  int t;
  if (a == 'A') {
    if (b == 'A') {
      t = 0;
    } else {
      t = 1;
    }
  } else {
    if (b == 'A') {
      t = 3;
    } else {
      t = 2;
    }
  }
  g[t * n + u].push_back((t + 1 & 3) * n + v);
}

int vis[maxn * 4];

void Dfs(int u) {
  if (vis[u] == 1) {
    puts("Yes");
    exit(0);
  }
  vis[u] = 1;
  for (int v : g[u]) {
    if (vis[v] != 2) {
      Dfs(v);
    }
  }
  vis[u] = 2;
}

bool Main(void) {
  for (int i = 0; i < 4 * n; ++i) {
    if (vis[i] == 0) Dfs(i);
  }
  return false;
}

int main(void) {
  scanf("%d%d", &n, &m);
  scanf("%s", col);
  for (int i = 0; i < m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u; --v;
    Add(u, v);
    Add(v, u);
  }
  puts(Main() ? "Yes" : "No");
  return 0;
}


Measured memory_bytes: 35840
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }

// x 以下のルンルン数が何個あるか
long long calc(long long x) {
    // x を文字列にする
    stringstream ss;
    ss << x;
    string S = ss.str();
    int N = S.size();

    long long dp[20][11][2] = {0};
    dp[1][10][1] = 1;
    for (int j = 1; j < S[0]-'0'; ++j) dp[1][j][1] = 1;
    dp[1][S[0]-'0'][0] = 1;
    for (int i = 1; i < N; ++i) {
        // from j = 10
        dp[i+1][10][1] += dp[i][10][0] + dp[i][10][1];
        for (int add = 1; add < 10; ++add)
            dp[i+1][add][1] += dp[i][10][0] + dp[i][10][1];

        // from j = 0 ~ 9
        for (int j = 0; j < 10; ++j) {
            for (int k = -1; k <= 1; ++k) {
                int add = j + k;
                if (add < 0 || add > 9) continue;

                dp[i+1][add][1] += dp[i][j][1];
                if (add < S[i]-'0') 
                    dp[i+1][add][1] += dp[i][j][0];
                else if (add == S[i]-'0')
                    dp[i+1][add][0] += dp[i][j][0];
            }
        }
    }
    long long res = 0;
    for (int j = 0; j < 10; ++j) res += dp[N][j][0] + dp[N][j][1];
    return res;
}

int main() {
    int K;
    cin >> K;
    long long left = 0, right = 1LL<<50;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (calc(x) >= K) right = x;
        else left = x;
    }
    cout << right << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
   int main()
     
   {
     int k,a,b,flag=0;
     cin>>k>>a>>b;
     for(int i=a;i<=b;i++)
       if(i%k==0){flag=1; break;}
     
     if(flag) cout<<"OK";
     else cout<<"NG";
     
     return 0;
   }


Measured memory_bytes: 3608