akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    int count = 0;
    for (int i = 0; i < n; i++){
        int a;
        cin >> a;
        // 2
        if (a == 2){
            count++;
            continue;
        }
        // even but 2
        if (a % 2 == 0) continue;
        // odd
        double b = sqrt(double(a));
        bool isPrime = true;
        for (int j = 2; j <= b; j++){
            if (a % j == 0){
                isPrime = false;
                break;
            }
        }
        if (isPrime) count++;
    }
    cout << count << endl;
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}
const int MAX_N = 50;
const int MAX_A = 50;
const int MAX_X = 50;
LL dp[MAX_N + 1][MAX_N + 1][MAX_X * MAX_N + 1];
int N, A;
VEC<LL> X;
int main() {
  cin >> N >> A;
  X = VEC<LL>(N + 1, 0);
  REP(i, 1, N + 1) cin >> X[i];
  sort(ALL(X));
  int maxX = X[X.size() - 1];
  DUMP(X);

  REP(j, 0, N + 1) {
    REP(k, 0, N + 1) {
      REP(s, 0, N * maxX + 1) {
        LL f = 0;
        if (j == 0 && k == 0 && s == 0)
          f = 1;
        else if (j >= 1 && s < X[j])
          f = dp[j - 1][k][s];
        else if (j >= 1 && k >= 1 && s >= X[j])
          f = dp[j - 1][k][s] + dp[j - 1][k - 1][s - X[j]];
        dp[j][k][s] = f;
        // DUMP(j, k, s, f);
      }
    }
  }
  int k = 1;
  LL ans = 0;
  while (k <= N) {
    // DUMP("   ", N, k, k * A, dp[N][k][k * A]);
    ans += dp[N][k][k * A];
    ++k;
  }
  cout << ans << endl;
}

Measured memory_bytes: 51072
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
int main(){
    string s;
    cin>>s;
    int t=s.size();
    cout<<s[0]<<t-2<<s[t-1]<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <math.h>
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;

int main() {
	ll N, L; cin >> N >> L;
	ll sum = 0;
	rep(i, 0, N)sum += L + i;

	ll minV = 1e10;
	ll V = 1e10;
	rep(i, 0, N) {
		if (minV > abs(L + i)) {
			minV = abs(L + i);
			V = L + i;
		}
	}

	cout << sum - V << endl;

	return 0;
}

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

using namespace std;

using ll = long long int;

const ll INF = 0x3FFFFFFFFFFFFFFFLL;

ll cost[2000][2000];

int main(){
    
    ll N, M;
    cin >> N >> M;
    for(ll i = 0; i < N; ++i){
        for(ll j = 0; j < i; ++j){
            cost[i][j] = INF;
        }
        cost[i][i] = 0;
        for(ll j = i + 1; j < N; ++j){
            cost[i][j] = INF;
        }
    }
    for(ll i = 0; i < M; ++i){
        ll A, B, C;
        cin >> A >> B >> C;
        cost[A - 1][B - 1] = -C;
    }
    for(ll k = 0; k < N; ++k){
        for(ll i = 0; i < N; ++i){
            for(ll j = 0; j < N; ++j){
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
    for(ll i = 0; i < N; ++i){
        if(cost[0][i] < INF / 2 && cost[i][N - 1] < INF / 2 && cost[i][i] < 0){
            cout  << "inf" << endl;
            return 0;
        }
    }
    cout << -cost[0][N - 1] << endl;
    return 0;
}

Measured memory_bytes: 16256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

int n;
string s;
// おおかみ、ひつじ: 0, 1
// ことなる、ひとしい: 0, 1
vi v, ans;

bool check(int a, int b) {
    ans[0] = a;
    ans[1] = b;
    for(int i = 2; i < n; ++i) {
        if(ans[i - 1] == 0) { // おおかみ
            if(v[i - 1] == 0)ans[i] = ans[i - 2];
            else ans[i] = 1 - ans[i - 2];
        } else { // 羊
            if(v[i - 1] == 0)ans[i] = 1 - ans[i - 2];
            else ans[i] = ans[i - 2];
        }
    }
    
    rep(i, n) {
        int same = v[i];
        if(ans[i] == 0)same = 1 - same;
        int p = ans[(n + i - 1) % n], q = ans[(i + 1) % n];
        if(same&&p!=q)return false;
        if(!same&&p==q)return false;
    }

    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n) {
        cin >> s;
        v.resize(n);
        ans.resize(n);

        rep(i, n)v[i] = (s[i] == 'o' ? 1 : 0);

        bool ok = false;
        rep(i, 2)rep(j, 2) {
            ok |= check(i, j);
            if(ok)goto HOGE;
        }
        HOGE:;
        if(!ok)cout << -1 << endl;
        else {
            string t;
            each(x, ans)t += x == 0 ? 'W' : 'S';
            cout << t << endl;
        }
    }
}


Measured memory_bytes: 1488
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
//#include <function>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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


int main() {

  vector<int> a(5);
  REP(i, 5){
    cin >> a[i];
  }
  int k;
  cin >> k;
  if (a[4] - a[0] > k){
    cout << ":("<< endl;
  } else {
    cout << "Yay!" << endl;
  }
  return 0;
}


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

typedef long long ll;
typedef pair<int,string> pis;
 
bool cmp(pis x, pis y){
  return x.first < y.first;
}
 
int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int N, m;
  cin >> N >> m;
    
  int p;
  string S;
  vector<pis> data(m);
  //map<int,string> data;
  for(int i=0;i<m;++i) {
      cin >> p >> S;
      data[i] = make_pair(p, S);
      
     // data[i].insert(pair<int, string>(p,S));
   }
  // for (int i = 0; i < m; ++i)
  // {
  //   cout<<data[i].first<<" "<<data[i].second<<endl;
  // }
  // cout<<endl;
  stable_sort(data.begin(), data.end(),cmp);
  // for (int i = 0; i < m; ++i)
  // {
  //   cout<<data[i].first<<" "<<data[i].second<<endl;
  // }
  // cout<<endl;

  // for (auto it=mymap.begin(); it!=mymap.end(); ++it)
  //   std::cout << it->first << " => " << it->second << '\n';

  ll temp = 0;
  ll penalty = 0;
  ll ans = 0;
  int flag = 0;   
  for(int i=0;i<m;i++){
    
    if(i != 0 && data[i-1].first != data[i].first) {
          flag = 0;
          temp = 0;
          //cout<<"TESTING"<<endl;
      }
      if(flag == 0 && data[i].second != "AC"){
          temp++;
          //cout<<temp<<endl;
      }
      else if(flag == 0 && data[i].second == "AC") {
          flag = 1;
          penalty += temp;
          ans++;
      }
      //cout<<temp<<endl;
      // if(temp!=0 && penalty==0)
      //   penalty+=temp;
  }
  
  cout << ans << " " << penalty << endl;
  return 0;
}
 

Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i, s, n) for(int i=(s); i<=(n); ++i)
#define outl(x) cout<< (x) << '\n'
template <class T> inline void chmin(T &a, T b) { if(b<a)a = b; }
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define let const auto
#define LEN 100010
#define NIL (-1)

int N;
vector <int> G[LEN];
bool vis[LEN];
int pre[LEN], par[LEN], lowest[LEN];
int timer;

void dfs(let cur, let from)
{
   pre[cur] = lowest[cur] = timer++;   //ノード cur を訪問した直後の処理
   vis[cur] = true;

   for(let nxt: G[cur]) {
      if ( !vis[nxt] ) {          //未訪問の場合
         par[nxt] = cur;           //親を設定
         dfs(nxt, cur);              //e へ探索
         chmin( lowest[cur], lowest[nxt] );
      }
      else if (nxt!= from) {   //cur ~ nxtが Back-edge の場合 (訪問済みで、 from と異なる場合)
         chmin( lowest[cur], pre[nxt] );
      }
   }
   return ;
}

void articulation_points()
{
   /* rep(i,N) vis[i] = false; */
   timer = 1;
   //lowest の計算
   dfs(0, NIL);   // 0 == root

   set <int> ap;
   int np = 0;
   for(int i=1; i<N; ++i) {
      let p = par[i];
      if(p == 0)++np;
      else if(pre[p] <= lowest[i])ap.emplace(p);
   }
   if(np > 1)ap.emplace(0);
   for(let x : ap)outl(x);
}

signed main()
{
   cin.tie(0), ios::sync_with_stdio(false);
   int m;
   cin >> N >> m;

   while(m--) {
      int s,t ;
      cin >> s >> t;
      G[s].emplace_back(t);
      G[t].emplace_back(s);
   }

   articulation_points();
}




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

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

using namespace std;

int N;
double memo[1010][1010];

double dfs(int n,int m){ // n -> already know, m -> unknown
  assert( m >= n );
  if( n >= m ) return 0.0;
  if( memo[n][m] >= 0 ) return memo[n][m];
  double ret = 0;
  // 一枚目が既知のカード

  double know_p = ( (double)n / (double)m );
  if( n )  ret += dfs(n-1,m-1) * know_p;

  // 一枚目がしらないカード
  double unknown_p = 1 - know_p;
  if( m - n >= 1 ) {
    // 二枚目も知らないカード
    if( m - n >= 2 && n+2 <= m-2 ) {
      double unknown = ( m - 1 - n ) ;
      double np = unknown_p * ( (unknown-1) / (double)(m-1) );
      ret += ( 1 + dfs(n+2,m-2) ) * np;
    }
    // 二枚目が偶然知っているカード
    // １枚目と同じ
    if( m - n >= 2 ) { 
      double np = unknown_p * ( 1.0 / (double)(m-1) );
      ret += dfs(n,m-2) * np;
    }

    // １枚目と同じではないが知っているカー土 
    if( n ) {
      double np = unknown_p * ( n / (double)(m-1) );
      ret += ( 1 + dfs(n,m-2) ) *  np ;
    }
  }
  return memo[n][m] = ret;
}

int main(){
  while( cin >> N, N ){
    rep(i,1010)rep(j,1010) memo[i][j] = -1;
    printf("%.8f\n",dfs(0,N));
  }
  return 0;
}

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

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    string M[3];
    while(cin >> M[0] >> M[1] >> M[2])
        cout << M[0][0] << M[1][1] << M[2][2] << '\n';
    return 0;
}

Measured memory_bytes: 256
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int main() {
    int a=read(),b=read();
    if (a<=0&&b>=0) puts("Zero");
    else if (a>0) puts("Positive");
    else if ((b-a+1)&1) puts("Negative");
    else puts("Positive");
    return 0;
}


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

int main(){
  int n;cin>>n;
  vector<int> a(n);
  ll ans=0;
  rep(i,n){
    cin>>a[i];
  }
  sort(all(a));
  if(n%2==1)ans-=a[n/2];
  for(int i=n/2;i<n;i++){
    ans+=a[i]*2;
  }
  
  cout<<ans-a[n-1];
}

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

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

void
empty(int *x, int *y)
{
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			if (!puzz[i][j])
			{
				*x = j;
				*y = i;
				return;
			}
		}
	}
}

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

int
cal()
{
	int sum = 0;
	for (int i = 0; i < 9; ++i)
	{
		int a = puzz[i / 3][i % 3];
		if (a)
		{
			a--;
			sum += abs(i / 3 - a / 3) + abs(i % 3 - a % 3);
		}
	}

	return sum;
}

int
dfs(int x, int y, int p, int dep, const int lim)
{
	int h = cal();
	if (h == 0)
		return dep;

	if (dep + h > lim)
		return -1;

	for (int i = 0; i < 4; ++i)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (p != -1 && i == (p + 2) % 4)
			continue;

		if (0 <= nx && nx < 3 && 0 <= ny && ny < 3)
		{
			swap(&puzz[y][x], &puzz[ny][nx]);
			int res = dfs(nx, ny, i, dep + 1, lim);
			if (res != -1)
				return res;

			swap(&puzz[y][x], &puzz[ny][nx]);
		}
	}

	return -1;
}

int
main(int argc, char **argv)
{
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
			scanf("%d", &puzz[i][j]);
	}

	int x = 0, y = 0;
	empty(&x, &y);

	for (int l = 0; l < 100; ++l)
	{
		for (int i = 0; i < 3; ++i)
		{
			for(int j = 0; j < 3; ++j)
				temp[i][j] = puzz[i][j];
		}

		int ans = dfs(x, y, -1, 0, l);
		if (ans != -1)
		{
			printf("%d\n", ans);
			break;
		}

		for (int i = 0; i < 3; ++i)
		{
			for(int j = 0; j < 3; ++j)
				puzz[i][j] = temp[i][j];
		}

		ans = -1;
		if (l == 99)
			printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 1808
while True:
    n,x=map(int,input().split())
    if n==0 and x==0:break
    ans =0
    for a in range(1,n+1):
        for b in range(1,n+1):
            if b<=a:continue
            c=x-(a+b)
            if c>b and c<=n:ans+=1
    print("%d"%(ans))



Measured memory_bytes: 5596
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;

int ad,muki,pos,leng,hight[6],map1[6][6000];

int main(){
  while(true){
    for(int raw=1;raw<6;raw++){
      for(int high=0;high<6000;high++){
	map1[raw][high]=0;
      }
    }
    int blo=0; 
    int x=0;
    cin>>ad;
    if(ad==0){break;}
    for(int i=0;i<ad;i++) {
      for(int j=1;j<6;j++){
	hight[j]=0;}

      cin>>muki;
      cin>>leng;
      cin>>pos;
      blo+=leng;
      for(int raw=1;raw<6;raw++){
	for(int high=0;high<6000;high++){
	  if(map1[raw][high]==1){
	    hight[raw]=max(hight[raw],high);
	  }
	}
	if(map1[raw][hight[raw]]==1){
	  hight[raw]++;
	}
	///cout<<hight[raw]<<" ";
      }
      ///cout<<endl;
      if(muki==2){
	for(int hhhh=0;hhhh<leng;hhhh++){
	  map1[pos][hight[pos]+hhhh]=1;
	}
      }
      if(muki==1){
	int hamu=0;
	for(int raw=pos;raw<pos+leng;raw++){
	  hamu=max(hight[raw],hamu);
	}
	for(int raw=pos;raw<pos+leng;raw++){
	  map1[raw][hamu]=1;
	}
      }/*
      for(int high=0;high<10;high++){
	for(int raw=1;raw<6;raw++){
	  cout<<map1[raw][high]<<" ";
	}
	cout<<endl;
      }
      cout<<"-----------------------"<<endl;
       *///kesi
      for(int high=0;high<6000;high++){
	int hantei=0;
	for(int raw=1;raw<6;raw++){
	  if(map1[raw][high]==0){break;}
	  else{hantei++;}
	}
	if(hantei==5){
	  x++;
	  for(int j=1;j<6;j++){
	    hight[j]--;}
	  for(int a=1;a<6000-high;a++){
	    for(int raw=1;raw<6;raw++){
	      map1[raw][high+a-1]=map1[raw][high+a];
	    }
	  }
	  high--;
	}
      }
    }
    int xxx=0;
    xxx=blo-(5*x);
    cout<<xxx<<endl;
  }
}

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

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

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N)
  {
    cin >> A[i];
  }
  vector<pair<int,int>> vec;
  rep(i,N)
  {
    vec.push_back(make_pair(A[i],i+1));
  }
  sort(ALL(vec));
  rep(i,N)
  {
    if(i!=N-1)
    {
      cout << vec[i].second << " ";
    }
    if(i==N-1)
    {
      cout << vec[i].second << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 4600
n = int(input())
S = ['']*n
T = []
for i in range(n):
    S[i] = input()
S.sort()
if n == 1:
    print(S[0])
    exit()
cnt = 1
mxcnt = 1
for i in range(n-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        cnt = 1
    mxcnt = max(mxcnt,cnt)
cnt = 1
for i in range(n-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        cnt = 1
    if cnt == mxcnt:
        T.append(S[i])
if mxcnt == 1:
    T.append(S[-1])
for t in T:
    print(t)

Measured memory_bytes: 25248
#include <stdio.h>
#include <stdlib.h>

signed int a[100000],ans;
/*unsigned*/ int n,k;
FILE*fp,*fq;

void solve(void){
	int i,diff;
	ans = 0;
	for(i = 0;i < k;i++)ans += a[i];
	diff = 0;
	while(i < n){
		diff += a[i];
		diff -= a[i - k];
		if(diff > 0){
			ans += diff;
			diff = 0;
		}
		i++;
	}
	return;
}

int inp(void){
	int i;
	fscanf(stdin,"%d",&n);
	if(!n)return 0;
	fscanf(stdin,"%d",&k);
	for(i = 0;i < n;i++)scanf("%d",&a[i]);
	return 1;
}

void oup(void){
	fprintf(stdout,"%d\n",ans);
	return;
}

int main(void){
	while(inp()){
		solve();
		oup();
	}
	return 0;
}

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

const int N = 1e6 + 5;

int main(){
    ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
    int n; cin >> n;
    int dd[n][3];
    memset(dd , 0 , sizeof(dd));

    int x , y , z;
    cin >> x >> y >> z;
    dd[0][0] = x;
    dd[0][1] = y;
    dd[0][2] = z;

    for(int i = 1; i < n ; i ++) {
        cin >> x >> y >> z;
        dd[i][0] = max(dd[i-1][1] , dd[i-1][2]) + x;
        dd[i][1] = max(dd[i-1][0] , dd[i-1][2]) + y;
        dd[i][2] = max(dd[i-1][0] , dd[i-1][1]) + z;
    }
    cout << max(dd[n-1][0] , max(dd[n-1][1] , dd[n-1][2]));
}

Measured memory_bytes: 1408
// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::queue;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int n, m, v, p;
    cin >> n >> m >> v >> p;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    sort(ALL(a));

    auto ok = [&](int from) {
        int rev_pos = n - 1 - from;
        if (rev_pos < p)
            return true;
        
        vector<int> new_arr = a;

        new_arr[from] += m;
        
        int64_t votes = int64_t(m) * max(0, v - (from + 1) - (p - 1));
                
        int64_t has_votes = 0;
        for (int i = from + 1; i <= n - p; ++i) {
            if (new_arr[from] < new_arr[i])
                return false;
            
            has_votes += new_arr[from] - new_arr[i];
        }

        return has_votes >= votes;
    };
    
    int lo = -1;
    int hi = n - 1;

    while (hi - lo > 1) {
        int mi = lo + (hi - lo + 1) / 2;

        if (ok(mi))
            hi = mi;
        else
            lo = mi;
    }

    cout << n - hi << "\n";

    return 0;
}


Measured memory_bytes: 1152
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    assert N == len(A)
    for i in A:
        if i % 2 == 0 and not (i % 3 == 0 or i % 5 == 0):
            print("DENIED")
            exit()
    print("APPROVED")


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val s = sc.next()

    var pre = 'x'
    s.forEach { c ->
        if (pre == c) {
            print("Bad")
            return
        }
        pre = c
    }
    print("Good")
}


Measured memory_bytes: 31384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
 
using namespace std;
typedef long long int lli;
const int MAX=1e5;
 
int main(){
	int N,C,K;
	cin>>N>>C>>K;
	int T[MAX];
	rep(i,N)cin>>T[i];
	sort(T,T+N);
	
	int bus=1,pas=1,lim=T[0]+K;
	rep1(i,N-1){
		if(pas+1>C||lim<T[i]){
			bus++;
			pas=1;
			lim=T[i]+K;
		}
		else pas++;
	}
	cout<<bus<<endl;
}

Measured memory_bytes: 640
import sys

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    tree = [[] for _ in range(4)]
    for i in range(3):
        a, b = il()
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)

    def dfs(prev, s, ans):
        for t in tree[s]:
            if t == prev:
                continue
            ans.append(s)
            _ = dfs(s, t, ans)
        return len(set(ans))

    return "YES" if dfs(-1, 0, []) == 3 else "NO"


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};
int main(void){
  int A, B;
  string S;
  cin >> A >> B >> S;

  if (S[A] != '-'){
    cout << "No" << endl;
    return 0;
  }
  for (int i = 0; i < A; i++){
    if (S[i] == '-'){
      cout << "No" << endl;
      return 0;
    }
  }
  for (int i = A + 1; i < A + B + 1; i++){
    if (S[i] == '-'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 3596
/*
abc103_b
*/
#include<algorithm>
#include<iostream>
#include<vector>
#include<fstream>
#include<string>
using namespace std;

string rotate(string x) {
	string res = x[x.size() - 1] + x;
	res = res.substr(0, res.size() - 1);
	return res;
}

int main() {
	string S, T;
	cin >> S >> T;
	string st = S;
	for (int i = 0; i < S.size(); i++) {
		st = rotate(st);
		if (st == T) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 384
/*
    やるだけでバグって辛い
 */

#include <cstdio>
#include <cassert>
using namespace std;

int n;
int a[100000];
int pos[100000];
long long int low;
long long int high;
long long int sum;

bool check(long long int x) {
    int s = 0;
    int t = 0;
    long long int now = 0;

    while (s < n) {
        while ((t+1)%n != s && now < x) {
            now += a[t];
            t = (t+1)%n;
        }
        if ((t+1)%n == s) return false;
        pos[s] = t;
        now -= a[s++];
    }

    for (int i=0; i<n; i++) {
        int len1 = pos[i] - i;
        int len2 = pos[pos[i]] - pos[i];
        int len3 = pos[pos[pos[i]]] - pos[pos[i]];

        if (len1 < 0) len1 += n;
        if (len2 < 0) len2 += n;
        if (len3 < 0) len3 += n;
        if (len1 + len2 +len3 <= n) return true;
    }

    return false;
}
    

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

    low = -1;
    high = (sum/3) + 1;
    while (high - low > 1) {
        long long int mid = (high+low)/2;
        if (check(mid)) low = mid;
        else high = mid;
    }

    printf("%lld\n", low);
}

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

using namespace std;

const int LIM = 2300;

using LL = long long;

vector<int> primes;

void
gen_primes()
{

	auto is_prime = [] (int n) -> bool
	{
		for(int i = 2; i * i <= n; ++i)
			if (n % i == 0)
				return false;
		return true;
	};

	primes.reserve(LIM);
	for(int i = 2; i <= LIM; ++i) {
		if (is_prime(i))
			primes.push_back(i);
	}
}

struct Entry 
{
	int prime;
	int pow;

	bool operator< (const Entry e) const
	{
		return tie(prime, pow) < tie(e.prime, e.pow);
	}
};

using Equiv = pair<vector<Entry>, LL>;

Equiv decompose(LL num)
{
	vector<Entry> ret;

	for(auto prime: primes) {
		if (num % prime == 0) {
			int p = 0;

			while(num % prime == 0) {
				p++;
				num /= prime;
			}

			p %= 3;

			if (p > 0)
				ret.push_back({prime, p});

		}
	}

	return {ret, num};
}

Equiv complement(const Equiv& equiv)
{
	vector<Entry> ret;
	for(auto e: equiv.first) {
		ret.push_back({e.prime, 3 - e.pow});
	}

	LL now = equiv.second;

	LL sol = 1;

	if (now > 1) {
		LL root = sqrt(now);

		sol = -1;

		for(int i = 0; i <= 1; ++i) {
			auto cur = root + i;
			if (cur * cur == now)
				sol = cur;
		}
	}

	return {ret, sol};
}

map<Equiv, int> normalize;

int main() 
{

	gen_primes();
	int N;
	cin >> N;
	vector<LL> v(N, 0);
	for(int i = 0; i < N; ++i)
		cin >> v[i];

	vector<Equiv> equivalence;
	equivalence.reserve(N);

	vector<int> freq(N, 0);
	for(int i = 0; i < N; ++i) {
		equivalence.push_back(decompose(v[i]));
		Equiv& ev = equivalence.back();

		int idx;

		auto it = normalize.find(ev);

		if (it == normalize.end()) {
			auto sz = normalize.size();
			normalize[ev] = sz;
			idx = sz;
		} else {
			idx = it->second;
		}

		freq[idx]++;
	}

	auto is_first = [] (const Equiv& equiv) -> bool 
	{
		if (equiv.first.empty())
			return equiv.second > 1;

		return  equiv.first[0].pow == 1 || equiv.second > 1;
	};

	int answer = N;

	for(auto &equiv_p: normalize) {

		auto &equiv = equiv_p.first;

		if (equiv.first.empty() && equiv.second == 1) {
			answer -= freq[equiv_p.second] - 1;
			continue;
		}


		if (is_first(equiv)) {
			auto comp = complement(equiv);

			int f1 = freq[equiv_p.second];

			auto it = normalize.find(comp);

			int f2 = (it == normalize.end() ? 0 : freq[it->second]);

			answer -= min(f1, f2);
		}
	}

	cout << answer << "\n";

	return 0;
}


Measured memory_bytes: 18688
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))


N=input1()
p=input_array()
count=0
min_int=0
for i in range(N):
	num=p[i]
	if i==0:
		min_int=num
		count+=1
	elif num<=min_int:
		min_int=num
		count+=1
		
print(count)








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

using namespace std;

int isp(long long n) {
    if (n < 0) return -1;
    int k = (int)pow(n+0.1, 0.2);
    return 1LL*k*k*k*k*k == n ? k : -1;
}

void solve() {

    int n;
    cin >> n;
    // A^5 - B^5
    for (int i = 1; i <= 1000; i++) {
        int ret = isp(1LL*i*i*i*i*i - n);
        if (ret < 0) continue;
        assert(1LL*i*i*i*i*i - 1LL*ret*ret*ret*ret*ret == n);
        printf("%d %d\n", i, ret);
        return ;
    }

    for (int i = 1; 2LL*i*i*i*i*i <= n; i++) {
        int ret = isp(n - 1LL*i*i*i*i*i);
        if (ret < 0) continue;
        assert(1LL*i*i*i*i*i + 1LL*ret*ret*ret*ret*ret == n);
        printf("%d -%d\n", i, ret);
        return ;
    }

}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 4168
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  int n;
  cin>>n;
  int vec[n+1];
    for(int idx = 1;idx<=n;idx++)
      cin>>vec[idx];
  
   int dp[n+1] = {0};
   
  
  if(n>=2){
    dp[n-1] = abs(vec[n-1]-vec[n]);
  }
     for(int idx = n-2;idx>0;idx--){
        dp[idx] = min(dp[idx+1]+abs(vec[idx+1]-vec[idx]),dp[idx+2]+abs(vec[idx]-vec[idx+2]) );
     }
  cout<<dp[1];
  return 0;
}

Measured memory_bytes: 1024
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>
#include <stdio.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N)cin >> A[i];

  int allxor = 0;

  rep(i,N){
    allxor ^= A[i];
  }

  rep(i,N){
    int  ans = (allxor)^(A[i]);
    cout << ans << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 3984
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include <set>
#include <queue>
#include <iomanip>
#include <sstream>
typedef long long ll;

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

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[510][510];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}
/*
ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}*/

int main() {
	ll x, y;
	cin >> x >> y;
	for (ll i = 0; i <= x; i++) {
		ll sum = 2 * i + 4 * (x - i);
		if (sum == y) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 3720
//
//  main.cpp
//  CoderTest
//
//  Created by yuya on 2019/05/20.
//  Copyright © 2019 yuya. All rights reserved.
//

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




int main(){
    int i;
    
    int A,P;
    
    cin >> A >> P;
    
    P += 3*A;
    
    cout << P/2 << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;
vector<int> ans;
signed main(){
    int n,m;
    string s;
    cin >> n >> m;
    cin >> s;
    int i = s.size()-1;
    while(i>0){
        i -= m;
        REP(j,m){
            if(i+j<0) continue;
            if(s[i+j] == '0'){
                ans.pb(m-j);
                i = i+j;
                break;
            }
            if(j==m-1){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    REP(i,ans.size()-1){
        cout << ans[ans.size()-1-i] << " ";
    }
    cout << ans[0] << endl;
    return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll A, B, T;
    cin >> A >> B >> T;
    ll ans = 0;
    ll i = 1;
    while(i++ * A <= T) ans += B;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
const lli INF = 1e9 + 100;
const lli INF64 = (1LL << 61) + 100;
const lli MOD = 1e9 + 7;
const lli MH1 = 1599614977, MH2 = 2034417103, MH3 = 1090250123, MH4 = 2024491871; 
lli bpow(lli baseee, lli exponenttt) {
	if(exponenttt < 0) return 0;
	lli res = 1;
	baseee %= MOD;
	while (exponenttt > 0) {
		if ((exponenttt & 1) == 1) res = (res*baseee) % MOD;
		baseee = (baseee*baseee) % MOD;
		exponenttt >>= 1;
	}
	return res;
}
lli multInverse(lli a) {//if_mod_is_prime
	return bpow(a, MOD - 2);
}
lli divm(lli a, lli b) {//if_mod_is_prime
	return (a * multInverse(b)) % MOD;
}
lli multm(lli a, lli b) {
	return (a * b) % MOD;
}
lli subm(lli a, lli b) {
	a += MOD;
	lli r = a - b;
	if(r >= MOD) return r - MOD;
	return r;
}
lli addm(lli a, lli b) {
	lli r = a + b;
	if(r >= MOD) return r - MOD;
	return r;
}
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	lli n, k;
	cin >> n >> k;
	n %= k;
	lli ans = n;
	for(int i = 1; i <= 10; i++) {
		n = abs(n - k);
		ans = min(ans, n);
	}
	cout << ans << "\n";
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  int index = 1;
  for (int i=0; i<n; i++) {
    int in;
    cin >> in;
    if(in == index){
      index++;
    }
  }
  if(index == 1){
    cout << -1 << endl;
    return 0;
  }
  int ans = n + 1 - index;
  cout << ans << endl;
}



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

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

    vector <int> v[n + 1];

    for (int i = 0; i < n; i++) {
        int x, no;
        cin >> x >> no;
        for(int j = 0; j < no; j++) {
            int temp;
            cin >> temp;
            v[x].push_back(temp);
        }
    }
	
//	for(int i=1;i<=n;i++){
//		for(int x:v[i]) cout<< x<< ' ';
//		cout<<endl;
//	}
//	cout<<endl;//deb
	
    for (int i = 1; i <= n; i++) {
        int pre = 1;

        for (int j = 0; j < v[i].size(); j++) {
            for (int k = pre ; k < v[i][j]; k++)
                cout << "0 ";
            
			cout << "1"<< ((v[i][j]==n)?'\n':' ');

            pre = v[i][j] + 1;
        }
        for (int j = pre; j <= n; j++)
            cout << "0" << ((j==n)?'\n':' ');
    }

} 


Measured memory_bytes: 3144
import java.util.Scanner;
 
 
public class Main {
     
 
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int m = stdIn.nextInt();
         
        int[][] A = new int[n][m];
        int[] B = new int[m];
        int[] C = new int[n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <  m; j++) {
                A[i][j] = stdIn.nextInt();
            }
        }
        for(int i = 0; i < m; i++) {
            B[i] = stdIn.nextInt();
        }
         
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                C[i] += A[i][j] * B[j];
            }
        }
         
        for(int i = 0; i < n; i++) {
            System.out.println(C[i]);
        }
    }
 
}


Measured memory_bytes: 40648
/*
* @Author Silviase(@silviasetitech)
* For ProCon
*/

import java.util.*;
import java.lang.*;
import java.math.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans;
        int var = 0;
        int[] card = new int[100001];
        int amari = 0;
        for (int i = 0; i < n; i++) {
            int tmp = sc.nextInt();
            card[tmp]++;
        }

        for (int i = 0; i <= 100000; i++) {
            if (card[i] >= 1) {
                var++;
            }
            if (card[i] >= 2) {
                amari += (card[i] - 1);
            }
        }

        if (amari % 2 == 0) {
            ans = var;
        }else{
            ans = var - 1;
        }
        System.out.println(ans);
        sc.close();
    }
}





Measured memory_bytes: 52424
def INT():
    return int(input())

def MI():
    return map(int, input().split())

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

N = INT()
A = LI()

for i in range(N):
    A[i] = [i + 1, A[i]]
    
A.sort(key = lambda x : x[1])

ans = []

for i in range(N):
    ans.append(A[i][0])
    
print(*ans)

Measured memory_bytes: 100860
<?php
fscanf(STDIN, "%d", $n);

$array = explode(' ', trim(fgets(STDIN)));

if (in_array(0, $array)) {
  echo 0;exit;
}

$prev = 1;
for ($i=0; $i < $n; $i++) {
  $ans = $prev * $array[$i];

  if ($prev != ($ans / $array[$i])) {
    echo -1;exit;
  }

  $prev = $ans;
}

if ($ans > pow(10, 18)) {
  echo -1;
} else {
  echo $ans;
}


Measured memory_bytes: 25468
from operator import truediv
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def make_divisors(n):
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

n = ni()
a = na()
g = [0]*1000000

for i in range(n):
    ii = list(set(make_divisors(a[i])))
    b = True
    for p in ii:
        if g[p] == 0:
            g[p] += 1
        else:
            b = False
            break
    if not b:
        break
else:
    print('pairwise coprime')
    exit()

import math

k = a[0]
for i in a:
    k = math.gcd(k,i)
    if k == 1:
        print('setwise coprime')
        exit()

print('not coprime')

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

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

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

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

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int n;
  cin>>n;
  vector<int> v(n);
  rep(i,n) cin>>v[i];
  if(n%2==0){
    for(int i=n/2;i>0;i--){
      cout<<v[2*i-1]<<' ';
    }
    for(int i=0;i<n/2;i++){
      cout<<v[2*i]<<' ';
    }
    cout<<endl;
    return 0;
  }else{
    for(int i=n/2;i>0;i--){
      cout<<v[2*i]<<' ';
    }
    cout<<v[0]<<' ';
    for(int i=0;i<n/2;i++){
      cout<<v[2*i+1]<<' ';
    }
    cout<<endl;
    return 0;
  }
  
}
///////////////////////////

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

int main() {
  int A, B;
  cin >> A >> B;
  if (A == 1) A += 13;
  if (B == 1) B += 13;

  if (A > B) {
    cout << "Alice" << endl;
  }
  else if (A < B) {
    cout << "Bob" << endl;
  }
  else {
    cout << "Draw" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int h[100005],k;
vector<int> mem(100005,-1);
int dp(int n);
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    cout<<dp(n)<<"\n";
    return 0;
}
int dp(int n){
    if(n==1){
        mem[1]=0;
        return 0;
    }
    if(n==2){
        mem[2]=abs(h[n-1]-h[n]);
        return abs(h[n-1]-h[n]);
    }
    if(mem[n]<0){
        int minv=1000000007;
        for(int i=1;i<=k&&n-i>0;i++){
            minv=min(minv,abs(h[n]-h[n-i])+dp(n-i));
        }
        mem[n]=minv;
    }
    return mem[n];
}

Measured memory_bytes: 11896
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;

struct Graph {
    struct Edge { int i, n; double t; };
    struct Vertex { int n; int k; double t; };
    Graph(int n, int m) : v(n, { -1, 0, 0 }), e(m), m(0) {}
    void add_edge(int i, int j) {
        e[m] = { j, v[i].n, 0.0 };
        v[i].n = m;
        m++;
    }
    double foo(int i, int p) {
        double t = 0.0;
        int k = 0;
        for (int j = v[i].n; j >= 0; j = e[j].n) {
            Edge& o = e[j];
            if (o.i == p) continue;
            o.t = foo(o.i, i) + 1;
            t += o.t;
            k++;
        }
        if (k == 0) return 0.0;
        v[i].t = t;
        v[i].k = k;
        return t / k;
    }
    void bar(int i, int p, double t) {
        if (p >= 0) {
            v[i].t += t + 1;
            v[i].k++;
        }
        int k = v[i].k - 1;
        for (int j = v[i].n; j >= 0; j = e[j].n) {
            Edge& o = e[j];
            if (o.i == p) continue;
            bar(o.i, i, k == 0 ? 0.0 : (v[i].t - o.t) / k);
        }
    }
    vector<Edge> e;
    vector<Vertex> v;
    int m;
};

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

    int n;
    cin >> n;
    Graph g(n, (n - 1) * 2);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g.add_edge(u, v);
        g.add_edge(v, u);
    }

    g.foo(0, -1);
    g.bar(0, -1, 0.0);
    for (int i = 0; i < n; i++) {
        cout << fixed << setprecision(9) << g.v[i].t / g.v[i].k << '\n';
    }

    return 0;
}

Measured memory_bytes: 12416
N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))


Measured memory_bytes: 90972
#include<iostream>
#include<stdio.h>
using namespace std;

int main() 
{
	int n,a[100];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		printf("%d", a[n - i]);
		if (i != n) printf(" ");
		else printf("\n");
	}
	return 0;
}

Measured memory_bytes: 3208
import heapq
t = 1
def max(a,b):
	if a > b:
		return a
	return b
def min(a,b):
	if a < b:
		return a
	return b

while t > 0:
	t -= 1
	# n,k = map(int,input().split())
	# n = int(input())
	s = input()
	r = input()
	ans = 0
	for i in range(0,len(s)):
		if(s[i] == r[i]):
			ans += 1
	print(ans)
	# v = list(map(int,input().strip().split()))[0:n]
	# b = list(map(int,input().strip().split()))[0:n]
	# c = list(map(int,input().strip().split()))[0:n-1]
	# s = input()
	# for i in range(n,0,-1):
	

Measured memory_bytes: 62292
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e18;

vector<int>accsum(vector<int>&v) {
	vector<int>ret(v.size());
	REP(i, v.size()) ret[i + 1] += ret[i] + v[i];
	return ret;
}

signed main(){
	int N, K;
	cin >> N >> K;
	vector<int>p(N), c(N);
	cin >> p >> c;
	REP(i, N) --p[i];
	auto f = [&](int start, int K) -> int {
		vector<int>v;
		vector<int>visit(N);
		{
			auto dfs = [&](auto&&f, int now) -> void {
				if(visit[now]++) {
					return;
				}
				v.emplace_back(now);
				f(f, p[now]);
			};
			dfs(dfs, start);
		}
		for(auto&&e: v) e = c[e];
		int sumLoop = accumulate(ALL(v), 0ll);
		int ret = -INF, acc = 0;
		REP(i, min(K, (int)v.size())) {
			acc += v[i];
			CHMAX(ret, acc);
		}
		if(K <= v.size()) return ret;
		acc = sumLoop * (K / v.size());
		REP(i, K % v.size()) {
			acc += v[i];
		}
		CHMAX(ret, acc);
		int now = K % v.size();
		REP(i, v.size()) {
			now = (now - 1 + v.size()) % v.size();
			acc -= v[now];
			CHMAX(ret, acc);
		}
		return ret;
	};
	int ans = -INF;
	REP(i, N) {
		int t = f(p[i], K);
		CHMAX(ans, t);
	}
	out(ans);
}

Measured memory_bytes: 4088