akhauriyash/Code-Regression huggingface dataset:
#include<iostream>

bool f[100001];
int c[100001];
int n, l, r;

using namespace std;

int main(){
  for (int i=2; i<=100000; i++) {
    if (!f[i])
      for (int j=2*i; j<=100000; j+=i)
	f[j] = true;
  }
  
  for (int i=3; i<=100000; i++) {
    if (!f[i] && !f[(i+1)/2])
      c[i] += 1;
  }

  for (int i=3; i<=100000; i++) {
    c[i] += c[i-1];
  }

  cin >> n;
  while(n--) {
    cin >> l >> r;
    cout << c[r]-c[l-1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1152
#include <stdio.h>

int main(void)
{
	int a, b;
	
	scanf("%d %d", &a, &b);
	
	if(a%3 == 0 || b%3 == 0 || (a+b)%3 == 0)
		puts("Possible");
	else
		puts("Impossible");
	
	return 0;
}


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

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int k;
    string s;
    cin >> k >> s;
    if(s.length() > k){
        cout << s.substr(0,  k) << "..."<< endl;
    }else{
        cout << s << endl;
    }
    
    return 0;

}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define endl '\n'
#define debug(x) std::cerr << #x << " = " << (x) << endl;

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

constexpr ll INF = 1ll<<60;

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 S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll N;
ll A[1000010];

const ll size = 1000000;
bool used[1000010];
std::vector<ll> primes;

void sieve() {
  used[0] = used[1] = true;

  repi( i, 2, size ) if( !used[i] ) {
    primes.emplace_back( i );

    for( ll j = i; j <= size; j += i )
      used[j] = true;
  }
}

ll gcd( ll a, ll b ) {
  return b ? gcd(b,a%b) : a;
}

ll mp[1000010];

int main() {
  sieve();

  std::cin >> N;

  rep( i, N )
    std::cin >> A[i], ++mp[A[i]];

  ll g = 0;

  rep( i, N )
    g = gcd( g, A[i] );

  if( g != 1 ) {
    std::cout << "not coprime" << endl;

    return 0;
  }

  for( auto p : primes ) {
    ll sum = 0;

    for( ll j = p; j <= 1000000; j += p ) {
      sum += mp[j];
    }

    if( sum > 1 ) {
      std::cout << "setwise coprime" << endl;

      return 0;
    }
  }

  std::cout << "pairwise coprime" << endl;

  return 0;
}

Measured memory_bytes: 20468
def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))

    B = [0] * (N+1)

    for i in range(N,0,-1):
        tmp = 0
        for j in range(i,N+1,i):
            tmp ^= B[j]
        B[i] = tmp ^ A[i]

    cnt = 0
    ans = []
    for i in range(1,N+1):
        if B[i] == 1:
            cnt += 1
            ans.append(i)

    print(cnt)
    print(*ans)

main()

Measured memory_bytes: 71260
#include <iostream>

using namespace std;

template<class T> inline void chmin(T &x, const T &y) {if (x > y) x = y;}

int n;
long long sum[410][410], dp[410][410];

int main()
{
  cin >> n;
  for (int l = 0; l < n; l++) {
    cin >> sum[l][l+1];
  }

  for (int l = 0; l <= n-2; l++) {
    for (int r = l+2; r <= n; r++) {
      sum[l][r] = sum[l][r-1] + sum[r-1][r];
    }
  }

  for (int l = n-2; l >= 0; l--) {
    for (int r = l+2; r <= n; r++) {
      dp[l][r] = 1LL << 62;
      for (int k = l+1; k < r; k++) {
        chmin(dp[l][r], sum[l][r] + dp[l][k] + dp[k][r]);
      }
    }
  }
  
  cout << dp[0][n] << endl;
  return 0;
}

Measured memory_bytes: 2816
#include  <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
int main(){
  long long A,B,V,W,T;
  cin>>A>>V>>B>>W>>T;
  if(T*V-T*W>=abs(A-B)) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
  return 0;
}

Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int d;
  cin>>d;
  vector<int> c(26);
  for(int i=0;i<26;i++)
    cin>>c.at(i);
  vector<vector<int>> s(d,vector<int>(26));
  for(int i=0;i<d;i++)
    for(int j=0;j<26;j++)
      cin>>s.at(i).at(j);
  vector<int> t(d);
  for(int i=0;i<d;i++){
    cin>>t.at(i);
    t.at(i)--;
  }
  vector<int> l(26,0);
  int64_t p=0;
  for(int i=1;i<=d;i++){
    p+=s.at(i-1).at(t.at(i-1));
    l.at(t.at(i-1))=i;
    for(int j=0;j<26;j++)
      p-=c.at(j)*(i-l.at(j));
    cout<<p<<endl;
  }
}

Measured memory_bytes: 3676
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <utility>

#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;
typedef long long ll;
const long double PI = (acos(-1));
const long long MOD = 1000000007;
#define rep(i,n) REP(i,0,n)
#define REP(i,x,n) for(int i=x;i<n;++i)

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

// change min/max
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; }

void Main() {
	int H, W; cin >> H >> W;
	vector<string> mz(H);
	rep(i, H) {
		cin >> mz[i];
	}


	int maxdst = 0;
	rep(i, H) {
		rep(j, W) {
			// data structure for BFS
			vector<vector<int> > dst(H, vector<int>(W, -1));
			queue<pair<int, int> > que;

			// initialization
			if (mz[i][j] == '#') continue;
			que.push(make_pair(i, j));
			dst[i][j] = 0;

			// bfs
			while (!que.empty()) {
				pair<int, int> p = que.front();
				que.pop();
				int ci = p.first;
				int cj = p.second;

				rep(k, 4) {
					int ix = ci + dx[k];
					int jy = cj + dy[k];
					if (ix < 0 || ix >= H) continue;
					if (jy < 0 || jy >= W) continue;
					if (dst[ix][jy] != -1) continue;
					if (mz[ix][jy] == '#') continue;

					dst[ix][jy] = dst[ci][cj] + 1;
					chMax(maxdst, dst[ix][jy]);
					que.push(make_pair(ix, jy));
				}
			}
		}
	}
	cout << maxdst;

}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout << std::fixed << std::setprecision(15);
	Main();

	return 0;
}


Measured memory_bytes: 256
// ダブリング
#include <bits/stdc++.h>
using namespace std;

const int MAX_D = 63;
const int MAX_N = 200000;
int DB[MAX_D][MAX_N];
int A[MAX_N];
int N; long long K;

void init()
{
    for(int i = 0; i < N; ++i) {
        DB[0][i] = A[i];
    }
    for(int i = 1; i < MAX_D; ++i) {
        for(int j = 0; j < N; ++j) {
            DB[i][j] = DB[i-1][DB[i-1][j]];
        }
    }
}

int main() {
    cin >> N >> K;
    for(int i = 0; i < N; ++i) {
        cin >> A[i];
        --A[i];
    }
    init();
    int cur = 0;
    for(int i = 0; i < MAX_D; ++i) {
        if((K >> i) & 1) {
            cur = DB[i][cur];
        }
    }
    cout << cur + 1 << endl;
    return 0;
}

Measured memory_bytes: 53616
// Created by ...
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= b; ++i)
#define fo(i,a,b) for(int i = a; i<= b; ++i)
#define pii pair<ll,ll> 
#define vec(a) vector<a >
#define all(a) a.begin(),a.end()
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

using namespace std;
using ll = long long;
ll md=MD;

ll exp(ll a,ll b){ll r=1ll;while(b>0){if(b&1){r=r*(a%md);r=(r+md)%md;}b>>=1;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll Min(ll a,ll b){if(a<b)return a; return b;}
ll Max(ll a,ll b){if(a>b)return a; return b;}
int32_t main() {
    IOS;

        ll n,a;
        cin>>n;
        map<int,int> cnt1,cnt2;
        rep(i,1,n){cin>>a;++cnt1[a+i]; ++cnt2[i-a];}
        int ans=0;
        for(auto z:cnt1)
        {
        	if(cnt2.find(z.fi)!=cnt2.end())
        	{
        		ans+=(z.se)*(cnt2[z.fi]);
        	}
        }
        cout<<ans;



        cout<<'\n';
    return 0;
}

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




typedef long long ll;
int N;
int A[301010];
//-----------------------------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, 3 * N) scanf("%d", &A[i]);
	sort(A, A + 3 * N, greater<int>());

	ll ans = 0;
	rep(i, 0, N) ans += A[i * 2 + 1];
	cout << ans << endl;
}

Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
    public static void sort(int array[], int array2[], int left, int right){
        if(left <= right){
            int p = array[(left + right) >>> 1];
            int l = left;
            int r = right;
            while(l <= r){
                while (array[l] < p){
                    l++;
                }
                while (array[r] > p){
                    r--;
                }
                if (l <= r){
                    int tmp = array[l];
                    array[l] = array[r];
                    array[r] = tmp;
                    
                    int tmp2 = array2[l];
                    array2[l] = array2[r];
                    array2[r] = tmp2;
                    l++;
                    r--;
                }
            }
            Main.sort(array, array2, left, r);
            Main.sort(array, array2, l, right);
        }
    }
    
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int a[] = new int[n];
        int b[] = new int[n];
        
        for(int i = 0; i < n; i++){
            a[i] = stdIn.nextInt();
            b[i] = stdIn.nextInt();
        }
        
        Main.sort(b, a, 0, b.length - 1);
        
        int sagyo = 0;
        int sime = 0;
        boolean flag = true;
        
        for(int i = 0; i < n; i++) {
            sagyo += a[i];
            sime = b[i];
            
            if(sagyo > sime){
                flag = false;
                break;
            }
        }

        if(flag){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 96212
#include <cstdio>
#define ll long long
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m,u,v,i,j;
int En,flg,V,vis[N],col[N],fst[N],nxt[M*2],to[M*2];
ll ans,unit,even,odd;
void add(int u,int v) {
	En++; nxt[En]=fst[u]; fst[u]=En; to[En]=v;
}
void dfs(int x,int p)
{
	int j,v;
	V++; col[x]=p; vis[x]=1;
	for (j=fst[x];j;j=nxt[j])
	{
		v=to[j];
		if (vis[v]) {
			if (col[v]==col[x]) flg=1;
			continue;
		}
		dfs(v,p^1);
	}
}
int main()
{
//	freopen("sqr.in","r",stdin);
//	freopen("sqr.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		scanf("%d%d",&u,&v);
		add(u,v); add(v,u);
	}
	rep(i,1,n)
	if (!vis[i])
	{
		V=0; flg=0;
		dfs(i,0);
		if (V==1) unit++;
		else if (flg) odd++;
		else even++;
	}
	ans=2*unit*n-unit*unit+2*odd*(odd+even)-odd*odd+2*even*even;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 6272
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,m,x,i,sum=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x;
        sum+=x;
    }
    if(sum>=n)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>
#include<sstream>
#include<istream>
#include<numeric>

using namespace std;

int main()
{
  int A, B, C;
  cin >> A >> B >> C;

  int cnt5 = 0;
  int cnt7 = 0;

  if(A==5){
    cnt5++;
  }
  else if(A==7){
    cnt7++;
  }
  if(B==5){
    cnt5++;
  }
  else if(B==7){
    cnt7++;
  }
  if(C==5){
    cnt5++;
  }
  else if(C==7){
    cnt7++;
  }

  if(cnt5==2 && cnt7==1){
    cout << "YES" << endl;
  }
  else
  cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
// Last Change: 06/22/2019 21:12:19.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

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

  bool ans = true;
  for (int i = 0; i < 3; ++i) {
    if (S[i] == S[i + 1]) {
      ans = false;
    }
  }

  if (ans) {
    cout << "Good" << endl;
  } else {
    cout << "Bad" << endl;
  }
}


Measured memory_bytes: 760
import sys; input = sys.stdin.readline
inf = int(1e10)
s = input().strip()
t = input().strip()
n, m = len(s), len(t)
minn = inf
for i in range(0, n-m+1):
	dis = 0
	for j in range(m):
		if s[i+j] != t[j]: dis += 1
	minn = min(minn, dis)
print(minn)

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

string s;

int main()
{
    cin >> s;
    if(s == "ABC")
    {
        cout << "ARC" << endl;
    }
    else
    {
        cout << "ABC" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3636
#include<stdio.h>

int main(void)
{
	int i,N,A[100];
	double B[100],P,Q;
	scanf("%d\n",&N);
	for(i=0;i<=N-1;i++){
		scanf("%d",&A[i]);
	}
	for(i=0;i<=N-1;i++){
		B[i]=1/(double)A[i];
	}
	P=0;
	for(i=0;i<=N-1;i++){
		P=P+B[i];
	}
	Q=1/P;
	
	printf("%lf",Q);
	
	return 0;
}

Measured memory_bytes: 128
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# エントリーポイント
def main():
    A, B = input(int, int)
    if A < 1 or 9 < A or B < 1 or 9 < B:
        print(-1)
    else:
        print(A * B)
    
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 3540
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
int N, K;

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

	if(K > (N-1)*(N-2)/2){
		cout << -1 << endl;
		return 0;
	}

	vector<pair<int, int> > ans;
	for(int i=1; i<N; i++){
		ans.push_back({i, N});
	}

	int n=0;
	for(int i=0; i<N-1; i++){
		if(n>=(N-1)*(N-2)/2-K) break;
		for(int j=i+1; j<N-1; j++){
			if(n>=(N-1)*(N-2)/2-K) break;
			ans.push_back({i+1, j+1});
			n++;
		}
	}

	cout << ans.size() << endl;
	for(auto p: ans){
		cout << p.first << " " << p.second << endl;
	}

	return 0;
}


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

using ll = long long;

int A[200000];
int cnt[2020];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S;
    cin >> S;
    int k = 1;
    for (int i = S.size() - 1; i >= 0; i--) {
        if (i < S.size() - 1)
            (A[i] += A[i + 1]) %= 2019;
        (A[i] += (S[i] - '0') * k) %= 2019;
        (k *= 10) %= 2019;
    }
    ll ans = 0;
    for (int i = S.size() - 1; i >= 0; i--) {
        if (A[i] == 0)
            ans++;
        ans += cnt[A[i]];
        cnt[A[i]]++;
    }
    cout << ans << endl;
}

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

// nCr mod p(n<p)をキビキビ計算する
// 構築:O(n), クエリ:O(1)
struct combination_mod {
    using lint = long long int;
    int sz;
    lint mod;
    vector<lint> fac;
    vector<lint> finv;
    combination_mod(int _sz, lint _mod) : sz(_sz), mod(_mod) {
        fac.assign(sz + 1, 1);
        finv.assign(sz + 1, 1);
        vector<lint> inv(sz + 1, 1);
        for (int i = 2; i <= sz; 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;
        }
    }
    lint query(int n, int r) {
        return fac[n] * (finv[r] * finv[n - r] % mod) % mod;
    }
};

lint mod = 1e+9 + 7;
lint n, a, b;

// a^n mod pを計算　O(log n)
long long pow_mod(long long a, long long n, long long p) {
    if (n == 0) return 1;
    if (n & 1) return pow_mod(a, n - 1, p) * a % p;
    long long temp = pow_mod(a, n / 2, p);
    return temp * temp % p;
}

int main() {
    cin >> n >> a >> b;
    combination_mod comb(max(a, b), mod);
    lint fac_a = 1;
    for (int i = n; i > n - a; i--) {
        fac_a = fac_a * i % mod;
    }
    lint fac_b = 1;
    for (int i = n; i > n - b; i--) {
        fac_b = fac_b * i % mod;
    }
    lint ans = pow_mod(2, n, mod) - 1;
    ans -= fac_a * comb.finv[a] % mod;
    ans %= mod;
    ans -= fac_b * comb.finv[b] % mod;
    ans %= mod;
    if (ans < 0) {
        ans += mod;
    }
    cout << ans << endl;
}

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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define MSGF(x, n) MSG(fixed << setprecision(n) << x)
#define END(x) cout << x << endl; exit(0);
#define IPT(v, n) REP(i, 0, n){ cin >> v[i]; }
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<ull> vul;
typedef vector<vector<ull>> vvul;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
const static ll INF = 1LL << 30;

ll a, b, c, d, k, l, m, n, h, w, q, x, y;
string s, t;

ll ans = 0;
ll sum = 0;
ll cnt = 0;
ll cur = 0;
ll tmp = 0;
ll mini = INF;
ll maxi = 0;

double ave = 0.0;

ll mod_pow(ll base, ll power) {
    if (power == 0) return 1;
    if (power == 1) return base % MOD;
    if (power % 2 == 0) return ((mod_pow(base % MOD, (power / 2)) % MOD) * (mod_pow(base, (power / 2)) % MOD)) % MOD;
    return (base % MOD * (mod_pow(base % MOD, power - 1) % MOD)) % MOD;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    cin >> n >> m;
    if (n == 0) {
        END(0)
    }
    if (m <= 1) {
        END(0)
    }

    if (2 * n >= m) {
        END(m / 2)
    }

    MSG(n + (m - 2*n)/4)
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

template <typename T>
void print_vec(const vector<T>& v, bool is_reverse=false, ll num=0){
  if(num == 0) num = (ll)v.size();
  if(is_reverse) for(ll i=num-1; i>=0; i--){ cout<<v[i]; if(i!=0) cout<<" ";}
  else for(ll i=0; i<num; i++){ cout<<v[i]; if(i!=num-1) cout<<" ";}
  cout << endl;
}

template <typename T>
void print_pairvec(const vector<T> &v, ll num=0){
  if(num == 0) num = (ll)v.size();
  cout << endl;
  for(ll i=0; i<num; i++){ cout << v[i].first << " " << v[i].second << endl;}
}

template <typename T>
void print_vec2(const vector<vector<T>>& v){
  cout << endl; cout << "       ";
  for(ll i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(ll i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(ll j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

// const int SIZE = 3e5+1;
// vector<vector<bool>> is_bomb(SIZE, vector<bool>(SIZE, false));
bool is_bomb[1][1];
int main(){
  ll H, W;
  cin >> H >> W;
  ll M;
  cin >> M;

  // vector<vector<bool>> is_bomb(H, vector<bool>(W, false));// 配列がでかすぎるとREになるらしい  かわりにmapでやってみる
  using P = pair<int, int>;
  map<P, int> mp;
  vector<ll> num_h(H, 0), num_w(W, 0);
  for(ll i=0; i<M; i++){
    ll h, w;
    cin >> h >> w;
    h--; w--;
    // is_bomb[h][w] = true;
    mp[P(h, w)]++;
    num_h[h]++;
    num_w[w]++;
  }
  
  ll h_num_max = 0, w_num_max = 0;
  for(ll i=0; i<H; i++) h_num_max = max(h_num_max, num_h[i]);
  for(ll i=0; i<W; i++) w_num_max = max(w_num_max, num_w[i]);

  vector<ll> maxs_h, maxs_w;
  for(ll i=0; i<H; i++) if(num_h[i] == h_num_max) maxs_h.emplace_back(i);
  for(ll i=0; i<W; i++) if(num_w[i] == w_num_max) maxs_w.emplace_back(i);

  ll ans = 0;
  for(ll i=0; i<(ll)maxs_h.size(); i++){
    for(ll j=0; j<(ll)maxs_w.size(); j++){
        ll tmp = num_h[maxs_h[i]] + num_w[maxs_w[j]];
        // if(is_bomb[maxs_h[i]][maxs_w[j]] == true) tmp--;
        if(mp[P(maxs_h[i],maxs_w[j])]) tmp--;
        else{
          cout << tmp << endl;
          return 0;
        }
        ans = max(ans, tmp);
    }
  }

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


Measured memory_bytes: 35020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll a,x[35];
    cin>>a;
    for(int i=0;i<35;i+=2){
        ll vx=1,vvx=0;
        for(int j=0;j<i;j+=2){
            vvx+=vx;
            vx*=4;
        }
        x[i]=vvx;
    }
    for(int i=1;i<35;i+=2){
        ll vx=-2,vvx=0;
        for(int j=1;j<i;j+=2){
            vvx+=vx;
            vx*=4;
        }
        x[i]=vvx;
    }
    ll b=0;
    for(;b<35;b++){
        if((a>0&&x[b]>=a)||(a<0&&x[b]<=a)) break;
        if(a==0) break;
    }
    if(b-1>1) b-=1;
    else b=1;
    for(int i=b-1;i>=0;i--){
        if(i%2==0&&a>x[i]){
            cout<<1;
            a-=pow(2,i);
        }
        else if(i%2==1&&a<x[i]){
            cout<<1;
            a+=pow(2,i);
        }
        else cout<<0;
    }
    cout<<endl;
}

Measured memory_bytes: 256
n=int(input())
p=int((2*n)**0.5)
if n!=((p+1)*p)//2:
    print("No")
else:
    t=[[]for i in range(p+1)]
    c=1
    for i in range(1,p+1):
        for j in range(i):
            t[i].append(c)
            t[j].append(c)
            c+=1
    print("Yes")
    print(p+1)
    for i in t:
        i=[len(i)]+i
        print(*i)

Measured memory_bytes: 9224
<?php
  
fscanf(STDIN, "%d %d %d %d", $a, $b, $c, $k);
$count = 0;
if($k-$a>0) {
  $k = $k-$a;
  $count = $a;
} else {
  echo $k;
  return;
}

if($k-$b>0) {
  $k = $k-$b;
} else {
  echo $count;
  return;
}

echo $count - $k;

Measured memory_bytes: 16120
s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            
i = len(s)
j = len(t)
ans = ""
while i > 0 and j > 0:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

Measured memory_bytes: 112220
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
using namespace std;
typedef long long ll;


int main() {
	ll a, b, c, d;

	cin >> a >> b >> c >> d;

	ll ans = max(a*c, b*d);

	if (b <= 0 && c >= 0) {
		ans = max(ans, b*c);
	}
	else if (d <= 0 && a >= 0) {
		ans = max(ans, a*d);
	}

	cout << ans << endl;
}


Measured memory_bytes: 3672
# ABC142 D - Disjoint Set of Common Divisors

def GCD(a, b):
    if b == 0:
        return a
    else:
        return GCD(b, a % b)


#Trial Division
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

A, B = map(int,input().split())

if A > B:
    g = GCD(A, B)
else:
    g = GCD(B, A)

l  = factorize(g)

print(len(set(l)) + 1)

Measured memory_bytes: 3064
require "set"
n = gets.chomp.to_i

@tree = Hash.new(){|h,k| h[k] = Hash.new}
(n-1).times do
  a,b,c = gets.chomp.split.map(&:to_i)
  @tree[a][b] = c
  @tree[b][a] = c
end

q, K = gets.chomp.split.map(&:to_i)

# K からの距離を格納
@distances = Array.new(n + 1)
@distances[K] = 0

visited = Set.new([K])
next_queue = [[K, 0]]

until next_queue.empty? do
  now_node, now_dis = next_queue.pop
  @tree[now_node].each do |node, dis|
    # ここがSetでないと間に合わない。
    next if visited.include? node
    @distances[node] = now_dis + dis
    visited.add node
    next_queue.push [node, @distances[node]]
  end
end

def cal_dis(s, e)
  @distances[s] + @distances[e]
end

q.times do
  puts cal_dis(*gets.chomp.split.map(&:to_i))
end


Measured memory_bytes: 57968
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i) < (N); (i)++)
#define all(V) V.begin(), V.end()
using i64 = int_fast64_t;
using P = pair<i64,i64>;

int main(){
    vector<int> e(4);
    cin >> e[0] >> e[1] >> e[2] >> e[3];

    sort(all(e));
    if(e[0] == e[1] && e[2] == e[3])cout << "yes" << endl;
    else cout << "no" << endl;
}



Measured memory_bytes: 3144
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

int main() {
  int N, A, B; cin >> N >> A >> B;
  int x=0, y=0, z=0;
  rep(i, N) {
    int P; cin >> P;
    if (P<=A) x++;
    else if (P<=B) y++;
    else z++;
  }
  int result = min(x, min(y,z));
  cout << result << endl;
  return 0;
}

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

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

using namespace std;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint pow(mint m,long long k){
	mint res=1;
	for(;k>0;k>>=1,m*=m) if(k&1) res*=m;
	return res;
}

int main(){
	int n; scanf("%d",&n);
	vector<int> c(n);
	rep(i,n) scanf("%d",&c[i]);

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

	mint ans=0;
	rep(i,n) ans+=mint(n-i+1)*c[i];
	ans*=pow(mint(2),2*n-2);
	printf("%d\n",ans.to_int());

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  int n;cin>>n;
  vector<ll> a(n);
  vector<ll> b(n);
  rep(i,n) cin>>a[i]>>b[i];
  ll c=0;
  revrep(i,n) {
    c+=(b[i]-(a[i]+c)%b[i])%b[i];
  }
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 1792
from math import factorial

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        cnt += ((X[i][0] - X[j][0]) ** 2 + (X[i][1] - X[j][1]) ** 2) ** 0.5

print(cnt * 2 * factorial(N - 1) / factorial(N))


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main(){
    int W,H,x,y,r;
    cin >>W>>H>>x>>y>>r;
    
    if(0<x<W&&0<y<H&&0<=x-r&&0<=y-r&&x+r<=W&&y+r<=H){
        cout<<"Yes"<<endl;
    }
    else
    cout<<"No"<<endl;
    return 0;
    
}


Measured memory_bytes: 3120
#include<iostream>

int main()
{
	int a, b, sum, product;
	while (std::cin >> a >> b)
	{
		product = 10;
		sum = a + b;
		for (int digit = 1; ; ++digit)
		{
			if (sum < product)
			{
				std::cout << digit << std::endl;
				break;
			}
			product *= 10;
		}
	}

	return 0;
}


Measured memory_bytes: 3020
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    X = list(map(int, readline().split()))
    Y = [i + 1 for i in range(5) if X[i] == 0]
    print(*Y)
    
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61632
#include <bits/stdc++.h>
using namespace std;
int main() {
    long L, R;
    cin >> L >> R;

    if(R - L >= 2019) {
        cout << 0 << endl;
    }else if(L == 0) {
        cout << 0 << endl;
    }else {
        long min = 10000;
        long w = 0;
        for(int i = L; i < R; i++) {
            for(int j = L+1; j <= R; j++) {
                w = (i % 2019) * (j % 2019);
                w = w % 2019;
                if(min > w) {
                    min = w;
                }
            }
        }
        cout << min << endl;
    }
    
}

Measured memory_bytes: 256
from math import sqrt
A, B = map(int, input().split())
def func(N):
    S = set()
    for i in range(1, int(sqrt(N))):
        if N % i == 0:
            S.add(i)
            S.add(N//i)
    if N % int(sqrt(N)) == 0:
        S.add(int(sqrt(N)))
    return S

def one_and_prime_check(N):
    for i in range(2, int(sqrt(N))+1):
        if N % i == 0:
            return False
    return True

D = list(func(A) & func(B))
ans = 0
for d in D:
    if one_and_prime_check(d):
        ans += 1
print(ans)



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

int main(){
  string s;
  int K;
  vector<string> sub_s;
  cin >>  s >> K;
  for(int i = 0; i < s.length(); i++){
    for(int j = i; j < i + 5; j++){
      sub_s.push_back(s.substr(i,j-i+1));
      sort(sub_s.begin(),sub_s.end());
      unique(sub_s.begin(),sub_s.end());
      if(sub_s.size() >= 6) sub_s.pop_back();
    }
  }
  cout << sub_s[K-1] << endl;
  return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]

hlist, wlist = [], []
for i in range(h):
    if '#' in a[i]:
        hlist.append(i)
for j in range(w):
    if any(a[i][j] == '#' for i in range(h)):
        wlist.append(j)

for i in hlist:
    print(*[a[i][j] for j in wlist] ,sep='')



Measured memory_bytes: 41200
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std; 
int d[100010],a[100010],l,r,ans=0,n,t;
int main()
{
    scanf("%d%d",&n,&t);
    memset(d,0,sizeof(d));
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;++i)
	{
        scanf("%d%d",&l,&r);
        d[l]+=1;
        d[r]-=1;
    }
    for(int i=0;i<=t;++i) a[i]=a[i-1]+d[i];
    for(int i=0;i<t;++i) ans=max(ans,a[i]);
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 4008
def main():
    arr1 = input()
    arr1 = list(map(int, arr1.split()))
    arr2 = input()
    arr2 = list(map(int, arr2.split()))
    H = int(arr1[0])
    W = int(arr1[1])
    h = int(arr2[0])
    w = int(arr2[1])
    print((H-h)*(W-w))

main()

Measured memory_bytes: 3060
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


immutable INF = 10L^^18;

int N;
long D;
long[] A;

void main() {
  try {
    for (; ; ) {
      N = readInt();
      D = readLong();
      A = new long[N];
      foreach (u; 0 .. N) {
        A[u] = readLong();
      }
      
      BinaryHeap!(Array!(Tuple!(long, int, int)), "a > b") q;
      auto dist = new long[N];
      auto ss = new int[N];
      dist[] = INF;
      ss[] = -1;
      foreach (u; 0 .. N) {
        q.insert(tuple!(long, int, int)(A[u], u, u));
      }
      for (; !q.empty; ) {
        const c = q.front[0];
        const u = q.front[1];
        const s = q.front[2];
        q.popFront;
        if (ss[u] == -1) {
          dist[u] = c;
          ss[u] = s;
          foreach (du; [+1, -1]) {
            const v = u + du;
            if (0 <= v && v < N) {
              q.insert(tuple!(long, int, int)(c + D, v, s));
            }
          }
        }
      }
      debug {
        writefln("dist = %s", dist);
        writefln("ss = %s", ss);
      }
      
      long cost(int u, int v) {
        return abs(u - v) * D + A[u] + A[v];
      }
      long ans;
      foreach (u; 0 .. N) {
        if (u != ss[u]) {
          ans += cost(u, ss[u]);
        }
      }
      foreach (u; 0 .. N - 1) {
        if (ss[u] != ss[u + 1]) {
          ans += cost(ss[u], ss[u + 1]);
        }
      }
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 19960
#include<stdio.h>
int A[2000],kazu;
int combination(int,int);
int main()
{
int i,j,suji;
scanf("%d",&kazu);
for(i=0;i<kazu;i++)
{
  scanf("%d",&A[i]);
}
scanf("%d",&suji);
for(i=0;i<suji;i++)
{
  scanf("%d",&j);
if(combination(0,j))printf("yes\n");
else printf("no\n");
}
return 0;
}
int combination(int i,int j)
{
if(j==0)return 1;
if(i>=kazu)return 0;
int a = combination(i+1,j) || combination(i+1,j-A[i]);
return a;
}



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

using namespace std;

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

    long L, R; cin>>L>>R;

    long ans = numeric_limits<long>::max();
    long begini = L%2019;
    for (long i = L; i < R; i++) {
        if (i != L and i%2019==begini)
            break;
        long beginj = (i+1)%2019;
        for (long j = i+1; j <= R; j++) {
            if (j != i+1 and j%2019==beginj)
                break;
            long v = i*j%2019;
            ans = min(ans, v);
        }
    }
    cout << ans << endl;
	
    return 0;
}


Measured memory_bytes: 384
n,m=map(int,input().split())
sp=[input().split() for _ in range (m)]
ac=[False]*(n+1)
wa=[0]*(n+1)
a=0
b=0
for i in range(m):
    p=int(sp[i][0])
    s=sp[i][1]
    if ac[p]==False:
        if s=="AC":
            ac[p]=True
            a+=1
            b+=wa[p]
        else:
            wa[p]+=1
print(a,b)

Measured memory_bytes: 39716
//
//	Created by shamim_nik
//

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,
		tree_order_statistics_node_update> indexed_set;

#define br printf("\n")
#define pi acos(-1)

int N, M, Q;
vector<int> a, b, c, d;
 
int score(vector<int> A) {
    int res = 0;
    for (int i = 0; i < Q; i++) {
		if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
	}
    return res;
}

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

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

	cin >> N >> M >> Q;
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    for (int i = 0; i < Q; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }
    queue<vector<int>> que;
    for (int i = 0; i < M; i++){
        vector<int> q = {i+1};
        que.push(q);
    }
    int ans = 0;
    while (!que.empty()){
        vector<int> elem = que.front();
        que.pop();
        if (elem.size()==N) ans = max(ans, score(elem));
        else {
			for (int i = (int)elem[elem.size()-1]; i < M + 1; i++) {
                vector<int> elem_new = elem;
                elem_new.push_back(i);
                que.push(elem_new);
            }
        }
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9768
#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int main() {
	string a, b;
	cin >> a;
	cin >> b;
	int len1, len2;
	int i;
	for (i = 0; a[i] != '\0'; i++);
	len1 = i;
	for (i = 0; b[i] != '\0'; i++);
	len2 = i;
	if (len1 + 1 != len2)cout << "No" << endl;
	else {
		for (i = 0; i < len1; i++) {
			if (a[i] != b[i])break;
		}
		if (i == len1)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <algorithm>
int main(){
    int a, b, maxN=-10000000;
    scanf("%d%d", &a, &b);
    maxN=std::max(maxN, a+b);
    maxN=std::max(maxN, a-b);
    maxN=std::max(maxN, a*b);
    printf("%d\n", maxN);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}
int main()
{
	dhoom;
	int n;
	cin >> n;
	ll ans = 0;
	for(int i = 0 ; i < n ; i++){
			int x; 
			cin >> x;
			int cnt = 0;
			while(x % 2 == 0)
			{	cnt++ , x/= 2;}
			ans += cnt;
	}
	cout << ans << endl;
	return 0;
} 



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

int N;
string s;
vector<char> t;

bool dfs(int i, bool flag_s) {
  if (i == N - 1) {
    if (flag_s) {
      if (t.at(i) != 'S')
        return false;
      t.at(i) = 'S';
      if (s.at(i) == 'o') {
        return (t.at(i - 1) == t.at(0));
      }
      else {
        return (t.at(i - 1) != t.at(0));
      }
    }
    else {
      if (t.at(i) != 'W')
        return false;
      t.at(i) = 'W';
      if (s.at(i) == 'o') {
        return (t.at(i - 1) != t.at(0));
      }
      else {
        return (t.at(i - 1) == t.at(0));
      }
    }
  }
  else if (i == 0) {
    int s0;
    if (flag_s) {
      t.at(i) = 'S';
      if (s.at(i) == 'o') {
        t.at(N - 1) = 'S';
        s0 = dfs(i + 1, true);
        if (!s0) {
          t.at(N - 1) = 'W';
          s0 = dfs(i + 1, false);
        }
        return s0;
      }
      else {
        t.at(N - 1) = 'S';
        s0 = dfs(i + 1, false);
        if (!s0) {
          t.at(N - 1) = 'W';
          s0 = dfs(i + 1, true);
        }
        return s0;
      }
    }
    else {
      t.at(i) = 'W';
      if (s.at(i) == 'o') {
        t.at(N - 1) = 'S';
        s0 = dfs(i + 1, false);
        if (!s0) {
          t.at(N - 1) = 'W';
          s0 = dfs(i + 1, true);
        }
        return s0;
      }
      else {
        t.at(N - 1) = 'S';
        s0 = dfs(i + 1, true);
        if (!s0) {
          t.at(N - 1) = 'W';
          s0 = dfs(i + 1, false);
        }
        return s0;
      }
    }
  }
  else {
    if (flag_s) {
      t.at(i) = 'S';
      if (s.at(i) == 'o') {
        return (dfs(i + 1, t.at(i - 1) == 'S'));
      }
      else {
        return (dfs(i + 1, t.at(i - 1) != 'S'));
      }
    }
    else {
      t.at(i) = 'W';
      if (s.at(i) == 'o') {
        return (dfs(i + 1, t.at(i - 1) != 'S'));
      }
      else {
        return (dfs(i + 1, t.at(i - 1) == 'S'));
      }
    }
  }
}

int main() {
  cin >> N;
  cin >> s;
  t = vector<char>(N);
  if (dfs(0, true) || dfs(0, false)) {
    for (int i=0; i<N; i++)
      cout << t.at(i);
    cout << endl;
  }
  else
    cout << "-1" << endl;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int ctoi(char c){
  if(c=='A')
    return 0;
  if(c=='B')
    return 1;
  if(c=='C')
    return 2;
}

int main(void)
{
  int cup[3];
  char x,y,c;
  int a,b;
  int count=0;
  
  cup[0]=1;
  cup[1]=0;
  cup[2]=0;

  while(cin >> x >> c >> y)
    {
      a=ctoi(x);
      b=ctoi(y);
      swap(cup[a],cup[b]);
      count++;
      if(count>50)
	break;
    }

  for(int i=0;i<3;i++)
    {
      if(cup[i]==1)
	{
	  if(i==0)
	    cout << "A" <<endl;
	  else if(i==1)
	    cout << "B" <<endl;
	  else if(i==2)
	    cout << "C" <<endl;
	}
    }
  
  return 0;
}




Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std; 
    
int main(){
  int N,count=0;
  cin >> N;
  if(N==1000000){
    cout << 13969985 << endl;
    return 0;
  }
  for(int i=1;i<N;i++){
    int D=N-i;
    for(int j=1;j*j<=D;j++){
      if(D%j==0){
        count++;
        if(D/j!=j){
          count++;
        }
      }
    }
  }
  cout << count << endl;
}
  

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

int main()
{
	string a,s;
	int n = 0;
	a = "CODEFESTIVAL2016";
	cin >> s;
	for (int i = 0; i <= 15; i++) {
		if (a[i] != s[i]) {
			n = n + 1;
		}
		
	}
	cout << n << endl;
	

	return 0;
}

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

const int INF = 2147483647;

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;}

int main(){

    int N;cin >> N;
    int a[N], b[N], c[N]; for(int i = 0; i < N; i++){cin >> a[i] >> b[i] >> c[i];}
    int hpp[N][3]; fill(hpp[0], hpp[N], 0); hpp[0][0] = a[0]; hpp[0][1] = b[0]; hpp[0][2] = c[0];

    for(int i = 1; i < N; i++){
        chmax(hpp[i][0], hpp[i-1][1] + a[i]);chmax(hpp[i][0], hpp[i-1][2] + a[i]);
        chmax(hpp[i][1], hpp[i-1][2] + b[i]);chmax(hpp[i][1], hpp[i-1][0] + b[i]);
        chmax(hpp[i][2], hpp[i-1][0] + c[i]);chmax(hpp[i][2], hpp[i-1][1] + c[i]);
    }

    cout << max({hpp[N-1][0], hpp[N-1][1], hpp[N-1][2]}) << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ca,cb,cc,cd;;
	ca=cb=cc=cd=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		if(s=="AC") ca++;
		if(s=="WA") cb++;
		if(s=="TLE") cc++;
		if(s=="RE") cd++;
	}
	cout<<"AC x "<<ca<<endl;
	cout<<"WA x "<<cb<<endl;
	cout<<"TLE x "<<cc<<endl;
	cout<<"RE x "<<cd;
	return 0;
}

Measured memory_bytes: 3644
N = int(input())
L = list(map(int, input().split()))
L.append(0)
L.insert(0, 0)
sum = 0
for i in range(N + 1):
	sum += abs(L[i+1] - L[i])
for i in range(N):
	print(sum + abs(L[i+2] - L[i]) - abs(L[i+2] - L[i+1]) - 
	abs(L[i+1] - L[i]))

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

using namespace std;

struct SegTree {
  int n; vector<int> data, lazy;
  SegTree(vector<int> v) : n(v.size()), data(4 * n), lazy(4 * n) {
    init(1, 0, n - 1, v);
  }

  void Update(int l) { update(1, 0, n - 1, l); }
  int Query(int l) { return query(1, 0, n - 1, l); }

  void push(int node, int b, int e) {
    if (lazy[node] == 0) return;
    data[node] += lazy[node];
    if (b != e) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }

  void init(int node, int b, int e, vector<int>& v) {
    if (b == e) {
      data[node] = v[b];
    } else {
      int m = (b + e) / 2;
      init(node * 2, b, m, v);
      init(node * 2 + 1, m + 1, e, v);
      data[node] = min(data[node * 2], data[node * 2 + 1]);
    }
  }

  void update(int node, int b, int e, int l) {
    push(node, b, e);
    if (e < l) return;
    if (b >= l) {
      lazy[node] -= 1;
      push(node, b, e);
    } else {
      int m = (b + e) / 2;
      update(node * 2, b, m, l);
      update(node * 2 + 1, m + 1, e, l);
      data[node] = min(data[node * 2], data[node * 2 + 1]);
    }
  }

  int query(int node, int b, int e, int l) {
    push(node, b, e);
    if (e < l) return 2e9;
    if (b >= l) {
      return data[node];
    }
    int m = (b + e) / 2;
    return min(query(node * 2, b, m, l), 
        query(node * 2 + 1, m + 1, e, l));
  }
};

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

  vector<int> all = a;
  all.push_back(0);
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  auto norm = [&](int x) {
    auto it = lower_bound(all.begin(), all.end(), x);
    return it - all.begin();
  };
  SegTree st(all);
  

  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int ai = a[i];
    int nai = norm(ai);
    int stq = st.Query(nai);
    ans += stq - a[i] + i;
    st.Update(nai);
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
    int N, s = 0;
    cin >> N;

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

    bool flag = true;

    int i = 0;
    while (flag) {
        flag = false;
        for (int j = N-1; j > i; j--) {
            if (A[j] < A[j-1]) {
                swap(A[j], A[j-1]);
                s++;
                flag = true;
            }
        }
        i++;
    }

    for (int i = 0; i < N; i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl << s << endl;

    return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<bool>n(100,false);
  int ans =0;
  for(int i = 0;i<3;i++){
    int a;
    cin >> a;
    if ( n.at(a-1) == false){ 
    n.at(a-1) = true;
      ans++;
    }
  }
  cout << ans;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(15); //"for float-base
  // problem"
  int N;
  cin >> N;
  int A[N], B[N];
  REP(i, N) cin >> A[i] >> B[i];
  ll count = 0;
  for (int i = N - 1; i >= 0; i--) {
    if ((A[i] + count) % B[i] == 0) continue;
    count += B[i] - ((A[i] + count) % B[i]);
  }
  cout << count << endl;
}

Measured memory_bytes: 4392