akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& vec) {
    out << "[";
    for (int x : vec) out << x << ", ";
    out << "]";
    return out;
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
    #define dbg_var(x) cerr << #x << ": " << x << endl;
#endif


int n;
char g[700][700];
int s[700][700];

int calc(int x, int y){
    for(int i=x-1; i<2*n; i++) for(int j=y-1; j<2*n; j++) s[i][j] = 0;
    
    for(int i=x; i<2*n && i<2*n+x-y; i++) for(int j=y; j<2*n && j < 2*n+y-x; j++){
        s[i][j] = (g[i][j] == g[j-y+x][i-x+y]) + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    }
    
    //~ cout << x << ' ' << y << endl;
    //~ for(int i=x; i<2*n; i++) {for(int j=y; j<2*n; j++) cout << s[i][j] << ' '; cout << endl;}
    //~ cout << endl;
    
    int ans = 0;
    for(int i=n-1; x+i<2*n && y+i<2*n; i++){
        if(s[x+i][y+i] - s[x+i-n][y+i] - s[x+i][y+i-n] + s[x+i-n][y+i-n] == n * n) ans++;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> g[i][j];
    for(int i=1; i<2*n; i++) for(int j=n+1; j<2*n; j++) g[i][j] = g[i][j-n];
    for(int i=n+1; i<2*n; i++) for(int j=1; j<2*n; j++) g[i][j] = g[i-n][j];
    
    int ans = calc(1,1);
    for(int x=2; x<=n; x++) ans += calc(x, 1);
    for(int y=2; y<=n; y++) ans += calc(1, y);
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 2432
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int st[12];
int H, W, K;
string S[12];
int best;
int total[12][1024];

void horizontal(int ind, int nr) {
    st[nr] = ind;
    st[nr + 1] = H;
    // try greedy
    
    int last = 0;
    int res = nr;
    //cout << res << endl;
    for (int col = 1; col <= W && res < best; ++col) {
        for (int i = 1; i <= nr + 1; ++i) {
            int s = total[st[i]][col] - total[st[i-1]][col] - total[st[i]][last] + total[st[i-1]][last];
            /*
            if (nr == 3) {
                for (int i = 1; i <= 3; ++i) {
                    cout << st[i] << endl;
                }
                cout << col << " " << s << " " << st[i] << endl;
            }*/
            if (s > K) {
                if (last == col - 1) {
                    res = best + 1;
                    break;
                }
                last = col - 1;
                --col;
                ++res;
                break;
            }
        }
    }
    if (res < best) {
        /*
        for (int i = 1; i <= nr; ++i) {
            cout << st[i] << " ";
        }
        cout << endl;*/
        best = res;
    }
    
    if (ind + 1 == H || ind == 0) return;
    horizontal(ind + 1, nr + 1);
    horizontal(ind + 1, nr);
}

int main() {
    cin >> H >> W >> K;
    best = H * W;
    for (int i = 1; i <= H; ++i) {
        cin >> S[i];
        for (int j = 1; j <= W; ++j) {
            total[i][j] = total[i-1][j] + total[i][j-1] - total[i-1][j-1] + (S[i][j - 1] == '1');
        }
    }
    
    if (total[H][W] <= K) {
        cout << 0 << endl;
        return 0;
    }
    
    horizontal(0, 0);
    for (int i = 1; i < H; ++i) {
        horizontal(i, 1);
    }
    
    cout << best;
    
    return 0;
}


Measured memory_bytes: 256
s1 = input()
s2 = input()
if len(s1) != len(s2):
    print("No")
else:
    D1 = {}
    D2 = {}
    flag = True
    for x, y in zip(s1, s2):
        if x not in D1:
            D1[x] = y
        else:
            flag = (flag and (D1[x] == y))
        if y not in D2:
            D2[y] = x
        else:
            flag = (flag and (D2[y] == x))
        if not flag:
            break
    if flag:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 3632
#include <iostream>
#include<iomanip>

using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  double a[n+1];
  a[0]=0;
  double ans=0;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    a[i]=(a[i]+1)/2;
    a[i]+=a[i-1];
    if(i>=m)
      ans=max(ans,a[i]-a[i-m]);
  }
       
  cout<<fixed<<setprecision(12)<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int h1, h2, k1, k2, a, b, c, d;
    cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;
    int x = h1*a + h2*b + (h1/10) * c + (h2/20) * d;
    int y = k1*a + k2*b + (k1/10) * c + (k2/20) * d;
    string ans = "even";
    if(x > y) ans = "hiroshi";
    else if(x < y) ans = "kenjiro";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3208
import numpy as np

N,K = map(int,input().split(' '))
a = np.array(list(map(int,input().split(' '))))

cost = np.full(N,10**9)
cost[0] = 0
for i in range(1 , N):
    
    size =  min(i,K)
    cost[i] = (np.abs(a[i] - a[i-size:i]) + cost[i-size:i]).min()

print(int(cost[-1]))

Measured memory_bytes: 22840
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <tuple>
#include <stack>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
typedef long long ll;
using namespace std;
ll mod = pow(10,9) + 7;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
char upper(char c){
	return c-0x20;
}
char lower(char c){
	return c+0x20;
}
int main() {
	int N,M; cin>>N>>M;
    const int nmmax=50;
    char A[nmmax][nmmax],B[nmmax][nmmax];
    for(int y=0;y<N;++y){
        for(int x=0;x<N;++x){
            cin >> A[y][x];
        }
}
    for(int y=0;y<M;++y){
        for(int x=0;x<M;++x){
            cin >> B[y][x];
        }
}
    bool exist=false;
    for(int ly=0;ly<N;++ly){
        for(int lx=0;lx<N;++lx){
            if(ly+M-1>=N or lx+M-1>=N) continue;
            bool match=true;
            for(int y=0;y<M;++y){
                for(int x=0;x<M;++x){
                    if(A[ly+y][lx+x]!=B[y][x]) match=false;
} }
            if(match) exist=true;
        }
}
    if(exist)
        cout << "Yes" << endl;
else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
v = gets.split.map(&:to_i)
for i in 0..(n-1)
  v[i] = v[i] * 1.0
end
v.sort!

ave = (v[0]+v[1]) / 2.0
for i in 2..(n-1)
  ave = (ave+v[i]) / 2.0
end
puts ave

Measured memory_bytes: 1788
# D - Knight

X, Y = map(int, input().split())
####

a = (2*Y - X) / 3
b = (2*X - Y) / 3

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
# を一部修正
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] % mod * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = int(a+b)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

if a%1 != 0 or b%1 != 0:
    print(0)
else:
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    ans = cmb(int(a+b), int(min(a,b)), mod)
    print(ans)


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

int n, m;
int road[8][8];

int dfs(int posi, bool *yet){
	int count = 1;
	for(int i = 0; i < n; ++i){
		count *= yet[i];
	}
	if(count) return 1;
	int ret = 0;
	for(int i = 0; i < n; ++i){
		if(road[posi][i] && !yet[i]){
			yet[i] = 1;
			ret += dfs(i, yet);
			yet[i] = 0;
		}
	}
	return ret;
}

int main(){	
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			road[i][j] = 0;
		}
	}
	for(int i = 0; i < m; ++i){
		int a, b; cin >> a >> b; --a; --b;
		road[a][b] = road[b][a] = 1;
	}
	bool yet[n] = {0};
	yet[0] = 1;
	cout << dfs(0, yet) << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()

# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    ans[i] = total - ans[i]
print(*ans[1:], sep="\n")

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

#define FASTIO ios::sync_with_stdio(NULL); cin.tie(NULL);
#define popcnt(x) __builtin_popcount(x)
#define compination(x) ((x*(x-1))/2)
#define all(x) x.begin() , x.end()
#define ll long long
#define ld long double
#define vii vector  <ll>
#define dqi deque   <ll>
#define sii set     <ll>
#define vch vector  <char>
#define mii map     <ll,ll>
#define pii pair    <ll,ll>
#define vss vector  <string>
#define PI 3.141592654

using namespace std;
void ONLINE__JUDGE();

const int mod = 998244353;
const int MAX = 1009;

ll x , y , cnt; vii vec; mii odd,even;

int main()
{
    cin >> x;
    for ( int i = 0; i < x; i++    ) cin >> y , vec.push_back(y);
    for ( int i = 0; i < x; i += 2 ) even[ vec[i] ]++;
    for ( int i = 1; i < x; i += 2 ) odd [ vec[i] ]++;

    vector < pii > e,o;
    for ( auto it : even ) e.push_back( { ((x/2)-it.second),it.first} );
    for ( auto it : odd  ) o.push_back( { ((x/2)-it.second),it.first} );
    sort( all(e) ); sort( all(o) );

    if      ( e.front().second != o.front().second )
        cout << e.front().first + o.front().first;
    else if ( e.size() > 2 && o.size() > 2  )
        cout << min( e[0].first+o[1].first , e[1].first+o[0].first );
    else if ( e.size() > 2 && o.size() == 1 )
        cout << e[1].first+o[0].first;
    else if ( e.size() == 1 && o.size() > 2 )
        cout << e[1].first+o[0].first;
    else
        cout << min( e[0].first , o[0].first ) + x/2;
    return 0;
}


void ONLINE__JUDGE()
{
    #ifndef ONLINE_JUDGE
    freopen( "inp.c"         , "r" , stdin  );
    //freopen( "OutPut.txt"   , "w" , stdout );
    #endif // ONLINE_JUDGE
}


Measured memory_bytes: 9588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

//幅優先探索
//全て添字で扱うこと
vll bfs(ll n, vector<vector<vll>> &next, ll start) {
  vll ans(n, 0);

  queue<vll> task;
  task.push({0, start});

  vll seen(n, 0);
  seen[start] = 1;

  ll depth = 0;
  while (task.size() > 0) {
    for (ll j = 0; j < next[task.front()[1]].size(); j++) {
      if (seen[next[task.front()[1]][j][1]] == 0) {
        ans[next[task.front()[1]][j][1]] = ans[task.front()[1]] + next[task.front()[1]][j][0];

        task.push(next[task.front()[1]][j]);
        seen[next[task.front()[1]][j][1]] = 1;
      }
    }
    task.pop();
  }
  return ans;
}

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

  vector<vector<vll>> next(n, vector<vll>(0));
  for (ll i = 0; i < n - 1; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    next[a - 1].push_back({c, b - 1});
    next[b - 1].push_back({c, a - 1});
  }

  ll q, k;
  cin >> q >> k;

  vll ans = bfs(n, next, k - 1);

  for (ll i = 0; i < q; i++) {
    ll x, y;
    cin >> x >> y;
    cout << ans[x - 1] + ans[y - 1] << endl;
  }
}

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

using namespace std;

const int N = 2e5+5;

int n;
int ar[N];
map < int , int > cnt;

int main(){
    scanf("%d" , &n);
    for(int i = 1; i <= n; i++){
        scanf("%d" , &ar[i]);
        cnt[i - ar[i]]++;
    }
    long long ways = 0;
    for(int i = 1; i <= n; i++){
        cnt[i - ar[i]]--;
        ways += cnt[ar[i] + i];
        cnt[i - ar[i]]++;
    }
    printf("%lld\n" , ways);

}


Measured memory_bytes: 21540
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {
  ll a, b, x;
  cin >> a >> b >> x;
  if (a == 0) {
    cout << b / x + 1 << endl;
  } else {
    cout << b / x - ((a - 1) / x) << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define ri register int
#define Max(x, y) (((x) > (y)) ? (x) : (y))
#define Min(x, y) (((x) < (y)) ? (x) : (y))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
#define int long long
const int maxn = 1e5 + 10;
inline int read()
{
    int f = 1, r = 0;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (isdigit(c)) {
        r = 10 * r + c - '0';
        c = getchar();
    }
    return f * r;
}
inline void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void writesp(int x) { write(x), putchar(' '); }
inline void writeln(int x) { write(x), puts(""); }
int N, arr[maxn], cnt[maxn];
signed main()
{
    N = read();
    for (ri i = 1; i <= N; ++i)
        arr[i] = read(), cnt[arr[i]]++;
    int ans = 1;
    for (ri i = 0; i < N; ++i) {
        if (cnt[i] > 2) {
            puts("0");
            return 0;
        } else if (cnt[i]) {
            if ((N - 1 - i) % 2) {
                puts("0");
                return 0;
            }
            if (N % 2 && cnt[0] != 1) {
                puts("0");
                return 0;
            }
            ans *= cnt[i], ans %= MOD;
        }
    }
    writeln(ans);
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>

using namespace std;


int main(){

//	変数の宣言
	int A,B,C;
//	変数の入力
	cin >> A >> B >> C;
//	カウント変数の宣言
	int count;
//	合計コイン
	int sum = 0;

	for(count=1;sum < C;count++)
	{
//		コインの加算
		sum += A;
		if(count%7 == 0) sum += B;
	}
//	結果の出力
	cout << count-1 << "\n";

	return 0;
}



Measured memory_bytes: 3112
//=template===================================================================//
// include
#include <vector>
#include <list>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <map>

// namespace
using namespace std;

// define
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(i,n) FOR(i,0,n)
#define MIN_V(v) *min_element(v.begin(), v.end())
#define MAX_V(v) *max_element(v.begin(), v.end())

// typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef long long LL;
typedef unsigned long long ULL;
typedef struct {
  LL cost;
  bool done;
} node_t;

// conversion
inline int
toInt(string s)
{
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
inline int countChar(string s, char c) {int cnt,i; cnt=0; REP (i,s.size()) {if (s[i]==c) cnt++;} return cnt;}
template<class T> inline string toString(T x) {ostringstream sout; sout<<x; return sout.str();}
//============================================================================//

//=variables==================================================================//

//============================================================================//
int main(void)
{
  // Scan begin.
  int n;
  cin >> n;
  // Scan done.

  // Code begin.
  map<string, int> s;
  int max = 0;

  for (int i = 0; i < n; i++) {
      string s_i;
      cin >> s_i;
      if (s.count(s_i) > 0)
      {
          s[s_i]++;
          if (s[s_i] > max) {
              max = s[s_i];
          }
      }
      else {
          s.insert(make_pair(s_i, 1));
          if (max == 0) {
              max = 1;
          }
      }
  }

  VS out;
  for (auto itr = s.begin(); itr != s.end(); itr++) {
      if (itr->second == max) {
          out.push_back(itr->first);
      }
  }

  sort(out.begin(), out.end());
  for (int i = 0; i < out.size(); i++) {
      cout << out[i] << endl;
  }

  // Code done.

  return 0;
}

Measured memory_bytes: 26868
#include<bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long n,x,t,ans=0;
    cin>>n>>x>>t;
    int rem=n%x;
    n=n-rem;
    ans=n/x;
    if(rem!=0)ans++;
    cout<<ans*t<<"\n";
}


Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  long n;
  cin >> n;
  vector<long> v;
  for (int i=0; i<n; i++) {
    long t;
    cin >> t;
    v.push_back( t );
  }
  long max = 0;
  long sum = 0;
  for (int i=0; i<n; i++) {
    if (v[i]<max){
      sum += max - v[i];
    }
    else if (v[i]>max) {
      max = v[i];
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 5356
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
 


public class Main {
	private static Scanner sc = new Scanner(System.in);
	//result = Math.pow(num1, num3)
	//StringBuffer str = new StringBuffer(hoge1);
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)

	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );
		
		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
	//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
	//ArrayList<String> cc = new ArrayList<>(n);
	//Collections.sort(list);
	//Array.sort(list);   cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");//1 1 2 3 5
	static long mod =1000000007;
	//static 	ArrayList<Integer> cc = new ArrayList<>(100);
	
	
	
	
	public static void main(String[] args) {
		//int N=sc.nextInt();for(int i=0;i<N;i++) {}
		//Random sc =new Random();
		long N=sc.nextInt();
		long C=sc.nextInt();
		long K=sc.nextInt();

		long t[]=new long[(int) N];
		for(int i=0;i<N;i++) {
			t[i]=sc.nextInt();
			
		}
		Arrays.sort(t);
		
		long tk=t[0]+K;
		long ic1=C-1;
		
		long ans=0;
		
		for(int i=0;i<N;i++) {
		
			if(t[i]>tk||i>ic1) {
				tk=t[i]+K;
				ic1=i+C-1;
				i--;
				ans++;
				
			}else if(i==N-1) {
				ans++;
				
			}
			
			
			
		}
		
		p(ans);
		
		
		
		
		
		
		
		
		
	}
	

	
	
	
	

	


	
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p() {System.out.println();};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	static String nextPermutation(String s) {
		ArrayList<Character> list=new ArrayList<>();
		for(int i=0;i<s.length();i++) {
			list.add(s.charAt(i));
		}
		int pivotPos=-1;
		char pivot=0;
		for(int i=list.size()-2;i>=0;i--) {
			if(list.get(i)<list.get(i+1)) {
				pivotPos=i;
				pivot=list.get(i);
				break;
			}
		}
		if(pivotPos==-1&&pivot==0) {
			return "Final";
		}
		int L=pivotPos+1,R=list.size()-1;
		
		
		
		int minPos=-1;
		char min =Character.MAX_VALUE;
		
		for(int i=R;i>=L;i--) {
			if(pivot<list.get(i)) {
				if(list.get(i)<min) {
					min=list.get(i);
					minPos=i;
				}
			}
		}
		
		Collections.swap(list, pivotPos, minPos);
		Collections.sort(list.subList(L, R+1));
		
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<list.size();i++) {
			sb.append(list.get(i));
		}
		return sb.toString();
	}
}
	


Measured memory_bytes: 60176
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;



int main() {
  int N; cin >> N;
  vector<int> d(N);
  rep(i,N)cin >> d[i];
  sort(d.begin(),d.end());
  int arc = d.size()/2; 
  int abc = d.size()/2 -1;
  int ans = d[arc] - d[abc];
  cout << ans << endl;
  


	return 0;
}



Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define ll long long int
#define ff first
#define pb push_back
#define ss second
#define debug 0
#define ff first
#define mp make_pair
 
using namespace std;
 
const ll MOD = 1000000007LL;
 
ll fact[1000006];
ll ifact[1000006];
ll power2[1000006];

int n;
 
ll ar[2000056];
ll visit[2000056];
ll least_prime[1000005];
ll level[300005];
vector<int> adj[5000005];

const long double pi=3.1415926535897;

set<string> st;
 
bool vis[500020];
 
bool prime[10000006];
 
vector<int> primes,pec,vec;

vector<pair<ll,ll> > vp;

map<ll,ll> has;


ll day[3000006];
 
 
 
ll powr (ll a, ll  b)
{
    if (b == 0)
        return 1;
    long long int x = powr(a, b/2);
    if (b % 2 == 0)
        return (x*x)%MOD;
    else
        return ((x*x)%MOD*a%MOD)%MOD;
}
 
inline ll inv(ll x) {
  return powr(x, MOD - 2);
}
 
inline ll mulMod(ll a, ll b) {
  return (a%MOD * b%MOD) % MOD;
 
}
 
inline void process() {
  fact[0] = 1;
  power2[0] = 1;
  for(int i = 1; i < 200003; i++) {
    fact[i] = mulMod(fact[i - 1], i);
    power2[i] = mulMod(power2[i - 1], 2);
  }
  ifact[200002] = inv(fact[200002]);
  for(int i = 200002 - 1; i >= 0; i--) {
    ifact[i] = mulMod(ifact[i + 1], i + 1);
  }
}
 
inline ll ncr(ll n, ll r) {
  if(n < r) return 0;
  return mulMod(fact[n], mulMod(ifact[r], ifact[(n - r)]));
}
 
 
 
void sieve()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    
    for(ll i=2;i*i<=1000006;i++)
    {
        if(prime[i])
        {
            for(ll j=i*2;j<=1000006;j+=i)
            {
                prime[j]=false;
            }
        }
    }
    
    for(int i=2;i<=100005;i++)
    {
    	if(prime[i])
    	primes.pb(i);
	}
}





void LeastPrimeFactor(){
	int tot=1000003;
	least_prime[1]=1;
	for (ll i = 2; i <tot; i += 2)	least_prime[i] = 2;
	for (ll i = 3; i < tot; i += 2){
		if (!visit[i]){
			least_prime[i] = i;
			for (ll j = i; (j*i) < tot; j += 2){
				if (!visit[j*i])
				{
					visit[j*i] = true;
					least_prime[j*i] = i;
				}
			}
		}
	}
}

int solve(int idx, int prod)
{
   
   if(idx==n)
   {
   	
   //	cout<<"prod="<<prod<<"\n";
   	if(prod%2==0)
   	return 1;
   	else
   	return 0;
   }
   
   int x,y,z;
   
   
    x = solve(idx+1,(ar[idx]-1)*prod);
    y = solve(idx+1,(ar[idx])*prod);
    z = solve(idx+1,(ar[idx]+1)*prod);

   
   return x+y+z;
  
}
  
ll catalan(ll n)
{
   
    ll c = solve(2*n, n);
    ll d= inv(n+1);
    ll ans = (c%MOD*d%MOD)%MOD;
    return ans;
}




 

int main() 
{
//	freopen("input4.in","r",stdin);
//	freopen("output4.out","w",stdout);
    ll m,t,p,q,s,c,d,e,f,g,h,res=0,u,v,i,j,l=0,k,len,tot=0,rad,w,pos=0,y,r=0,z,x,maxm=-1;
	ll cycle,val,max1=0,max2=0,num=0,zero,ans=0,min1=INT_MAX,min2=INT_MAX,sum=0;
    bool flag=0;
    ll a,b,minm=INT_MAX;
    ll x1,x2;
    
    string str;
    
	cin>>n;
	
	for(i=0;i<n;i++)
	cin>>ar[i];
	
	p=solve(1,ar[0]-1);
    q=solve(1,ar[0]);
    r=solve(1,ar[0]+1);
    
    cout<<p+q+r;
	
    
	return 0;
    
}    

Measured memory_bytes: 125184
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int k, q; std::cin >> k >> q;
    std::vector<long long> d(k), e(k);
    for (int i = 0; i < k; i++) std::cin >> d[i];
    while (q--) {
        long long n, x, m; std::cin >> n >> x >> m;
        for (int i = 0; i < k; i++) e[i] = d[i] % m == 0 ? m : d[i] % m;
        long long sum = std::accumulate(e.begin(), e.end(), 0LL);
        sum *= (n - 1) / k;
        for (int i = 0; i < (n - 1) % k; i++) sum += e[i];
        std::cout << n - 1 - (x + sum) / m + x / m << std::endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N,A;
  cin >> N >> A;
  
  int x;
  x = N % 500;
  
  if (x<=A){
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
using namespace std;
const long long M=1000000007ll;
int n,k,i,x,a,s,ans;
int main()
{
	scanf("%d %d",&n,&x);
	ans=1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		s+=a;
		if(s<=x)
			ans++;
	}
	cout<<ans;
}


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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(a) (a).rbegin(), (a).rend()

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll d[100][100];
ll h, w, t;
ll sx, sy, gx, gy;

vs maze;

int main() {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    string ans;
    rep(i, ty-sy) ans += 'U';
    rep(i, tx-sx) ans += 'R';
    rep(i, ty-sy) ans += 'D';
    rep(i, tx-sx) ans += 'L';
    ans += 'L';
    rep(i, ty-sy+1) ans += 'U';
    rep(i, tx-sx+1) ans += 'R';
    ans += 'D';
    ans += 'R';
    rep(i, ty-sy+1) ans += 'D';
    rep(i, tx-sx+1) ans += 'L';
    ans += 'U';
    cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func maxFloat64(a, b float64) float64 {
	if a > b {
		return a
	} else {
		return b
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func powInt(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func isPrime(x int) bool {
	if x == 1 {
		return false
	}
	if x == 2 {
		return true
	}
	if x%2 == 0 {
		return false
	}

	b := true
	rootx := int(math.Sqrt(float64(x)))
	i := 3
	for i <= rootx {
		if x%i == 0 {
			b = false
			break
		}
		i += 2
	}
	return b
}

func PrimeFactors(n int) (pfs []int) {
	// Get the number of 2s that divide n
	for n%2 == 0 {
		pfs = append(pfs, 2)
		n = n / 2
	}

	// n must be odd at this point. so we can skip one element
	// (note i = i + 2)
	for i := 3; i*i <= n; i = i + 2 {
		// while i divides n, append i and divide n
		for n%i == 0 {
			pfs = append(pfs, i)
			n = n / i
		}
	}

	// This condition is to handle the case when n is a prime number
	// greater than 2
	if n > 2 {
		pfs = append(pfs, n)
	}

	return
}

func sumInts(x []int) int {

	total := 0
	for _, v := range x {
		total += v
	}

	return total
}

//Main
const (
	initialBufSize = 10000
	maxBufSize     = 1000000
	mod            = 1e9 + 7
)

var (
	sc *bufio.Scanner = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
		sc.Buffer(buf, maxBufSize)
		return sc
	}()
)

var N, A, B int

func main() {
	sc.Split(bufio.ScanWords)

	N, A, B = nextInt(), nextInt(), nextInt()
	ans := 0
	if (B-A)%2 == 0 {
		fmt.Println((B - A) / 2)
	} else {
		if B-1 < N-A {
			ans += A - 1
			B -= A - 1
			ans += (B-1)/2 + (B-1)%2
		} else {
			ans += N - B
			A += N - B
			ans += (N-A)/2 + (N-A)%2
		}
		fmt.Println(ans)
	}

}


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

const long long INF=0;
long long n,node[100000000];
void init(long long N_){
    n=1;
    while(n<N_)n*=2;
    for(long long i=0;i<2*n-1;i++)node[i]=INF;
}
void update(long long a,long long x){
    a+=n-1;
    node[a]=x;
    while(a>0){
        a=(a-1)/2;
        node[a]=max(node[2*a+1],node[2*a+2]);
    }
}
long long query(long long a,long long b,long long k,long long l,long long r){
    if(b<=l||r<=a)return INF;
    if(a<=l&&r<=b)return node[k];
    long long vl=query(a,b,2*k+1,l,(l+r)/2);
    long long vr=query(a,b,2*k+2,(l+r)/2,r);
    return max(vl,vr);
}

int main(void)
{
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    init(300001);
    for (long long i = 0; i < N; i++)
    {
        long long premin = max((long long)0, A[i]-K);
        long long premax = min((long long)300000, A[i]+K);
        long long num = query(premin, premax+1, 0, 0, n);
        update(A[i], num+1);
    }
    long long ans = query(0, n-1, 0, 0, n);
    cout << ans << endl;
}

Measured memory_bytes: 13804
#include<stdio.h>
#pragma GCC optimize("O2")
#define rep(i,N) for(int i=0;i<(int)N;i++)
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void Radix(int A[],const int N)
{
  int temp[200001];
  rep(k,4)
  {
    int u[256]={},v[256]={};
    rep(i,N)u[A[i]>>8*k&255]++;
    rep(i,255)u[i+1]+=u[i];
    rep(i,N){temp[--u[A[N-1-i]>>8*k&255]]=A[N-1-i];}k++;
    rep(i,N)v[temp[i]>>8*k&255]++;
    rep(i,255)v[i+1]+=v[i];
    rep(i,N)A[--v[temp[N-1-i]>>8*k&255]]=temp[N-1-i];
  }
}
int main()
{
  int i=0,N=IN(),A[200000];long sum=0;
  while(i<N){A[i++]=IN();}
  Radix(A,N);
  i=1;while(i<N){sum+=A[N-1-i++/2];}
  return printf("%ld\n",sum),0;
}

Measured memory_bytes: 3140
// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES
#include<math.h>

//#include<cmath>

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>



//#include "Ants.h"
using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1000000000000000000ll)
//typedef pair < int, int> P;
ll gcd(ll a, ll b) {//最大公約数を求める///最大公倍数a*b/gcd(a,b)
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcd(ll a, ll b) {//最小公倍数を求める　b=0のときaを返す
	if (b == 0) return a;
	return (a / gcd(a, b)) * b;
}
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
int digiter(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}
vector<int> convert(string s) {
	vector<int> d;
	ll n = s.size();
	rep(i, n) {
		d.push_back(s[i] - '0');
	}
	return d;
}
int N, X, Y;
int sz[1000000];
int bfs(int s) {
	queue<int>que;
	vector<int>dist(N, INF);
	dist[s] = 0;
	que.push(s);
	while (!que.empty()) {
		int u = que.front(); que.pop();
		if (dist[u + 1] == INF && u + 1 < N) {
			dist[u + 1] = dist[u] + 1;
			que.push(u + 1);
		}
		if (dist[u - 1] == INF && u - 1 >= 0) {
			dist[u - 1] = dist[u] + 1;
			que.push(u - 1);
		}
		if (u == X && dist[Y] == INF) {
			dist[Y] = dist[u] + 1;
			que.push(Y);
		}
		if (u == Y && dist[X] == INF) {
			dist[X] = dist[u] + 1;
			que.push(X);
		}
		sz[dist[u]]++;

	}
}

int main()
{
	cin >> N >> X >> Y;
	X--; Y--;
	
	rep(i, N) {
		queue<int>que;
		vector<int>dist(N, INF);
		dist[i] = 0;
		que.push(i);
		auto push = [&](int u, int d) {
			if (dist[u] != INF)return;
			dist[u] = d;
			que.push(u);
		};
		while (!que.empty()) {
				int u = que.front(); que.pop();
				if (u + 1 < N) {
					push(u + 1, dist[u] + 1);
				}
				if (u - 1 >= 0) {
					push(u - 1, dist[u] + 1);
				}
				if (u == X ) {
					push(Y,dist[u]+1);
				}
				if (u == Y ) {
					push(X,dist[u]+1);
				}
				sz[dist[u]]++;

		}
		
		
	}
	rep(i, N - 1) {
		cout << sz[i + 1] / 2 << endl;
	}
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int A,B;
    cin >> A>>B;
    if (B==1) {cout<<0 << endl; return 0;}
    int count=0, total=0;
    while (B>total)
    {
        total+=A; count++;
        if (total < B) total--;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main (final String[] args) {
        final Scanner s = new Scanner(System.in);
        int k = Integer.parseInt(s.next());
        int x = Integer.parseInt(s.next());
        
        if (k*500 < x) System.out.println("No");
        else System.out.println("Yes");
    }
}

Measured memory_bytes: 22100
N = gets.to_i
h = gets.split().map(&:to_i)

inf = 1000000000

dp = []

1000000.times do 
  dp.push(inf)
end

dp[0] = 0

def chmin(a, b)
  if a > b
    return b
  end
  return a
end

(1..N-1).each do |i|
  dp[i] = chmin(dp[i], (h[i-1]-h[i]).abs + dp[i-1])
  if i > 1
    dp[i] = chmin(dp[i], (h[i-2]-h[i]).abs + dp[i-2])
  end
end

puts dp[N-1]

Measured memory_bytes: 15884
#![allow(unused_imports)]

//input
use proconio::input;
use proconio::marker::{Bytes, Chars};
//use std::io::Read;

//collections
//use std::collections::BTreeMap;
//use std::collections::BTreeSet;
//use std::collections::HashMap;
//use std::collections::HashSet;
//use std::collections::VecDeque;
//use std::collections::BinaryHeap;

//use std::cmp::*;

fn main() {
    input! {
        s: u64,
        w: u64,
    }

    //tabで移動
    if s <= w {
        println!("unsafe",);
    } else {
        println!("safe",);
    }
}


Measured memory_bytes: 2144
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		
		long num500 = x / 500;
		x %= 500;
		long num5 = x / 5;
		long ans = num500 * 1000 + num5 * 5;
		System.out.println(ans);
		
		sc.close();
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
int main() {
    int n,k,q;
    cin >> n >> k >> q;
    vector<int> a(q),kaisuu(n);
    for (int i = 0; i < q; ++i) {
        cin >> a[i];
        kaisuu[a[i]-1]++;
    }
    for (int i = 0; i < n; ++i) {
        if(q - kaisuu[i] < k) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
N = int(input())
b = list(map(int,input().split()))
a = []
flag = 0
answer_flag = 0

while(1):
    count = len(b)
    if(count == 0):
        break
    for i in reversed(range(count)):
        if(b[i] == i + 1):
            a.append(b.pop(i))
            answer_flag = 1
            break
    if(answer_flag):
        answer_flag = 0
        continue
    flag = 1
    break

if(flag == 1):
    print('-1')
else:
    for i in reversed(range(N)):
        print(a[i])

Measured memory_bytes: 39024
#include <iostream>
#include <vector>
#include <bitset>
#include <functional>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <tuple>
using namespace std;

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

#include <string>
#include <cassert>

bool comp(char x,char y)
{
    if(x=='?' or y=='?') return true;
    return x==y;
}

using p32=pair<int,int>;

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

    string s[3]; cin>>s[0]>>s[1]>>s[2];
    const int offs=4040;
    bool dif[3][3][offs*3]={};
    for(int i=0; i<3; ++i)
    {
        for(int j=0; j<3; ++j)
        {
            auto &now=dif[i][j];
            for(int x=0; x<(int)s[i].size(); ++x)
            {
                for(int y=0; y<(int)s[j].size(); ++y)
                {
                    now[x-y+offs]|=!comp(s[i][x],s[j][y]);
                }
            }
        }
    }
  

    int ans=6000;
    for(int i=-offs; i<offs; ++i)
    {
        if(dif[0][1][i+offs]) continue;
        for(int j=(i<0?-offs:-offs/2); j<(i>0?offs:offs/2); ++j)
        {
            if(!dif[0][2][j+offs] and (j-i+offs<0 or !dif[1][2][j-i+offs]))
            {
                int l=min({0,i,j});
                int r=max({(int)s[0].size(),i+(int)s[1].size(),j+(int)s[2].size()});
                chmin(ans, r-l);
            }
        }
    }
    cout << ans << "\n";
}


Measured memory_bytes: 384
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cinttypes>
#include <cstdint>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <chrono>
#include <forward_list>
#include <initializer_list>
#include <random>
#include <regex>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

using Field = vector<vector<ll>>;
using Graph = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VC = vector<char>;
using PI = pair<int, int>;

#define FOR(i, s, n) for (int i = s; i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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

ll modpow(ll a, ll n) {
   ll res = 1;
   while (n > 0) {
      if (n & 1) {
         res *= a;
         res %= mod;
      }
      a *= a;
      a %= mod;

      n >>= 1;
   }
   return res;
}

ll N;
vector<ll> A, B;

map<pair<ll, ll>, ll> M;
ll zero_zero, zero_no, no_zero;

pair<ll, ll> rev(pair<ll, ll> x) {
    ll a = -x.first;
    ll b = x.second;

    if (a < 0) return make_pair(-b, -a);
    return make_pair(b, a);
}


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

    cin >> N;
    A.resize(N + 1);
    B.resize(N + 1);

    REP(i, N) {
        cin >> A[i] >> B[i];
    }

    zero_zero = 0, no_zero = 0, zero_no = 0;


    REP(i, N) {
        if (A[i] == 0 && B[i] == 0) zero_zero++;
        else if (A[i] == 0) zero_no++;
        else if (B[i] == 0) no_zero++;
        else {
            ll g = gcd(abs(A[i]), abs(B[i]));
            A[i] /= g;
            B[i] /= g;
            if (B[i] < 0) {
                A[i] *= -1;
                B[i] *= -1;
            }
            M[make_pair(A[i], B[i])]++;
        }
    }

    ll ans = modpow(2, zero_no) + modpow(2, no_zero) + mod - 1;
    ans %= mod;

    set<pair<ll, ll>> used;
    for (auto m : M) if (!used.count(m.first)) {
        auto p = m.first;
        auto pp = rev(p);
        if (M.count(pp)) {
            ans *= modpow(2, M[p]) + modpow(2, M[pp]) +mod - 1;
            ans %= mod;
            used.insert(pp);
        } else {
            ans *= modpow(2, M[p]);
            ans %= mod;
        }
    } 

    ans += zero_zero;
    ans = ans + mod - 1;
    ans %= mod;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 18740
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n; 
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(a.begin(), a.end());
	vector<int> b = a;
	map<int, bool> mp;
	rrep(i, n) {
		if (a[i] == a[i - 1]) mp[a[i]] = true;
	}
	int ans = 0;
	for (int i = n - 1; i >= 0; --i) {
		int x = a[i];
		b.pop_back();
		if (mp[a[i]]) {
			ans++;
			continue;
		}
		vector<int> rec;
		for (int j = 1; j * j <= x; ++j) {
			if (x % j == 0) {
				rec.push_back(j);
				if (j * j != x) rec.push_back(x / j);
			}
		}
		bool ok = false;
		for (int c : rec) {
			if (binary_search(all(b), c)) {
				ok = true;
				break;
			}
		}
		if (ok) ans++;
	}
	cout << n - ans << endl;
	return 0;
}


Measured memory_bytes: 14196
// 1行にintが1つだけ入っているときに読み取る
fn read_int() -> i32{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_right().parse().unwrap()
}

fn main(){
    let n = read_int();
    println!("{}",n*n*n);
}


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

signed main() {
  int n, l;
  cin >> n >> l;
  vector<string> s(n);
  for (auto&& u : s) cin >> u;
  sort(begin(s), end(s));
  string ret = "";
  for (auto&& u : s) ret += u;
  cout << ret << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, char const *argv[]) {
  int a,b,c,d;

  scanf("%d %d %d %d",&a,&b,&c,&d );

  if( a * b > c * d){
    printf("%d\n",a*b );
  }else{
    printf("%d\n",c*d );
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <thread>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)

using namespace std;

int main()
{
	uint32_t n, m; cin >> n >> m;

	uint32_t max = m / n;
	uint32_t val = max;

	while (true) {
		if (m % val == 0) break;
      val--;
	}

	cout << val << endl;

	return 0;
}

Measured memory_bytes: 256
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
a = A[0]
for i in range(1,N):
    a = gcd(a,A[i])
print(a)


Measured memory_bytes: 14252
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = [input() for i in range(3)]
    print(s[0][0] + s[1][1] + s[2][2])

solve()


Measured memory_bytes: 2940
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

A = int(input())
B = int(input())
C = int(input())
X = int(input())

cnt = 0
for i in range(A + 1):
    for j in range(B + 1):
        for k in range(C + 1):
            if i * 500 + j * 100 + 50 * k == X:
                cnt += 1

print(cnt)

Measured memory_bytes: 9676
#include<stdio.h>

int main(void){
  int a[3],n,i,m;
  scanf("%d",&n);
  m=n;
  for(i=0;i<3;i++){
    a[i]=m%10;
    m/=10;
  }
  if((a[0]==a[1]) && (a[1]==a[2])){
    printf("%d\n",n);
    return 0;
  }
  for(i=1;i<10;i++){
    if(n<111*i) break;
  }
  printf("%d\n",i*111);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>

using namespace std;

int main()
{
	for(;;){
		int x;
		int h;
		double S = 0;
		
		cin >> x >> h;
		
		if(x == 0 && h == 0){
			break;
		}
		
		S += x*x;
		S += x*(double)sqrt((x*(double)x/4)+(h*h))*2;
		
		printf("%lf\n",S);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

int main(){

    int N;
    cin >> N;

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

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

    int n = a[N - 1];
    int ans = -1;
    ll min_pivot_dist = 1e18;
    for(int i=0;i<N-1;i++){
        int pivot_dist = abs(n / 2 - a[i]);
        if(n % 2 == 1){
            pivot_dist = min(pivot_dist, abs(n / 2 + 1 - a[i]));
        }
        if(pivot_dist < min_pivot_dist){
            ans = a[i];
            min_pivot_dist = pivot_dist;
        }
    }
    assert(ans >= 0);
    cout << n << " " << ans << endl;

    return 0;
}

Measured memory_bytes: 640
N,S,T=open(0)
ans=3
i=1
if S[0]!=T[0]:
    ans*=2
    i*=2
while i<int(N):
    if S[i-1]==T[i-1]:
        ans*=2
    elif S[i]!=T[i]:
        ans*=3
    i+=1+(S[i]!=T[i])
print(ans%(10**9+7))

Measured memory_bytes: 9036
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
 
void fio() 
{
    std::ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
}
 
void inputread()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}
const ld p=6.28318530717958623200;

int32_t main()
{
    fio();
    ll r;
    cin >> r;
    cout << fixed << setprecision(20)<< r*p;
    

    return 0;
}

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

int dp[2001];

int solve(int S) {
    if(S == 0)
        return 1;
    if(S < 3)
        return 0;
    
    if(dp[S] != -1)
        return dp[S];
    int ans = 0;
    for(int i = 3; i<=S; i++) {
        ans += solve(S - i);
        ans %= 1000000007;
    }
    return dp[S] = ans;
}

int main() {
    int tc = 1;
    while(tc--) {
        int S;
        cin>>S;
        if(S <= 2 && S != 0)
            cout<<0<<endl;
        else {
            memset(dp, -1, sizeof(dp));
            cout<<solve(S)<<endl;        
        }
    }
    return 0;
}

Measured memory_bytes: 3652
N=int(input())
A=list(map(int,input().split()))
from collections import defaultdict
cnt=defaultdict(int)
for a in A:
    cnt[a]+=1
ans,two=0,0
for k,v in cnt.items():
    if v%2==1:
        ans+=1
    else:
        two+=1
        ans+=1
if two%2==1:
    ans-=1
print(ans)

Measured memory_bytes: 17652