akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 55;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
struct Edge {
	int to;
	Edge *nxt;
	Edge(int to, Edge *nxt) : to(to), nxt(nxt) {}
} *head[N];
void add(int x, int y) {head[x] = new Edge(y, head[x]);}
struct node {LL v; int w, id;} a[N];
bool operator < (node a, node b) {return a.w * b.v > b.w * a.v;}
int n, d, X;
LL dp[N * N * N];
void dfs(int x) {
	a[x].w = 1; a[x].id = x;
	for(Edge *i = head[x]; i; i = i->nxt) {
		dfs(i->to);
		a[x].v += a[i->to].v; a[x].w += a[i->to].w;
	}
}
signed main() {
	n = read(); X = read(); d = read();
	a[1].v = read();
	for(int i = 2; i <= n; ++ i) a[i].v = read(), add(read(), i);
	dfs(1); int mx = n * n * n, L = min(n, d);
	memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
	for(int i = 1; i <= n; ++ i) {
		int x = L;
		for(int j = 0; (1 << j) <= x; ++ j) {
			int w = a[i].w * (1 << j); LL v = a[i].v * (1 << j);
			for(int k = mx; k >= w; -- k) dp[k] = min(dp[k], dp[k - w] + v);
			x -= (1 << j);
		}
		if(x) {
			int w = a[i].w * x; LL v = a[i].v * x;
			for(int j = mx; j >= w; -- j) dp[j] = min(dp[j], dp[j - w] + v);
		}
	}
	sort(a + 1, a + n + 1);
	while(a[n].id != 1) n --;
	LL ans = 0;
	for(int i = 0 ; i <= mx; ++ i) {
		if(dp[i] > X) continue;
		LL w = i, v = dp[i];
		for(int j = 1; j < n; ++ j) {
			LL c = min((LL)d - L, (X - v) / a[j].v);
			w += c * a[j].w; v += c * a[j].v;
		}
		LL c = (X - v) / a[n].v;
		w += c * a[n].w; v += c * a[n].v;
		ans = max(ans, w);
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1664
import * as fs from "fs";

// inputで受け取り配列化する
const input = fs.readFileSync("/dev/stdin", "utf8").split("\n");
const [n, w] = input.shift().split(" ").map(Number);
const items = input.map((item) => item.split(" ").map(Number));

const dp = [];
for (let i = 0; i <= n; i++) {
  const arr = [];
  for (let j = 0; j <= w; j++) {
    arr.push(0);
  }
  dp.push(arr);
}

for (let index = 0; index < n; index++) {
  for (let sum_weight = 0; sum_weight <= w; sum_weight++) {
    const item = items[index];
    if (sum_weight - item[0] >= 0) {
      dp[index + 1][sum_weight] = Math.max(
        dp[index + 1][sum_weight],
        dp[index][sum_weight - item[0]] + item[1]
      );
    }
    dp[index + 1][sum_weight] = Math.max(
      dp[index + 1][sum_weight],
      dp[index][sum_weight]
    );
  }
}

console.log(dp[n][w]);


Measured memory_bytes: 187036
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
#define ff first
#define ss second
#define pb push_back


void solve() {
	string str1, str2 ; cin>>str1>>str2;
	int mn = 1e9, ln = str2.size();
	for(int i=0;i<str1.size()-str2.size()+1;i++) {
		int k = 0, cnt = 0;
		for(int j=i;j<i+ln;j++) {
			if(str1[j] != str2[k++]) cnt += 1;
		}
		mn = min(mn, cnt) ;
	}
	cout<<mn<<endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t = 1, no = 0;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3660
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = n%1000;
		System.out.println(a==0?0:1000-a);
	}

}


Measured memory_bytes: 35748
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define nes ios_base :: sync_with_stdio(0); cin.tie(0);
using namespace std;
ll des=1e12;
ll des1=1e10;
int main(){
	nes;
	ll a;
	ld b;
	cin>>a>>b;
	cout<<(long long)(a*b*100+0.5)/100;
	return 0;
}

Measured memory_bytes: 3708
#include <stdio.h>
 
int main(void) {
	int n,i,m,k,h,j,t;
	scanf("%d",&n);
	for(i=1;i<n+1;i++){
		m=i%10;
		j=i*10;
		k=i%100;
		h=i%1000;
		t=i%10000;
		if(i%3==0){
			printf(" %d",i);
		}else if(m==3){
			printf(" %d",i);
		}else if(i/10==3){
			printf(" %d",i);
		}else if(k>29&&k<40){
				printf(" %d",i);
		}else if(299<h&&h<400){
			printf(" %d",i);
		}else if(2999<t&&t<4000){
			printf(" %d",i);
		}
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define ppi pair<int,pair<int,int> >
#define fr first
#define sc second
#define PI acos(-1)
#define mp make_pair

using namespace std;


#define sim template < class c

#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "



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

    int a , b;
    cin >> a >> b;

    int r = 1;
    int cnt = 0;
    while(r < b){
        r += a - 1;
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(final String[] args) {
    @SuppressWarnings("resource")
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Card[] arr = new Card[n];
    for (int i = 0; i < n; i++) {
      arr[i] = new Card();
      char[] c = sc.next().toCharArray();
      arr[i].suit = c[0];
      arr[i].value = c[1];
    }
    Card[] arr2 = Arrays.copyOf(arr, n);

    bubbleSort(arr);// always stable
    trace(arr);
    System.out.println("Stable");

    selectionSort(arr2);
    trace(arr2);
    System.out.println(isStable(arr, arr2) ? "Stable" : "Not stable");
  }

  static boolean isStable(Card[] arr, Card[] arr2) {
    for (int i = 0; i < arr.length; i++) {
      if (arr[i].suit != arr2[i].suit)
        return false;
    }
    return true;
  }

  static int selectionSort(Card[] arr) {
    int cnt = 0, minIdx;
    for (int i = 0; i < arr.length - 1; i++) {
      minIdx = i;
      // 未ソートの部分から最小の要素の位置を特定して
      for (int j = i; j < arr.length; j++) {
        if (arr[j].value < arr[minIdx].value)
          minIdx = j;
      }
      // 交換する
      if (i != minIdx) {
        Card tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
        cnt++;
      }
    }
    return cnt;
  }

  static int bubbleSort(Card[] arr) {
    int cnt = 0;
    for (int i = 0; i < arr.length - 1; i++) {
      for (int j = arr.length - 1; j >= i + 1; j--) {
        if (arr[j].value < arr[j - 1].value) {
          Card tmp = arr[j];
          arr[j] = arr[j - 1];
          arr[j - 1] = tmp;
          cnt++;
        }
      }
    }
    return cnt;
  }

  static void trace(Card[] arr) {
    StringBuilder sb = new StringBuilder();
    for (Card c : arr) {
      sb.append(c.toString()).append(' ');
    }
    System.out.println(sb.toString().trim());
  }
}

class Card {
  char suit;
  char value;

  public String toString() {
    return String.valueOf(suit) + value;
  }
}


Measured memory_bytes: 26452
#include <stdio.h>
#include <ctype.h>
int main(void) {                                                                
    int c;                                                                      
    while ((c = getchar()) != EOF) {                                            
        putchar(toupper(c));                                                    
    }                                                                                                                                                           
    return 0;                                                                   
}

Measured memory_bytes: 524
x, k, d = map(int, input().split())
x = abs(x)
e = x//d

if e>k:
    print(x-d*k)
else:
    if (k-e)%2 == 0:
        print(abs(x-d*e))
    else:
        print(abs(x-d*(e+1)))

Measured memory_bytes: 9140
#include <stdio.h>

int main(void){
int th[3],mx = 0,md = 0,k;
scanf("%d%d%d",&th[0],&th[1],&th[2]);
for(int i = 0;i <= 2;i++){
if(mx < th[i]){
mx = th[i];
k = i;
}
}
th[k] = 0;
for(int i = 0;i <= 2;i++){
md = th[i] + md;
}
scanf("%d",&k);
for(int i = 0;i < k;i++){
mx *=2;
}
printf("%d",mx + md);
return 0;
}

Measured memory_bytes: 128
#if 0
date +%Y.%m.%d

  先放长度最大的弧，然后根据其位置把环转成链，问题变为连续的线段覆盖问题。
  注意到长度都是整数，那么只要枚举剩下所有弧的位置的小数部分的大小关系，问题就可以转换
为离散的线段覆盖，而所有弧的小数部分是独立同分布随机变量，因此每种大小关系是等概率出现
的。
  既然小数部分的大小关系已经确定，不妨设其为 1/n, 2/n, ... ，那么问题就是在长为 C * n
的链上做离散的线段覆盖问题，DP 设 f[S][i] 表示用 S 集合内的线段，恰好覆盖 [0, i] 的方
案数。不重不漏的转移需要枚举左端点最右边的线段，实现可以直接从小到大枚举左端点，再枚举
状态进行插入线段的转移。
#endif
#include <cstdio>
#include <cstring>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef long double ld;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
} read;

const int maxn = 6, maxc = 50;
int len[maxn], p[maxn];
ll f[1 << maxn][maxc * maxn + 1];

int main () {
	int n = read, c = read;
	for (int i = 0; i < n; i ++) read(len[i]);
	std::sort(len, len + n);

	ll ans = 0, tot = 0;
	for (int i = 1; i < n; i ++) p[i] = i - 1;
	do {
		int U = (1 << n >> 1) - 1;
		memset(f, 0, sizeof f);
		int min = len[n - 1] * n;
		f[0][min] = 1;
		for (int l = 0, i; l < c * n; l ++)
			if ((i = l % n)) {
				i = p[i];
				int r = std::min(c * n, l + len[i] * n);
				for (int S = 0; S <= U; S ++)
					if (!(S >> i & 1))
						for (int k = l; k <= c * n; k ++)
							f[S | (1 << i)][std::max(k, r)] += f[S][k];
			}
		ans += f[U][c * n];
		++ tot;
	} while (std::next_permutation(p + 1, p + n));

	ld Ans = ans;
	Ans /= tot;
	for (int i = 0; i < n - 1; i ++)
		Ans /= c;
	printf("%.12Lf\n", Ans);
}


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

int main() {
  vector<char>moji(3);  
  for(int i=0;i<3;i++){
     cin >> moji.at(i);
  }
  int count=0;  
  for(int i=0;i<3;i++){
  	if(moji.at(i)=='o')count++;
  }
  cout << 700+100*count << endl;
}

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

const int MAXV = 100005;
vector<int> to[MAXV];

bool visited[MAXV];
int dp[MAXV]; // max length of path from v
int dfs(int v) {
  if (visited[v]) return dp[v];
  visited[v] = true;
  dp[v] = 0;
  for (int u : to[v]) {
    int res = dfs(u);
    dp[v] = max(dp[v], res+1);
  }
  return dp[v];
}

int main() {
  int n,m;
  cin >> n >> m;
  rep(i,m) {
    int x,y;
    cin >> x >> y;
    x--;y--;
    to[x].push_back(y);
  }

  int ans = 0;
  rep(i,n) {
    int res = dfs(i);
    ans = max(ans, res);
  }
  cout << ans << endl;
  return 0;
}


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

int main(void){
    int N;
    vector<long long> L;
    long long tmp;
    int count = 0;

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> tmp;
        L.push_back(tmp);
    }

    vector<long long> tL;
    for(int i=0; i<(N-2); i++){
        tL.push_back(L[i]);
        for(int j=i; j<(N-1); j++){
            tL.push_back(L[j]);
            for(int k=j; k<N; k++){
                tL.push_back(L[k]);
                if( L[i]!=L[j] && L[i]!=L[k] && L[j]!=L[k]){
                    int max = max_element(tL.begin(),tL.end()) - tL.begin();
                    int maxElement = *max_element(tL.begin(), tL.end());
                    if( (tL[0]+tL[1]+tL[2]) > (maxElement*2) ){
                        count ++;
                    }
                }
                tL.pop_back();
            }
            tL.pop_back();
        }
        tL.pop_back();
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using ll = long long;
#define ull unsigned ll
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ppi pair<int, pii>
#define mt make_tuple
#define eb emplace_back
using namespace std;

const int N = 305, mod = 1e9 + 7;
const int inf = 1e9;
void solve(){
    int n;
    cin >> n;
    string s;
    int a = 0, b = 0, c = 0, d = 0;
    for(int i = 0; i < n; i++){
        cin >> s;
        if(s == "AC") a++;
        else if(s == "WA") b++;
        else if(s == "TLE") c++;
        else d++;
    }
    cout << "AC x " << a << endl;
    cout << "WA x " << b << endl << "TLE x " << c << endl << "RE x " << d << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);//cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll t,p;
    t=1;
    //cin>>t;
    for(p=1;p<=t;p++){
        solve();
    }
    return 0;
}


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

using namespace std;

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

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

    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i] - 1;
    }

    cout << sum << endl;

    return 0;
}


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

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

template <typename T>
void debug_out(T t) {
  cerr << t;
}

template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}

template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << ", ";
  }
}

template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << endl;
  }
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" << endl, debug_out(__VA_ARGS__), cerr << endl;


int n;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  vector<int> a(n);
  range(i, 0, n) {
    cin >> a[i];
  }
  bool easy = true;
  range(i, 1, n) {
    easy &= a[i] > a[i - 1];
  }
  if(easy) {
    cout << 1;
    return 0;
  }
  vector<pair<int, int>> one;
  vector<pair<int, int>> other;
  auto solve = [&](int s) {
    one.clear(); other.clear();
    one.emplace_back(0, a[0] - 1);
    range(i, 1, n) {
      if(a[i] > a[i - 1]) {
        if(one.size() && one.back().second == a[i - 1] - 1) one.back().second = a[i] - 1;
        else one.push_back(make_pair(a[i - 1], a[i] - 1));
        continue;
      }
      while(one.size() && one.back().first >= a[i]) one.pop_back();
      if(one.size()) one.back().second = min(one.back().second, a[i] - 1);
      while(other.size() && other.back().first >= a[i]) other.pop_back();
      if(one.empty() && other.empty()) {
        return false;
      }
      int pos = INT_MIN;
      if(one.size()) pos = one.back().second;
      if(other.size()) pos = max(pos, other.back().first);
      if(one.size() && one.back().second == pos) {
        one.back().second--;
        if(one.back().second < one.back().first) one.pop_back();
        if(s > 2) other.emplace_back(pos, 2);
      } else {
        other.back().second++;
        if(other.back().second == s) other.pop_back();
      }
      if(pos + 1 < a[i]) one.emplace_back(pos + 1, a[i] - 1);
    }
    return true;
  };
  int lo = 1, hi = n;
  while(hi - lo > 1) {
    int mid = (hi + lo) >> 1;
    if(solve(mid)) hi = mid;
    else lo = mid;
  }
  cout << hi;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

map<ll, ll> m;
ll sum;

int main(void) {
    int n, q;
    cin >> n;
    rep(i, 0, n) {
        ll x;
        cin >> x;
        m[x]++;
        sum += x;
    }
    cin >> q;
    rep(i, 0, q) {
        ll b, c;
        cin >> b >> c;
        sum -= b*m[b];
        sum += c*m[b];
        m[c] += m[b];
        m[b] = 0;
        printf("%lld\n", sum);
    }



    return 0;
}



Measured memory_bytes: 9536
#include<stdio.h>
#include<limits.h>

#define LEN 200000

int max(long long int x,long long int y){
  long long int maxi = x;
  if(y > maxi){
    maxi = y;
  }
  return maxi;
}

int min(long long int x,long long int y){
  long long int mini = x;
  if(y < mini){
    mini = y;
  }
  return mini;
}

int main(){
  int R[LEN],n;

  scanf("%d",&n);
  for(int i = 0; i < n; i++)
    scanf("%d",&R[i]);

  int maxv = -1145141919;
  int minv = R[0];

  for(int i = 1; i < n; i++){
    maxv = max(maxv,R[i] - minv);
    minv = min(minv,R[i]);
  }

  printf("%d\n",maxv);
}



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

def print_list(A):
    for a in A[:-1]:
        print ("%d "%a, end="")
    print(A[-1])

def InsertionSort(A, N):
    print_list(A)
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print_list(A)

InsertionSort(A, N)

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

struct nod
{
  struct nod* parent;
  struct nod* left;
  struct nod* right;
  int node_number;
  int height_check;
};

typedef struct nod *NodePointer;


void visit(int);
void visit2(int);
void visit3(int);

NodePointer node[27];

main()
{
  int i,j,n,k;
  int n1,n2,n3;
  int sibling=0,degree=0,depth=0,height=0;
  int count=0;
  NodePointer roop;

  int countmax=0;
  NodePointer NIL;


  roop = malloc(sizeof(struct nod));


  NIL = malloc(sizeof(struct nod)); 
  NIL->node_number=-1;
  NIL->left=NULL;
  NIL->right=NULL;
  NIL->parent=NULL;
  NIL->height_check=0;
  
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++)
    {  
      node[i]=malloc(sizeof(struct nod));
    }
  
  for(i=0;i<n;i++)
    {
      node[i]->node_number=-1;
      node[i]->left=NIL;
      node[i]->right=NIL;
      node[i]->parent=NIL;
      node[i]->height_check=0;
    }
  
  for(i=0; i<n ;i++)
    {
      scanf("%d",&n1);
      scanf("%d",&n2);
      scanf("%d",&n3);
      
      node[n1]->node_number=n1;
      
      if(n2!=-1)
	{
	  node[n1]->left=node[n2];
	  node[n2]->parent=node[n1];
	  node[n2]->node_number=n2;
	}
      else
	node[n1]->left=NIL;
      
      if(n3!=-1)
	{
	  node[n1]->right=node[n3];
	  node[n3]->parent=node[n1];
	  node[n3]->node_number=n3;
	}
      else
	node[n1]->right=NIL;
    }


  for(i=0;i<n;i++)
    {
      if(node[i]->parent->node_number==-1)
	{
	  node[i]->height_check=1;
	  k=i;
	}

      else if( node[i]->left==NIL &&node[i]->right==NIL)
	node[i]->height_check=3;
	
      else
	node[i]->height_check=2;

    }


  for(j=0;node[j]->parent->node_number!=-1;j++);

  printf("Preorder\n");
  visit(node[j]->node_number);
  printf("\n");

  printf("Inorder\n");
  visit2(node[j]->node_number);
  printf("\n");

  printf("Postorder\n");
  visit3(node[j]->node_number);
  printf("\n");
  return 0;
}



void visit(int k)
{
  printf(" %d",k);

  if(node[k]->left->node_number!=-1)
    {
      visit(node[k]->left->node_number);
    }
  if(node[k]->right->node_number!=-1)
    {
      visit(node[k]->right->node_number);
    }


}


void visit2(int k)
{
  if(node[k]->left->node_number!=-1)
    {
      visit2(node[k]->left->node_number);
    }

  printf(" %d",k);


  if(node[k]->right->node_number!=-1)
    {
      visit2(node[k]->right->node_number);
    }


}



void visit3(int k)
{
  if(node[k]->left->node_number!=-1)
    {
      visit3(node[k]->left->node_number);
    }
  if(node[k]->right->node_number!=-1)
    {
      visit3(node[k]->right->node_number);
    }
  printf(" %d",k);


}

Measured memory_bytes: 616
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC target ("avx2,tune=native")
#include<bits/stdc++.h>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define __V vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define oit ostream_iterator
#define mod 1000000007ll
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
	in >> a.first >> a.second;
	return in;
}
template<typename T>
void getv(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
	v.resize(n);
	for (auto& i : v)
		getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
	v.resize(n + 1);
	for (int i = 1; i <= n; i++)
		getv1(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &x) {
	while (x = getchar_unlocked(), x < 33) {
		;
	}
}
inline void getstr(string &str) {
	str.clear();
	char cur;
	while (cur = getchar_unlocked(), cur < 33) {
		;
	}
	while (cur > 32) {
		str += cur;
		cur = getchar_unlocked();
	}
}
template<typename T> inline bool sc(T &num) {
	bool neg = 0;
	int c;
	num = 0;
	while (c = getchar_unlocked(), c < 33) {
		if (c == EOF)
			return false;
	}
	if (c == '-') {
		neg = 1;
		c = getchar_unlocked();
	}
	for (; c > 47; c = getchar_unlocked())
		num = num * 10 + c - 48;
	if (neg)
		num *= -1;
	return true;
}
template<typename a, typename b>
void minq(a& x, b y) {
	if (x > y)
		x = y;
}
template<typename a, typename b>
void maxq(a& x, b y) {
	if (x < y)
		x = y;
}
typedef unsigned long long ull;
typedef long long ll;
typedef float ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <string> vs;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
//store differences, not the elements for rsq in fenwick or array(for write-only)
//SQRT-heuristic divide items into groups: >sqrt and <=sqrt and do something according to group(eg. trie for one, z-func for other) - 1202E
uniform_real_distribution<double> double_dist(0, 1);
//WHEN DOING MODULAR SUBTRACTION ALWAYS **ALWAYS** ADD MOD
//don't use AVX at AtCoder
//Trie: MAXDEPTH!=MAXSIZE
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
	doin();
	int a;string s;
	cin >> a >> s;
	if(a >= 3200) cout << s;else cout << "red";
}


Measured memory_bytes: 256
N = int(input())
listP = [int(_) for _ in input().split()]

count = 0
for i in range(N-1):
    if listP[i] == (i+1):
        listP[i],listP[i+1] = listP[i+1],listP[i]
        count += 1
if listP[N-1] == N:
    count += 1

print(count)


Measured memory_bytes: 13880
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
int main(){
    int A,B;
    cin >> A >> B;
    string S;
    cin >> S;
    bool flg = true;
    for(int i=0; i<A; i++){
        if(S[i] == '-') flg = false;
    }
    if(S[A] != '-') flg = false;
    for(int i=A+1; i<A+B+1; i++){
        if(S[i] == '-') flg = false;
    }
    if(flg) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<string.h>
#include<set>
#include<algorithm>
using namespace std;

int main(){
	long long n,m;
    cin>>n>>m;

    long long scc = 0;
    if(n*2<=m){
        scc += n;
        m -= n*2;
        scc += m/4;
    }
    else{
        scc += m/2;
    }

    cout<<scc;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	if (n == m)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int F[44];

void fibonacci(int n){
    int i;
    F[0]=1;
    F[1]=1;
    for(i=2;i<=n;i++)F[i]=F[i-2]+F[i-1];
}

int main(){
    int n;
    scanf("%d",&n);
    fibonacci(n);
    printf("%d\n",F[n]);
    return 0;
}



Measured memory_bytes: 2100
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

bool next_choice(int ixh[], int h, int N) {
  for(int i = h-1, n = N; i >= 0; --i, --n) {
    if(ixh[i]+1 < n) {
      int v = ixh[i]+1;
      for(int j = i; j < h; ++j) ixh[j] = v++;
      return true;
    }
  }
  return false;
}

struct bit {
  int data_[32];
  bit() { std::fill_n(data_, 32, 0); }
  int lb(int i){ return i&-i; }
  int query(int i) { // 1-base
    int res = 0;
    while(i > 0) { res += data_[i-1]; i -= lb(i); }
    return res;
  }
  void add(int i, int v) { // 1-base
    while(i <= 32) { data_[i-1] += v; i += lb(i); }
  }
};

int calc(int ix[], int N) {
  bit b;
  int res = 0;
  for(int i = 0; i < N; ++i) {
    res += i - b.query(ix[i]+1);
    b.add(ix[i]+1, 1);
  }
  return res;
}

uint64_t getZ() {
  uint64_t v = 0; int c;
  while((c = getchar_unlocked()) >= '0') v=v*10+c-'0';
  return v;
}

int main() {
  int N = getZ(), H = (N+1)/2;
  int ab[2][18];
  for(int i = 0; i < N; ++i) std::cin >> ab[i%2][i];
  for(int i = 0; i < N; ++i) std::cin >> ab[(i+1)%2][i];
  int ix[18], ixh[9], ixe[9], ixo[9];
  bool used[18];
  std::iota(ixh, ixh+H, 0);
  
  int ans = 10000;
  // check all possibility; MAX: comb(18,9) < 50000
  for(;;) {
    // prepare even
    std::copy_n(ixh, H, ixe);
    std::sort(ixe, ixe+H, [&](int l, int r){ return ab[0][l] < ab[0][r]; });
    
    // prepare odd
    std::fill_n(used, N, false);
    for(int i = 0; i < H; ++i) used[ixh[i]] = true;
    int ix_o = 0;
    for(int i = 0; i < N; ++i) if(!used[i]) ixo[ix_o++] = i;
    std::sort(ixo, ixo + N-H, [&](int l, int r){ return ab[1][l] < ab[1][r]; });
    
    // check if sorted
    bool sorted = true;
    for(int i = 0; i < N-H; ++i) {
      if(ab[0][ixe[i]] > ab[1][ixo[i]]) { sorted = false; break; }
      if(i+1 < H &&  ab[1][ixo[i]] > ab[0][ixe[i+1]]) { sorted = false; break; }
    }
    if(sorted) {
      // merge
      for(int i = 0; i < H; ++i) ix[i*2] = ixe[i];
      for(int i = 0; i < N-H; ++i) ix[i*2+1] = ixo[i];
      ans = std::min(ans, calc(ix, N));
    }
    
    if(!next_choice(ixh, H, N)) break;
  }
  if(ans > 9999) ans = -1;
  fin(ans);
  return 0;
}


Measured memory_bytes: 384
iN,iY = [int(_) for _ in input().split()]
iY //= 1000

#a+b+c = n
#10a+5b+c = y

#9a+4b = y-n
#a=(y-n-4b)/9
#b=(y-n-9a)/4

iD = iY -iN
for i10 in range(iD//9 + 1):
    iD2 = iD - 9*i10
    if iD2 % 4 :
        continue
    else:
        i5 = iD2 // 4
        if iN-i10-i5 >= 0:
            print(i10,i5,iN-i10-i5)
            exit()
print(-1,-1,-1)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k;cin>>n>>k;
    vector<ll> p(n), c(n);
    vector<ll> pinv(n);
    rep(i,n){
        ll P; cin>>P;
        p[i]=P-1;
        pinv[p[i]]=i;
    }
    rep(i,n)cin>>c[i];
    ll ans = -INF;
    rep(i,n){
        ll now = i;
        vector<P> vis(n, {-1, 0});
        ll t = k, score = 0;
        ll MAX = -INF;
        
        while(t>0&&vis[now].first==-1){
            vis[now].first=t;
            vis[now].second=score;
            now = p[now];
            score+=c[now];
            MAX = max(score, MAX);
            t--;
        }
        if(t==0||score - vis[now].second<0){
            ans=max(MAX,ans);
            continue;
        }
        ll per = vis[now].first-t;
        score += (score - vis[now].second)*(t/per);
        t %=per;
        MAX = max(score, MAX);
        while(t>0){
            t--;
            
            now=p[now];
            score+=c[now];
            
            MAX = max(score, MAX);
        }
        rep(i,per){
            score -= c[now];
            MAX = max(score, MAX);
            now = pinv[now];
        }
        ans=max(MAX,ans);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
     
int main() {
  int N;
  cin >> N;
  vector<string> blue(N);
  int ans = 0;
  for(int i = 0; i < N; i++){
    cin >> blue.at(i); 
  }
  int M;
  cin >> M;
  vector<string> red(M);
  for(int j = 0; j < M; j++){
    cin >> red.at(j);
  }
  
  string XX;
  int point;
  for(int k = 0; k < N; k++){
    
    XX = blue.at(k);
    point = 0;  
    
    for(int l = 0; l < N; l++){
      
      if(blue.at(l) == XX){
      point += 1;
      }
      
    }
    
    for(int m = 0; m < M; m++){
      
      if(red.at(m) == XX){
      point -= 1;
      }
      
    }
    
    if(ans <= point){
    ans = point;
    }
    
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    int i = 1;
    int count = 1;
    while(1){
        if(a >= pow(b,i)){
            i++;
            count++;
        }
        else{
            break;
        }
        
    }
    cout << count << endl;
}


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

#define int long long int
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back

const int MOD = 1e9 + 7;

vvi adj;

int dp[101][4][2];


int power(int x, int y) {
    if(y == 0)  return 1ll;
    if(y % 2)   return (x * power(x, y - 1)) % MOD;
    int f = power(x, y / 2);
    return (f * f) % MOD;
}

int f(string s, int k, int i, bool lastSame) {
    if(k == 0)  return 1;
    if(k < 0 || i == s.size())   return 0;
    int num = s[i] - '0';
    if(dp[i][k][lastSame] != -1)    return dp[i][k][lastSame];
    int ans = 0;
    if(lastSame) {
        for(int j = 0; j <= num; j++) { 
            ans += f(s, k - (j != 0), i + 1, (j == num));
        }
    }
    else {
        for(int j = 0; j <= 9; j++) {
            ans += f(s, k - (j != 0), i + 1, false);
        }
    }
    return dp[i][k][lastSame] = ans;
}

signed main() {
    string s;
    int k;
    cin >> s >> k;
    memset(dp, -1, sizeof dp);
    cout << f(s, k, 0, true);
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int F,T;
	bool f=true;
	char c;
	int Q;
	string s;
	cin>>s;
	cin>>Q;
	for(int i=0;i<Q;i++){
		cin>>F;
		if(F==1) f^=1;
		else{
			cin>>T>>c;
			if(T==1&&f||T==2&&!f)
				s.insert(s.begin(),c);
			if(T==1&&!f||T==2&&f)
				s.push_back(c);
		}
	}
	if(!f)reverse(s.begin(),s.end());
	cout<<s<<endl;
}


Measured memory_bytes: 900
#include <cstdint>
#include <iostream>
#include <set>

using namespace std;

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

  set<std::int64_t> set{s};

  std::int64_t a = s;
  for (int i = 1; i <= 1000000; ++i) {
    std::int64_t b;
    if (a % 2 == 0) {
      b = a / 2;
    } else {
      b = 3 * a + 1;
    }
    if (set.find(b) != set.end()) {
      cout << i + 1 << endl;
      return 0;
    }
    set.insert(b);
    a = b;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c + 9 * max({a, b, c}) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
  int X, Y, Z;
  cin >> X >> Y >> Z;

  int ans = 0;
  int length = 0;

  while(length <= X){
    ans++;
    length = Y*ans + Z*(ans+1);    
  }
  cout << ans-1 <<endl;
  
  return 0;
}

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

using namespace std;

const int N = 15;

int n;
int a[N], x[N][N], y[N][N];

inline bool check(int s) {
    for (int i = 0; i < n; ++i) if((s>>i)&1) {
        for (int j = 0; j < a[i]; ++j) {
            if (((s>>x[i][j])&1) != y[i][j])
                return false;
        }
    }
    return true;
}

inline int count(int x)
{
    int res = 0;
    while (x) {
        res += x&1;
        x >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        for (int j = 0; j < a[i]; ++j) {
            cin >> x[i][j] >> y[i][j];
            --x[i][j];
        }
    }
    int res = 0;
    for (int i = 0; i < 1<<n; ++i) {
        if (check(i))
            res = max(res, count(i));
    }
    cout << res << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

using namespace std;
const int INF = 1 << 30;
const long long LINF = 1LL << 60;
const long long MOD = 1000000000 + 7;
const double PI = acos(-1);

int main() {
	int N; cin >> N;
	vector<int> A(N), B(N);
	rep(i, N) {
		cin >> A[i] >> B[i];
	}
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	if (N % 2 == 1) {
		cout << B[N / 2] - A[N / 2] + 1;
	}
	else {
		long long num = B[N / 2 - 1] + B[N / 2];
		num -= A[N / 2 - 1] + A[N / 2];
		cout << num + 1;
	}
}

Measured memory_bytes: 4764
#include <bits/stdc++.h>
using namespace std;
 
typedef long long lint;
 
void ans(lint n) {
  cout << "! " << n << endl;
}
 
bool q(lint n) {
  char c;
  cout << "? " << n << endl;
  cin >> c;
 
  return c == 'Y';
}
 
lint N;
bool debug(lint n) {
  cout << "? " << n << endl;
  return ((n <= N) == (to_string(n) <= to_string(N)));
}
 
int main() {
  int s;
  
  // cin >> N;
  // cin >> s;
 
  bool f = q(1000000000000);
  if (f) {
    s = 1;
    for (lint i = 9; !q(i); i = i * 10 + 9) s++;
  } else {
    s = 0;
    for (lint i = 1; q(i); i *= 10) s++;
  }
 
  lint l = pow(10, s - 1) - 1, r = pow(10, s) - 1;
  while (r - l > 1) {
    lint m = (l + r) / 2;
    if (q(10 * m)) {
      r = m;
    } else {
      l = m;
    }
  }
 
  ans(r);
}

Measured memory_bytes: 652
from math import factorial

N = int(input())
S1 = input()
S2 = input()
S = list(zip(S1,S2))

new = []
z = 0
while z != len(S):
    if S[z][0] == S[z][1]:
        new.append("V")
    else:
        new.append("H")
        z += 1
    z += 1

if new[0] == "H":
    result = 6
else:
    result = 3
    
for i in range(len(new)-1):
    if new[i] == "H" and new[i+1] == "H":
        result = (result * 3) % 1000000007
    elif new[i] == "H" and new[i+1] == "V":
        result = (result * 1) % 1000000007
    elif new[i] == "V":
        result = (result * 2) % 1000000007
print(result)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int N,M;
vector<int> X;

int main(){
    cin >> N >> M;
    X.resize(N);
    rep(i,N) cin >> X[i];

    vi cnt(100005,0);
    rep(i,N) cnt[X[i]]++;
    vi modcnt(M+10,0);
    rep(i,N) modcnt[X[i]%M]++;

    int ans = 0;

    for(int i=0;i<M;i++){
        int j = (M - i)%M;
        if(i == j){
            ans += modcnt[i] / 2;
            modcnt[i] %= 2;
        }else{
            int a = min(modcnt[i],modcnt[j]);
            ans += a;
            modcnt[i] -= a;
            modcnt[j] -= a;
        }
    }


    for(int i=0;i<=100000;i++){
        int m = i % M;
        int ad = min(cnt[i],modcnt[m]);
        ans += ad / 2;
        modcnt[m] -= ad / 2 * 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define R register
const ll mod = 1e9+7;

inline void read(int &x){
	static int ch; static bool flag;
	for(flag=0,ch=getchar(); ch>'9'||ch<'0'; ch=getchar()) flag |= ch=='-';
	for(x=0; ch>='0'&&ch<='9'; ch=getchar()) x = (x<<1) + (x<<3) + ch-48;
	x = flag ? -x : x;
}

int H,W,A,B;
ll Ans,jc[200002],inv[200002];

inline ll ksm(ll a,int b){
	R ll ret=1;
	while(b){
		if(b&1) ret=ret*a%mod;
		a=a*a%mod; b>>=1;
	}
	return ret;
}

inline ll C(int n,int m){
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}

inline ll calc(int n,int m){
	return C(n+m,m);
}

int main()
{
	read(H),read(W),read(A),read(B);
	jc[0]=inv[0]=1;
	for(R int i=1;i<H+W-1;++i) jc[i]=jc[i-1]*i%mod,inv[i]=ksm(jc[i],mod-2);
	for(R int i=B+1;i<=W;++i)
		Ans=(Ans+calc(H-A-1,i-1)*calc(A-1,W-i)%mod)%mod;
	printf("%lld\n",Ans);
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;

 
int main() {
  int h,w;
  cin >> h >> w;
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a.at(i);
  vector<vector<int>> maze(h,vector<int>(w,0));
  int now = 0;
  rep(i,h){
    if(i%2 == 0){
      for(int j=0;j<w;j++){
        maze.at(i).at(j) = now;
        a.at(now) --;
        if(a.at(now) == 0) now ++;
      }
    }else{
      for(int j=w-1;j>=0;j--){
        maze.at(i).at(j) = now;
        a.at(now) --;
        if(a.at(now) == 0) now ++;
      }
    }
  }
  rep(i,h){
    rep(j,w){
      cout << maze.at(i).at(j) + 1 ;
      if(j == w-1) cout << endl;
      else cout << ' ';
    }
  }  
        
  return 0;
}




Measured memory_bytes: 384
k, q = list(map(int, input().split()))
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for _ in range(q)]

D = [[0] * 2 for _ in range(k)]
for i in range(q):
  n, x, m = nxm[i]
  D[-1] = [0, 0]
  D[0][0] = d[0] % m
  D[0][1] = 0

  for j in range(k):
    D[j][0] = (D[j - 1][0] + d[j] % m)
    D[j][1] = D[j - 1][1]
    if D[j - 1][0] != D[j][0]:
      D[j][1] += 1

  N, M = divmod(n - 1, k)

  ans = N * D[-1][1]
  t = N * D[-1][0] + (x % m)
  ans -= t // m
  t = t % m
  if M != 0:
    ans += D[M - 1][1]
    t += D[M - 1][0]
    ans -= t // m
  
  print(ans)
     



Measured memory_bytes: 49512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define ln '\n'
const long long MOD = 1000000007LL;
//const long long MOD = 998244353LL;
typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////
int N;
set<string> dic;
void dfs(string S) {
	int L = S.size();
	if (L==N) {
		dic.emplace(S);
		return;
	}
	char c = '`';
	rep(i,L) chmax(c,S[i]);
	++c;
	for (char i = 'a'; i <= c; ++i) {
		dfs(S+i);
	}
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> N;
	dfs("");
	for (auto i : dic) cout << i << ln;
}


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

int main(){
  	int n;
	scanf("%d", &n);
	int cont=0;
	for (int i=1; i<=n; i++){
      	int x;
     	scanf("%d", &x);
      	if(x != i) cont++;
    }
	if(cont <= 2) puts("YES");
	else puts("NO");
}


Measured memory_bytes: 256
#include <stdio.h>

int main () {
	int c,d,n,m,count;
	scanf("%d", &n);

	int a[n];
	for (c = 0; c < n; c++) {
		scanf("%d", &a[c]);
	}

	count = 0;
	for (c = 0; c < (n - 1); c++) {
		if (a[c] > a[c + 1]) {
			d = c;
			while (a[d] > a[d + 1]) {
				m = a[d];
				a[d] = a[d + 1];
				a[d + 1] = m;
				if (d != 0) {
					d--;
				}
				count++;
			}
		}
	}

	for (c = 0; c < n; c++) {
		if (c == (n - 1)) {
			printf("%d\n", a[c]);
		}else {
			printf("%d ", a[c]);
		}
	}

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

	return 0;
}


Measured memory_bytes: 2116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,k,a[1005],ans;
vector<ll>s;
int main(void){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		a[i]+=a[i-1];
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			s.PB(a[j]-a[i-1]);
		}
	}
	n=s.size();
	for(ll i=40;i>=0;i--){
		int p=0;
		for(int j=0;j<n;j++)if(s[j]>>i&1)p++;
		if(p>=k){
			ans+=1LL<<i;
			vector<ll>o;
			for(int j=0;j<n;j++)if(s[j]>>i&1)o.PB(s[j]);
			s.clear();
			for(int j=0;j<o.size();j++)s.PB(o[j]);
			n=s.size();
		}
	}
	cout<<ans<<endl;
}


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

// #include <boost/algorithm/string/join.hpp>
// using boost::algorithm::join;
//
// #include "boost/multi_array.hpp"
// boost::multi_array<int, 3> dp;
// dp.resize(boost::extents[10][9][8]);
//
// #include <boost/multiprecision/cpp_dec_float.hpp>  // quite slowly
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision; // mp::log10
// using bigint = boost::multiprecision::cpp_int;
// using rational = mp::cpp_rational;  // double d = static_cast<double>(r);

typedef long long ll;
typedef unsigned long long ull;
//typedef long double ld;

typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<pair<int, int > > vii;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vll> vvll;

//constexpr ll MOD = 1e9+7;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/4;
constexpr int INF=inf<int>;
constexpr ll LINF=inf<ll>;

#define Sort(x) sort(begin(x),end(x))
#define Reverse(x) reverse(begin(x),end(x))
#define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b))
#define nbit(n) (1ull<<(n))
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,(v).size())

// sort(begin(x), end(x), greater<ll>());
// lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
// upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置

// Returns minimum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmin(T& a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}

// Returns maximum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmax(T& a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}

template <typename T>
void dumpContents(const T& v, const string& msg)
{
  cerr << "### " << msg << " ###\n";
  for (const auto& x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

struct before_main_function {
  before_main_function() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(20)<<fixed;
#define endl "\n"
  }
} before_main_function;

// ========== end of template ==========
int N;
vll X;

ll score(int a) {
  ll ret = 0;

  for (auto x : X) {
    ret += (x-a)*(x-a);
  }

  return ret;
}

int main(int argc, char** argv) {
  cin >> N;
  X.resize(N);
  for (auto& x : X) {
    cin >> x;
  }
  Sort(X);

  if (N==1) {
    cout << 0 << endl;
    return 0;
  }

  ll ret = LINF;
  for (ll x = X[0]; x<=X[N-1]; x++) {
    chmin(ret, score(x));
  }

  cout << ret << endl;

  return 0;
}

/* vim: set expandtab shiftwidth=2 softtabstop=2 : */


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

using namespace std;

int main() {
  int n;
  while(true) {
    cin >> n;
    if(!n) break;

    bool flg;
    int ans = 0;
    for(int i = n+1; i <= 2*n; i ++) {
      flg = false;
      if(i == 2) {
	ans ++;
	continue;
      }
      for(int j = 2; j <= sqrt(i); j ++) {
	if(i%j == 0) {
	  flg = true;
	  break;
	}
      }
      if(!flg) {
	ans ++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
import sys
S = input()
num = len(S)
S = S + "zzzzzzzzzzzzzzzzzzzzzz"
cur = 0
while cur < num:
    if S[cur] == 'd':
        if S[cur:cur+11] == 'dreameraser':
            cur += 11
        elif S[cur:cur+10] == 'dreamerase':
            cur += 10
        elif S[cur:cur+7] == 'dreamer':
            cur += 7
        elif S[cur:cur+5] == 'dream':
            cur += 5
        else:
            print('NO')
            sys.exit()
    elif S[cur] == 'e':
        if S[cur:cur+6] == 'eraser':
            cur += 6
        elif S[cur:cur+5] == 'erase':
            cur += 5
        else:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
    if cur == num:
        print('YES')
        sys.exit()

Measured memory_bytes: 40688
import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))

ans = []
X1 = sum(A) - (2 * A[1::2]).sum()
ans.append(X1)

for i in range(0, n-1):
    ans.append(2*A[i] - ans[-1])

print(" ".join(map(str, ans)))

Measured memory_bytes: 24868
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    
    if ((7+n)%7 == 1) cout << "fri" << endl;
    else if ((7+n)%7 == 2) cout << "sat" <<endl; 
    else if ((7+n)%7 == 3) cout << "sun" << endl;
    else if ((7+n)%7 == 4) cout << "mon" <<endl; 
    else if ((7+n)%7 == 5) cout << "tue" <<endl; 
    else if ((7+n)%7 == 6) cout << "wed" <<endl; 
    else cout << "thu" <<endl; 
}



Measured memory_bytes: 3104