akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef pair<int,int> mypair;
void jump(int x,int y,int acc,int n,vector<vector<bool> >&map,vector<vector<mypair> > &map2){
	if(map[x][y]){
int sx=map2[x][y].first;
int sy=map2[x][y].second;
if(acc==n*n+1)map[x][y]=false;
acc++;
jump(sx,sy,acc,n,map,map2);
}
}

int main(void){
int n;
while(1){
cin>>n;
if(n==0)break;
vector<vector<bool> >map(n,vector<bool>(n,true));
vector<vector<mypair> >map2(n,vector<mypair>(n));
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		cin>>map2[j][i].first>>map2[j][i].second;
	}
}int t=0;
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
jump(i,j,0,n,map,map2);
	}
}
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
if(map[i][j]==false)t++;
	}
}
cout<<t<<endl;
}
return 0;
}

Measured memory_bytes: 3084
/*
 * (a + b) - (a xor b) = 2 * (a and b)
 *  e.g. 0111 + 1010 - 1101 = 2 * 0010
 * Use two pointers technique.
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <tuple>
#include <string>
#include <iterator>
#include <regex>

#define int long long
using namespace std;

#define MAX_N 200000

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

    int rt = 0, l = 0, r = 0, bin_or = 0;
    for (; l < N; l++) {
        while (r < N && !(bin_or & A[r])) {
            bin_or |= A[r];
            r++;
        }
        rt += r - l;
        bin_or = bin_or & ~A[l];
        //cout << "(l, r, rt, bin_or) = " << l << " " << r << " " << rt << " " << bin_or << endl;
    }
    cout << rt << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, m;
int a[200005], sz[200005], b[200005];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	int cnt = n;
	FOR(i, n) {
		cin >> a[i];
		sz[a[i]]++;
		int pos = a[i] - sz[a[i]] + 1;
		if (pos > 0) {
			b[pos]++;
			if (b[pos] == 1) cnt--;
		}
	}

	vector<int> ans(m);
	FOR(i, m) {
		int x, y;
		cin >> x >> y;
		x--;
		
		int pos = a[x] - sz[a[x]] + 1;
		if (pos > 0) {
			b[pos]--;
			if (b[pos] == 0) cnt++;
		}
		sz[a[x]]--;
		
		a[x] = y;
		sz[a[x]]++;
		pos = y - sz[a[x]] + 1;
		if (pos > 0) {
			b[pos]++;
			if (b[pos] == 1) cnt--;
		}
		ans[i] = cnt;
	}

	FOR(i, m) cout << ans[i] << endl;

	return 0;
}

Measured memory_bytes: 4608
#include<iostream>
#include<vector>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;


int main(){
	int n,m;
	cin>>n>>m;
	vector<int>h(n);
	rep(i,n)cin>>h[i];
	vector<int> a(m),b(m);
	rep(i,m)cin>>a[i]>>b[i];
	vector<int> k(n,0);//k[i]==0 means higher
	rep(i,m){
		if(h[a[i]-1]<h[b[i]-1]){
			k[a[i]-1]=1;
		}else if(h[a[i]-1]>h[b[i]-1]){
			k[b[i]-1]=1;
		}else{
			k[a[i]-1]=1;
			k[b[i]-1]=1;
		}
	}
	int sum=0;
	rep(i,n){
		if(k[i]==0)sum++;
	}
	cout<<sum<<endl;

	return 0;
}

Measured memory_bytes: 4768
import math

#X=int(input())
# a=int(input())
A,B,N=map(int,input().split(" "))
#a=[int(_) for _ in input().split(" ")]

s=N//B

if s==0:
  x=N
else:
  x=s*B-1

if B==1:
  ans=0
  #print("B")
else:
  ans = int(x/B*A) - A * int(x/B)

print(ans)

Measured memory_bytes: 9208
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

struct SegmentTree{
    private:
        int n;
        vector<ll> node; //セグ木の持つデータの型を入力
        ll e = INF; //単位元
    public:
        ll F(ll a,ll b){
            return min(a,b);//二項演算
        }

        void init(vector<ll> v) {
            int sz = v.size();
            n = 1; while(n < sz) n *= 2;
            node.resize(2*n-1, e);

            rep(i,sz) node[i+n-1] = v[i];
            per(i,n-1) node[i] = F(node[2*i+1], node[2*i+2]);

            //rep(i,2*n-1) cout << node[i] << endl;
        }

        void update(int x,ll val){
            x += n-1;
            node[x] = val;
            while(x > 0) {
                x =(x-1)/2;
                node[x]=F(node[2*x+1],node[2*x+2]);
            }
        
        }

        ll get(int a, int b, int k=0, int l=0, int r=-1) {
            if(r < 0) r = n;
            if(r <= a || b <= l) return e;
            if(a <= l && r <= b) return node[k];

            ll vl = get(a, b, 2*k+1, l, (l+r)/2);
            ll vr = get(a, b, 2*k+2, (l+r)/2, r);
            return F(vl, vr);
        }
};

int n;
LP q[100010];
ll min_r=INF,max_l=0;

void solve(){
    cin >> n;
    rep(i,n){
        cin >> q[i].first >> q[i].second;
        min_r=min(min_r,q[i].second);
    }
    sort(q,q+n);
    int sta;
    vector<ll> l,r;
    rep(i,n){
        l.push_back(q[i].first);
        r.push_back(q[i].second);
    }
    per(i,n){
        if (q[i].second==min_r) {
            sta=i;
            break;
        }
    }
    SegmentTree seg;seg.init(r);
    ll ans=0;
    //cout << sta << endl;
    rep(i,n){
        //cout << l[i] << " " << r[i] << endl;
        //cout << min(seg.get(0,i),seg.get(i+1,n)) << endl;
        ll res=r[i]-l[i]+1;
        if (i!=n-1) res+=max(0ll,min(seg.get(0,i),seg.get(i+1,n))-l[n-1]+1);
        else res+=max(0ll,seg.get(0,i)-l[n-2]);
        ans=max(ans,res);
        //cout << res << endl;
    }
    Rep(i,sta,n-1){
        ll res=max(0ll,min_r-l[i]+1)+max(0ll,seg.get(i+1,n)-l[n-1]+1);
        ans=max(ans,res);
        //cout << res << endl;
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 6380
include Math
a,b,c = gets.split.map(&:to_f)
c = c * PI / 180
s = a * b * sin(c) / 2
l = a + b + sqrt(a**2 + b**2 - 2*a*b*cos(c) )
h = b * sin(c)
puts s
puts l 
puts h


Measured memory_bytes: 6936
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>



#define rep(i,p,q) for(ll i = p;i < q;i++)
#define ll long long

using namespace std;

//36A
int main(void) {
	string s;
	cin >> s;
	string sF = "";
	string sN = "";
	ll ans = 0;
	rep(i, 0, s.size()) {
		sN += s[i];
		if (sN != sF) {
			ans++;
			sF = sN;
			sN = "";
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	buf := []byte{}
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func main() {
	var MOD int64 = 1e9 + 7

	N := nextInt()
	A := make([]int64, N)
	for i := 0; i < N; i++ {
		A[i] = int64(nextInt())
	}

	var sum int64
	for i := 0; i < N; i++ {
		sum += A[i]
		sum %= MOD
	}

	var result int64
	for i := 0; i < N; i++ {
		sum -= A[i]
		if sum < 0 {
			sum += MOD
		}
		result += A[i] * sum
		result %= MOD
	}

	fmt.Println(result)
}


Measured memory_bytes: 5848
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int N, Y;
  cin >> N >> Y;

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N - i; j++) {
      if (10000 * i + 5000 * j + (N - i - j) * 1000 == Y) {
        cout << i << " " << j << " " << N - i - j << "\n";
        return 0;
      }
    }
  }

  cout << "-1 -1 -1\n";
  return 0;
}


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

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl


int main(){
    //入力受け取り
    int n,m;
    cin >> n >> m;
    vector<vector<int>> vec(m);//各電球につながっているスイッチの種類
    for(int i=0;i<m;i++){
        int k;
        cin >> k;
        for(int j=0;j<k;j++){
            int x;
            cin >> x;
            vec[i].push_back(x-1);
        }
    }
    vector<int> p(m);
    for(int i=0;i<m;i++){
        cin >> p[i];
    }
    
    
    //bit全探索開始
    int count = 0;
    for(int bit=0;bit<(1<<n);++bit){
        bool flag = true;
        for(int j=0;j<m;++j){
            int con = 0;
            for(int v:vec[j]){
                if (bit & (1<<v)) ++con;
            }
            if (con % 2 != p[j]){
                flag = false;
                break;
            }
        }
        if(flag)++count;
    }
    COUT(count);
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[float('inf')]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
x=distance[n-1]
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=-float('inf')
if distance[n-1]==x:
  print(-distance[n-1])
else:
  print('inf')

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;

  if (b - a == c - b){
    cout << "YES" << endl;
  }
  else
  {
    cout << "NO" << endl;
  }
  
}

Measured memory_bytes: 3640
n,m = map(int, input().split()) 
sc = [list(map(int, input().split())) for _ in range(m)]
def check(num):
    num_str = str(num)
    if len(num_str) != n:
        return False
    for s, c in sc:
        if num_str[s-1] != str(c):
          return False
    return True

for i in range(1000):
    if check(i):
      	print(i)
      	exit()

print(-1)


Measured memory_bytes: 2940
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define int ll
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;

    vector<int> v;

    void fact(ll n)
    {
        ll x=sqrt(n);
        while((x+1)*(x+1)<=n)
        {
            ++x;
        }
        while((x-1)*(x-1)>=n)
        {
            --x;
        }
        int i;
        for(i=1;i<=x;++i)
        {
            if((n%i)==0)
            {
                v.pb(i);
                if(n/i!=i)
                {
                    v.pb(n/i);
                }
            }
        }
    }

    signed main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            ll n,i,j;
            cin>>n;
            if(n==2)
            {
                cout<<1<<endl;
                return 0;
            }
            if(n==3)
            {
                cout<<2<<endl;
                return 0;
            }
            fact(n);
            ll ans=0,x;
            for(auto it:v)
            {
                if(it==n || it==1)
                    continue;
                x=n;
                while(x%it==0)
                    x=x/it;
                if(x%it==1)
                {
                    ++ans;
                }
            }
            v.clear();

            fact(n-1);
            for(auto it:v)
            {
                if(n%it==1)
                {
                    ++ans;
                }
            }
            ++ans;
            cout<<ans<<endl;
        }
        return 0;
    }


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

A.sort(reverse=True)

def split_cnt(L):
    cnt = 0
    for a in A:
        if a <= L:
            break
        cnt += -(-a // L) - 1
    return cnt



l = 0
r = A[0]
while l + 1< r:
    mid = (l + r) // 2
    if split_cnt(mid) <= K:
        r = mid
    else:
        l = mid
print(r)

Measured memory_bytes: 103728
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <stack>
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <set>
#include <limits>
#include <numeric>
#include <array>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<array<int, 3>> dp(n);

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

	array<int, 3> prev = dp[0];
	array<int, 3> cur;

	for (int i = 1; i < dp.size(); ++i)
	{
	    cur[0] = dp[i][0] + max(prev[1], prev[2]);
		cur[1] = dp[i][1] + max(prev[0], prev[2]);
		cur[2] = dp[i][2] + max(prev[0], prev[1]);
		prev = cur;
	}

	cout << *max_element(prev.begin(), prev.end());

	return 0;
}

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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true; } return false; }

// const int INF = 1001001001;
// long long max => LLONG_MAX

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

    int n, m;
    cin >> n >> m;

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


    for(int i =0; i < n-m+1; i++){
        for(int j = 0; j < n-m+1; j++){
            bool check = true;
            for(int k = 0; k < m; k++){
                for(int l = 0; l < m; l++){
                    if(a[i+k][j+l] != b[k][l]) check = false;
                }
            }
            if(check){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}


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

int main(){
    char c;
    cin >> c;
    if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'){
        cout << "vowel" << endl;
    }else{
        cout << "consonant" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n);
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

int n, k;

int main()
{
    cin>>n>>k;
    double r = 1e-11;
    REP(i,n) {
        r += 1.0 / n / (i + 1 >= k ? 1 : pow(2, (int)log2((k*2-1) / (i+1))));
        //cout<<(int)log2((k*2-1) / (i+1)) + 1<<endl;
    }
    printf("%10.9f\n",r);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i, n) cin >> p.at(i);
  vector<int> s = p;
  sort(s.begin(), s.end());
  int co = 0;
  rep(i, n){
    if(s.at(i) != p.at(i)) co++;
  }
  if(co <= 2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

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

const int MOD = (int)1e9 + 7;
struct mint { int n; mint(int n = 0) : n(n) { } };
mint operator+(mint a, mint b) { return (a.n += b.n) >= MOD ? a.n - MOD : a.n; }
mint operator-(mint a, mint b) { return (a.n -= b.n) < 0 ? a.n + MOD : a.n; }
mint operator*(mint a, mint b) { return 1LL * a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
ostream &operator<<(ostream &os, mint a) { return os << a.n; }

vector<vector<int>> E;
vector<vector<mint>> dp;

enum { W, B };
void dfs(int cu, int pa = -1) {
    dp[cu][W] = dp[cu][B] = 1;
    for (int& to : E[cu]) if (to != pa) {
        dfs(to, cu);
        dp[cu][W] *= dp[to][W] + dp[to][B];
        dp[cu][B] *= dp[to][W];
    }
}

int main() {
    int N; cin >> N;
    E.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y; cin >> x >> y; x--, y--;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    dp.assign(N, vector<mint>(2, 0));
    dfs(0);
    cout << dp[0][W] + dp[0][B] << endl;
    return 0;
}

Measured memory_bytes: 16768
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    long long n,m;
    long long num;
    scanf("%lld %lld",&n,&m);
    if(n!=1&&m!=1)
    {
        num=(m-2)*(n-2);
        printf("%lld\n",num);
    }
    else
        if(n==1&&m==1)
        {
            printf("1\n");
        }
        else
        {
            num=n*m-2;
            printf("%lld\n",num);
        }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

#define lli long long int

int main(){
    string s;
    cin>>s;

    //cout<<s<<"\n";
    vector<int>v(3,0);
    v[0]=(s[0]=='S')?0:1;
    int ans=v[0];
    for(int i=1;i<3;i++){
        v[i]=(s[i]=='S')?0:v[i-1]+1;
        ans=max(ans, v[i]);
    }

    // for(auto x:v)cout<<x;
    // cout<<"\n";

    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 3160
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}

template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << i << "\n"

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

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

  ll n,k;
  std::cin>>n>>k;


  if(n==1){
    std::cout<<k;
    return 0;
  }

  if(k==1){
    std::cout<<0;
    return 0;
  }

  std::vector<std::vector<ll>> graph(n);

  std::vector<ll> conv(k-1);

  conv[0]=1;
  rep(i,1,k-1)conv[i]=(conv[i-1]*(k-1-i))%MOD;

  rep(i,0,n-1){
    ll a,b;
    std::cin>>a>>b;
    a--;b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  std::stack<P> que;
  
  ll ans=k;
  if(graph[0].size()>=k){
    ans=0;
  }else{
    rep(i,0,graph[0].size())ans=(ans*(k-1-i))%MOD;
  }

  for(ll next:graph[0]){
    que.push({0,next});
  }

  while(!que.empty()){
    P now=que.top();que.pop();

    if(graph[now.second].size()>=k){
      ans=0;
    }else{
      ans=(ans*conv[graph[now.second].size()-1])%MOD;
    }

    for(ll next:graph[now.second]){
      if(next!=now.first)que.push({now.second,next});
    }
  }

  std::cout<<ans;

  return 0;
}






Measured memory_bytes: 8948
i = 0

while True:
    n = int(input())
    x = 1000 - n
    if n == 0:
        break
    
    a = x//500
    x = x%500
    
    b = x//100
    x = x%100
    
    c = x//50
    x = x%50
    
    d = x//10
    x = x%10
    
    e = x//5
    
    f = x%5
    
    print(a+b+c+d+e+f)
    
    i += 1


Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N = 2e5 + 5;
int n;
ll arr[N], dp[N][3];
int lst;
ll solve(int idx, int state) {
    if (idx >= n)
        return 0;
    ll &ret = dp[idx][state];
    if (ret != -1)
        return ret;
    ret = -1e18;
    if (state < 2)
        ret = solve(idx + 1, state + 1);
    if (idx != n - 1 || state)
        ret = max(ret, arr[idx] + solve(idx + 2, state));
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    memset(dp, -1, sizeof dp);
    if (n & 1)
        cout << solve(0, 0);
    else
        cout << solve(0, 1);
    return  0;
}

Measured memory_bytes: 17688
from sys import stdin

def main():
  N, *LR = map(int, stdin.buffer.read().split())
  L, R = LR[::2], LR[1::2]#偶数個目、奇数個目を取ってきている
  max_l = max(L)
  min_r = min(R)
  ab = [(max(0, r - max_l + 1), max(0, min_r - l + 1)) for l, r in zip(L, R)]
  #各RとLの上限との間に何人いるか、各LとRの下限との間に何人いるか全員調査
  #abは各LRが、L上限、R下限の境界をどの程度超えているかのリスト
  ab.sort()
  mi = float("inf")
  ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
  #maはLRの間に入る人数の最大値＋共通ライン（簡単に考えられる最大の分け方）
  for i in range(N - 1):
    mi = min(mi, ab[i][1])
    #過去に調査したR下限を超える部分下の部分のうち最小のもの（第1グループ）
    ma = max(ma, mi + ab[i + 1][0])
    #miとL上限を超える上の部分（ソートしているので次の候補が一番最小）の和とmaを比べている。
  print(ma)
    
main()

Measured memory_bytes: 26708
'use strict'

function Main(input) {
  input = input.trim()
  const H = parseInt(input)

  let cc = 1
  const dfs = (n) => {
    if(n === 1) return
    const h = Math.floor(n/2)
    cc++
    dfs(h)
  }
  dfs(H)
  console.log(Math.pow(2, cc) - 1)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
#include <iostream>
typedef long long ll;
#define rep(i,a,b) for(ll i =a ;i <= b;i++)
#define per(i,a,b) for(ll i =a ;i >= b;i--)
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int main(int argc, char const *argv[])
{
	//ifstream cin("input.txt");
	ll n,a,b;
	cin>>n>>a>>b;
	
	ll q = n /(a+ b);
	n = n % (a + b);
	if(a >= n)
		cout<<q*a + n;
	else
		cout<<q*a + a;

}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int N, K;
    cin >> N >> K;
    vector<ll> v[K];
    rep(i, N){
        int C; ll V;
        cin >> C >> V; C--;
        v[C].pb(V);
    }

    vector<pli> p;
    priority_queue<pli> que1, que4; 
    priority_queue<ll, vector<ll>, greater<ll> > que2;
    priority_queue<pli, vector<pli>, greater<pli> > que3;
    rep(i, K){
        sort(all(v[i]), greater<ll>());
        rep(j, 2) p.pb(pli(v[i][0]+v[i][1], i));
        rep2(j, 2, sz(v[i])-1) p.pb(pli(2*v[i][j], i));
        if(sz(v[i]) >= 3){
            que4.push(pli((v[i][0]+v[i][1]+v[i][2])*2, i));
        }
    }
    sort(all(p), greater<pli>());

    vector<int> cnt(K, 0);
    ll sum = 0;
    rep(i, N){
        int j = p[i].second;
        cnt[j]++;
        if(cnt[j] == 1){
            ll tmp = -INF;
            if(!que1.empty()) chmax(tmp, que1.top().first);
            if(!que2.empty()) chmax(tmp, p[i].first*2-que2.top());
            if(!que3.empty() && !que4.empty()){
                chmax(tmp, que4.top().first-que3.top().first);
            }
            if(tmp == -INF) cout << -1 << endl;
            else cout << (sum+tmp)/2 << endl;
        }
        else{
            cout << (sum+p[i].first)/2 << endl;
            while(!que1.empty()){
                int k = que1.top().second;
                if(cnt[k] == sz(v[k]) || que1.top().first > v[k][cnt[k]]*2) que1.pop();
                else break;
            }
            if(cnt[j] < sz(v[j])){
                que1.push(pli(v[j][cnt[j]]*2, j));
            }
            if(cnt[j] >= 3){
                que2.push((v[j][cnt[j]-1])*2);
            }
            while(!que3.empty()){
                int k = que3.top().second;
                if(cnt[k] > 2) que3.pop();
                else break;
            }
            if(cnt[j] == 2){
                que3.push(pli(p[i].first*2, j));
            }
            while(!que4.empty()){
                int k = que4.top().second;
                if(cnt[k] > 0) que4.pop();
                else break;
            }
        }
        sum += p[i].first;
    }
}

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

int main() {
	std::string s;

	std::getline(std::cin, s);
	std::size_t n = s.length();
		
	for (char &c : s) {
		if (std::islower(c)) {
			c = std::toupper(c);
		} else if (std::isupper(c)) {
			c = std::tolower(c);
		}
	}
		
	std::cout << s << '\n';
	
	return 0;
}


Measured memory_bytes: 3212
#include <iostream>
using namespace std;
int main(void){
    string s;
    cin>>s;
    for(int j=0;j<s.length();j++){
        if(j%2==0 & s[j]!='h'){
            cout<<"No"<<endl;
            return 0;
        }
        else if(j%2==1 & s[j]!='i'){
            cout<<"No"<<endl;
            return 0;
        }
        else if (j==s.length()-1 & s[j]=='h'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}


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

int main(){
   int h, r;
   cin>>h>>r;
   if( - h - r < 0 ) cout<<"1"<<endl;
   if( - h - r > 0 ) cout<<"-1"<<endl;
   if( h + r == 0 ) cout<<"0"<<endl;

   return 0;
}



Measured memory_bytes: 3100
//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>
#include <cstdint>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef unsigned long long		SQWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int N;
int x[100], y[100], h[100];

bool check(int cx, int cy)
{
	int cnt = 0;
	int calcH[100];

	REP(i, N) {
		if (0 < h[i]) {
			calcH[cnt] = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
			cnt++;
		}
	}

	REP(i, cnt) {
		if (calcH[0] != calcH[i]) {
			return false;
		}
	}

	REP(i, N) {
		if (0 == h[i]) {
			if (abs(x[i] - cx) + abs(y[i] - cy) < calcH[0]) {
				return false;
			}
		}
	}

	cout << cx << " " << cy << " " << calcH[0] << endl;
	return true;
}

int main()
{
	cin >> N;

	REP(i, N) {
		cin >> x[i] >> y[i] >> h[i];
	}

	REP(cx, 101) {
		REP(cy, 101) {
			if (check(cx, cy)) {
				break;
			}
		}
	}

	return 0;
}


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

int main(){
  ll n,i,a,b;
  cin >> n;
  string s[n];
  string x;
  ll t[n];
  a=0;
  for(i=0;i<n;i++){
    cin >> s[i] >> t[i];
  }
  cin >> x;
  for(i=0;i<n;i++){
    if(x!=s[i]){
      a+=t[i];
    }
    else a=0;
  }
  cout << a;
}

Measured memory_bytes: 256
N = int(input())
T = [int(t) for t in input().split()]
M = int(input())
P, X = [], []
for m in range(M):
    line = input().split()
    P.append(int(line[0]))
    X.append(int(line[1]))

for m in range(M):
    print(sum(T) - T[P[m]-1] + X[m])

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
#define MAXH 101
#define MAXW 101
#define INF 1000

string S;
int main(){
    cin >> S;

    if(S[2] == S[3] && S[4] == S[5]){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 256
N,M,X,Y = map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))

mx=max(x)
my=min(y)

ans="War"
for i in range(X+1,Y):
  if mx<i<=my:
    ans="No War"
    break
    
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


template< typename T >
struct WeightedUnionFind {
  vector< int > data;
  vector< T > ws;

  WeightedUnionFind() {}

  WeightedUnionFind(int sz) : data(sz, -1), ws(sz) {}

  int find(int k) {
    if(data[k] < 0) return k;
    auto par = find(data[k]);
    ws[k] += ws[data[k]];
    return data[k] = par;
  }

  T weight(int t) {
    find(t);
    return ws[t];
  }

  bool unite(int x, int y, T w) {
    w += weight(x);
    w -= weight(y);
    x = find(x), y = find(y);
    if(x == y) return false;
    if(data[x] > data[y]) {
      swap(x, y);
      w *= -1;
    }
    data[x] += data[y];
    data[y] = x;
    ws[y] = w;
    return true;
  }

  T diff(int x, int y) {
    return weight(y) - weight(x);
  }
};

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

  int n,q;
  cin>>n>>q;
  WeightedUnionFind<int> uf(n);
  while(q--){
    int t;
    cin>>t;
    if(t==0){
      int x,y,z;
      cin>>x>>y>>z;
      uf.unite(x,y,z);
    }else{
      int x,y;
      cin>>x>>y;
      if(uf.find(x)==uf.find(y))
        cout<<uf.diff(x,y)<<endl;
      else
        cout<<'?'<<endl;
    }
  }


}


Measured memory_bytes: 4420
import std.stdio, std.math;

double s, s1, s2, a, t;
int n, m;

void main(){
	while (readf("%d\n", &n), n) {
		s1 = calc(n-1);
		readf("%d\n", &m);
		s2 = calc(m-1);
		if (abs(s1-s2) < 1e-10) writeln(0);
		else writeln(s1 > s2 ? 1 : 2);
	}
}

double calc(int n){
	s = t = 0;
	foreach (i; 0..n) {
		readf("%s\n", &a);
		t += a;
		s += sin(a/180*PI);
	}
	s += sin((360-t)/180*PI);
	return s;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main() {
    string a, b;
    cin >> a >> b;
    int n = stoi(a + b);
    int r = sqrt(n);
    if (n == r * r) cout << "Yes\n";
    else cout << "No\n";
}

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

result = "Yes"

for i in range( N-2, -1,-1):
  if list[i] > list[i+1]:
    list[i] -=1
    if list[i] > list[i+1]:
      result = "No"
      break

print(result)

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

using namespace std;

int const MAXN = 200000 + 5;

int memo[MAXN][2];
int n;
string str;

int dp(int pos, bool bef){
	if(pos==n-1){
		if(bef) return 0;
		else return (str[pos]!='#');
	}
	int &ans = memo[pos][bef];
	if(ans!=-1) return ans;
	int ans1 = (str[pos]!='#') + dp(pos+1,0);
	int ans2 = 1e9;
	if(bef) ans2= (str[pos]!='.') + dp(pos+1,1);
	return ans = min(ans1,ans2);
}


main(){
	cin >> n; cin >> str;
	memset(memo,-1,sizeof(memo));
	cout << dp(0,1) << endl;
}

Measured memory_bytes: 11524
#include<bits/stdc++.h>
using namespace std;
int main() {
	cin.sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	if(n % 2) {
		cout << b[n/2] - a[n/2] + 1 << endl;
	}else{
		cout << (long long)(((b[n/2] + b[n/2-1]) /2.0 - (a[n/2] + a[n/2-1]) /2.0) * 2 + 1)<< endl;
	}
    return 0;
}


Measured memory_bytes: 4772
from collections import deque

K = int(input())

q = deque()

for i in range(1, 10):
    q.appendleft(i)

cnt = 0

while True:
    a = q.pop()
    cnt += 1
    if cnt == K:
        print(a)
        exit()
    for i in (-1, 0, 1):
        m = a % 10 + i
        if not m < 0 and not m > 9:
            q.appendleft(a * 10 + m)

Measured memory_bytes: 74324
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;} 
int main(void)
{
    int a[5];
    for(int i=0;i<5;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==0)
        printf("%d",i+1);
    }
}

Measured memory_bytes: 1724
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;

struct zahyo{
  int x,y;
};

bool x_cmp(const zahyo& left,const zahyo& right){
  return left.x==right.x?left.y<right.y:left.x<right.x;
}

int main(){
  int n,ans=0;
  cin>>n;
  vector<zahyo> r(n),b(n);
  for(int i=0;i<n;i++){
    cin>>r[i].x>>r[i].y;
  }
  for(int i=0;i<n;i++){
    cin>>b[i].x>>b[i].y;
  }
  sort(b.begin(),b.end(),x_cmp);
  sort(r.begin(),r.end(),x_cmp);
  vector<int> list(100,0);
  int ymax=-1,rj=-1;
  for(int i=0;i<n;i++){
    rj=-1,ymax=-1;
    for(int j=0;j<n;j++){
      if(list[j]){
        continue;
      }
      if(b[i].x<=r[j].x||b[i].y<=r[j].y){
        continue;
      }
      if(r[j].y>ymax){
        ymax=r[j].y;
        rj=j;
      }
    }
    if(rj!=-1){
      list[rj]=1;
      //printf("i=%d r %d %d, b %d %d\n",i,r[i].x,r[i].y,b[i].x,b[i].y);
    }
  }
  for(int i=0;i<n;i++){
    if(list[i]==1){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3600
#![allow(unused_macros)]

// cf. [Rustで競技プログラミングの入力をスッキリ記述するマクロ - Qiita](https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8)
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::collections::HashMap;
fn main() {
    input! {
        K: usize,
    }
    let mut ans = 0;
    //let mut memo = HashMap::new();
    for a in 1..=K {
        for b in 1..=K {
            for c in 1..=K {
                ans += gcd(a as u64, gcd(b as u64, c as u64));
                //let (a, b, c) = {
                //let mut slice = [a, b, c];
                //slice.sort();
                //(slice[0] as u64, slice[1] as u64, slice[2] as u64)
                //};
                //ans += gcd3(a, b, c, &mut memo);
            }
        }
    }
    println!("{}", ans);
}

fn gcd3(a: u64, b: u64, c: u64, memo: &mut HashMap<(u64, u64, u64), u64>) -> u64 {
    if memo.contains_key(&(a, b, c)) {
        return *memo.get(&(a, b, c)).unwrap();
    }

    let ans = gcd(a, gcd(b, c));
    memo.insert((a, b, c), ans);
    ans
}

pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}


Measured memory_bytes: 2140
import collections

S = input()
Q = int(input())

Query = [input() for i in range(Q)]

deq = collections.deque(S)

flg = False
for q in Query:
    query = q.split(' ')
    if query[0]=='1':
        flg = not flg

    elif query[0] == '2':
        if query[1] == '1':
            if flg == True:
                deq.append(query[2])
            else:
                deq.appendleft(query[2])
        else:
            if flg==True:
               deq.appendleft(query[2])
            else:
               deq.append(query[2]) 
if flg == True:
    deq.reverse()        
print(''.join(deq))

Measured memory_bytes: 21340
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

int main() {
  int a;
  cin>>a;
  cout<<24+(24-a)<<endl;
}



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

int main() {
	int n;
	cin >> n;
	int k;
	double sum = 0;
	for ( int i = 0; i < n; i++ ) {
		cin >> k;
		sum += (double)k/n;
	}
	cout << (int)floor(sum) << 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 n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        // 0からiまでの最大公約数
        int[] leftCache = new int[n];
        leftCache[0] = a[0];
        for (int i = 1; i < n; i++) {
////            System.out.println(leftCache[i - 1] + "/" + a[i]);
            leftCache[i] = gcd(leftCache[i - 1], a[i]);
//            System.out.println(leftCache[i]);
        }
////        System.exit(0);

        // iからn-1までの最大公約数
        int[] rightCache = new int[n];
        rightCache[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightCache[i] = gcd(rightCache[i + 1], a[i]);
//            System.out.println(rightCache[i]);
        }

        int ans = rightCache[1]; // 左端を除いた場合
        for (int i = 0; i < n - 2; i++) {
            int candidate = gcd(leftCache[i], rightCache[i + 2]);
            if (candidate > ans) {
                ans = candidate;
            }
        }
        // 右端を除いた場合
        if (leftCache[n - 2] > ans) {
            ans = leftCache[n - 2];
        }
        System.out.println(ans);
    }

    static int gcd(int a, int b) {
        if (a == 0 || b == 0) {
            return 1;
        }
        if (a > b) {
            if (a % b == 0) {
                return b;
            } else {
                return gcd(b, a % b);
            }
        } else {
            if (b % a == 0) {
                return a;
            } else {
////            System.out.println("a:" + a + ", b:" + b);
                return gcd(a, b % a);
            }
        }
    }
}


Measured memory_bytes: 50696
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin);i>(end);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" <<; 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 Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
ll mod = 1000000007;


int main()
{
	// 入力
	ll N, M;
	cin >> N >> M;

	vector<Pii> AB(N);

	REP(i, N) {
		cin >> AB[i].f >> AB[i].s;
	}

	SORT(AB);

	ll stid = 0;
	ll ans = 0;
	while (M > 0) {
		if (AB[stid].s <= M) {
			M -= AB[stid].s;
			ans += AB[stid].f * AB[stid].s;
			stid++;
		} else {
			ans += AB[stid].f * M;
			break;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <tuple>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[])
{
	int a, b, n, i;
	int tmp;
	int lex_a, lex_b;
	vector<int> p, q, samplep, sampleq;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> tmp;
		p.push_back(tmp);
		samplep.push_back(i + 1);
	}
	for (i = 0; i < n; i++) {
		cin >> tmp;
		q.push_back(tmp);
		sampleq.push_back(i + 1);
	}

	lex_a = lex_b = 0;
	do {
		lex_a++;
		if (samplep == p)
			break;
	} while (next_permutation(samplep.begin(), samplep.end()));
	do {
		lex_b++;
		if (sampleq == q)
			break;
	} while (next_permutation(sampleq.begin(), sampleq.end()));

	cout << max(lex_a, lex_b) - min(lex_a, lex_b) << endl;			
	
	return 0;
}


Measured memory_bytes: 256
/*
.....   .   .   .   .
  .    . .   . .   . .
  .   .....   .   .....
  .  .     .  .  .     .
*/
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
   
using namespace std;
   
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
   
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}



#define left left228
#define right right228
#define set set228

const int maxn = 200 * 1000 + 228;

int n;
int a[maxn];

struct block
{
    int len, d;
    block() {}
    block(int _len, int _d) {
        len = _len;
        d = _d;
    }
};

int D;
vector<block> v;

void add(block b) {
    if (v.empty()) {
        v.push_back(b);
    } else {
        if (v.back().d == b.d) {
            v.back().len += b.len;
        } else {
            v.push_back(b);
        }
    }
}

void del(int k) {
    while (v.back().len <= k) {
        k -= v.back().len;
        v.pop_back();
    }
    if (k) {
        v.back().len -= k;
    }
}

void inclast() {
    if (v.back().len == 1) {
        int curd = v.back().d;
        v.pop_back();
        add({1, curd + 1});
    } else {
        --v.back().len;
        int d = v.back().d;
        add({1, d + 1});
    }
}

void inc() {
    if (v.back().d != D - 1) {
        inclast();
    } else {
        int len = v.back().len;
        v.pop_back();
        inclast();
        add({len, 0});
    }
}

bool check(int x) {
    D = x;
    v.clear();
    v.push_back({a[1], 0});
    for (int i = 2; i <= n; ++i) {
        if (a[i] > a[i - 1]) {
            add(block(a[i] - a[i - 1], 0));
        } else {
            del(a[i - 1] - a[i]);
            if ((int)v.size() == 1 && v[0].d == x - 1) {
                return 0;
            }
            inc();
        }
    }
    return 1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int l = 0, r = n;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << '\n';
    return 0;
}
  
  
  
  


Measured memory_bytes: 1024