akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<numeric>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<map>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define VE vector<int>
#define VEP vector<pair<int,int>>
#define llong long long
#define pb(a) push_back(a)
using namespace std;
const vector<VE> DIR{ {-1,0},{1,0},{0,-1},{0,1} };
const int z = 1000000007;
long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
int main() {
    int n;
    cin >> n;
    vector<bool> color(n);
    string str;
    cin >> str;
    int red_cnt = 0;;
    REP(i, n) {
        if (str[i] == 'R') {
            red_cnt++;
            color[i] = true;
        }
        else
            color[i] = false;
    }
    int lhs = 0, rhs = n - 1;
    int swap_cnt = 0;
    while (lhs < rhs) {
        while(color[lhs] == true) {
            lhs++;
            if (lhs >= n - 1)
                break;
        }
        while(color[rhs] == false) {
            rhs--;
            if (rhs <= 0)
                break;
        }
        if (lhs < rhs) {
            color[lhs] = true;
            color[rhs] = false;
            lhs++;
            rhs--;
            swap_cnt++;
        }
    }
    int ans = 0;
    if (swap_cnt < min(n - red_cnt, red_cnt))
        ans = swap_cnt;
    else
        ans = min(n - red_cnt, red_cnt);
    cout << ans << endl;
    return 0;
    
}


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

int main() {
        const string ok = "Possible";
        const string ng = "Impossible";

        int N, L;
        cin >> N >> L;
        vector<int> a(N);
        for(int i = 0; i < N; ++i) {
                cin >> a[i];
        }

        int key = -1;
        for(int i = 0; i < N - 1; ++i) {
                if(L <= a[i] + a[i + 1]) {
                        key = i;
                        break;
                }
        }

        if(key == -1) {
                cout << ng << endl;
                return 0;
        }

        cout << ok << endl;
        for(int i = 0; i < key; ++i) {
                cout << i + 1 << endl;
        }
        for(int i = N - 2; i >= key; --i) {
                cout << i + 1 << endl;
        }
}



Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c,d,e,f;
  cin >> a >> b >> c;
  d = b/a;
  e = (d+1)*a;
  f = b%a;
  if ((e <= c) || (f == 0)){
    cout << "OK";
  }else{ 
    cout << "NG";
  }
} 

Measured memory_bytes: 3632
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>

using namespace std;


long MOD = 1000000007;

/*class A_val{
public:
    long val;
    int p_m;
    A_val(long v, int p_m) : val(v), p_m(p_m){}

    friend bool operator <(const A_val& m1, const A_val& m2)
    { return m1->val < m2->val; };

};*/

typedef pair<long, int> A_val;

long modpow(long a, long b){
    if(b == 1){
        return a % MOD;
    }
    if(b == 0){
        return 1;
    }
    long res = b/2;
    long rem = b%2;
    long p = modpow(a, res) % MOD;
    long pp = (p*p) % MOD;
    if(rem == 1){
        return (pp * a) % MOD;
    }else{
        return pp;
    }
}


long modinv(long a){
    return modpow(a, MOD-2);
}

void retSmallerstMinus(vector<A_val>& as, int K){
//    sort(as.begin(), as.end(), less<A_val>());
    long mul=1;
    int N = as.size();
    for(int i=N-1;i>=(N-K);i--){
        mul *= as[i].first;
        mul %= MOD;
    }
    long ans = (-mul + 2 * MOD) % MOD;
    cout << ans << endl;
    return;
}

int main(){
    int N, K;
    cin >> N >> K;
    vector<A_val> as;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        auto v = make_pair(abs(a), a==0 ? 0 : a/abs(a));
        as.push_back(v);
    }
    sort(as.begin(), as.end(), greater<A_val>());
    long fugo=1;
    long mul = 1;
    for(int i=0;i<K;i++){
        mul *= as[i].first;
        mul %= MOD;
        fugo *= as[i].second;
    }
    if(fugo > 0){
        cout << mul << endl;
        return 0;
    }else if(fugo == 0){
        cout << 0 << endl;
        return 0;
    }else{
        int i=K-1;
        int hikumns,hikuplus;
        int tasumns,tasuplus;
        while(i>=0 && as[i].second == 1){
            i--;
        }
        hikumns = i;
        i=K-1;
        while(i>=0 && as[i].second == -1){
            i--;
        }
        hikuplus = i;
        i=K;
        while(i < N && as[i].second == -1){
            i++;
        }
        tasuplus = i;
        i =K;
        while(i < N && as[i].second == 1){
            i++;
        }
        tasumns = i;


        if(hikuplus == -1 || tasumns == N){
            if(tasuplus == N){
                retSmallerstMinus(as, K);
                return 0;
            }else{
                mul *= as[tasuplus].first;
                mul %= MOD;
                mul *= modinv(as[hikumns].first);
                mul %= MOD;
                cout << mul << endl;
                return 0;
            }
        }

//        if(as[tasuplus].first / as[hikumns].first > as[tasumns].first / as[hikuplus].first){
        if(as[tasuplus].first * as[hikuplus].first > as[tasumns].first * as[hikumns].first){
            mul *= as[tasuplus].first;
            mul %= MOD;
            mul *= modinv(as[hikumns].first);
            mul %= MOD;
        }else{
            mul *= as[tasumns].first;
            mul %= MOD;
            mul *= modinv(as[hikuplus].first);
            mul %= MOD;
        }
        cout << mul << endl;

    }


    return 0;
}


Measured memory_bytes: 6992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
int A[100010], B[100010];
ll sum, tmp, cnt;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    sum += A[i];
  }  
  tmp = (ll)N * (N + 1) / 2;
  if (sum % tmp != 0) {
    cout << "NO" << endl;
    return 0;
  }
  cnt = sum / tmp;
  for (int i = 0; i < N; i++) {
    B[i] = A[i] - A[(i - 1 + N) % N] - cnt;
    if (B[i] > 0 || abs(B[i]) % N != 0) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

  return 0;
}

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

int main(){
    int N, A, B;
    scanf("%d%d%d", &N, &A, &B);

    array<int, 3> p({0, 0, 0});
    for(int i = 0, c; i < N; ++i){
        scanf("%d", &c);
        ++p[(c > A) + (c > B)];
    }
    
    printf("%d", *min_element(p.begin(), p.end()));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 998244353;

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[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 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];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }


  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  SegmentTree<int> seg(n, [](int a, int b) { return max(a, b); }, -1);
  vector<pair<ll, ll>> R(n);
  rep(i, n) cin >> R[i].first >> R[i].second;
  sort(all(R));
  vector<int> next(n);
  rrep(i, n) {
    int ne = upper_bound(all(R), make_pair(R[i].first+R[i].second-1, longinf)) - begin(R);
    seg.update(i, ne);
    next[i] = seg.query(i, ne);
    seg.update(i, next[i]);
  }
  vector<ll> dp(n+1);
  dp[0] = 1;
  rep(i, n) {
    (dp[i+1] += dp[i]) %= mod;
    (dp[next[i]] += dp[i]) %= mod;
  }
  cout << dp[n] << "\n";
  return 0;
}


Measured memory_bytes: 10868
#include <stdio.h>

int main(void)
{
  int N;
  scanf("%d", &N);
  
  int a[N];
  int sum = 0;
  int num;
  double ava;
  int ans = 0;
  
  int i;
  for( i = 0; i < N; i++ ){
    scanf("%d", &a[i]);
    sum += a[i];
  }
  
  ava = (double)sum / (double)N;
  if( ava > 0 ) num = (int)(ava + 0.5);
  else{         num = (int)(ava - 0.5);}
  
  
  
  for( i = 0; i < N; i++ ){
    ans += (a[i]-num)*(a[i]-num);
  }
  
  printf("%d\n", ans);
  
  return 0;
 
}       
       

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

#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define sl1(a)  scanf("%lld",&a)
#define sl2(a,b)  scanf("%lld %lld",&a,&b)
#define sl3(a,b,c)  scanf("%lld %lld %lld",&a,&b,&c)
#define PI 3.1415926535897932

int main(){
    int mod=1000000007;
    int n,m,ans;
    char w[1001];
    scanf("%s",w);
    sc1(n);
    rep(i,n) {
        int a,b;
        char s[1001],t[1001];
        scanf("%s",s);
        if (!strcmp("replace",s)) {
            sc2(a,b);
            scanf("%s",t);
            for (int j=a;j<=b;j++) w[j]=t[j-a];
        } else if (!strcmp("reverse",s)) {
            sc2(a,b);
            strcpy(t,w);
            int c=b;
            for (int j=a;j<=b;j++) {
                w[j]=t[c];
                c--;
            }
        } else {
            sc2(a,b);
            for (int j=a;j<=b;j++) printf("%c",w[j]);
            puts("");
//            printf("%s\n",w);
        }
    }
    return 0;
}



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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

int main(){
    int n;
    cin>>n;
    Vi h(n);
    REP(i,n){
        cin>>h[i];
    }

    int max_h = 0;
    int cnt = 0;
    REP(i,n){
        if(max_h<=h[i]) cnt++;
        max_h = max(max_h,h[i]);
    }

    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<climits>
using namespace std;
#define int long long
// int solve(vector<int>&weights,vector<int>&values,int index,int max_weight,vector<vector<int>>&dp){
// 	if(max_weight<0)return LLONG_MIN;
// 	if(index==0||max_weight==0){
// 		return 0;
// 	}
// 	if(dp[index][max_weight]!=-1)return dp[index][max_weight];
// 	return dp[index][max_weight]=max(values[index-1]+solve(weights,values,index-1,max_weight-weights[index-1],dp),solve(weights,values,index-1,max_weight,dp));
// }
int32_t main(){
	int n,w;
	cin>>n>>w;
	vector<int>weights(n);
	vector<int>values(n);
	int sum=0;
	// cout<<"Helo";
	for(int i=0;i<n;i++){
		cin>>weights[i];
		cin>>values[i];
		sum+=values[i];
	}
	// cout<<sum<<endl;
	// vector<vector<int>>dp(n+1,vector<int>(sum+1,0));
	// // vector<vector<int>>dp(n+1,vector<int>(sum+1,0));
	int dp[n+1][sum+1];
	memset(dp,0,sizeof(dp));
	
	for(int i=1;i<=sum;i++)dp[0][i]=INT_MAX;
	for(int i=1;i<=n;i++){
		// vector<int>temp(w+1);
		// temp[0]=0;
		for(int j=1;j<=sum;j++){
			// temp[j]=dp[j];
			dp[i][j]=dp[i-1][j];
			if(j>=values[i-1]){

				dp[i][j]=min(dp[i][j],weights[i-1]+dp[i-1][j-values[i-1]]);
			}
		}

	}
	// cout<<dp[w]<<endl;
	int ans=0;
	for(int i=1;i<=sum;i++)if(dp[n][i]<=w)ans=i;
	cout<<ans<<endl;
}

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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll N;
    ll temp;
    ll mini = LONG_LONG_MAX;
    cin >> N;
    temp = sqrt(N);
    for(ll i = 1;i <= temp;i++) {
        if(N % i == 0) {
            ll temp = N / i;
            if(temp <= N) {
                ll distance = i + temp - 2;
                mini = min(mini, distance);
            }
        }
    }
    cout << mini << endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    s=input()
    k=int(input())
    if s.count(s[0])==len(s):
        print(len(s)*k//2)
    else:
        ans=0
        cnt=1
        res=[0,0]
        t=s+"X"
        flg=0
        for i in range(len(s)):
            if t[i]==t[i+1]:
                cnt+=1
            else:
                if flg==0:
                    res[0]=cnt
                    flg=1
                elif i==len(s)-1:
                    res[1]=cnt
                ans+=cnt//2
                cnt=1
        ans*=k
        if s[0]==s[-1] and res[0]%2==1 and res[1]%2==1:
            ans+=k-1
        print(ans)
if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#define MAXN 110000
int n,q,pa[MAXN],vis[MAXN];
int main()
{
    pa[1]=1;
    while (~scanf("%d%d",&n,&q)&&(n||q))
    {
        for (int i=2;i<=n;i++) scanf("%d",&pa[i]);
        char s[3];
        int id;
        long long ans=0;
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        while (q--)
        {
            scanf("%s%d",s,&id);
            if (s[0]=='Q')
            {
                while (!vis[id]) id=pa[id];
                ans+=id;
            }
            else vis[id]=1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Measured memory_bytes: 1864
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

int func(int num){
    int cnt=0;
    while(num>0){
        num/=10;
        cnt++;
    }
    return cnt;
}

int func2(int num){
    int cnt=0;
    int x=0;
    while(num>0){
        x=num;
        num/=10;
        cnt++;
        
    }
    return x;
}

signed main(){
   int x;
   cin>>x;
   for (int i = 1; i <= 10000; i++)
   {
    if(100*i<=x && x<=105*i){
        cout<<1<<endl;
        return 0;
    }
   }
   cout<<0<<endl;
    return 0;
}

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

#define REP(n) for(int i = 0;i < n;i++)
using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> a(n);
    
    REP(n){
        cin >> a[i];
    }
    sort(a.begin(),a.end());

    cout << a[n-1]-a[0] << endl;
   
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 150
#define NIL -1
int graph[MAX][MAX];
int d[MAX];
int n;


int Que[10000];
int head=0, tail=0;

void enQue(int q){
  Que[head]=q;
  head++;
}

int deQue(void){
  tail++;
  return Que[tail-1];
}

int size(void){
  return head-tail;
}


void bfs(int i){
  int j;
  for(j=0; j<n; j++){
    if(graph[i][j]==1 && d[j]==NIL){
      d[j]=d[i]+1;
      enQue(j);
    }
  }
}

int main(){
  int u,k,i,j,v;
  scanf("%d",&n);
  for(i=0;i<MAX;i++) d[i]=NIL;
  for(i=0;i<n;i++){
    scanf("%d",&u);
    scanf("%d",&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      graph[u-1][v-1]=1;
    } 
  }
  d[0]=0;
  bfs(0);
  while(size()!=0){
    bfs(deQue());
  }
  for(i=0;i<n;i++){
    printf("%d %d\n",i+1,d[i]);
  }
return 0;
}

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

int main(void) {
  string S;
  cin >> S;
  bool flag = S[0] == 'A';
  flag = flag && islower(S[1]);
  int cnt = 0;
  for (int i = 2, len = S.length(); i < len; i++) {
    if (isupper(S[i])) {
      if (S[i] == 'C' && i < (int)S.length() - 1) {
        cnt++;
      } else {
        flag = false;
        break;
      }
    }
  }
  flag = flag && cnt == 1;
  cout << (flag ? "AC" : "WA") << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    vector<vector<ll>>A(N,vector<ll>(N));

    ll ans=0;
    rep(i,N){
        rep(j,N){
            cin>>A[i][j];
            ans+=A[i][j];
        }
    }
    //ans/=2;

    
    rep(i,N){ 
        rep3(j,0,N){
            rep(k,N){
            if(k==j)continue;
            if(k==i)continue;
            if(A[i][j]==A[i][k]+A[k][j]){
                //cout<<i<<" "<<k<<" "<<j<<endl;
                //cout<<ans<<endl;
                ans-=A[i][j];
                break;
            }else if(A[i][j]>A[i][k]+A[k][j]){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    }
    cout << ans/2 << endl;


    return 0;
    

}

Measured memory_bytes: 4348
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

int W, H;
vector<string> smap;
int map[25][25];
int cpmap[25][25];

struct Tile {
	int x, y;
	Tile() {};
	Tile(int _x, int _y) : x(_x), y(_y) {}
};

struct State {
	int x, y, d;
	State() {};
	State(int _x, int _y, int _d) : x(_x), y(_y), d(_d) {}
};

int DX[4] = {-1, 1, 0, 0};
int DY[4] = {0, 0, -1, 1};

int search(int sx, int sy, int ex, int ey) {
	// map copy
	memset(cpmap, 0, sizeof(cpmap));
	for (int i=0; i<H; i++) for (int j=0; j<W; j++) cpmap[i][j] = map[i][j];
	
	// search start
	int res = 1e9;
	queue<State> q;
	q.push(State(sx, sy, 0));
	
	while (!q.empty()) {
		State s = q.front(); q.pop();
		
		if (s.x == ex && s.y == ey) {
			res = min(res, s.d);
			continue;
		}
		
		if (res <= s.d) continue;
		
		for (int d = 0; d < 4; d++) {
			if (!(0 <= s.x + DX[d] && s.x + DX[d] < W && 0 <= s.y + DY[d] && s.y + DY[d] < H)) continue;
			if (cpmap[s.y + DY[d]][s.x + DX[d]] != -1) {
				cpmap[s.y + DY[d]][s.x + DX[d]] = -1;
				q.push(State(s.x + DX[d], s.y + DY[d], s.d + 1));
			}
		}
	}
	
	return res;
}

int solver() {
	memset(map, 0, sizeof(map));
	int yogore = 1;
	int sx, sy;
	vector< Tile > YG;
	
	for (int i=0; i<H; i++) {
		for (int j=0; j<W; j++) {
			if (smap[i][j] == '.') map[i][j] = 0;
			else if (smap[i][j] == '*') {
				map[i][j] = yogore++;
				YG.push_back(Tile(j, i));
			}
			else if (smap[i][j] == 'x') map[i][j] = -1;
			else if (smap[i][j] == 'o') {
				map[i][j] = 0;
				sy = i; sx = j;
			}
		}
	}
	
	// dist matrix    start:0   YG:1~yogore-1
	vector< vector<int> > dist(yogore, vector<int>(yogore, 0));
	
	// start to yogore
	for (int i=1; i<yogore; i++) {
		dist[0][i] = search(sx, sy, YG[i-1].x, YG[i-1].y);
		if (dist[0][i] >= 1e9) return -1;	// 到達できないゴミがある
	}
	
	// 各ゴミから他のゴミへの距離
	for (int i=1; i<yogore; i++) {
		for (int j=i+1; j<yogore; j++) {
			dist[i][j] = dist[j][i] = search(YG[i-1].x, YG[i-1].y, YG[j-1].x, YG[j-1].y);
		}
	}
	
	// dist についてTSPを解く　スタートは　0
	int res = 1e9;
	
	vector<int> order(yogore-1);
	for (int i=0; i<yogore-1; i++) order[i] = i + 1;
	
	do {
		// 現在の訪問順序での総距離を求める
		int cur = 0;
		cur += dist[0][order[0]];
		for (int i=1; i<yogore-1; i++) {
			cur += dist[order[i-1]][order[i]];
		}
		
		res = min(res, cur);
	} while (next_permutation(order.begin(), order.end()));
	
	return res;
}

int main() {
	while (1) {
		cin >> W >> H; if (W==0 && H==0) break;
		smap.assign(H, "");
		for (int i=0; i<H; i++) cin >> smap[i];
		
		cout << solver() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1252
#https://atcoder.jp/contests/abc142/tasks/abc142_d

def prime_factorize(n):
    a = []
    a.append(1)
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    
    b = [[],[]]
    cnt = 1
    for i in range(len(a)+1):
        if i > 0 and i < len(a):
            if a[i] == a[i-1]:
                cnt += 1
            else:
                b[0].append(a[i-1])
                b[1].append(cnt)
                cnt = 1
        if i == len(a) and i > 0:
            b[0].append(a[i-1])
            b[1].append(cnt)
        elif i == len(a) and i == 0:
            b[0].append(a[i])
            b[1].append(cnt)
    return a, b


a,b = map(int,input().split())

apa, ap = prime_factorize(a)
bpa, bp = prime_factorize(b)

c = [[],[]]

for i in range(len(ap[0])):
    for j in range(len(bp[0])):
        if ap[0][i] == bp[0][j]:
            c[0].append(ap[0][i])
            c[1].append(min(ap[1][i],bp[1][j]))
            break

print(len(c[0]))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
vector<ll> num;
vector<ll> p;

//レベルN層の左からXにあるPの数
ll findNum(int N, ll X)
{
    if(N==0)
        return 1;

    if(X==1)
        return 0;
    else if(X<=num[N]/2)
    {
        return findNum(N-1, X-1);
    }
    else if(X==(num[N]/2+1))
    {
        return 1+findNum(N-1, X-2);
    }

    return 1 + p[N-1] + findNum(N-1, X-2-num[N-1]);

}

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

    num.resize(50);
    p.resize(50);

    num[0] = 1;
    p[0] = 1;
    for(int i=0; i<50; ++i)
    {
        num[i+1]= 2 * num[i] + 3;
        p[i+1] = 2 * p[i] + 1;
    }

    ll ans = findNum(N, X);

    cout<<ans<<endl;


    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
	val (x, y) = readLine()!!.split(" ").map{it.toInt()}
	
  	if ((y-2*x)/2 <= x && (y-2*x)/2 >= 0 && (y-2*x)%2 == 0) println("Yes") else println("No")
}

Measured memory_bytes: 36308
#include<bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int> > V;
int main()
{
    cin >> N;
    V.resize(N);
    for(int i=0; i<N; ++i)
    {
        cin >> V[i].first >> V[i].second;
        ++V[i].second;
    }

    int ans = 0;

    // case #1 rightmost L, leftmost R in same group
    int maxv=0, maxi=0, rightl=0, leftr=(int)1e9+1;
    for(int i=0; i<N; ++i)
    {
        maxv = max(V[i].second-V[i].first, maxv);
        if(maxv==V[i].second-V[i].first) maxi = i;
    }
    for(int i=0; i<N; ++i)
    {
        if(i==maxi) continue;
    
        rightl = max(rightl, V[i].first);
        leftr = min(leftr, V[i].second);
    }
    ans = maxv + max(leftr-rightl, 0);


    // case #2 rightmost L, leftmost R diff group
    
    sort(V.begin(), V.end());
    sort(V.begin(), V.end()-1, [&](pair<int, int> a, pair<int, int> b)
    {
        return a.first > b.first;
    });

    multiset<int> Lv, Rv;
    for(int i=0; i<N-1; ++i)
    {
        Lv.insert(V[i].first);
        Rv.insert(V[i].second);
    }
    int ls = V[N-1].first, rs = V[N-1].second;

    for(int i=0; i<N-2; ++i)
    {
        rs=min(rs, V[i].second);
        Lv.erase(Lv.find(V[i].first));
        Rv.erase(Rv.find(V[i].second));
        ans = max((rs-ls)+*Rv.begin()-*Lv.rbegin(), ans);
    }
    cout << ans << endl;
}











Measured memory_bytes: 10368
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long int
const int MAX_V = 100010;

vector<int> G[MAX_V];
int V;

int color[MAX_V];
int black;
int white;

bool dfs(int v, int c) {
    color[v] = c;
    if (c == 1) black++;
    if (c == -1) white++;
    rep(i, G[v].size()) {
        if (color[G[v][i]] == c) return false;
        if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
    }
    return true;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int M;
    cin >> V >> M;
    rep(i, M) {
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    if (dfs(1,1) == true) {
        cout << black*white - M << endl;
    } else {
        cout << V*(V-1)/2 - M << endl;
    }

    return 0;
}


Measured memory_bytes: 7424
n = int(input())

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

can4 = 0
even = 0
odd = 0

for i in a:
    if i % 4 == 0:
        can4 += 1
    elif i % 2 == 0:
        even += 1
    else:
        odd += 1

if even == 0 and odd == can4 + 1:
    print("Yes")
elif odd > can4:
    print("No")
else:
    print("Yes")

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

string words[105];
int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        string w;
        cin >> w;
        words[i] = w;
        if(i){
            if(w[0] != words[i-1][words[i-1].length()-1]){
                cout << "No" << endl;
                return 0;
            }
            for(int j = 0; j < i; j++){
                if(words[i] == words[j]){
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;

    double d = 0.0;
    ll water = 0;
    ll sugar = 0;
    for(ll i=0; i<=30; i++){
        for(ll j=0; j<=30; j++){
            ll max_sugar = (i*A+j*B)*E;

            for(ll k=0; k<=max_sugar; k++){
                for(ll l=0; l<=max_sugar-k*C; l++){
                    if(k*C+l*D > (i*A+j*B)*E) break;
                    if(100*(i*A+j*B) + k*C+l*D > F) break;
                    double temp;
                    temp = 100 * double(k*C+l*D) / double(100*(i*A+j*B) + k*C+l*D);
                    if(temp >= d){
                        d = temp;
                        sugar = k*C+l*D;
                        water = 100*(i*A+j*B);
                    }
                }
            }
        }
    }
    cout << sugar + water << " " << sugar << endl;
    return 0;
}

Measured memory_bytes: 3568
set1 = set([1,3,5,7,8,10,12])
set2 = set([4,6,9,11])
set3 = set([2])

x,y  = map(int, input().split())
x_y = set([x,y])

if x_y<set1:
    print("Yes")
elif x_y<set2:
    print("Yes")
elif x_y<set3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();   
    int b = sc.nextInt();   
    int k = sc.nextInt(); 
    int count = 0;
    int i = Math.min(a, b);
    while(true){
      if(a % i == 0 && b % i == 0){
        count++;
        if(count == k){
          System.out.println(i);
          break;
        }
      }
      i--;
    }
  }
}

Measured memory_bytes: 21588
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

void pakuri_sort(int N, int A[]) {
	const int b = 8;
	int tmp[100001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint(), M = getint();

	int A[100000];
	int B[30] = {};
	rep(i, N) {
		A[i] = getint();
		B[31 - __builtin_clz(A[i])]++;
	}
	int k = 29;
	while (k >= 0 && M - B[k] >= 0) {
		M -= B[k];
		B[k - 1] += B[k];
		k--;
	}
	if (k == -1) {
		printf("0");
		return 0;
	}
	rep(i, N) {
		int kari = 31 - __builtin_clz(A[i]);
		if (kari > k) A[i] >>= kari - k;
	}

	pakuri_sort(N, A);

	ll kotae = 0;
	rep(i, N - M) kotae += A[i];
	for (int i = max(0, N - M); i < N; i++) kotae += A[i] >> 1;
	printf("%lld", kotae);

	Would you please return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> count(4,0);
    rep(i, N) {
        string s;
        cin >> s;
        if (s == "AC") {
            count[0]++;
        }
        else if (s == "WA") {
            count[1]++;
        }
        else if (s == "TLE") {
            count[2]++;
        }
        else {
            count[3]++;
        }
    }

    cout << "AC x "  << count[0] << endl;
    cout << "WA x "  << count[1] << endl;
    cout << "TLE x " << count[2] << endl;
    cout << "RE x "  << count[3] << endl;

    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>                   // below comment for pbds
#include<ext/pb_ds/assoc_container.hpp>   // to use it make ordered_set
#include<ext/pb_ds/tree_policy.hpp>       // all set fnct + = 1. order_of_key(x); // number of 
#define ll long long                      //element strictly smaller than it;
#define ld long double                    // 2. find_by_order(x),pointer el at x pos after sort  use as s.f();
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;                     
using namespace __gnu_pbds;
// assert(a[i]<n ) // if we want to check for special cond , used for debug
// make less_equal in order to make a multiset pbds
const ll Mod = 998244353;
ll CaseN=1;



ll tst(ll n ,ll *a)
{
 ll ans=0; 
	

 return ans;
}


void solve()
{	
	ll n;
	cin>>n;
	vector<ll> v(5,0);
	
	for(ll i=0;i<n;i++)
	{
	string s;
	cin>>s;
	if(s=="AC")
	{
	v[0]++;	
	}
	else if(s=="WA")
	{
	v[1]++;	
	}
	else if(s=="TLE")
	{
	v[2]++;	
	}
	else if(s=="RE")
	{
	v[3]++;
	}
	}
	
	cout<<"AC x "<<v[0]<<endl;
	cout<<"WA x "<<v[1]<<endl;
	cout<<"TLE x "<<v[2]<<endl;
	cout<<"RE x "<<v[3]<<endl;
	//cerr<<"Case #"<<CaseN<<": ";
    CaseN++;   

return ;
}


signed main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--)
	{	
	
	solve();	
	}
}


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

int main(void){
    ll n,m;
    cin >> n >> m;
    //vector<int> a(n), b(n);
    vector<pair<ll, int>> x(n);
    for(int i=0;i<n;i++) cin >> x[i].first >> x[i].second;
    
    sort(x.begin(), x.end());
    
    ll ans =0;
    for(int i=0;i<n;i++){
        if(m<=x[i].second){
            ans += m*x[i].first;
            break;
        }
        ans += x[i].first * x[i].second;
        m -= x[i].second;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4828
#include<cstdio>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<iostream>
#include<algorithm>
#define m(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const LL inf = 1 << 30;
map<char,int>mp;
const int maxn = 1e4;
int n,m;
char num[maxn+5][maxn+5];
int main(){
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			num[i][j] = '.';
		}
	}
	cin >> n >> m;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> num[i][j];
		}
	}
	bool ans = true;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			if(num[i][j] == '#'){
				if(num[i-1][j] == '.'&&num[i][j-1] == '.'&&num[i+1][j] == '.'&&num[i][j+1] == '.') ans = false;
			}
		}
	}
	if(ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>//for queue and priority_queue
#include <fstream>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#define endl "\n"
typedef long long ll;
using namespace std;
void Lancer() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
bool isPrime(ll n){
	if (n == 2 || n == 3 || n == 5)
		return true;
	else if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n == 1)
		return false;
	else {
		for (int i = 5; i <= sqrt(n); i += 2){
			if (n%i == 0)
				return false;
		}
		return true;
	}
}
//int frq[123];
//int arr[107];
int main(){
	Lancer();
	ll res = 0, t = 0;
	string str;
	cin >> str;
	for (int i = 0; i < str.length(); i++){
		if (str[i] == 'A'){
			for (int j = i+1; j < str.length(); j++){
				if (str[j] == 'Z'){
					t = j - i + 1;
					res = max(res, t);
				}
			}
			break;
		}
	}
	cout << res;
	cout << endl;
	return 0;
}


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

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  a.at(0) -= 32;
  b.at(0) -= 32;
  c.at(0) -= 32;
  
  
  cout << a.at(0) << b.at(0) << c.at(0) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <ratio>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;
template<class T> using v = vector<T>;
template<class T, class U> using p = pair<T, U>;

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

template<class T> T read() { T x{}; cin >> x; return x; }
template<class T> v<T> read(int N){ v<T> x(N); REP(i, N) cin >> x[i]; return x; }

template<class T>
void write(const T &x){ cout << x << endl; }
void write(double x){ printf("%.15f\n", x); }

const ull MOD = 1000'000'007;



int main(){
    ll N; cin >> N;
    v<p<ll, ll>> XL(N);
    for(auto& x : XL){
        ll xv, lv;
        cin >> xv >> lv;
        x.first = xv + lv;
        x.second = xv - lv;
    }
    sort(XL.begin(), XL.end());
    ll last_l = -1e9 - 1;
    ll ans = 0;
    for(auto& x: XL){
        if(last_l <= x.second){
            ++ans;
            last_l = x.first;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 1792
/*
 * a.c
 *
 *  Created on: 2017/06/13
 *      Author: AWV060608
 */

#include	<stdio.h>
#include	<math.h>

#define		MXNMB		1000+5

int		main(void)
{
	int		n;
	int		si[MXNMB];
	int		i;
	double	sum, sum1, avrg;
	double	rst;

	while(1)
	{
		sum = avrg = 0;
		scanf("%d",&n);
		if( n == 0)
			break;

		for(i=0; i<n; i++)
		{
			scanf("%d",&si[i]);
			sum = sum + si[i];
		}
		avrg = sum/n;
		sum1 = 0;
		for(i=0; i<n; i++)
		{
			sum1 = pow((si[i] - avrg),2) + sum1;
		}
		rst = sqrt(sum1/n);
		printf("%f\n",rst);
	}

	return 0;
}

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

int x, y, z;
multiset<string> s;

int main() {
    cin >> x >> y >> z;
    rep(i, 1, x) s.insert("a");
    rep(i, 1, y) s.insert("b");
    rep(i, 1, z) s.insert("c");
    while (s.size() > 1) {
        string ss = *s.begin() + *--s.end();
        s.erase(s.begin());
        s.erase(--s.end());
        s.insert(ss);
    }
    cout << *s.begin() << endl;
    return 0;
}


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

string s;
deque<char>d;
int q;
bool state=0;
//state=0 -> f1 depan, f2 belakang

int main(){
	cin >> s >> q;
	for (char c : s) d.push_back(c);
	while (q--){
		int type;
		cin >> type;
		if (type==1) state^=1;
		else{
			int f;
			char c;
			cin >> f >> c;
			if (!state){
				if (f==1) d.push_front(c);
				else d.push_back(c);
			}
			else{
				if (f==1) d.push_back(c);
				else d.push_front(c);
			}
		}
	}
	if (!state){
		while (!d.empty()){
			cout << d.front();
			d.pop_front();
		}
	}
	else{
		while (!d.empty()){
			cout << d.back();
			d.pop_back();
		}
	}
	cout << "\n";
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll powK(ll K, int n){
    ll ret = 1;
    while(n>0){
        if(n&1) ret = ret*K % MOD;
        n >>= 1;
        K = (K*K) % MOD;
    }
    return ret;
}

vector<int> yaku(100001);

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    COMinit();
    ll N, K; cin >> N >> K;
    ll ans = 0;
    for(int i = 1; i <= K; i++){
        yaku[i] = K/i;
    }
    ll dp[100001];
    for(int i = K; i >= 1; i--){
        ll res = powK(yaku[i], N);
        //cout << "pow(" << yaku[i] << ", " << N << ")= " << res << endl;
        for(int j = (i << 1); j <= K; j+=i){
            res = (res - dp[j]) % MOD;
        }
        if(res < 0) res += MOD;
        dp[i] = res;
        ans = (ans + res*i) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 16344
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字列の入力
		String[] lineString = sc.nextLine().split(" ");
		int numberOfObservatory = Integer.parseInt(lineString[0]);
		int numberOfLoad = Integer.parseInt(lineString[1]);

		int[] elevationList = new int[numberOfObservatory];
		int[] elevationMaxList = new int[numberOfObservatory];
		for (int observatory = 0; observatory < numberOfObservatory; observatory++) {
			int elevation = sc.nextInt();
			elevationList[observatory] = elevation;
			elevationMaxList[observatory] = 0;
		}

		for (int load = 0; load < numberOfLoad; load++) {
			int observatoryA = sc.nextInt() - 1;
			int observatoryB = sc.nextInt() - 1;
			elevationMaxList[observatoryA] = Math.max(elevationMaxList[observatoryA], elevationList[observatoryB]);
			elevationMaxList[observatoryB] = Math.max(elevationMaxList[observatoryB], elevationList[observatoryA]);
		}

		int goodObservatory = 0;
		for (int observatory = 0; observatory < numberOfObservatory; observatory++) {
			if (elevationMaxList[observatory] < elevationList[observatory]) {
				goodObservatory++;
			}
		}

		// 出力
		System.out.println(goodObservatory);
		sc.close();
	}
}


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

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

typedef Point<double> P;
double ccRadius(const P& A, const P& B, const P& C) {
	return (B-A).dist()*(C-B).dist()*(A-C).dist()/
			abs((B-A).cross(C-A))/2;
}
P ccCenter(const P& A, const P& B, const P& C) {
	P b = C-A, c = B-A;
	return A + (b*c.dist2()-c*b.dist2()).perp()/b.cross(c)/2;
}

pair<P, double> mec(vector<P> ps) {
	shuffle(all(ps), mt19937(time(0)));
	P o = ps[0];
	double r = 0, EPS = 1 + 1e-8;
	rep(i,0,sz(ps)) if ((o - ps[i]).dist() > r * EPS) {
		o = ps[i], r = 0;
		rep(j,0,i) if ((o - ps[j]).dist() > r * EPS) {
			o = (ps[i] + ps[j]) / 2;
			r = (o - ps[i]).dist();
			rep(k,0,j) if ((o - ps[k]).dist() > r * EPS) {
				o = ccCenter(ps[i], ps[j], ps[k]);
				r = (o - ps[i]).dist();
			}
		}
	}
	return {o, r};
}

int main()
{
    cout.precision(10);
    int n;
    cin >> n;
    vector<P> ps(n);
    for(int i=0; i<sz(ps); i++)
    {
        double first,second;
        cin >> first >> second;
        Point<double> x;
        x.x=first;
        x.y=second;
        ps[i]=x;
    }
    cout << mec(ps).second; 
}


Measured memory_bytes: 256
while True:
    dict = {}
    n = input()
    if n == 0:break
    for x in xrange(n):
        a, b = raw_input().split()
        dict[a] = b
    res = ""
    for x in xrange(input()):
        a = raw_input()[0]
        if a in dict:
            res += dict[a]
        else:
            res += a
    print res

Measured memory_bytes: 6328
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    int n; cin >> n;
    vector<int> s(1 << n);
    rep(i, (1 << n)) cin >> s[i];
    sort(RALL(s));

    multiset<int> t;
    FOR(i, 1, (1 << n)) t.insert(s[i]);
    vector<int> p;
    p.pb(s[0]);

    rep(i,n){
        vector<int> nex = p;
        for(int v : p){
            auto it = t.lower_bound(v);
            if(it == t.begin()){
                cout << "No" << endl;
                return 0;
            }
            it--;
            nex.pb(*it);
            t.erase(it);
        }
        sort(RALL(nex));
        swap(p, nex);
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 16704