akhauriyash/Code-Regression huggingface dataset:
//Zory-2019
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define pr pair<ll,ll>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    #define bin(x) (1ll<<(x))
    #define GG(x) if(x) {puts("error");exit(666);}
    #define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
    #define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;GG(e<0)while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e6+10;

    vc<int> to[2][N];int dep[N],fs[N][30];
    void pre1(int x,int fa)
    {
        dep[x]=dep[fa]+1;fs[x][0]=fa;fo(i,1,20) fs[x][i]=fs[fs[x][i-1]][i-1];
        for(auto y:to[1][x]) if(y!=fa) pre1(y,x);
    }
    int getlca(int x,int y)
    {
        if(dep[x]<dep[y]) swap(x,y);
        fd(t,20,0) if(bin(t)<=dep[x]-dep[y]) x=fs[x][t];if(x==y) return x;
        fd(t,20,0) if(fs[x][t]!=fs[y][t]) x=fs[x][t],y=fs[y][t];return fs[x][0];
    }
    int getdis(int x,int y){return dep[x]+dep[y]-2*dep[getlca(x,y)];}
    int ans=0;
    void solve(int x,int fa,int dis)
    {
        if(dis>=dep[x]) return;chmax(ans,dep[x]*2);
        for(auto y:to[0][x]) if(y!=fa)
        {
            if(getdis(x,y)>2) {puts("-1");exit(0);}
            solve(y,x,dis+1);
        }
    }
	void main()
	{
        int n=qread(),X=qread(),Y=qread();
        fo(i,1,n-1){int x=qread(),y=qread();to[0][x].PB(y);to[0][y].PB(x);}
        fo(i,1,n-1){int x=qread(),y=qread();to[1][x].PB(y);to[1][y].PB(x);}
        dep[0]=-1;pre1(Y,0);solve(X,0,0);write(ans);
	}
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 95100
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for _ in range(N)]

maxpoint=0
var=[(1,1,1),(1,1,-1),(1,-1,1),(-1,1,1),(1,-1,-1),(-1,1,-1),(-1,-1,1),(-1,-1,-1)]
for (dx,dy,dz) in var:
    sumXYZ=[dx*x+dy*y+dz*z for x,y,z in XYZ]
    maxpoint=max(maxpoint,sum(sorted(sumXYZ,reverse=True)[:M]))
print(maxpoint)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
   char s[3];
   cin>>s;
   if(s[0]=='R' && s[1]=='R' && s[2]=='R'){
       cout<<3;
   }
   if(s[0]=='R' && s[1]=='R' && s[2]=='S'){
      cout<<2;
   }
   if(s[0]=='S' && s[1]=='R' && s[2]=='R'){
      cout<<2;
   }
   if(s[0]=='S' && s[1]=='S' && s[2]=='S'){
      cout<<0;
   }
   if(s[0]=='R' && s[1]=='S' && s[2]=='R'){
      cout<<1;
   }
  if(s[0]=='S' && s[1]=='S' && s[2]=='R'){
      cout<<1;
   }
  if(s[0]=='R' && s[1]=='S' && s[2]=='S'){
      cout<<1;
   }
   if(s[0]=='S' && s[1]=='R' && s[2]=='S'){
      cout<<1;
   }
  
  
  
  
   
   
    
  return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    double r;
    cin >> r;
    double p = 3.14159265358979323846;
    printf("%.10f\n", r*2*p);
    return 0;
}


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

bool is_prime(int n){
  if(n<=1)
    return false;

  for(int i=2; i*i<=n; i++){
    if(n%i==0){
      return false;
    }
  }

  return true;
}


int main(){
  while(true){
    int next=0;
    int prev=0;

    int n;
    cin >> n;

    if(cin.eof())
      break;

    for(int i=n+1; i<=50100; i++){
      if(is_prime(i)){
        next=i;
        break;
      }
    }
    for(int i=n-1; i>=2; i--){
      if(is_prime(i)){
        prev=i;
        break;
      }
    }

    cout << prev << ' ' << next <<endl;
  }

  return 0;
}



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

#ifdef LOCAL
	#define de(x) cout<<#x<<"="<<x<<endl
	#define rff freopen("input.txt","r",stdin)
#else
	#define de(x)
	#define rff
#endif

#define itr(x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define For(i,n) for (int i=1;i<=(int)(n);i++)
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(x) (x).begin(),(x).end()
#define PQ priority_queue
#define pii pair<int,int>
#define vi vector <int>
#define ll long long
#define pb push_back
#define mp make_pair
#define re return
#define se second
#define fi first
const int INF=0x7fffffff;
const int MAXN=+3;

ll n,m,l;
string a,b,x;

ll gcd(ll a,ll b){
	if (b){
		while ((a%=b) && (b%=a));
	}
	re a+b;
}

ll lcm(ll a,ll b){
	re a*b/gcd(a,b);
}

int main(){
	cin>>n>>m>>a>>b;
	l=lcm(n,m);
	ll t=lcm(l/n,l/m);
	for(ll i=0;i<l;i+=t){
		if (a[i/(l/n)]!=b[i/(l/m)]){
			cout<<-1;
			re 0;
		}
	}
	cout<<l;
	re 0;
}

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

using namespace std;
using ll = long long;

int main() {
    int N = 0;
    cin >> N;
    if (N == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    
    for (size_t i = 0; i < N/10*9; i++)
    {
        if((N - i)*108/100 == N){
            cout << N - i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
    

    return 0;
}

Measured memory_bytes: 3612
// 2011/01/23 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int n;
		cin >> n;
		if(n==0)
			break;

		int S[12];
		for(int i=0; i<n; i++)
			cin >> S[i];

		int cnt = 0;
		int P[12];
		while(true){
			for(int i=0; i<n; i++)
				P[i] = 0;

			for(int i=0; i<n; i++)
				for(int j=0; j<n; j++)
					if(S[i]==S[j])
						P[i]++;

			bool flg = true;
			for(int i=0; i<n; i++)
				if(S[i]!=P[i]){
					flg = false;
					break;
				}

			if(flg)
				break;
			else
				cnt++;

			for(int i=0; i<n; i++)
				S[i] = P[i];
		}

		cout << cnt << endl;
		for(int i=0; i<n; i++){
			cout << P[i];
			if(i!=n-1)
				cout << ' ';
			else
				cout << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <stdlib.h>
int main(){
  int i,j,n,B,x,*A;
 
  scanf("%d",&n);
 
  A=malloc(sizeof(int)*(n+1));
 
  for(i=1;i<n+1;i++)
    scanf("%d",&A[i]);
  


  i=0;
  for(j=1;j<n;j++)
    if(A[j]<=A[n]){
      i++;
      B=A[i];
      A[i]=A[j];
      A[j]=B;
    }
  

  B=A[i+1];
  A[i+1]=A[n];
  A[n]=B;
  x=i+1;
 
  for(i=1;i<x;i++)
    printf("%d ",A[i]);
  printf("[");
  printf("%d]",A[x]);

  for(i=x+1;i<n+1;i++)
    printf(" %d",A[i]);
  printf("\n");
 
  
  return 0;
}

Measured memory_bytes: 996
#include <iostream>

using namespace std;

int main(void) {
    int a, b;
    
    cin >> a >> b;
    
    if(a == b) {
        cout << "a == b\n";
    } else if(a > b) {
        cout << "a > b\n";
    } else {
        cout << "a < b\n";
    }
    
    return 0;
}

Measured memory_bytes: 1124
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    int W, H, N;
    cin >> W >> H >> N;

    vector<vector<int>> map(W, vector<int>(H, 0));

    int x, y, a;
    int k = 0;
    while (k < N)
    {
        cin >> x >> y >> a;
        if (a == 1)
        {
            for (int i = 0; i < x; i++)
            {
                for (int j = 0; j < H; j++)
                {
                    map[i][j] = 1;
                }
            }
        }
        else if (a == 2)
        {
            for (int i = x; i < W; i++)
            {
                for (int j = 0; j < H; j++)
                {
                    map[i][j] = 1;
                }
            }
        }
        else if (a == 3)
        {
            for (int i = 0; i < W; i++)
            {
                for (int j = 0; j < y; j++)
                {
                    map[i][j] = 1;
                }
            }
        }
        else
        {
            for (int i = 0; i < W; i++)
            {
                for (int j = y; j < H; j++)
                {
                    map[i][j] = 1;
                }
            }
        }
        k++;
    }

    int ans = 0;
    for (int i = 0; i < W; i++)
    {
        for (int j = 0; j < H; j++)
        {
            if (map[i][j] == 0)
            {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

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

#define MOD 1000000007LL

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

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

    string s;
    cin>>s;
    reverse(s.begin(),s.end());
    vector<vector<ll>> dp(2,vector<ll>(13));
    if(s[0]=='?'){
        for(int i=0; i<10; i++){
            dp[0][i]=1;
        }
    }
    else dp[0][s[0]-'0']=1;
    int idx=0;

    for(int i=1,tmp=10; i<s.length(); i++,tmp=(tmp*10)%13){
        idx=1-idx;
        for(int j=0; j<13; j++) dp[idx][j]=0;
        if(s[i]=='?'){
            for(int j=0; j<10; j++){
                for(int k=0; k<13; k++){
                    dp[idx][(j*tmp+k)%13]=(dp[idx][(j*tmp+k)%13]+dp[1-idx][k])%MOD;
                }
            }
        }
        else{
            for(int j=0; j<13; j++){
                dp[idx][(j+(s[i]-'0')*tmp)%13]=dp[1-idx][j];
            }
        }
    }
    cout<<dp[idx][5];

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MM_PI		3.14159265358979323846

typedef vector<lint> vl;
typedef pair<lint,lint> pll;

#define mpr make_pair

int main()
{
    ios_base::sync_with_stdio(0);    cin.tie(NULL);    cout.tie(NULL);

    int n, m; cin>>n>>m;
    vector<vi> mp(n+1);

    for (int i=0; i<m; ++i){
        int u, v;
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }

    vi len(n+1, INT_MAX);
    queue<int> bfs;
    auto push = [&](int id, int l){
        if (len[id]>l){
            bfs.push(id);
            len[id] = l;
        }
    };

    push(1, 0);
    while(!bfs.empty()){
        int node = bfs.front(); bfs.pop();
        int l = len[node];
        for (int son : mp[node]){
            push(son, l+1);
        }
    }

    cout<<"Yes\n";
    for (int i=2; i<=n; ++i){
        int l = len[i];
        for (int nb : mp[i]){
            if (len[nb] == l-1){
                cout<<nb<<"\n";
                break;
            }
        }
    }
}


Measured memory_bytes: 10248
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n;
    string s,t,u;
    cin>>n>>s>>t;
    rep(i,n){
        u.push_back(s[i]);
        u.push_back(t[i]);
    }
    cout<<u<<endl;
    return 0;
}

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

int main() {
	long long a, b, c;
	cin >> a >> b >> c;

	long long d = c - a - b;

	if (d > 0 && d * d > 4 * a * b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
};


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i=0;i<(int)(n);++i)
template <typename T> ll gcd(T a, T b) {return b?gcd(b, a%b):a;}
template <typename T> ll lcm(T a, T b) {return a * b / gcd(a, b);};
template <typename T> inline void chmin(T &a, const T& b){if(a>b)a=b;}
template <typename T> inline void chmax(T &a, const T& b){if(a<b)a=b;}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  double n, k;
  cin >> n >> k;
  vector<double> vec(n);
  rep(i, n) {
    double a; cin >> a;
    vec[i] = (a+1.0)/2;
  }
  vector<double> sum(n);
  double tmp = 0.0;
  double ans = 0.0;
  
  for (int i = 0; i < k; ++i) {
    tmp += vec[i];
  }
  sum[k - 1] = tmp;
  for (int i = k; i < n; ++i) {
    sum[i] = sum[i-1] + vec[i] - vec[i - k];
    chmax(ans, sum[i]);
  }
  chmax(ans, sum[k-1]);
  cout << ans << '\n';
}


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

typedef long long ll;

int main(){
    ll n, a, b;
    cin >> n >> a >> b;

    if((n < 2 && a != b) || a > b){
        cout << 0 << endl;
    }else{
        cout << b*(n-2) - a*(n-2) + 1<< endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    int l,r,d;
    cin >> l >> r >> d;
    l--;
    cout << r/d - l/d << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Measured memory_bytes: 3632
s = gets.chomp.split("")

num = 0

#BとWとの境界を数える
#B問題ならこれで通りそうだが、C問題なので想定していないケースがありそう

state = s.shift

s.each do |stone|
	if stone != state then
		num +=1
	end
	state = stone
end

puts num

Measured memory_bytes: 9212
{-# LANGUAGE MultiWayIf #-}

main :: IO ()
main = do
  [a, b] <- map read . words <$> getLine
  putStrLn $ if
    | a > 0                 -> "Positive"
    | a == 0                -> "Zero"
    | b >= 0                -> "Zero"
    | (b - a) `mod` 2 == 0  -> "Negative"
    | otherwise             -> "Positive"


Measured memory_bytes: 508
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	int N;
	cin>>N;
	REP(i, N) {
		vector<int> hoge(3);
		REP(j, 3) cin>>hoge[j];
		sort(ALL(hoge));
		if(hoge[0] * hoge[0] + hoge[1] * hoge[1] == hoge[2] * hoge[2])cout<<"YES"<<endl;
		else cout<<"NO"<<endl;

	}
}

Measured memory_bytes: 3016
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <set>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin >> n;
    string t;
    set<string> s;
    bool r = true;
    cin >> t;
    string prev = t;
    s.insert(t);
    long k;
    for(int i = 1; i < n; i++){
        cin >> t;
        k = s.size();
        s.insert(t);
        if(s.size() == k || t[0] != prev[prev.size()-1])
            r = false;
        prev = t;
    }
    if (r)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<cstdio>
#define N 100000

using namespace std;



int main(){
  int K,c[N],i,ans=0;

  while(1){
    ans=0;
    for(i=0;i<N;i++){
      c[i]=0;
    }
    
    cin >> K;
    if(K==0)break;
    
  
   
    for(i=0;i<(K*(K-1))/2;i++){
      cin >> c[i];
    }
  
   
    
    for(i=0;i<=(K*(K-1))/2;i++){
      ans+=c[i];  
    }

    
  ans=ans/(K-1);
  
  cout << ans << endl;
  
  
  }
  
}

Measured memory_bytes: 1256
def valid?(a, b, c)
  a <= b + c && b <= c + a + 1 && c <= a + b + 1
end
 
def calc(rear, front, west, east, north, south, best)
  path = []
  loop do
    a = rear + front
    b = west + east
    c = north + south
 
    return path if a + b + c == 0
 
    if east > 0 && valid?(b - 1, c, a)
      rear, front, west, east = east - 1, west, rear, front
      y = 69
    elsif north > 0 && valid?(c - 1, a, b)
      rear, front, north, south = north - 1, south, front, rear
      y = 78
    elsif south > 0 && valid?(c - 1, a, b)
      rear, front, north, south = south - 1, north, rear, front
      y = 83
    #elsif west > 0 && valid?(b - 1, c, a)
    else
      rear, front, west, east = west - 1, east, front, rear
      y = 87
    end
     
    if best
      x = best[path.size]
      return best if x < y
      best = nil if x > y
    end
    path << y  
  end
end
 
def find(target)
  best = nil
  target.permutation(6).to_a.uniq.each do |rear, front, west, east, north, south|
    a = rear + front
    b = west + east
    c = north + south
    if valid?(a, b, c)
      best = calc(rear, front, west, east, north, south, best)
    end
  end
  best
end
 
loop do
  target = gets.split.map!(&:to_i)
  break if target.all?(&:zero?)
  p, q = gets.split.map!(&:to_i)
  result = find(target)
  puts result ? result[p-1...q].pack('C*') : 'impossible'
end

Measured memory_bytes: 76908
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVL vector<vector<ll>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
using std::cout;
using std::endl;
using std::cin;
using std::sort;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::multiset;


// 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; }
// ll pow(ll a, ll b) { ll ans = 1; while (b > 0) { if (b % 2 == 1) { ans *= a; ans %= MOD; }b /= 2; a *= a; a %= MOD; }return ans%MOD; }
// ll comb(ll n, ll r) { if (n - r < r) { return comb(n, n - r); }static VVL memo = {{1}}; if (memo.size() < n + 1) { memo.reserve(n + 1); FOR(i, memo.size(), n + 1) { memo.emplace_back(i + 1, 0); REP(j, i + 1) { memo[i][j] = 0;	if (j < i) { memo[i][j] += memo[i - 1][j]; }if (j > 0) { memo[i][j] += memo[i - 1][j - 1]; }memo[i][j] %= MOD; } } }return memo[n][r]; }
// ll comb_L(ll a, ll b) { if (a - b < b) { return comb(a, a - b); }static unordered_map<ll, ll> memo; ll c = 1; FOR(i, a - b + 1, a + 1) { c *= i; c %= MOD; }if (memo.find(b) == memo.end()) { ll k = 1; FOR(i, 2, b + 1) { k *= i;	k %= MOD; }memo[b] = pow(k, MOD - 2); }	c *= memo[b]; return c % MOD; }
// multiset<ll> prime_decomposition(ll n) { ll i = 2; multiset<ll> table{}; while (i * i <= n) { while (n % i == 0) { n /= i;	table.emplace(i); }++i; }if (n > 1) { table.emplace(n); return table; }return table; }
//-- bit -- REP(i, (1 << n)) {REP(j, n) {cout << (1 & (i >> j));}cout << endl;}

//==============================================================================================


int main() {
	ll n;
	cin >> n;
	cout << ((n == 3 || n == 5 || n == 7) ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
# 文字列の数（N）の分だけ、文字列を取得する
n=[input() for i in range(int(input()))]

# 文字列の数（M）の分だけ、文字列を取得する
m=[input() for i in range(int(input()))]

# 重複する文字列を削除するため、Nを集合にし、再度リスト化する
l = list(set(n))

# Lのリストの要素の文だけ繰り返す。
# Nのリストにおいて、任意の数番目のLのリストの要素の数から、
# Nのリストにおいて、任意の数番目のLのリストの要素の数を引く
# Lの要素の数だけ引き算を繰り返し、その中で最大のものを取り出す
# 取り出したものを0と比較し、大きい方を出力する
print(max(0,max(n.count(l[i]) - m.count(l[i]) for i in range(len(l)))))

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

int main () {
  ll a, b, k;
  cin >> a >> b >> k;
  
  if (a > k) {
    a -= k;
  }
  else {
    k -= a;
    a = 0;
    if (b > k) {
      b -= k;
    }
    else {
      b = 0;
    }
  }
  cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(in) in.begin(),in.end()

using ll = long long;
using namespace std;

struct BIT{
    int n;
    vector<ll> bit;

    BIT(int s){
        bit.resize(s+1,0); n = s;
    }
    ll sum(int i){
        ll res = 0;
        for( ; i>0; i -= i & -i) res += bit[i];
        return res;
    } // i番目(1-indexed)までの和
    void add(int i, ll x){
        for( ; i<=n; i += i & -i) bit[i] += x;
    } // i番目(1-indexed)にxを加える
};

int main(){
    int n, k; cin >> n >> k;
    vector<ll> a(n), sum(n+1,0), copy(n+1,0);
    rep(i,n){
        cin >> a[i], a[i] -= k;
        sum[i+1] = copy[i+1] = sum[i] + a[i];
    }

    sort(all(copy));
    copy.erase(unique(all(copy)), copy.end());
    rep(i,n+1) sum[i] = lower_bound(all(copy), sum[i]) - copy.begin(), sum[i]++;
    int s = copy.size(); // index : 1 ~ s

    ll count = 0;
    BIT ans(s);
    rep(i,n+1){
        count += ans.sum(sum[i]);
        ans.add(sum[i],1);
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 9592
#include<bits/stdc++.h>
using namespace std;
int LEFT[6][6] = {
  { -1, 4, 2, 5, 3, -1},
  { 3, -1, 6, 1, -1, 4},
  { 5, 1, -1, -1, 6, 2},
  { 2, 6, -1, -1, 1, 5},
  { 4, -1, 1, 6, -1, 3},
  { -1, 3, 5, 2, 4, -1}
};
struct Dice{
  int cnt; // 個数
  int left, right; // 左 , 右
  int ue, sita;    // 上 , 下
  int mae, usiro;  // 前 , 後
  Dice():cnt(0){};
  Dice(int _ue, int _mae){
    ue = _ue; sita = 7 - ue;
    mae = _mae; usiro = 7 - mae;
    left = LEFT[_ue - 1][_mae - 1]; right = 7 - left;
  }
  int get(int ang){ //サイドな値を返す
    if(ang == 0) return mae;
    if(ang == 1) return usiro;
    if(ang == 2) return left;
    if(ang == 3) return right;
  }
  void Roll(int ang){ //愚直
    int temp ;
    if(ang == 1){ //後ろへ転がす
      temp = ue;
      ue = mae;
      mae = sita;
      sita = usiro;
      usiro = temp;
    } else if(ang == 0){ //前に転がす
      temp = ue;
      ue = usiro;
      usiro = sita;
      sita = mae;
      mae = temp;
    } else if(ang == 2){ //左に転がす
      temp = ue;
      ue = right;
      right = sita;
      sita = left;
      left = temp;
    } else { //右に転がす
      temp = ue;
      ue = left;
      left = sita;
      sita = right;
      right = temp;
    }
  }
};

int main(){
  int n;
  Dice dice[200][200];
  
  int dy[] = { -1, 1, 0, 0}, dx[] = { 0, 0, -1, 1};
  while(cin >> n, n){

    fill_n( *dice, 200 * 200, Dice());

    for(int i = 0; i < n; i++){
      int t, f;
      cin >> t >> f;

      int y = 100, x = 100;

      Dice HR = Dice( t, f);

      while(true){

        int ret = 0;
        int ang = -1;
        for(int j = 0; j < 4; j++){
          int ny = y + dy[j], nx = x + dx[j];
          if(dice[y][x].cnt > dice[ny][nx].cnt){ //転がれて
            if(HR.get(j) >= 4){ //転がれて
              if(ret < HR.get(j)){ //よりよかったら
                ret = HR.get(j);
                ang = j;
              }
            }
          }
        }

        //転がれない
        if(ang == -1){
          int prev = dice[y][x].cnt;
          dice[y][x] = HR;
          dice[y][x].cnt = prev + 1;
          break;
        } else { //転がる
          HR.Roll(ang);
          y += dy[ang], x += dx[ang];
        }
      }
    }
    int ret[7] = {};
    for(int i = 0; i < 200; i++){
      for(int j = 0; j < 200; j++){
        if(dice[i][j].cnt > 0){
          ret[dice[i][j].ue]++;
        }
      }
    }
    for(int i = 1; i <= 6; i++){
      if(i != 1) cout << " ";
      cout << ret[i];
    }
    cout << endl;
  }
}

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

int main() {
  vector<int> a;
  int L, A;

  while(1){
    cin >> A >> L;
    if(L == 0 && A == 0) return 0;
    a.push_back(A);

    for(int k = 0; k < 20; k++) {
      vector<int> n;
      //数を細切れにする                                                             
      for(int i = L-1; i >= 0 ; i--) {
        int div = pow(10, i);
        n.push_back(A/div);
        A = A % div;
      }

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

      //最大と最小を求める                                                           
      int min = 0;
      int max = 0;
      for(int i = L-1; i >= 0; i--) {
        int mal = pow(10, i);
        min = min + mal*n[L-i-1];
        max = max + mal*n[i];
      }

      a.push_back(max-min);

      //過去に同じものがないか比較                                                   
      int flag = 0;
      for(int i = 0; i < a.size()-1; i++) {
        if(a[a.size()-1] == a[i]) {
	cout << i << ' ' << a[i] << ' ' << a.size()-i-1 << endl;
        flag = 1;
	}
      }
      if(flag == 1) break;
      A = max-min;
    }
    a.clear();
  }
  return 0;
}



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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

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

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

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> p(n);
  for(int i=0;i<n;i++) cin >> p[i];

  UnionFind tree(n);

  for(int i=0;i<m;i++){
    int x,y;
    cin >> x >> y;
    tree.unite(x-1,y-1);
  }
  int cnt = 0;
  for(int i=0;i<n;i++){
    if(tree.same(i,p[i]-1)) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >>N;
  vector<long long> A(N*3,0);
  for(int i=0; i<N*3; i++){
    long long a;
    cin >>a;
    A[i]=a;
  }
  sort(A.begin(), A.end());
  long long ans=0;
  for(int i=0; i<N; i++){
    int z=3*N-2-2*i;
    ans+=A[z];
//    cout<<"i:"<<i<<" ans:"<<ans<<endl;
  }
  cout <<ans <<endl;
}


Measured memory_bytes: 2560
//c.c C-Unification
#include<stdio.h>
#include<string.h>


int main(void){
    char buf[100001];
    scanf("%s",buf);
    int len = strlen(buf);

    int x0 = 0,x1 = 0;
    for(int i=0;i<len;++i){
        if(buf[i]=='0'){
            x0++;
        }else{
            x1++;
        }
    }
    if(x0==x1){
        printf("%d\n",x0+x1);
    }else if(x0>x1){
        printf("%d\n",x1*2);
    }else{
        printf("%d\n",x0*2);
    }
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
 
input_num = stdin.readline().strip().split(" ")

X = int(input_num[0])
N = int(input_num[1])
num_list = []
if N != 0:
    num_list = [int(x) for x in stdin.readline().strip().split(" ")]


dec_num = X
inc_num = X
if N == 0:
    print(X)
elif X not in num_list:
    print(X)
else:
    while True:
        dec_num += -1
        inc_num += 1
        if dec_num not in num_list:
            print(dec_num)
            break
        if inc_num not in num_list:
            print(inc_num)
            break

Measured memory_bytes: 9200
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int[][] bridges = new int[m][2];
    for (int i = 0; i < m; i++) {
      bridges[i][0] = scanner.nextInt() - 1;
      bridges[i][1] = scanner.nextInt() - 1;
    }

    UnionFind uf = new UnionFind(n);
    long[] result = new long[m + 1];
    result[m] = (long) n * (n - 1) / 2;
    for (int i = m - 1; i >= 0; i--) {
      int a = bridges[i][0];
      int b = bridges[i][1];
      result[i] = result[i + 1];
      if (uf.find(a) == uf.find(b)) continue;
      result[i] -= (long) uf.size(a) * uf.size(b);
      uf.union(a, b);
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= m; i++) sb.append(result[i]).append('\n');
    System.out.println(sb.toString());
  }

  private static class UnionFind {
    private final int[] table;
    private final int[] ranks;
    private final int[] sizes;

    public UnionFind(int size) {
      this.table = new int[size];
      this.ranks = new int[size];
      this.sizes = new int[size];
      for (int i = 0; i < size; i++) {
        this.table[i] = i;
        this.sizes[i] = 1;
      }
    }

    public int size(int n) {
      return sizes[find(n)];
    }

    public int find(int n) {
      if (table[n] != n) {
        table[n] = find(table[n]);
      }
      return table[n];
    }

    public void union(int x, int y) {
      int xRoot = find(x);
      int yRoot = find(y);
      if (xRoot == yRoot) return;

      if (ranks[xRoot] < ranks[yRoot]) {
        int tmp = xRoot;
        xRoot = yRoot;
        yRoot = tmp;
      }
      table[yRoot] = xRoot;
      sizes[xRoot] += sizes[yRoot];
      if (ranks[xRoot] == ranks[yRoot]) ranks[xRoot]++;
    }
  }
}

Measured memory_bytes: 94128
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//ここまでテンプレ
int main(){
	string S;
	cin>>S;
	bool N=0,E=0,W=0,T=0;
	for(int i=0;i<S.size();i++){
		if(S[i]=='N')
			N=1;
		if(S[i]=='E')
			E=1;
		if(S[i]=='W')
			W=1;
		if(S[i]=='S')
			T=1;
	}
	if(N==T && E==W)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long A, B;
    cin >> A >> B;
    if (A % 2 != B %2){
        cout << "IMPOSSIBLE" << endl;
    }
    else{
        cout << (A+B)/2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys

def comb_mod(n, r, mod):
  x = 1
  y = 1
  for i in range(r):
    x = (x * (n - i)) % mod
    y = (y * (i + 1)) % mod
    
  ans = x * pow_k(y, mod-2, mod)
  
  return ans % mod
  
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod
  
MOD = 10 ** 9 + 7
x, y = map(int, input().split())

if (2*x - y) % 3 != 0:
  print(0)
  sys.exit(0)
  
a = (2*x - y) // 3
b = (2*y - x) // 3

if a < 0 or b < 0:
  print(0)
  sys.exit(0)  

ans = comb_mod(a+b, min(a,b), MOD)
print(ans)

Measured memory_bytes: 3064
s=input()
s=s.replace("BC","D")
m=[]
is_seq=False
t=""
for ss in s:
  if is_seq:
    if ss=="A" or ss=="D":
      t+=ss
    else:
      m.append(t)
      t=""
      is_seq=False
  else:
    if ss=="A":
      is_seq=True
      t+=ss
if t!="":
  m.append(t) 
# print(m)
ans=0
for mm in m:
  cnt_a=mm.count("A")
  for i in range(len(mm)):
    if mm[i]=="A":
      ans+=len(mm)-cnt_a-i
      cnt_a-=1
print(ans)



Measured memory_bytes: 4516
#include<stdio.h>
int main()
{

          int X,h,m,s,x,y,z;
          scanf("%d",&X);
          h=X/3600;
          X=X%3600;
          m=X/60;
          X=X%60;
          s=X;
          printf("%d:%d:%d\n",h,m,s);
          return 0;


}



Measured memory_bytes: 2740
from itertools import product, accumulate
S = input()

def eval_(s, pat):
    s = list(map(int, s))
    ans = s[0]
    for i in range(3):
        if pat[i] == '+':
            ans += s[i+1]
        else:
            ans -= s[i+1]
    return ans

eq = ''
for pat in product(('+', '-'), repeat=3):
    if eval_(S, pat) == 7:
        eq = S[0]
        for i in range(3):
            eq += pat[i] + S[i+1]
        break

print(eq+'=7')


Measured memory_bytes: 3064
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = [0]*10000
    a[n] = 1
    cnt = 1
    while True:
        if n%2 == 0:
            n //= 2
        else:
            n = 3*n + 1
        cnt += 1
        if a[n] == 1:
            print(cnt)
            break
        else:
            a[n] = 1

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mod =1e9+7;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

template<class T> T maxt(T x,T y) {if (x>y) return x;else return y;}
template<class T> T mint(T x,T y) {if (x>y) return y;else return x;}
//sort(v.begin(), v.end(), [](auto& x, auto& y){return x[1] < y[1];});


//小数出力
double print_double(double d){printf("%.15lf\n", d);}

//約数列挙
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}



// ll combination_mod(int n, int k) {
//   k = mint(k,n-k);
//   ll ans = 1;
//   if (n==0 || k ==0) return ans;
//   rep(i,k) {
//     ans = ans*(n-i)%mod;
//     ans = ans*modinv(i+1)%mod;
//   }
//   return ans;
// }

struct edge {
  int from; //出発点
  int to;   //到達点
  ll cost; //移動コスト
};

//ベルマンフォード法
vector<ll> bellman_ford (vector<edge> edges, int V, int E, int r, ll INF = 100000000000) {  
  vector<ll> cost_to(V,INF);
  cost_to[r] = 0;
  rep(i,V) {
    rep(j,E) {
      edge e = edges[j];
      if (cost_to[e.from]==INF) continue;
      if (cost_to[e.to] > cost_to[e.from] + e.cost) {
        cost_to[e.to] = cost_to[e.from] + e.cost;
        if (i==V-1) {
          printf("NEGATIVE CYCLE\n");
          return {};
        }
      }

    }
  }
  return cost_to;
}

// combination
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}


// 木上の探索
vector<int> cnt;
void dfs(const vector<vector<int>> &G, int v, int p) {
    for (auto nv : G[v]) {
        if (nv == p) continue; // nv が親 p だったらダメ
        dfs(G, nv, v);
    }

    // 帰りがけ時に、部分木サイズを求める
    cnt[v] = 1; // 自分自身
    for (auto c : G[v]) {
        if (c == p) continue;
        cnt[v] += cnt[c]; // 子のサイズを加える
    }
}


int main() {
  ll A,B,N,x;
  cin >> A >> B >> N;
  x = min(N,B-1);
  cout << A*x/B - A*(x/B) << endl;
}


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

vector<int>vc;

int main()
{
    ll a,b,cnt=0,ans=2018;
    cin >> a >> b;
    for(ll i =a;i<=b;i++)
    {
        ll x = i%2019;
        vc.push_back(x);
        cnt++;
        if(cnt>2020)break;
    }
    int s = vc.size();
    for(int i=0;i<s;i++)
    {
        for(int j=i+1;j<s;j++)
        {
            ll x = (vc[i] * vc[j])%2019;
            ans = min(ans,x);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
map<ll,ll> mp;
ll df(ll n){
    ll res=1;
    while(--n){
        res*=(n+1);
        res%=mod;
    }
    return res;
}
int main(){
ll n;
cin>>n;
string s;
cin>>s;
string tmp="L";
for(int i=1;i<s.size();i++){
    if(s.at(i-1)!=s.at(i)){
        tmp+=tmp.at(tmp.size()-1);
    }
    else {
        if(tmp.at(tmp.size()-1)=='L')tmp+='R';
        else tmp+='L';
    }
}
int cntl=0,cntr=0;
for(int i=0;i<tmp.size();i++){
    if(tmp.at(i)=='L')cntl++;
    else cntr++;
}
if(cntr!=cntl||s.at(0)=='W'||s.at(s.size()-1)=='W'){
    cout<<0<<endl;
    return 0;
}
cntl=0;cntr=0;
ll ans=1;
for(int i=0;i<tmp.size();i++){
    if(tmp.at(i)=='L')cntl++;
    else{
             ans*=cntl;
             ans%=mod;
             cntl--;
    }
}
ans=ans*df(n)%mod;
cout<<ans<<endl;
}




Measured memory_bytes: 776
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        if(a < b && b < c) System.out.printf("Yes\n");
        else System.out.printf("No\n");
    }
}


Measured memory_bytes: 26192
import heapq
import sys
n, m = [int(i) for i in input().split()]
que = list()
dic = dict()
for i in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    if dic.get(a) is None:
        dic[a] = []
    dic[a].append(b)

cnt = 0
for i in range(1, m+1):
    if dic.get(i) is not None:
        for j in dic.get(i):
            heapq.heappush(que, -j)
    if len(que) > 0:
        _max = heapq.heappop(que)
        cnt += -_max
print(cnt)

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

int N;
int A[210];

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

	while (A[0] % 2 == 0) {
		for (int i = 0; i < N; i++) {
			if (A[i] % 2 != 0) {
				break;
			}
			else {
				A[i] = A[i] / 2;
			}
			if (i == N-1)c++;
		}
	}

	cout << c << endl;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int, input().split()))
#3枚とって最大最小の二枚を食べる
B=[0]*(max(A))
for a in A:
    B[a-1]+=1

B=sorted(B, reverse=True)

#print(sorted(A))
#print(B)
ans=0
pre=0
for b in B:
    b-=pre
    if b>=2 and b%2==1:
        #ans+=(b-1)//2
        #print((b-1)//2)
        pre=0
        b=1
    elif b>=2 and b%2==0:
        #ans+=(b-2)//2+1
        #print((b-2)//2+1)
        pre=1
        b=1
    elif b<2:
        pre=0
    ans+=b
    #print(b)
print(ans)

Measured memory_bytes: 14396
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int i;
int A[1000000];
int n;
vector<int>G;

void insertionSort(int A[], int n, int g) {
	for (int i = g; i < n; i++) {
		int v = A[i];
		int j = i - g;
		while (j >= 0 && A[j] > v) {
			A[j + g] = A[j];
			j -= g;
			cnt++;
		}
		A[j + g] = v;
	}
}

void shellSort(int A[], int n) {
	for (int h = 1;;) {
		if (h > n)break;
		G.push_back(h);
		h = 3 * h + 1;
	}

	for (int i = G.size() - 1; i >= 0; i--) {
		insertionSort(A, n, G[i]);
	}
}

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

	shellSort(A, n);
	cout << G.size() << endl;
	for (int i = G.size() - 1; i >= 0; i--) {
		printf("%d", G[i]);
		if (i)printf(" ");
	}
	printf("\n");
	printf("%d\n", cnt);
	for (int i = 0; i < n; i++)printf("%d\n", A[i]);

	return 0;
}


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

using namespace std;

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

int main(){
    long int n;
    cin >> n;
    long int a[n];
    rep(i, n){
        cin >> a[i];
        a[i]--;
    }
    long int c[n];
    rep(i, n) c[i] = 0;
    
    rep(i, n){
        c[a[i]]++;
    }
    long int sm = 0;
    rep(i, n){
        if (c[i] > 1){
            sm += ((c[i] - 1) * c[i]) / 2;
        }
    }
    rep(i, n){
        long int num = c[a[i]] - 1;
        long int ans = sm;
        ans -= ((c[a[i]] - 1) * c[a[i]]) / 2;
        if (num > 1){
            ans += ((num - 1) * num) / 2;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 5760
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n = ri()
    L = [0] * (n + 1)
    for i in rl():
        L[i] += 1

    for i in range(1, n + 1):
        print (L[i])






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


Measured memory_bytes: 105192
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int ans = INT32_MAX;
    for(int AB=0; AB<=max(X, Y)*2; AB+=2) {
        ans = min(ans, A*max(X-AB/2, 0) + B*max(Y-AB/2, 0) + C*AB);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), n)
#define ub(v,n) upper_bound(v.begin(), v.end(), n)
#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")

template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7; const int MAX = 200020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 2e18;

template<typename T>
struct SegmentTree {
	int n;
	T unit;
	vector<T>dat;
	function<T(T, T)> func;
	SegmentTree(const int N, T _unit, function<T(T, T)> _func)
		:unit(_unit), func(_func) {
		n = 1;
		//簡単のため、要素数を2のべき乗に
		while (n < N)n *= 2;
		dat.assign(2 * n, unit);
	}

	void update(int k, T a) {
		k += n - 1;//葉の節点
		dat[k] = a;
		//上りながら更新
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}
	T _query(int a, int b, int k, int l, int r) {
		//[a,b)と[l,r)が交差していなければ、funcに影響を与えない値を返す
		if (r <= a || b <= l)return unit;
		//[a,b)が[l,r)を完全に含んでいれば、この節点の値
		if (a <= l && r <= b)return dat[k];
		else {
			int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
			return func(vl, vr);
		}
	}
	//[a,b)
	T query(int a, int b) {
		return _query(a, b, 0, 0, n);
	}
};
//auto f = [](int a, int b) {return a + b; };
//SegmentTree<int>seg(N,0,f);

int cnt[100010];
void solve() {
	map<int, int>mp;
	int N, K; cin >> N >> K;
	vector<int>A(N), cum(N + 1);
	REP(i, N) {
		cin >> A[i];
		A[i] = A[i] + K - 1;
		A[i] %= K;
	}
	ll ans = 0;
	mp[0]++;
	queue<int>que;
	que.push(0);
	REP(i, N) {
		if (i >= K - 1) {
			int tmp = que.front(); que.pop();
			mp[tmp]--;
		}
		int now = A[i];
		cum[i + 1] = cum[i] + A[i];
		cum[i + 1] %= K;
		ans += mp[cum[i+1]];
		que.push(cum[i + 1]);
		mp[cum[i+1]]++;
	}
	print(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//test();
	solve();
}

Measured memory_bytes: 17536
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

H,W = inputIL()
s = []
for i in range(H):
  s.append(list(inputS()))

dp = [[INF for __ in range(W)] for ___ in range(H)]

for i in range(H):
  for j in range(W):
    if i==0 and j==0: 
      dp[i][j] = 0
    if i!=0:
      
      if s[i][j] == s[i-1][j]:
        dp[i][j] = min(dp[i-1][j],dp[i][j])
      else:
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j])
    if j!=0:
      if s[i][j] == s[i][j-1]:
        dp[i][j] = min(dp[i][j-1],dp[i][j])
      else:
        dp[i][j] = min(dp[i][j-1]+1,dp[i][j])


if s[0][0] == ".":
  print((dp[-1][-1]+1)//2)
else:
  print((dp[-1][-1])//2+1)

Measured memory_bytes: 68204
#include "bits/stdc++.h"
#define F first
#define S second
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
ll ceil(ll n, ll d) {
  return (n + d - 1) / d;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll h = 0, a = 0;
  cin >> h >> a;
  cout << ceil(h, a);
}



Measured memory_bytes: 3604