akhauriyash/Code-Regression huggingface dataset:
#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()
#define pb push_back
typedef long long ll;
const int INF = 1000000000;
const long INF64 = 1000000000000000ll;
const int MOD = 1000000007;
int main(){
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	rep(i,n)std::cin >> a[i];
	bool han=1;
	int b=n+1;
	sort(all(a),greater<int>());
	rep(i,n){
		if(i%2==0)b-=2;
		if(b!=a[i])han=0;
		
	}
	if(!han)std::cout << 0 << std::endl;
	
	else{
		int ans=1;
		rep(i,n/2){
			ans*=2;
			ans%=MOD;
		
		}
			std::cout << ans << std::endl;
	} //std::cout << pow(2,n/2) << std::endl;
	
}



Measured memory_bytes: 640
#!/usr/bin/python3
# ABC057_A
""" Remaining Time """



def answer():
    """ A時にB時間足して、24で割った余りが答え """
    A, B = map(int, input().split())
    return (A + B) % 24


def main():
    """ 答えを出力する関数 """
    print(answer())


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
using namespace std;
int main(){
    ll a,b,m;
    cin>>a>>b>>m;
    V vec1(a);
    V vec2(b);
    rep(i,a)cin>>vec1[i];
    rep(i,b)cin>>vec2[i];
    ll sum=1e18;
    rep(i,m){
        ll x,y,c;
        cin>>x>>y>>c;
        x--;y--;
        chmin(sum,vec1[x]+vec2[y]-c);
    }
    sort(all(vec1));
    sort(all(vec2));
    chmin(sum,vec1[0]+vec2[0]);
    cout<<sum<<endl;
}

Measured memory_bytes: 1792
from math import log2, ceil
n, k = map(int, input().split())
ans = n-k if k<n else 0
if n<=k:
    for i in range(1, n+1):
        ans += 0.5**ceil(log2(k/i))
else:
    for i in range(1, k+1):
        ans += 0.5**ceil(log2(k/i))
print(ans/n)

Measured memory_bytes: 3060
#include <iostream>
#include <map>  // pairはutilityヘッダにあり、mapヘッダから読み込まれる
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> p;
/*
bool operator< (const p p1, const p p2){
    return p1.first < p2.first;
};
*/


int main(){
    int N;
    int H, W;
    priority_queue<p> que;
    map<int, int> m;
    cin >> H >> W >> N;
    for(int i = 0; i < N; i++){
        int X, Y;
        cin >> X >> Y;
        que.push(make_pair(-X, Y));
    }
    int cur_diff = 0;
    
    int len = que.size();
    for(int i = 0; i < len; i++){
        //cout << -que.top().first << ' ' << que.top().second << endl;
        if(que.top().first + que.top().second == cur_diff) cur_diff--;
        else if(que.top().first + que.top().second < cur_diff){
            //cout << cur_diff << endl;
            cout << -que.top().first - 1 << endl;
            return 0;
        }
        que.pop();
    }
    cout << H << endl;
}

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

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

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)

i32 c[6][6];

int main() {
  i32 h, k, w;
  cin >> h >> w >> k;

  rep(i, h) {
    string row;
    cin >> row;
    rep(j, w) {
      if (row[j] == '.') {
        c[i][j] = 0;
      } else if (row[j] == '#') {
        c[i][j] = 1;
      }
    }
  }
  // rep(i, h) {
  //   rep(j, w) { cout << c[i][j]; }
  //   cout << endl;
  // }

  u32 ans = 0;
  u32 b = 0;

  rep(i, 1 << (h)) {
    rep(j, 1 << (w)) {
      b = 0;
      rep(hi, h) {
        rep(wi, w) {
          if ((i & (1 << hi)) == 0 && (j & (1 << wi)) == 0 && c[hi][wi] == 1) {
            b++;
          }
        }
      }
      if (b == k)
        ans++;
    }
  }

  cout << ans;

  return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
map<int,int>mp;
int main(){
  int n,m,v;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&v);
    mp[v]++;
  }
  scanf("%d",&m);
  for(int i=0;i<m;i++){
    scanf("%d",&v);
    if(mp.count(v)==0 || mp[v]==0){
      puts("NO");
      return 0;
    }
    mp[v]--;
  }
  puts("YES");
  return 0;
}


Measured memory_bytes: 9600
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int n,m;
vector<vector<pi> >e;
bool use[11][11];
int mxl; vi ans,tmp;

void dfs(int c,int s)
{
	bool f=1;
	tmp.pb(c);
	fr(i,e[c])
	{
		int h=c,t=i->first;
		if(h>t)swap(h,t);
		if(use[h][t])continue;
		use[h][t]=1;
		dfs(i->first,s+i->second);
		f=use[h][t]=0;
	}
	if(f)
	{
		if(mxl<s||mxl==s&&ans>tmp)
		mxl=s,ans=tmp;
	}
	tmp.pop_back();
}
int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		e.clear(); e.resize(n+1);
		ans.clear(); ans.pb(inf);
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c);
			e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
		}
		mxl=0;
		for(int i=1;i<=n;i++)
		{
			rep(j,11)rep(k,11)use[i][j]=0;
			tmp.clear(); dfs(i,0);
		}
		printf("%d\n",mxl);
		int na=ans.size();
		rep(i,na)printf("%d%c",ans[i],i==na-1?'\n':' ');
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (long long  i=a;i<n;i++)
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;

void solve() {
	ll a;
	cin >> a;
	cout << a + a*a + a*a*a;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T_ = 1;
	//cin >> T_;
	for (int i = 0; i < T_; i++)solve();
	return 0;
}







Measured memory_bytes: 3644
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  ll N;
  cin >> N;
  if (N == 0) {
    print(0);
    return 0;
  }
  string ans = "";
  ll now = 1;
  for (int i = 0; i < 32; ++i) {
    if (abs(N) % abs(now * 2) != 0) {
      ans += "1";
      N -= now;
    } else {
      ans += "0";
    }
    now *= -2;
  }
  reverse(ALL(ans));
  int st = 0;
  FOR(i, 32) {
    if (ans[i] == '0') {
      st = i + 1;
    } else {
      break;
    }
  }
  ans = ans.substr(st);
  print(ans);
  return 0;
}

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

using namespace std;

int n;
int a[300001];
int b[100001];

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    int s = 0; 
    for(int i = 1;i <= n;i++)
        s = s ^ a[i];
    if(s)
        printf("No\n");
    else
        printf("Yes\n");
    return 0;
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        long a = s.nextLong(),b=s.nextLong(),x=s.nextLong();
        long sum = (b/x)-(a/x);
        if(a%x==0)sum++;
        System.out.println(sum);

    }


}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {return Integer.parseInt(next());}

    public long nextLong() throws IOException {return Long.parseLong(next());}

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25364
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
int main(void) {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i, n) {
    cin >> p[i];
    p[i]--;
  }
  int cnt = 0;
  rep(i, n) {
    if(p[i] == i)
      continue;
    else
      cnt++;
  }
  if(cnt == 2 || cnt == 0)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
use std::str::FromStr;

fn read_vec<T:FromStr>() -> Vec<T>{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|x| x.parse().ok().unwrap()).collect()
}

fn main(){
    let d: Vec<i32> = read_vec();
    
    if d[0] <= d[1] * d[2]{
        println!("Yes");
    }else{
        println!("No")
    }
}

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

int a,b;

int main() {
    cin >> a >> b;
    int _max=a+b;
    _max = _max > (2*a-1) ? _max : (2*a-1);
    _max = _max > (2*b-1) ? _max : (2*b-1);
    cout << _max << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#define rep(i,n) for (int i = 0; i < (n); ++i)


using namespace std;

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

int main () {
    int N, K;
    cin >> N >> K;
    set<int> c;
    rep(i,K) {
        int d, a;
        cin >> d;
        rep(j,d){
            cin >> a;
            c.insert(a);
        }
    }
    cout << N - c.size() << endl; 
    return 0;
}

Measured memory_bytes: 3224
n, x, m = map(int, input().split())
ans = [x]
for _ in range(m):
    ans.append(pow(ans[-1], 2, m))
loop = [ans[-1]]
check = ans[-1]
for _ in range(m):
    next = pow(loop[-1], 2, m)
    if next == check:
        break
    else:
        loop.append(next)
if n <= m+1:
    A = sum(ans[:n])
else:
    times = (n - m) // len(loop)
    amari = (n - m) % len(loop)
    A = sum(ans[:-1]) + sum(loop) * times + sum(loop[:amari])
print(A)

Measured memory_bytes: 73296
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int memo[2010][2010];
int child[2010][2010];
char str[3000];

int calc(int left, int right) {
  if (memo[left][right] != -1) { return memo[left][right]; }
  if (left >= right) { return 0; }
  if (left == right - 1) { return 1; }
  int ret = 0;
  if (str[left] == str[right - 1]) {
    child[left][right] = 0;
    ret = calc(left + 1, right - 1) + 2;
  } else {
    int lret = calc(left + 1, right);
    int rret = calc(left, right - 1);
    if (lret >= rret) {
      child[left][right] = 1;
    } else {
      child[left][right] = 2;
    }
    ret = max(lret, rret);
  }
  return memo[left][right] = ret;
}

string MakeString(int left, int right) {
  if (left >= right) { return ""; }
  string ret = "";
  if (left == right - 1) { ret = str[left]; }
  else if (child[left][right] == 0) {
    ret = str[left] + MakeString(left + 1, right - 1) + str[right - 1];
  } else if (child[left][right] == 1) {
    ret = MakeString(left + 1, right);
  } else {
    ret = MakeString(left, right - 1);
  }
  return ret;
}

int main() {
  while (scanf("%s", str) > 0) {
    MEMSET(memo, -1);
    MEMSET(child, -1);
    calc(0, strlen(str));
    cout << MakeString(0, strlen(str)) << endl;
  }
}

Measured memory_bytes: 0
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

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

const ll MOD = INF + 7;



int main(){
    int n, k;
    string s;
    cin >> n >> s >> k;
    k--;
    char key = s[k];
    for(char c : s){
        if(key != c)cout << '*';
        else cout << c;
    }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N, M;
	in >> N >> M;
	std::vector<LL>X(M);
	rep(i, M) in >> X[i];

	std::sort(X.begin(), X.end());
	LL ans = X[M - 1] - X[0];
	std::vector<LL>length;
	rep(i, M - 1) length.push_back(X[i + 1] - X[i]);
	std::sort(length.rbegin(), length.rend());
	rep(i, std::min<LL>(N - 1, length.size())) ans -= length[i];

	out << ans << std::endl;
}


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

int main(){
	int H, W, h, w;
	cin >> H >> W >> h >> w;
	
	int S = H * W;
	int A = h * W + w * H;
	int B = h * w;
	int ans = S - A + B;
	cout << ans << endl;
}
	

Measured memory_bytes: 256
S = input()
N = len(S)
count_L = [0]*N
count_R = [0]*N
for i in range(N):
    if S[i]=='L':
        count_L[i] = count_L[i-1]+1
for i in range(N)[::-1]:
    if S[i]=='R':
        count_R[i] = count_R[i+1]+1
ans = [0]*N
for i in range(N):
    res = i
    if S[i] == 'L':
        res -= count_L[i]
        if count_L[i]%2==1:
            res+=1
    else:
        res+=count_R[i]
        if count_R[i]%2== 1:
            res-=1
    ans[res] += 1
ans = map(str, ans)
print(' '.join(ans))

Measured memory_bytes: 52976
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))


//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    int N;
    int x[100], y[100], h[100];
    int base_idx;
    cin >> N;

    REP(i, N) {
        cin >> x[i] >> y[i] >> h[i];
        if(h[i] > 0) base_idx = i;
    }

    for(int i = 0; i <= 100; i++) {
        for(int j = 0; j <= 100; j++) {
            int H = abs(x[base_idx] - i) + abs(y[base_idx] - j) + h[base_idx];
            if(H < 1) continue;
            bool is_success = true;
            for(int n = 0; n < N; n++) {
                if(h[n] != max(H - abs(x[n] - i) - abs(y[n] - j), 0)) {
                    is_success = false;
                    break;
                }
            }
            if(is_success) {
                cout << i << ' ' << j << ' ' << H << endl;
                break;
            }
        }
    }
}


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

const int N = 2e5 + 10;
const int L = 18;
const int inf = 0x3f3f3f3f;

int n, a[N], b[2][N];
int dp[2][N][L], key[2][N][L];
int len[N];

void init(int op){
    for(int i=1; i<=n; i++){
        dp[op][i][0] = b[op][i];
        key[op][i][0] = i;
    }

    for(int j=1; j<L; j++){
        for(int i=1; i<=n; i++){
            int k = i + (1 << (j - 1));
            if(k > n)   k = n;
            if(dp[op][i][j-1] < dp[op][k][j-1]){
                key[op][i][j] = key[op][i][j-1];
            } else {
                key[op][i][j] = key[op][k][j-1];
            }
            dp[op][i][j] = b[op][key[op][i][j]];
        }
    }
}

int query(int op, int l, int r){
    int g = len[r - l + 1];
    int k = r - (1 << g) + 1;
    if(dp[op][l][g] < dp[op][k][g]){
        return key[op][l][g];
    } else {
        return key[op][k][g];
    }
}

int getfst(int l, int r){
    return query(1 - (l & 1), l, r);
}

int getsec(int l, int r){
    return query(l & 1, l, r);
}

struct Node{
    int l, r, v, w;
    Node(){}
    Node(int l, int r):l(l),r(r){
        v = getfst(l, r);
    }
    bool operator < (const Node &A)const{
        return a[v] > a[A.v];
    }
};

priority_queue<Node> Q;
Node nd;

void add(int l, int r){
    if(l < r){
        Q.push(Node(l, r));
    }
}

int main(){
    memset(len, -1, sizeof(len));
    for(int i=0; (1<<i) < N; i++){
        len[1<<i] = i;
    }
    for(int i=1; i<N; i++){
        if(len[i] == -1){
            len[i] = len[i-1];
        }
    }
    int p, q;
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++){
            scanf("%d", a+i);
            b[1 - (i & 1)][i] = a[i];
            b[i & 1][i] = inf;
        }

        init(0);
        init(1);

        Q.push(Node(1, n));

        bool st = 0;
        while(!Q.empty()){
            if(st)  putchar(' ');
            st = 1;
            nd = Q.top(); Q.pop();

            if(nd.r == nd.l + 1){
                printf("%d %d", a[nd.l], a[nd.r]);
            } else {
                p = getfst(nd.l, nd.r);
                q = getsec(p, nd.r);
                printf("%d %d", a[p], a[q]);
                add(nd.l, p-1);
                add(p+1, q-1);
                add(q+1, nd.r);
            }
        }

        puts("");
    }
    return 0;
}


Measured memory_bytes: 61684
#include <cstdio>
#include <vector>
#include <map>

int n, m;
std::vector<std::vector<int> > G;
int dp[100000];

int dfs(int p, int x){
  long long int r = 1;
  for(int y: G[x]){
    if(y == p) continue;
    r = r * (1 + dfs(x, y)) % m;
  }
  return dp[x] = r;
}

void dfs2(int p, int x){
  int ans = (long long int) dp[x] * (p == -1 ? 1 : (dp[p]+1)) % m;
  std::vector<int> prod(G[x].size()+1);
  prod[0] = 1;
  int i = 1;
  for(int y: G[x]){
    prod[i] = (long long) prod[i-1] * (dp[y] + 1) % m;
    i++;
  }
  std::vector<int> rprod(G[x].size()+1);
  rprod[G[x].size()] = 1;
  i = G[x].size()-1;
  for(auto j = G[x].crbegin(); j != G[x].crend(); ++j){
    rprod[i] = (long long) rprod[i+1] * (dp[*j] + 1) % m;
    i--;
  }
  i = 1;
  for(int y: G[x]){
    if(y != p){
      dp[x] = (long long) prod[i-1] * rprod[i] % m;
      dfs2(x, y);
    }
    i++;
  }
  dp[x] = ans;
}

int main(){
  scanf("%d%d", &n, &m);
  G.resize(n);
  for(int i = 0; i < n - 1; i++){
    int a, b;
    scanf("%d%d", &a, &b);
    G[b-1].push_back(a-1);
    G[a-1].push_back(b-1);
  }

  dfs(-1, 0);
  dfs2(-1, 0);

  for(int i = 0; i < n; i++) printf("%d\n", dp[i]);

  return 0;
}


Measured memory_bytes: 18304
n, m = [int(elem) for elem in input().split()]

divisors = []
for i in range(1, int(m**0.5)+1):
  if m % i == 0:
    divisors.append(i)
    if i != m // i:
      divisors.append(m//i)

divisors = sorted(divisors)
for i in range(len(divisors), 0, -1):
  if m/n >= divisors[i-1]:
    print(divisors[i-1])
    break

Measured memory_bytes: 3064
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

const ll mod = 1000000007;

int main() {
  ll l;
  cin >> l;

  l--;

  ll clogl = 0;
  ll lcpy = l;
  do {
    lcpy /= 2;
    clogl++;
  } while (lcpy > 0);

  ll n = clogl;
  vT es;

  if (l == (1 << n) - 1) {
    rep(i, n) {
      es.push_back(T(i + 1, i + 2, 0));
      es.push_back(T(i + 1, i + 2, 1 << i));
    }
    assert(n + 1 <= 20);
    assert(es.size() <= 60);
    cout << n + 1 << " " << es.size() << endl;
    rep(i, (ll)es.size()) {
      ll s, t, wt;
      tie(s, t, wt) = es[i];
      cout << s << " " << t << " " << wt << endl;
    }
    return 0;
  }

  rep(i, n - 1) {
    es.push_back(T(i + 1, i + 2, 0));
    es.push_back(T(i + 1, i + 2, 1 << i));
  }

  ll th = (1 << (n - 1)) - 1;
  ll d = l - th;
  ll c = 0;
  ll sum = 0;
  do {
    ll t = d % 2;
    d /= 2;
    if (t == 1) {
      es.push_back(T(c + 1, n, th + 1 + sum));
      sum += (1 << c);
    }
    c++;
  } while (d > 0);

  assert(n <= 20);
  assert(es.size() <= 60);
  cout << n << " " << es.size() << endl;
  rep(i, (ll)es.size()) {
    ll s, t, wt;
    tie(s, t, wt) = es[i];
    cout << s << " " << t << " " << wt << endl;
  }

  return 0;
}


Measured memory_bytes: 256
M=10**9+7;N,K=map(int,input().split())
def c(n,k):
 if k>n:return 0
 m=d=1
 for i in range(k):m*=n-i;d*=i+1
 return m%M*pow(d%M,M-2,M)%M
for i in range(K):print(c(K-1,i)*c(N-K+1,i+1)%M)

Measured memory_bytes: 3316
a,b,c=map(int,input().split('/'))
count=0
if a<2019:
  pass
elif a>2019:
  count+=1
elif b>4:
  count+=1
elif b<4:
  pass
elif c>30:
  count+=1
else:
  pass
if count==0:
  print('Heisei')
else:
  print('TBD')

Measured memory_bytes: 3060
#s = input()
#n = int(input())
#s,t = input().split()
#n,m = map(int,input().split())
#a = list(map(int,input().split()))
#w = [int(input()) for _ in range(N)]


n,k=map(int,input().split())
p=list(map(int,input().split()))

p.sort()

ans = 0
for i in range(k):
    ans += p[i]

print(ans)


Measured memory_bytes: 9252
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;

struct Unionfind {
  vector<int> size;
  vector<int> par;

  Unionfind( int n ) :  size(n, 1), par(n) {
    iota( par.begin() , par.end() , 0 );
  }

  int find( int x ) {
    if ( par[x] == x ) return x;
    return par[x] = find( par[x] );
  }

  bool unite( int x , int y ) {
    x = find(x);
    y = find(y);
    if ( x == y ) return false;

    if ( size[y] < size[x] ) swap( x , y );
    par[x] = y;
    size[y] += size[x];

    return true;
  }

  bool same( int x , int y ) {
    return find(x) == find(y);
  }
};
int main(void)
{
  for(;;){
    int n,m;
    cin >> n >> m;
    if(!n&&!m) return 0;
    Unionfind t(n+1);
    vector<tuple<int,int,int> > e(m);
    REP(i,m){
      int a,b,c;
      cin >> a >> b >> c;
      e[i]=make_tuple(c,a,b);
    }
    SORT(e);
    int tmp=0,answer;
    REP(i,m){
      int a,b,c;
      tie(c,a,b)=e[i];
      if(t.unite(a,b)){
	++tmp;
	if(tmp*2==n) answer=c;
      }
    }
    cout << answer << endl;
  }
}

Measured memory_bytes: 3208
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};
int main(void){
  int N, L;
  cin >> N >> L;
  vector <string> S(N);
  rep(i,N) cin >> S[i];

  sort(all(S));
  rep(i,N){
    cout << S[i];
  }
  cout << endl;
}


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

const int N = 2e5+15;
const int M = 26;
int Next[N][M];
int dp[N],go[N],ggo[N];

void solve(){
   string s;
   cin>>s;
   int n = s.size();
   for(int j = 0;j<M;++j) {
      Next[n+1][j] = n+1;
   }
   for(int i=n;i>=0;--i){
      for(int j = 0;j<M;++j){
         Next[i][j] = Next[i+1][j];
      }
      if(i+1<=n){
         int g = s[i] - 'a';
         Next[i][g] = i+1; 
      }
   }
   for(int i=n;i>=0;--i) {
      dp[i] = 1e9;
      for(int j = 0;j<M;++j){
         int cur = Next[i][j];
         if(cur>n+1){
            dp[i] = 1;
            go[i] = j;
            ggo[i] = cur;
         } else {
            if(dp[i]> dp[cur]+1){
               dp[i] = dp[cur]+1;
               go[i] = j;
               ggo[i] = cur;
            }
         }
      }
   }
   int cur = 0;
   while(cur<=n) {
      putchar(char('a'+go[cur]));
      cur = ggo[cur];
   }
   putchar('\n');
}


int main() {
   //freopen("input.txt","r",stdin);
   solve();
}

Measured memory_bytes: 23172
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
#define pii pair<int,int>
#pragma GCC optimize("Ofast")
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
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(a>b){a = b; return 1;} return 0; };
inline void IN(void){return;}
template <typename First, typename... Rest> void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
inline void OUT(void){cout << "\n";return;}
template <typename First, typename... Rest> void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}
const double EPS = 1e-9;
const int mod = 1e9 + 7;
const int INF = 1e9;
const long long LLINF = 1e18;
long long lcm(ll a, ll b){return a * b / __gcd(a,b);}
struct IoSetup { IoSetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
} } iosetup;
template< int mod > struct ModInt {
    int x; ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}
    ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }return ModInt(u);}
    ModInt pow(int64_t n) const {ModInt ret(1), mul(x); while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); }
    static int get_mod() { return mod; }
}; using modint = ModInt< mod >;

int main(){
    iosetup;
    int N, K; IN(N, K);
    vector<int> H(N);
    rep(i, 0, N) cin >> H[i];
    sort(ALL(H), greater<int>());
    ll sum = 0;
    rep(i, 0, N){
        if(i < K) continue;
        sum += H[i];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		scan.useDelimiter("[^-0-9.]+");
		
		while(scan.hasNext()){
			 int[] Asan = san(scan);
			 int[] Bsan = san(scan);
			 
			 int hits = 0;
			 int blows = 0;
			 
			 for(int i=0;i<10;++i){
				 int a = Asan[i];
				 int b = Bsan[i];
				 
				 if(a>0 && b>0){
					 if(a==b){
						 hits++;
					 }else
					 {
						 blows++;
					 }
				 }
			 }
			 
			 System.out.println(String.format("%d %d", hits, blows));
		}
		
		scan.close();
	}
	
	static int[] san(Scanner s){
		 int[] xsan = new int[10];
		 for(int i=1;i<=4;i++){
			 xsan[s.nextInt()] = i;
		 }
		 return xsan;
	}
}

Measured memory_bytes: 26208
#include <stdio.h>
 int main(void){ 
   int i, n, count;   
 long min, max, sum;  
  max = -1000000;    
min = 1000000;   
 sum = 0;   
 scanf("%d", &count); 
   for (i = 0; i < count; i++){  
      scanf("%d",&n);    
    if (max < n) max = n;  
      if (min > n) min = n;    
    sum += n; 
   }   
 printf("%ld %ld %ld\n",min,max,sum);  
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll x;
    cin>>x;
    ll t = 0;
    ll init = 100;
    while(init < x)
    {
        ll temp = init;
        init = temp + temp/100;
        t += 1;
    }
    cout<<t<<'\n';
}

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

#define rep(i,c) for(int i = 0; i < (int)c; ++i)
using llint = long long int ;
using namespace std;



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

    int count=0;
    for(int i=0;i<N-2;++i){
        if (S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C') ++count;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
N,K=map(int,input().split())
P=list(map(int,input().split()))

A={k+1:P[k] for k in range(N)}


U=list()
S=set()
x=1
k=0

while (x not in S) and (k<=K):
    U.append(x)
    S.add(x)
    
    x=A[x]
    k+=1

if k>K:
    print(U[-1])
else:
    d=U.index(x)
    V=U[d:]
    print(V[(K-d)%len(V)])


Measured memory_bytes: 146228
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,x,y;
cin>>n>>x>>y;
long long dp[n]={0};

for(long long i=1;i<n;i++){
   for(long long j=i+1;j<=n;j++){
    long long temp=min(j-i,abs(x-i)+1+abs(y-j));
    dp[temp]++;
}
}
for(long long i=1;i<n;i++){
  cout<<dp[i]<<endl;
}
return 0;
}


Measured memory_bytes: 256
n=int(input())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
c=[int(x) for x in input().split()]
m=0
before=-1
for i in a:
  m+=b[i-1]
  if before+1==i:
    m+=c[before-1]
  before=i
print(m)

Measured memory_bytes: 3060
x, n = gets.chomp.split(" ").map(&:to_i)
l = gets.chomp.split(" ").map(&:to_i)

ans = nil

if l.index(x)
  1.step do |i|
    ans = x + i unless l.index(x + i)
    ans = x - i unless l.index(x - i)
    break unless ans.nil?
  end
else
  ans = x
end

puts ans


Measured memory_bytes: 14372
#include <bits/stdc++.h>
using namespace std;
#define l S.size()

int main(){
	string S;
	cin >> S;
	const int m = 1000000007;
	long long dp[100010][4] = {};
	for (int i = l; i >= 0; i--){
		for (int j = 3; j >= 0; j--){
			if (i == l)
				dp[i][j] = (j == 3 ? 1 : 0);
			else{
				dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3LL : 1LL);
				if (j < 3 && (S[i] == '?' || S[i] == "ABC"[j]))
					dp[i][j] += dp[i+1][j+1];
				dp[i][j] %= m;
			}
		}
	}
	cout << dp[0][0] << endl;
	return 0;
} 

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ss second
#define ff first
#define mk make_pair
#define pp pair<int,int>
#define ppl pair<long long int,long long int>
#define vec vector<int> 
#define finput ifstream cin;cin.open("in.txt")
#define foutput ofstream cout;cout.open("out.txt") 

//solve()
int count(int n){
	int res=0;
	for(int i=1;i<=n;i++){
		if(n%i==0) res++;
	}
	return res;
}
int main(){
	bool a[201];
	for(int i=1;i<=200;i++){
		if(count(i)==8) a[i]=1;
		else a[i]=0;
	}
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i+=2){
		if(a[i]==1) ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "random"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

const int N=5010;

int n,m;
int a[N],bit[N];

void upd(int i){
    for(;i;i-=i&-i) bit[i]++;
}
int que(int i){
    int ret=0;
    for(;i<=2000;i+=i&-i) ret+=bit[i];
    return ret;
}

main(){
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    n=in;
    forinc(i,1,n) a[i]=in;
    sort(a+1,a+n+1);
    forinc(i,1,n){
        m+=que(a[i]+1); //cout<<i<<" "<<que(a[i])<<"\n";
        forinc(j,1,i-1) upd(a[i]+a[j]);
    }
    cout<<m;
}


Measured memory_bytes: 256
package main

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

// AtCoder Functions
var sc = bufio.NewScanner(os.Stdin)

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

func main() {
	sc.Split(bufio.ScanWords)
	H := nextInt()
	W := nextInt()
	A := nextInt()
	B := nextInt()

	s := ""
	t := ""
	for i := 0; i < A; i++ {
		s += "1"
		t += "0"
	}
	for i := A; i < W; i++ {
		s += "0"
		t += "1"
	}

	for i := 0; i < B; i++ {
		fmt.Println(s)
	}
	for i := B; i < H; i++ {
		fmt.Println(t)
	}
}


Measured memory_bytes: 2688
# Pythonのスライスは最後が開区間だから癖がある
t = input()
for i in range(int(input())):
    cmd = list(input().split())
    cmd[1] = int(cmd[1])
    cmd[2] = int(cmd[2])
    if cmd[0] == "print":
        print(t[cmd[1] : cmd[2]] + t[cmd[2]])
    elif cmd[0] == "reverse":
        tmp = t[cmd[1] : cmd[2]] + t[cmd[2]]
        tmp = tmp[::-1]
        t = t[:cmd[1]] + tmp + t[cmd[2]+1:]
    elif cmd[0] == "replace":
        t = t[:cmd[1]] + cmd[3] + t[cmd[2]+1:]


Measured memory_bytes: 5620
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
/*#include <math.h>*/
#include <string.h>

#define N 10005
#define INF 12345678
#define WHITE 0 
#define GRAY  1
#define BLACK 2
#define NIL -1

void create_generate_super_makeone_node(int, int, int );

struct node{
  struct node *next;
  // struct node *prev;
  int vertex;
  int omosa;
};

typedef struct node *NodePointer;
NodePointer nil;

NodePointer data[N];
//int adj[N][N];
int d[N];
int color[N];
//int check[N];
int pi[N];
//int n;
/*
  void MinHeapify(int );
  void BuildMinHeap(void );
  int  ExtractMin(void );
  void HeapDecreace(int, int );
  void dijkstra(int );
*/

int main(){
  int ex;
  int i,j;
  int n,u,k,vertex,c;
  int uid;
  int mincost;
  int r;

  for(i=0;i<10001;i++){
    data[i] = (NodePointer)malloc(sizeof(struct node));
    data[i]->vertex = INF;
    data[i]->omosa = INF;
    data[i]->next  = NULL;
    // d[i] = INF;
    // color[i] = WHITE;
    // pi[i] = NIL;
  }
  
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    d[i] = INF;
    color[i] = WHITE;
    pi[i] = NIL;

    
    scanf("%d%d",&uid,&k);
    r = uid;
    for(j=0;j<k;j++){
      scanf("%d%d",&vertex,&c);
      create_generate_super_makeone_node(r,vertex,c);
    }
  }


  d[0] = 0;
  for(ex=0;;ex++){
    mincost = INF;
    for(j=0;j<n;j++){
      if(color[j] != BLACK && d[j] < mincost){
	mincost = d[j];
	u = j;
	  }
    }
  
  


    if(mincost == INF) break;

    color[u] = BLACK;
    
    nil = data[u]->next; 
    
    while(nil != NULL){
      // if(nil != NULL) break;

      if(color[nil->vertex] != BLACK && d[u]+nil->omosa<d[nil->vertex]){
	//	printf("aiueo\n\n");
	pi[nil->vertex] = u;
	d[nil->vertex] = nil->omosa+d[u];
      }
      //if(nil != NULL) break;
      nil = nil->next;
      // if(nil != NULL) break;
    }
  }
  for(i=0;i<n;i++){
    printf("%d %d\n",i,d[i]);
  }

  


  

  
    return 0;
}

void create_generate_super_makeone_node(int r, int vertex, int c){
  NodePointer n;
  n =(NodePointer)malloc(sizeof(struct node));
  n->vertex = vertex;
  n->omosa = c;
  n->next = data[r]->next;
  data[r]->next = n;

}



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

int main(){
  string S;
  cin >> S;
  
  if(S=="SAT"){
    cout << 1 << endl;
  }
  else if(S=="FRI"){
    cout << 2 << endl;
  }
  else if(S=="THU"){
    cout << 3 << endl;
  }
  else if(S=="WED"){
    cout << 4 << endl;
  }
  else if(S=="TUE"){
    cout << 5 << endl;
  }
  else if(S=="MON"){
    cout << 6 << endl;
  }
  else {
    cout << 7 << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int n = input.nextInt();
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = input.nextInt();
    }

    if (n == 1) {
      System.out.println("Yes");
      return;
    }

    else {
      for (int i = 1; i < n; i++) {

        if (array[i] < array[i - 1]) {
          System.out.println("No");
          return;

        } else if (array[i] > array[i - 1]) {
          array[i] = array[i] - 1;
        }
      }
    }
    System.out.println("Yes");
  }



}




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

int main() {
  int N, M;
  cin >>N>> M;
  vector<int64_t> h(N);
  for(int i=0; i <N; i++){
    cin >> h.at(i);
  }
  vector<vector<int>> a(N);
  for(int i=0; i <M; i++){
    int x, y;
    cin >> x >> y;
    x -= 1;
    y -= 1;
    a.at(x).push_back(y);
    a.at(y).push_back(x);
  }
  int q= 0;
  for(int i=0; i<N; i++){
    bool z= true;
    for(int j =0; j < a.at(i).size(); j++){
      if(h.at(i) <= h.at(a.at(i).at(j))){
        z=false;
      }
         }
    if(z)q++;
  }
  
         cout << q <<endl;
}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while((x->left) != NIL)
    x = x->left;
  return x;

}

Node treeMaximum(Node x){
  while((x->right) != NIL)
    x = x->right;
  return x;
  
}

Node treeSearch(Node u, int k){
  if(u == NIL || k == (u->key))
    return u;
  if(k < (u->key))
    return treeSearch(u->left,k);
  else
    return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){
  Node y;
  
  if((x->right) != NIL)
    return treeMinimum(x->right);

  y = x->parent;
  while(y != NIL && x == (y->right)){
    x = y;
    y = y->parent;
  }

  return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if((z->left) == NIL || (z->right) == NIL)
    y = z;
  else
    y = treeSuccessor(z);

  if((y->left) != NIL)
    x = y->left;
  else
    x = y->right;

  if(x != NIL)
    x->parent = y->parent;

  if((y->parent) == NIL)
    root = x;
  else if(y == ((y->parent)->left))
    (y->parent)->left = x;
  else
    (y->parent)->right = x;
    
  if(y != z)
    z->key = y->key;


}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL ){
    y = x;
    if((z->key) < (x->key))
      x = x->left;
    else
      x = x->right;
  }

  z->parent = y;
  
  if(y == NIL)
    root = z;
  else
    if((z->key) < (y->key))
    y->left = z;
  else
    y->right = z;

}

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){
  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 25172
#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  long long int arr[n], max = 1e18, product = 1, flag = 0, zero = 0;
  
  for (int i = 0; i < n; i++) {
    scanf("%lld", &arr[i]);
    flag = (arr[i] > max) ? 1 : flag;
    product *= arr[i];
    (arr[i]) ? max /= arr[i] : zero = 1;
  }

  (zero) ? puts("0") : ((flag) ? puts("-1") : printf("%lld\n", product));
  return 0;
}

Measured memory_bytes: 3992
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 200010;
int n, m;
int a[MAX], b[MAX];
VI G[MAX];

int main(void) {
    scanf("%d%d", &n, &m);
    REP(i, m) {
        scanf("%d%d", a + i, b + i);
        a[i]--;
        b[i]--;
        G[a[i]].EB(b[i]);
        G[b[i]].EB(a[i]);
    }
    FORE(e, G[0]) {
        FORE(e1, G[e]) {
            if (e1 == n - 1) {
                cout << "POSSIBLE" << endl;
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 13552