akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    int N; cin >> N;
    FOR(i,1,50010){
        if(int(i * 1.08) == N){
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;

}


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

int main() {
	int a, f = 0, s = 0;
	for (int i = 0; i < 3; i++) {
		cin >> a;
		if (a == 5) f++;
		else if (a == 7) s++;

		a = 0;
	}
	if (f == 2 && s == 1) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
n,t,*a=`dd`.split.map(&:to_i)
amin=[a[0]]
1.upto(a.size-1){|i|amin[i]=[amin[i-1],a[i]].min}
amax=[]
amax[a.size-1]=a[-1]
(a.size-2).downto(0){|i|amax[i]=[amax[i+1],a[i]].max}
r=amax.zip(amin).uniq.map{|x,y|y-x}.sort
p r.take_while{|e|e==r[0]}.size

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

using namespace std;

//#define FILE_IO

int N, K, ans;
int fth[100005];
vector <int> edg[100005];

int DFS(int nod)
{
    int mx = 0;
    for(auto nxt: edg[nod])
    {
        if(nxt == fth[nod]) continue;

        int dpt = DFS(nxt);
        if(dpt == K - 1)
        {
            ans++;
            continue;
        }
        mx = max(mx, dpt + 1);
    }
    return mx;
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &K);
    scanf("%d", &fth[1]);
    if(fth[1] != 1) ans++;
    fth[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        scanf("%d", &fth[i]);
        edg[ fth[i] ].push_back(i);
    }

    for(auto nxt: edg[1])
        DFS(nxt);

    printf("%d\n", ans);

    return 0;
}


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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

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

    if (k == 0) {
        cout << n * n << endl;
        return 0;
    }

    ll t = 0;

    for (int i = k + 1; i <= n; i++) {
        t += n / i * (i - k);
        t += max(0ll, n - ((n / i) * i) - k + 1);
    }

    cout << t << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 1000000000
#define MOD 1000000007

typedef  long long ll;

using namespace std;

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        a = a^b;
        b = a^b;
        a = a^b;
    }
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }
    cout<<  ans << endl;
    }
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}


void solve(void){
    int n;
    cin >> n;
    rep(i,1,10){
        if(n <= i*100+i*10+i){
            cout << i*100+i*10+i<<endl;
            return;
        }
    }
}


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


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

using namespace std;
static const int N = 100;
static const int INFTY = (1 << 21);

int n, M[N][N];
int d[N];

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    for (int i = 0; i < n; i++) {
        d[i] = INFTY;
    }
    d[s] = 0;
    int u;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
            if (M[u][v] == 0) continue;
            if (d[v] != INFTY) continue;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    for (int i = 0; i < n; i++) {
        cout << i + 1 << " " << ((d[i] == INFTY) ? (-1) : d[i]) << endl;
    }
}

int main(int argc, char const *argv[])
{
    int u, k, v;

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            M[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        u--;
        for (int j = 0; j < k; j++) {
            cin >> v;
            v--;
            M[u][v] = 1;
        }
    }

    bfs(0);

    return 0;
}




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

using namespace std;

int main()
{
    float a, b;
	cin >> a >> b;
	int count = 0;
	if (b == 1) {
		cout << 0 << '\n';
		return 0;
	}
	while (1) {
		b -= a;
		count++;
		if (b > 0) {
			b++;
		}
		else break;
	}
	cout << count << '\n';
	return 0;
}


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

using namespace std;

using ll = long long;

constexpr ll mod = 1e9 + 7;

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

  int n, k;
  cin >> n >> k;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());

  vector<bool> dp(k + 1);
  for (int i = 1; i <= k; ++i) {
    for (int x: a) {
      if (i - x < 0) {
        break;
      }
      if (!dp[i - x]) {
        dp[i] = true;
        break;
      }
    }
  }

  cout << (dp[k] ? "First" : "Second") << '\n';

  return 0;
}


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N;
    cin >> N;
    if(N/100 == N%10) {
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 順列　do {} while(next_permutation(ALL(X)));
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  int n;
  cin >> n;
  vi h(n);
  REP(i,n) {
    cin >> h[i];
  }
  int ans=h[0];
  REP(i,n-1) {
    if(h[i]<h[i+1]) ans+=h[i+1]-h[i];
  }
  
  cout << ans << endl;
  return 0;
}


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

#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define Rep(i, n) for( int i = 0; i < (n); i++ )
#define Rrep(i, a, n) for( int i = (a); i < (n); i++ )
#define All(v) v.begin(), v.end()

typedef pair<int, int> Pii;
typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

signed main() {
    int x, y;
    cin >> x >> y;
    int ans = 0;
    int n = x;
    while ( 1 ) {
        if ( n > y ) break;
        ans++;
        n *= 2;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int n, a=0, nam[20];
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> nam[i];
    for(int i=1; i<n-1; i++)
    {
        if((nam[i-1]<nam[i]&&nam[i]<nam[i+1])||(nam[i-1]>nam[i]&&nam[i]>nam[i+1]))
            a++;
    }
    cout << a << '\n';
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;

int main()
{
	int n;
    cin>>n;
    vi a(n);
    vc<ll> pre(n);
    for(int i=0;i<n;i++) cin>>a[i];
    ll ans=(!a[0]);
    ll ans2=0;
    pre[0]=a[0]+(!a[0]);
    for(int i=1;i<n;i++) pre[i]=pre[i-1]+a[i];
    ll delta=0;
    for(int i=1;i<n;i++)
    {
        if(pre[i-1]+delta>0)
        {
            if(pre[i]+delta>=0)
            {
                ans+=pre[i]+delta+1;
                delta-=pre[i]+delta+1;
            }
        }
        else{
            if(pre[i]+delta<=0)
            {
                ans+=-(pre[i]+delta)+1;
                delta-=pre[i]+delta-1;
            }
        }
    }
    delta=0;
    if(a[0]>=0) {
        ans2=a[0]+1;
        a[0]=-1;
    }
    else{
        ans2=-a[0]+1;
        a[0]=1;
    }
    pre[0]=a[0];
    for(int i=1;i<n;i++) pre[i]=pre[i-1]+a[i];
    for(int i=1;i<n;i++)
    {
        if(pre[i-1]+delta>0)
        {
            if(pre[i]+delta>=0)
            {
                ans2+=pre[i]+delta+1;
                delta-=pre[i]+delta+1;
            }
        }
        else{
            if(pre[i]+delta<=0)
            {
                ans2+=-(pre[i]+delta)+1;
                delta-=pre[i]+delta-1;
            }
        }
    }
    cout<<min(ans,ans2)<<'\n';
}

Measured memory_bytes: 1408
T=int(input())
if T>=400 and T<=599: print(8)
if T>=600 and T<=799: print(7)
if T>=800 and T<=999: print(6)
if T>=1000 and T<=1199: print(5)
if T>=1200 and T<=1399: print(4)
if T>=1400 and T<=1599: print(3)
if T>=1600 and T<=1799: print(2)
if T>=1800 and T<=1999: print(1)

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

using namespace std;

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

	vector<int> arr(N);
	for (auto &a: arr) {
		cin >> a;
	}

	int swaps = 0;
	for (int i = 0; i < N-1; ++i) {
		int minj = i;
		for (int j = i+1; j < N; ++j) {
			if (arr[j] < arr[minj]) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(arr[i], arr[minj]);
			++swaps;
		}
	}

	cout << arr[0];
	for (int i = 1; i < N; ++i) {
		cout << ' ' << arr[i];
	}
	cout << '\n';
	cout << swaps << endl;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mod 1000000007
// #define mod 998244353
using namespace std;

map<vector<ll>, ll> mymap;

void insert(vector<ll> &v)
{
	for (int i = 0; i < 4; i++)
	{
		rotate(v.begin(), v.begin() + 1, v.end());
		mymap[v]++;
	}
}

void remove(vector<ll> &v)
{
	for (int i = 0; i < 4; i++)
	{
		rotate(v.begin(), v.begin() + 1, v.end());
		mymap[v]--;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> c[n];
	for (int i = 0; i < n; i++)
	{
		c[i].resize(4);
		for (int j = 0; j < 4; j++)
		{
			cin >> c[i][j];
		}
		insert(c[i]);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++)
	{
		vector<ll> top = c[i];
		remove(top);
		for (int j = i + 1; j < n; j++)
		{
			vector<ll> rev_bot = c[j], bot = c[j];
			reverse(bot.begin(), bot.end());
			remove(rev_bot);
			for (int dir = 0; dir < 4; dir++)
			{
				vector<ll> req[4];
				for (int num = 0; num < 4; num++)
				{
					req[num].pb(top[num]);
					req[num].pb(top[(num + 1) % 4]);
					req[num].pb(bot[(num + 1) % 4]);
					req[num].pb(bot[num]);
					reverse(req[num].begin(), req[num].end());
				}
				ll temp_ans = 1;
				vector<bool> was_removed(4);
				for (int num = 0; num < 4; num++)
				{
					temp_ans *= mymap[req[num]];
					if (mymap[req[num]] > 0)
					{
						remove(req[num]);
						was_removed[num] = 1;
					}
				}
				for (int num = 0; num < 4; num++)
				{
					if (was_removed[num])
					{
						insert(req[num]);
					}
				}
				// if (i == 1 && j == 3)
				// {
				// 	for (int x : top)
				// 	{
				// 		cout << x << " ";
				// 	}
				// 	cout << endl;
				// 	for (int x : bot)
				// 	{
				// 		cout << x << " ";
				// 	}
				// 	cout << endl;
				// 	for (int num = 0; num < 4; num++)
				// 	{
				// 		for (int x : req[num])
				// 		{
				// 			cout << x << " ";
				// 		}
				// 		cout << endl;
				// 	}
				// 	cout << temp_ans << endl;
				// 	cout << endl;
				// }
				ans += temp_ans;
				rotate(bot.begin(), bot.begin() + 1, bot.end());
			}
			insert(rev_bot);
		}
		insert(top);
	}
	cout << ans / 3 << endl;
	return 0;
}

Measured memory_bytes: 163472
n=int(input())
s=input()
p=list(s.split())
s1=0
s2=0
for i in range(0,n):
  s1=s1+int(p[i])
  s2=s2+(int(p[i])*int(p[i]))
k= ((s1**2)-s2)//2
k=k%1000000007
print(k)
 

Measured memory_bytes: 98612
s = gets.chomp.chars
abc = s.each_index.each_cons(3).find {|abc| abc.map{|i| s[i] }.uniq.size < abc.size }
if abc
    puts "%d %d" % abc.values_at(0,2).map{|i| i + 1}
elsif s.size < 3 && s.uniq.size < s.size
    puts "1 2"
else
    puts "-1 -1"
end


Measured memory_bytes: 9468
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int a,b,c;
    cin >> a>>b>>c;

    
    if(a==b&&b==c)
      cout <<1<<endl;
  	else if(a==b&&b!=c)
      cout <<2<<endl;
  	else if(a==c&&a!=b)
      cout <<2<<endl;
  	else if(b==c&&c!=a)
      cout <<2<<endl;
  	else
      cout<<3<<endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
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);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
	int64_t x;
	mint(int64_t x=0):x((x%mod+mod)%mod){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	mint pow(int64_t t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}

	//for prime mod
	mint inv() const { return pow(mod-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
	vector<mint> frac, ifrac;
	combination(int n):frac(n+1), ifrac(n+1) {
		assert(n < mod);
		frac[0] = 1;
		for (int i = 1; i <= n; ++i) frac[i] = frac[i-1]*i;
		ifrac[n] = frac[n].inv();
		for (int i = n; i >= 1; --i) ifrac[i-1] = ifrac[i]*i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return frac[n]*ifrac[k]*ifrac[n-k];
	}
} c(1000000);

//head

mint n[2];
int k;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n[0] >> n[1] >> k;

	mint *now = n, *other = n+1;
	mint ans;
	const int X = (n[0] * n[1]).x;
	rep(i, 2) {
		ans += (*now-1) * (*now) * (*now+1) / 6 * (*other) * (*other) * c(X-2, k-2);
		swap(now, other);
	}

	cout << ans << endl;
}

Measured memory_bytes: 18644
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    for(int n; cin >> n, n;){
        vi a(n); for(auto& e: a) cin >> e;
        sort(_all(a));

        int minDiff = a[1] - a[0];
        rep(i, n - 1){
            int diff = a[i + 1] - a[i];
            chmin(minDiff, diff);
        }

        cout << minDiff << endl;
    }

    return 0;
}

Measured memory_bytes: 3180
def f(start,goal,stat)

  num=((goal+start)/2).floor
  puts num
  STDOUT.flush
  numStat=gets
  if numStat=="Vacant"
    return 0
  end
  
  if (num-start)%2==0
    if stat==numStat
      f(num,goal,numStat)
    else
      f(start,num,stat)
    end
  else
    if stat==numStat
      f(start,num,stat)
    else
      f(num,goal,numStat)
    end
  end
end

n=gets.to_i
puts 0
STDOUT.flush
s=gets
if s!="Vacant"
  f(0,n,s)
end


Measured memory_bytes: 4336
#include<iostream>
#include <stdio.h>
using namespace std;
 
int main(){
	int a;
	cin>>a;
	if(a==1){
	cout<<1<<endl;}
	if(a==2){
	cout<<2<<endl;}
	if(a==3){
	cout<<6<<endl;}
	if(a==4){
	cout<<24<<endl;}
	if(a==5){
	cout<<120<<endl;}
	if(a==6){
	cout<<720<<endl;}
	if(a==7){
	cout<<5040<<endl;}
	if(a==8){
	cout<<40320<<endl;}
	if(a==9){
	cout<<362160<<endl;}
	if(a==10){
	cout<<3621600<<endl;}
	if(a==11){
	cout<<39916800<<endl;}
	if(a==12){
	cout<<479001600<<endl;}
	if(a==13){
	cout<<6227020800<<endl;}
	if(a==14){
	cout<<87178291200<<endl;}
	if(a==15){
	cout<<1307674368000<<endl;}
	if(a==16){
	cout<<20922789888000<<endl;}
	if(a==17){
	cout<<355687428096000<<endl;}
	if(a==18){
	cout<<6402373705728000<<endl;}
	if(a==19){
	cout<<121645100408832000<<endl;}
	if(a==20){
	cout<<2432902008176640000<<endl;}
	return 0;}


Measured memory_bytes: 1160
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps = 1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.txt"


int main() {
	while (1) {
		int y, m, d;
		if (!(cin >> y >> m >> d)) {
			return 0;
		}
		else {
			int hash = y * 10000 + m * 100 + d;
			string gou;
			if (hash >= 1989 * 10000 + 1 * 100 + 8) {
				gou = "heisei";
			}
			else if (hash >= 1926 * 10000 + 12 * 100 + 25) {
				gou = "showa";
			}
			else if (hash >= 1912 * 10000 + 7 * 100 + 30) {
				gou = "taisho";
			}
			else if(hash>=1868*10000+9*100+8){
				gou = "meiji";
			}
			else {
				gou = "pre-meiji";
			}
			if (gou == "pre-meiji") {
				cout << gou << endl;
			}
			else {
				cout << gou << " ";
				map<string, int>mp;
				mp["heisei"] = 1988;
				mp["showa"] = 1925;
				mp["taisho"] = 1911;
				mp["meiji"] = 1867;
				cout << y - mp[gou] << " "<<m << " " << d << endl;
			}
			
		}
	}

	return 0;
}



Measured memory_bytes: 3164
using System; using System.Collections.Generic; using System.Linq;  public class Prog {     public void run()     {         var input = Console.ReadLine().Split();         int r = int.Parse(input[0]);         int D = int.Parse(input[1]);         int x0 = int.Parse(input[2]);         int[] x = new int[11];         x[0] = x0;         for(int i = 1; i <= 10; i++)         {             x[i] = r * x[i - 1] - D;             Console.WriteLine(x[i]);         }     }     public static void Main()     {         //var input = Console.ReadLine().Split();         //int[] X = Array.ConvertAll(input, int.Parse);         var prog = new Prog();         prog.run();     } }  //Array.ConvertAll(int

Measured memory_bytes: 11092
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var array = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        decimal n = array[0];
        decimal m = array[1];
        decimal d = array[2];
        //double res = 1.0 * (m - 1) * Math.Pow(n, m-1) / Math.Pow(n, m);
        decimal res;
        if (d==0)
        {
            res = (m - 1.0m) / n;
        }
        else
        {
            res = (m - 1.0m) * 2 * (n - d) / n / n;
        }
        Console.WriteLine(string.Format("{0:f10}",res));
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <unordered_map>
#define Debug 0
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

//最大公約数
template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//最小公倍数
template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

vector<string> button;

void solve(string &ret){
    string s; cin >> s;
    int num = 0;
    int cnt = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '0') {
            if (num) {
                ret.push_back(button[num][(cnt-1)%button[num].length()]);
            }
            num = 0;
            cnt = 0;
        } else {
            num = (int)(s[i] - '0');
            cnt++;
        }
    }
    return;
}

void init() {
    button = vector<string>(10);
    button[1] = ".,!? ";
    button[2] = "abc";
    button[3] = "def";
    button[4] = "ghi";
    button[5] = "jkl";
    button[6] = "mno";
    button[7] = "pqrs";
    button[8] = "tuv";
    button[9] = "wxyz";
}

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

    init();

    int N; cin >> N;
    vector<string> ans(N);
    for (int i = 0; i < N; i++) {
        string tmp;
        solve(tmp);
        ans[i] = tmp;
    }
    for (auto &i: ans) {
        cout << i << endl;
    }
}





Measured memory_bytes: 3224
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

ll fac[200007],finv[200007],inv[200007];
void cominit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<200007;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll com(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cominit();
    ll n,k;
    cin>>n>>k;
    ll num=1;
    for(int i=1;i<=n;i++){
    	num*=i;
    	num%=mod;
    }
    cout << (com(k,n)*num)%mod <<endl;
    return 0;
}



Measured memory_bytes: 7904
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


    public static void main(String args[] ) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] origin = br.readLine().split("");
        String[] serch = br.readLine().split("");

       // System.out.println( SameString(serch) );
        for(int i = 0; i < origin.length; ){
        	 //System.out.println(i);

           if( i + serch.length  <= origin.length && SearchWord(origin , serch, i)){
              System.out.println(i);
              i++;

              /*
              if(SameString(serch)){
            	  i++;
              }else{
                i = i + serch.length ;
              }*/
           }else{

        	   i++;

           }



        }







    }



    public static boolean SearchWord(String[] Origin , String[] Serch , int i){


    	boolean SerchCheck = false;
    	for(int j = i , k = 0; k < Serch.length; j++ , k++){

    	    if( Serch[k].equals(Origin[j]) ){
    	    	SerchCheck = true;
    	    }
    	    else{
    	    	return false;
    	    }



    	}


    	return SerchCheck;

    }


    public static boolean SameString(String[] Serch ){


    	boolean SerchCheck = false;
    	for(int i = 0 ; i < Serch.length; i++){

    	    if( Serch[0].equals(Serch[i]) ){
    	    	SerchCheck = true;
    	    }
    	    else{
    	    	return false;
    	    }



    	}


    	return SerchCheck;

    }



}

Measured memory_bytes: 24992
#include<stdio.h>
int main(){
int a;
double q,x1,x2,r;
while(1){
scanf("%d\n",&a);
if(a==-1){
break;
}
q=a;
x1=q/2;
while(1){
x2=x1-((x1*x1*x1-q)/(3*x1*x1));
if(x2*x2*x2>q){
r=x2*x2*x2-q;
}
else{
r=q-x2*x2*x2;
}
if(r<0.00001*q){
printf("%lf\n",x2);
break;
}
x1=x2;
}
}
return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <numeric>

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}

int cnt[1000001];

int main(){
  int n = read();
  int num = read();
  int o = 0, g = num;
  if(num==1) o = 1;
  int ex = (n-1)/8;
  cnt[num] = 1;

  for(int i=0;i<ex;i++){
    int num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;

    num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;
  }

  for(int i=0;i<(n-1)%8;i++){
    int num = read();
    if(num==1) o++;
    g = std::gcd(g, num);
    cnt[num]++;
  }

  if(n - o > 80000){
    if(g==1) printf("setwise coprime\n");
    else printf("not coprime\n");
    return 0;
  }

  int use[1000001];
  int max_S = 0;
  for(int i=2;i<=1000000;i++){
    if(use[i]==-1) continue;
    int S = 0;
    for(int j=i;j<=1000000;j+=i) {
      S += cnt[j];
      use[j] = -1;
    }
    if(max_S<S) max_S = S;
  }
  if(max_S<2) printf("pairwise coprime\n");
  else if(max_S != n) printf("setwise coprime\n");
  else printf("not coprime\n");
}


Measured memory_bytes: 11444
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_i()

def dfs(s):
    if int(s) > N:
        return 0
    
    if all([s.count(c) > 0 for c in '753']):
        ret = 1
    else:
        ret = 0

    for c in '753':
        ret += dfs(s+c)

    return ret

print(dfs('0'))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>

typedef long long ll;

using namespace std;

int main(void){
  int n;
  ll x;
  cin >> n >> x;
  vector<ll> psum = vector<ll>(), sum = vector<ll>();
  psum.push_back(1);
  sum.push_back(1);
  for(int i = 1; i <= n; ++i){
    psum.push_back(psum[i-1]*2+1);
    sum.push_back(sum[i-1]*2+3);
  }
  ll ans = 0;
  for(int i = n; i >= 0; --i){
    if (i == 0){
      ++ans;
      break;
    }
    if (x == 1){
      break;
    }
    if (x == sum[i]){
      ans += psum[i];
      break;
    }
    if (x*2-1 == sum[i]){
      ans += psum[i-1]+1;
      break;
    }
    if (x <= sum[i]/2){
      --x;
    }else{
      ans += psum[i-1]+1;
      x -= sum[i-1]+2;
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

void fastio() {
	cin.tie(nullptr);
	cin.sync_with_stdio(false);
}

using LL = long long;
using LD = long double;

const LL MOD = 1e9+7;
const LL INF = LLONG_MAX;
const LL N = 1e6+1;

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

	LL cnt = 0, mx = 0;

	for (LL i = 0; i < s.size(); ++i) {
		if (s[i] == 'R') {
			cnt++;
		}
		else {
			mx = max(mx, cnt);
			cnt = 0;
		}
	}
	mx = max(mx, cnt);
	cout << mx << '\n';
	

}

Measured memory_bytes: 3608
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n, m, s; cin >> n >> m >> s;
	chmin(s, 2500);
	vector<vector<pair<int, pair<ll, ll>>>> g(n);
	rep(i, m)
	{
		int u, v; cin >> u >> v;
		ll a, b; cin >> a >> b;
		--u, --v;
		g[u].push_back(make_pair(v, make_pair(a, b)));
		g[v].push_back(make_pair(u, make_pair(a, b)));
	}
	vector<ll> c(n), d(n);
	rep(i, n)cin >> c[i] >> d[i];
	ll INF = 1e18;
	vector<vector<ll>> dp(n, vector<ll>(2510, INF));
	dp[0][s] = 0;
	queue<pair<int, ll>> q;
	q.push(make_pair(0, s));
	while (!q.empty())
	{
		int now = q.front().first;
		ll sc = q.front().second;
		q.pop();
		for (auto p : g[now])
		{
			int next = p.first;
			ll cost = p.second.first;
			ll time = p.second.second;
			if (sc - cost >= 0 && chmin(dp[next][sc - cost], dp[now][sc] + time))
			{
				q.push(make_pair(next, sc - cost));
			}
		}
		ll plusSc = min(sc + c[now], 2500LL);
		if (chmin(dp[now][plusSc], dp[now][sc] + d[now]))
		{
			q.push(make_pair(now, plusSc));
		}
	}
	for (int i = 1; i < n; ++i)
	{
		ll res = INF;
		rep(j, 2501)chmin(res, dp[i][j]);
		cout << res << endl;
	}
}

Measured memory_bytes: 5400
N = int(input())
S = input()

dp = [[0]*N for _ in range(N)]
for i in range(1, N):
  if S[i] == S[0]:
    dp[0][i] = 1

for i in range(1, N-1):
  for j in range(i+1, N):
    if S[i] == S[j]:
      if dp[i-1][j-1] == j - i:
        dp[i][j] = dp[i-1][j-1]
      else:
        dp[i][j] = dp[i-1][j-1] + 1

ans = 0
for i in range(N):
  ans = max(ans, max(dp[i]))

print(ans)

Measured memory_bytes: 264200
n, q = map(int, input().split())
size = 1
while size < n:
    size *= 2
size = size
seg_tree = [0]*(size*2)

def update(i, x):
    ind = size-1+i
    seg_tree[ind] += x
    while ind>1:
        ind = ind//2
        left = seg_tree[ind*2]
        right = seg_tree[ind*2+1]
        seg_tree[ind] = left + right

def _find(s,t,i,l,r):
    if r < s or t < l:return 0
    if s <= l and r <= t:
        return seg_tree[i]
    else:
        left = _find(s,t,i*2,l, (l+r)//2)
        right = _find(s,t,i*2+1,(l+r)//2+1,r)
        return left+right

def find(s,t):
    return _find(s,t,1,1,size)

for _ in range(q):
    com, x, y = map(int, input().split())
    if not com:
        update(x, y)
    else:
        print(find(x,y))


Measured memory_bytes: 10748
#include <bits/stdc++.h>    
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds; 
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long 
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N       = 1000 * 100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p = LLONG_MAX ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}

signed main()
{
    fastio();
    //cout<<fixed<<setprecision(20);
    //CHECK for LONG LONG and LONG DOUBLE
    /*comment for all except cc/cf    
    #ifndef ONLINE_JUDGE    
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
    #endif//*/
    string s;
    cin>>s;
    if(s[2]==s[3]&&s[4]==s[5])
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;


    printclock;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int d, t, s;
	cin >> d >> t >> s;
	if (t*s >= d)cout << "Yes\n";
	else cout << "No\n";
	system("pause");
	return 0;
}


Measured memory_bytes: 3712
import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    uf = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        a, b = map(int, x.split())
        uf.union(a-1, b-1)

    grp = {}
    for i in range(n):
        grp.setdefault(uf._root(i), []).append(i)

    ans = 0
    for x in grp.values():
        l = len(x)
        if ans < l:
            ans = l
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 48852
#include <iostream> 
#include <algorithm>

using namespace std;

int D[100000 + 10];

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

    for (int i = 0; i < n; i++)
    {
        cin >> D[i];
    }

    sort(D, D + n);

    int middle1 = D[n / 2 - 1], middle2 = D[n / 2];
    int ans = (middle1 == middle2) ? 0 : middle2 - middle1;
    cout << ans << endl;
}

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

void base(int (*paper)[10],int x, int y) {
    if (x - 1 >= 0) {
		paper[y][x - 1]++;
	}
	if (x + 1 < 10) {
		paper[y][x + 1]++;
	}
	if (y - 1 >= 0) {
		paper[y - 1][x]++;
	}
	if (y + 1 < 10) {
		paper[y + 1][x]++;
	}
}

void sqare(int(*paper)[10], int x, int y) {
	if (x - 1 >= 0 && y - 1 >= 0) {
		paper[y - 1][x - 1]++;
	}
	if (x + 1 < 10 && y - 1 >= 0) {
		paper[y - 1][x + 1]++;
	}
	if (y + 1 < 10 && x - 1 >= 0) {
		paper[y + 1][x - 1]++;
	}
	if (y + 1 < 10 && x + 1 < 10) {
		paper[y + 1][x + 1]++;
	}
}

void slant(int(*paper)[10], int x, int y) {
	if (x - 2 >= 0) {
		paper[y][x - 2]++;
	}
	if (x + 2 < 10) {
		paper[y][x + 2]++;
	}
	if (y - 2 >= 0) {
		paper[y - 2][x]++;
	}
	if (y + 2 < 10) {
		paper[y + 2][x]++;
	}
}

int main()
{
	int paper[10][10] = {0};
	int x, y, s;
	char t;
	
	while (cin >> x >> t >> y >> t>> s) {
		paper[y][x]++;
		switch (s) 
		{
		    case 3:slant(paper,x, y);
		    case 2:sqare(paper,x, y);
		    case 1:base(paper,x, y);
		}
	}
	
	int sum = 0,max = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (paper[i][j] > max) {
				max = paper[i][j];
			}
			if (paper[i][j] == 0) {
				sum++;
			}
		}
	}
	cout << sum << endl << max << endl;

	return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
#define maxl 100010
#define inf 2000000001

using namespace std;

int n,ans,res;
int a[maxl],dp[maxl],cnt[16];

inline void prework()
{
	for(int i=0;i<n;i++)
		a[i]=0,cnt[i]=0;
	int u,v,val;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&val);
		a[u]^=val;a[v]^=val;
	}
	for(int i=0;i<n;i++)
		cnt[a[i]]++;
	res=0;ans=0;
	for(int i=1;i<16;i++)
	{
		ans+=cnt[i]/2;
		if(cnt[i]&1)
			res^=(1<<i);
	}		
}

inline int dfs(int s)
{
    if(s==0)
        return 0;
    if(dp[s])
        return dp[s];
    dp[s]=inf;
    for(int i=1;i<16;i++)
        if(s&(1<<i)){
            for(int j=1;j<16;j++){
                if(j!=i&&(s&(1<<j))){
                    int q=i^j;
                    if(s&(1<<q))
                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+2);
                    else
                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+1);
                }
            }

        }
    return dp[s];
}

inline void mainwork()
{
	int x=dfs(res);
	ans+=x;
}

inline void print()
{
	printf("%d\n",ans);
}

int main()
{
	while(~scanf("%d",&n))
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int main(){
    int h, w, ans;
    int num = 0;
    cin >> h >> w;
    vector<string> field_s;
    vector<vector <bool> > field(h, (vector<bool>(w, true)));
    for(int i=0; i<h; i++){
        string str;
        cin >> str;
        field_s.push_back(str);
    }

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(field_s[i][j] == '#'){
               field[i][j] = false;
               num++;
            }
        }
    }

    queue<pair<int, int> > que;
    pair<int, int> p;
    vector<vector <int> > dist(h, (vector<int>(w, -1)));

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

    que.push(pair<int, int>(0, 0));
    dist[0][0] = 0;

    while(!que.empty()){
        p = que.front();
        que.pop();
        for(int i=0; i<4; i++){
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];
            if(ny >= h || ny < 0 || nx >= w || nx < 0) continue;
            if(!field[ny][nx]) continue;
            if(dist[ny][nx] != -1) continue;

            dist[ny][nx] = dist[p.first][p.second] + 1;
            que.push(pair<int, int>(ny, nx));
        }
    }

    if(dist[h-1][w-1] == -1) ans = -1;
    else ans = h*w - dist[h-1][w-1] - num - 1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
int main() {
    int N;
    cin >> N;
    map<int, int> m;
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if(!m.count(a)) m[a] = 0;
        m[a]++;
    }
    if(m.size() == 2) {
        int a, b, x, y;
        auto i = m.begin();
        tie(x, a) = *i;
        i++;
        tie(y, b) = *i;
        if(x > y) {
            swap(x, y);
            swap(a, b);
        }
        if(y - x == 1 && 2 * a + b >= 2 * y && y > a) {
            cout << "Yes" << endl;
            return 0;
        }
    } else if(m.size() == 1) {
        int a, x;
        tie(x, a) = *m.begin();
        if(x == a - 1 || a >= 2 * x) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 4992
//----------------------------------------------------------------------
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
//----------------------------------------------------------------------

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

int main(void) {
    int n, r;
    cin >> n >> r;
    if(n<10) cout << r + 100 * (10-n) << endl;
    else cout << r<< endl;
    return 0;
}

Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,C=MI()
    D=LLIN(C)
    c=LLIN(N)
    group = [defaultdict(int) for _ in range(3)]
    for i in range(N):
        for j in range(N):
            col = c[i][j]-1
            group[(i+j)%3][col]+=1
    
    ans = inf
    Colors = [i for i in range(C)]
    for it in permutations(Colors,r=3):
        tmp = 0
        for i,col in enumerate(it):
            for col_ori,num in group[i].items():
                tmp += D[col_ori][col]*num

        ans = min(ans, tmp)
    print(ans)
if __name__ == '__main__':
    main()

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

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

int T;
ll A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>D;
		
		if(D<B || A<B) {
			cout<<"No"<<endl;
			continue;
		}
		if(C>=B-1) {
			cout<<"Yes"<<endl;
			continue;
		}
		
		D=__gcd(D,B);
		ll L=((A-(B-1))%B+B)%B;
		ll R=((A-(C+1))%B+B)%B;
		if(R>=L) {
			if(L/D == R/D && L%D) {
				cout<<"Yes"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
		}
		else {
			cout<<"No"<<endl;
		}
		
		
	}
}


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


Measured memory_bytes: 256
N, M = map(int, input().split())
LR = [map(int, input().split()) for _ in range(M)]

Min, Max = 1, N

for i in range(M):
    L, R = LR[i]
    Min = max(Min, L)
    Max = min(Max, R)

print(max(Max - Min + 1, 0))

Measured memory_bytes: 75864
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N, T, A; cin >> N >> T >> A;
    vector<int> H(N);
    for(int i = 0; i < N; i++)
    {
        cin >> H.at(i);
    }
    int temp = abs(1000*A - 1000*T + H.at(0)*6);
    int ans = 1;
    for(int i = 0 ; i < N; i++)
    {
        if(temp > abs(1000*A - 1000*T + H.at(i)*6) )
        {
            temp = abs(1000*A - 1000*T + H.at(i)*6);
            ans = i + 1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256