akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const ll mod = 1e+9 + 7;
const int INF = 1001001001;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

template<typename Monoid>
struct SegmentTree{
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;      // モノイドに対して二項演算を行う関数オブジェクト
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
        sz = 1;
        while(sz < n)   sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x){
        seg[k + sz] = x;
    }

    void build(){
        for(int k = sz - 1; k > 0; --k){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    void update(int k, const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    Monoid query(int a, int b){
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1)   L = f(L, seg[a++]);
            if(b & 1)   R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const{
        return seg[k + sz];
    }
};

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

    int n;
    cin >> n;
    int limit = 0;
    SegmentTree<int> seg(1e+5 + 5, [](int a, int b){return a+b;}, 0);
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        seg.update(a, seg[a] + 1);
        chmax(limit, a);
    }
    int res = 0;
    for(int i = 1; i <= limit; ++i){
        chmax(res, seg.query(i - 1, i + 2));
    }
    chmax(res, seg.query(0, 1));
    cout << res << endl;
}

Measured memory_bytes: 1280
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	A, B, N := getInt(), getInt(), getInt()
	x := min(N, B-1)
	out(A * x / B)
}


Measured memory_bytes: 1776
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
using namespace std;
 
int main() {
  int n,m;
  cin >> n >> m;
  //cout << n << m << "\n";

  vector<int> ac(n+1),wa(n+1);
  int i,p;
  string result;
  for(i=0;i<m;i++){
    cin >> p >> result;
    //cout << p << ' ' << result << '\n';
    if(ac[p]){continue;}
    if(result == "AC"){
      ac[p] = 1;
    }else{
      wa[p]++;
    }
  }

  int wa_sum=0;
  for(i = 0;i<n+1;i++){
      if(ac[i]){
          wa_sum = wa_sum + wa[i];
      }
  }
  
  cout << accumulate(ac.begin(), ac.end(), 0) << ' ' << wa_sum << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

typedef long long ll;

// vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  return s;
}

int to[100010][26];

int main() {
  unordered_map<char, vector<int>> pos;
  string s, t;
  cin >> s;
  cin >> t;
  for (int i = 0; i < s.size()*2; ++i) {
    char c = s[i%s.size()];
    pos[c].push_back(i);
  }
  for (int j = 0; j < 26; ++j) {
    int offset = 0;
    char c = 'a'+j;
    if (pos.find(c) == pos.end()) continue;
    int t = pos[c][offset];
    for (int i = 0; i < s.size(); ++i) {
      while (i > t) {
        t = pos[c][++offset];
      }
      to[i][j] = t;
    }
  }
  for (int i = 0; i < s.size(); ++i) {
    // cout << i << " " << endl;
    for (int j = 0; j < 26; ++j) {
      if (pos.find('a'+j) == pos.end()) continue;
      // cout << (char)('a'+j) << to[i][j];
    }
    // cout << endl;
  }
  int iter = 0;
  int prev = 0;
  for (char c : t) {
    if (pos.find(c) == pos.end()) {
      cout << -1 << endl;
      return 0;
    }
    int cur = to[prev][c-'a']+1;
    if (cur >= s.size()) { ++iter; }
    // cout << c << " " << prev << " " << cur << endl;
    prev = cur % s.size();
  }
  ll ans = iter * s.size() + prev;
  assert(ans >= 0);
  cout << ans << endl;
}



Measured memory_bytes: 11712
N = int(input())
A = [int(x) for x in input().split()]
d = {}
for i in range(N-1):
    try:
        d[A[i]] += 1
    except:
        d[A[i]] = 1
for i in range(N):
    try:
        print(d[i+1])
    except:
        print(0)

Measured memory_bytes: 119076
#include<bits/stdc++.h>
#define REP(i,x) for(int i=0,i##_len=(x);i<i##_len;++i)
#define rep(i,a,b) for(int i=(a),i##_len(b);i<i##_len;++i)
#define All(x) begin(x),end(x)
#define rAll(x) rbegin(x),rend(x)
using namespace std;
using ll = long long;

int main(){
    int A,B;cin>>A>>B;
    cout<<max({A+B,A-B,A*B})<<endl;
}


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

using ll = long long;
using pii = pair<int, int>;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

int dfs(vector<vector<int>> const& g, int v) {
    if(g[v].size() == 0) {
        return 0;
    }
    vector<int> ch;
    for(auto to : g[v]) {
        ch.push_back(dfs(g, to));
    }
    sort(ch.rbegin(), ch.rend());
    int res = 0;
    for(int i = 0; i < ch.size(); ++i) {
        res = max(res, ch[i] + i + 1);
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    for(int i = 1; i <= N - 1; ++i) {
        int a;
        cin >> a;
        g[a - 1].push_back(i);
    }

    cout << dfs(g, 0) << endl;
}


Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int n;
vector<PII> e;
int main() {
	scanf("%d",&n);
	rep(i,1,n+1) rep(j,i+1,n+1) {
		if (n%2==0&&i+j!=n+1) e.pb(mp(i,j));
		if (n%2==1&&i+j!=n) e.pb(mp(i,j));
	}
	printf("%d\n",SZ(e));
	for (auto p:e) printf("%d %d\n",p.fi,p.se);
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int N, M;
  std::cin >> N >> M;
  vvl cake = vv(N, 4, 0, ll);
  range(i, N) std::cin >> cake[i][1] >> cake[i][2] >> cake[i][3];
  ll ab[2] = {-1, 1};
  std::vector<ll> count(N);
  ll ans = 0, reg;
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
      for(int k=0;k<2;k++){
        reg = 0;
        range(l, N){
          count[l] = cake[l][1]*ab[i];
          count[l] += cake[l][2]*ab[j];
          count[l] += cake[l][3]*ab[k];
        }
        sort(count.begin(), count.end());
        range(m, M) {
          reg+=count[N-1-m];
          //std::cout << count[N-1-m] << '\n';
        }
        ans = max(reg, ans);
        //std::cout << reg <<"hello" << '\n';
      }
    }
  }
  std::cout << ans << '\n';
  return 0;
}


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

int main(){
    long long A,B,Mtmp,mtmp,p,ABmin,ABmax;
    cin >> A >> B;
    vector <long long> common;

    p=2;
    common.push_back(1);
    bool isCount;
    isCount=false;

    if(A > B){
        ABmin=B;
        ABmax=A;
    }else{
        ABmin=A;
        ABmax=B;
    }

    Mtmp=ABmax;
    mtmp=ABmin;

    while( mtmp>=p*p ){
        if( mtmp%p==0 ){
            if( !isCount && Mtmp%p==0 ){
                common.push_back(p);
                isCount=true;
                //cout << "common push back " << p << endl;
            }
            mtmp /= p;
            //cout << "mtmp " << mtmp << endl;
        }else{
            p++;
            isCount=false;
            //cout << "count new p " << p << endl;
        }
    }    
    if(Mtmp%mtmp==0 && mtmp>1 && common.at( common.size()-1 )!=mtmp ){
        common.push_back(mtmp);
        //cout << "common push back last " << mtmp << endl;        
    }

    long long ans;
    ans = (long long) common.size();

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
using namespace std;
#define N 2000005
#define ll long long
#define mod 1000000007
int fac[N],inv[N],t[N],a,b,c,mx,ans;
int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}
int C(int n,int m){return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{
	// freopen("8102.in","r",stdin);
	// freopen("8102.out","w",stdout);
	mx=2000000;t[0]=fac[0]=1;
	for(int i=1;i<=mx;i++)fac[i]=(ll)i*fac[i-1]%mod,t[i]=(ll)t[i-1]*3%mod;inv[mx]=q_pow(fac[mx],mod-2);
	for(int i=mx;i;i--)inv[i-1]=(ll)inv[i]*i%mod;
	// int T;scanf("%d",&T);
	// while(T--)
	// {
	scanf("%d%d%d",&a,&b,&c);ans=0;int rb=0,rc=0;
	for(int i=0;i<=b+c;i++)
	{
		int tmp=(ll)t[b+c-i]*fac[a+i-1]%mod,w=q_pow(2,i);
		if(i>b)
		{
			rb=(rb*2)%mod;
			rb=(rb+C(i-1,b))%mod;
			w=(w-rb)%mod;
		}
		if(i>c)
		{
			rc=(rc*2)%mod;
			rc=(rc+C(i-1,c))%mod;
			w=(w-rc)%mod;
		}
		w=((ll)w*inv[i])%mod;
		ans=(ans+(ll)w*tmp)%mod;
	}
	printf("%lld\n",(ll)(ans+mod)*inv[a-1]%mod);
	// }
}


Measured memory_bytes: 23680
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

int N;
vector<ll> A;

const ll INF=2e18;

bool cmp(ll af,ll ar,ll bf,ll br){
    ll vala=ar,valb=br;
    while(af<bf){
        if(ar<=br) break;
        br*=4;
        bf--;
    }
    while(af>bf){
        if(ar>=br) break;
        ar*=4;
        af--;
    }
    if(af==bf) return ar<br;
    else return af<bf;
}

void solve(bool minus,vector<ll> &res){
    vector<ll> B=A;
    if(minus) rep(i,N) B[i]*=2;
    else reverse(B.begin(),B.end());

    vector<pair<ll,ll>> four(N);
    rep(i,N){
        ll val=abs(B[i]);
        ll num=0;
        ll rest=0;
        while(val>0){
            val/=4;
            num++;
        }
        ll f=1;
        num--;
        rep(j,num) f*=4;
        rest=abs(B[i])-f;
        four[i]=mkp(num,rest);
    }

    res.resize(N+1,0);
    vector<int> back(N,0);
    rep(i,N) back[i]=i-1;
    vector<ll> diff(N,0);
    for(int i=1;i<N;i++){
        if(four[i-1]>=four[i]){
            res[i+1]=res[i];
            continue;
        }

        int now=i;
        ll sum=0;
        ll adv=(four[now].first-four[now-1].first);
        if(four[now-1].second<four[now].second) adv++;

        while(now>0){
            int tar=back[now];
            if(tar+1<now){
                if(tar>=0){
                    sum+=adv*(now-tar);
                    diff[tar]+=adv;
                }else sum+=adv*(now);
                back[i]=back[now];
                now=back[now];
            }else{
                ll nexadv=(four[now].first+diff[now]-(four[now-1].first+diff[now-1]));
                if(nexadv<0) break;
                diff[now-1]+=nexadv;
                if(cmp(diff[now-1],four[now-1].second,diff[now],four[now].second)){
                    diff[now-1]++;
                    nexadv++;
                }
                if(nexadv==0) break;

                adv=nexadv;
                sum+=adv;
                back[i]=now-1;
                now=now-1;
            }
        }
        res[i+1]=res[i]+sum;
    }

    if(minus==false) reverse(res.begin(),res.end());
}

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

  cin>>N;
  A.resize(N);
  rep(i,N) cin>>A[i];

  vector<ll> lsum(N+1,0),rsum(N+1,0);
  solve(true,lsum);
  solve(false,rsum);

  ll ans=INF;
  for(int i=0;i<=N;i++){
      ll res=lsum[i]+rsum[i];
      res*=2;
      res+=i;
      chmin(ans,res);
  }

  cout<<ans<<endl;

  return 0;
}


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

int main() {
    string a ;
  	char b ='o';
    cin >> a ;
  	int c=0;
    	if( a.at(0) == b ) ++c;
  		if( a.at(1) == b ) ++c;
  		if( a.at(2) == b ) ++c;
    
  	int d = 700 + c* 100;
      
    cout << d << endl;
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int x,a,b; cin >> x >> a >> b;
  if(a >= b){
    cout << "delicious" << endl;
    return 0;
  }
  if(b-a > x){
    cout << "dangerous" << endl;
  } else {
    cout << "safe" << endl;
  }
}


Measured memory_bytes: 3560
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
static const int N=1000;
/*int max(int a,int b){
    if(a>b)return a;else return b;
}*/
int lcs(string X,string Y){
    int c[N+1][N+1];
    int m=X.size();
    int n=Y.size();
    int maxl=0;
    X=' '+X;
    Y=' '+Y;
    for(int i=0;i<=m;i++)c[i][0]=0;
    for(int j=1;j<=n;j++)c[0][j]=0;
    
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(X[i]==Y[j]){
                c[i][j]=c[i-1][j-1]+1;
            }else{
                c[i][j]=max(c[i-1][j],c[i][j-1]);
            }
            maxl=max(maxl,c[i][j]);
        }
    }
    return maxl;
}

int main(){
    string s1,s2;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>s1>>s2;
        cout<<lcs(s1,s2)<<endl;
    }
    return 0;
}

Measured memory_bytes: 7112
n,a,b,c = map(int,input().split())
s = []
for _ in range(n):
    s.append(input())
if a + b + c == 0:
    print('No')
elif a + b + c == 1:
    ans = ''
    for i in range(n):
        if s[i] == 'AB':
            if a == 1 and b == 0:
                a = 0
                b = 1
                ans += 'B'
            elif a == 0 and b == 1:
                a = 1
                b = 0
                ans += 'A'
            else:
                print('No')
                exit()
        elif s[i] == 'BC':
            if b == 1 and c == 0:
                b = 0
                c = 1
                ans += 'C'
            elif b == 0 and c == 1:
                b = 1
                c = 0
                ans += 'B'
            else:
                print('No')
                exit()
        else:
            if a == 1 and c == 0:
                a = 0
                c = 1
                ans += 'C'
            elif a == 0 and c == 1:
                a = 1
                c = 0
                ans += 'A'
            else:
                print('No')
                exit()
    print('Yes')
    for i in range(n):
        print(ans[i])
else:
    ans = ''
    s2 = 'AC'
    for i in range(n):
        s1 = s[i]
        if i != n-1:
            s2 = s[i+1]
        if s1 == 'AB':
            if a >= 1 and b == 0:
                a -= 1
                b = 1
                ans += 'B'
            elif a == 0 and b >= 1:
                a = 1
                b -= 1
                ans += 'A'
            elif a >= 1 and b >= 1:
                if s2 == 'BC':
                    b += 1
                    a -= 1
                    ans += 'B'
                else:
                    a += 1
                    b -= 1
                    ans += 'A'
            else:
                print('No')
                exit()
        elif s1 == 'BC':
            if b >= 1 and c == 0:
                b -= 1
                c = 1
                ans += 'C'
            elif b == 0 and c >= 1:
                b = 1
                c -= 1
                ans += 'B'
            elif b >= 1 and c >= 1:
                if s2 == 'AC':
                    c += 1
                    b -= 1
                    ans += 'C'
                else:
                    b += 1
                    c -= 1
                    ans += 'B'
            else:
                print('No')
                exit()
        else:
            if a >= 1 and c == 0:
                a -= 1
                c = 1
                ans += 'C'
            elif a == 0 and c >= 1:
                a = 1
                c -= 1
                ans += 'A'
            elif a >= 1 and c >= 1:
                if s2 == 'AB':
                    a += 1
                    c -= 1
                    ans += 'A'
                else:
                    a -= 1
                    c += 1
                    ans += 'C'
            else:
                print('No')
                exit()
        s1 = s2
    print('Yes')
    for i in range(n):
        print(ans[i])


Measured memory_bytes: 132448
#include <iostream>
using namespace std;
int main(void){
    int n,p[10000],d1[10000],d2[10000],i,m,a,j;
    while(1){
        cin >> n  ;
        if (n==0){
            break;
        }
        m=0;
        for(i=0;i<n;i++){
            cin >> p[i] >> d1[i] >> d2[i] ;
            a=d1[i]+d2[i];
            if(a>m){
                m=a;
                j=i;
            }    
            
        }    
        cout<< p[j] << " " << m << endl;
    }
}



Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
vector < int > g[maxn];
int num[maxn], num1[maxn];
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
		num[i] = a;
		num1[i] = b;
	}
	for(int i = 1; i <= n; i++){
		sort(g[i].begin(), g[i].end());
	}
	for(int i = 1; i <= m; i++){
		int y = num1[i], z = num[i];
		int x = upper_bound(g[z].begin(), g[z].end(), y) - g[z].begin();
		printf("%06d%06d\n", z, x);
	}
	return 0;
}

Measured memory_bytes: 7808
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
//--
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<cstring>
#include<sstream>
#include<complex>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()

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

int primes[1123456];
int maps[1123][1123];
pii num[1123456];
pii dp[1123][1123];

int main(){
  int i,j,k,m,n,dx[]={1,0,-1,0},dy[]={0,-1,0,1};
  fill(primes+2,primes+1123456,1);
  for(i=2;i<1120000;i++)
    if(primes[i])
      for(j=i*2;j<1120000;j+=i)
        primes[j]=0;
  while(cin>>m>>n){
    if(m==0&&n==0)break;
    fill(maps[0],maps[0]+1123*1123,0);
    fill(num,num+1123456,pii(-1,0));
    fill(dp[0],dp[0]+1123*1123,pii(-1,0));
    int d=0,mx=2,cnt=0,x=520,y=520;
    i=1;
    maps[y][x]=i;
    num[i]=pii(x,y);
    for(i=2;i<=m;i++){
      if(cnt==mx/2){
        cnt=0;
        mx++;
        d=(d+1)%4;
      }
      x+=dx[d];
      y+=dy[d];
  //    cout<<i<<":"<<x<<","<<y<<endl;
      maps[y][x]=i;
      num[i]=pii(x,y);
      cnt++;
    }
    if(primes[n])dp[num[n].Y][num[n].X]=pii(1,n);
    else dp[num[n].Y][num[n].X]=pii(0,0);
    /*cout<<num[n].X<<","<<num[n].Y<<endl;
    for(i=-2;i<=+2;i++){
      for(j=-2;j<=2;j++)
        printf("(%2d,%2d)",dp[num[n].Y+i][num[n].X+j].X,dp[num[n].Y+i][num[n].X+j].Y);
      cout<<endl;
    }*/
    for(i=1;i<1122;i++){
      for(j=1;j<1122;j++){
        if(maps[i][j]<=0)continue;
        pii mxp=pii(-1,0);
        for(k=-1;k<=1;k++)
         mxp=max(dp[i-1][j+k],mxp);
        if(mxp.X<0)continue;
        if(primes[maps[i][j]]){
          mxp.X++;
          mxp.Y=maps[i][j];
        }
        dp[i][j]=mxp;
      }
    }
    pii re=pii(-1,-1);
    rep(i,1123)rep(j,1123)re=max(re,dp[i][j]);
   /* for(i=-2;i<=2;i++){
      for(j=-2;j<=2;j++)
        printf("%2d ",maps[num[n].Y+i][num[n].X+j]);
      cout<<endl;
    }
    for(i=-2;i<=+2;i++){
      for(j=-2;j<=2;j++)
        printf("(%2d,%2d)",dp[num[n].Y+i][num[n].X+j].X,dp[num[n].Y+i][num[n].X+j].Y);
      cout<<endl;
    }*/
    cout<<re.X<<" "<<re.Y<<endl;
  }
  return 0;
}

Measured memory_bytes: 29108
n = int(input())
s = input()
t = input()


def head(u):
    if u[0] == u[1]:
        return 3
    else:
        return 6

def conn(u, v):
    if u[0] == u[1]:
        """
        AX
        AX

        or

        AX
        AY
        """
        return 2
    else:
        if v[0] == v[1]:
            """
            AX
            BX
            """
            return 1
        else:
            if u[0] == v[0] and u[1] == v[1]:
                """
                AA
                BB
                """
                return 1
            else:
                """
                AY
                BX
                """
                return 3

m = 1
u = None
for v in zip(s, t):
    if u is None:
        m = head(v) 
    else:
        m = (m * conn(u, v)) % 1000000007
    u = v
print(m)



Measured memory_bytes: 3064
#include<stack>
#include<cstdio>

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

using namespace std;

const int from[]={0,2,1,1},to[]={1,1,2,0};

stack<int> tray[3];

inline bool move(int i){
	const int &f=from[i],&t=to[i];
	if(!tray[f].empty() && (tray[t].empty() || tray[f].top()>tray[t].top())){
		tray[t].push(tray[f].top());
		tray[f].pop();
		return true;
	}
	return false;
}

inline bool over(){
	return tray[1].empty() && (tray[0].empty() || tray[2].empty());
}

int simulate(int prev){
	for(int k=0;;k++){
		if(over()) return k;
		rep(i,4) if(i!=3-prev && move(i)) { prev=i; break; }
	}
}

int main(){
	for(int n,m;scanf("%d%d",&n,&m),n;){
		rep(k,3){
			while(!tray[k].empty()) tray[k].pop();

			int nk; scanf("%d",&nk);
			rep(j,nk){
				int tmp; scanf("%d",&tmp);
				tray[k].push(tmp);
			}
		}

		if(over()){ puts("0"); continue; }

		int ans=(1<<31)-1;
		rep(i,4){
			stack<int> tmp[3];
			copy(tray,tray+3,tmp);
			if(move(i)) ans=min(ans,simulate(i)+1);
			copy(tmp,tmp+3,tray);
		}
		if(ans>m) ans=-1;
		printf("%d\n",ans);
	}

	return 0;
}

Measured memory_bytes: 828
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      if(a > b){
          System.out.println("a > b");
      }else if(a < b){
          System.out.println("a < b");
      }else{
          System.out.println("a == b");
      }
    }
}



Measured memory_bytes: 26168
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    if (a > b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    string ans;
    rep(i, b) {
        ans += to_string(a);
    }

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

Measured memory_bytes: 256
n = int(input())
f = ['']*(n+2)


def question(a):
    print('?', *a)
    response = input()
    if response == "-1":
        exit()
    return response


def chk(x):
    a = [x+j for j in range(n)]
    if f[x] == '':
        f[x] = question(a)
    return f[x]


bottom = 1
top = n+1
f[bottom] = chk(bottom)
f[top] = chk(top)

while top - bottom > 1:
    middle = (top + bottom)//2
    if chk(middle) == f[top]:
        top = middle
    else:
        bottom = middle

a = [bottom+j for j in range(1, n)]
b = []
for x in range(1, 2*n+1):
    if x not in a and x != bottom and x != bottom+n:
        b.append(x)

ans = []
for x in range(1, 2*n+1):
    if x in a:
        c = b+[x]
    else:
        c = a+[x]
    ans.append(question(c)[0])

print('!', ''.join(ans))


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

using ll = long long;

int main()
{
    int N; ll A, B; cin >> N >> A >> B;
    ll delta = A - B;

    vector<ll> healths(N);
    for (ll& x : healths)
        cin >> x;

    int lower = 1, upper = int(1e9);
    while (lower < upper)
    {
        const int mid = (lower + upper) / 2;

        ll moves = 0;
        for (ll x : healths)
        {
            x -= mid * B;
            if (x >= 0)
                moves += (x + delta - 1) / delta;
        }

        if (moves <= mid)
            upper = mid;
        else
            lower = mid+1;
    }
    cout << lower << endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 100001
#define lowbit(x) x&-x
int c[N*10];
int n,a[N],s[N*10],f[N];
void add(int x){
    for(int i=x;i<=2*N;i+=lowbit(i))c[i]++;
}
ll query(int x){
    ll sum=0;
    for(int i=x;i>0;i-=lowbit(i))sum+=c[i];
    return sum;
}
bool check(int x){
	//x=8;
    for(int i=1;i<=2*N;i++)c[i]=0;
    s[0]=0;
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+(a[i]>=x?1:-1);
    ll sum=0;
    for(int i=0;i<=n;i++){
        sum+=query(s[i]+N);
        add(s[i]+N);
    }
    return sum>=1ll*n*(n+1)/4;
}
int main(){
    in1(n);
    int l=0,r=0;
    for(int i=1;i<=n;i++){
        in1(a[i]);f[i]=a[i];
        //r=max(r,a[i]);
    }r=n;sort(f+1,f+n+1);
    int ans=0;l=1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(f[mid]))l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",f[r]);
}

Measured memory_bytes: 2944
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define N 3
#define N2 9
#define TRUE 1
#define FALSE 0
#define MAX 500000

int V[MAX];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void swap(int x, int y){/*入れ替えます*/
  int z = x;
  x = y;
  y = z;
}

struct Puzzle{/*構造体の宣言*/
  int f[N2];
  int space;
  int path;
};

struct Puzzle Q[MAX];
int head = 0, tail = 0;

void enqueue(struct Puzzle x){/* Q[tail] に x を代入し、tail を１つ増やします。 */
  int next = (tail+1)%MAX;  
  Q[tail] = x;
  tail = next;
}

struct Puzzle dequeue(){/* Q[head] の値を返し、head を１つ増やします。  */
  struct Puzzle t; 
  t = Q[head];
  head = (head+1)%MAX;
  return t;
}

int sort(struct Puzzle p){
  int i, j, key, count, n = 0;
  for(i = 0, key = 1; i < N2; key *= ++i){
    for(j = 0, count = 0; j < i; j++){
      if(p.f[j] < p.f[i])count++;
    }
    n += count * key;
  }
  return n;
}

int isTarget(struct Puzzle p){
  for(int i = 0; i < N2; i++)if(p.f[i] != (i+1))return FALSE;
  return TRUE;
}

int bfs(struct Puzzle s){
  struct Puzzle u, v;
  s.path = FALSE;
  enqueue(s);
  V[sort(s)] = TRUE;
  

  while(head != tail){ 
    u = dequeue();
    if(isTarget(u) == TRUE)return u.path;
    int sx = u.space / N;
    int sy = u.space % N;
    for(int r = 0; r < 4; r++){
      int tx = sx + dx[r];
      int ty = sy + dy[r];
      if(tx < 0 || ty < 0 || tx >= N || ty >= N)continue;
      v = u;
      int num = v.f[u.space];
      v.f[u.space] = v.f[tx * N + ty];
      v.f[tx * N + ty] = num;
      v.space = tx * N + ty;
      if(V[sort(v)] != TRUE){
	V[sort(v)] = TRUE;
	v.path++;
	enqueue(v);
      }
    }
  }

  return -1;
}

int main(){
  struct Puzzle in;

  for(int i = 0; i < N2; i++){
    scanf("%d",&in.f[i]);
    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }

  int ans = bfs(in);
  printf("%d\n",ans);

  return 0;
}



Measured memory_bytes: 10992
import sys
H,W = map(int, input().split())
C = [list(map(int,i.split())) for i in sys.stdin.readlines()]
G =[[None for i in range(W)] for j in range(H)]

for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
  else: G[i][0] = 0


for i in range(1,H):
    for j in range(1,W):
        if C[i][j] == 0:
            G[i][j] = min(G[i-1][j], G[i][j-1],G[i-1][j-1]) + 1
        else:G[i][j] = 0

ans = max(max(i) for i in G) ** 2
print(str(ans))

Measured memory_bytes: 57784
function Main(input) {
    input = input.split("\n");
    for(var i=0;i<10;i++){
        input[i]=parseInt(input[i], 10);
    }
    input.sort(descendingOrder);
    for(i=0;i<3;i++){
        console.log(input[i]);
    }
}
//??°????????????????????¢??°??¨(??????)
function ascendingOrder(val1,val2){
    return val1 - val2;
}
//??°????????????????????¢??°??¨(??????)
function descendingOrder(val1,val2){
    return val2 - val1;
}


//???????????°??¨
function debug(){
	var input = document.getElementById("input").value;
	Main(input);
}

//?????????????????\??????????????????
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 15512
private fun readStrings() = readLine()!!.split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main(args: Array<String>) {
    val (a, b) = readInts()
    println(if (a + b == 15) "+" else if (a * b == 15) "*" else "x")
}

Measured memory_bytes: 37904
#include <stdio.h>

#define MOD 2019

int main(void) {
	int l, r;
	scanf("%d%d", &l, &r);

	if (r-l+1 >= MOD) {
		puts("0");
		return 0;
	}
	int dist = (r-l+1) % MOD;

	l %= MOD;
	r %= MOD;

	if (r < l) {
		puts("0");
		return 0;
	}

	int min = -1;
	for (int i = 0; i < dist; i++) {
		for (int j = i+1; j < dist; j++) {
			int a = (l+i)%MOD;
			int b = (l+j)%MOD;
			if (min == -1 || (a*b)%MOD < min) min = (a*b)%MOD;
		}
	}

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


Measured memory_bytes: 128
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N=input()
fn = 0
for n in N:
    fn += int(n)

yn(int(N)%fn==0)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
   int n,t; cin>>n>>t;
   ll p=0;
   int arr[n]; for(int i=0;i<n;i++)cin>>arr[i];
   for(int i=1;i<n;i++){
    if(arr[i]-arr[i-1]<t){
        p=p+(arr[i]-arr[i-1]);
    }
    else p=p+t;
   } cout<<p+t;
}


Measured memory_bytes: 4308
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define eb(t) emplace_back(t)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;

void solve(){

    ll a[4][4];
    rep(i,3){
        rep(j,3){
            cin >> a[i][j];
        }
    }
    ll n;
    cin >> n;
    ll b[12];
    rep(i,n){
        cin >> b[i];
        rep(x,3){
            rep(y,3){
                if(a[x][y]==b[i]) a[x][y]=-1;
            }
        }
    }

    bool ans = false;
    rep(i,3){
        if(a[i][0]==-1 && a[i][1]==-1 && a[i][2]==-1) ans = true;
        if(a[0][i]==-1 && a[1][i]==-1 && a[2][i]==-1) ans = true;
    }
    if(a[0][0]+a[1][1]+a[2][2]==-3) ans = true;
    if(a[2][0]+a[1][1]+a[0][2]==-3) ans = true;

    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
 
}

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


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


#include <assert.h>    // LON
#include <math.h>    // sqrt()


using namespace std;
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = 10e15;
const ll MINF = -10e10;
const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//typedef priority_queue<P, vector<P>, greater<P>> PQ_ASK;
const int mod = 1000000007;

class Field {
public:
    vector<vector<char>> field;

    Field(int h, int w) {
        field = vector<vector<char>>(w, vector<char>(h));
    }

    char get(int x, int y) {
        if (x == -1 || y == -1) {
            return '.';
        }
        if (x == field.size() || y == field[x].size()) {
            return '.';
        }
        return field[x][y];
    }

};


int main() {
    int h, w;
    cin >> h >> w;
    Field field(h, w);
    rep(y, h) rep(x, w) {
            cin >> field.field[x][y];
        }

    rep(y, h) {
        rep(x, w) {
            if (field.get(x, y) == '#') {
                cout << '#';
                continue;
            }

            int now = 0;
            if (field.get(x - 1, y - 1) == '#') {
                now++;
            }
            if (field.get(x, y - 1) == '#') {
                now++;
            }
            if (field.get(x + 1, y - 1) == '#') {
                now++;
            }

            if (field.get(x - 1, y) == '#') {
                now++;
            }
            if (field.get(x + 1, y) == '#') {
                now++;
            }

            if (field.get(x - 1, y + 1) == '#') {
                now++;
            }
            if (field.get(x, y + 1) == '#') {
                now++;
            }
            if (field.get(x + 1, y + 1) == '#') {
                now++;
            }
            cout << now;
        }
        cout << endl;
    }
}


Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    flag = True

    for a in A:
        if a%2==0:
            if not (a%3==0 or a%5==0):
                flag = False
   
    if flag:
        print('APPROVED')
    else:
        print('DENIED')

if __name__ == '__main__':
    resolve()


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

int box[100001];

int get_gcd(int a, int b)
{
    while (b != 0)
    {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

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

    int n, k, a, gcd, max = 0;

    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        box[i] = a;
        if (a > max)
            max = a;
        if (a == k)
        {
            cout << "POSSIBLE\n";
            return 0;
        }
    }

    sort(box, box + n);

    gcd = box[0];

    for (int i = 1; i < n; ++i)
        gcd = get_gcd(gcd, box[i]);


    if (k % gcd != 0 || k > max)
        cout << "IMPOSSIBLE\n";
    else
        cout << "POSSIBLE\n";
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin >> s;
    long K;
    cin >> K;
    int n = s.length();
    int cnt=0;
    int tmp=1;
     for(int i=0;i<n-1;i++){
        if(s[i]==s[i+1]) tmp++;
        else{
            cnt+=tmp/2;
            tmp=1;
        }
    }
    if(s[n-2]==s[n-1]) cnt+=tmp/2;
    string s2 = s+s;
    //cout << s2 << endl;
    int tmp2 = 0;
    int cnt2=0;
    tmp=1;
    for(int i=0;i<2*n-1;i++){
        if(s2[i]==s2[i+1]) tmp++;
        else{
            cnt2+=tmp/2;
            tmp=1;
        }
    }
    if(s2[2*n-2]==s2[2*n-1]) cnt2+=tmp/2;
    tmp=1;
    string s3=s+s+s;
    int tmp3 = 0;
    int cnt3=0;
    for(int i=0;i<3*n-1;i++){
        if(s3[i]==s3[i+1]) tmp++;
        else{
            cnt3+=tmp/2;
            tmp=1;
        }
    }
    if(s2[3*n-2]==s3[3*n-1]) cnt3+=tmp/2;
    int interval = cnt2-cnt;
    long ans = cnt+(K-1)*interval;
    bool serial = true;
    for(int i=0;i<n-1;i++){
        if(s[i]!=s[i+1]) serial = false;
    }
    if(n==1) cout << K/2 << endl;
    else if(serial) cout << n*K/2 <<endl;
    else cout << ans << endl;
}

Measured memory_bytes: 632
import java.lang.Math

fun main(args: Array<String>)
{
    val (a, p) = readInts()

    val m = 3 * a + p
    val pie = m / 2
    println(pie)
}

fun readInts(): List<Int> = readLine()!!.split(" ").map(String::toInt)
fun readLongs(): List<Long> = readLine()!!.split(" ").map(String::toLong)

fun readIntArr(): IntArray = readLine()!!.split(" ").map(String::toInt).toIntArray()
fun readLongArr(): LongArray = readLine()!!.split(" ").map(String::toLong).toLongArray()

fun readIntArrS(): IntArray = readLine()!!.split(" ").map(String::toInt).toIntArray().sortedArray()
fun readLongArrS(): LongArray = readLine()!!.split(" ").map(String::toLong).toLongArray().sortedArray()

fun readIntArrSD(): IntArray = readLine()!!.split(" ").map(String::toInt).toIntArray().sortedArrayDescending()
fun readLongArrSD(): LongArray = readLine()!!.split(" ").map(String::toLong).toLongArray().sortedArrayDescending()

fun readString() = readLine()!!


Measured memory_bytes: 36148
#include <bits/stdc++.h>
#include <atcoder/math>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  using namespace atcoder;
  long long n;
  cin>>n;
  
  vector<long long> divs;
  for(long long k = 1; k <= sqrt(2 * n); k++){
    if((2 * n) % k != 0) continue;
    divs.push_back(k);
    divs.push_back((2*n)/k);
  }
  sort(ALL(divs));
  
  long long ans = INF;
  for(long long x: divs){
    vector<long long> rems = {0, -1};
    vector<long long> mods = {x, (2*n)/x};
    pair<long long, long long> p = crt(rems, mods);
    long long y = p.first, z = p.second;
    if(y == 0 && z == 0) continue;
    if(y == 0) y = z;
    ans = min(ans, y);
  }
  
  cout << ans << endl;  
  return 0;
}

Measured memory_bytes: 3848
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
  int n;
  cin >> n;
  long a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  
  int p[n];
  for (int i = 0; i < n; i++) {
  	p[i] = (i % 2 == 0) ? 1 : -1;
  }
	
  long ans = 0;
  for (int i = 0; i < n; i++) {
  	ans += p[i] * a[i];
  }
  cout << ans << " " ;
  for (int i = 0; i < n - 1; i++) {
    ans = ans * (-1) + 2 * a[i];
    cout << ans << " " ;
  }

  return 0;
}

Measured memory_bytes: 2432
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
s=[[0,0] for i in range(n)]
s[0][0]=min(a[0],b[0])
s[0][1]=min(a[1],b[0]-s[0][0])
for i in range(1,n):
	s[i][0]=min(a[i]-s[i-1][1],b[i])
	s[i][1]=min(a[i+1],b[i]-s[i][0])

sum=0
for i in range(n):
	sum+=s[i][0]+s[i][1]
print(sum)

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

string t[15]={
  "Rock",
  "Fire",
  "Scissors",
  "Snake",
  "Human",
  "Tree",
  "Wolf",
  "Sponge",
  "Paper",
  "Air",
  "Water",
  "Dragon",
  "Devil",
  "Lightning",
  "Gun"
};

int search(string s){
  for(int i=0;i<15;i++)if(t[i]==s)return i;
  assert(0);
  return 0;
}

int check(int a,int b){
  if(a==b)return 0;
  for(int i=1;i<=7;i++)if( (a+i)%15==b )return 1;
  return -1;
}

int main(){
  int n;
  while(1){
    cin>>n;
    if(n==0)break;
    vector<string> t(n);
    vector<int> u(n);
    for(int i=0;i<n;i++){
      cin>>t[i];
      u[i]=search(t[i]);
    }
    
    string ans="Draw";
    for(int i=0;i<n;i++){
      int A=0,B=0;
      for(int j=0;j<n;j++){
        int k=check(u[i],u[j]);
        if(k==1)A++;
        if(k==-1)B++;
      }
      if(A>0&&B==0)ans=t[i];
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

using namespace std;

#define reps(i, n, m) for (int i = (int) (n); i < (int) (m); i++)
#define rep(i, n) reps(i, 0, (n))
#define all(v) (v).begin(), (v).end()

int main() {
    unsigned int n; cin >> n;
    bitset<32> b(n);
    cout << b << endl;
    cout << ~b << endl;
    cout << (b << 1) << endl;
    cout << (b >> 1) << endl;
}


Measured memory_bytes: 3144
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
    char a[3];
    int count=0;
    for(int i=0;i<3;i++){
        cin>>a[i];
        if(a[i]=='1')
            count++;
    }
    cout<<count<<endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){

  int n;
  while(cin >> n){
    vector<int>co;
    int i;
    int no;
    if(n==0)
      break;
    for(i=0;i<10;i++)
      co.push_back(0);
    for(i=0;i<n;i++){
      cin >> no;
      co[no]++;
    }
    for(i=0;i<10;i++){
      int j;
      for(j=0;j<co[i];j++)
	cout << '*';
      if(co[i]==0)
	cout << '-';
      cout << endl;
    }
  }
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
const ll INF = 1e18;
#define print(x) cout << (x) << endl;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> d(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> d.at(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans += d.at(i) * d.at(j);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define F first
#define S second
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

vector<string> split(const string &str, char delim){
  vector<string> res;
  size_t current = 0, found;
  while((found = str.find_first_of(delim, current)) != string::npos){
    res.push_back(string(str, current, found - current));
    current = found + 1;
  }
  res.push_back(string(str, current, str.size() - current));
  return res;
}

int main(){
	map<string,li> table;
	string sin;
	string longest="";
	getline(cin,sin);
	vector<string> ss=split(sin, ' ');
	
	rep(i,sz(ss)){
		table[ss[i]]++;
		if(sz(ss[i])>sz(longest))longest=ss[i];
	}
	
	vector<pair<li,string> > s;
	
	for(map<string, li>::iterator it=table.begin(); it!=table.end(); it++){
		s.pb(mp(it->S, (it->F)));
	}
	
	sort(allof(s) ,greater<pair<li,string> >());
	
	//rep(i,sz(s)){p2(s[i].F, s[i].S);}
	
	cout<<s[0].S<<" "<<longest<<endl;
	
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include<string>
#include<cmath>
#include<ciso646>
#include<cstring>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;
ll Max = 10 + 1e8;
int main()
{
	int n;
	cin >> n;
	map<ll, ll> mp;
	rep(i, n) {
		ll drn; cin >> drn;
		mp[drn]++;
		if (mp[drn] != 1) {
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
}


Measured memory_bytes: 15960