akhauriyash/Code-Regression huggingface dataset:
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) { // p must be a prime, O(log p)
    assert ((x % p + p) % p != 0);
    return powmod(x, p-2, p);
}
constexpr int mod = 1e9+7;
int fact(int n) {
    static vector<int> memo(1, 1);
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n+1);
        repeat_from (i, l, n+1) memo[i] = memo[i-1] *(ll) i % mod;
    }
    return memo[n];
}
int choose(int n, int r) { // O(n) at first time, otherwise O(\log n)
    if (n < r) return 0;
    r = min(r, n - r);
    return fact(n) *(ll) inv(fact(n-r), mod) % mod *(ll) inv(fact(r), mod) % mod;
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n + 1); repeat (i, n + 1) scanf("%d", &a[i]);
    // solve
    int dup[2]; {
        vector<int> used(n, -1);
        repeat (i, n + 1) {
            if (used[a[i] - 1] != -1) {
                dup[0] = used[a[i] - 1];
                dup[1] = i;
                break;
            }
            used[a[i] - 1] = i;
        }
    }
    int l = dup[0];
    int m = dup[1] - (dup[0] + 1);
    int r = n + 1 - (dup[1] + 1);
    repeat_from (k, 1, n + 2) {
        ll result = choose(n + 1, k) - choose(l + r, k - 1);
        result = (result + mod) % mod;
        printf("%lld\n", result);
    }
    return 0;
}


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



int main()
{
	long long int N,M;
	cin >> N>>M;

	long long int ans;

	if (N >= 2 && M >= 2) 
		ans = (N - 2)*(M - 2);
	else if (N+M!=2)
		ans=N+M-3;
	else ans = 1;


	cout <<ans<< endl;

	return 0;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

struct edge {
	int to, cost;
	edge(int t,int c):to(t),cost(c) {}
};

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

ll mypow(ll x,ll n,ll m) {	//xのn乗をmで割った余り
	if(n==0) return 1;
	if(n%2==0) return mypow(x*x%m,n/2,m);
	else return x*mypow(x,n-1,m)%m;
}

//-----------------------------------------------------------------------------

string a,b;

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

	cin>>a>>b;
	REP(i,b.size()) {
		cout<<a[i]<<b[i];
	}
	if(a.size()>b.size()) {
		int sz=a.size()-1;cout<<a[sz];
	}
	cout<<endl;

	return 0;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N; cin >> N;
    i64 s = 0;
    for (i64 i = 1; i * i <= N; i++) {
        if (N % i > 0) continue;
        auto f = [&](i64 div) {
            i64 m = div - 1;
            if (m == 0) return;
            if (N / m == N % m) s += m;
        };
        f(i);
        f(N / i);
    }
    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }

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

  int n; cin >> n;
  string s; cin >> s;
  // '(' < ')'
  stack<char> st;

  for (int i = 0; i < n; ++i) {
    if (st.empty()) st.push(s[i]);
    else if (st.top() == '(' && s[i] == ')') {
      st.pop();
    } else {
      st.push(s[i]);
    }
    //debug(st.size());
  }

  int left = 0, right = 0;
  while (!st.empty()) {
    char c = st.top(); st.pop();
    left += c == '(';
    right += c == ')';
  }
  //debug(left);debug(right);
  for (int i = 0; i < right; ++i) cout << '(';
  cout << s;
  for (int i = 0; i < left; ++i) cout << ')';
  cout << '\n';

  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

var (
	priceList []int
)

func main() {
	var n int

	fmt.Scanf("%d", &n)

	gems := make([]Gem, n)

	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &gems[i].Value)
	}

	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &gems[i].Cost)
	}

	X := 0
	Y := 0

	// 再帰での探索
	buy(n-1, gems, X, Y)

	sort.Sort(sort.Reverse(sort.IntSlice(priceList)))

	fmt.Println(priceList[0])

}

type Gem struct {
	Value int
	Cost  int
}

func buy(now int, gems []Gem, X int, Y int) {
	if now < 0 {
		priceList = append(priceList, X-Y)
	} else {
		// now番目を買わない
		buy(now-1, gems, X, Y)

		// now番目を買う
		X += gems[now].Value
		Y += gems[now].Cost
		buy(now-1, gems, X, Y)
	}
}


Measured memory_bytes: 32000
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(ll i = (ll)(n)-1;i >= 0;--i)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
//#define int ll
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int n,k;
  cin >> n >> k;
  vi x(k);
  REP(i,k) cin >> x.at(i);
  vi y(10);
  set<int> d;
  REP(i,10) y.at(i) = i;
  set_difference(ALL(y),ALL(x),inserter(d,d.end()));
  for(;;++n){
    bool fl = false;
    int m = n;
    for(;m>0;m/=10){
      if(d.find(m%10)==d.end()) {
        fl = false;
        break;
      }
      if(m<10) fl =true;
    }
    if(fl) break;
  }
  cout << n << endl;
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)













int main(){
    ll a, b;
    cin >> a >> b;
    cout << max({a + b, a - b, a * b}) << endl;
}


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

long long MOD=1000000007;

int main(){
	int N,K;
	cin >> N >> K;
	vector<long long> A(N);
	for(auto &i:A)cin >> i;
	
	vector<long long> pos,neg,zero;
	for(int i=0;i<N;i++){
		if(A[i]>0)pos.push_back(A[i]);
		if(A[i]<0)neg.push_back(A[i]);
		if(A[i]==0)zero.push_back(A[i]);
	}
	sort(pos.begin(),pos.end());
	sort(neg.begin(),neg.end());
	
	if(zero.size()>0){
		if((min((int)neg.size(),K)/2*2)<(K-(int)pos.size())){
			//ans...0
			cout << "0" << endl;
			return 0;
		}
	}
	if(zero.size()==0){
		
		if((min((int)neg.size(),K)/2*2)<(K-(int)pos.size())){
			//ans...negative
			reverse(neg.begin(),neg.end());
			long long ans=neg[0]+MOD;
			neg.erase(neg.begin());
			K--;
			
			if(K%2){
				ans*=pos[0];
				ans%=MOD;
				pos.erase(pos.begin());
				K--;
			}
			int negp=0,posp=0;
			while(negp+posp<K){
				if(posp+1>=pos.size()){
					for(int i=0;i<2;i++){
						ans*=-1*neg[negp];
						ans%=MOD;
						negp++;
					}
				}
				else if(negp+1>=neg.size()){
					for(int i=0;i<2;i++){
						ans*=pos[posp];
						ans%=MOD;
						posp++;
					}
				}
				else{
					if(pos[posp]*pos[posp+1]>neg[negp]*neg[negp+1]){
						for(int i=0;i<2;i++){
						ans*=-1*neg[negp];
						ans%=MOD;
						negp++;
						}
					}
					else{
						for(int i=0;i<2;i++){
						ans*=pos[posp];
						ans%=MOD;
						posp++;
						}
					}
				}
			}
			cout << ans << endl;
			return 0;
		}
	}
	//ans...positive
	reverse(pos.begin(),pos.end());
	long long ans=1;
	if(K%2){
		ans*=pos[0];
		ans%=MOD;
		pos.erase(pos.begin());
		K--;
	}
	int posp=0,negp=0;
	while(posp+negp<K){
		if(posp+1>=pos.size()){
			for(int i=0;i<2;i++){
				ans*=-1*neg[negp];
				ans%=MOD;
				negp++;
			}
		}
		else if(negp+1>=neg.size()){
			for(int i=0;i<2;i++){
				ans*=pos[posp];
				ans%=MOD;
				posp++;
			}
		}
		else{
			if(pos[posp]*pos[posp+1]<neg[negp]*neg[negp+1]){
				for(int i=0;i<2;i++){
				ans*=-1*neg[negp];
				ans%=MOD;
				negp++;
				}
			}
			else{
				for(int i=0;i<2;i++){
				ans*=pos[posp];
				ans%=MOD;
				posp++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6852
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int n, k, q; cin >> n >> k >> q;
  vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  vector<bool> b(n, true);
  vector<P> s(n);
  for (int i = 0; i < n; i++) {
    s[i].first = a[i];
    s[i].second = i;
  }
  sort(s.begin(), s.end());
  int res = 2e9;
  for (int i = 0; i < n - k + 1; i++) {
    vector<int> c;
    int l = 0, r = 1;
    while (r <= n) {
      while (r < n and b[r]) r++;
      vector<int> tmp;
      tmp.assign(a.begin() + l, a.begin() + r);
      sort(tmp.begin(), tmp.end());
      for (int j = 0; j < r - l - k + 1; j++) {
        c.push_back(tmp[j]);
      }
      if (r == n) break;
      l = r;
      while (l < n and not b[l]) l++;
      r = l + 1;
    }
    if (c.size() < q) continue;
    sort(c.begin(), c.end());
    res = min(res, c[q - 1] - c[0]);
    b[s[i].second] = false;
  }
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<pair<string, int>> vec(N);
    rep(i, N) {
        cin >> vec[i].first >> vec[i].second;
    }
    string X;
    cin >> X;
    int ans = 0;
    bool flag = false;
    rep(i, N) {
        if (flag) ans += vec[i].second;
        if (vec[i].first == X) flag = true;
    }
    cout << ans << endl;
    return 0;
}

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


int main(){

    ll S,W;

    cin >> S >> W;

    if(S <= W)
    {
        cout << "unsafe";
    }else{
        cout << "safe";
    }


    return 0;
}


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

int bubblesort(int n, int a[])
{
    int cnt = 0;
    for (int i = 0;i < n;i++)
    {
        for (int j = n-1;j >= i+1;j--)
        {
            if (a[j] < a[j-1])
            {
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
                cnt++;
            }
        }
    }
    return cnt;
}

int main ()
{
    int n, cnt = 0;
    cin >> n;
    int a[n];
    for (int i = 0;i < n;i++) cin >> a[i];
    
    cnt = bubblesort (n, a);
    
    for (int i = 0;i < n;i++)
    {
        cout << a[i];
        if (i < n-1) cout << " ";
    }
    cout << endl << cnt << endl;
    return 0;
}


Measured memory_bytes: 3112
#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;
const int MOD = (int)1e9 + 7;

int main(){
  int h,w;
  cin>>h>>w;
  vector<string> grid(h);
  rep(i,h) cin>>grid[i];

  vector<vector<int> > L(h,vector<int>(w));
  vector<vector<int> > R(h,vector<int>(w));
  vector<vector<int> > U(h,vector<int>(w));
  vector<vector<int> > D(h,vector<int>(w));

  rep(i,h) rep(j,w){
    if (grid[i][j] == '#'){
      L[i][j] = 0;
      continue;
    }
    if(j==0){
      L[i][j] = 1;
      continue;
    }
    L[i][j] = L[i][j-1] + 1;
  }

  rep(i,h) rep(j,w){
    if (grid[i][w-j-1] == '#'){
      R[i][w-j-1] = 0;
      continue;
    }
    if(j==0){
      R[i][w-j-1] = 1;
      continue;
    }
    R[i][w-j-1] = R[i][w-j] + 1;
  }

  rep(i,h) rep(j,w){
    if (grid[i][j] == '#'){
      U[i][j] = 0;
      continue;
    }
    if(i==0){
      U[i][j] = 1;
      continue;
    }
    U[i][j] = U[i-1][j] + 1;
  }

  rep(i,h) rep(j,w){
    if (grid[h-i-1][j] == '#'){
      D[h-i-1][j] = 0;
      continue;
    }
    if(i==0){
      D[h-i-1][j] = 1;
      continue;
    }
    D[h-i-1][j] = D[h-i][j] + 1;
  }

  int ans = 0;
  rep(i,h) rep(j,w){
    int buf =  L[i][j] + R[i][j] + U [i][j] + D[i][j] - 3;
    if (buf > ans) ans = buf;
  }

  cout<<ans<<endl;
}



Measured memory_bytes: 67200
# include<iostream>
# include<vector>
# include<time.h>
# include<random>
using namespace std;
using vector1 = vector<int>;
using vector2 = vector<vector1>;
int last(int d, int j, vector1 t){ //d日目から数えてタイプjのコンテストが最後に開催された日を計算
  for(int i=d; i>=1; i--){
    if(t[i] == j) return i;
  }
  return 0;
}
int penalty(vector1 c, int d, vector1 t){ //ペナルティの合計を計算
  int m = 0;
  for(int i=1; i<=26; i++){
    m += c[i] * (d - last(d, i, t));
  }
  return m;
}
int calc_score(int d, int j, int c, vector1 t){ //開催されるコンテストが変更された場合のスコア差を算出
  int s = 1;
  if(d > 1) s = d - last(d-1, j, t);

  int r = s * c; //1日分のスコア差
  int sum = 0;  //スコア差の合計
  int i = d;
  do{
    sum += r;
    i++;
    if((int)t.size() < i) break;
  }while(t[i] != j);
  return sum;
}
void swap_(int d1, int d2, vector1& t){
  int tmp = t[d1]; t[d1] = t[d2]; t[d2] = tmp;
  return;
}
int main(){
  clock_t start = clock();
  int D; cin >> D; //日数d
  vector1 c(26+1, 0); for(int i=1; i<=26; i++) cin >> c[i]; //ペナルティc
  vector2 s(D+1, vector1(26+1)); //あるコンテストが開催された場合の満足度s
  for(int i=1; i<=D; i++){
    for(int j=1; j<=26; j++){
      cin >> s[i][j];
    }
  }
  vector1 t(D+1, 0); for(int i=1; i<=D; i++) t[i] = (i % 26) + 1;
/*  vector1 v(D+1, 0); //スコアv
  for(int i=1; i<=D; i++){
    v[i] = s[i][t[i]];
    v[i] -= penalty(c, i, t);
  }*/
  int score = 0;
  for(int i=1; i<=D; i++){
    score += s[i][t[i]];
    score -= penalty(c, i, t);
  }
  clock_t end = clock();
//  cout << score <<"\n";
  random_device random_a;
  auto num = random_a();
  mt19937 random_b;
  //num = 3180901575;
  random_b.seed(num);
//  cout <<"num: "<< num <<"\n";

  while((double)(end - start) / CLOCKS_PER_SEC < 1.9){
    int r = (int)random_b();
    if(r > 0){
      int p = ((int)random_b() * random_b() % 26) + 1;
      int d = ((int)random_b() * random_b() % D) + 1;
      int old = t[d];
      t[d] = p;
      int up = calc_score(d, p, c[p], t); //増えるスコア
      int down = calc_score(d, old, c[old], t); //減るスコア
      int l = up - down + s[d][p] - s[d][old];
      if(l > 0){
        score += l;
      }else{
        t[d] = old;
      }
    }else{
      int d1 = ((int)random_b() * random_b() % D) + 1;
      int d2 = ((int)random_b() * random_b() % D) + 1;
      int l_old_d1 = calc_score(d1, t[d1], c[t[d1]], t);
      int l_old_d2 = calc_score(d2, t[d2], c[t[d2]], t);
      //cout << t[d1] <<"  "<< t[d2] <<"\n";
      swap_(d1, d2, t);
      //cout << t[d1] <<"  "<<t[d2] <<"\n";
     // break;
      int l_d1 = calc_score(d1, t[d1], c[t[d1]], t);
      int l_d2 = calc_score(d2, t[d2], c[t[d2]], t);
      int l = l_d1 + l_d2 - l_old_d1 - l_old_d2 + s[d1][t[d1]] - s[d1][t[d2]] + s[d2][t[d2]] - s[d2][t[d1]];
      if(l >0){
        score += l;
      }else{
        swap_(d1, d2, t);
      }
    }
    end = clock();
  }
  for(int i=1; i<=D; i++){
    cout << t[i] <<"\n";
  }
  /*cout << score <<"\n";
  int score2=0;
  for(int i=1; i<=D; i++){
    score2 += s[i][t[i]];
    score2 -= penalty(c, i, t);
  }
  cout <<score2 <<"\n";*/
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  int res = n;
  for(int i = 0; i <= n; ++i){
    int a = 0;
    int t = i;
    while(t > 0) a += t % 6, t /= 6;
    t = n -i;
    while(t > 0) a += t % 9, t /= 9;
    res = min(res, a);
  }
  
  cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct data{
	ll t,a,id;
	data(){}
	data(ll tt,ll aa,ll ii){
		t=tt;
		a=aa;
		id=ii;
	}
	bool operator<(const data &d)const{
		return t<d.t;
	}
};

ll x,k,q;
ll r[100005];
data d[100005];
ll res[100005];

int main(void){
	scanf("%lld",&x);
	scanf("%lld",&k);
	for(int i=0;i<k;i++){
		scanf("%lld",&r[i]);
	}
	r[k]=1000000001;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		scanf("%lld%lld",&d[i].t,&d[i].a);
		d[i].id=i;
	}
	sort(d,d+q);
	ll minix=0,miniv=0,maxix=x,maxiv=x;
	int l=0;
	ll prev=0;
	for(int i=0;i<=k;i++){
		ll cost=r[i]-prev;
		while(l<q && d[l].t<=r[i]){
			ll now=miniv+(d[l].a-minix);
			if(d[l].a<=minix){
				now=miniv;
			}
			if(d[l].a>=maxix){
				now=maxiv;
			}
			if(i%2==0){
				res[d[l].id]=max(0LL,now-(d[l].t-prev));
			}else{
				res[d[l].id]=min(x,now+(d[l].t-prev));
			}
			l++;
		}
		if(i%2==0){
			if(miniv<=cost){
				minix+=cost-miniv;
				minix=min(minix,x);
				miniv=0LL;
			}else{
				miniv-=cost;
			}
			if(maxiv<=cost){
				maxix=minix;
				maxiv=0LL;
			}else{
				maxiv-=cost;
			}
		}else{
			if(miniv+cost>=x){
				minix=x;
				miniv=x;
			}else{
				miniv+=cost;
			}
			if(maxiv+cost>=x){
				maxix+=(x-cost-maxiv);
				maxix=max(maxix,0LL);
				maxix=max(maxix,minix);
				maxiv=x;
			}else{
				maxiv+=cost;
			}
		}
		prev=r[i];
	}
	for(int i=0;i<q;i++){
		printf("%lld\n",res[i]);
	}
	return 0;
}

Measured memory_bytes: 5120
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int n  = sc.nextInt();
        int[] a = new int[n];

        double res = 0;

        for(int i=0; i<n; i++) {
            res += 1d / sc.nextInt();
        }

        System.out.println(1/res);

    }


}


Measured memory_bytes: 21716
#include <stdio.h>

int main(){
	int n, h[100];
	int i, result = 0;
	
	scanf("%d", &n);
	for(i = 0; i < n; i++) scanf("%d", &h[i]);
	
	while(1){
		for(i = 0; i < n; i++){
			if(h[i] > 0) break;
		}
		if(i == n) break;
		for(; i < n; i++){
			if(h[i] == 0) break;
			h[i]--;
		}
		result++;
	}
		
	printf("%d\n", result);
	return 0;
}


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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;
const int INF = pow(2, 30) - 1;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

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

    ll H,W,h,w;
    string S;
    cin >> H>>W>>h>>w;

    cout << (H - h) * (W - w) << endl;


}


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

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

  vector<int> a(n);
  rep(i, n) cin >> a.at(i);

  sort(a.begin(), a.end());
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    x -= a.at(i);
    if (x < 0) {
      break;
    }
    cnt++;
    if (i == n - 1 && x > 0) {
      cnt--;
    }
  }

  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
n, m, x = map(int, input().split())
a = list(map(int, input().split()))

go_left = 0
go_right = 0

for i in range(x, n+1):
    if a.count(i) == 1:
        go_right += 1

for j in range(0, x):
    if a.count(j) == 1:
        go_left += 1

print(min(go_left, go_right))


Measured memory_bytes: 61984
def main():
    n=int(input())
    s=input()
    r=[]
    g=[]
    b=[]
    rdict={}
    gdict={}
    bdict={}
    ans=0
    for i in range(n):
        if s[i]=='R':
            r.append(i)
            rdict[2*i]=2*i
        if s[i]=='G':
            g.append(i)
            gdict[2*i]=2*i
        if s[i]=='B':
            b.append(i)
            bdict[2*i]=2*i
    ans=len(r)*len(g)*len(b)
    for i in r:
        for j in g:
            if i+j in bdict:
                ans-=1
    for i in g:
        for j in b:
            if i+j in rdict:
                ans-=1
    for i in b:
        for j in r:
            if i+j in gdict:
                ans-=1
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9540
a11, a12, a13 = map(int, input().split())
a21, a22, a23 = map(int, input().split())
a31, a32, a33 = map(int, input().split())
n = int(input())
b = [int(input()) for i in range(n)]
c = 0
if a11 in b and a12 in b and a13 in b:
    c += 1
if a21 in b and a22 in b and a23 in b:
    c += 1
if a31 in b and a32 in b and a33 in b:
    c += 1
if a11 in b and a21 in b and a31 in b:
    c += 1
if a12 in b and a22 in b and a32 in b:
    c += 1
if a13 in b and a23 in b and a33 in b:
    c += 1
if a11 in b and a22 in b and a33 in b:
    c += 1
if a13 in b and a22 in b and a31 in b:
    c += 1
if c > 0:
    print("Yes")
else:
    print("No")

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A + B == C + D) {
    cout << "Balanced" << endl;
  } else if (A + B > C + D) {
    cout << "Left" << endl;
  } else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r = sc.nextInt();
        if(x + r <= W && x - r >= 0 && y + r <= H && y - r >= 0)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


Measured memory_bytes: 26332
#include<iostream>
using namespace std;
int main() {
  int r,g,b;
  cin >> r >> g >> b;
  if((r*100+g*10+b) % 4 == 0) {
    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<(int)(n);i++)
#define REPS(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
using ll = long long;
using ld = long double;

int main(void) {
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    int A[N];
    REP (i, N) {
        A[i] = S.at(i) - '0';
    }

    int block[N] = {};
    for (int i = 1; i < N; i++) {
        if (A[i] == A[i-1]) {
            block[i] = block[i-1];
        } else {
            block[i] = block[i-1] + 1;
        }
    }

    int ans = 0, sentinel;
    REP (i, N) {
        if (A[i] == 0) {
            sentinel = lower_bound(block, block+N, block[i]+K*2) - block;
        } else {
            sentinel = lower_bound(block, block+N, block[i]+K*2+1) - block;
        }
        ans = max(ans, sentinel - i);
    } 

    cout << ans << endl;
}

Measured memory_bytes: 1280
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		while(solve());
	}
	
	public static boolean solve() {
		char[] s = sc.next().toCharArray();
		if (s[0] == '#') {
			return false;
		}
		int n = s.length;
		for(int i=0;i<n;i++) {
			s[i] -= '1';
		}
		int[][][][] dp = new int[2][2][9][9];
		for(int i=0;i<9;i++) {
			for(int j=0;j<9;j++) {
				for(int k=0;k<2;k++) {
					dp[0][k][i][j] = i == 4 || j == 4 ? 1 << 29 : 0;
				}
			}
		}
		int now = 0;
		int next = 1;
		for(int i=0;i<n;i++) {
			for(int j=0;j<2;j++) {
				for(int k=0;k<9;k++) {
					Arrays.fill(dp[next][j][k], 1 << 29);
				}
			}
			for(int j=0;j<2;j++) {
				for(int f1=0;f1<9;f1++) {
					for(int f2=0;f2<9;f2++) {
						//use left
						if (valid(s[i], f2)) {
							dp[next][0][s[i]][f2] = Math.min(dp[next][0][s[i]][f2], dp[now][j][f1][f2] + (j == 0 ? 1 : 0));
						}
						//use right
						if (valid(f1, s[i])) {
							dp[next][1][f1][s[i]] = Math.min(dp[next][1][f1][s[i]], dp[now][j][f1][f2] + (j == 1 ? 1 : 0));
						}
					}
				}
			}
			now = 1 - now;
			next = 1 - next;
		}
		int min = 1 << 29;
		for(int i=0;i<2;i++) {
			for(int f1=0;f1<9;f1++) {
				for(int f2=0;f2<9;f2++) {
					min = Math.min(min, dp[now][i][f1][f2]);
				}
			}
		}
		System.out.println(min);
		return true;
	}
	
	public static boolean valid(int f1,int f2) {
		return f1 != 4 && f2 != 4 && f1 % 3 <= f2 % 3;
	}

}

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

using namespace std;

const long long mo = 998244353;

long long dp[3010][3010];
int a, b, c, d;
int main()
{
   cin>>a>>b>>c>>d;

   c-=a;
   d-=b;

   dp[0][0] = 1;

   for (int i = 0;i<=c;i++)
    for (int j = 0;j<=d;j++)
    if (i+j)
   {
       if (i) dp[i][j]+=dp[i-1][j]*(j + b);
       if (j) dp[i][j]+=dp[i][j-1]*(i + a);
       if (i && j)
       dp[i][j]-=dp[i-1][j-1] * (j - 1 + b) * ( i - 1 + a);
       dp[i][j]%=mo;
       if (dp[i][j] < 0) dp[i][j]+=mo;
   }

   cout<<dp[c][d];
}


Measured memory_bytes: 74072
n=int(input())
a=list(map(int,input().split()))
m=sum(a)
k=0
l=0
for i in range(n):
    k+=a[i]
    if k>m//2:
        l=i
        break
if n==2:
    print(abs(a[1]-a[0]))
else:
    print(min(abs(k-(m-k)),abs(k-a[i]-(m-(k-a[i])))))


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
#else
#define dbg(x)
#endif

#define X first
#define Y second

int main(){
    std::ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pii> arr(n);
    for (int i = 0; i < n; i++){
        cin >> arr[i].X;
        arr[i].Y = i;
    }
    sort(arr.begin(), arr.end());
    int res = 0;
    for (int i = 0; i < n; i++){
        int p = (i & 1) ^ ((arr[i].Y) & 1);
        res += p;
    }
    res = (res + 1) / 2;
    cout << res << endl;


    return 0;
}


Measured memory_bytes: 1024
n,m,x=map(int,input().split())
ca=[]
ans=-1
for i in range(n):
  ca.append(list(map(int,input().split())))
for i in range(1<<n):
  suma=[0]*(m+1)
  for j in range(n):
    if ((i>>j)&1):
      for k in range(m+1):
        suma[k]+=ca[j][k]
  chk=True
  for j in range(1,m+1):
    if suma[j]<x:
      chk=False
      break
  if chk and (ans==-1 or ans>suma[0]):
    ans=suma[0]
print(ans)

Measured memory_bytes: 9224
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=readln.splitter;foreach(ref v;t){v=r.front.to!T;r.popFront;}}

void main()
{
  int n, m, x; readV(n, m, x);
  int[] a; readA(m, a);

  auto as = a.assumeSorted;
  writeln(min(as.lowerBound(x).length, as.upperBound(x).length));
}


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

bool Check(const std::vector<int> Wi, int k, int P)
{
    int p = 0;
    --k;
    for(int i = 0; i < Wi.size(); ++i){
        if(P - p >= Wi[i]){
            p += Wi[i];
        }else{
            p = Wi[i];
            --k;
        }
    }
    return k >= 0;
}
int main()
{
    int n,k;
    std::cin >> n >> k;
    std::vector<int> Wi(n);
    for(int i = 0; i < n; ++i){
        std::cin >> Wi[i];
    }

    int MaxValue = *std::max_element(Wi.begin(), Wi.end());
    int MaxBad  = std::floor(std::accumulate(Wi.begin(), Wi.end(), 0) / k - 0.1);
    // int MinGood = std::ceil(((double)n / k)) * MaxValue;
    int MinGood = std::accumulate(Wi.begin(), Wi.end(), 0);
    while(MaxBad + 1 != MinGood){
        int P = (MaxBad + MinGood) / 2;
        if(MaxValue <= P && Check(Wi, k, P)){
            MinGood = P;
        }else{
            MaxBad = P;
        }
    }
    std::cout << MinGood << std::endl;
    return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>

int main(void){
  int r,c,i,j;
  static int s[101][101];

  scanf("%d%d",&r,&c);

  for(i=0;i<=r;i++){
    for(j=0;j<c;j++){
      scanf("%d", &s[i][j]);
      printf("%d ", s[i][j]);
      s[i][c] += s[i][j];
      s[r][j] += s[i][j];
    }
    printf("%d\n",s[i][c]);
  }

  return 0;
}


Measured memory_bytes: 2052
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n = k()

print((10**n-2*9**n+8**n) % mod)

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

int main() {

	// 2つの整数
	int a, b;
	
	// a, bを入力
	cin >> a >> b;
	
	// 小数点以下を切り上げた平均
	int avg = (a + b + 1) / 2;
	
	// 結果の出力
	cout << avg << endl;
}

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

const long long INF = 1LL<<60;
const int inf = 1 << 30;
const int mod = 1e9+7;


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; }

long long f(long long a, long long b, long long x){
  return ((a * x) / b) - a * (x / b);
}

int main(){
  int k;
  cin >> k;
  int a, b;
  cin >> a >> b;

  for (int i=a; i<=b; i++){
    if(i % k == 0){
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
}


Measured memory_bytes: 3620
from scipy.sparse.csgraph import *
import numpy as np
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
ans = 0

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = shortest_path(G).astype(int)
for a,b,c in E:
  if F[a-1][b-1]!=c:
    ans+=1

print(ans)

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

int main() {
	int n, k, m = 1 << 30;
	cin >> n >> k;
	auto r = 0.;
	for (int i = 1; i <= n; i++) {
		while (m / 2 >= (k + i - 1) / i) m /= 2;
		r += 1. / m;
	}
	cout.precision(18);
	cout << r / n << endl;
	return 0;
}


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

int main(){
  int n, a=0, b=0;
  cin >> n;
  vector<int> x(n);

  for(int i=0; i<n ; i++){
    cin >> x.at(i);
  }
  sort(x.begin(), x.end());
  reverse(x.begin(),x.end());
  for(int i=0 ; i< n; i += 2){
    a += x.at(i);
  }
  for(int i=1 ; i< n; i += 2){
    b += x.at(i);
  }
  cout << a - b << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

def solve(A, B):
    a = A / 0.08
    b = B / 0.10
    c = int(max(a, b)) + 1
    answer = -1
    while int(c * 0.08) == A and int(c * 0.10) == B:
        answer = c
        c -= 1
    return answer


def main():
    A, B = [int(n) for n in input().split()]
    print(solve(A, B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
package main

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

const mod = 1000000007

// 1MB
const ioBufferSize = 1 * 1024 * 1024

var sc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	sc.Split(bufio.ScanWords)
	return sc
}()

func next() string {
	sc.Scan()
	return sc.Text()
}

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

func main() {
	w := next()
	m := map[byte]int{}

	for i := 0; i < len(w); i++ {
		m[w[i]]++
	}

	for _, count := range m {
		if count%2 == 1 {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 640
main(){
  int a,b,y,c;
  while(scanf("%d %d",&a,&b)!=-1)
    {
      c=0;
      y=a+b;
      while(y>0){
	y=y/10;
	c++;
      }
      printf("%d\n",c);
    }
  exit(0);
}

Measured memory_bytes: 0
/*
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Threading.Tasks;

namespace Matrix_Multiplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            int n = int.Parse(input[0]);
            int m = int.Parse(input[1]);
            int l = int.Parse(input[2]);
            
            int[,] a = new int[n, m];
            int[,] b = new int[m, l];
            int[,] c = new int[n, l];
            for (int i = 0; i < n; ++i)
            {
                String[] str = Console.ReadLine().Split(' ');
                for (int j = 0; j < m; ++j)
                {
                    a[i, j] = int.Parse(str[j]);
                }
            }
            for (int i = 0; i < m; ++i)
            {
                String[] str = Console.ReadLine().Split(' ');
                for (int j = 0; j < l; ++j)
                {
                    b[i, j] = int.Parse(str[j]);
                }
            }
            c = multi_matrix(a, b, n, m, l);
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < l; ++j)
                {
                    if(j != (l - 1)) Console.Write("{0} ",c[i,j]);
                    else Console.WriteLine("{0}",c[i,j]);
                }
            }
        }

        static int[,] multi_matrix(int[,] a, int[,] b, int n, int m, int l)
        {
            int[,] ans = new int[n, l];
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < l; ++j)
                {
                    for (int k = 0; k < m; ++k)
                    {
                        ans[i,j] += a[i,k] * b[k,j];
                    }
                }
            }
            return ans;
        }
    }
}
*/

using System;

namespace ITP1_7_D
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] strs = Console.ReadLine().Split(' ');
            int n = int.Parse(strs[0]);
            int m = int.Parse(strs[1]);
            int l = int.Parse(strs[2]);
            int[,] a = ReadMatrix(n, m);
            int[,] b = ReadMatrix(m, l);
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < l; j++)
                {
                    long sum = 0;
                    for (int k = 0; k < m; k++) sum += (long)a[i, k] * b[k, j];
                    Console.Write(sum);
                    if (j < l - 1) Console.Write(" ");
                }
                Console.WriteLine();
            }
        }

        static int[,] ReadMatrix(int r, int c)
        {
            int[,] m = new int[r, c];
            for (int i = 0; i < r; i++)
            {
                string[] strs = Console.ReadLine().Split(' ');
                for (int j = 0; j < c; j++) m[i, j] = int.Parse(strs[j]);
            }
            return m;
        }
    }
}


Measured memory_bytes: 9492
from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
N, P = map(int, input().split())
A = list(map(int, input().split()))

modA = [i % 2 for i in A]
odd = modA.count(1)
even = modA.count(0)

even_count = 1
for i in range(1, even+1):
    even_count += combinations_count(even, i)

if P == 0:
    """
    evenからは好きなだけ選べる
    それに対してoddから偶数個を選ぶ
    """
    odd_count = 0
    for i in range(0,odd+1,2):
        odd_count += combinations_count(odd, i)
    print(even_count * odd_count)
else:
    """
    evenから好きなだけ選べる
    oddから奇数個を選ぶ
    """
    odd_count = 0
    for i in range(1,odd+1,2):
        odd_count += combinations_count(odd, i)
    print(even_count * odd_count)



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x;
	scanf("%d" , &x);
	if(x>=1&&x<=3000){
		if(x<1200){
			printf("ABC");
		}
		else if(x>=1200){
			printf("ARC");
		}
		else{
		printf("Error");
		}
	}
	else{
		printf("Error");
	}
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String args[]) throws IOException{
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	int n=Integer.parseInt(br.readLine());
	String str[]=br.readLine().split(" ");
	int a[]=new int[n];
	
	for(int i=0;i<n;i++){
	    a[i]=Integer.parseInt(str[i]);
	}

	int q=partition(a,0,n-1);

	for(int i=0;i<n;i++){
	    if(i!=0)
		System.out.print(" ");
	    if(i==q)
		System.out.print("[");
	    System.out.print(a[i]);
	    if(i==q)
		System.out.print("]");
	}
	System.out.println();
    }
    static int partition(int A[], int p, int r){
	int x = A[r];
	int i = p-1;
	for (int j = p;j<r;j++){
	    if (A[j] <= x){
		i = i+1;
		int temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	    }
	}
	int temp=A[i+1];
	A[i+1]=A[r];
	A[r]=temp;
	return i+1;
    }
}



Measured memory_bytes: 55668
import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    @tailrec
    def convert(line:String):String = {
      line match {
        case str if str.matches(".*(the|that|this).*") => str
        case str =>
          convert(str.map {
            case ch if 'b' to 'z' contains ch => (ch - 1).toChar
            case ch if ch == 'a' => 'z'
            case ch => ch
          })
      }
    }
    val sc = new java.util.Scanner(System.in)
    while (sc.hasNextLine) {
      println(convert(sc.nextLine()))
    }
  }
}

Measured memory_bytes: 47684
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> P;

const int INF = 1 << 30;

int main(){
    int T;
    int t[30];
    int N;
    int itv[101], dp[101][31];
    while(true){
        scanf("%d", &T);
        if(T == 0) break;
        for(int i = 0; i < T; i++){
            scanf("%d", t + i);
        }
        scanf("%d", &N);
        fill(itv, itv + 101, INF);
        for(int i = 0; i < N; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            --a;
            itv[a] = min(itv[a], b);
        }
        for(int i = 0; i <= 100; i++){
            fill(dp[i], dp[i] + 30, INF);
        }
        dp[0][0] = 0;
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < T; j++){
                dp[i+1][1] = min(dp[i+1][1], dp[i][j] + 1);
                if(itv[i] >= t[j]){
                    dp[i+1][(j + 1) % T] = min(dp[i+1][(j + 1) % T],
                                               dp[i][j]);
                }
            }
        }
        int ans = INF;
        for(int i = 0; i < T; i++){
            ans = min(ans, dp[100][i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 1196
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

const ll mod = 1000000007LL;

vector< bool > prime_table(int n) {
	vector< bool > prime(n + 1, true);
	if (n >= 0) prime[0] = false;
	if (n >= 1) prime[1] = false;
	for (int i = 2; i * i <= n; i++) {
		if (!prime[i]) continue;
		for (int j = i + i; j <= n; j += i) {
			prime[j] = false;
		}
	}
	return prime;
}

signed main() {
	auto t = prime_table(200000);
	int x; cin >> x;
	for (int i = x;; ++i) {
		if (t[i]) {
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

ll modpow(ll b, ll e, ll p) {
  if(e==0) return 1;
  if(e%2==0) {
    ll t = modpow(b,e/2,p);
    return (t*t)%p;
  }
  return (b*modpow(b,e-1,p))%p;
}

ll modinv(ll n, ll p) {
  return modpow(n,p-2,p);
}

ll modcomb(ll n, ll k, ll p) { // O(k)
  ll ans=1;
  for(ll i=n; i>=n-k+1; i--) {
    ans*=i;
    ans%=p;
  }
  for(ll i=1; i<=k; i++) {
    ans*=modinv(i,p);
    ans%=p;
  }
  return ans;
}

// O(1) nCk calculation
const ll p = 1e9+7;
const int MX = 1000000;
ll modFact[MX+1];
ll modFactInv[MX+1];
void precalc() {
  modFact[0]=1;
  modFactInv[0]=1;
  repeat(i,1,MX+1) {
    modFact[i]=(modFact[i-1]*i)%p;
    modFactInv[i]=modinv(modFact[i],p);
  }
}

ll fastModComb(ll n, ll k, ll p) {
  // call precalc() first.
  ll ret=modFact[n];
  ret=ret*modFactInv[n-k];
  ret%=p;
  ret=ret*modFactInv[k];
  ret%=p;
  return ret;
}

ll nHk(ll n, ll k) {
  return fastModComb(n+k-1,k-1,p);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  cout<<fixed;
  precalc();
  ll n, k;
  cin>>n>>k;
//  nHk(0,1);
//  nHk(-1,0);
  repeat(i,1,k+1) {
//    cout << "nHk("<<k-i<<"," <<i<<")="<<nHk(k-i,i) << endl;
    //cout << "nHk("<<n-k-(i-1)<<","<<i+2<<")="<<nHk(n-k-(i-1),i+1)<<endl;
    if(n-k-(i-1)<0) {
      cout << 0 << endl;
      continue;
    }
    cout << (nHk(k-i,i)*nHk(n-k-(i-1),i+1))%p << endl;
  }
  return 0;
}


Measured memory_bytes: 15872
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
s = s[::-1]
t = 1
for i in range(len(s)):
    num_int += t * int(s[i])
    num_int %= mod
    t *= 10
    t %= mod
    mod_dict[num_int] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

print(ans)

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

ll u[102],d[102];

int main() {
	ll n,no_t,nox,noy;
	no_t=nox=noy=0;
	cin>>n;
	bool ans=true;
	for(int i=0;i<n;i++){
		int net,nex,ney;
		cin>>net>>nex>>ney;
		ll dept=net-no_t,depd=abs(nex-nox)+abs(ney-noy);
		if(dept<depd){
			ans=false;
		}
		if(dept%2!=depd%2){
			ans=false;
		}
	}
	cout << (ans ? "Yes":"No");
}

Measured memory_bytes: 256
var f:array[0..100000]of longint;
    n,a,ans,i:longint;
begin
  readln(n);
  for n:=1 to n do
  begin
    read(a);
    inc(f[a-1]);
    inc(f[a+1]);
    inc(f[a]);
  end;
  for i:=1 to 100000 do
    if f[i]>ans then
      ans:=f[i];
  writeln(ans);
end.

Measured memory_bytes: 512
N,M = map(int,input().split())
ab = []
cd = []

for i in range(N):
    a,b = map(int,input().split())
    ab.append((a,b))

for i in range(M):
    c,d = map(int,input().split())
    cd.append((c,d))

for a,b in ab:
    dec = 1e9
    for j, s in enumerate(cd):
        dist = abs(a-s[0])+abs(b-s[1])
        if dist < dec:
            idx = j
            dec = dist
    print(idx+1)

Measured memory_bytes: 3064
import java.lang.Math;
import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;

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

        int N = sc.nextInt();
        Integer[] A = new Integer[N];

        int numberOfNegatives = 0;
        int minAbs = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
            if (A[i] < 0) { numberOfNegatives++; }
            int abs = Math.abs(A[i]);
            if (abs < minAbs) { minAbs = abs; }
        }

        long answer = 0;
        for (int i = 0; i < N; i++) {
            answer += Math.abs(A[i]);
        }

        // If the number of negatives are even, all negatives could be flipped to positives
        // if odd, one must be retained somewhere in the array
        if (numberOfNegatives % 2 == 1) {
            answer -= (2 * minAbs);
        }

        System.out.println(answer);
    }
}


Measured memory_bytes: 62276
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 1000000000+7;

ll solve(ll x) {
    if (x == 1 || x == 0) {
        return 1;
    } else {
        return solve(x-1)*x % MOD;
    }
}

int main() {
    ll N, M;
    ll ans;
    cin >> N >> M;
    
    if (abs(N-M) >= 2) {
        ans = 0;
    } else if (abs(N-M) == 0){
        ans = solve(N)*solve(M)*2 % MOD;
    } else {
        ans = solve(N)*solve(M) % MOD;
    }

    cout << ans << endl;
}


Measured memory_bytes: 1792