akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
main(){
	int n,i,start,M;
	double x,y,dX,dY,dx,dy,dot,n1,n2,co,m;
	for(;scanf("%d",&n),n;){
		vector<pair<pair<double,double>,int> >v;
		for(i=0;i<n;i++)scanf("%lf,%lf",&x,&y),v.push_back(make_pair(make_pair(x,y),i));
		pair<pair<double,double>,int>p=*min_element(v.begin(),v.end());
		dX=0,dY=-1;
		start=p.second;
		vector<int>V;
		for(;;){
			m=-1,M=0;
			for(i=0;i<n;i++){
				if(i==p.second)continue;
				dx=v[i].first.first-p.first.first,dy=v[i].first.second-p.first.second;
				dot=dX*dx+dY*dy;
				n1=hypot(dX,dY),n2=hypot(dx,dy);
				co=dot/n1/n2;
				//printf("%f\n",co);
				if(m<co)m=co,M=i;
			}
			if(M==start)break;
			V.push_back(M);
			//printf("---%d %d\n",M,start);
			dX=v[M].first.first-p.first.first,dY=v[M].first.second-p.first.second;
			p=v[M];
		}
		printf("%d\n",n-V.size()-1);
	}
}

Measured memory_bytes: 1112
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		long lNum = s.nextInt();
		long rNum = s.nextInt();
		s.close();
		long min = 2019;
		if (lNum / 2019 == rNum / 2019) {
			for (long i = lNum; i < rNum; i++) {
				for (long j = i + 1; j <= rNum; j++) {
					long amari = (i * j) % 2019;
					if (amari < min) {
						min = amari;
					}
					if(amari == 0) {
						min = 0;
						break;
					}
				}
			}
		}else {
			min = 0;
		}
		System.out.println(min);

	}

}


Measured memory_bytes: 23124
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;

int main(){
  string s;
  cin>>s;
  int k=s[9]-'0'+(s[8]-'0')*10+(s[6]-'0')*100+(s[5]-'0')*1000+(s[3]-'0')*10000+(s[2]-'0')*100000+(s[1]-'0')*1000000+(s[0]-'0')*10000000;
  if(k<=20190430)cout<<"Heisei"<<endl;
  else cout<<"TBD"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007

ll ceil1(ll a,ll b)
{	if(a%b==0)
		return a/b;
	else
		return a/b+1;}


void solve()
{
	ll a,b;
	cin>>a>>b;
	if(a==b)
	{
		cout<<"Draw";
	}
	else if(a==1)
	{
		cout<<"Alice";
	}
	else if(b==1)
		cout<<"Bob";
	else if(a>b)
	{
		cout<<"Alice";
	}
	else
		cout<<"Bob";
	return;
}

int main()
{
	fast;
	ll q=1;
	// cin>>q;
	while(q--)
		solve();
	return 0;
}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int n; cin >> n;
	vector<Int> p(n);
	for(auto &i:p) cin >> i;
	Int ans = 0;
	Int mi = n+1;
	for(Int i=0; i<n; ++i){
		if(mi >= p[i]) ++ans;
		mi = min(mi, p[i]);
	}
	cout << ans << "\n";
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string.h>
using namespace std;
#define pb push_back
#define all(v) v. begin(),v. end()
#define  rep(i,n,v) for(i=n;i<v;i++)
#define per(i,n,v) for(i=n;i>v;i--)
#define ff first 
#define ss second 
#define pp pair<ll,ll>
#define ll  long long
#define endl '\n'
void solve()
{
  ll n, a,m=0,b=1, c,k=0, i, j,l=1e9+7;
  string s, r, y;
  cin>>n>>a;
  ll ar[n];
  rep(i,0,n) cin>>ar[i];
  sort(ar,ar+n);
  rep(i,0,a) k+=ar[i];
  cout<<k<<endl;
}
int main()
{
 ios_base::sync_with_stdio(false);
  cin. tie(0);cout. tie(0);
    ll t=1;
  // cin>>t;
    while(t--)
    {
      solve();
    }
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; --i)
#define FOR(i, n, m) for (int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

typedef long long ll;
/**
 * C問以降は ll を使う.
 * double型にするのを忘れない.
 * nC2の求め方 (1/2)*n*(n-1)
 * vector<型> 変数名(要素数, 初期値)
 */
int main()
{
    string S;
    cin >> S;
    int count = 0;
    REP(i, S.length())
    {
        if((i%2 == 1 && S.at(i) == 'R') || (i%2 == 0 && S.at(i) == 'L')) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>

using namespace std;

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

long long int INF = 1e18;
long long int mod = 1000000007;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "RULD";
//↓,→,↑,←

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl

ll rui(ll number1,ll number2){
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
    if(number1 > number2){
        swap(number1 , number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1 , number1);
    }
}

ll i,j,k,ii,jj,n,m,a,b,c,d,e,f,g,h,r,w,l,num,ans,sum,ok,ng,mid;
ll x[500005],y[500005],z[500005];
bool used[500005];
char s[500005],t[500005],u[500005];
bool dame,flag;
//string s;

int main(){
	for(i=0;i<3;i++){
		cin >> a >> b;
		x[a]++;
		x[b]++;
	}
	for(i=1;i<=4;i++){
		if(x[i] == 1)c++;
		if(x[i] == 2)d++;
	}
	if(c == 2 && d == 2){
		p("YES");
	}else{
		p("NO");
	}
	return 0;
}

Measured memory_bytes: 27136
#include<bits/stdc++.h>
using namespace std;
int main(){
  int j,n,x;
  cin>>j; n=j;
  vector<int> rec(n,0);
  while(n-- > 1){
      cin>>x;
      rec[x-1] = rec[x-1] + 1;
  }
  for(int i = 0; i < j; ++i){
      cout<<rec[i]<<endl;
  }
  return 0;
}

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

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;

int n, m;
int a[MAXN];
int b[MAXN];

void init ();
void input ();
void work ();

bool check ( int tst );



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d", &n );
	m = ( n << 1 ) - 1;
	lpi ( i, 1, m ) scanf ( "%d", &a[i] );
}

void work ()
{
	// main work
	
	int l = 1, r = m, mid;
	while ( l < r ){
		mid = ( l + r + 1 ) >> 1;
		if ( check ( mid ) ) l = mid;
		else r = mid - 1;
	}
	
	cout << l << endl;
}



bool check ( int tst )
{
	lpi ( i, 1, m ) b[i] = a[i] >= tst;
	
	int mp = -1;
	lpi ( i, 2, m ){
		if ( b[i] == b[i-1] ){
			if ( i <= n && n - i < qabs ( n - mp ) ) mp = i;
			else if ( i - 1 - n < qabs ( n - mp ) ) mp = i - 1;
		}
	}
	
	if ( mp == -1 ) return ( b[n] ^ ( ~n & 1 ) );
	else return b[mp];
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define lli long long int
#define ulli unsigned long long int
#define ld long double
#define loop(i,m,n) for(lli i=m;i<=n;i++)
#define loopr(i,m,n) for(lli i=m;i>=n;i--)
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define pii pair<int,int>
#define vpii vector<ii>
#define INF 1000000000
#define mod 1000000007
#define siz 1000001
#define endl "\n"
const double PI=3.14159265358979323846264338327950288419716939937510;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;

int main()
{
	int n,i,j;
	cin>>n;
	pair<int,int> pp[n];
	for(i=0;i<n;i++)
	{
		cin>>pp[i].ff>>pp[i].ss;
	}
	for(i=0;i<=n-3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(pp[i+j].ff!=pp[i+j].ss)
				break;
		}
		if(j==3)
		{
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
//#include <boost/lexical_cast.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define mp make_pair
#define endl '\n'
#define PI acos(-1)
#define P pair<int,int>
typedef tree<int,null_type,less_equal <int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

long mod=1e9+7;
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	vector<int> v[m];
	for(int i=0;i<m;i++)
	{
		int k;
		cin>>k;
		while(k--)
		{
			int a;
			cin>>a;
			v[i].pb(a);
		}
		sort(v[i].begin(),v[i].end());
	}
	int parity[m];
	for(int i=0;i<m;i++)cin>>parity[i];
	int ans=0;
	for(int i=0;i<(1<<n);i++)
	{
		bool on[n+1]={0};
		for(int j=0;j<n;j++)
		{
			if(i&(1<<j))
			{
				on[j+1]=1;
			}
		}
		bool is_ans=1;
		for(int i=0;i<m;i++)
		{
			int temp=0;
			for(auto u:v[i])
			{
				if(on[u])
					++temp;
			}
			if(temp%2!=parity[i])
				is_ans=0;
		}
		if(is_ans)
			++ans;
	}
	cout<<ans;
	return 0;
}

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

int n,k,r,s,p;
string t;

int main() {
  cin >> n >> k >> r >> s >> p >> t;
  int ans=0;
  rep(i,n){
    if(i<k){
    if(t[i]=='r') ans+=p;
    if(t[i]=='s') ans+=r;
    if(t[i]=='p') ans+=s;
    } else{
      if(t[i-k]==t[i]) t[i]='a';
      else if(t[i]=='r') ans+=p;
      else if(t[i]=='s') ans+=r;
      else if(t[i]=='p') ans+=s;
    }
  } 
  cout << ans << endl; 
}

Measured memory_bytes: 512
from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))

ans = 0
l.sort()

for i in range(n):
    for j in range(i + 1, n):
        a = l[i]
        b = l[j]
        idx = bisect_left(l, a + b)
        # print(a, b, idx)

        ans += idx - (j + 1)


print(ans)


Measured memory_bytes: 3188
#include<iostream>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<ctype.h>
#include<unordered_set>
#include<string>
#include<iomanip>
#include<queue>
#include<limits>
#include<map>
#include<stack>
#include<iterator>
#include<deque>
#define MOD 1000000009
#define INF 9999999999999 
#define pb push_back
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;
ll ncr(ll n, ll r)
{
	ll i, ans = 1, k = 0;
	if (r == 0)
		return 1;
	else if (n < r)
		return 0;
	for (i = n; i >= n - r + 1; i--)
	{
		ans *= i;
		ans /= n - i + 1;
	}


	return ans;

}
bool visited[6] = { false };
int n = 6;
vector<int> adj[6];


void max_heapify(int a[100], int i)
{
	int l, r, largest = i;
	l = 2 * i + 1;
	r = 2 * i + 2;
	if (l<n && a[l]>a[i])
		largest = l;
	if (r<n && a[r]>a[l])
		largest = r;
	if (largest != i)
	{
		int k;
		k = a[i];
		a[i] = a[largest];
		a[largest] = k;
		max_heapify(a, largest);
	}

}
int power(ll x, ll y, ll p)
{
	int res = 1;
	x = x % p;

	while (y > 0)
	{

		if (y & 1)
			res = (res * x) % p;


		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

bool square(ll n)
{
	double x;
	x = sqrt(n);
	if (x == floor(x))
		return true;
	else return false;
}


bool prime(ll n)
{
	ll i;
	for (i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}
void dfs(ll a, ll b, vector<pair<ll, ll>>adj[][1001], bool visited[][1001])
{
	visited[a][b] = true;
	for (auto u : adj[a][b])
	{
		if (!visited[get<0>(u)][get<1>(u)])
		{
			visited[get<0>(u)][get<1>(u)] = true;
			dfs(get<0>(u), get<1>(u), adj, visited);
		}
	}
}
ll modi(ll a, ll m)
{
	return power(a, m - 2, m);

}
void kmp(string s, ll pi[]) {
	int n = (int)s.length();
	pi[0] = 0;
	for (int i = 1; i < n; i++) {
		int j = pi[i - 1];
		while (j > 0 && s[i] != s[j])
			j = pi[j - 1];
		if (s[i] == s[j])
			j++;
		pi[i] = j;
	}

}
struct pair_hash {
	size_t operator()(const pair<int, int>& p) const noexcept {
		return hash<ll>() ((((ll)p.first) << 32) | ((ll)p.second));
	}
};


int main() {
	fast;
	double h, w;
	cin >> h >> w;
	if (h != 1 && w != 1)
	{
		ll ans = ceil((h * w) / 2);
		cout << ans;
	}
	else
		cout << 1;
	return 0;
}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector <int> ans(N, 0);
    vector <bool> dfnd(N, false);
    for (int i=0; i<M; i++) {
        int s,c;
        cin >> s >> c;
        if (dfnd.at(s-1) && ans.at(s-1)!=c) {
            cout << "-1";
            return 0;
        }
        else {
            dfnd.at(s-1) = true;
            ans.at(s-1) = c;
        }
    }
    if (ans.at(0)==0 && N!=1) {
        if (dfnd.at(0)) {
            cout << "-1";
            return 0;
        }
        else ans.at(0)=1;
    }
    for (int i=0; i<N; i++) cout << ans.at(i);
}

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

int bfs(vector<string> &maze, vector<vector<int> > &moving_count, int i, int j, int H, int W){
    if (maze[i][j] == '#'){
        return 0;
    }
    vector<int> dx(4);
    dx[0] = 1;
    dx[1] = 0;
    dx[2] = -1;
    dx[3] = 0;
    vector<int> dy(4);
    dy[0] = 0;
    dy[1] = 1;
    dy[2] = 0;
    dy[3] = -1;
    queue<pair<int,int> > que;
    que.push(pair<int,int> (i,j));
    moving_count[i][j] = 0;
    while(que.size() != 0){
        pair<int,int> p = que.front();
        que.pop();
        rep(a,4){
            int nx = p.second + dx[a];
            int ny = p.first + dy[a];
            if (0 <= nx && nx < W && 0 <= ny && ny < H && maze[ny][nx] == '.' && moving_count[ny][nx] == 150){
                que.push(pair<int,int>(ny,nx));
                moving_count[ny][nx] = moving_count[p.first][p.second] + 1;
            }
        }
    }
    return moving_count[H - 1][W - 1];
}

int main(){
    int H,W;
    cin >> H >> W;
    vector<string> vec(H);
    rep(i,H){
        cin >> vec[i];
    }
    int white_count = 0;
    rep(i,H){
        rep(j,W){
            if (vec[i][j] == '.') white_count++;
        }
    }
    vector<vector<int> > moving_count(H, vector<int> (W));
    rep(i,H){
        rep(j,W){
            moving_count[i][j] = 150;
        }
    }
    int ans = bfs(vec, moving_count, 0, 0, H, W);
    if (ans == 150) cout << -1 << endl;
    else cout << white_count - ans - 1<< endl;
}

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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 500100, MAXK = 30;
const ll MOD = 1e9+7;
const int INF = 1e8;
const ld PI = asin(1) * 2;

void setIO () {
    FAST_IO;
}

void setIO (string s) {
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

ll pwr (ll a, ll p) {
    if (p == 0) return 1ll;
    if (p == 1) return a%MOD;
    ll ret = pwr(a, p/2);
    ret *= ret;
    ret %= MOD;
    if (p%2 == 1) ret*=a;
    return (ret%MOD);
}

ll modInv (ll a) {
    return pwr(a%MOD, MOD-2);
}

ll ans[MAXN];
vi adj[MAXN];
int n;
ll sz[MAXN];
ll dp[MAXN];
ll fac[MAXN];

ll binom (ll up, ll down) {
    ll ret = fac[up];
    ret *= modInv(fac[down]);
    ret %= MOD;
    ret *= modInv(fac[up-down]);
    ret %= MOD;
    return (ret%MOD);
}

void dfs1 (int v, int p) {
    sz[v] = 1;
    dp[v] = 1;
    ans[v] = 1;

    for (int u : adj[v]) {
        if (u == p) continue;
        dfs1(u, v);
        sz[v] += sz[u];
    }

    ll rem = sz[v]-1;
    for (int u : adj[v]) {
        if (u == p) continue;
        dp[v] *= (binom(rem, sz[u])*dp[u])%MOD;
        dp[v] %= MOD;
        rem -= sz[u];
    }

}

void dfs2 (int v, int p) {

    if (p > 0) {
        dp[v] *= (binom(n-1, n-sz[v])*dp[p])%MOD;
        dp[v] %= MOD;
    }

    //cout << " v=" << v << endl;
    //FOR(i, 1, n) cout << " i=" << i << " dp=" << dp[i] << endl;

    ans[v] = dp[v];

    for (int u : adj[v]) {
        if (u == p) continue;
        dp[v] *= modInv((dp[u]*binom(n-1, sz[u]))%MOD);
        dp[v] %= MOD;
        //cout << " v=" << v << " u=" << u << " dpv=" << dp[v] << endl;
        dfs2(u, v);
        dp[v] = ans[v];
    }

    if (p > 0) {
        dp[v] *= modInv((binom(n-1, n-sz[v])*dp[p])%MOD);
        dp[v] %= MOD;
    }
}

int main() {
	setIO();

    cin >> n;

    fac[0] = 1;
    FOR(i, 1, n) fac[i] = (fac[i-1]*((ll)i))%MOD;

    REP(n-1) {
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    dfs1(1, -1);
    dfs2(1, -1);

    //FOR(i, 1, n) cout << " dp" << " i=" << i << " " << dp[i] << "\n";
    FOR(i, 1, n) cout << ans[i] << "\n";

	return 0;
}


Measured memory_bytes: 35444
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
typedef vector<long long> V;
typedef vector<V> VV;
template <class T>
inline bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return 1;
	}
	return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return 1;
	}
	return 0;
}
const long long INFLL = 1LL << 60;
const int INF = 1 << 28;
void solve(int a) { cout << (a ? "Yes" : "No") << endl; }
long long modpow(long long a, long long n, long long mod)
{
	long long res = 1;
	while (n > 0)
	{
		if (n & 1)
			res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
ll MOD = 1000000000 + 7;
int main()
{
	int n;
	ll ans = 0;
	cin >> n;
	int bef;
	map<int, int> a;
	for (int i = 0; i < n; i++)
	{
		cin >> bef;
		if (n % 2 == bef % 2)
		{
			ans = -1;
			break;
		}
		a[bef] += 0;
		a[bef]++;
		if (a[bef] > 2)
		{
			ans = -1;
			break;
		}
	}
	if (n % 2 == 1 and a[0] != 1)
	{
		ans = -1;
	}
	if (ans != -1)
	{
		ans = modpow(2, n/2, MOD);
	}
	else
	{
		ans = 0;
	}
	cout << ans << endl;
}


Measured memory_bytes: 2560
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for a in A:
    d[a] += 1

S = sum(A)
Q = int(input())
ans = []
for i in range(Q):
    b, c = map(int, input().split())
    nb = d[b]
    diff = (c - b) * nb
    d[b] = 0
    d[c] += nb
    S += diff
    ans.append(S)

print(*ans, sep='\n')

Measured memory_bytes: 27292
#include<stdio.h>

int main(){
  int i, n, p_min,p[200003],ans;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",p+i);
  }
  ans = 0;
  p_min = p[0];
  for(i=0;i<n;i++){
    if(p[i] <= p_min){
      ans++;
      p_min = p[i];
    }
  }
  printf("%d",ans);
}

Measured memory_bytes: 896
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);


		int n = sc.nextInt();

		int N[] = new int[n];

		for (int i=0; i<n; i++) {
			N[i] = sc.nextInt();
		}

		for (int i = n-1; i>=0; i--) {
			if (i>0) {
				System.out.print(N[i] + " ");
			}else if (i==0) {
				System.out.println(N[i]);
			}
		}
	}
}


Measured memory_bytes: 26228
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string a, b;
	cin >> a >> b;
	if(a.size() > b.size()) cout << "GREATER" << endl;
	else if(a.size() < b.size()) cout << "LESS" << endl;
	else{
		if(a > b) cout << "GREATER" << endl;
		else if(a < b) cout << "LESS" << endl;
		else cout << "EQUAL" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define NIL -1
struct Node{
	int p,l,r;
};

Node T[10000];
int n,D[10000],H[10000];
void setdepth(int u ,int d){
	if(u == NIL) return;
	D[u] = d;
	setdepth(T[u].l ,d+1);
	setdepth(T[u].r,d+1);
}
int setheight(int u){
	int h1 = 0,h2 = 0;
	if(T[u].l != NIL)
		h1 = setheight(T[u].l)+1;
	if(T[u].r !=NIL)
		h2 = setheight(T[u].r)+1;
	return H[u] = (h1> h2 ? h1 :h2);
}
int getsebling(int u){
	if(T[u].p == NIL)return NIL;
	if(T[T[u].p].l != u && T[T[u].p].l != NIL)
		return T[T[u].p].l;
	if(T[T[u].p].r != u && T[T[u].p].r != NIL)
		return T[T[u].p].r;
	return NIL;
}
void print(int u){
	cout<<"node "<<u<<": ";
	cout<<"parent = "<<T[u].p<<", ";
	cout<<"sibling = "<<getsebling(u)<<", ";
	int deg = 0;
	if(T[u].l  != NIL)deg++;
	if(T[u].r != NIL)deg++;
	cout<<"degree = "<<deg<<", ";
	cout<<"depth = "<<D[u]<<", ";
	cout<<"height = "<<H[u]<<", ";

	if(T[u].p == NIL){
		cout<<"root"<<endl;
	}
	else if(T[u].l ==NIL && T[u].r ==NIL){
		cout<<"leaf"<<endl;
	}
	else cout<<"internal node"<<endl;
}
int main(){
	int v,l,r,root = 0;
	cin>>n;
	for(int i = 0;i<n;i++){
		T[i].p = NIL;
	}

	for(int i = 0;i<n;i++){
		cin>>v>>l>>r;
		T[v].l = l;
		T[v].r = r;
		if(l != NIL)T[l].p = v;
		if(r != NIL)T[r].p = v;
	}
	for(int i = 0;i<n;i++)if(T[i].p == NIL)root = i;

	setdepth(root, 0);
	setheight(root);
	for(int i = 0;i<n;i++){
		print(i);
	}
	return 0;
}



Measured memory_bytes: 3108
/*"Success isn't permanent, failure isn't fatal,
                                      it's the courage to continue that counts"*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back     
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
const int mod=1e9+7;         
const int N=2e6+4;

int main()
{
	string s; cin>>s;

	if(s.back()=='3')cout<<"bon";
	else if(s.back()=='0' or s.back()=='1' or s.back()=='6' or s.back()=='8')
	cout<<"pon";
	else
	cout<<"hon";

	return 0;
}

Measured memory_bytes: 3624
//Shunji Lin 08-144505

#include <iostream>

using namespace std;

bool adjmatrix[101][101]; //adjmatrix
int discover[101];
int processed[101];
int cur_time = 0;


void DFS(int vertex, int N) {
  cur_time++;
  discover[vertex] = cur_time; // set cost
  
  for (int i=1; i<= N; i++) {
    if(adjmatrix[vertex][i] && discover[i] == -1) {
      DFS(i, N);
    }
  }
  
  cur_time++;
  processed[vertex] = cur_time;
}


  
int main() {
  const int cur_time = 0;
  
  for (int i = 0; i < 101; i++) {
    discover[i] = -1; // upper limit
    processed[i] = -1;
  }
  int N;
  cin >> N;

  for (int i = 1; i <= N; i++) {
    int vertex, degree;
    cin >> vertex >> degree;

    for (int j = 0; j < degree; j++) {
      int outvertex;
      cin >> outvertex;
      adjmatrix[i][outvertex] = true;
    }
  }



  for (int i = 1; i <= N; i++) {
    if (discover[i] == -1) {
      DFS(i,N);
    }
  }

  for (int i = 1; i <=N; i++) {
    cout << i << " " << discover[i] << " "<< processed[i] << endl;
  }
}

Measured memory_bytes: 1172
# include <iostream>
# include <stdint.h>
# include <stdio.h>
# include <math.h>
using namespace std;


int main(){
	string n,s;
    cin>> n;
    int q=0;
    while (cin>> s){
        for (int i=0;i<s.size();i++){
            if (s[i]<97){
                s[i] +=32;
            }
        }
        if (s==n){
            q++;
        }
    }
    cout<< q<< "\n";
	return 0;
}



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

using namespace std;

int find(int arr[], int a){
	while(a != arr[a]){
		a = arr[a];
	}
	return a;
}

void unite(int arr[], int a, int b, int size[]){
	a = find(arr, a);
	b = find(arr, b);
	if(a != b){
		if(size[a] > size[b]){
			swap(a, b);
		}
		arr[a] = b;
		size[b] += size[a];
		size[a] = 0;
	}
}

int main(){
	int n, m;
	cin >> n >> m;
	int size[n], arr[n];
	for(int i=0;i<n;i++) size[i] = 1;
	for(int i=0;i<n;i++) arr[i] = i;
	int A, B;
	for(int i=0;i<m;i++){
		cin >> A >> B;
		unite(arr, A-1, B-1, size);
	}
	int maxcnt = 1;
	for(int i=0;i<n;i++){
		if(size[i] > maxcnt){
			maxcnt = size[i];
		}
	}
	cout << maxcnt << endl;
}


Measured memory_bytes: 5196
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
if s[2] == s[3] and s[4] == s[5]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38740
#include<stdio.h>
#include<string.h>
#include<ctype.h>
 
char s[10000];
 
void min(){
  int i,len=strlen(s);
 
  for(i=0;i<len;i++)
    s[i]=tolower(s[i]);
}
 
int main(){
  char t[10000];  //target
  int cnt=0;
 
  scanf("%s",t);
  for(;;){
    scanf("%s",s);
 
    if(strcmp(s,"END_OF_TEXT")==0)
      break;
 
    min();
    if(strcmp(s,t)==0)
      cnt++;
  }
  printf("%d\n",cnt);
 
  return 0;
}

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

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;

const double PI = 3.141592653;

int main(){
  IO; double A, B, H, M; cin >> A >> B >> H >> M;
  double a = (H+M/60)/12*2*PI, b = M/60*2*PI;
  double dx = A*cos(a) - B*cos(b);
  double dy = A*sin(a) - B*sin(b);
  cout << setprecision(12) << sqrt(dx*dx+dy*dy) << endl;
}


Measured memory_bytes: 4104
import java.util.Arrays;
import java.util.Scanner;
class Player implements Comparable<Player>{
	int party;
	int num;
	String time;
	Player(int p,int n,String t){
		this.party = p;
		this.num = n;
		this.time = t;
	}
	/*@Override
	public int compareTo(Player p) {
		return this.time.compareTo(p.num);
	}
	*/
	public String getTime() {
        return time;
    }
	@Override
	public int compareTo(Player o) {
		// TODO Auto-generated method stub
	
		return this.time.compareTo(((Player) o).getTime());
	}
	
}

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Player[] person = new Player[24];
		int[] rank1 = new int[8];
		int[] rank2 = new int[8];
		int[] rank3 = new int[8];
		int cnt1 = 0;
		int cnt2 = 0;
		int cnt3 = 0;
		for(int i = 0;i < 3;i++){
			for(int j = 0;j < 8;j++){
				person[i*8+j] = new Player(i,sc.nextInt(),sc.next());
			}
		}
		Arrays.sort(person);
		for(int i = 0;i < 24;i++){
			if(person[i].party == 0){
				rank1[cnt1] = i;
				cnt1++;
			}else if(person[i].party == 1){
				rank2[cnt2] = i;
				cnt2++;
				
			}else{
				rank3[cnt3] = i;
				cnt3++;
			}
		}
		for(int j = 0;j < 2;j++){
			System.out.println(person[rank1[j]].num+" "+person[rank1[j]].time);
			person[rank1[j]].time = "999";
		}
		for(int j = 0;j < 2;j++){
			System.out.println(person[rank2[j]].num+" "+person[rank2[j]].time);
			person[rank2[j]].time = "999";
		}
		for(int j = 0;j < 2;j++){
			System.out.println(person[rank3[j]].num+" "+person[rank3[j]].time);
			person[rank3[j]].time = "999";
		}
		Arrays.sort(person);
		for(int j = 0;j < 2;j++){
			System.out.println(person[j].num+" "+person[j].time);
		}
		
	}
}

Measured memory_bytes: 26200
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=998244353;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int dp[310][310 * 310] = {},dp2[310][310 * 310];

signed main(){
	int n,a[310],sum = 0;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
		sum += a[i];
	}
	dp[0][0] = 1;
	dp2[0][0] = 1;
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= sum;j++){
			(dp[i + 1][j] += dp[i][j] * 2) %= MOD;
			if(j + a[i] <= sum) (dp[i + 1][j + a[i]] += dp[i][j]) %= MOD;
			(dp2[i + 1][j] += dp2[i][j]) %= MOD;
			if(j + a[i] <= sum) (dp2[i + 1][j + a[i]] += dp2[i][j]) %= MOD;
		}
	}
	int ans = 1;
	for(int i = 0;i < n;i++) ans = ans * 3 % MOD;
	for(int i = (sum + 1) / 2;i <= sum;i++){
		if(i * 2 == sum) dp[n][i] = (dp[n][i] - dp2[n][i] % MOD + MOD) % MOD; 
		ans = (ans - dp[n][i] * 3 % MOD + MOD) % MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 454144
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    char a, b; cin >> a >> b;
    cout << ((a == b) ? "H" : "D") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=2e9;

int main(){
    int a,b;
    cin>>a>>b;
    if(a+b>=10)cout<<"error"<<endl;
    else cout<<a+b<<endl;
}


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

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 100010
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()


template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solve2(void)
{
  int a,b;cin>>a>>b;
  if(a == b)
  {
    cout<<2*a  -2 <<endl;
    return;
  }
    int lim = a*b - 1;
    int l = 1,r = I32_MAX;
    while(abs(l - r) > 1)
    {
      int mid = (l + r)/2;
      int mul = (mid + 1)/2 * (mid + 1 - (mid +1)/2);
      if(mul > lim) r = mid;
      else l = mid;
      // DEBUG(mul,mid,"\n");
  }
  cout<<l-1<<endl;

}
void solve(void)
{
  int q;cin>>q;
  for (int lq = 0; lq < q; lq++)
  {
    solve2();
  }
  
  return;
}

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

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


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

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define ANS(ans) cout << (ans) << endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

class UnionFind {
 public:
  vector<ll> par;  // 各元の親を表す配列
  vector<ll> siz;  // 素集合のサイズを表す配列(1 で初期化)

  // Constructor
  UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
    for (ll i = 0; i < sz_; ++i) par[i] = i;  // 初期では親は自分自身
  }
  void init(ll sz_) {
    par.resize(sz_);
    siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
    for (ll i = 0; i < sz_; ++i) par[i] = i;  // 初期では親は自分自身
  }

  // Member Function
  // Find
  ll root(ll x) {  // 根の検索
    while (par[x] != x) {
      x = par[x] = par[par[x]];  // x の親の親を x の親とする
    }
    return x;
  }

  // Union(Unite, Merge)
  bool merge(ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    // merge technique（データ構造をマージするテク．小を大にくっつける）
    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
    return true;
  }

  bool issame(ll x, ll y) {  // 連結判定
    return root(x) == root(y);
  }

  ll size(ll x) {  // 素集合のサイズ
    return siz[root(x)];
  }
};

int main() {
  int n, m, k;

  cin >> n >> m >> k;

  UnionFind uf(n);
  Graph errors(n);

  int a, b;
  REP(i, m) {
    cin >> a >> b;
    a--;
    b--;

    uf.merge(a, b);
    errors[a].push_back(b);
    errors[b].push_back(a);
  }
  REP(i, k) {
    cin >> a >> b;
    a--;
    b--;

    errors[a].push_back(b);
    errors[b].push_back(a);
  }

  REP(i, n) {
    errors[i].push_back(i);
    ll size = uf.size(i);
    int diff = 0;

    REP(j, errors[i].size()) {
      if (uf.issame(i, errors[i][j])) {
        diff++;
      }
    }

    ll count = size - diff;
    if (i == n - 1) {
      cout << count << endl;
    } else {
      cout << count << " ";
    }
  }

  return 0;
}


Measured memory_bytes: 10112
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define M 1000000007
#define N 610
int n,a[N],used[N],mark[N],f[N][N],g[N][N],num;
signed main(){
	scanf("%lld",&n);
	for (int i=1;i<=2*n;i++) scanf("%lld",&a[i]);
	for (int i=1;i<=n;i++){
		if (a[2*i-1]!=-1 && a[2*i]!=-1) used[a[2*i-1]]=used[a[2*i]]=1;
		if (a[2*i-1]==-1 && a[2*i]==-1) num++;
		if (a[2*i-1]!=-1) mark[a[2*i-1]]=1;
		if (a[2*i]!=-1) mark[a[2*i]]=1;
	}
	f[0][0]=1; int x=0,y=0;
	for (int i=1;i<=2*n;i++){
		if (used[i]) continue;
		memset(g,0,sizeof(g));
		if (mark[i]){
			for (int j=0;j<=x+y;j++)
				for (int k=0;k<=x+y;k++){
					if (!f[j][k]) continue;
					if (k) (g[j][k-1]+=f[j][k]*k%M)%=M;
					(g[j+1][k]+=f[j][k])%=M;
				}
			x++;
		}else{
			for (int j=0;j<=x+y;j++)
				for (int k=0;k<=x+y;k++){
					if (!f[j][k]) continue;
					(g[j+1][k]+=f[j][k])%=M;
					if (j) (g[j-1][k]+=f[j][k])%=M;
					if ((j-k-x+y)>=0) (g[j][k+1]+=f[j][k])%=M;
				}
			y++;
		}
		memcpy(f,g,sizeof(g));
	}
	for (int i=1;i<=num;i++) f[0][0]=1LL*f[0][0]*i%M;
	printf("%lld\n",f[0][0]);
	return 0;
}


Measured memory_bytes: 6016
def factorial(n)
  i = 1
  k = 1
  while i < n
    k *= i+1
    i += 1
  end
  k
end

s = gets.to_i
max = s/3#数列が取り得る最大の長さ
i = 1
ans = 0

while i <= max#数列の長さ毎に考える。
  n = s - (i * 3)#この値をiに分配する場合の数
  ans +=  factorial(n + i -1) / (factorial(n) * factorial(i-1))
  i += 1
end
ans %= 10**9 + 7
puts ans


Measured memory_bytes: 18504
while True:
    try:
        formula = raw_input().split("=")
        sum = formula[1]
        left = formula[0].split("+")
        a = left[0]
        b = left[1]
        ok = 0
        for i in range(10):
            A = a.replace('X', str(i))
            B = b.replace('X', str(i))
            Sum = sum.replace("X", str(i))
            if ((len(A) > 1 and A[0] == '0') or ((len(B) > 1and B[0] == '0')) or ((len(Sum) > 1 and Sum[0] == 'X'))):
                continue
            if (int(A) + int(B) == int(Sum)):
                ok = 1
                print i
        if (ok == 0):
            print "NA"
    except:
        break
        

Measured memory_bytes: 4280
let inp = readLine()!.split(separator: " ").map { Int($0)! }
let (N, K) = (inp[0], inp[1])
let As = (1...K).map { _ -> [Int] in
    _ = readLine()
    return readLine()!.split(separator: " ").map { Int($0)! }
}

print(N - Set(As.flatMap{$0}).count)



Measured memory_bytes: 8448
n, m = input().split()
m = int(m)

votes = input().split()
votes = [int(i) for i in votes]
votes.sort(reverse=True)

total = sum(votes)

valid = True
for i in range(m):
    if votes[i] < total/(4*m):
        valid = False
        break

if valid:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
// new day,new strength,new thougts

#include<bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define F first
#define S second
#define sz(c) (c).size()
#define REP(i,n)  for(ll i=0;i<n;i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define all(s) (s).begin(),(s).end()
#define bit(num,i) ((num>>i)&1)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll inf=4e18;
const ll maxn=1e5+10;
const ll mod=1e9+7;

#pragma GCC Optimize("Ofast")

ll L[maxn],R[maxn],n;
bool is[maxn];

priority_queue<pll,vector<pll>,greater<pll> > en;
priority_queue<pll> st;

ll check(bool turn){
	memset(is,0,sizeof is);
	ll num=0,bef=0;
	REP(i,n){
		st.push(MP(L[i],i));
		en.push(MP(R[i],i));
	}
	REP(i,n){
		ll ind;
		if(turn){
			ind=en.top().S;
			en.pop();
		}
		else{
			ind=st.top().S;
			st.pop();
		}
		turn^=1;
		if(is[ind])continue;// osoolan nabayad pish biad
		is[ind]=1;
		if(bef<L[ind]){
			num+=L[ind]-bef;
			bef=L[ind];
		}
		if(R[ind]<bef){
			num+=bef-R[ind];
			bef=R[ind];
		}
	}
	num+=(abs(bef));
	return num;
}

int main(){
	cin>>n;
	REP(i,n){
		cin>>L[i]>>R[i];
	}
	cout<<max(check(0),check(1));
}

Measured memory_bytes: 12128
import java.util.*;

public class Main{
		
		public static boolean func(int n) {
			
			int count = 0;
			while(n != 0) {
				
				n = n/10;
				count++;
			
			}
			
			if(count % 2 == 1){
				
				return true;
				
			} else {
				
				return false;
				
			}
			
		}
		
		
		public static void main(String args[]){
	
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
	
			int count = 0;
			for(int i = 1; i <= n; i++){
			
			if(func(i)){
				
					count++;
				
				}
			
			}
			
			System.out.println(count);
			
		}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

int main(){
	string S;
	cin >> S;

	int N = S.size();
	int ans=1;
	int i=1;
	int j=1;
	while(i<N){
		int k=1;
		if(S.substr(i-j, j) == S.substr(i, k)) k++;
		j = k;
		i += k;
		if(i<=N) ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
#define SEG_LEN (1 << 18)
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
long long n,k;
vector<ll>v(1000000),c(1000000);
int main(){
  cin >> n >> k;
  rep(i,n){
    cin >> v[i];
    v[i]--;
  }
  ll now = 0;
  bool can = true;
  for(long long i = 1; i <= k; i++){
    if(c[now] && can){
      can = false;
      ll tmp = abs(c[now] - i);
      i += tmp * ((k - i) / tmp);
    }
    c[now] = i;
    now = v[now];
  }
  cout << now + 1 << endl;
  return 0;
}
 

Measured memory_bytes: 18688
def selection(l):
	N = len(l)
	count = 0

	for i in range(N):
		minj = i

		for j in range(i, N):
			if l[j] < l[minj]:
				minj = j
		if i == minj:
			continue
		else:
			l[i], l[minj] = l[minj], l[i]
			count += 1

	return l, count




if __name__ == '__main__':
	n = int(input())
	l = input().split()

	for i in range(n):
		l[i] = int(l[i])

	l, c = selection(l)
	count = 0
	leng = len(l)
	for i in l:
		count += 1
		if count < leng:
			print(i, end =' ')
		else:
			print(i)
			print(c)



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

bool is_prime(int num){
    if(num<=1) return false;
    for(int i=2;i*i<=num;i++){
        if(num%i==0) return false; 
    }
    return true;
}

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

    while(1){
        if(is_prime(x)){
            break;
        }
        x++;
    }

    cout << x << endl;
}

Measured memory_bytes: 256
S,C = map(int, input().split())

if S*2 < C:
    #use all peace

    #1. use all S, and create Scc
    scc_num=S
    C -= S*2

    #2. c->s, and create Scc
    scc_num += int(C/4)

else:
    #Scc is bound by c
    scc_num=int(C/2)

print(scc_num)

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i=0; i<N; ++i) cin >> A[i];

    int g = A[0];
    for (int i=1; i<N; ++i) g = __gcd(g, A[i]);
    if (g != 1) {
        cout << "not coprime" << '\n';
        return;
    }

    set<int> st;
    vector<int> used;
    for (int x : A) {
        used.clear();
        for (int i=2; i*i<=x; ++i) {
            if (x%i == 0) {
                used.push_back(i);
                while (x%i == 0) x /= i;
            }
        }
        if (x != 1) used.push_back(x);
        for (int y : used) {
            if (st.count(y)) {
                cout << "setwise coprime" << '\n';
                return;
            }
            st.insert(y);
        }
    }
    cout << "pairwise coprime" << '\n';
}

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

    solve();

    return 0;
}


Measured memory_bytes: 7308
from itertools import groupby
def print_ans(input_line):
    """Test Case
    >>> print_ans("aabbbbaaca")
    5
    >>> print_ans("aaaaa")
    1
    >>> print_ans("xxzaffeeeeddfkkkkllq")
    10
    """
    print(len(list(groupby(input_line))))

if __name__ == '__main__':
    N = int(input())
    s = input()
    print_ans(s)

Measured memory_bytes: 15860
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll powmod(ll a, ll b) {
    a %= MOD;
    ll res = 1;
    while (b > 0) {
        if (b % 2 == 1)res = res * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return res;
}
ll f[2200000];
void cominit() {
    f[0] = 1;
    REP(i, 2100000)f[i + 1] = f[i] * (i + 1) % MOD;
}

ll nCr(ll n, ll r) {
    if (n < r)return 0;
    if (n < 0 or r < 0)return 0;
    return f[n] * powmod(f[r] * f[n - r], MOD - 2) % MOD;
}

ll nPr(ll n, ll r) {
    if (n < r)return 0;
    if (n < 0 or r < 0)return 0;
    return f[n] * powmod(f[n - r], MOD - 2) % MOD;
}

ll nHr(ll n, ll r) {
    if (n < r)return 0;
    if (n < 0 or r < 0)return 0;
    return nCr(n + r - 1, r);
}
ll k, ans;
string s;
int main() {
    cominit();
    cin >> k >> s;
    ll sz = s.size();
    ll n = k + sz;
    ans = powmod(26, n);
    REP(i, sz){
        ans -= nCr(n, i) * powmod(25, n - i) % MOD;
        ans = (ans + MOD * 2) % MOD;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 21668