akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
const int MN=200000+5;
const int P=1000000007;
using namespace std;
typedef long long ll;
template<typename T>T&IN(T&in){
	in=0;char c=getchar();int f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))in=in*10+c-'0',c=getchar();
	in*=f;return in;
}
int n,m,a,b,N;ll ans;
ll fac[MN],inv[MN];
ll qp(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P;return c;}
ll C(int n,int m){return n>=m?fac[n]*inv[m]%P*inv[n-m]%P:0;}
void input(){
	IN(n),IN(m),IN(a),IN(b),fac[0]=1;N=200000;
	for(int i=1;i<=N;++i)fac[i]=fac[i-1]*i%P;
	inv[N]=qp(fac[N],P-2);
	for(int i=N;i>=1;--i)inv[i-1]=inv[i]*i%P;
	for(int i=b+1;i<=m;++i){
		ans=(ans+C(n-a-1+i-1,i-1)*C(a-1+m-i,a-1)%P)%P;
	}
	printf("%lld\n",ans);
}
int main(){
	input();
	return 0;
}

Measured memory_bytes: 3328
#include <stdio.h>          // printf(), scanf()

#define MAX_N 100000
#define swap(x, y) { int t = x; x = y; y = t; }

int
partition(int a[], int p, int r)
{
	int j;

	int x = a[r];
	int i = p - 1;
	for (j = p; j < r; ++j)
	{
		if (a[j] <= x)
		{
			i++;
			swap(a[i], a[j]);
		}
	}

	swap(a[i + 1], a[r]);
	return i + 1;
}

int
main(int argc, char** argv)
{
	int a[MAX_N];
	int n, i;

	scanf("%d", &n);
	for (i = 0; i < n; ++i)
		scanf("%d", &a[i]);

	int j = partition(a, 0, n - 1);
	for (i = 0; i < n; ++i)
	{
		if (i == j)
			printf("[%d]%c", a[i], (i != n - 1) ? ' ' : '\n');
		else
			printf("%d%c", a[i], (i != n - 1) ? ' ' : '\n');
	}

	return 0;
}

Measured memory_bytes: 988
/*
 USER: josifte4
 LANG: C++
 TASK: camelot
 */
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
int n;
int arr[100006];
int cnt[100005];
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; i < n; i ++){
        cin >> arr[i];
        cnt[arr[i]] ++;
    }
    int mxx = 0;
    
    for(int num = 1; num <= 100000; num ++){
        mxx = max(mxx, cnt[num] + cnt[num - 1] + cnt[num + 1]);
    }
    cout << mxx << endl;
   
    return 0;
    
}


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

int main() {
  int X, Y;
  cin >> X >> Y;
  
  bool flag = false;
  int legs = 0;
  for(int i=0; i<=X; i++){
    int j = X-i;
    legs = 2*i + 4*j;
    if(legs == Y){
      flag = true;
      break;
    }
  }
  if(flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3628
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)


int Len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}


int Sint(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


int GCD(int a,int b)
{
  int r, tmp;
   /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}


int Factorial(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}


int Svec(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int n,ans=0;
  cin>>n;
  int k=1;
  while(ans<n){
    ans+=k;
    k++;
  }
  cout<<k-1<<endl;
}
///////////////////////////

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


int main(){
 int n;cin >> n;
 int a[n]; int tmp;
 ll sum = 0;rep{cin >> tmp;sum+=tmp;a[i]=tmp;}
 int m;cin >> m;
 int p,x;
 for(int i = 0;i<m;i++){
     cin >> p >> x;
     cout << sum - a[p-1]  + x  << endl;
 }
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <numeric>
#include <list>
#include <queue>

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

using namespace std;

int main()
{
    LL n;
    cin >> n;

    if (n == 0) {
        cout << '0' << endl;
        return 0;
    } 

    LL tmp = n;
    string str = "";
    while (tmp != 0) {
        LL amari = tmp % 2;
        if (amari == 0) {
            str = '0' + str;
        } else {
            str = '1' + str;
            tmp--;
        }
        tmp /= -2;
    }
    cout << str << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long 
#define pb push_back
#define ins insert
#define rs resize
#define br break;
#define cont continue;
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int>>
#define si set<ll>
#define sll set<long long>
#define pii pair<ll,ll>
#define pll pair<long long, long long>
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);
#define vec vector
#define cend cout<<endl;
#define sc second
#define fr first
#define retz return 0;
#define ll_MAX (ll)(1e9*1e9)
#define ll_MIN (ll)(-1e9*1e9)
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b)  for(int i=a; i<=b; i++)
#define repd(i,a,b) for(int i=a; i>=b; i--)
#define ps(arr, n) for(int i=1; i<n; i++)arr[i]+=arr[i-1];
#define inp(arr, n)for(int i=0; i<n; i++)cin>>arr[i];
#define out(arr, n)for(int i=0; i<n; i++)cout<<arr[i];
#define inp1(arr,n,m)for(int i=0; i<n; i++)for(int j=0;j<m;j++)cin>>arr[i][j];
#define out1(arr,n,m)for(int i=0; i<n; i++)for(int j=0;j<m;j++)cin>>arr[i][j];
#define loop(q) for(auto it:q)
#define loop1(q) for(auto&it:q)
#define db1 cout << "*" << endl
#define db2 cout << "YES" << endl
using namespace std;
using namespace __gnu_pbds; 
#define oset(X) tree<X,null_type,less<X>, rb_tree_tag, tree_order_statistics_node_update> 
#define roset(X) tree<X,null_type,greater<X>, rb_tree_tag, tree_order_statistics_node_update>  
#define okey order_of_key //lower_bound_set
#define ofind find_by_order
#define cyes cout << "Yes" << endl; 
#define cno cout << "No" << endl;
#define mod (long long)1000000007
#define mod2 (long long)998244353
#define INT_MAX1 900000000
#define MAXN 2000000
#define INF INT_MAX



 
void solve()
{
    int n;
    cin >> n;
    int arr[n];
    inp(arr, n);
    sort(arr, arr+n);
    multiset<int> q;
    rep(i,0,n-2)
        q.insert(arr[i]);
    map<int,vec<pii>> q2;
    q2[arr[n-1]].pb({arr[n-1], arr[n-1]});


    int ans = 0;

    while(q.size())
    {

        int curr = *q.rbegin();
        q.erase(q.find(curr));
        ans += q2.rbegin()->first;
        int x1 = q2.rbegin()->fr;
        auto it = q2.rbegin();


        pii xx = it->sc[it->sc.size()-1];
        q2[x1].pop_back();

        if(q2[x1].size()==0)
            q2.erase(x1);
        pii aa = {xx.fr, curr};
        pii bb = {curr, xx.sc};
        q2[min(xx.fr,curr)].pb(aa);
        q2[min(xx.sc,curr)].pb(bb);
    }

    cout << ans << endl;



}


signed main()
{
    
    speed;
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

Measured memory_bytes: 18748
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begins[j];i;i=nxt[i])
using namespace std;
int const mn=2*1e3+3,mo=1e9+7;
int n,K,tmp,u[mn],v[mn],gra,begins[mn],to[mn*2],nxt[mn*2];
void inserts(int u,int v){
    to[++gra]=v;
    nxt[gra]=begins[u];
    begins[u]=gra;
}
void dfs(int p,int q,int dep){
    tmp++;
    if(!dep)return;
    fr(i,p)if(to[i]!=q)
            dfs(to[i],p,dep-1);
}
int main(){
//    freopen("c.in","r",stdin);
//    freopen("c.out","w",stdout);
    scanf("%d%d",&n,&K);
    fo(i,1,n-1){
        scanf("%d%d",&u[i],&v[i]);
        inserts(u[i],v[i]);
        inserts(v[i],u[i]);
    }
    int ans=0;
    if(K&1){
        fo(i,1,n-1){
            tmp=0;
            dfs(u[i],v[i],K/2);
            dfs(v[i],u[i],K/2);
            ans=max(ans,tmp);
        }
    }else{
        fo(i,1,n){
            tmp=0;
            dfs(i,0,K/2);
            ans=max(ans,tmp);
        }
    }
    printf("%d",n-ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) prllf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

class Monoid {
public:
    ll unit;  // 単位元

    Monoid() {
        // 単位元(gcdのときは0)
        unit = 0;
    }
    
    // 演算関数(いまはgcd)
    ll calc(ll a, ll b) {
        return gcd(a, b);
    }
};

class SegmentTree {
public:
    ll n;  // セグメント木の葉の要素数
    vector<ll> tree;  // セグメント木
    Monoid mono;  // モノイド
    
    SegmentTree(vector<ll> &v) {
        n = 1 << (ll)ceil(log2(v.size()));
        tree = vector<ll>(n << 1);
        for(ll i = 0; i < v.size(); i++) {
            update(i, v[i]);
        }
        for(ll i = v.size(); i < n; i++) {
            update(i, mono.unit);
        }
    }
    
    // k番目の値(0-index)をxに変更
    void update(ll k, ll x) {
        k += n;
        tree[k] = x;
        for(k = k >> 1; k > 0; k >>= 1){
            tree[k] = mono.calc(tree[k << 1 | 0], tree[k << 1 | 1]);
        }
    }
    
    // [l, r)(0-index)で演算をする
    ll query(ll l, ll r) {
        ll res = mono.unit;
        l += n;
        r += n;
        while(l < r) {
            if(l & 1) {
                res = mono.calc(res, tree[l++]);
            }
            if(r & 1) {
                res = mono.calc(res, tree[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

    ll operator[](ll k) {
        // seg[i]で添字iの要素の値を返す
        if(k - n >= 0 || k < 0) {
            return -INF;
        }
        return tree[tree.size()-n+k];
    }
    
    void show() {
        ll ret = 2;
        for(ll i = 1; i < 2*n; i++) {
            cout << tree[i] << " ";
            if(i == ret - 1) {
                cout << endl;
                ret <<= 1;
            }
        }
        cout << endl;
    }
};

int main() {
    ll n;
    cin >> n;
    
    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }
    
    ll ans = 0;
    SegmentTree seg(a);
    rep(i, n) {
        ll x = seg[i];
        seg.update(i, 0);
        chmax(ans, seg.query(0, n));
        seg.update(i, x);
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 3072
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main()
{
    int n;
    scanf("%d", &n);
    int sum = 0;
    int tmp = n;
    while (n>0)
    {
        sum += n%10;
        n = n/10;
    }
    if (tmp%sum == 0) printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using 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 debug(x) cout << #x << "=" << (x) << endl;

template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> void fail(T v){cout << v << endl;exit(0);}
//template end

void solve(){
  while(true){
    int m,n;
    cin>>m>>n;
    if(!(m|n))return;
    int ct=0,i;
    vector<bool> p((int)8e6);
    for(i=m;ct!=n;i++)
      if(!p[i]){
        ct++;
        for(int j=2*i;j<p.size();j+=i)
          p[j]=true;
      }
    while(p[i])i++;
    cout<<i<<endl;
  }
}

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



Measured memory_bytes: 4052
#!/usr/bin/env python3
#ABC100 C

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

ans = 0
for i in range(N):
    if a[i] % 2 == 0:
        while a[i] % 2 == 0:
            a[i] = a[i] / 2
            ans += 1
print(ans) 


Measured memory_bytes: 4148
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
#define all(a) a.begin(), a.end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;
using P  = pair<int,int>;
const int INF = 1001001001;
const int MOD = 1000000007;



int main(){
    int n;
    cin >> n;
    vi c(n,0);
    rep(i,n-1){
        int a;
        cin >> a;
        a--;
        c[a]++;
    }
    rep(i,n)printf("%d%c", c[i], i==n-1?'\n':' ');
    return 0;
}

Measured memory_bytes: 4036
#include <iostream>
#include <list>
#include <climits>
using namespace std;

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

  list<int> p;
  for ( int i=0; i<N; i++ ) {
    int x;
    cin >> x;
    p.push_back(x);
  }
  p.sort();

  int minval = INT_MAX;
  auto it1 = p.begin();
  auto it2 = it1;
  for ( int i=0; i<K-1; i++ )
    it2++;

  while ( it2 != p.end() ) {
    minval = min(minval, *it2 - *it1);
    it1++;
    it2++;
  }
  cout << minval << endl;
  return 0;
}


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

int main() {
    int oneNum;
    int money;

    cin >> money >> oneNum;

    money %= 500;
    if(money == 0 || money <= oneNum) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    cout << endl;

}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001
#define MOD ((ll)1e9 + 7)

int main(){
  cin.sync_with_stdio(false);
  ll n, m;
  cin >> n >> m;

  ll d;
  ll tmp[2];
  cin >> tmp[0];
  ll sx = 0, sy = 0;
  repl(i, 1, n) {
    cin >> tmp[1];
    d = (tmp [1] - tmp[0]) % MOD;
    tmp[0] = tmp[1];
    d = (d * (i * ((n - i)) % MOD)) % MOD;
    sx = (sx + d) % MOD;
  }

  cin >> tmp[0];
  repl(i, 1, m) {
    cin >> tmp[1];
    d = (tmp [1] - tmp[0]) % MOD;
    tmp[0] = tmp[1];
    d = (d * (i * ((m - i)) % MOD)) % MOD;
    sy = (sy + d) % MOD;
  }

  cout << ((sx * sy) % MOD) << endl;

  return 0;
}

Measured memory_bytes: 256
import sys

a, b, k = map(int, input().split())
l = []

for i in range(1, max(a,b)+1):
    if a%i == 0 and b%i == 0:
        l.append(i)
if l == []:
    print(1)
    sys.exit()
l.sort(reverse=True)
print(l[k-1])


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

int main(){

    int n,m;
    int temp;
    cin>>n>>m;
    vector<int> a(50);

    for(int i=0;i<m;i++){

        cin>>temp;
        a.at(temp-1)++;
        cin>>temp;
        a.at(temp-1)++;

    }

    for(int i=0;i<n;i++) cout<<a.at(i)<<endl;






}

Measured memory_bytes: 256
n=int(input())
X=[]*n
A=[]*n

for i in range(n):
	a=int(input())
	A.append(a)
	xy = [list(map(int,input().split())) for _ in range(a)]
	X.append(xy)

ans=0
for i in range(2**n):
	cnt=0
	for j in range(n):
		if (i>>j)&1:
			for k,l in X[j]:
				if not ((i>>(k-1))&1)==l:
					cnt=1

	if cnt==0:
		ans = max(ans,bin(i).count("1"))

print(ans)

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

int n, m, q, ans = 0;
vector<tuple<int, int, int, int>> vec;

int A[10];


void calc(void) {
    int sum = 0;
    for(auto tup : vec) {
        if(A[get<1>(tup)] - A[get<0>(tup)] == get<2>(tup)) {
            sum += get<3>(tup);
        } 
    }
    ans = max(ans, sum);
}

void dfs(int depth, int n, int m) {
    if(depth == n) {
        calc(); return;
    }
    
    rep(i, m) {
        A[depth] = i+1;
        if(depth >= 1) {
            if(A[depth] < A[depth-1]) continue;
        }
        dfs(depth+1, n, m); 
    }
}

int main(void) {   
    int n, m, q;
    cin >> n >> m >> q;
    rep(i, q) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--; b--;
        vec.emplace_back(a, b, c, d);
    }

    dfs(0, n, m);
    cout << ans << endl;
    return 0;
}

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

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

  vector<ll> h(N);
  for(ll i = 0; i < N; i++){
    cin >> h[i];
  }

  sort(h.begin(), h.end());

  ll ans = 1000000000;
  for(ll i = 0; i < N-K+1; i++){
    ans = min(ans, h[i+K-1]-h[i]);
  }
  
  cout << ans << endl;
  
  return 0;

}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cmath>
#include <climits>
#include <map>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)
#define rep1(i, n) for(int i = 1; i <= (int) n; i++)
#define all(v) v.begin(),v.end()
const ll mod = 1e9+7;

int main() {
    int n;
    cin >> n;
    vector<int> a(4);
    rep(i,n) {
        string s;
        cin >> s;
        if (s[0] == 'A') a[0]++;
        if (s[0] == 'W') a[1]++;
        if (s[0] == 'T') a[2]++;
        if (s[0] == 'R') a[3]++;
    }
    cout << "AC x " << a[0] << endl;
    cout << "WA x " << a[1] << endl;
    cout << "TLE x " << a[2] << endl;
    cout << "RE x " << a[3] << endl;
    return 0;
}

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

typedef long long ll;

int main(void){
    ll n,k;
    cin >> n >> k;
    ll ans = 0;
    for(ll i=k+1; i<=n; i++){
        ll sub = max((ll)0,k - 1) + k*(n/i - 1);
        sub += min(k,n%i+1);
        ans += n-sub;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int makeg( int n )
{
  int k = 1 ;
  int i ;
  for ( i = 0 ; i < n ; i++) {
    if ( k > n ) break ;
    k = 3 * k + 1 ;
  }
  return i ;
}

void shellsort( int n, int a[] )
{
  int m = makeg(n) ;
  int g[20] ;
  int k = 1 ;
  for (int i = 0 ; i < m ; i++) {
    g[i] = k ;
    k = 3 * k + 1 ;
  }

  int ans = 0 ;
  for( int i = m-1 ; i >= 0 ; i-- ){
    int gg = g[i] ;
    for (int j = gg; j < n; j++) {
      int v = a[j] ; // sort対象
      int l = j -gg ;
      while( l >= 0 && a[l] > v ){
        a[l+gg] = a[l] ;
        l = l - gg ;
        ans++ ;
      }
      a[l+gg] = v ;
    }
  }

  printf("%d\n", m) ;
  for (int i = m-1; i > 0 ; i--) {
    printf("%d ", g[i]) ;
  }
  printf("%d\n", g[0]) ;
  printf("%d\n", ans) ;

  for (int i = 0; i < n ; i++) {
    printf("%d\n", a[i] ) ;
  }
}

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

  int a[n] ;
  for (int i = 0; i < n ; i++){
    scanf("%d",&a[i]) ;
  }

  shellsort( n, a ) ;

  return 0;
}



Measured memory_bytes: 5640
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<int> p(N);
  rep(i,N)
  {
    cin >> p[i];
  }
  int sum = 0;
  rep(i,N)
  {
    sum += p[i];
  }
  int m = 0;
  rep(i,N)
  {
    if(p[i]>m)
    {
      m = p[i];
    }
  }
  cout << sum - m/2 << endl;
  return 0;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N;
    cin >> N;
    map<string,ll> X;
    REP(i,0,N) {
        string s;
        cin >> s;
        ASC(s);
        ++X[s];
    }

    ll cnt = 0;
    FORR(x,X) cnt += x.second * (x.second - 1) / 2;
    PR(cnt);

    return 0;
}

/*



*/

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
    int k, n; cin >> k >> n;
    vector<int> a(n);
    REP(i, n) cin >> a[i];
    vector<int> s(n);
    REP(i, n - 1) s[i] = a[i + 1] - a[i];
    s[n - 1] = (k - a[n - 1]) + a[0];
    DESC(s);
    cout << k - s[0] << endl;
}


Measured memory_bytes: 1792
S = input()

R_n = 0
R_max = 0
for i in S:
  if i == 'R':
    R_n += 1
  else:
    if R_n != 0:
      R_max = R_n
    R_n = 0
    
if R_n > R_max:
  R_max = R_n

print(R_max)

Measured memory_bytes: 9100
import qualified Data.Map.Strict as Map
import Control.Applicative

main :: IO ()
main = do
  _ <- getLine
  s <- map read . words <$> getLine
  _ <- getLine
  t <- map read . words <$> getLine
  print $ solve s t

solve :: [Int] -> [Int] -> Int
solve s t = length $ filter (`Map.member` s') t
  where
    s' = (Map.fromList [(k, k) | k <- s])



Measured memory_bytes: 98348
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    An = [0] * N
    Bn = [0] * N
    for n in range(N):
        An[n], Bn[n] = [int(x) for x in input().strip().split()]
    An.sort()
    Bn.sort(reverse=True)
    if N % 2:
        A = An[(N+1)//2-1]
        B = Bn[(N+1)//2-1]
        print(B - A + 1)
    else:
        Amin = An[N//2-1]
        Amax = Bn[N//2]
        Bmax = Bn[N//2-1]
        Bmin = An[N//2]
        # print(Amin, Amax, Bmin, Bmax)
        print(int(((Bmax+Amax)/2-(Bmin+Amin)/2)//0.5+1))

if __name__ == '__main__':
    main()

Measured memory_bytes: 25528
h, w = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(h)]
count = 0
B = []

for i in range(h):
    for j in range(w-1):
        if A[i][j] % 2 == 1:
            count += 1
            A[i][j+1] += 1
            B.append([i+1, j+1, i+1, j+2])

for i in range(h-1):
    if A[i][w-1] % 2 == 1:
        count += 1
        A[i+1][w-1] += 1
        B.append([i+1, w, i+2, w])
        
print(count)
for i in range(count):
    print(B[i][0], B[i][1], B[i][2], B[i][3])

Measured memory_bytes: 30100
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut x = read::<usize>();
    let y = read::<usize>();
    
    let mut i = 0;
    while x <= y { 
        i+=1;
        x *= 2;
    }

    println!("{}", i);
}

Measured memory_bytes: 4352
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int main() {
  int a, b, c, d;
  scan(a, b, c, d);
  int left = max(a, c);
  int right = min(b, d);
  int ans = max(0, right - left);
  print(ans);
  return 0;
}


Measured memory_bytes: 256
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string { sc.Scan(); return sc.Text() }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }

func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1000000)

	a := getPrimes(55555)

	n := scanInt()
	for i := 0; i < len(a); i++ {
		if a[i]%5 != 1 {
			continue
		}
		n--
		fmt.Printf("%d ", a[i])
		if n == 0 {
			break
		}
	}
	fmt.Println()
	fmt.Fprintln(os.Stderr, a)
}

func getPrimes(n int) []int {
	res := make([]int, 0)
	f := make([]bool, n+1)
	var m int
	for m = 2; m*m <= n; m++ {
		if f[m] {
			continue
		}

		res = append(res, m)
		for i := 2; i*m < n+1; i++ {
			f[i*m] = true
		}
	}

	for i := m; i < n+1; i++ {
		if f[i] {
			continue
		}

		res = append(res, i)
	}

	return res
}


Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int i, j;
    long long k, n;
    cin >> k >> n;
    vector<int> a(n);
    long long max = 0;

    for (i = 0; i < n; i++) {
        cin >> a[i];
        if (i != 0) {
            if (a[i] - a[i-1] > max) {
                max = a[i] - a[i-1];
            }
        }
    }
    long long s = a[0] + (k - a[n-1]);
    if (s > max) max = s;

    cout << k - max << endl;

    return 0;
}


Measured memory_bytes: 1152
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
//use proconio::fastout;
use proconio::input;
//use proconio::marker::*;
//use std::collections::HashSet;
// use std::cmp::*;
//use std::collections::VecDeque;

fn main() {
    input! {
       A:i32,B:i32,C:i32
    }
    if A == B && B != C || A == C && A != B || B == C && A != B {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2088
local mod = 1000000007
local mfl = math.floor

local function bmul(x, y)
  local x0, y0 = x % 31623, y % 31623
  local x1, y1 = mfl(x / 31623), mfl(y / 31623)
  return (x1 * y1 * 14122 + (x1 * y0 + x0 * y1) * 31623 + x0 * y0) % mod
end

local function badd(x, y)
  return (x + y) % mod
end

local function bsub(x, y)
  return x < y and x - y + mod or x - y
end

local function modpow(src, pow)
  local res = 1
  while 0 < pow do
    if pow % 2 == 1 then
      res = bmul(res, src)
      pow = pow - 1
    end
    src = bmul(src, src)
    pow = mfl(pow / 2)
  end
  return res
end

local function modinv(src)
  return modpow(src, mod - 2)
end

local function getComb(n, k)
  local ret = 1
  for i = 1, k do
    ret = bmul(ret, n + 1 - i)
    ret = bmul(ret, modinv(i))
  end
  return ret
end

local n, k = io.read("*n", "*n")
local t = {}
for i = 1, n do
  t[i] = io.read("*n")
end
table.sort(t)
local maxsum = 0

local combs = {1}
for i = 1, k - 2 do
  combs[i] = 1
end

for i = k - 1, n do
  if i == k - 1 then
    combs[i] = 1
  else
    combs[i] = bmul(combs[i - 1], i)
    combs[i] = bmul(combs[i], modinv(i - k + 1))
  end
end
-- print(table.concat(combs, " "))

for i = n, k, -1 do
  local cmb = combs[i - 1]--getComb(i - 1, k - 1)
  maxsum = badd(maxsum, bmul(cmb, t[i]))
end
local minsum = 0
for i = 1, n - k + 1 do
  local cmb = combs[n - i]--getComb(n - i, k - 1)
  minsum = badd(minsum, bmul(cmb, t[i]))
end
-- print(maxsum, minsum)
local ret = bsub(maxsum, minsum)
print(ret)


Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int n;
map<int,map<string,int>> dp;
char c[]={'A','T','G','C'};

bool ok(string s){
    for(int i=0;i<4;i++){
        string tmp=s;
        if(i<3) swap(tmp[i],tmp[i+1]);
        for(int j=0;j<2;j++){
            if(tmp.substr(j,3)=="AGC") return false;
        }
    }
    return true;
}
int dfs(int now,string s){
    if(now==n) return 1;
    if(dp[now].count(s)){
        return dp[now][s];
    }
    int ret=0;
    for(char cc:c){
        if(ok(s+cc)){
            ret+=dfs(now+1,s.substr(1,2)+cc);
            ret%=MOD;
        }
    }
    dp[now][s]=ret;
    return ret;

}
int main(){
    cin>>n;
    cout<<dfs(0,"TTT")<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define SQ(a) (a)*(a)

template <class T, class U> ostream& operator<< (ostream &out, pair<T,U> c) { out << "(" << c.first << " "; out << c.second << ")"; return out; }
template <class T> ostream& operator<< (ostream &out, vector<T> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
const double PI  = 3.141592653589793238463;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    if(s.size() - t.size() == 1){
        FOR(i,0,t.size()){
            cout << s[i] << t[i];
        }
        cout << s[s.size()-1];
    }
    else
    {
        FOR(i,0,t.size()){
            cout << s[i] << t[i];
        }
    }
    cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct{
  char suit;
  char value;
}Card;

void swap(Card *,Card *);

int main(){
  Card C1[100], C2[100];
  int n, i,j,c1,c2,mini,sum=0;
  char a;
  scanf("%d%c", &n,&a);
  for ( i = 0; i < n; i++ ){
    scanf("%c%c%c",&C1[i].suit,&C1[i].value,&a);
  }
  for(i=0;i<n;i++){
  strcpy(&C2[i].suit,&C1[i].suit);
  strcpy(&C2[i].value,&C1[i].value);
  }

  for(i=0;i<n-1;i++){
    for(j=n-1;j>i;j--){
      c1 = atoi(&C1[j].value);
      c2 = atoi(&C1[j-1].value);
      if(c1 < c2) {
	swap(&C1[j],&C1[j-1]);
      }
    }
  }
  for(i=0;i<n-1;i++)printf("%c%c ",C1[i].suit,C1[i].value);
  printf("%c%c\n",C1[n-1].suit,C1[n-1].value);
  printf("Stable\n");

  for(i=0;i<n;i++){
    mini=i;
    for(j=i;j<n;j++){
      c1 = atoi(&C2[j].value);
      c2 = atoi(&C2[mini].value);
      if(c1 < c2){
	mini = j;
      }
    }
    swap(&C2[i],&C2[mini]);
  }

  for(i=0;i<n-1;i++)printf("%c%c ",C2[i].suit,C2[i].value);
  printf("%c%c\n",C2[n-1].suit,C2[n-1].value);

  for(i=0;i<n;i++){
    if(strcmp(&C1[i].suit,&C2[i].suit)!=0 && strcmp(&C1[i].value,&C2[i].value)!=0){
      printf("Not stable\n");
      sum=1;
      break;
    }
  }
  if(sum!=1) printf("Stable\n");
  return 0;
}

void swap(Card *a,Card *b){
  Card temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

Measured memory_bytes: 624
#include<bits/stdc++.h>
using namespace std;
#define i64 long long int
map<int,int> a;int n,m;
int main(){
	scanf("%d%d",&n,&m);
	int s = 0, x;
	a[s] = 1;
	for(int i=0; i<n; i++){
		scanf("%d",&x);
		s = (s+x)%m;
		a[s] ++;
	}
	i64 res = 0;
	for(auto it : a){
		i64 y = it.second;
		res += y * (y - 1)/2;
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3200
#include<stdio.h>
#define MAX 100000

int A[MAX], n;

int partition(int p, int r){
  int x = A[r];
  int i = p - 1;
  for(int j = p; j < r; j++){
    if(A[j] <= x){
      i++;
      int t = A[i]; A[i] = A[j]; A[j] = t;
    }
  }
  int t = A[i+1]; A[i+1] = A[r]; A[r] = t;
  return i+1;
}

int main(){
  scanf("%d",&n);
  for(int i = 0; i < n; i++)scanf("%d",&A[i]);

  int q = partition(0, n-1);

  for(int i = 0; i < n; i++){
    if(i)printf(" ");
    if(i == q)printf("[");
    printf("%d",A[i]);
    if(i == q)printf("]");
  }
  printf("\n");

  return 0;
}



Measured memory_bytes: 2248
#include <iostream>
using namespace std;
int main()
{
  int N,K,s;
  cin>>N;
  cin>>K;
  int x[N];
  s=0;
  for(int i=0;i<N;i++){
    cin>>x[i];
    s+=2*min(x[i],K-x[i]);
  }
  cout<<s<<endl;
  return 0;
}

Measured memory_bytes: 256
n, a = gets.split.map(&:to_i)
x = gets.split.map(&:to_i)

dp = Array.new(n+1).map{ Array.new(n+1).map{ Array.new(n * 50 + 1, 0) }}

dp[0][0][0] = 1

1.upto(n) do |i|
	dp[i][0][0] = 1
	1.upto(i) do |j|
		1.upto(n * 50) do |k|
			if x[i-1] <= k
				dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i-1]]
			else
				dp[i][j][k] = dp[i-1][j][k]
			end
		end
	end
end

puts (1..n).inject(0) { |sum, i| sum += dp[n][i][a*i] }

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

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define ALL(c) (c).begin(), (c).end()

template <typename T>
inline void assign_max(T& x, const T& value) {
    x = max(x, value);
}

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

    int R, C, K; cin >> R >> C >> K;
    map<pair<int, int>, int64_t> items;
    REP(i, K) {
        int r, c; int64_t v; cin >> r >> c >> v; --r; --c;
        items.insert({{r, c}, v});
    }

    vector dp(2, vector(C, vector(4, numeric_limits<int64_t>::min())));

    dp[0][0][0] = 0;
    REP(y, R+1) REP(x, C) REP(k, 4) {
        if (auto it = items.find({y, x}); k < 3 && it != items.end()) {
            // (y, x) にアイテムが存在し、拾うことが可能な場合
            int64_t value = it->second;
            if (y+1 < R+1)
                assign_max(dp[(y+1)%2][x][0], dp[y%2][x][k] + value);
            if (x+1 < C)
                assign_max(dp[y%2][x+1][k+1], dp[y%2][x][k] + value);
        }
        if (y+1 < R+1)
            assign_max(dp[(y+1)%2][x][0], dp[y%2][x][k]);
        if (x+1 < C)
            assign_max(dp[y%2][x+1][k], dp[y%2][x][k]);
    }

    cout << *max_element(ALL(dp[R%2][C-1])) << '\n';
}


Measured memory_bytes: 16464
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 111111;
const long long inf = 1e9;
long long arr[maxn], dp[maxn];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < maxn; i++) {
		dp[i] = inf;
	}
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	dp[1] = 0;
	dp[2] = dp[1] + abs(arr[2] - arr[1]);
	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= k && i - j >= 1; j++) {
			dp[i] = min(dp[i], dp[i - j] + abs(arr[i] - arr[i - j]));
		}
	}
	cout << dp[n] << '\n';
	return 0;
}


Measured memory_bytes: 1920
#include <iostream>

using namespace std;

int main(){
  int N, cnt=0;
  cin >> N;
  int p[N];
  for(int i=0; i<N; i++) cin >> p[i];
  for(int i=0; i<N; i++){
    if(p[i] != i+1) cnt++;
  }
  if(cnt > 2) cout << "NO" << endl;
  else cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<complex>
#include<utility>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
#define all(v) v.begin(),v.end()
using namespace std;

const double eps = 1e-8;
const double INF = 1e12;

int cal(int p,int q,int r){
	return (p+r)*4+q*9;
}

int main(){
	int n;
	while(cin>>n,n){
		int dt[n],p[n],q[n],r[n];
		rep(i,n){
			cin>>dt[i]>>p[i]>>q[i]>>r[i];
		}
		int rp,rq,rr,rc;
		cin>>rp>>rq>>rr>>rc;
		int cnt=0;
		rep(i,n){
			if(rp>=p[i] && rq>=q[i] && rr>=r[i] && rc>=cal(p[i],q[i],r[i])){
				cout<<dt[i]<<endl;
				cnt++;
			}
		}
		if(cnt==0)cout<<"NA"<<endl;

	}
	return 0;
}

Measured memory_bytes: 1176
N = int(input())

s = (1+N)*N // 2
s1 = 0
s2 = 0
s3 = 0
if N >= 3:
    s1 = ((3 + (N//3)*3) * (N//3)) // 2
if N >= 5:
    s2 = ((5 + (N//5)*5) * (N//5)) // 2
if N >= 15:
    s3 = ((15 + (N//15)*15) * (N//15)) // 2
print(s + s3 - s1 - s2)


Measured memory_bytes: 61840
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define DESCEND greater<int>()  // sort 降順 大きい順
#define UNIQUE(vec) (vec).erase(unique(ALL((vec))), (vec).end());  // 必ずsortを行なってから
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007


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

    // input
    string S, front, back;
    cin >> S;
    
    // calculation
    bool flag = true;
    size_t len = S.length();
    while (flag) {
        S.pop_back();
        S.pop_back();
        len = S.length();
        front = S.substr(0, len/2);
        back = S.substr(len/2, len/2);
        if (front == back) {
            flag = false;
        }
    }
    cout << len << "\n";
    
    return 0;
}


Measured memory_bytes: 760
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long int ll;
ll mod=1e9+7;
int main(){
	string s; cin >>s;
	int cnt=0;
	int ans=s.size();
	for(int i=0;i<s.size();i++){
		if(s[i]=='S')cnt++;
		else if(s[i]=='T'&&cnt>0){
			cnt--;
			ans-=2;
		}
	}
	cout << ans << endl;
}

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

int main(){
  double w;
  while(cin>>w){
    if(w<=48.0)cout<<"light fly";
    else if(w<=51.0)cout<<"fly";
    else if(w<=54.0)cout<<"bantam";
    else if(w<=57.0)cout<<"feather";
    else if(w<=60.0)cout<<"light";
    else if(w<=64.0)cout<<"light welter";
    else if(w<=69.0)cout<<"welter";
    else if(w<=75.0)cout<<"light middle";
    else if(w<=81.0)cout<<"middle";
    else if(w<=91.0)cout<<"light heavy";
    else cout<<"heavy";
    cout<<endl;
  }
  return 0;
}

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

const int INF = 1<<29;

typedef pair<int, int> P;

int N;
int t[16][20];
int dp[1 << 16];
int mt[1 << 16][16];
int ans;

int main(){
    while(true){
        scanf("%d", &N);
        if(N == 0) break;
        for(int i = 0; i < N; i++){
            for(int j = 0; j <= N; j++){
                scanf("%d", &t[i][j]);
            }
        }
        fill(dp, dp + (1 << N), INF);
        for(int i = 0; i < (1 << N); i++){
            fill(mt[i], mt[i] + 16, INF);
        }
        for(int i = 0; i < N; i++){
            mt[(1 << N) - 1][i] = t[i][0];
        }
        queue<int> bq;
        bool visited[1 << 16];
        fill(visited, visited + (1 << N), false);
        visited[(1 << N) - 1] = true;
        bq.push((1 << N) - 1);
        while(!bq.empty()){
            int b = bq.front(); bq.pop();
            for(int i = 0; i < N; i++){
                if((b >> i) & 1){
                    int nb = b ^ (1 << i);
                    if(visited[nb]) continue;
                    for(int j = 0; j < N; j++){
                        mt[nb][j] = min(t[j][i+1], mt[b][j]);
                    }
                    bq.push(nb);
                    visited[nb] = true;
                }
            }
        }
        queue<P> sq;
        sq.push(P((1 << N) - 1, 0));
        dp[(1 << N) - 1] = 0;
        while(!sq.empty()){
            P s = sq.front(); sq.pop();
            int b = s.first, cost = s.second;
            if(cost > dp[b]) continue;
            for(int i = 0; i < N; i++){
                if((b >> i) & 1){
                    int nb = b ^ (1 << i);
                    if(cost + mt[b][i] < dp[nb]){
                        dp[nb] = cost + mt[b][i];
                        sq.push(P(nb, dp[nb]));
                    }
                }
            }
        }
        printf("%d\n", dp[0]);
    }

    return 0;
}

Measured memory_bytes: 5912
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := 0
	ans := 0
	for i := 1; i <= n; i++ {
		fmt.Scan(&a)
		if i%2 == 1 && a%2 == 1 {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1768
#include <bits/stdc++.h>
using namespace std;
#define ELEM(array)  (sizeof (array) / sizeof *(array))
#define MOD 1000000007
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号
    vector<int> siz; 

    UnionFind(int N) : par(N), siz(N,1) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        if (siz[rx] < siz[ry]) swap(rx, ry); //データ構造をマージするテク．小を大にくっつける
        siz[rx] += siz[ry];
        par[ry] = rx;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x){ // 素集合のサイズ
        return siz[root(x)];
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> road(m);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        road[i]=make_pair(a,b);
    }
    UnionFind uf(n);
    vector<ll> able(m+1,0);
    for(int i=m-1;i>=0;i--){
        int a=road[i].first-1, b=road[i].second-1;
        able[i]= able[i+1];
        if(!uf.same(a,b)){
            able[i]+= uf.size(a)*uf.size(b);
            uf.unite(a,b);        
        }
    }
    rep(i,m) cout<<able[0]-able[i+1]<<endl;
    return 0;
}

Measured memory_bytes: 3712
#include <stdio.h>
int main()
{
	int n,i,k=0,t,j,s[100001];
	scanf("%d",&n);
	t=n;
	for(i=0;t>0;i++)
	{
		s[i]=t%10;
		t/=10;
		k=k+s[i];
			
	}
	if(n%k==0)
	printf("Yes\n");
	else printf("No\n");
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define pii pair<int, int> 
#define mod 1000000007
ll power(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b%2!=0) res=(res*a);
        a=(a*a);
        b/=2;
        if(res>INT_MAX){
            return INT_MAX;
        }
    }
    return res;
}
ll ncr(ll n,ll k){
    if(k==0||k==n) return 1ll;
    if(k>n-k) k=n-k;
    ll pro=1;
    for(ll i=0;i<k;i++){
        pro=(pro*(n-i))%mod;
        pro/=(i+1);
    }
    return (pro%mod);
}
vector<int> prime;
void seive(){
    vector<bool > isprime(101,true);
    for(int i=2;i*i<=100;i++){
        if(isprime[i]){
            for(int j=i*i;j<=100;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<=100;i++){
        if(isprime[i]) prime.push_back(i);
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a,b;
    cin>>a>>b;
    if(0>=a && 0<=b) cout<<"Zero";
    else if(b<0){
        ll x=abs(a-b)+1;
        if(x%2!=0) cout<<"Negative";
        else cout<<"Positive";
    }
    else cout<<"Positive";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	string s;
	cin>>s;
	ll n=s.size()-2;
	bool ch=false;
	if(s[0]==s[s.size()-1]){
		ch=true;
	}
	if(ch){
		cout << (n%2!=0?"Second":"First");
	}
	else{
		cout << (n%2!=0?"First":"Second");
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 512