akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#define mp make_pair
#define FOR(i, a, b) for (int(i) = a; (i) <= (b); ++(i))
#define rep(i, n) FOR(i, 0, n-1 )
#define FFOR(i, a, b) for (int(i) = a; (i) > (b); --(i))
#define rrep(i, n) FFOR(i, 0, n)
#define vsort(v) sort((v).begin(), (v).end());           //小さい順
#define rvsort(v) sort(v.begin(), v.end(), greater<>()); //大きい順
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define all(c) (c).begin(), (c).end()
#define ll long long
#define lb long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout << (p) << endl
#define F first
#define S second
#define pb push_back
#define mod 1000000007LL
#define INF 123456789012345
#define int ll
typedef pair<int, int> P;
typedef pair<int, P> PP;

const int maxn = 1e5 + 10;
int a[maxn];
map<int,int> mp;

signed main() {

  int n;cin>>n;
  if(!n)
  {
    cout << 0 << endl;
    return 0;
  }
  int ue = 1,shita = 0,keta =0,value = 1;
  while(!(ue > n && n > shita))
  {
    keta++;
    value *= -2;
    if(value > 0) ue += value;
    else shita += value;
  }
  
  string ans = "";

  while(keta>-1)
  {
    if(value>0)ue-=value;
    else shita -= value;

    if(!(ue>=n&&n>=shita))
    {
      ans += "1";
      n -= value;
    }
    else ans +="0";

    value /= -2;
    keta--;
  }

  cout << ans << endl;
 
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l;
    cin >> n >> l;
    vector<string> s(n);
    REP(i,n) cin >> s[i];
    sort(ALL(s));
    string ans = "";
    REP(i,n){
        ans += s[i];
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
int main() {
  int N, K;
  ll S;
  cin >> N >> K >> S;
  if(2*K >= N) {
    rep(i, N-K) cout << S << ' ' << ((S+1==1e+9+1)?1:S+1) << ' ';
    rep(i, 2*K-N) cout << S << ' ';
    cout << endl;
  } else {
    rep(i, K) cout << S << ' ' << ((S+1==1e+9+1)?1:S+1) << ' ';
    rep(i, N-2*K) cout << ((S+1==1e+9+1)?1:S+1) << ' ';
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 1280
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <string>
#include <vector>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
const int ININF = 1000000;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int A, B;
    cin >> A >> B;
    string res[100];
    rep(i, 0, 50) {
        rep(j, 0, 100) { res[i] += '#'; }
    }
    rep(i, 50, 100) {
        rep(j, 0, 100) { res[i] += '.'; }
    }
    int shiro = A - 1;
    rep(i, 2, 50) {
        rep(j, 0, 100) {
            if(shiro > 0 && i % 2 == 0 && j % 2 == 0) {
                res[i][j] = '.';
                shiro--;
            }
        }
    }
    int kuro = B - 1;
    rep(i, 52, 100) {
        rep(j, 0, 100) {
            if(kuro > 0 && i % 2 == 0 && j % 2 == 0) {
                res[i][j] = '#';
                kuro--;
            }
        }
    }
    cout << "100 100" << endl;
    rep(i, 0, 100) {
        rep(j, 0, 100) { cout << res[i][j]; }
        cout << endl;
    }
}


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

std::array<int, 100> d;

int main() {
    int n, yen;
    int ret = 0;
    std::cin >> n >> yen;
    for(int x = yen / 10000; x >= 0; -- x) {
        int xYen = x * 10000;
        for(int y = (yen - xYen) / 5000; y >= 0; -- y) {
            int z = n - x - y;
            int xyzYen = xYen + y * 5000 + z * 1000;
            if (xyzYen == yen) {
                std::cout << x << " " << y << " " << z;
                std::exit(0);
            }
        }
    }
    std::cout << "-1 -1 -1";
    return 0;
}


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

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef double db;
typedef complex<db> cd;

ll qpow(ll x,ll k,ll mod)
{
    ll ret=1;
	while(k)
	{
	   if(k&1)	
	   {
	   	 ret=ret*x;
	   	 ret=ret%mod;
	   }
	   x=x*x;
	   x=x%mod;
	   k=(k>>1);
	}
	return ret;	
}
#define MP make_pair
#define FF first
#define SS second
#define LB lower_bound
#define UB upper_bound
#define PB push_back
#define lc ((p<<1)+1)
#define rc ((p<<1)+2)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define all(v) (v).begin(),(v).end()
#define clean(v,a) memset(v,a,sizeof(v))
#define PQ priority_queue

/*
 * high precision: printf("%.12lf",(db)ans);
 *
 * clear output buffer: fflush(stdout);
 *
 * sync off: ios::sync_with_stdio(false);
 *
 */

const int Maxn=4005;
const int md=998244353;

ll c[Maxn][Maxn];
ll ans[Maxn];
ll pw[Maxn];
int n,k;

void init()
{
	clean(c,-1);
	pw[0]=1;
	for(int i=1;i<Maxn;i++) pw[i]=(pw[i-1]<<1)%md;
}

ll comb(int x,int y)
{
	if(y<0||x<0) return 0;
	if(y>x) return c[x][y]=0;
	if(c[x][y]!=-1) return c[x][y];
	if(y==0) return c[x][y]=1;
	return c[x][y]=(comb(x-1,y)+comb(x-1,y-1))%md;
}

int main()
{
	init();
	scanf("%d%d",&k,&n);
	for(int i=2;i<=k;i+=2)
	{
		for(int j=0;j<=(i>>1);j++)
		{
			ans[i]=(ans[i]+pw[j]*comb(i>>1,j)%md*comb(n+k-i-1,k-i-1+j))%md;
		}
		ans[i-1]=ans[i];
	}
	if(k&1)
	{
		for(int j=0;j<=(k>>1);j++)
		{
			ans[k]=(ans[k]+pw[j]*comb(k>>1,j)%md*(comb(n-1,j-1)+comb(n-2,j-1)))%md;
		}
	}
	for(int i=1;i<k;i++)
	{
		ans[k+i]=ans[k-i];
	}
	for(int i=1;i<(k<<1);i++) printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 125824
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int n, p[50];

int main() {
	cin >> n;
	inc(i, n) { cin >> p[i]; }
	
	int c = 0;
	inc(i, n) { if(p[i] != i + 1) { c++; } }
	
	cout << (c <= 2 ? "YES" : "NO") << endl;
	
	return 0;
}


Measured memory_bytes: 256
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Math;
using System;

public class hello
{
    public static Dictionary<int, int> dic, dic2;
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var q = int.Parse(line[1]);
        var s = Console.ReadLine().Trim();
        dic = getDiv(n);
        var c = new int[dic.Count() + 1, n, 26];
        dic2 = new Dictionary<int, int>();
        foreach (var x in dic) dic2[x.Value] = x.Key;
        var m = new int[dic.Count() + 1];
        foreach (var x in dic)
            getC(c, m, n, s, x.Value);
        var s2 = s.ToCharArray();
        var sb = new StringBuilder();
        for (int i = 0; i < q; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            var p = int.Parse(line[0]) - 1;
            var c0 = s2[p];
            var c1 = line[1][0];
            s2[p] = c1;
            change(c, m, n, p, c0, c1);
            var ans = checkM(m, n);
            sb.Append(ans.ToString());
            sb.Append("\n");
        }
        Console.Write(sb);
    }
    static int checkM(int[] m, int n)
    {
        var res = n;
        for (int i = 0; i < dic.Count(); i++)
            if (dic[i] * m[i] == n) res = Min(res, m[i]);
        return res;
    }
    static void change(int[,,] c, int[] m, int n, int p, char c0, char c1)
    {
        var pre = c0 - 'a';
        var now = c1 - 'a';
        foreach (var x in dic2)
        {
            var sL = n / x.Key;
            var np = p % sL;

            if (x.Key == c[x.Value, np, pre]) m[x.Value]--;
            c[x.Value, np, pre]--;
            c[x.Value, np, now]++;
            if (x.Key == c[x.Value, np, now]) m[x.Value]++;
        }
    }
    static void getC(int[,,] c, int[] m, int n, string s, int t)
    {
        var jmax = n / t;
        for (int i = 0; i < t; i++)
        {
            var b = i * jmax;
            for (int j = 0; j < jmax; j++)
            {
                var w = s[b + j] - 'a';
                var nt = dic2[t];
                c[nt, j, w]++;
                if (c[nt, j, w] == t) m[nt]++;
            }
        }
    }
    static Dictionary<int, int> getDiv(int n)
    {
        var d = new Dictionary<int, int>();
        var p = 0;
        for (int i = 1; i <= Sqrt(n); i++)
        {
            if (n % i == 0)
            {
                d[p++] = i;
                if (n != i * i) d[p++] = n / i;
            }
        }
        return d;
    }
}



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

int main(){
	int h, w;
	while(true) {
		scanf("%d%d", &h, &w);
		if(h == 0 && w == 0) break;
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				if(i == 0 || i == h-1 || j == 0 || j == w-1)
					printf("#");
				else
					printf(".");
			}
			printf("\n");
		}
		printf("\n");
	}
}



Measured memory_bytes: 3088
n=int(input())
a=[]
for _ in range(n):
  a.append(int(input()))
i=0
c=0
ans=0
while i<=n-1:
  if a[i]==0:
    ans+=c//2
    i=i+1
    c=0
  else:
    c+=a[i]
    i=i+1
ans+=c//2
print(ans)
    

Measured memory_bytes: 7072
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>
#include <limits>
#include <map>
#include <set>
#include <functional>

using namespace std;

int main()
{
  int H, W, K;
  vector<vector<string>> grid;

  cin >> H >> W >> K;
  grid.resize(H, vector<string>(W, "."));
  for (int h = 0; h < H; h++) {
    string temp;
    cin >> temp;
    for (int w = 0; w < W; w++) {
      grid[h][w] = temp[w];
    }
  }

  int result = 0;
  int h_red_flag = 0;
  int w_red_flag = 0;

  while (true) {
    int black_cell_num = 0;
    for (int h = 0; h < H; h++) {
      for (int w = 0; w < W; w++) {
        if (grid[h][w] == "#" &&
            (h_red_flag >> h & 1) == 0 &&
            (w_red_flag >> w & 1) == 0) {
          black_cell_num++;
        }
      }
    }

    if (black_cell_num == K) {
      result++;
    }

    if (w_red_flag != pow(2, W) - 1) {
      w_red_flag++;
    }
    else if (h_red_flag != pow(2, H) - 1) {
      w_red_flag = 0;
      h_red_flag++;
    }
    else {
      break;
    }
  }

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 4100
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string yn(bool x){
    return x ? "YES" : "NO";
}

int main(){
    int x; cin >> x;
    bool ans = 0;
    if(x == 3 or x == 5 or x==7)ans = true;
    cout << yn(ans) << endl;
}









Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;
typedef unsigned long long int ull;


int main()
{
	FAST;
	int a,b,c,x;
	cin >> a >> b >> c >> x;
	int ans = 0;
	for(int i=0 ; i<=a ; i++)
	{
		for(int j=0 ; j<=b ; j++)
		{
			for(int k=0 ; k<=c ; k++)
			{
				if( (500*i) + (100*j) + (50*k) == x)
					ans++;
		
			}
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 256
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<int,int>
 
#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 500005;

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
     ll n;
     cin >> n;
     ll ans = 0;
     ans = n/500;
     ans = ans * 1000;
     n = n%500;
     ans += ((n/5)*5);
     cout<<ans;
}

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

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

using namespace std;

struct St{
  int x;
  int y;
  int sp;
};

int ydir[12] = {-1, 0, 1, -2, 2, -2, 2, -2, 2, -1, 0, 1};
int xdir[12] = {-2, -2, -2, -1, -1, 0, 0, 1, 1, 2, 2, 2};

bool bfs(bool a[11][11][11], St py, int n)
{
  bool f = false;
  queue<St> que;
  que.push(py);
  St s, t;

  while(!que.empty()){
    s = que.front();
    que.pop();
    if(s.sp == n){
      f = true;
      break;
    }
    t.sp = s.sp+1;
    for(int i = 0; i < 12; i++){
      t.y = s.y + ydir[i];
      t.x = s.x + xdir[i];

      if(0 <= t.x && t.x <= 9 && 0 <= t.y && t.y <= 9 && a[t.x][t.y][t.sp]){
	que.push(t);
	a[t.x][t.y][t.sp] = false;
      }
    }
  }

  return f;
}

int main()
{
  int n, s, t;
  St py;
  bool a[11][11][11];

  while(cin>>py.x>>py.y && (py.x+py.y)){
    cin >> n;
    py.sp = 0;
    fill(&a[0][0][0], &a[10][10][10], false);
    for(int i = 1; i <= n; i++){
      cin >> s >> t;
      for(int j = -1; j < 2; j++){
	for(int k = -1; k < 2; k++){
	  int dx = s+j, dy = t+k;
	  if(0 <= dx && dx <= 9 && 0 <= dy && dy <= 9){
	    a[dx][dy][i] = true;
	  }
	}
      }
    }

    cout << ((bfs(a, py, n))? "OK" : "NA") << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s,c;
cin>>s;
if(s!="abc"&& s!="acb"&& s!="bac" && s!="bca" && s!="cab" && s!="cba")
cout<<"No";
else
cout<<"Yes";
return 0;
}

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

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

fn main() {
    let a: u32 = read();
    let b: u32 = read();
    let c: u32 = read();
    let d: u32 = read();

    let left: u32 = a + b;
    let right: u32 = c + d;

    if left > right {
        println!("Left");
    } else if left < right {
        println!("Right");
    } else {
        println!("Balanced");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

struct BIT {
    ll n;
    VL dat;
    void init(ll n_input) {
        n = n_input + 1;
        dat.resize(n + 1);
        for (int i = 0; i <= n; i++) dat[i] = 0;
    }
    ll sum(ll i) {
        ll s = 0;
        while (i >= 0) {
            s += dat[i];
            i = (i & (i + 1)) - 1;
        }
        return s;
    }
    void add(ll i, ll x) {
        while (i <= n) {
            dat[i] += x;
            i |= i + 1;
        }
    }
};

int main() {
    ll n;
    cin >> n;
    VL a(n), sorted(n);
    FOR(i, 0, n) {
        scanf("%d", &a[i]);
        sorted[i] = a[i];
    }
    sort(sorted.begin(), sorted.end());
    int ok = 0, ng = n;
    BIT bit;

    ll border = ((n * (n + 1) / 2) + 1) / 2;
    while (ng - ok > 1) {
        int mid = (ng + ok) / 2;
        int midnum = sorted[mid];
        bit.init(2 * n + 1);
        int sum = 0;
        bit.add(sum + n, 1);
        ll result = 0;
        FOR(i, 0, n) {
            sum += (a[i] >= midnum ? 1 : -1);
            result += bit.sum(sum + n);
            bit.add(sum + n, 1);
        }
        if (result >= border)ok = mid;
        else ng = mid;
    }
    cout << sorted[ok] << endl;
}


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

int b[2002][2002];
int w[2002][2002];

int s[2002][2002];

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int x, y;
        char c;
        cin >> x >> y >> c;
        x %= k * 2; y %= k * 2;
        if(c == 'B') b[x][y]++;
        else w[x][y]++;
    }
    for(int j = 0; j < k * 2; j++){
        for(int i = 0; i < k; i++) s[0][j] += w[i][j];
        for(int i = k; i < k * 2; i++) s[0][j] += b[i][j];
        for(int i = 1; i < k * 2; i++)
            s[i][j] = s[i - 1][j] + w[(i + k - 1) % (k * 2)][j] - b[(i + k - 1) % (k * 2)][j] +
                                    b[i - 1][j] - w[i - 1][j];
    }
    int ans = 0;
    for(int i = 0; i < k * 2; i++){
        int t = 0;
        for(int j = 0; j < k; j++) t += s[i][j];
        for(int j = k; j < k * 2; j++) t += s[(i + k) % (k * 2)][j];
        ans = max(ans, t);
        for(int j = 1; j < k * 2; j++){
            t += s[i][(j + k - 1) % (k * 2)] - s[(i + k) % (k * 2)][(j + k - 1) % (k * 2)] +
                 s[(i + k) % (k * 2)][j - 1] - s[i][j - 1];
            ans = max(ans, t);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 50548
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const double PI = 3.14159265358979;
static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;

ll a[200001] = {};
ll s[200001] = {};
map<ll, ll> mp;
int main() {
	ll n; cin >> n;

	repe(i, 1, n) {
		cin >> a[i];
	}
	repe(i, 1, n) {
		s[i] = a[i] + s[i - 1];
	}
	repe(i, 0, n) {
		mp[s[i]] ++;
	}
	ll ans = 0;
	for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); it++) {
		if (it->second >= 2) {
			ans += (it->second*(it->second - 1) / 2);
		}
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

int is_prime(int n){
    if(n < 2){
        return 0;
    }else if(n == 2){
        return 1;
    }
    if(n%2 == 0){
        return 0;
    }

    for(int i = 3; i<=sqrt(n); i+=2){
        if(n%i == 0){
            return 0;
        }
    }
    return 1;
}


const int N =100010;
vector<int> p(N);
void solve() {
    int Q;
    cin >> Q;
    for (int i = 1; i < N; i++)
    {
        if (i % 2 == 0)
        {
            p[i] = p[i-1];
            continue;
        }
        
        if (is_prime(i) && is_prime((i + 1) / 2))
        {
            p[i] = p[i-1] + 1;
        }
        else
        {
            p[i] = p[i-1];
        }
    }

    for (int i = 0; i < Q; i++)
    {
        int l, r;
        cin >> l >>  r;
        cout << p[r] - p[l-1] << endl;
    }
    
}

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

Measured memory_bytes: 3736
import itertools
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
r,c = 0,0
for i in itertools.permutations(a):
    for j in range(n-1):
        r += ((i[j][0]-i[j+1][0])**2+(i[j][1]-i[j+1][1])**2)**0.5
    c += 1
print(r/c)

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

int main(void) {
  long long A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  long long ans = LONG_LONG_MAX;
  for (int i = 0; i < 1e5 + 1; i++) {
    ans = min(C * i * 2 + A * max(0LL, X - i) + B * max(0LL, Y - i), ans);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define fo(i,n) for(i=0;i<n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define MAXN 1000002
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod=1e9+7;

void solve()
{
  int n;
  set<string> V;
  cin>>n;
  string str;
  for(int i=0;i<n;i++)
  {
    cin>>str;
    V.insert(str);
  }
  cout<<V.size();
}

int main()
{
  fastio
  solve();
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
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;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------
//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  ll n, m;
  cin >> n >> m;
  vll v(n+1), w(n+1);
  REP(i,n) cin >> v[i+1] >> w[i+1];

  vvll dp(n+1,vll(m+1,0));

  for(ll i = 1; i <= n; i++){
    for(ll j = 0; j <= m; j++){
      if(j - w[i] < 0) dp[i][j] = dp[i-1][j];
      else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
    }
  }

  cout << dp[n][m] <<endl;

  return 0;
}




Measured memory_bytes: 10812
def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= x**(1/2):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

x = int(input())
for i in range(x,10**6+1):
    if is_prime(i):
        print(i)
        exit()
    else:
        pass


Measured memory_bytes: 38384
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main()
{
    double x1;
    double x2;
    double y1;
    double y2;
    double x;
    double y;
    double dis;    //距離

    cin >> x1 >> y1 >> x2 >> y2;
    x = x1 - x2;
    y = y1 - y2;
    x = pow(x, 2);
    y = pow(y, 2);
    dis = x + y;
    dis = sqrt(dis);

    cout << fixed << setprecision(8) << dis << endl;

    return 0;
}


Measured memory_bytes: 3284
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define dup(x,y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
#define diup(v,a) distance((v).begin(),upper_bound((v).begin(),(v).end(),(a)))
#define dilo(v,a) distance((v).begin(),lower_bound((v).begin(),(v).end(),(a)))
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(v.size())o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const double eps = 1e-6;
const ll LINF = 100200300400500600ll;
const int INF = 1001001001;
//--------------------------------------------------------
#define fastio cin.tie(nullptr); std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
#define myloopset int loop = 1; if(argc>2) loop =stoi(argv[2]); rep(i,loop)
//--------------------------------------------------------------
template <class T> T chmin(T &a,T b){if(a>b){a=b; return 1;}else return 0;}
template <class T> T chmax(T &a,T b){if(a<b){a=b; return 1;}else return 0;}
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};
#define MOD 1000000007

struct D21{
  int is,js;
  D21(int isize,int jsize){
    is = isize;
    js = jsize;
  }
  int operator()(int i,int j){
    return i*js+j;
  }
};


void Main(){
  int n;
  cin>>n;
  vi h(n);
  cin>>h;
  h.pb(0);
  h.pb(0);
  vi dp(n+2,INF);
  dp[0] = 0;
  rep(i,n){
    chmin(dp[i+1], dp[i]+abs(h[i+1]-h[i]));
    chmin(dp[i+2], dp[i]+abs(h[i+2]-h[i]));
  }

  cout<<dp[n-1]<<endl;
} signed main(int argc,char** argv)
{fastio; myio; myloopset Main();}


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

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;

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

    int a,b;
    cin >> a >> b;
    int cnt = a, sol = 1;
    if(b==1)
        cout << 0;
    else{
        while(cnt<b){
            cnt+=(a-1);
            sol++;
        }
        cout << sol;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define sc second
#define mp make_pair
pair<int,int> dp[105][100005];
int n,p[105];
void chh(pair<int,int> &a,pair<int,int> &b){
	if(a.fi < b.fi) a = b;
	else if(a.fi == b.fi) a.sc = min(a.sc,b.sc);
}
int main(){
	while(1){
		cin>>n; if(!n) return 0;
		for(int i=1;i<=n;i++) cin>>p[i];
		for(int i=0;i<105;i++) for(int j=0;j<100005;j++) dp[i][j] = mp(-10000,100000000);
		dp[0][0] = mp(0,0);
		for(int i=0;i<n;i++){
			for(int j=0;j<=1000*i;j++){
				if(dp[i][j].fi < 0) continue; //cout <<i << " " <<j<< endl;
				if(dp[i+1][j].fi < dp[i][j].fi) dp[i+1][j] = dp[i][j];
				else if(dp[i+1][j].fi == dp[i][j].fi) dp[i+1][j].sc = min(dp[i+1][j].sc,dp[i][j].sc);
				
				if(p[i+1]%1000 == 0){
					if(j>=500){
						pair<int,int> Q=mp(dp[i][j].fi+1,dp[i][j].sc+p[i+1]) ;
						chh(dp[i+1][j-500],Q);
					}
				}
				else if(p[i+1]%1000 <= 500){
					pair<int,int> Q=mp(dp[i][j].fi+1,dp[i][j].sc+p[i+1]) ;
					chh(dp[i+1][j+500-(p[i+1]%1000)],Q);
				}
				else{
					if(j+500-(p[i+1]%1000)>=0){
						pair<int,int> Q=mp(dp[i][j].fi+1,dp[i][j].sc+p[i+1]) ;
						chh(dp[i+1][j+500-(p[i+1]%1000)],Q);
					}
					pair<int,int> Q=mp(dp[i][j].fi,dp[i][j].sc+p[i+1]) ;
					chh(dp[i+1][j+1000-(p[i+1]%1000)],Q);
				}
			}
		}
		pair<int,int> ans = mp(-10000,100000000);
		for(int i=0;i<=n;i++){
		for(int j=0;j<100005;j++){
			if(ans.fi < dp[i][j].fi) ans = dp[i][j];
			else if(ans.fi == dp[i][j].fi) ans.sc = min(ans.sc,dp[i][j].sc);
		}}
		cout <<ans.fi<<" " << ans.sc << endl;
	}
}

Measured memory_bytes: 85112
#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
LL i,j,k,m=998244353,n,p=1,q,x,y,a[525000],l[525000],r[525000],z[525000],w[200040];
LL sum(int x,int y,int d)
{
	if(z[d])
	{
		a[d]=z[d]*(w[l[d]]-w[r[d]+1]+m)%m;
		if(l[d]<r[d])
		{
			z[d<<1]=z[d];
			z[(d<<1)+1]=z[d];
		}
		z[d]=0;
	}
	if(x<=l[d]&&r[d]<=y)return a[d];
	if(x>r[d]||y<l[d])return 0;
	return (sum(x,y,d<<1)+sum(x,y,(d<<1)+1))%m;
}
void REP(int x,int y,int d,LL k)
{
	if(z[d])
	{
		a[d]=z[d]*(w[l[d]]-w[r[d]+1]+m)%m;
		if(l[d]<r[d])
		{
			z[d<<1]=z[d];
			z[(d<<1)+1]=z[d];
		}
		z[d]=0;
	}
	if(x<=l[d]&&r[d]<=y)
	{
		a[d]=k*(w[l[d]]-w[r[d]+1]+m)%m;
		if(l[d]<r[d])
		{
			z[d<<1]=k;
			z[(d<<1)+1]=k;
		}
		return;
	}
	if(x>r[d]||y<l[d])return;
	REP(x,y,d<<1,k);
	REP(x,y,(d<<1)+1,k);
	a[d]=a[d<<1]+a[(d<<1)+1];
}
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(cin>>n>>q;p<=n;)p<<=1;
	for(w[i=n]=1;--i;)w[i]=w[i+1]*10%m;
	for(i=0;i++<n;)
	{
		a[p+i]=w[i];
		l[p+i]=r[p+i]=i;
	}
	for(;i<p;i++)l[p+i]=r[p+i]=i;
	for(i=n;--i;)w[i]=(w[i]+w[i+1])%m;
	for(i=p;--i;)
	{
		a[i]=a[i<<1]+a[(i<<1)+1];
		l[i]=l[i<<1];
		r[i]=r[(i<<1)+1];
	}
	for(;q--;)
	{
		cin>>x>>y>>k;
		REP(x,y,1,k);
		cout<<sum(1,n,1)<<endl;
	}
}

Measured memory_bytes: 20164
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

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

		while (in.hasNext()) {
			int N = in.nextInt();
			ArrayList<Integer> lmds = new ArrayList<Integer>();

			for (int i = 0; i < N; ++i) {
				int a = in.nextInt();

				int idx = upperBound(lmds, a, Collections.reverseOrder());
				idx = Math.max(idx, -(idx + 1));

				if (idx >= lmds.size()) {
					lmds.add(a);
				} else {
					if (lmds.get(idx) == a && lmds.get(lmds.size() - 1) == a) {
						lmds.add(idx, a);
					} else {
						lmds.set(idx, a);
					}
				}

			}

			System.out.println(lmds.size());
		}
	}

	private static <T> int upperBound(List<? extends T> list, T key, Comparator<? super T> c) {
		int fromIdx = 0;
		int toIdx = list.size();

		while (fromIdx < toIdx) {
			int mid = fromIdx + (toIdx - fromIdx) / 2;

			if (c.compare(key, list.get(mid)) < 0) {
				toIdx = mid;
			} else {
				fromIdx = mid + 1;
			}
		}

		if (0 <= fromIdx && fromIdx < list.size()) {
			return fromIdx;
		} else {
			return -fromIdx - 1;
		}
	}
}


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

#define in cin
#define out cout

#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)
#define REPE(i,s,e) for(int i=s; i<=e; i++)
#define REPR(i,s,e) for(int i=s; i>=e; i--)

#define all(v) v.begin(), v.end()
#define pb push_back

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rd(n) scanf("%d", &n)

#define x first
#define y second
#define intINF 2147483647
#define llINF 9223372036854775807LL
#define MOD 1000000007

int main()
{
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    int n; in >> n;
    ll A[101010], B[101010];
    REP(i, n) in >> A[i] >> B[i];

    ll res = 0LL;
    ll t = 0LL;
    REPR(i,n-1,0)
    {
        A[i] += t;
        A[i] %= B[i];
        if(A[i])
        {
            t += B[i]-A[i];
            res += B[i]-A[i];
        }
    }

    out << res << endl;

    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int F[101][10];
int P[101][11];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		FOR(j,10) cin>>F[i][j];
	}
	FOR(i,N) {
		FOR(j,11) cin>>P[i][j];
	}
	
	ll ma=-1LL<<60;
	for(int mask=1;mask<1<<10;mask++) {
		ll ret=0;
		int cnt[101]={};
		
		FOR(i,N) {
			x=0;
			FOR(j,10) if((mask&(1<<j)) && F[i][j]) x++;
			ret+=P[i][x];
		}
		
		ma=max(ma,ret);
	}
	cout<<ma<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
class InputLine
  def self.to_s
    gets.chomp
  end

  def self.to_i
    InputLine.to_s.to_i
  end
  
  def self.to_f
    InputLine.to_s.to_f
  end

  def self.to_sa
    InputLine.to_s.split(' ')
  end

  def self.to_ia
    InputLine.to_sa.map(&:to_i)
  end
  
  def self.to_fa
    InputLine.to_sa.map(&:to_f)
  end
end

def main(argv)
  k = InputLine.to_i
  s = InputLine.to_s

  if s.size <= k then
    puts s
  else
    puts (s[0...k] + '...')
  end
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 14312
local memo={}
local function rec(x)
    if x==0 then 
        return 0 
    end
    if memo[x]~=-1 then
        return memo[x]
    end
    local result=x
    local six=1
    while six<=x do
        result=math.min(result,rec(x-six)+1)
        six=six*6
    end
    local nine=1
    while nine<=x do
        result=math.min(result,rec(x-nine)+1)
        nine=nine*9
    end
    memo[x]=result
    return memo[x]
end

local n=io.read("n")
for i=1,n do
    memo[i]=-1
end
print(rec(n))

Measured memory_bytes: 21772
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"
#define P           pair<int, int>
#define dint        long double

const int mod = 998244353;

inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }

int modpow(int a, int b) {
    if(a == 0 || a == 1 || b == 1) return a;
    int ans = 1;
    while(b) {
        if(b%2) ans = mul(ans, a);    
        b /= 2; a = mul(a, a);
    }   return ans;
}

void solve() {
    int n; cin >> n;
    map<int, int> cnt;
    for(int i=0; i<n-1; i++) {
        int x; cin >> x;
        cnt[x]++;
    }
    for(int i=1; i<=n; i++) {
        cout << cnt[i] << "\n";
    } 
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;

}



Measured memory_bytes: 16148
n=int(input())
s=list(map(int,input().split()))
t=[]
var=0
over=0
for i in s:
    if i//400 >= 8:
        over+=1
    elif i//400 in t:
        pass
    else:
        var+=1
        t.append(i//400)

if len(t)==0:
    print(1,over)
else:
    print(len(t),len(t)+over)

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

int main() {
  int a, b;
  scanf("%d %d", &a, &b);
  printf("%d\n", (int)std::ceil(((double)(b - 1)) / (a - 1)));
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;  
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define pii pair<int,int>
#define piii pair<int,pii>
#define mp make_pair
#define pb push_back  
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second  
const int INF = (INT_MAX/2);
const double eps = 1e-14;
const double PI = M_PI;  
#define DEB cout<<"!"<<endl
#define SHOW(a,b) cout<<(a)<<" "<<(b)<<endl  
#define DIV 1000000007

int main(){
	map<int,int> table;
	int N; cin >> N;
	REP(i,N){
		int A; cin >> A;
		table[A]++;
	}
	cout << (table.size() % 2? table.size() : table.size() - 1) << endl;
	return 0;
}

Measured memory_bytes: 4864
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF (1LL<<60)
#define MOD 1000000007

struct BIT {
  int n;
  vector<int> xs;
  BIT (int n) : n(n) {
    xs.resize(n+1);
  }
  void add(int i, int v) {
    for (int x=i+1; x<=n; x+=x&-x) {
      xs[x] += v;
      if (xs[x] >= MOD) xs[x] -= MOD;
    }
  }
  int sum(int i) {
    int s = 0;
    for (int x=i+1; x>0; x-=x&-x) {
      s += xs[x];
      if (s >= MOD) s -= MOD;
    }
    return s;
  }

  int sum(int l, int r) {
    if (l > r) return 0;
    return (0LL + sum(r) - sum(l-1) + MOD) % MOD;
  }
};

long long N, A, B;
long long S[100001];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> A >> B;
  S[0] = -INF;
  rep(i, N) cin >> S[i+1];

  BIT dp0(N+1), dp1(N+1);
  dp0.add(0, 1);
  //dp1.add(0, 1);

  int lower0 = 0, lower1 = 0;
  int ska = 0, skb = 0;
  for (int i=1; i<=N; i++) {
    while (ska < i && S[ska] <= S[i]-A) ska++;
    while (skb < i && S[skb] <= S[i]-B) skb++;
    int add1 = dp0.sum(lower0, ska-1), add2 = dp1.sum(lower1, skb-1);
    if (S[i]-S[i-1] < A) lower1 = i-1;
    if (S[i]-S[i-1] < B) lower0 = i-1;
    dp1.add(i-1, add1);
    dp0.add(i-1, add2);
  }
  int s = dp0.sum(lower0, N) + dp1.sum(lower1, N);
  if (s >= MOD) s -= MOD;
  cout << s << "\n";
  return 0;
}


Measured memory_bytes: 1792
//
// Created by rajshah9914 on 13/04/20.
//

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,ll> pp;
vector<ll>visited(200000,0);
vector<ll>adj[200000];
ll prime[2000000];
ll M=1000000007;
void boost() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void sieve(ll ending)
{
    for(ll i=2;i<ending;i++)
        prime[i]=1;
    for(int i=2;i*i<=ending;i++)
    {
        if(prime[i]==1)
        {
            for(int j=2*i;j<=ending;j=j+i)
            {
                prime[j]=0;
            }
        }
    }
    prime[1]=0;
}

ll ncrmodp(ll num,ll r)
{
    ll C[r+1];
    ll i,j;
    memset(C,0,sizeof(C));
    C[0]=1;
    for(i=1;i<=num;i++)
    {
        for(j=min(i,r);j>0;j--)
        {
            C[j]=((C[j])%M+(C[j-1])%M)%M;
        }
    }
    return C[r];
}

ll power(ll x,ll y)
{
    ll res = 1;
    x = x % M;

    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % M;

        y = y>>1; // y = y/2
        x = (x*x) % M;
    }
    return res;
}

void add_self(int& a,int b )
{
    a+=b;
    if(a>=M)
    a-=M;
    // return a;
}

void sub_self(int& a,int b )
{
    a-=b;
    if(a<0)
    a+=M;
}

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>dp(k+1);
    dp[0]=1;
    for(int child=0;child<n;child++)
    {
        int m;
        cin>>m;
        vector<int>f(k+1);
        for(int used=k;used>=0;used--)
        {
            int temp=dp[used];
            int L=used+1;
            int R=used+min(k-used,m);
            if(L<=R)
            {
                add_self(f[L],temp);
                if(R+1<=k)
                sub_self(f[R+1],temp);
            }
        }
        int pr=0;
        for(int i=0;i<=k;i++)
        {
            add_self(pr,f[i]);
            // cout<<pr<<endl;
            add_self(dp[i],pr);
        }
    }  
    cout<<dp[k]<<endl;
}

int main()
{
    boost();
    // int t;
    // cin>>t;
    // while(t--)
        solve();
}

Measured memory_bytes: 8576
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;

int main(){

    ll n, k;
    cin >> n >> k;

    ll ans = k;
    for(int i = 1; i < n; i++){
        ans *= (k-1);
    }    
    cout << ans << endl;
}

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

int main() {
  int n; cin >> n;
  int even = 0;
  int odd = 0;

  for(int i = 0; i < n; i++) {
    int a; cin >> a;
    if(a % 2 == 0) even++;
    else odd++;
  }

  if(even == 0 or odd == 0) cout << 0 << endl;
  else if(odd % 2 == 0) cout << n - 2 << endl;
  else cout << n - 1 << endl;
  return 0;
}



Measured memory_bytes: 3092
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.D_Challenge
{
    class ABC_081
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            long[] array = ReadLongs();
            int absMaxIndex = 0;
            for(int i = 1; i < n; i++)
            {
                if (Math.Abs(array[absMaxIndex]) < Math.Abs(array[i]))
                {
                    absMaxIndex = i;
                }
            }
            var handles = new List<int[]>();
            for(int i = 0; i < n; i++)
            {
                if (array[i] * array[absMaxIndex] < 0)
                {
                    handles.Add(new int[2] { absMaxIndex + 1, i + 1 });
                    array[i] += array[absMaxIndex];
                }
            }
            if (array[absMaxIndex] > 0)
            {
                for (int i = 1; i < n; i++)
                {
                    if (array[i] - array[i - 1] < 0)
                    {
                        handles.Add(new int[2] { i, i + 1 });
                        array[i] += array[i - 1];
                    }
                }
            }
            else if (array[absMaxIndex] < 0)
            {
                for (int i = n - 2; i >= 0; i--)
                {
                    if (array[i + 1] - array[i] < 0)
                    {
                        handles.Add(new int[2] { i + 2, i + 1 });
                        array[i] += array[i + 1];
                    }
                }
            }

            Console.WriteLine(handles.Count);
            for(int i = 0; i < handles.Count; i++)
            {
                Console.WriteLine(handles[i][0] + " " + handles[i][1]);
            }
            /*for(int i = 0; i < n; i++)
            {
                Console.Write(array[i] + " ");
            }*/
        }

        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13268
import numpy as np
N = int(input())
lst=input().split(" ")

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

for i in range(N-1):
    lst[i+1]= gojo(int(lst[i]),int(lst[i+1]))
    
print(lst[N-1])

Measured memory_bytes: 20160
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

N = int(input())
a = [int(i) for i in input().split()]

sum_a = sum(a)

ans = 10**10
x = 0
for i in range(N-1):
    x += a[i]
    ans = min(ans,abs(sum_a-2*x))

print(ans)


Measured memory_bytes: 26200
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[False]*(k+1)
for i in range(1,k+1):
  for j in range(n):
    if  i-a[j]<0:
      break
    if dp[i-a[j]]==False:
      dp[i]=True
if dp[k]==True:
  print('First')
else:
  print('Second')

          


Measured memory_bytes: 74776
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <numeric>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

typedef long long ll;

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i = a; i < b; i++)
#define vec_all(vec) vec.begin(), vec.end()

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

    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    int point = -1;
    rep(i, n - 1) {
        if (a[i] + a[i + 1] >= l) {
            cout << "Possible" << endl;
            point = i;
            break;
        }
    }

    if (point != -1) {
        repr(i, 0, point) {
            cout << i + 1 << endl;
        }

        for (int i = n - 2; i > point; i--) {
            cout << i + 1 << endl;
        }

        cout << point + 1 << endl;
        return 0;
    }

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

Measured memory_bytes: 1152