akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<fstream>
#include<utility>
#include<bitset>
#include<map>
#include<deque>
#include<cmath>
#include<random>
#include<set>
#include<string.h>
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makel(N) ll N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007
#define re return 0

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

int main() {
	makei(N);
	set<int> s;
	rep(N) {
		int a;
		cin >> a;
		if (s.find(a) == s.end())s.insert(a);
		else s.erase(a);
	}
	say(s.size());
}

Measured memory_bytes: 4864
#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+1); ++i)
using namespace std;
using ll = long long;
const int INF = -100100100;

int main(){
    int n, l;
    cin >> n >> l;
    int s = 10000000;
    rrep(i,n){
        if(abs(s)>abs(l + i -1)){
            s = l+i-1;
        }
    }
    cout << (l-1)*(n) + (n*(n+1))/2 -s  << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
const LL lim = 1e10;

int n, m, p, q, ans;
bool flag, is_prime[N];
LL a[N], prime[N], prime2[N], prime3[N];
set<LL> ST;
map<LL, LL> MP, G;

void init(){
	LL s;
    for(LL i=1; ;i++){
		s = i * i * i;
		if(s > lim)	break;
		ST.insert(s);
    }
    for(LL i=1; ;i++){
		s = i * i;
		if(s > lim)	break;
		MP[s] = i;
    }

    memset(is_prime, 1, sizeof(is_prime));
    p = q = 0;

    for(int i=2; i<N; i++){
		if(is_prime[i]){
			prime[p] = i;
			prime2[p] = prime[p] * prime[p];
			s = prime2[p] * prime[p];
			p++;
			if(s <= lim){
				prime3[q++] = s;
			}
			for(int j=i<<1; j<N; j+=i){
				is_prime[j] = 0;
			}
		}
    }
}

void trans(LL x){
	if(ST.count(x)){
		flag = 1;
		return;
	}

    for(int i=0; i<q && prime3[i]<=x; i++){
        while(x % prime3[i] == 0){
			x /= prime3[i];
        }
    }

    LL y = 1, z = x;

    for(int i=0; prime[i]<3000 && prime2[i]<=x; i++){
		if(x % prime[i] == 0){
			if(x % prime2[i] == 0){
				y *= prime[i];
				x /= prime2[i];
			} else {
				x /= prime[i];
				y *= prime2[i];
			}
		}
    }

    if(x > 1){
		if(MP.count(x)){
			y *= MP[x];
			a[m++] = z;
			G[z] = y;
		} else if(x <= 100000){
			y = y * x * x;
			a[m++] = z;
			G[z] = y;
		} else {
			ans++;
		}
    } else {
    	a[m++] = z;
    	G[z] = y;
    }
}

int Cnt(LL x){
	int j = lower_bound(a, a+m, x) - a;
	int k = upper_bound(a, a+m, x) - a;
	return k - j;
}

int main(){
	init();
	LL x, y;
	int c, d;
    while(~scanf("%d", &n)){
		ans = m = 0;
		flag = 0;
		G.clear();
		for(int i=0; i<n; i++){
			scanf("%lld", &x);
			trans(x);
		}

		ans += flag;

		if(m){
			sort(a, a+m);

			y = G[a[0]];
			c = Cnt(a[0]);
			d = Cnt(y);
			ans += max(c, d);
			for(int i=1; i<m; i++){
				if(a[i]==a[i-1])	continue;
				y = G[a[i]];
				d = Cnt(y);
				if(y<a[i] && d)	continue;
                c = Cnt(a[i]);
                ans += max(c, d);
			}
		}

		printf("%d\n", ans);
    }
	return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <string>
#include <vector>

int main() {
    int N;
    std::cin >> N;
    std::string s;
    std::cin >> s;

    std::vector<std::vector<int>> dpt(N+1, std::vector<int>(N+1, 0));
    int result = 0;
    for (int i = 1; i < N + 1; i++) {
        for (int j = i+1; j < N + 1; j++) {
            if (s[j-1] == s[i-1]) {
                if (j - dpt[i-1][j-1] > i) {
                    dpt[i][j] = dpt[i-1][j-1] + 1;
                }
            }
            if (dpt[i][j] > result) result = dpt[i][j];
        }
    }
    std::cout << result << std::endl;
}

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

int main(void){
  int N;
  scanf("%d",&N);
  int t[N+1],x[N+1],y[N+1];

  t[0]=x[0]=y[0]=0;

  for(int i=1;i<=N;i++){
    scanf("%d %d %d",&t[i],&x[i],&y[i]);
  }

  int dt,dx,dy,check=0;

  for(int k=0;k<N;k++){
    dt=t[k+1]-t[k];
    dx=abs(x[k+1]-x[k]);
    dy=abs(y[k+1]-y[k]);
    if(dt<dx+dy||dt%2!=(dx+dy)%2){
      check=1;
      break;
    }
  }

  if(check==1) printf("No\n");
  else printf("Yes\n");
  return 0;
}


Measured memory_bytes: 1280
/******************************************
*******************************************
*******************************************
	PREPARED BY - SOMESH AWASTHI 
	CHANDIGARH UNIVERSITY
*******************************************
*******************************************
*******************************************/

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(long long i=a;i<b;i++)
#define io ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
long int mod=1000000007;

int main()
{
	io
	#ifdef SOMU
		clock_t startTime = clock();
		freopen("input.txt","r",stdin);
	#endif

	int n;
	cin >> n;
	vl arr(n);
	vl dp(n);
	fr(i, 0, n) cin >> arr[i];
	fr(i, 1, n) {
		if(i == 1)
			dp[i] += labs(arr[i] - arr[i - 1]);
		else {
			dp[i] += min(labs(arr[i] - arr[i - 1]) + dp[i - 1], labs(arr[i] - arr[i - 2]) + dp[i - 2]); 
		}
	}
	cout<<dp[n - 1];

	#ifdef SOMU
		cout << endl <<setprecision(20)<< double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
	#endif
	return 0;
}

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

using namespace std;
using ll=long long;
using vi=vector<int>;

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int n;
    cin >> n;
    vi a(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a.begin(), a.end());
    ll ans = 0;
    for(int i = n - 1; i >= 1; --i){
        int lo = 0 , hi = i - 1 ;
        while ( lo < hi ){
            if(a[lo] + a[hi] > a[i]) ans += hi - lo , hi--;
            else lo++;
        }
    }
    cout << ans << '\n';



    return 0;
}













Measured memory_bytes: 256
import sys

N,K,C=map(int,input().split())

S=list(input())
if C>=N-1:
    if K==1:
        if S.count("o")>=2:
            sys.exit()
        else:
            print(S.index("o")+1)
            sys.exit()
    else:
        sys.exit()
    
    
left=[0]*N
right=[0]*N

if S[0]=="o":
    left[0]=1
for i in range(1,C+1):
    left[i]=left[i-1]
    if S[i]=="o":
        left[i]=1
for i in range(C+1,N):
    if S[i]=="o":
        left[i]=max(left[i-1],left[i-C-1]+1)
    else:
        left[i]=left[i-1]

if S[-1]=="o":
    right[-1]=1
for i in range(N-2,N-C-2,-1):
    right[i]=right[i+1]
    if S[i]=="o":
        right[i]=1
for i in range(N-C-2,-1,-1):
    if S[i]=="o":
        right[i]=max(right[i+1],right[i+C+1]+1)
    else:
        right[i]=right[i+1]

data=[]
for i in range(N):
    if S[i]=="o":
        L=i-C-1
        R=i+C+1
        num=1
        if L>=0:
            num+=left[L]
        if R<N:
            num+=right[R]
        if num>K:
            sys.exit()
        if num==K:
            data.append(i)

for i in range(len(data)):
    if i==0:
        if data[i+1]-data[i]>C:
            print(data[i]+1)
    elif i==len(data)-1:
        if data[i]-data[i-1]>C:
            print(data[i]+1)
    else:
        if data[i+1]-data[i]>C and data[i]-data[i-1]>C:
            print(data[i]+1)
            

Measured memory_bytes: 65008
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;

const int dy[2]={1,0},dx[2]={0,1};
int H,W,stage[1000][1000],ansy,ansx;
int dp[1000][1000];

void solve(int y,int x){
	if(y>=H || x>=W){
		ansy = y+1; ansx = x+1;
		return;
	}
	int ny,nx;
	solve(y+dy[(stage[y][x]+dp[y][x])%2],x+dx[(stage[y][x]+dp[y][x])%2]);
}

int main(){
	int N;
	while(cin>>H>>W>>N,H||W||N){
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				cin>>stage[i][j];
				dp[i][j] = 0;
			}
		}
		dp[0][0] = N-1;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				dp[i+dy[stage[i][j]]][j+dx[stage[i][j]]] += (dp[i][j]+1)/2;
				dp[i+dy[(stage[i][j]+1)%2]][j+dx[(stage[i][j]+1)%2]] += dp[i][j]/2;
			}
		}
		solve(0,0);
		printf("%d %d\n",ansy,ansx);
	}
	return 0;
}

Measured memory_bytes: 8956
#include <iostream>
#include <unordered_set>

int parent[100010];

void init(int n) {
	for(int i = 0; i < n; i++) {
		parent[i] = i;
	}
}

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

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

void unite(int x, int y) {
	x = root(x);
	y = root(y);
	if(x == y) {
		return;
	}
	parent[x] = y;
}

int numGroup(int n) {
	int result = 0;
	for(int i = 0; i < n; i++) {
		if(parent[i] == i) {
			result++;
		}
	}
	return result;
}

int main() {
	int N, M;
	std::cin >> N >> M;

	init(N);

	for(int i = 0; i < M; i++) {
		int X, Y, Z;
		std::cin >> X >> Y >> Z;

		unite(X - 1, Y - 1);
	}

	std::cout << numGroup(N) << std::endl;

	return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>

using std::list;
using std::max;
using std::min;
using std::vector;

class Cake {
  public:
    long long x;
    long long y;
    long long z;
    void print() const;
};

void Cake::print() const
{
  printf("%lld, %lld, %lld\n", x, y, z);
}

bool x_smallest(const Cake& a, const Cake& b)
{
  return a.x < b.x;
}

bool x_largest(const Cake& a, const Cake& b)
{
  return a.x > b.x;
}

bool y_xmallest(const Cake& a, const Cake& b)
{
  return a.y < b.y;
}

bool y_largest(const Cake& a, const Cake& b)
{
  return a.y > b.y;
}

bool z_xmallest(const Cake& a, const Cake& b)
{
  return a.z < b.z;
}

bool z_largest(const Cake& a, const Cake& b)
{
  return a.z > b.z;
}

void print_all(const vector<Cake>& cake)
{
  for(const auto& c : cake) {
    c.print();
  }
}

bool long_long_largest(long long a, long long b)
{
  return a > b;
}

long long try_one_candidate(const vector<Cake>& cake, vector<long long>& tmp, int nchoice, bool x_is_negative, bool y_is_negative, bool z_is_negative)
{
  for(size_t i = 0; i < cake.size(); i++) {
    long long x, y, z;
    if(x_is_negative) {
      x = -cake[i].x;
    } else {
      x = cake[i].x;
    }
    if(y_is_negative) {
      y = -cake[i].y;
    } else {
      y = cake[i].y;
    }
    if(z_is_negative) {
      z = -cake[i].z;
    } else {
      z = cake[i].z;
    }
    tmp[i] = x + y + z;
  }
  std::sort(tmp.begin(), tmp.end(), long_long_largest);
  long long result = 0;
  for(int i = 0; i < nchoice; i++) {
    result += tmp[i];
  }
  return result;
}

long long try_all_candidate(const vector<Cake>& cake, int nchoice)
{
  vector<long long> tmp(cake.size());
  long long result = 0;
  result = max(result, try_one_candidate(cake, tmp, nchoice, false, false, false));
  result = max(result, try_one_candidate(cake, tmp, nchoice, false, false, true));
  result = max(result, try_one_candidate(cake, tmp, nchoice, false, true, false));
  result = max(result, try_one_candidate(cake, tmp, nchoice, false, true, true));
  result = max(result, try_one_candidate(cake, tmp, nchoice, true, false, false));
  result = max(result, try_one_candidate(cake, tmp, nchoice, true, false, true));
  result = max(result, try_one_candidate(cake, tmp, nchoice, true, true, false));
  result = max(result, try_one_candidate(cake, tmp, nchoice, true, true, true));
  return result;
}

int main()
{
  int ncake, nchoice;
  scanf("%d%d", &ncake, &nchoice);
  vector<Cake> cake(ncake);
  for(int i = 0; i < ncake; i++) {
    scanf("%lld%lld%lld", &cake[i].x, &cake[i].y, &cake[i].z);
  }
  //std::sort(cake.begin(), cake.end(), x_largest);
  //std::stable_sort(cake.begin(), cake.end(), y_largest);
  //std::stable_sort(cake.begin(), cake.end(), z_largest);
  //print_all(cake);
  printf("%lld\n", try_all_candidate(cake, nchoice));
  return 0;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y-1);(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()

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

int large(int n,int l){
  vector<int> v;
  rep(i,l){
    v.pb(n%10);
    n/=10;
  }
  sort(rall(v));
  int re=0;
  rep(i,l){
    re*=10;
    re+=v[i];
  }
  return re;
}
int small(int n,int l){
  vector<int> v;
  rep(i,l){
    v.pb(n%10);
    n/=10;
  }
  sort(all(v));
  int re=0;
  rep(i,l){
    re*=10;
    re+=v[i];
  }
  return re;
}

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,l;
  while(cin>>n>>l){
    if(!l)break;
    map<int,int> mp;
    for(int cnt=0;;++cnt){
      if(mp.count(n)){
	cout<<mp[n]<<" "<<n<<" "<<cnt-mp[n]<<endl;
	break;
      }
      mp[n]=cnt;
      //cout<<cnt<<","<<large(n,l)<<","<<small(n,l);
      n=large(n,l)-small(n,l);
      //cout<<":"<<n<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

template<typename T>
struct BinaryIndexedTree{
    vector<T> data;
    int sz;

    BinaryIndexedTree(int n){
        sz = n + 1;
        data.assign(sz, 0);
    }

    void add(int i, T x){
        ++i;
        while(i < sz){
            data[i] += x;
            i += i & -i;
        }
    }

    // [0, i] の区間和
    T sum(int i){
        T res = 0;
        ++i;
        while(i > 0){
            res += data[i];
            i -= i & -i;
        }
        return res;
    }

    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }

    // val 以上を満たす 0-indexed の位置を返す
    int lower_bound(T val){
        // if(val <= 0)    return -1;
        int res = 0;
        int n = 1;
        while(n < sz)   n <<= 1;
        for(int k = n >> 1; k > 0; k >>= 1){
            if(res + k < sz && data[res + k] < val){
                val -= data[res + k];
                res += k;
            }
        }
        return res;     // 1-indexed であれば、res + 1 を返す
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n);
    int maxe = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        chmax(maxe, a[i]);
    }
    int lb = 1, ub = maxe + 1;
    ll bound = (ll)n * (n + 1) >> 1;
    bound = (bound >> 1) + (bound % 2);
    while(ub - lb > 1){
        int x = (lb + ub) >> 1;
        int S = 0;
        vector<P> table;
        table.emplace_back(0, 0);
        for(int i = 0; i < n; ++i){
            S += (a[i] >= x) ? 1 : -1;
            table.emplace_back(S, i + 1);
        }
        sort(table.begin(), table.end(), greater<P>());
        BinaryIndexedTree<int> bit(n + 1);
        ll c = 0;
        for(auto p : table){
            c += bit.sum(p.second, n + 1);
            bit.add(p.second, 1);
        }
        if(c >= bound)  lb = x;
        else    ub = x;
    }
    cout << lb << endl;
}

Measured memory_bytes: 5436
from math import gcd

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        b = 1
    elif b == 0:
        a = 1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a != 0 and a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

MOD = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][1]
    else:
        a, b = d[p]
        ans *= pow(2, a, MOD) + pow(2, b, MOD) - 1
        ans %= MOD

print((ans + zero - 1) % MOD)

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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = 1;
    fact[1] = 1;
    for(int i=2; i<=num; i++){
        fact[i] = fact[i-1] * i % MOD;
    }
}

void create_seq_inv_mod(int num){
    seq_inv[0] = 1;
    seq_inv[1] = 1;
    for(int i=2; i<=num; i++){
        seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
    }
}

void create_fact_inv_mod(int num){
    fact_inv[0] = 1;
    fact_inv[1] = 1;
    for(int i=2; i<=num; i++){
        fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
    }
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

template<typename T>
struct BIT {
    int n;
    vector<T> dat;

    BIT(int n=0){
        initialize(n);
    }

    void initialize(int nin){
        n = nin;
        dat.resize(n, 0);
    }

    T sum(int i){
        T s = 0;
        while(i >= 0){
            add(s, dat[i]);
            i = (i & (i+1)) - 1;
        }
        return s;
    }

    T sum_between(int i, int j){
        return (MOD + sum(j) - sum(i-1)) % MOD;
    }

    void plus(int i, T x){
        while(i < n){
            add(dat[i], x);
            i |= i+1;
        }
    }
};

int main(){
    int N, H, D;
    cin >> N >> H >> D;

    create_mod_tables((int)1e6);

    int64_t C = 0;
    for(int i=1; i<=N; i++) add(C, fact[i]);

    BIT<int64_t> bit(H+1);
    bit.plus(0, fact[N] * inv_mod(C) % MOD);
    for(int i=1; i<=H; i++) bit.plus(i, C * bit.sum_between(i-D, i-1) % MOD);

    int64_t ans = bit.sum_between(H, H);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 31488
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
#define inf 0x7fffffff
#define pi acos(-1)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
typedef long long ll;

int n;
string s;

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout.tie(0);
	cin >> n >> s;
	
	int ans = 0;
	int l = 0, r = --n;
	while (l < r)
	{
		while (l <= n && s[l] == 'R') l++;
        while (r >= 1 && s[r] == 'W') r--;
        if (l < r) swap(s[l], s[r]), ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3732
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;

#define int long long

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)
#define rrep(i, s) rep(i, s, >= 0, --)

#define all(c) begin(c), end(c)
template<typename T>bool maxup(T& a, T&& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool maxup(T& a, T& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool minup(T& a, T&& b) { if (a > b) { a = b; return true; }; }
template<typename T>bool minup(T& a, T& b) { if (a > b) { a = b; return true; }; }

#define X first
#define Y second

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

signed main() {
	int N, K, L; cin >> N >> K >> L;
	
	UnionFind a(N), b(N);
	rep(i, K) {
		int p, q; cin >> p >> q;
		p--; q--;
		a.unionSet(p, q);
	}
	rep(i, L) {
		int p, q; cin >> p >> q;
		p--; q--;
		b.unionSet(p, q);
	}
	map<P, int> s;
	rep(i, N) {
		s[{ a.root(i), b.root(i) }]++;
	}
	rep(i, N) {
		cout << s[{ a.root(i), b.root(i) }] << " ";
	}
	cout << endl;

	system("pause");
}

Measured memory_bytes: 15352
// https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
const int MOD = 998244353;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> C(N);
    int ans = 1;
    REP(i, N) {
        int d;
        cin >> d;
        if (i == 0 ^ d == 0)
            ans = 0;
        C[d]++;
    }
    FOR(d, 2, N) REP(i, C[d]) ans = ans * C[d - 1] % MOD;
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  REP(i, N)
  cin >> S[i];
  string ans = "";
  sort(ALL(S));
  REP(i, N)
  ans += S[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import fractions
from functools import reduce

n,x = map(int,input().split())
base = list(map(int,input().split()))
base_1 = [0]*n

for i in range(n):
  base_1[i] = base[i] - x
  
ans = reduce(fractions.gcd,base_1)
print(abs(ans))

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

using namespace std;
using ll = long long;
using ld = long double;

//#define int long long
//signed main(){
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,q;
    cin >> a >> b >> q;
    vector<ll> s(a+2);
    vector<ll> t(b+2);
    s[0]=-1e11;
    t[0]=-1e11;
    for(int i = 0; i < a; i++) {
        cin >> s[i+1];
    }
    for(int i = 0; i < b; i++) {
        cin >> t[i+1];
    }
    s[a+1]=1e11;
    t[b+1]=1e11;
    for(int i = 0; i < q; i++) {
        ll x;
        cin >> x;
        ll ls,rs,lt,rt;
        auto sit=lower_bound(s.begin(),s.end(),x);
        auto tit=lower_bound(t.begin(),t.end(),x);
        ls= x - *(sit-1);
        rs= *(sit)   - x;
        lt= x - *(tit-1);
        rt= *(tit)   - x;
        ll route[4];
//        cout << ls << " " << rs << " " << lt << " " << rt << "\n";


        route[0]=max(rt,rs);
        route[1]=max(lt,ls);
        route[2]=lt+rs+min(lt,rs);
        route[3]=rt+ls+min(rt,ls);
//        cout << route[0] << " " << route[1] << " " << route[2] << " " << route[3] << "\n";
        cout << min({route[0], route[1], route[2], route[3]}) << "\n";
    }

    return 0;
}

Measured memory_bytes: 4724
// D - Negative Cycle
#include <bits/stdc++.h>

using namespace std;

#define	INF	1e16

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n;
	cin >> n;
	vector<vector<long long> > a(n, vector<long long>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (i != j) cin >> a[i][j];

	vector<vector<long long> > dp(n + 1, vector<long long>(n + 1, INF));
	dp[0][0] = 0;

	for (int i = 1; i <= n; i++) {
		vector<long long> c(i), d(i);
		for (int j = 1; j < i; j++) {
			for (int k = i; k < n; k++) c[j] += a[k][j - 1];
			c[j] += c[j - 1];
		}
		for (int j = i - 2; j >= 0; j--) {
			for (int k = j + 1; k < i; k++) d[j] += a[j][k];
			d[j] += d[j + 1];
		}
		for (int j = 0; j < i; j++)
			for (int k = 0; k <= j; k++)
				dp[i][j] = min(dp[i][j], dp[j][k] + c[j] - c[k] + d[j]);
	}

	cout << *min_element(dp[n].begin(),dp[n].end()) << endl;

	return 0;
}


Measured memory_bytes: 4224
import java.util.*;

class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        //タップダンスの動きを取得する
        String allStep = sc.next();
        //1文字ずつに分解する
        String[] stepArray = allStep.split("");
        
        
        //踏みやすいステップかどうかのフラグを設定する
        boolean easyStepFlg = true;
        
        //結果出力用の文字列を定義する
        String result = "";
        
        //踏みやすいかどうかを判定する
        for(int i = 0; i < stepArray.length; i++) {

          	//奇数偶数で分岐する文字判定ロジック
            if(i % 2 == 0) {
            // 奇数文字目：L以外なら踏みやすい
            // リストとしては0番目から始まるため、iが偶数の場合となる
                if(stepArray[i].equals("L")) {
                    easyStepFlg = false;
                }
            } else if (i % 2 == 1) {
            // 偶数文字目：R以外なら踏みやすい（iが奇数の場合を判定する）
                if(stepArray[i].equals("R")) {
                    easyStepFlg = false;
                }
            } else {
                //普通はここに入らないが念の為falseにしておく
                easyStepFlg = false;
            }
            
            //L,R,U,Dのいずれでもない場合は踏みにくいためfalseとする
            if(!(stepArray[i].equals("L") || stepArray[i].equals("R") || stepArray[i].equals("U") || stepArray[i].equals("D"))) {
                easyStepFlg = false;
            }
            
            //踏みやすいかどうかフラグがfalseになったらfor文を抜けて処理を終わらせる
            if(!easyStepFlg) {
                break;                
            }
        }
        
        //for文を最後まで回して踏みやすいフラグがtrueのままならYes、ダメな場合はNoを結果に詰める
        if(easyStepFlg) {
            result = "Yes";
        } else {
            result = "No";
        }

        //判定の結果を出力する
        System.out.println(result);
    }    
}

Measured memory_bytes: 23124
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] b = new int[n - 1];
        for (int i = 0 ; i < n - 1 ; i++) {
            b[i] = sc.nextInt();
        }
        int max = 0;
        int[] a = new int[n];
        a[0] = b[0];
        for (int i = 1 ; i < n - 1 ; i++) {
            a[i] = Math.min(b[i - 1], b[i]);
        }
        a[n - 1] = b[n - 2];
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            sum += a[i];
        }
        System.out.println(sum);
    }

}

Measured memory_bytes: 21844
N = int(input())
A = list(map(int, input().split()))
R = [0] * 8
A.sort()
c = 0
for a in A:
    if 1 <= a < 400:
        R[0] = 1
    elif 400 <= a < 800:
        R[1] = 1
    elif 800 <= a < 1200:
        R[2] = 1
    elif 1200 <= a < 1600:
        R[3] = 1
    elif 1600 <= a < 2000:
        R[4] = 1
    elif 2000 <= a < 2400:
        R[5] = 1
    elif 2400 <= a < 2800:
        R[6] = 1
    elif 2800 <= a < 3200:
        R[7] = 1
    else:
        c += 1

if c != 0 and not 1 in R:
    mi = 1
else:
    mi = R.count(1)
ma = R.count(1) + c

print(mi, ma)

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

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

    int a,b;
    int k;
    cin>>k;
    cin>>a>>b;
    for(int i=a; i<=b; ++i)
    {
        if(i%k==0)
        {
            cout<<"OK"<<"\n";
            return 0;
        }
    }
    cout<<"NG"<<"\n";
    return 0;
}


Measured memory_bytes: 3648
package main

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

var N, T, ans int

func main() {
	fmt.Scan(&N, &T)
	reader := bufio.NewScanner(os.Stdin)
	reader.Split(bufio.ScanWords)

	t := make([]int, N)
	for i := 0; i < N; i++ {
		reader.Scan()
		t[i], _ = strconv.Atoi(reader.Text())
	}

	for i := 0; i < N-1; i++ {
		if T < t[i+1]-t[i] {
			ans += T
		} else {
			ans += t[i+1] - t[i]
		}
	}

	fmt.Println(ans + T)
}

/*  ----------------------------------------  */

func gcd(x, y uint64) uint64 {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

func combination(x, y int) int {
	return permutation(x, y) / permutation(y, y)
}

func permutation(x, y int) int {
	var ans int = 1
	for i := x - y; 0 < i; i-- {
		ans *= i
	}
	return ans
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}

func pow(x, y int) uint64 { return uint64(math.Pow(float64(x), float64(y))) }
func abs(x int) int       { return int(math.Abs(float64(x))) }
func floor(x int) int     { return int(math.Floor(float64(x))) }

type si struct {
	s int
	i int
}

type SortBy []si

func (a SortBy) Len() int           { return len(a) }
func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool { return a[i].s < a[j].s }


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

struct Edge {
  int to;
  int a;
  int b;
};

struct State {
  int pos;
  int s;
  ll time;
  bool operator < (const State &o) const {
    return time > o.time;
  }
};

const int MAX_N = 55;
vector<Edge> g[MAX_N];

int C[MAX_N];
int D[MAX_N];

const int MAX_S = 5550;
ll memo[MAX_N][MAX_S];

int main2() {
  REP(i, MAX_N) g[i].clear();

  int N = nextInt();
  int M = nextInt();
  int S = nextInt();
  if (S >= 5000) S = 5000;

  REP(i, M) {
    int u = nextInt();
    int v = nextInt();
    int a = nextInt();
    int b = nextInt();
    g[u].push_back((Edge){v, a, b});
    g[v].push_back((Edge){u, a, b});
  }
  REP(i, N) {
    C[i+1] = nextInt();
    D[i+1] = nextInt();
  }

  const ll INF = 1LL << 61;
  REP(i, MAX_N) REP(j, MAX_S) memo[i][j] = INF;

  priority_queue<State> pq;
  pq.push((State){1, S, 0LL});
  memo[1][S] = 0;
  while (!pq.empty()) {
    State cur = pq.top(); pq.pop();
    for (Edge e : g[cur.pos]) {
      State n_state = cur;
      n_state.pos = e.to;
      n_state.s -= e.a;
      n_state.time += e.b;
      if (n_state.s < 0) continue;
      if (memo[n_state.pos][n_state.s] > n_state.time) {
        memo[n_state.pos][n_state.s] = n_state.time;
        pq.push(n_state);
      }
    }

    {
      State n_state = cur;
      n_state.s += C[cur.pos];
      if (n_state.s >= 5000) n_state.s = 5000;
      n_state.time += D[cur.pos];
      if (memo[n_state.pos][n_state.s] > n_state.time) {
        memo[n_state.pos][n_state.s] = n_state.time;
        pq.push(n_state);
      }
    }

  }

  vector<ll> ans(MAX_N + 1, INF);
  for (int t = 2; t <= N; t++) {
    for (int s = 0; s < MAX_S; s++) {
      chmin(ans[t], memo[t][s]);
    }
  }
  for (int t = 2; t <= N; t++) {
    cout << ans[t] << endl;
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 9712
#include <stdio.h>

int main() {
	char matriz[4][4];
	int y=0,c=0;
	for(int x = 0;x<3;++x){
		scanf("%s",&matriz[x][y]);
		++y;
	}
	for(int z = 0;z<3;++z){
		printf("%c",matriz[z][z+c]);
		++c;
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

def factorize(n):
    factor = []
    if n % 2 == 0:
        f = [2, 1]
        n //= 2
        while n % 2 == 0:
            n //= 2
            f[1] += 1
        factor.append(f)

    k = 3
    while k * k <= n:
        if n % k == 0:
            f = [k, 1]
            n //= k
            while n % k == 0:
                n //= k
                f[1] += 1
            factor.append(f)
        k += 2
    if n != 1:
        factor.append([n, 1])
    return factor

a, b = map(int, input().split())
c = gcd(a, b)
f = factorize(c)
print(len(f) + 1)


Measured memory_bytes: 61880
/*
 *  Lang    : C++
 *  Author  : little_angel
 */
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

//#define int long long
#define oset tree < int , null_type , less<> , rb_tree_tag , tree_order_statistics_node_update >
const int mod = 998244353;
//const int inf = 1e18;
const int MAX = 1e6 + 10;

//    auto random_address = [] {
//        char *p = new char;
//        delete p;
//        return (uint64_t) p;
//    };
//    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1ull));


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i:a)cin >> i;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    sort(a.begin(), a.end());
    unordered_set<int> m;
    vector<int> dp(n);
    dp[0] = (a[0] != a[1]);
    m.insert(a[0]);
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j * j <= a[i]; ++j) {
            if (a[i] % j == 0) {
                if (m.count(j) or m.count(a[i] / j)) {
                    dp[i] = -1;
                    break;
                }
            }
        }
        if (!dp[i]) {
            if (i < n - 1)dp[i] = a[i] != a[i + 1];
            else dp[i] = 1;
        }
        m.insert(a[i]);
    }
    cout << count(dp.begin(), dp.end(), 1ll) << endl;
}

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


int main() {
    ll N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    --A;
    --B;
    --C;
    --D;

    for (int i = A; i < C; ++i) {
        if (S.at(i) == '#' && S.at(i+1) == '#') {
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = B; i < D; ++i) {
        if (S.at(i) == '#' && S.at(i+1) == '#') {
            cout << "No" << endl;
            return 0;
        }
    }
    if (C < D) cout << "Yes" << endl;
    else {
        rep(i,N-2) {
            if (S.at(i) == '.' && S.at(i+1) == '.' && S.at(i+2) == '.' 
            && B <= i + 1 && i + 1 <= D) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
typedef long long ll;
const int N=100005;
int n,m,Q,x[N],y[N];
map<pair<int,int> ,int> a;
ll ans[10];
void solve(int l,int r){
	if (l<1||r<1||l+2>n||r+2>m)return;
	int v=0;
	for (int i=0;i<=2;i++)
		for (int j=0;j<=2;j++)
			v+=a.count(mp(l+i,r+j));
	ans[v]++;
}
int main(){
	scanf("%d%d%d",&n,&m,&Q);
	for (int i=1;i<=Q;i++){
		scanf("%d%d",&x[i],&y[i]);
		a[mp(x[i],y[i])]=1;
	}
	for (int i=1;i<=Q;i++)
		for (int j=0;j<=2;j++)
			for (int k=0;k<=2;k++)
				solve(x[i]-j,y[i]-k);
	for (int i=1;i<=9;i++)ans[i]/=i;
	for (int i=1;i<=9;i++)ans[0]-=ans[i];
	ans[0]+=(ll)(n-2)*(m-2);
	for (int i=0;i<=9;i++)printf("%lld\n",ans[i]);
}


Measured memory_bytes: 7296
N = int(input())
L = list(map(int, input().split()))

c = 0
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if L[i] + L[j] > L[k] and L[j] + L[k] > L[i] and\
            L[k] + L[i] > L[j] and L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
                c += 1
print(c)

Measured memory_bytes: 73968
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
const int mod=1e9+7;
inline ll fpm(ll a,ll p){
	ll res=1;
	while(p){
		if (p&1) res=res*a%mod;
		a=a*a%mod;
		p/=2;
	}
	return res;
}
ll mem[maxn];
inline ll inv(ll x){
	return fpm(x,mod-2);
}
int main(){
	int n;
	cin>>n;
	ll ans=0;
	if (n==1){
		cout<<"0"<<endl;
		return 0;
	}
	for (int i=n;i>=1;i--){
		mem[i]=fpm(9,i)*fpm(10,n-i)%mod;
		mem[i]=(mem[i]+mem[i+1])%mod;
	}
	for (int i=1;i+1<=n;i++){
		ll tp=fpm(8,i-1)*inv(fpm(9,i+1))%mod*mem[i+1];
		ans=(ans+tp*2%mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 11408
#include<iostream>
using namespace std;
int main(){
  int n, d;
  cin >> d >> n;
  if(d == 0 && n != 100){
    cout << n << "\n";
  }else if(d == 1 && n != 100){
    cout << n * 100 << "\n";
  }else if(d == 2 && n != 100){
    cout << n * 10000 << "\n";
  }else if(d == 0){
    cout << 101 << "\n";
  }else if(d == 1){
    cout << 10100 << "\n";
  }else{
    cout << 1010000 << "\n";
  }
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException;
import java.util.stream.Stream;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        int n = 0;
        int[] A = Arrays.stream(getContents().get(1).split(" ")).mapToInt(Integer::parseInt).toArray();
        for(int i = 0, len = A.length; i < len; ++i){
            int j = minIndex(A, i);
            if(A[i] != A[j]){
                int v = A[i];
                A[i] = A[j];
                A[j] = v;
                ++n;
            }
        }
        System.out.println(String.join(" ", Arrays.stream(A).mapToObj(String::valueOf).toArray(String[]::new)));
        System.out.println(String.valueOf(n));
    }
    
    public static ArrayList<String> getContents() throws IOException{
        String line;
        ArrayList<String> list = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while((line = br.readLine()) != null) list.add(line);
        
        return list;
    }
    
    public static int minIndex(int[] A, int i){
        int j = i;
        for(int len = A.length; i < len; ++i)
            if(A[i] < A[j]) j = i;
        return j;
    }
}


Measured memory_bytes: 31108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define INF 1000000000000000
#define fi first
#define se second
#define all(v) v.begin(),v.end()
typedef pair<int, int> P;
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
struct edge { int to, cost; };
int a, b, c;
signed main() {
	cin >> a >> b >> c;
	if (a < c && c < b)puts("Yes");
	else if (b < c && c < a)puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	  public static void main(String[] args) {
		    Scanner sc = new Scanner(System.in);
		    int N = sc.nextInt();
		    int x[] = new int[N];
		    int y[] = new int[N];
		    
		    for (int i = 0; i < N; i++) {
		      x[i] = sc.nextInt();
		      y[i] = sc.nextInt();
		    }
        	double sum = 0.0;
 			for(int i = 0; i < N; i++){
      			for(int j = i + 1; j < N; j++){
            	  sum += Math.sqrt((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]));
                }
            }
	        System.out.print(sum * 2/ N);
	  }
}

Measured memory_bytes: 22100
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
const int MX = 300005;
int n, a[MX], b, un[MX], t, av[MX];
int main(){
	scanf("%d", &n);
	rep(i,n){
		scanf("%d", &b);
		a[b-1]++;
	}
	sort(a,a+n, greater<int>());
	un[n] = n; av[n] = 1;
	for(int i = n-1; i > 0; i--){
		for(;a[t] > i; t++);
		un[i] = un[i+1] - t;
		av[i] = un[i] / i;
	}
	av[0] = n;t = n;
	rep(i,n){
		for(; av[t] < i+1; t--);
		printf("%d\n", t);
	}
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)

//累積和的なものを考えると良いらしい
int main() {
    string s;
    cin >> s;
    ll n = s.size();
    vector<ll> a(2019, 0);
    ll fac = 1;
    ll cur = 0;
    a[cur]++;
    rep1(i, n){
        //1桁目から順になめていく
        ll add = s[n-1-i] - '0';
        //i桁目までの数のあまりを考えていけばよい
        cur = (cur + fac*add) % 2019;
        //倍数を増やしていけばいい
        fac = (fac*10) % 2019;
        //mod2019の値に合わせて格納
        a[cur]++;
    }
    ll ans = 0;
    rep1(i, a.size()){
        ans += a[i]*(a[i]-1)/2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3760
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = []
for _ in range(M):
    AB.append(list(map(int, input().split())))

good = [1 for _ in range(N)]

for ab in AB:
    if H[ab[0]-1] > H[ab[1]-1]:
        good[ab[1]-1] = 0
    elif H[ab[0]-1] < H[ab[1]-1]:
        good[ab[0]-1] = 0
    elif H[ab[0]-1] == H[ab[1]-1]:
        good[ab[0]-1] = 0
        good[ab[1]-1] = 0

print(good.count(1))

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


#define rep(i, a, b) for(long long i = a; i < (b); ++i)
#define repdown(i, a, b) for(long long i = a; i >= b; --i)
#define all(x) x.begin(), x.end()
#define bfs(a) while(a.size())

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vector<ll>> vvi;
typedef vector<vector<double>> vvd;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<pdd> vpdd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
vi inl(1e6), inh(1e6);
ll n, best = 0;
void dp(ll ind, ll la, ll ha, ll lb, ll hb, bool a, bool b){
	ll happy = max(ll(0), ha-la) + max(ll(0), hb- lb);
	if(happy <= best)return;
	if( ind == n){
		if(a and b){
			//cout<<la<<' '<<ha<<'.'<<lb<<' '<<hb<<'.'<<happy<<endl;
			best = happy;
		}
		return;
	}
	ll l = inl[ind]-1, h = inh[ind];
	ind++;
	dp(ind, max(la, l), min(ha, h), lb       , hb       , 1, b);
	dp(ind, la        , ha        ,max(lb, l),min(hb, h), a, 1);
	return;
}
int main() {    
	cin.sync_with_stdio(0); cin.tie(0);    cin.exceptions(cin.failbit);//OUTPUT MANAGEMENT

	cin>>n;
	rep(i,0,n)cin>>inl[i]>>inh[i];
	dp(0 , 0 , 1e9, 0, 1e9, 0, 0);
	cout<<best<<endl;

	
}

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

//LIFE IS NOT A PROBLEM TO BE SOLVED

#define rep(i,a,b) for( int i = (int) a; i < (int) b; i++ )
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define debug(a) cout << #a << " = " << a << endl;
#define debug2(a,b) cout << #a << " = " << a << " --- " << #b << " = " << b << endl;
#define debugP(a) cout << a.F << " " << a.S << endl;
#define debugM(mat,n,m) rep( i, 0, n ){ rep( j, 0, m ) cout << mat[i][j] << " "; cout << endl; }

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

int dp[200020], pos[200020], n[200020], N;

int solve(int i){
	if(n[i]==N) return dp[i] = 1;
	if(dp[i]!=-1) return dp[i];
	dp[i] = 1;
	if(pos[n[i]+1] > i)
		dp[i] += solve(pos[n[i]+1]);
	return dp[i];
}

int main(){
	
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	
	
	scanf("%d", &N);
	rep(i, 1, N+1){
		scanf("%d", &n[i]);
		pos[n[i]] = i;
	}
	
	memset(dp, -1, sizeof dp);
	
	rep(i, 1, N+1) dp[i] = solve(i);
	
	//rep(i, 1, N+1) cout << i << " " << dp[i] << '\n';
	
	int ans = N;
	rep(i, 1, N+1) ans = min(ans, N-dp[i]);
	
	cout << ans << "\n";
	
	
	return 0;
}

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

using namespace std;

using ll = long long;

template <class T>
struct FenwickTree {
    int n;
    std::vector<T> x;
    FenwickTree(int _n = 0) : n(_n), x(n + 1, 0) {}
    int size() const { return n; }
    T Sum(int r) const {
        T S = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
        return S;
    }
    T Sum(int l, int r) const { return Sum(r) - Sum(l); }
    void Add(int k, const T &a) {
        for (; k < n; k |= k + 1) x[k] += a;
    }
    void Set(int k, const T &a) { Add(k, a - Sum(k, k + 1)); }
};


class ProblemD {
public:
    ProblemD(ll _n) : n(_n), a(_n + 1), s(_n + 1, 0) {}
    void Input() { for (int i = 1; i <= n; ++i) cin >> a[i]; }

    int Solve() {
        const ll lim = ceil(n * (n + 1) / 4.0);

        ll lb = 0, ub = *max_element(a.begin(), a.end()) + 1;
        while (ub - lb > 1) {
            ll mid = 0.5 * (lb + ub), res = Check(mid);

            if (lim <= res) lb = mid;
            else ub = mid;
        }

        return lb;
    }

private:
    ll n;
    vector<int> a;
    vector<ll> s;

    ll Check(const int x) {
        for (int i = 1; i <= n; ++i) s[i] = (x <= a[i] ? 1 : -1) + s[i - 1];

        ll res = 0;
        FenwickTree<int> tree(2 * n + 1);

        tree.Add(s[0] + n, 1);
        for (int i = 1; i <= n; ++i) {
            res += tree.Sum(0, s[i] + n + 1);
            tree.Add(s[i] + n, 1);
        }

        return res;
    }
};

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

    int n;
    cin >> n;
    ProblemD p(n);
    p.Input();
    cout << p.Solve() << endl;

    return 0;
}


Measured memory_bytes: 2288
# Problem https://atcoder.jp/contests/abc082/tasks/abc082_a
# Python 2nd Try


def solver(a, b):
    answer = 0
    answer = (a + b + 1) // 2
    return answer


if __name__ == "__main__":
    a, b = map(int, input().split(' '))
    answer = 0
    answer = solver(a, b)
    print(answer)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,r) for (int i = 0; i < r; i++)
#define repeq(i,r) for (int i = 0; i <= r; i++)

int main() {
  int N;
  cin >> N;
  int X[N];
  rep(i,N) {
    scanf("%d", &X[i]);
  }
  
  int m = N * 100 * 100;
  rep(i,100) {
    int s = 0; 
    rep(j,N) {
      s += (X[j] - i) * (X[j] - i);
    }
    if (s < m) {
      m = s;
    } else {
      cout << m << endl;
      break;
    }
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int r;

	scanf("%d", &r);

	if (r < 1200) {
		printf("ABC");
	}
	else if (r < 2800) {
		printf("ARC");
	}
	else {
		printf("AGC");
	}

	getchar(); getchar();
}

Measured memory_bytes: 128