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

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

std::vector<std::vector<int>> Datum;


int main(void){
    int n, k; scanf("%d%d", &n, &k);
    int K = 2 * k;
    Datum.resize(K+1, std::vector<int>(K+1, 0));
    REP(i, n){
        int x, y; char c; scanf("%d%d %c", &x, &y, &c);
        if(c == 'W') x += k;
        x %= K; y %= K;
        Datum[x+1][y+1]++;
    }
    /*
    REP(i, K+1){
        REP(j, K+1) printf("%d ", Datum[i][j]);
        putchar('\n');
    }*/
    for(int x = 0; x <= K; ++x) for(int y = 1; y <= K; ++y) Datum[x][y] += Datum[x][y-1];
    for(int y = 0; y <= K; ++y) for(int x = 1; x <= K; ++x) Datum[x][y] += Datum[x-1][y];
    
    /*
    REP(i, K+1){
        REP(j, K+1) printf("%d ", Datum[i][j]);
        putchar('\n');
    }*/

    int ans = 0;
    for(int x = 0; x < k; ++x) for(int y = 0; y < k; ++y){
        int A1 = Datum[x][y];
        int A2 = Datum[K][y] - Datum[x+k][y];
        int A3 = Datum[x][K] - Datum[x][y+k];
        int A4 = Datum[x+k][y+k] - Datum[x+k][y] - Datum[x][y+k] + Datum[x][y];
        int A5 = Datum[K][K] - Datum[K][y+k] - Datum[x+k][K] + Datum[x+k][y+k];
        int koho = A1 + A2 + A3 + A4 + A5;
        if(koho < n - koho) koho = n - koho;
        if(ans < koho) ans = koho;
        //printf("%d %d ~> %d\n", x, y, koho);
    }
    printf("%d\n", ans);
    
    

    


    return 0;
}


Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long int
#define pb push_back
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll a,b,k;
	scanf("%lld%lld%lld", &a,&b,&k);
	if(a >= k){
		a -= k;
	}else{
		k -= a;
		a = 0;
		b -= k;
		if(b < 0) b = 0;
	}
	printf("%lld %lld\n", a,b);
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>



int main() {
  long i, j, k, num = 0, ans = 0, N, M, A[1000] = { 0 };
  scanf("%ld %ld", &N, &M);
  for (i = 0; i < N; i++) {
    scanf("%ld", A + i);
    num += A[i];
  }
  for (i = 0; i < N; i++) {
    if (!(A[i] < (float)num / (4 * M))) ans++;
  }
  if (ans >= M) printf("Yes");
  else          printf("No");
  return 0;
}


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

int main(){
    long long n, m;
    cin >> n >> m;
    if(n>1 && m>1){
        cout << (n-2) * (m-2) << endl;
    }else if(n == 1 && m>2){
        cout << m-2 << endl;
    }else if(m == 1 && n>2){
        cout << n-2 << endl;
    }else{
        cout << 1 << endl;
    }
    return 0;
}

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

#define int long long 
#define ull unsigned long long int
#define M (int)(1e9+7)
#define for0(i, n) for (int i = 0; i < (int)(n); i++) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); i++) // 1 based indexing
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); i++) // closed interver from l to r r inclusive
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; i--) // reverse 0 based.
#define forr1(i, n) for (int i = (int)(n); i >= 1; i--) // reverse 1 based


#define pb push_back
#define fi first
#define se second


#define all(x) (x).begin(), (x).end() 
#define rall(x) (x).rbegin, (x).rend() 
#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define sz(a) int((a).size())


using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef double ld;

//-------------------------------------------------------------------------------END----------------------------------------------------------------------------------//
int mod(int x){
    return ((x%M + M)%M);
}

int add(int a,int b){
    return mod(mod(a)+mod(b));
}

int mins(int a,int b){
    return mod(mod(a)-mod(b));
}

int mul(int a,int b){
    return mod(mod(a)*mod(b));
}

int modpower(int x, unsigned int y)  {  
    if(y==0)return 1;
    if(y==1)return x%M;

    int res=1;
    while(y){
        if(y%2==1)res=mul(res,x);
        x = mul(x,x);
        y = y/2;
    } 
    return res;
}

int factorial(int n){ 
    return (n==1 || n==0) ? 1: n * factorial(n - 1);  
} 

bool inc(vi vec){
    for1(i,vec.size()-1){
        if(vec[i]<vec[i-1])return 0;
    }
    return 1;
}





void solve(){
    string s;cin>>s;

    cout<<s.substr(0,3);
}





int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.precision(10);
    //cout << fixed;
    //int tt;cin>>tt;
    //while(tt--){
        solve();
    //}
    return 0;
}



Measured memory_bytes: 3624
n = int(input())
b = list(map(int, input().split()))

ans = []
for _ in range(n):
    #print(b)
    check = 0
    for i in range(len(b)-1, -1, -1):
        if b[i] == i+1:
            del b[i]
            ans.append(i+1)
            check = 1
            break
    if check == 0:
        print(-1)
        exit()

for x in reversed(ans):
    print(x)

Measured memory_bytes: 38512
#include <bits/stdc++.h>
#include<vector>
using namespace std;
struct edge{
	int a;
  	int b;
};
int nnum,m,r,n;
vector<edge> es;
vector<bool> vertexrecords;
void search(int nowvertex,int chipped){
	for(int j=0;j<m;j++){ // jが今見てる辺
         if(nowvertex==es[j].a&&j!=chipped&&vertexrecords[es[j].b] == false&&es[j].a!=es[j].b){
         	vertexrecords[es[j].a] = true;
            nnum += 1; //埋めたから
           	search(es[j].b,chipped);
         }else if(nowvertex==es[j].b&&j!=chipped&&vertexrecords[es[j].a] == false&&es[j].a!=es[j].b){
         	vertexrecords[es[j].b] = true;
            nnum += 1;
           	search(es[j].a,chipped);
         }
    }
  	vertexrecords[nowvertex] = true;
  	return;
}
int main(void){
	int i,j,nowvertex,result=0;
  	cin >> n >> m;
  	es.resize(m);
  	vertexrecords.resize(n+1);
  	for(i=0;i<m;i++){
      	cin >> es[i].a >> es[i].b;
    }
  	for(i=0;i<m;i++){ //全ての辺を欠けさせてみる
      	nnum = 1; //全ての点が通り済みかの記録
        for(j=1;j<n+1;j++){
            vertexrecords[j] = false;
        }
      	search(1,i);
      	if(nnum < n){
        	result += 1;
        }
    }
  	cout << result;
  	return 0;
}

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

int main() {
  string s;
  cin >> s;
  rep(i,s.length()){
    cout << 'x';
  }
  cout << endl;
  return 0;
}


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

int main(int argc, char const *argv[]) {
  int n, flag = 0;
  cin  >> n;
  vector <int> a(n, 0);
  for(int i = 0;i < n;i++) {
    cin >> a.at(i);
    if(i != 0) {
      if(a.at(i-1) == a.at(i)) {
        a.at(i) += 100;
        flag++;
      }
    }
  }
  cout << flag << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        var sc = new Scanner();
        string s = sc.next();
        if (s == "Sunny") Console.WriteLine("Cloudy");
        else if (s == "Cloudy") Console.WriteLine("Rainy");
        else Console.WriteLine("Sunny");
    }
}

// chokudai's Scanner
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 9044
#include <stdio.h>
#define INF (1<<21)

int main(void)
{
 int i,j,n,m,u,k,l,v,c,a[101],b[101],d[101][101];

 scanf("%d",&n);
 
 for(i=0;i<n;i++){
 	a[i]=INF;
 	b[i]=0;
 	for(j=0;j<n;j++){
 		d[i][j]=INF;
 	}
 }
 a[0]=0;
 
 for(i=0;i<n;i++){
 	scanf("%d %d",&u,&k);
 	for(j=0;j<k;j++){
 		scanf("%d %d",&v,&c);
 		d[u][v]=c;
 	}
 }
 
 while(1){
 	
 	l=-1;
 	m=INF;
 	
 	for(i=0;i<n;i++){
 		if(a[i]<m && b[i]==0){
 			m=a[i];
 			l=i;
 		}
 	}
 	
 	if(l==-1) break;
 	
 	b[l]=1;
 	
 	for(i=0;i<n;i++){
 		if(a[i]>=d[l][i]+a[l]) a[i]=d[l][i]+a[l];
 	}
 }
 
 for(i=0;i<n;i++) printf("%d %d\n",i,a[i]);
 
 return 0;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    set<int> S;
    for (int i = 0; i < 3; ++i) {
        int x;
        cin >> x;
        S.insert(x);
    }
    if (S.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



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

d = {}
flag = True

for i in range(M):
    s, c = map(int, input().split())
    if s in d.keys() and d[s] != c:
        flag = False
    d[s] = c

if M == 0:
    if N > 1: d[1] = 1
    else: d[1] = 0
elif 1 not in d.keys():
    d[1] = 1
elif N > 1 and d[1] == 0:
    flag = False

if M != 0 and max(d.keys()) > N:
    flag = False

if flag:
    res = 0
    for s, c in d.items():
        res += c * 10 ** (N - s)
    print(res)
else:
    print("-1")

Measured memory_bytes: 62084
#include<bits/stdc++.h>
using namespace std;
int main(){
//	int a,b;
//	scanf("%d%d",&a,&b);
//	map<int,int>m;
//	m[a]=1;
//	m[b]=1;
//	for(int i=1;i<=3;i++)
//		if(m[i]==0){
//			printf("%d\n",i);
//			break;
//		}
//	int n;
//	cin>>n;
//	string s,t;
//	cin>>s>>t;
//	int f=0;
//	for(int i=0;i<n;){
//		if(f==0)
//			cout<<s[i],f=!f;
//		else{
//			f=!f;
//			cout<<t[i];
//			i++;
//		}
//	}
	
	long long a,b;
	cin>>a>>b;
	cout<<a*b/__gcd(a,b)<<"\n";
	return 0;
} 

Measured memory_bytes: 256
n = gets.chomp.to_i
# a = gets.chomp.split.map(&:to_i)

if n.odd?
  puts 0
  exit
end

def g1(n, p)
  return 0 if n == 0
  n/p + g1(n/p,p)
end

def g2(n, p)
  res = g1(n/2,p)
  res += n/2 if p == 2
  res
end

ans = g2(n,5)
puts ans


Measured memory_bytes: 1788
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>

//#define libingzhen
#define space putchar(' ')
#define enter putchar('\n') 
#define MAXN 

using namespace std;

typedef long long int64;

int read() {
	int f = 1,res = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') f *= -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		res = res*10+ch-'0';
		ch = getchar();
	}
	return res*f;
}

void out(int i) {
	if(i < 0) {
		putchar('-');
		i = -i;
	}
	if(i > 9) out(i/10);
	putchar(i%10+'0');
	return;
}

void Init() {
	return;
}

void Solve() {
	int n;
	double a,b;
	string s;
	cin>>n;
	for(int i = 0; i < n; i++) {
		cin>>a>>s;
		if(s == "JPY") {
			b += a;
		}
		else {
			b += a*380000;
		}
	}
	printf("%f\n",b);
}

int main() {
	
#ifdef libingzhen
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif	
	
	Solve();
	
	return 0;
}

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

int main() {
    long long  H, W, N;
    cin >> H >> W >> N;
    using P = pair<int, int>;
    map<P, int> ma;
    rep(i, 0, N) {
        int a, b;
        cin >> a >> b;
        rep(y, -1, 2) rep(x, -1, 2) {
            int ny = a + y, nx = b + x;
            if(ny <= 1 || ny >= H || nx <= 1 || nx >= W) continue;
            ma[P(ny, nx)]++;
        }
    }
    vector<long long> ans(10);
    for(auto p : ma) {
        int y = p.first.first;
        int x = p.first.second;
        ans[p.second]++;
    }
    ans[0] = (H - 2) * (W - 2);
    rep(i, 1, 10) ans[0] -= ans[i];
    rep(i, 0, 10) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 56448
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int N, A; cin >> N >> A;
    if(A == 1){
        cout << 0 << endl;
        return 0;
    }
    int count = N, res = 1;
    while(count < A){
        res++;
        count += N - 1;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
    #include <cmath>
    #include <vector>
    #include <cstdlib>
    #include <algorithm>
     
    #include <stdio.h>
    #include <stdlib.h>
     
    using namespace std;
     
    int main(int argc, char *argv[]){
     
      int N, Z, W;
      cin >> N >> Z >> W;
      int *a = new int [N];
      for(int i = 0; i < N; i++){
        cin >> a[i];
      }
     
      /*
       a[N-2] is X
       a[N-1] is Y
      */
      int pattern1 = abs(a[N-2] - a[N-1]);
      if(N == 1) pattern1 = 0;
     
      /*
       a[N-1] is X
      */
      int pattern2 = abs(a[N-1] - W);
      int ans = pattern1>pattern2?pattern1:pattern2;
      cout << ans << endl;
     
      return 0;
    }

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

int value(string sbit,int bit0,int bit1);
int main(){
  int n,t;
  cin >> n >> t;
  vector<int> a(n),am(n),ai(n);
  map<int,vector<int> > mva;
  vector<int > sbit0(n);
  int bitcnt=0;
  int alocal=1e9+1;
  ai[0]=0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if(alocal>a[i]){
      alocal=a[i];
      ai[i]=i;
      bitcnt=1;
    }else {
      ai[i]=ai[i-1];
      if(a[i]==alocal)bitcnt++;
    }
    am[i]=a[i]-alocal;
    mva[am[i]].push_back(i);
    sbit0[i]=bitcnt;
  }
  for(auto it= mva.rbegin();it!= mva.rend();it++){
    sort(it->second.begin(),it->second.end());
    int iprev = 0;
    int ans =0;
    for (int i = 0; i < it->second.size()-1; i++) {
      if((it->second[i]!=it->second[i+1])){
        //iprev からiまでの区間で考える
        //bit列の構成
        string sbit;
        int bit0=0,bit1=0;
        for (int j = iprev; j <=i ; j++) {
          for (int k = 0; k < sbit0[it->second[j]]-bit0; k++) {
            sbit+='0';
          }
          sbit+='1';
          bit0=sbit0[it->second[j]];
          bit1++;
        }
        ans += value(sbit,bit0,bit1);

        iprev=i+1;
      }

      if(it->second.size()==(i+2)){
        i++;
        //iprev からiまでの区間で考える
        //bit列の構成
        string sbit;
        int bit0=0,bit1=0;
        for (int j = iprev; j <=i ; j++) {
          for (int k = 0; k < sbit0[it->second[j]]-bit0; k++) {
            sbit+='0';
          }
          sbit+='1';
          bit0=sbit0[it->second[j]];
          bit1++;
        }
        ans += value(sbit,bit0,bit1);
        iprev=i+1;
      }
    }
    if(it->second.size()==1){
      ans=1;
    }
    cout <<ans<<endl;
    break;
  }
}

int value(string sbit,int bit0,int bit1){
  if(bit0==0 || bit1==0)return 0;
  int bits = bit0+bit1;
  int cur0 = 0;
  int cur1 = 0;
  int ans = min(bit0,bit1);
  for (int i = 1; i < bits; i++) {
    if(sbit[i-1]=='0')cur0++;
    else cur1++;
    ans = min(ans,cur0+bit1-cur1);
  }
  return ans;
}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
# ifdef DEB
# define debug(...) fprintf(stderr, __VA_ARGS__)
# else
# define debug(...)
#endif
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define LL long long
#define LD long double
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define pb pop_back
#define VI vector<int> 
#define VPI vector<PII> 
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define FORD(i,a,b) for(int i = (a); i >= (b); i--)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define ALL(x) (x).begin(), (x).end()
#define siz(V) ((int)V.size())
const LL mod = 1e9 + 7;
const int M = 3002;

LL res;
int n, m;
int dp[2 * M][2 * M];
int P[3][2 * M];

void count(int k)
{
  dp[0][0] = 1;
  for (int i = 1; i <= 2 * m; i++)
  {
    for (int j = 0; j <= 2 * n; j++)
    {
      dp[i][j] = 0;
      if (j + k < 2 * n)
      {
        dp[i][j] = dp[i - 1][j + 1];
      }
      if (j > 0)
      {
        dp[i][j] += dp[i - 1][j - 1];
      }
      if (dp[i][j] >= mod)
      {
        dp[i][j] -= mod;
      }
      if (j + k <= 2 * n)
      {
        P[k][i] += dp[i][j];
        if (P[k][i] >= mod)
        {
          P[k][i] -= mod;
        }
      }
    }
  }
}

int main()
{
  //ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < 3; i++)
  {
    P[i][0] = 1;
  }
  
  count(0);
  for (int i = 0; i <= 2 * n; i++)
  {
    res += dp[2 * m][i];
    if (res >= mod)
    {
      res -= mod;
    }
  }
  
  count(1);
  for (int i = 1; i <= 2 * n; i++)
  {
    for (int j = 1; j <= 2 * m; j++)
    {
      LL x = 0;
      /*if (i % 2 == 1)
      {
        x = (LL)dp[j - 1][i - 1] * P[1][2 * m - j];
      }*/
      if (i % 2 == 0)
      {
        x = (LL)dp[j - 1][i - 1] * P[0][2 * m - j];
      }
     //debug("%d %d: %lld\n", i, j, x);
      res = (res + x) % mod;
    }
  }
  
  count(2);
  for (int i = 1; i <= 2 * n; i++)
  {
    for (int j = 1; j <= 2 * m; j++)
    {
      LL x = 0;
      if (i % 2 == 1)
      {
        x = (LL)dp[j - 1][i - 1] * P[1][2 * m - j];
      }
      /*if (i % 2 == 0)
      {
        x = (LL)dp[j - 1][i - 1] * P[0][2 * m - j];
      }*/
     //debug("%d %d: %lld\n", i, j, x);
      res = (res + x) % mod;
    }
  }
  printf("%lld\n", res);
  return 0;
}

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

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  int answer = 0;
  for (int i = 0; i < N; i++) {
    int H;
    cin >> H;
    if (H >= K) answer++;
  }
  cout << answer;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int N, ans = 0, ptr;
	scanf("%d", &N);
	char S[N];
	for (int i = 0; i < N; ++i) scanf(" %c", &S[i]);
	for (char i = '0'; i <= '9'; ++i) {
		for (char j = '0'; j <= '9'; ++j) {
			for (char k = '0'; k <= '9'; ++k) {
				for (ptr = 0; ptr < N && S[ptr] != i; ++ptr);
				for (++ptr; ptr < N && S[ptr] != j; ++ptr);
				for (++ptr; ptr < N && S[ptr] != k; ++ptr);
				if (ptr < N) ++ans;
			}
		}
	}
	printf("%d", ans);
	return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back #define eb emplace_back

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

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

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

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;


int main(){
	ios_base::sync_with_stdio(false);
	ll N, ans=0;

	cin >> N;

	if(N == 2){
		cout << 1 << endl;
		return 0;
	}

	ans += 2;
	for(ll i=2; i <= sqrt(N); i++){
		ll cur = N;
		while(cur % i == 0) cur = cur / i;
		if(cur % i == 1){
			// cout << i << endl;
			ans++;
		}
		if((N - 1) % i == 0 && (N - 1) / i > sqrt(N)){
			// cout << (N - 1) / i << endl;
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

int ans=0;
vector<int> to[100005];
bool visited[100005];
int temp=-1;
bool ok=1;
int h[100005];

void dfs(int u){

    for(int v:to[u]){
        if(h[v]>=h[u]){
            ok=0;
        }
    }
    return;
}

int main(){
    int n,m;
    cin >> n>> m;
    rep(i,n){
        cin >> h[i];
    }
    rep(i,m){
        int a,b;
        cin >> a>> b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    rep(i,n){
        
        
        ok=1;
        dfs(i);
        if(ok){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 12236
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PP pair<P,P>



struct UnionFind
{

  vector<int> par;
  vector<int> sizes;

  UnionFind(int n) : par(n), sizes(n, 1) {
    rep(i,n) par[i] = i;
  }

  int root(int x) {
    if (x == par[x]) return x;
    return par[x] = root(par[x]); 
  }

  bool unite(int x, int y) {

    x = root(x);
    y = root(y);

    if (x == y) return false;

    if (sizes[x] < sizes[y]) swap(x, y);

    par[y] = x;
    sizes[x] += sizes[y];

    return true;
  }

  bool find(int x,int y){
    return root(x)==root(y);
  }

  int size(int x) {
    return sizes[root(x)];
  }
};

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

  int n,m;
  cin>>n>>m;
  vi a(n);
  rep(i,n){
    cin>>a[i];
  }
  UnionFind uf(n);
  rep(i,m){
    int x,y;
    cin>>x>>y;
    uf.unite(x,y);
  }

  if(n==m+1){
    cout<<0<<endl;
    return 0;
  }


  map<int,int> mp;
  rep(i,n){
    int x=uf.root(i);
    if(mp.find(x)==mp.end()){
      mp[x]=i;
    }else if(a[mp[x]]>a[i]){
      mp[x]=i;
    }
  }

  int ans=0;
  for(P m:mp){
    //cout<<"   "<<m.S<<' '<<a[m.S]<<endl;
    ans+=a[m.S];
  }

  priority_queue<int,vi,greater<int>> q;
  rep(i,n){
    //cout<<i<<' '<<mp[i]<<endl;
    if(mp[uf.root(i)]!=i){
      //cout<<i<<endl;
      q.push(a[i]);
    }
  }

 

  rep(i,n-m-2){
    //cout<<q.top()<<endl;
    if(q.empty()){
      cout<<"Impossible"<<endl;
      return 0;
    }
    ans+=q.top();
    q.pop();
  }

  cout<<ans<<endl;



}

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

A = list(map(int, input().split()))
sumvote = sum(A)

count = 0
for i in range(N):
  if (A[i] * 4 * M >= 1 * sumvote):
    count += 1

if (count >= M):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<queue>
#include<utility>
#include<cstdio>
#include<cstring>
#include<new>
#include<float.h>
#include<ctype.h>
#include<cfloat>
#include<cmath>
#include<cctype>
#include<errno.h>
#include<cerrno>
#include<memory>
#include<memory.h>
#include<assert.h>
#include<cassert>
#include<deque>
#include<sstream>
#define fo(i,w,n) for(int i=(int) w;i<(int) n;i++)
#define qui queue<int>
#define vit vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define prq priority_queue
#define pii pair<int,int>
#define mp make_pair
#define sz size()
#define em empty()
#define ct continue
#define ms multiset
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define ppf pop_front()
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	fo(i,0,max(a.sz,b.sz)){
		if(i<a.sz)cout<<a[i];
		if(i<b.sz)cout<<b[i];
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>

typedef unsigned long long LL;

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int>A;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		A.push_back(tmp);
	}
	int n = 1;
	int noteven = 1;
	for (int i = 0; i < N; i++) {
		n *= 3;
		if (A[i] % 2 == 1) {
			noteven *= 1;
		}
		else {
			noteven *= 2;
		}
	}
	cout << n - noteven << endl;

}

Measured memory_bytes: 256
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int x;
  cin >> x;
  vector<int> dp(x+1);
  dp[0] = 1;
  for(int i = 0; i <= 5; i++) {
    for(int j = 0; j+100+i <= x; j++) {
      dp[j+100+i] |= dp[j];
    }
  }
  cout << dp[x] << endl;
  return 0;
}


Measured memory_bytes: 640
N = int(input())
S = input()
X = list(int(x) for x in S)


def popcount(x):
    return bin(x).count("1")


def f(x):
    if x == 0:
        return 0
    return f(x % popcount(x)) + 1


MAX = 2 * 10 ** 5 + 5
# print(X)

pc = sum(X)  # もとのpopcount

ans = [0] * (N + 1)
for b in range(2):
    npc = pc  # 今のpopcount
    if b == 0:
        npc += 1
    else:
        npc -= 1
    if npc <= 0:
        continue
    # もとの割った余りを求めていく
    r0 = 0
    for i in range(N):
        r0 = (r0 * 2) % npc
        r0 += X[i]
    k = 1
    for i in reversed(range(N)):
        if X[i] == b:  # i桁目がbのものだけ処理する。
            r = r0  # 今の桁を変えたときに割った余りがどう変化するか
            if b == 0:
                r = (r + k) % npc
            else:
                r = (r - k + npc) % npc
            # i桁目をフリップしたときの値がここまでで求まった。
            ans[i] = f(r) + 1
        k = (k * 2) % npc

for i in range(N):
    print(ans[i])


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  char a;
  cin >> a;
  
  if (a >= 'A' && a <= 'Z') cout << 'A' << '\n';
  else cout << 'a' << '\n';
}

Measured memory_bytes: 3648
###
### atcorder test program
###

import sys

### math class
class math:
    ### pi
    pi = 3.14159265358979323846264338

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

math = math()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#A, B, C = [x for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    a, b = map(int, line.split())

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

for line in sys.stdin.readlines():
    x, y = [int(temp) for temp in line.split()]
    print("{} {}".format(math.gcd(x,y), math.lcm(x,y)))
    


Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() 
{
  ll n,i;
  cin>>n;
  ll a[n+1],b[n];
  for(i=0;i<n+1;i++)
  cin>>a[i];
    for(i=0;i<n;i++)
  cin>>b[i];
  ll s=0;
  for(i=0;i<n;i++)
  {
    if((a[i]+a[i+1])>b[i])
    {
      s+=b[i];
      if(a[i]<b[i])
        a[i+1]-=(-a[i]+b[i]);
    }
    else
    {
      s+=a[i]+a[i+1];
      a[i+1]=0;
    }
  }
  cout<<s;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long 
#define ull unsigned long long
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define repr(i,n) for (int i = n; i >= 0; --i)
#define P pair<int, int>
#define ALL(x) (x).begin(),(x).end()
const int INF = 1e9;
using namespace std;

int main() {
	vector<P>v;
	int n;
	cin >> n;
	rep(i,n) {
		int x,y;
		cin >> x >> y;
		v.push_back(P(x,y));
	}
	sort(ALL(v));
	rep(i,v.size()) cout << v[i].first << ' ' << v[i].second << endl;
}


Measured memory_bytes: 3888
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main() {
  int N;
  cin>>N;
  
  Graph G(N);
  for(int i=1; i<N; ++i){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  vector<int> dist(N,-1);
  queue<int> Q;
  dist[0]=0;
  Q.push(0);
  
  while(!Q.empty()){
    int v=Q.front();//キューから先頭頂点を取り出す
    Q.pop();
    for(int nv:G[v]){
      if(dist[nv]!=-1) continue;
      dist[nv]=dist[v]+1;
      Q.push(nv);
    }
  }
  
  int T=0;
  REP(i,N){
    if(dist[T]<dist[i]) T=i;
  }
  
  vector<int> ddist(N,-1);
  queue<int> QQ;
  ddist[T]=0;
  QQ.push(T);
  
  while(!QQ.empty()){
    int v=QQ.front();//キューから先頭頂点を取り出す
    QQ.pop();
    for(int nv:G[v]){
      if(ddist[nv]!=-1) continue;
      ddist[nv]=ddist[v]+1;
      QQ.push(nv);
    }
  }
  
  int TT=T;
  REP(i,N){
    if(ddist[TT]<ddist[i]) TT=i;
  }
  
  if(ddist[TT]%3==1) co("Second");
  else co("First");
  return 0;
}

Measured memory_bytes: 14324
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [0] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)
mxd = max(depth)
i = depth.index(mxd)
depth = [0] * N
dfs(i)

diameter = max(depth)
print('Second' if diameter%3==1 else 'First')

Measured memory_bytes: 293828
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int main()
{int N,K; cin >> N >> K;
 
 vector<int> A(N); 
 for(int i = 0; i < N; i++)
 {cin >> A[i];}
 vector<int> KINDS(N,0);
 
 for(int i = 0; i < N; i++)
 {KINDS[A[i]-1]++;}
 //0-indexed化
 sort(KINDS.begin(),KINDS.end());
 int cnt = 0;
 int j = 0;
 for(int i = 0; i < N; i++)
 {if(KINDS[i] != 0){cnt++;}}
 //何種類の数が入っているかを数える
 if(cnt <= K ){cout << 0 <<endl;}
 //これがKより少なければ、直す必要はない
 else{ int sum = 0;//cnt - K種類塗り替える必要がある
      //まず最初に0でなくなるKINDSの位置を探す
      for(int i = 0; i < N;i++)
      {if(KINDS[i] != 0)
       { j = i;
         break;}}
    
       for(int i = j; i < cnt - K + j  ; i++)
         //jから初めて、cnt-K種類塗り替える
       { sum += KINDS[i];}
      cout << sum << endl;
     }
 return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)

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

    string str;
    cin >> str;
    int n;
    cin >> n;
    REP(i, n) {
        string order;
        cin >> order;
        if (order == "print") {
            int a, b;
            cin >> a >> b;
            cout <<  str.substr(a, b - a + 1) << '\n';
        }
        if (order == "reverse") {
            int a, b;
            cin >> a >> b;
            reverse(str.begin() + a, str.begin() + b + 1);
        }
        if (order == "replace") {
            int a, b;
            cin >> a >> b;
            string tmp;
            cin >> tmp;
            str.replace(a, b - a + 1, tmp);
        }
    }
    return 0;
}


Measured memory_bytes: 3168
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

string solve() {
    i64 sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    string ans;
    i64 dx = tx - sx, dy = ty - sy;
    ans += string(dx, 'R');
    ans += string(dy, 'U');
    ans += string(dx, 'L');
    ans += string(dy, 'D');
    ans += 'D';
    ans += string(dx + 1, 'R');
    ans += string(dy + 1, 'U');
    ans += 'L';
    ans += 'U';
    ans += string(dx + 1, 'L');
    ans += string(dy + 1, 'D');
    ans += 'R';
    return ans;
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int input (int x[],int y[]);
int swap  (int x[],int y[]);
int output(int x[],int y[]);

int main(void)
{
	int x[3000] = { 0 };
	int y[3000] = { 0 };

	input(x,y);
	swap(x, y);
	output(x,y);

	return 0;
}
int input(int x[], int y[])
{
	for(int loop = 0; loop<3000;loop++)
	{
		scanf("%d%d", &x[loop], &y[loop]);
		if (0 == x[loop] && 0 == y[loop])
			break;
	}
	return 0;
}
int swap(int x[],int y[])
{
	int iTemp = 0;

	for (int loop = 0; loop<3000; loop++)
	{
		if (*(x + loop) > *(y + loop))
		{
			iTemp = *(x + loop);
			*(x + loop) = *(y + loop);
			*(y + loop) = iTemp;
		}
		if (0 == x[loop] && 0 == y[loop])
		{
			break;
		}
	}
	return 0;
}
int output(int x[],int y[])
{
	for (int loop = 0; loop<3000; loop++)
	{
		if (0 == x[loop] && 0 == y[loop])
			break;
		printf("%d %d\n", x[loop], y[loop]);
	}
	return 0;
}


Measured memory_bytes: 2028
import itertools as it
N=int(input())
d=0
for i in range(3,10):
    for c in sorted(list(it.product('753',repeat=i))):
        if int(''.join(c))>N:
            print(d)
            exit(0)
        if len(set(c))==3:d+=1
print(d)

Measured memory_bytes: 6388
import java.util.*;
import java.awt.geom.*;

import static java.lang.Math.*;
public class Main {
	final Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main().init();
	}
	void init(){
		new AOJ1174();
	}
	class AOJ1174{
		AOJ1174(){
			while(sc.hasNext()){
				H=sc.nextInt(); W=sc.nextInt(); C=sc.nextInt();
				if((H|(W|C))==0)	break;
				solve();
			}
		}
		int H,W,C;
		int[][][] b;
		final int[] vx={0,-1,0,1},vy={-1,0,1,0};
		void solve(){
			b=new int[6][W][H];
			for(int h=0; h<H; ++h)for(int w=0; w<W; ++w)	b[0][w][h]=sc.nextInt();
			System.out.println(backtracking(b,0,b[0][0][0]));
		}
		int backtracking(int[][][] b,int depth,int last){
			if(depth>=4)	return cnt(chg(depth, C));
			int ret=0;
			for(int c=1; c<=6; ++c){
				if(c==last)	continue;
				chg(depth, c);
				ret=max(ret, backtracking(b, depth+1, c));
			}
			return ret;
		}
		int[][] chg(int d,int target){
			for(int w=0; w<W; ++w)for(int h=0; h<H; ++h)	b[d+1][w][h]=b[d][w][h];
			b[d+1][0][0]=target;
			chg(d,0,0,target);
			return b[d+1];
		}
		void chg(int d,int x,int y,int target){
			for(int v=0; v<4; ++v){
				int nx=x+vx[v],ny=y+vy[v];
				if(!(0<=nx&&nx<W && 0<=ny&&ny<H))	continue;
				if(b[d][nx][ny]!=b[d][0][0])	continue;
				if(b[d+1][nx][ny]==target)	continue;
				b[d+1][nx][ny]=target;
				chg(d,nx,ny,target);
			}
		}
		int cnt(int[][] a){
			return cnt(a,0,0,a[0][0]);
		}
		int cnt(int[][] a,int x,int y,int c){
			int ret=1;
			a[x][y]=-1;
			for(int v=0; v<4; ++v){
				int nx=x+vx[v],ny=y+vy[v];
				if(!(0<=nx&&nx<W && 0<=ny&&ny<H))	continue;
				if(a[nx][ny]!=c)	continue;
				ret+=cnt(a, nx, ny, c);
			}
			return ret;
		}
	}
}

Measured memory_bytes: 38148
@digits = ["0","1","2","3","4","5","6","7","8","9"]

def make_array str
    mode, arr, s = 0, [], ""
    str.each_char{|c|
        if @digits.include?(c)
            if mode == 0
                mode = 1
                arr << s
                s = ""
            end
        else
            if mode == 1
                mode = 0
                arr << s.to_i
                s = ""
            end
        end
        s += c
    }
    case mode
    when 0 then arr << s
    when 1 then arr << s.to_i
    end
    return arr
end

n = gets.to_i
s0 = gets.chomp
arr0 = make_array(s0)

n.times{
    i, result, arr1 = 0, "+", make_array(gets.chomp)
    if arr0 != arr1
        while true
            if arr0[i].nil? || arr1[i].nil?
                result = "-" if arr1[i].nil?
                break
            elsif arr0[i].class != arr1[i].class
                result = "-" if arr0[i].class == String
                break
            elsif arr0[i] != arr1[i]
                result = "-" if arr0[i] > arr1[i]
                break
            end
            i += 1
        end
    end
    puts result
}




Measured memory_bytes: 8912
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <list>
using namespace std;

int main(){

    int a, b; cin >> a >> b;

    if(a == b){
        cout << 2*a << endl;
    }
    else if(a > b){
        cout << 2*a-1 << endl;
    }
    else{
        cout << 2*b-1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
//B.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
  int N;
  cin >> N;
  int X;
  int cnt = 0;

  for(int i = 3; i <= N; i += 2){
    int num[220] = {0};
    int ans = 1;
    int x = i;
    bool flag = true;
    while(flag){
      flag = false;
      X = x;
      for(int j = 3; j < N; j++){
        if(x%j==0){
          ++num[j];
          x /= j;
          break;
        }
      }
      if(X!=x) flag = true;
    }
    for(int j = 3; j <= N; j++){
      ans *= num[j]+1;
    }
    if(ans == 8) ++cnt;
  }

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


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

int main () {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++){
    char  col;
    cin >> col;
    if (col == 'Y') {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
}

Measured memory_bytes: 3616
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
	int N; cin >> N;
	vector<LLONG> as(N); REP(i, N) cin >> as[i];
	sort(as.begin(), as.end());
	LLONG sum = 0;
	int ans = N;
	REP(i, N - 1)
	{
		sum += as[i];
		if (sum * 2 < as[i + 1])
		{
			ans = N - (i + 1);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3996
// Copyright 2020 yaito3014
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (auto& e : A)cin >> e;
  sort(rbegin(A), rend(A));
  bool ans = A[M - 1] >= accumulate(begin(A), end(A), 0) / 4. / M;
  cout << (ans ? "Yes" : "No") << endl;
}

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

using namespace std;

#define INF 1001001001  //int32_t
#define MOD 1000000007
#define MOD2 

#define all(a)  (a).begin(),(a).end()

#define mkp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

    int n;
    vector<pii> tpos;
    double dist[8][8];

long double solve(vector<bool> v,int nv,long double td){
    long double ret = 0;

    int visted = 0;
    for (int i = 0; i < v.size(); i++){
        if(i == nv)continue;
        if(v[i] == true){
            ++visted;
            continue;
        }

        v[i] = true;
        ret += dist[i][nv] + solve(v,i,td);
    }
    
    if(visted == v.size()-1){
        return 0;
    }

    return ret;
}

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    cin >>n;
    tpos.resize(n);

    for (int i = 0; i < n; i++){
        int x,y;
        cin >>x>>y;
        tpos[i] = make_pair(x,y);
    }
    
    long double td = 0;
    long double nfact = 1,nfact2=1;

    for (int i = 1; i <= n-2; i++)nfact2 *= i;
    for (int i = 1; i <= n; i++)nfact *= i;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(i==j)continue;

            double x = abs(tpos[i].first - tpos[j].first);
            double y = abs(tpos[i].second - tpos[j].second);

            double sqd = x*x + y*y;

            dist[i][j] = sqrt(sqd);
            dist[j][i] = sqrt(sqd);


            td += sqrt(sqd)*nfact2;
        }
    }

    /*

    for (int i = 0; i < n; i++){
        vector<bool> v(n,false);
        v[i]=true;
        td += solve(v,i,0);
    }
    */

    cout <<fixed<<setprecision(16)<< (n-1)*td/nfact << endl;
    //cout << td/nfact << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>



/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

const int MAX_N = 100000;
int N, K;
vector<int> table[MAX_N];

int fact[100001];
int revfact[100001];
int ans[MAX_N];

int powmod(int a, int p, int mod) {
    int ans = 1;
    int mul = a;

    for (; p > 0; p >>= 1, mul = (mul * mul) % mod) {
        if ((p & 1) == 1) ans = (ans * mul) % mod;
    }

    return ans;
}

void dfs(int node, int par) {
    int can_use = (par == -1) ? K-1 : K-2;
    int child_num = (par == -1) ? (int) table[node].size() : (int) table[node].size() - 1;

    if (can_use < child_num) {
        ans[node] = 0;
        return;
    }

    ans[node] = fact[can_use] * revfact[can_use - child_num];
    ans[node] %= MOD;

    for (int next : table[node]) {
        if (next == par) continue;
        dfs(next, node);
    }
}

signed main() {
    fact[0] = 1;
    for (int i = 1; i <= 100000; i++) {
        fact[i] = fact[i-1] * i;
        fact[i] %= MOD;
    }

    revfact[100000] = powmod(fact[100000], MOD - 2, MOD);
    for (int i = 100000 - 1; i >= 0; i--) {
        revfact[i] = revfact[i+1] * (i+1);
        revfact[i] %= MOD;
    }

    cin >> N >> K;
    for (int i = 0; i < N - 1; i++) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        table[s].push_back(t);
        table[t].push_back(s);
    }

    dfs(0, -1);

    int ret = K;
    for (int i = 0; i < N; i++) {
        ret *= ans[i];
        ret %= MOD;
    }
    cout << ret << endl;
}

Measured memory_bytes: 11520
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n; cin>>n;
	int ind[100010];
	for(int i=1; i<=n; i++){
		int a; cin>>a;
		ind[a]=i;
	}
	for(int i=1; i<=n; i++){
		cout<<ind[i]<<" ";
	}
	cout<<endl;
	return 0;
}

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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    int n; ll x; cin >> n >> x;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    ll ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ll s = a[i] + a[i + 1];
        if (s > x) {
            ans += s - x;
            if (a[i + 1] >= s - x) a[i + 1] -= s - x;
            else a[i + 1] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
// 检测圆是否在矩形内
int main()
{
    int w, h, x, y, r;
    scanf("%d%d%d%d%d", &w, &h, &x, &y, &r);
    if (x - r < 0 || x + r > w || y - r < 0 || y + r > h)
        printf("No\n");
    else
        printf("Yes\n");

    return 0;
}


Measured memory_bytes: 2692
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
 
int main(){
  ll a,b,c,d,r;
  ll k[4];
  cin >> a >> b >> c >> d;
  r = a*c;
  k[0]=a*c;
  k[1]=a*d;
  k[2]=b*c;
  k[3]=b*d;
  for(int i = 0; i<4; i++){
    if (r<k[i]) r = k[i];
  }
    
  cout << r <<endl;
}
  

Measured memory_bytes: 3608