akhauriyash/Code-Regression huggingface dataset:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    W, H, x, y = i2nn()
    m = W * H / 2
    n = 0
    if W == x * 2 and H == y * 2:
        n = 1
    print('%f %d' % (m, n))

main()


Measured memory_bytes: 38256
import scala.io.{StdIn => in}

object Main extends App {
  val Array(a, b, c, d) = in.readLine.split(" ").map(_.toInt)

  val ans = a + b match {
    case ab if ab == c + d => "Balanced"
    case ab if ab >  c + d => "Left"
    case ab if ab  < c + d => "Right"
  }

  println(ans)
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define pb push_back
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int) a.size())
#define REP(i,n) for(int i=0;i<(n);i++)
#define MP make_pair
#define SORT_UNIQUE(v) v.resize(unique(ALL(v))-v.begin())
#define GET_POS(v,a) lower_bound(ALL(v),a)-v.begin();

const int maxn=3e5+5;
const int INF=0x3f3f3f3f;

ll a[maxn];
ll pre[maxn];
set<ll> st;
pll ans[maxn];
int main(){
    int n;
    cin>>n;
    REP(i,n) cin>>a[i];
    REP(i,n) pre[i+1]=pre[i]+a[i];
    REP(i,n) st.insert(pre[i+1]);
    st.insert(0);
    for(int i=1;i<n;i++){
        auto it=st.lower_bound((pre[i]+1)/2);
        ll cur=pre[i]-(*it);
        if(it!=st.begin()){
            it--;
            cur=max(cur,min(pre[i]-(*it),(*it)));
        }
        ans[i]=MP(cur,pre[i]-cur);
    }
    reverse(a,a+n);
    REP(i,n) pre[i+1]=pre[i]+a[i];
    st.clear();
    REP(i,n) st.insert(pre[i+1]);
    st.insert(0);
    ll QAQ=8e17;
    for(int i=1;i<n;i++){
        auto it=st.lower_bound((pre[i]+1)/2);
        ll cur=pre[i]-(*it);
        if(it!=st.begin()){
            it--;
            cur=max(cur,min(pre[i]-(*it),(*it)));
        }
        ll meow=max(pre[i]-cur,ans[n-i].S)-min(ans[n-i].F,cur);
        QAQ=min(QAQ,meow);
    }
    cout<<QAQ<<'\n';
}


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

const int MAXN = 1e5 + 10;
vector<int> Mat[MAXN];
int n, m, ans;
bool se[MAXN];

void dfs(int v) {
	se[v] = 1;
	for (int i = 0; i < Mat[v].size(); i++)
		if (!se[Mat[v][i]])
			dfs(Mat[v][i]);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, z;
		cin >> a >> b >> z;
		Mat[a].push_back(b);
		Mat[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
		if (!se[i])
			dfs(i), ans++;
	cout << ans;
}

Measured memory_bytes: 8960
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main( void )
{
	int e;
	while(cin >> e, e) {
		bool hit = false;
		int answer = 1000001;
		for(int z=100; z > -1 && !hit; --z) {
			int sum_z = z * z * z;
			if(sum_z == e) { answer = min(answer, z); continue; }
			else if(sum_z > e) continue;
			else {
				int y = (int)sqrt((double)(e - sum_z));
				int sum_zy = sum_z + y * y;
				answer = min(answer, (z + y + e - sum_zy));
			}
		}
		cout << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

int main(void){
    // char ;
    ll n,ans=0;
    scanf("%lld",&n);
    // ll [n];
    rep(i,1,n+1){
        if(i%3!=0 && i%5!=0){
            ans+=i;
        }
    }

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


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

int main()
{
	int a = 2000, b = 2000;
	for (int i = 0; i < 3; i++) {
		int tmp;
		cin >> tmp;
		a = min(a, tmp);
	}
	for (int i = 0; i < 2; i++) {
		int tmp;
		cin >> tmp;
		b = min(b, tmp);
	}
	cout << a + b - 50 << endl;
	return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,M,Q;
char s[2005][2005];
int ch[4][2005][2005],sum[2005][2005],fa[2005 * 2005];
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
int id(int x,int y) {
    return (x - 1) * M + y;
}
int getfa(int u) {
    return fa[u] == u ? u : fa[u] = getfa(fa[u]);
}
void dfs(int x,int y) {
    for(int k = 0 ; k < 4 ; ++k) {
	int tx = x + dx[k],ty = y + dy[k];
	if(s[tx][ty] == '1') {
	    if(fa[id(x,y)] != id(tx,ty)) {
		ch[k][tx][ty] = 1;
		fa[id(tx,ty)] = id(x,y);
		dfs(tx,ty);
	    }
	}
    }
}
void Solve() {
    read(N);read(M);read(Q);
    for(int i = 1 ; i <= N ; ++i) {
	scanf("%s",s[i] + 1);
    }
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 1 ; j <= M ; ++j) {
	    if(s[i][j] == '1' && !fa[id(i,j)]) {
		sum[i][j] = 1;
		dfs(i,j);
	    }
	}
    }
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 1 ; j <= M ; ++j) {
	    sum[i][j] += sum[i][j - 1];
	}
    }
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 1 ; j <= M ; ++j) {
	    sum[i][j] += sum[i - 1][j];
	}
    }
    for(int j = 1 ; j <= M ; ++j) {
	for(int i = 1 ; i <= N ; ++i) {
	    ch[0][i][j] += ch[0][i - 1][j];
	    ch[2][i][j] += ch[2][i - 1][j];
	}
    }
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 1 ; j <= M ; ++j) {
	    ch[1][i][j] += ch[1][i][j - 1];
	    ch[3][i][j] += ch[3][i][j - 1];
	}
    }
    int x[2],y[2];
    for(int i = 1 ; i <= Q ; ++i) {
	read(x[0]);read(y[0]);read(x[1]);read(y[1]);
	int ans = 0;
	ans += ch[0][x[1]][y[0]] - ch[0][x[0] - 1][y[0]];
	ans += ch[1][x[0]][y[1]] - ch[1][x[0]][y[0] - 1];
	ans += ch[2][x[1]][y[1]] - ch[2][x[0] - 1][y[1]];
	ans += ch[3][x[1]][y[1]] - ch[3][x[1]][y[0] - 1];
	ans += sum[x[1]][y[1]] - sum[x[0] - 1][y[1]] - sum[x[1]][y[0] - 1] + sum[x[0] - 1][y[0] - 1]; 
	out(ans);enter;
    }
    
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


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

using namespace std;

int binary_serch(vector<int> v, int indx, int left, int right) {
	int s;
	while (left < right) {
		s = (left + right) / 2;
		if (v[s] == indx) return 1;
		else if (indx < v[s]) right = s;
		else left = s+1;
	}
	return 0;
}

int main() {
	int n; cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; i++) cin >> s[i];
	int t, ans = 0, m; cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> t;
		ans += binary_serch(s, t, 0, s.size());
	}
	cout << ans << endl;
}


Measured memory_bytes: 3596
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define YES cout << "YES" << endl
#define NO  cout << "NO"  << endl
#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 100001
using namespace std;
typedef long long ll;

int main(){
  string A, B; cin >> A >> B;
  if(A.length()==B.length()){
    if(A > B){
      cout << "GREATER" << endl;
    }
    else if(A < B){
      cout << "LESS" << endl;
    }
    else{
      cout << "EQUAL" << endl;
    }
  }
  else{
    if(A.length() > B.length()){
      cout << "GREATER" << endl;
    }
    else if(A.length() < B.length()){
      cout << "LESS" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
N = input()

ans = 0
for i in range(1, len(N)):
    if i % 2 != 0:
        ans += 9 * 10 ** (i - 1)

if len(N) % 2 != 0:
    ans += int(N) - 10 ** (len(N) - 1) + 1

print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <iomanip> //setprecision()
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
using ll = long long;
using namespace std;

double Mcos(double k){return cos(k*atan(1.0)*4/180);}

void monmo(){
    
}

int main() {
    ll x,k,d;
    ll ans=0;
    cin>>x>>k>>d;
    x=abs(x);
    ll h=x/d;
    if(h>k){
        ans=x-k*d;
    }
    if(h<=k){
        if(h%2==0){
            //偶数回で最小の正数
            if(k%2==0){
                //k回目で正数に居る
                ans=x%d;
            }else{
                //k回目で負数に居る
                ans=abs((x%d)-d);
            }
        }else{
            //奇数回で最小の正数
            if(k%2==1){
                //k回目で正数に居る
                ans=x%d;
            }else{
                //k回目で負数に居る
                ans=abs((x%d)-d);
            }
        }
    }
    cout<<ans;
}


Measured memory_bytes: 3640
/*Infor {{{
 ******************************************************
 * > File Name: a.cpp
 * > Author: zrz_orz
 * > Mail: 1281941815@qq.com
 * > Created Time: 2018/9/8/周六 19:55:46
 ******************************************************
}}}*/

#include <bits/stdc++.h>

using namespace std;

/*Abbreviation {{{ */
#define FOR(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define ROF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define cini(a) scanf("%d", &(a))
#define cinc(a) scanf("%c", &(a))
#define cinl(a) scanf("%lld", &(a))
#define cins(a) scanf("%s", (a))
#define cind(a) scanf("%lf", &(a))
#define coui(a) printf("%d", (a))
#define couc(a) printf("%c", (a))
#define coul(a) printf("%lld", (a))
#define cous(a) printf("%s", (a))
#define coud(a) printf("%f", (a))
#define SPA printf(" ")
#define LIN printf("\n")
#define ull unsigned long long int
/*}}}*/

/*Constant {{{*/
/*}}}*/

/*Class {{{*/
/*}}}*/

/*Variable {{{*/
/*}}}*/

/*Declare {{{*/
/*}}}*/

/*Main {{{*/
int main() {
  int a, b;
  scanf ("%d%d", &a, &b);
  if (!(a & 1) || !(b & 1)) {
    cout<<"No"<<endl;
  }
  else cout<<"Yes"<<endl;
  return 0;
}
/*}}}*/

/*Define {{{*/
/*}}}*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const long long INF = 1LL << 60;
const double PI = 3.14159265358979323846;
typedef long long ll;

vector<vector<int>> G;
vector<int> indeg;
int dp[100100];

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

  indeg.assign(N, 0);
  G.assign(N, vector<int>());
  for (int i = 0; i < M; i++) {
    int s, t;
    cin >> s >> t;
    s--, t--;
    G[s].push_back(t);
    indeg[t]++;
  }
  queue<int> q;
  for (int i = 0; i < N; i++) {
    if (indeg[i] == 0) q.push(i);
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto nv : G[v]) {
      indeg[nv]--;
      if (indeg[nv] == 0) {
        q.push(nv);
        dp[nv] = max(dp[nv], dp[v] + 1);
      }
    }
  }
  int res = 0;
  for (int i = 0; i < N; i++) res = max(res, dp[i]);
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#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(s) (s).begin(), (s).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()) , v.end());
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define pub push_back
#define sec second
#define fir first

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = (1 << 30);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vi A(n);
	REP(i,n)cin >> A[i];
	bool isNextPlus = true;
	ll sum = 0;
	ll ans = 0;
	ll ans1 = 0;
	ll ans2 = 0;
	//初項を正に
	REP(i,n){
		sum += A[i];
		if(isNextPlus && sum <= 0){
			ans1 += 1-sum;
			sum = 1;
		}
		else if((!isNextPlus) && sum >= 0){
			ans1 += sum + 1;
			sum = -1;
		}
		isNextPlus ^= true; 
	}
	sum = 0;
	
	isNextPlus = false;
	//初項を負に
	REP(i,n){
		sum += A[i];
		if(isNextPlus && sum <= 0){
			ans2 += 1-sum;
			sum = 1;
		}
		else if((!isNextPlus) && sum >= 0){
			ans2 += sum + 1;
			sum = -1;
		}
		isNextPlus ^= true;
	}
	ans = min(ans1,ans2);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define MODB 998244353
#define INF 9223372036854775807
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
signed main()
{
  int x=0,y=0,z=0,w=0,n=0,m=0;
  std::cin >> x>>y;
  string s;
  rep(i,x){
    std::cin >> s;
    std::cout << s << '\n';
    std::cout << s << '\n';
  }  
}


Measured memory_bytes: 256
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    int N;
    cin >> N;
    vint A(N), B(N + 1), C(N);
    rep(i, N) {
        cin >> A[i];
    }
    REP(i, 1, N + 1) {
        cin >> B[i];
    }
    REP(i, 1, N) {
        cin >> C[i];
    }
    int ans = 0;
    ans += B[A[0]];
    REP(i, 1, N) {
        ans += B[A[i]];
        if (A[i] == A[i - 1] + 1)
            ans += C[A[i - 1]];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
from itertools import count

def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = list(A[left:left+n1]+[float("inf")]), list(A[mid:mid+n2]+[float("inf")])
  i = j = 0
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1
  counter += right - left
def mergeSort(A, left, right):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

N = int(input())
A = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)

Measured memory_bytes: 63880
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

print(*ANS)

Measured memory_bytes: 261776
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int n,c[10]={0},m;
	while(1)
	{	
		for(int i=0;i<10;i++)
		{
			c[i]=0;
		}
		cin>>n;
		if(n==0)
		{
			break;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>m;
			c[m]+=1;
		}
		for(int i=0;i<10;i++)
		{
			if(c[i]==0)
			{
				cout<<"_"<<endl;
			}
			else
			{
				for(int j=0;j<c[i];j++)
				{
					cout<<"*";
				}
				cout<<endl;
			}
		}
	}	
	return 0;
}


Measured memory_bytes: 3048
#include<stdio.h>

void print(int* t,int i,int n){
    printf("node %d: key = %d,",i,t[i]);
    if(i!=1){
        printf(" parent key = %d,",t[i/2]);
    }
    if(i*2<=n){
        printf(" left key = %d,",t[i*2]);
    }
    if(i*2+1<=n){
        printf(" right key = %d,",t[i*2+1]);
    }
    printf(" \n");
}

int main(){
    int i,H;
    scanf("%d",&H);
    int tree[H+1];
    for(i = 1 ; i <= H ; i++){
        scanf("%d",&tree[i]);
    }
    for(i = 1 ; i <= H ; i++){
        print(tree,i,H);
    }
    return 0;
}



Measured memory_bytes: 2044
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main()
{
    ll N, K;
    cin >> N >> K;
    vector<P> v(N);
    for(int i = 0; i < N; ++i){
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), [](P a, P b) -> bool {return a.first < b.first;});

    ll cnt = 0;
    int ans = 0;
    for(int i = 0; i < N; ++i){
        if(cnt >= K)
            break;
        cnt += v[i].second;
        ans = v[i].first;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && b == c && a % 2 == 0) {
        cout << -1 << endl;
        return 0;
    }
    int cnt = 0;
    while (true) {
        if (a % 2 || b % 2 || c % 2) {
            cout << cnt << endl;
            return 0;
        }
        cnt++;
        int a2 = a / 2;
        int b2 = b / 2;
        int c2 = c / 2;
        a = b2 + c2;
        b = c2 + a2;
        c = b2 + a2;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int isPrime(int x){
  int i;
  if(x<2) return 0;
  else if(x==2) return 1;
  if(x%2==0) return 0;
  for(i=3;i*i<=x;i+=2){
    if(x%i==0) return 0;
  }
  return 1;
}

int main(){
  int n,x,i;
  int cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    if(isPrime(x)) cnt++;
  }
  printf("%d\n",cnt);

  return 0;
}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
	ll f,s;
}a[222222];
ll c[222222],dp[36];
bool mycmp(node xx,node yy)
{
	return xx.f*(yy.s+1)>yy.f*(xx.s+1); 
}
int main()
{
	ll n,t,cnt1=0,cnt2=0,x,y,pp,ans=0;
	cin>>n>>t;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		if(x==0) cnt1++,c[cnt1]=y+1;
		else cnt2++,a[cnt2]={x,y};
	}
	sort(c+1,c+cnt1+1);
	sort(a+1,a+cnt2+1,mycmp);
	for(int i=1;i<=35;i++)
	dp[i]=t+1;
	dp[0]=0;
	for(int i=1;i<=cnt2;i++)
	{
		for(int j=35;j>0;j--)
		{
			dp[j]=min(dp[j],(dp[j-1]+1)*(a[i].f+1)+a[i].s);
		}
	}
	for(int i=1;i<=cnt1;i++) c[i]+=c[i-1];
	for(int i=0;i<=35;i++)
	{
		if(dp[i]>t) continue;
		pp=0;
		if(cnt1)
		{
			pp=upper_bound(c+1,c+cnt1+1,t-dp[i])-c-1;
		}
		ans=max(ans,pp+i);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 6784
n, m = map(int, input().split())
ary = []
for i in range(m):
    #[0] = 県, [1] = 誕生年
    ary.append([int(x) for x in input().split()])
    ary[i].append(i) #[2] = 復元用の通し番号

#県でソートして、同じなら誕生年順にソート
ary.sort(key=lambda x:(x[0], x[1]))

p = 1
num = 1
for v in ary:
    if v[0] != p:
        p = v[0]
        num = 1
    _id = str(v[0]).zfill(6) + str(num).zfill(6)
    num += 1
    v.append(_id)

ary.sort(key=lambda x:x[2]) #最初の順序に復元

for v in ary:
    print(v[3])

Measured memory_bytes: 32412
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int h, w, n, y, x; string s, t;
    cin >> h >> w >> n >> y >> x >> s >> t;
    int l = 0, r = w, u = 0, d = h;
    y--; x--;
    rep(i, 2*n) {
        int idx = n-1-i/2;
        if (i % 2 == 0) {
            if (t[idx] == 'L') {
                r = min(r+1, w);
            } else if (t[idx] == 'R') {
                l = max(l-1, 0);
            } else if (t[idx] == 'U') {
                d = min(d+1, h);
            } else {
                u = max(u-1, 0);
            }
        } else {
            if (s[idx] == 'L') {
                l++;
            } else if (s[idx] == 'R') {
                r--;
            } else if (s[idx] == 'U') {
                u++;
            } else {
                d--;
            }
        }
        if (l == r || u == d) {
            cout << "NO" << endl;
            return 0;
        }
    }
    if (l <= x && x < r && u <= y && y < d) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 920
use std::io::*;

fn main() {
    let scan = stdin();

    let mut line = String::new();
    scan.read_line(&mut line).unwrap();

    let token: Vec<&str> = line.split_whitespace().collect();

    let x: i64 = token[0].parse().unwrap();
    let t: i64 = token[1].parse().unwrap();

    if t <= x {
        println!("{}", (x - t));
    } else {
        println!("0");
    }
}


Measured memory_bytes: 4352
N = int(input())
A = list(map(int, input().split() ) )

print( ' '.join(map(str, A)) )

for i in range(1, N):
    val = A[i]
    j = i - 1
    while j >= 0 and A[j] > val :
        A[j+1] = A[j]
        j -= 1
    A[j+1] = val
    print( ' '.join(map(str, A)) )


Measured memory_bytes: 5596
#include <bits/stdc++.h> 
#define lb lower_bound 
#define ub upper_bound 
#define sqr(x) (x)*(x) 
#define lowbit(x) (x)&(-x) 
#define mem(a,x) memset(a,x,sizeof(a));
using namespace std; 
typedef long long ll;
int a[200007],b[1000007];
int main(){
	int n;
	scanf("%d",&n);
	mem(b,0)
	int ans=0;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	sort(a,a+n);
	for(int i=0;i<n;i++){
		if(!b[a[i]]){
			for(int j=1;j*a[i]<=1000000;j++){
				//if(j*a[i]>1000000) break;
				b[j*a[i]]=1;
			}
			if(a[i]==a[i+1]){
				i=ub(a,a+n,a[i])-a-1;  ///siyu-1
				//printf("%d\n",i);
				continue;
			}
			ans++;
		}
	}
	//for(int i=0;i<10;i++) printf("%d ",b[i]);
	//printf("\n");
	printf("%d\n",ans);
}
//siyu 
//3 
//2 2 3

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

int main() {
    int N;
    cin >> N;
    vector<long long> A(N + 1), B(N);
    for (int i = 0; i < N + 1; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];

    long long ans = min(A[0], B[0]);
    B[0] -= ans;
    for (int i = 1; i < N; i++) {
        int tmp = min(A[i], B[i - 1]);
        ans += tmp;
        A[i] -= tmp;
        tmp = min(A[i], B[i]);
        ans += tmp;
        B[i] -= tmp;
    }
    ans += min(A[N], B[N - 1]);

    cout << ans << endl;
}

Measured memory_bytes: 1920
N,M=map(int,input().split())
cnt_loved=[0]*M
ans=0

for _ in range(N):
    love_list=list(map(int,input().split()))
    for a in love_list[1:]:
        cnt_loved[a-1]+=1
        
for i in range(M):
    if cnt_loved[i]==N:
        ans+=1
        
print(ans)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <queue>
#include <stack>
#include <utility>
#include <queue>
#define mp make_pair
#define pii pair<int,int> 
#define ff first
#define ss second

using namespace std;

char a[1000];
int b,c;

int main()
{
	while(fgets(a,999,stdin) != NULL)
	{
		c=0;
		while(true)
		{
			if(strstr(a,"this")!=NULL||strstr(a,"the")!=NULL||strstr(a,"that")!=NULL)break;
			for(b=0;a[b]!='\0';b++)
			{
				if(islower(a[b]))
				a[b]++;
				if(a[b]>122)
				a[b]=97;
			}
			c++;
			if(c>27)
			break;
		}
		printf("%s",a);
	}
	return 0;
}

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

#include <math.h>
#define PI 3.14159265358979323846264338327950L
const int mxN = 1e9 + 7;

bool is_sorted(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++)
        if (a[i] > a[i + 1]) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 0; i <= n; i++) cin >> a[i];
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int x = min(b[i], a[i]);
        ans += x;
        b[i] -= x;
        int y = min(b[i], a[i+1]);
        a[i + 1] -= y;
        ans += y;
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 3928
W, H, N = map(int, input().split())
x1, x2, y1, y2 = 0, W, 0, H
for _ in range(N):
    x, y, a = map(int, input().split())
    if a == 1:
        x1 = max(x1, x)
    elif a == 2:
        x2 = min(x2, x)
    elif a == 3:
        y1 = max(y1, y)
    elif a == 4:
        y2 = min(y2, y)

print(max(0, (y2 - y1)) * max(0, (x2 - x1)))


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

using namespace std;

using PII = pair<int,int>;
#define MP make_pair
#define FF first
#define SS second

bool inc(int l, string& s){
  for(int i=l-1;i>=0;--i){
	if(s[i] != 'z'){
	  s[i]++;
	  return true;
	}
	s[i] = 'a';
  }
  return false;
}

int main(){
  int N; cin >> N;
  vector<string> vs(N);
  for(int i=0;i<N;++i)
	cin >> vs[i];

  for(int l=1;l<10;++l){
	set<string> memo;
	for(int i=0;i<N;++i){
	  for(int j=0;j+l<=vs[i].size();++j){
		memo.insert(vs[i].substr(j,l));
	  }
	}

	bool done = false;
	string s(l, 'a');
	do{
	  if(!memo.count(s)){
		cout << s << endl;
		done = true;
		break;
	  }
	}while(inc(l,s));
	if(done) break;
  }
  
  return 0;
}

Measured memory_bytes: 40456
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() {
  int sum = 0 ;
  string in;

  cin >> in;
  for (int i = 0; i < (int)in.length(); i++)
  {
    sum += in[i] - '0';
  }
  // cout << sum << endl;
  // cout << sum%9 << endl;
  if((sum%9) != 0) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

}

Measured memory_bytes: 3716
from itertools import product


def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    s = ["#" * (w + 2)] + ["#" + _s + "#" for _s in s] + ["#" * (w + 2)]
    ans = 0
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for _h, _w in product(range(1, h + 1), range(1, w + 1)):
        if s[_h][_w] == "#":
            continue
        q = list()
        for x, y in d:
            if s[_h + x][_w + y] == ".":
                q.append((_h + x, _w + y, _h, _w))
        if len(q) > 2:
            continue
        c = [[h * w] * (w + 2) for _ in range(h + 2)]
        c[_h][_w] = 0
        while q:
            cx, cy, px, py = q.pop()
            if c[px][py] + 1 >= c[cx][cy]:
                continue
            c[cx][cy] = c[px][py] + 1
            for x, y in d:
                if s[cx + x][cy + y] == ".":
                    q.append((cx + x, cy + y, cx, cy))
        ans = max(
            ans,
            *(c[i][j] * (s[i][j] == ".") for i, j in product(range(1, h + 1), range(1, w + 1))))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ta = (c + b - 1) / b;
    int tb = (a + d - 1) / d;
    
    if(ta <= tb){
        cout << "Yes";
    }else{
        cout << "No";
    }
}

Measured memory_bytes: 3608
<?php

fscanf(STDIN, "%d", $n);
for ($i = 0; $i < $n; $i++) {
    fscanf(STDIN, '%s', $s[]);
}
fscanf(STDIN, "%d", $m);
for ($i = 0; $i < $m; $i++) {
    fscanf(STDIN, '%s', $t[]);
}

$max = 0;

$master = array_merge($s, $t);
$unique = array_unique($master);
$master_array = array_values($unique);

foreach ($master_array as $target) {

    $cnt = 0;
    for ($i = 0; $i < $n; $i++) {
        if ($s[$i] == $target) {
            $cnt++;
        }
    }
    for ($i = 0; $i < $m; $i++) {
        if ($t[$i] == $target) {
            $cnt--;
        }
    }
    if ($max < $cnt) {
        $max = $cnt;
    }
}
echo $max;

Measured memory_bytes: 4604
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int sum,i;
		double m,alpha;
		while(true){
			sum=0;
			alpha=0;
			int n = sc.nextInt();
			if(n==0)break;
			int s[] = new int[n];
			for(i=0;i<n;i++){
				s[i]=sc.nextInt();
				sum+=s[i];
			}
			m = (double)sum/n;
			for(i=0;i<n;i++){
				alpha+=Math.pow(s[i]-m,2);
			}
			alpha/=n;
			alpha=Math.sqrt(alpha);
			System.out.println(alpha);
		}
	}
}



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

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int n;
vector<vector<int>> g;
vector<ll> d, x;

ll dfs(int v, int p) {
    ll res = d[v];
    for(auto u : g[v]) {
        if(u != p) {
            res += dfs(u, v);
        }
    }
    return d[v] = res;
}

void dfs2(int v, int p) {
    if(p != -1) {
        x[v] = x[p] + d[v];
    }
    for(auto u : g[v]) {
        if(u != p) {
            dfs2(u, v);
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    g.resize(n), d.resize(n), x.resize(n, 0);
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for(int i = 0; i < n; i++) {
        cin >> d[i];
    }
    for(int i = 0; i < n; i++) {
        int b;
        cin >> b;
        d[i] -= b;
    }
    dfs(0, -1);
    dfs2(0, -1);
    ll ans = 0, one = 0;
    for(int i = 0; i < n; i++) {
        ans += x[i];
        chmin(one, x[i]);
    }
    ans -= one * n;
    cout << ans << endl;
}


Measured memory_bytes: 15692
a, b, c = map(int, input().split())
if a == b and b == c:
    if a % 2 == 1:
        print(0)
    else:
        print(-1)
else:
    ans = 0
    while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
        A = a
        B = b
        C = c
        a = B // 2 + C // 2
        b = A // 2 + C // 2
        c = A // 2 + B // 2
        ans += 1
    print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<math.h>

std::vector<int>dq[30];
char a[100010];
int main(){
	scanf("%s",a);
	int k,s=strlen(a),to,len,l,r;
	for(k=0;k<s;k++){
		dq[a[k]-'a'+1].push_back(k);
	}
	for(k=1;k<=26;k++){
		if(dq[k].size()<2) continue;
		l=0;
		r=dq[k].size()-1;
		to=dq[k].size();
		len=(dq[k][r]-dq[k][l]+1);
		if(to*2>len){
			printf("%d %d\n",dq[k][l]+1,dq[k][r]+1);
			return 0;
		}
		while(l+1<r){
			if(dq[k][l+1]-dq[k][l]>dq[k][r]-dq[k][r-1]){
				l++;
			}
			else{
				r--;
			}
			to--;
			len=(dq[k][r]-dq[k][l]+1);
			if(to*2>len){
				printf("%d %d\n",dq[k][l]+1,dq[k][r]+1);
				return 0;
			}
		}
	}
	printf("-1 -1");
}

Measured memory_bytes: 1024
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let h: usize = read();
    let w: usize = read();
    let count: usize = (0..h)
        .map(|_| read::<String>().chars().filter(|&c| c == '#').count())
        .sum();

    println!(
        "{}",
        if count == h + w - 1 {
            "Possible"
        } else {
            "Impossible"
        }
    );
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

using namespace std;

int main(){
  int w,h;
  char maze[1000][1000];

  cin>>w>>h;
  while(w!=0 && h!=0){
    //  cout<<w<<"::::::"<<h<<endl;
    //“?—???????'#'??'.'???????????H?????¬
    for(int i=0;i<2*w+1;i++){
      maze[0][i] = '#';
    }
    maze[0][1] = 's';//start

    for(int i=1;i<h*2;i++){
      int c;
      if(i%2 != 0){//?c????????
	maze[i][0] = '#';//???¶????
	for(int j=1;j<w*2;j++){
   if(j %2 ==0){
     cin>>c;
     if(c==0){
       maze[i][j] = '.';
     }else{
	      maze[i][j] = '#';//??‰E????
	    }
	  }else{
     maze[i][j] = '.';
   }
 }
 maze[i][w*2] = '#';
      }else{//‰?????????
       maze[i][0] = '#';
       for(int j=1;j<w*2;j++){
         if(j%2 == 0){
           maze[i][j] = '#';
         }else{
           cin>>c;
           if(c==0){
             maze[i][j] = '.';
           }else{
             maze[i][j] = '#';
           }
         }

       }
       maze[i][w*2] = '#';
     }
   }
   
   for(int i=0;i<2*w+1;i++){
    maze[h*2][i] = '#';
  }
    maze[h*2][w*2-1] = 'g';//goal

    int ans = 0;
    int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    queue<pair<pair<int,int>,int> >  que;
    que.push(make_pair(make_pair(0,1),0));

    while(!que.empty()){

      pair<int,int> now = que.front().first;
      int count = que.front().second;
      que.pop();
      
      if(maze[now.first][now.second] == 'g'){
       ans = count;

       break;
     }else if(maze[now.first][now.second] == '#'){
       continue;
     }
     maze[now.first][now.second] ='#';

     for(int i=0;i<4;i++){
       int ny = now.first + next[i][0];
       int nx = now.second + next[i][1];
       if(ny>=0 && nx>=0 && ny<=h*2 && nx<=w*2 && maze[ny][nx] != '#'){
         que.push(make_pair(make_pair(ny,nx),count+1));
       }
     }

   }

   cout<<ans/2<<endl;
   cin>>w>>h;
 }

 return 0;
}

Measured memory_bytes: 1280
/*
 *  AUTHOR : MANAV PATEl
*/
#include<bits/stdc++.h>
#include<functional>
//#include<boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

namespace fastio {

	template <class T> istream &operator>>(istream &os, vector<T> & vec) {
		for (auto &u : vec)os >> u;
		return os;
	}
	template <class T> ostream &operator<<(ostream &os, const vector<T> & vec) {
		for (auto &u : vec)os << u << " ";
		return os;
	}
	template<class T1, class T2> inline istream& operator>>(istream& os, pair<T1, T2>& p) {
		return os >> p.first >> p.second;
	}
	template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
		return os << p.first << " " << p.second;
	}
	template <class T> ostream &operator<<(ostream &os, set<T> & con) {
		for (auto &u : con) os << u << " ";
		return os;
	}
	void re() {}
	template <typename T, typename... args> void re(T& x, args&... tail) {
		cin >> x;
		re(tail...);
	}
	void pr() {}
	template <typename T> void pr(const T& x) {
		cout << x;
	}
	template <typename T, typename... args> void pr(const T& x, const args&... tail) {
		cout << x << " ";
		pr(tail...);
	}
	template <typename... args> void prln(const args&... tail) {
		pr(tail...);
		cout << "\n";
	}
}
using namespace fastio;

typedef long long int ll;
typedef long double ld;

const ll mod = 1e9+7;
const ll mod1 = 998244353;

#define fill(a)  memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back

int main()
{
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	cin.tie(0);
	int n;
	re(n);
	int arr[n],  cnt  =0;
	for(int i = 0; i < n; i++) re(arr[i]);
	for(int i = 1; i +1 < n; i++)
	{
		if(arr[i-1] > arr[i] && arr[i] > arr[i+1])
		{
			cnt++;
		}
		if(arr[i-1] < arr[i] && arr[i] < arr[i+1])
		{
			cnt++;
		}
	}
	cout<<cnt<<"\n";
}


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

int main() {
    ll n;
    while(cin>>n){
        if(n==0)break;
        vector<ll> a(n);
        rep(i,n)cin>>a[i];
        sort(a.begin(),a.end());
        ll min=1e9;
        rep(i,n-1){
            if(min>a[i+1]-a[i])min=a[i+1]-a[i];
        }
        cout<<min<<endl;
    }
}



Measured memory_bytes: 3156
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        if (n >= 10) {
            System.out.println(r);

        } else {
            System.out.println(r+100*(10-n));
        }

    }
}


Measured memory_bytes: 21588
import itertools

n = int(input())
l = list(map(int, input().split()))
cnt = 0
for a, b, c in itertools.combinations(l, 3) :
    if max([a, b, c]) < (sum([a, b, c]) - max([a, b, c])) :
        if len([a, b, c]) == len(set([a, b, c])) :
            cnt += 1
print(cnt)

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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int n,a[100000],sum,ans,tmp;

main() {
    cin >> n;
    rep(i,n) cin >> a[i];
    rep(i,n) {
        sum+=a[i];
        if (i%2 && sum>=0) ans += sum+1,sum=-1;
        if (!(i%2) && sum<=0) ans += sum*-1+1,sum=1;
    }sum=0;
    rep(i,n) {
        sum+=a[i];
        if (i%2 && sum<=0) tmp += sum*-1+1,sum=1;
        if (!(i%2) && sum>=0) tmp += sum+1,sum=-1;
    }
    ans = min(ans,tmp);
    ct(ans)
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<queue>
#include<string>
#include<sstream>
#include<iostream>
#include<sstream>
#include<stack>
#include<map>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define maxn 210
struct node
{
	int s, e, s1,e1;
}b[110000];
int n, cnt;
char a[110000];

int main() {
	scanf("%s", a);
	int n = strlen(a);
	int m = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == 'R')
		{
			b[cnt].s1++;
			if (a[i + 1] == 'L')
			{
				b[cnt].s = i;
			}
		}
		else
		{
			b[cnt].e1++;
			if (a[i + 1] == 'R'||i==n-1)
			{
				b[cnt].e = i;
				cnt++;
			}
		}
	}
	cnt--;
	for (int i = 0; i <= cnt; i++)
	{
		int sum = b[i].s1 + b[i].e1;
		int y = (b[i].s1 + 1) % 2;
		int z = (b[i].e1 + 1) % 2;
		if (y == z)
		{
			y = 0;
			z = 0;
		}
		int sum1 = sum / 2;
		for (int j = 0; j < sum; j++)
		{
			if (j == b[i].s1-1 )
			{
				printf("%d", sum1 + z);
			}
			else if (j == b[i].s1)
			{
				printf("%d", sum1 + y);
			}
			else
			{
				printf("0");
			}
			if (j != sum || i != cnt)
			{
				printf(" ");
			}
		}
	}
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for(int i=a;i<b;i++)
#define repds(i,a,b) for(int i=a+1;i<=b;i++)
#define rep(i,N) repd(i,0,N)
#define reps(i,N) repds(i,0,N)
#define debug(x) cout<<#x<<"="<<x<<endl
#define debugarr(arr,N,M){rep(i,N+1){rep(j,M+1){if(arr[i][j]==INF)printf(" INF");\
	else printf(" %3d",arr[i][j]);} cout<<endl;}}
#define pb push_back
#define pob pop_back
#define cint(a) int a;cin>>a
#define cint2(a,b) int a,b;cin>>a>>b
#define cint3(a,b,c) int a,b,c;cin>>a>>b>>c
typedef long long ll;
typedef pair<int,int> P;
const int INF=100000000;
const int dx[4]={ 0, 1, 0,-1};
const int dy[4]={ 1, 0,-1, 0};
//--------------------------------------//
int n;

int main(){
	cin>>n;
	if(n<105) cout<<"0"<<endl;
	else if(n<135) cout<<"1"<<endl;
	else if(n<165) cout<<"2"<<endl;
	else if(n<189) cout<<"3"<<endl;
	else if(n<195) cout<<"4"<<endl;
	else cout<<"5"<<endl;
	return 0;
}


Measured memory_bytes: 256
n = gets.to_i
l = gets.chomp.split(" ").map(&:to_i)
cnt = 0
l.combination(3).each do |s|
  if s[0] != s[1] && s[1] != s[2] && s[2] != s[0]
    cnt += 1 if s[0]+s[1] > s[2] && s[1]+s[2] > s[0] && s[2]+s[0] > s[1]
  end
end
puts cnt

Measured memory_bytes: 14360
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int graph[128][128];
	int num;
	
	while(cin >> num)
	{
		if(!num) break;
		int count = 0;
		int all = 0, las[128];
		for(int i = 0; i < 128; i++)
			las[i] = 0;

		for(int i = 0; i < num; i++)
		{
			for(int j = 0; j < num; j++)
			{
				cin >> graph[i][j];
				count += graph[i][j];
				las[j]  += graph[i][j];
				all += graph[i][j];
				if(j == num - 1) 
				{
					graph[i][j+1] = count;
					count = 0;
				}
				if(i == num - 1)
				{
					graph[i+1][j] = las[j];
				}
				if(i == num - 1 && j == num - 1)
				{
					graph[i+1][j+1] = all;
				}
			}
		}

		for(int i = 0; i < num + 1; i++)
		{
			for(int j = 0; j < num + 1; j++)
			{
				printf("%5d", graph[i][j]);
			}
			puts("");
		}

	}
}

Measured memory_bytes: 1172
M=998244353;N=gets.to_i;v=$<.map{|e|Complex(*e.split.map(&:to_i))};h={};r=2**N%M-N-1;N.times{|i|(i+1...N).map{|j|h[x=[i,j]]&&next;(j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-12&&x<<k};x.size.times{|a|(a+1...x.size).map{|b|r=(r-2**(b+~a))%M;h[[x[a],x[b]]]=1}}}};p r%M

Measured memory_bytes: 5116
def find(x):
    global s
    if s[x] == x:
        return x
    s[x] = find(s[x])
    return s[x]
 
n, q = map(int, input().split())
 
s =[i for i in range(n)]
 
for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if find(x) == find(y): print(1)
        else: print(0)
    else:
        s[find(y)] = find(x)


Measured memory_bytes: 5980
n=int(input());p=print;b=1<<n.bit_length()-1
if n==b:p("No");exit()
p("Yes");p(n+1,n+2)
for i in range(3,n+1,2):p(1,i);p(1,i-1);p(i,n+i-1);p(i-1,n+i)
if~n&1:p(b,n);p(n^1^b,n+n)

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

int main(){
  int a,m[101],cou,min,minhako;
  cin >>a;
  for(int i;i<a;i++)cin>>m[i];
  cou=0;
  for(int i=0;i<a-1;i++){
    min=101;
    for(int j=i;j<a;j++){
      if(m[j]<min){
	min=m[j];
	minhako=j;
      }
    }
    swap(m[i],m[minhako]);
    if(i!=minhako)cou++;
  }
  for(int i=0;i<a;i++){
    cout<<m[i];
    if(i<a-1)cout<<" ";
  }
  cout<<endl;
  cout<< cou<<endl;
  return 0;
}

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

// DAME: 
// シミュレーション
int main() {
    int n;
    cin >> n;
    vector<int> c(n-1);
    vector<int> s(n-1);
    vector<int> f(n-1);
    int max_s = 0;
    for(int i=0; i<n-1; i++){
        cin >> c[i] >> s[i] >> f[i];
    }
    for(int i=0; i<n; i++){
        int t=0;
        for(int j=i; j<n-1; j++){
            if(t<s[j]){
                t = s[j];
            }else if(t%f[j]==0){
                t = t;
            }else{
                t = t + f[j] - t%f[j];
            }
            t += c[j];
        }
        cout << t << endl;
    }

    return 0;
}

Measured memory_bytes: 256