akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

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

    int n, num, max = 0, id;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> num;
        if(abs(max) < abs(num)) max = num, id = i;
    }

    if(max == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    cout << 2*n << endl;
    if(max > 0){
        cout << id << " " << 1 << endl;
        cout << id << " " << 1 << endl;
        for(int i = 2; i <= n; i++){
            cout << i-1 << " " << i << endl;
            cout << i-1 << " " << i << endl;
        }
    }
    else {
        cout << id << " " << n << endl;
        cout << id << " " << n << endl;
        for(int i = n-1; i > 0; i--){
            cout << i+1 << " " << i << endl;
            cout << i+1 << " " << i << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

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

	if (d == 0) {
		cout << fixed << setprecision(9) << (m - 1) / n << endl;
	}
	else {
		cout << fixed << setprecision(9) << ((m - 1) * ((2 * n) - (2 * d)) / (n * n)) << endl;
	}

	return 0;
}

Measured memory_bytes: 764
a = input().split(" ")
h = input().split(" ")
c = {}
for j in range(int(a[0])):
    c[str(j+1)] = [int(h[j]),"good"]
b = []
good = int(a[0])
for i in range(int(a[1])):
    d = input().split()
    x = int(c[d[0]][0])
    y = int(c[d[1]][0])
    if x > y:
        c[d[1]][1] = "bad"
    if y > x:
        c[d[0]][1] = "bad"
    if y == x:
        c[d[1]][1] = "bad"
        c[d[0]][1] = "bad"
kotae = 0
for k in range(int(a[0])):
    if c[str(k+1)][1] == "good":
        kotae += 1
print(kotae)

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

int n, m, x[200][200], cnt[26];
char a[200];
priority_queue<int> pq, use;

int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%s", a);
for(int j = 0; j < m; j++) cnt[a[j] - 'a']++;
}
for(int i = 0; i < 26; i++) pq.push(cnt[i]);
for(int i = 0; i < (n + 1) / 2; i++) for(int j = 0; j < (m + 1) / 2; j++) x[i][j] = 4;
if(n & 1){ for(int j = 0; j < (m + 1) / 2; j++) x[(n - 1) / 2][j] /= 2; }
if(m & 1){ for(int i = 0; i < (n + 1) / 2; i++) x[i][(m - 1) / 2] /= 2; }
for(int i = 0; i < (n + 1) / 2; i++) for(int j = 0; j < (m + 1) / 2; j++) use.push(x[i][j]);
while(!use.empty()){
int t = pq.top(); pq.pop();
if(t < use.top()){ puts("No"); return 0; }
t -= use.top();
use.pop();
pq.push(t);
}
puts("Yes");
}

Measured memory_bytes: 256
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
if a[0]>x:
    ans+=a[0]-x
    a[0]-=a[0]-x
for i in range(n-2):
    if a[i]+a[i+1]>x:
        ans+=a[i]+a[i+1]-x
        a[i+1]-=a[i]+a[i+1]-x
if a[-1]+a[-2]>x:
    ans+=a[-1]+a[-2]-x
print(ans)

Measured memory_bytes: 63856
#include<iostream>
#include<climits>
#include<cmath>
#include<math.h>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int main(){
    int x[5];
    int ans = 0;
    for(int i=0;i<5;i++){
        cin >> x[i];
        if(x[i] == 0){
            ans = i+1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3160
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

class Main {

  static class Solver {
    final FastScanner sc;
    final PrintWriter writer;

    Solver(final FastScanner sc, final PrintWriter writer) {
      this.sc = sc;
      this.writer = writer;
    }

    void run() {
      int s = sc.nextInt();
      int w = sc.nextInt();
      writer.println(s <= w ? "unsafe" : "safe");
    }
  }

  public static void main(final String[] args) {
    final FastScanner sc = new FastScanner();
    try (final PrintWriter w = new PrintWriter(System.out)) {
      new Solver(sc, w).run();
      w.flush();
    }
  }

  // FastScanner
  static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner() {
    }

    private boolean hasNextByte() {
      if (ptr < buflen) {
        return true;
      } else {
        ptr = 0;
        try {
          buflen = in.read(buffer);
        } catch (final IOException e) {
          e.printStackTrace();
        }
        if (buflen <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte())
        return buffer[ptr++];
      else
        return -1;
    }

    private boolean isPrintableChar(final int c) {
      return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr]))
        ptr++;
      return hasNextByte();
    }

    public String next() {
      if (!hasNext())
        throw new NoSuchElementException();
      final StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    public long nextLong() {
      if (!hasNext())
        throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    public int nextInt() {
      final long nl = nextLong();
      if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
        throw new NumberFormatException();
      return (int) nl;
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(final int n) {
      final int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(final int n) {
      final long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }
}

Measured memory_bytes: 32576
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int X = sc.nextInt();
		int[] L = new int[N];
		for(int i = 0; i < N; i++)
			L[i] = sc.nextInt();
		int d = 0, ans = 1;
		for(int i = 0; i < N; i++){
			d += L[i];
			if(d > X)
				break;
			ans++;
		}
		System.out.println(ans);

	}

}

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


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

    int n;
    cin >> n;
    if (n) cout << 0 << endl;
    else cout << 1 << endl;
    return 0;
}

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

int main() {

	int N, M;
	int a[200020], b[200020], root[200020];
	int count1 = 0, countN = 0;
	bool check = false;

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {

		root[i] = 0;

	}
	for (int i = 1; i <= M; i++) {

		cin >> a[i] >> b[i];
		if (a[i] == 1) {

			root[b[i]] = 1;

		}

	}

	for (int i = 1; i <= M; i++) {

		if (b[i] == N) {

			if (root[a[i]] == 1) {

				check = true;
				break;

			}

		}

	}

	if (check)cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;

	return 0;
}

Measured memory_bytes: 2560
a,b,c = map(int,input().split())
res = 0
while a%2==0 and b%2==0 and c%2==0: # 値が偶数の間
    if a==b==c: #無限ループ
        print(-1)
        exit()
    tmpa = b//2+c//2
    tmpb = a//2+c//2
    tmpc = a//2+b//2
    a = tmpa
    b = tmpb
    c = tmpc
    res += 1
print(res)

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 100000;
const int MAX_M = 100000;
const int MOD = 1000000007;

int N, M, X[MAX_N], Y[MAX_M];

signed main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> X[i];
	}
	for (int i = 0; i < M; i++)
	{
		cin >> Y[i];
	}
	int sum = 0;
	for (int i = 0; i < N - 1; i++)
	{
		(sum += (X[i + 1] - X[i])*(i + 1)%MOD*(N - 1 - i)) %= MOD;
	}
	int ans = 0;
	for (int i = 0; i < M - 1; i++)
	{
		(ans += sum*(Y[i + 1] - Y[i])%MOD*(i + 1)%MOD*(M - 1 - i)) %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define INF 100000000000
#define MAX 200001
#define MOD 1000000007  

int main(){
    int N;
    ll ans = 0;
    cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    N -= 2;
    int now = 1;
    ans += A[0];
    while(N > 0){
        if(N == 1){
            ans += A[now];
            N = 0;
        }
        else{
            ans += A[now] * 2;
            N -= 2;
        }
        now++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4836
#include<cstdio>
#include<queue>
#define O 2002
#define MOD 1000000007
#define R 2000
int n;
int grid[4005][4005];
int dy[4005][4005];
int comb[8005][4005];
int my_pow(long long val, int exp) {
	long long ex = val;
	val = 1;
	while (exp > 0) {
		if (exp % 2 == 1) {
			val *= ex;
			val %= MOD;
		}
		ex = ex * ex%MOD;
		exp /= 2;
	}
	return val;
}
int main() {
	scanf("%d", &n);
	int i,j;
	comb[0][0] = 1;
	for (i = 1; i <= 8000; i++) {
		comb[i][0] = 1;
		for (j = 1; j <= i && j<=4000; j++) {
			comb[i][j] = comb[i-1][j - 1] + comb[i-1][j];
			comb[i][j] %= MOD;
		}
	}
	int ans = 0;
	for (i = 1; i <= n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		grid[O + a][O + b]++;
		grid[O - a][O - b]++;
		if (a > b) {
			int temp = a; a = b; b = temp;
		}
		ans -= comb[a * 2 + b * 2][a * 2];
		if (ans < 0) ans += MOD;
	}
	for (i = O - R; i <= O + R; i++) {
		for (j = O - R; j <= O + R; j++) {
			if (i < O && j < O) {
				dy[i][j] += grid[i][j];
			}
			dy[i][j] += dy[i - 1][j];
			dy[i][j] %= MOD;
			dy[i][j] += dy[i][j - 1];
			dy[i][j] %= MOD;
			if (i > O && j > O) {
				ans += (long long)dy[i][j] * grid[i][j] % MOD;
				ans %= MOD;
			}
		}
	}
	int divied = my_pow(2, MOD - 2);
	ans = (long long)ans*divied % MOD;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 249088
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> r(n+1);
  vector<int> g(n+1);
  vector<int> b(n+1);
  for(int i=n-1; i>=0; i--){
    r[i]=r[i+1];
    g[i]=g[i+1];
    b[i]=b[i+1];
    if(s[i]=='R'){
      r[i]++;
    } else if(s[i]=='G'){
      g[i]++;
    } else {
      b[i]++;
    }
  }
  ll ans=0;
  rep(i, n){
    for(int j=i+1; j<n; j++){
      if((s[i]=='R'&&s[j]=='G')||(s[i]=='G'&&s[j]=='R')){
        ans+=b[j+1];
        if(2*j-i<n && s[2*j-i]=='B'){
          ans--;
        }
      } else if((s[i]=='G'&&s[j]=='B')||(s[i]=='B'&&s[j]=='G')){
        ans+=r[j+1];
        if(2*j-i<n && s[2*j-i]=='R'){
          ans--;
        }
      } else if((s[i]=='B'&&s[j]=='R')||(s[i]=='R'&&s[j]=='B')){
        ans+=g[j+1];
        if(2*j-i<n && s[2*j-i]=='G'){
          ans--;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3616
#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Max zhi5968
typedef long long ll;
using namespace std;

int main ()
{
	int a,b;
	cin>>a>>b;
	cout<<2*b-a<<endl; 
	return 0;
}

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

using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
int N;	
string s;
int main(){
	cin>>N;
	int f;
	map<string,int> mp=
	{
		{"Vacant",0},
			{"Male",1},
				{"Female",2}
	};
	cout<<0<<endl;
	cin>>s;
	f=mp[s];
	if (!f){
		return 0;
	}
	int lb=0,ub=N+1;
	while(1){
		int mid=(lb+ub)>>1;
		cout<<mid<<endl;
		cin>>s;
		int a=mp[s];
		if (!a){
			return 0;
		}
		if ((a==f) ^ ((mid-lb)%2)){
			lb=mid;
			f=a;
		}else{
			ub=mid;
		}
	}
	return 0;
}

Measured memory_bytes: 852
import sys
sys.setrecursionlimit(10 ** 4)
from fractions import gcd

num = [10**9, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = [[""]*(n+1) for _ in range(len(a))]
    dp[0][num[a[0]]] = str(a[0])
    for i in range(num[a[0]], n+1):
        if len(dp[0][i-num[a[0]]]) > 0:
            dp[0][i] = dp[0][i-num[a[0]]] + str(a[0])
    for i in range(1, len(a)):
        for j in range(n+1):
            if j < num[a[i]]:
                dp[i][j] = dp[i-1][j]
            else:
                if j == num[a[i]] or dp[i][j-num[a[i]]] != "":
                    buf = dp[i][j-num[a[i]]] + str(a[i])
                    if len(buf) < len(dp[i-1][j]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = buf
                else:
                    dp[i][j] = dp[i-1][j]
    ans = list(dp[len(a)-1][n])
    ans.sort(reverse=True)
    print("".join(ans))

if __name__ == "__main__":
    main()

Measured memory_bytes: 69340
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const int maxm = 1e6 + 5;
const double eps = 1e-8;
const double pi = acos(-1.0);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a * b / gcd(a,b);}
ll poww(ll x,ll y,ll p){ll ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans % p;}
bool isp(ll x){if(x < 2) return 0; for(ll i = 2;i * i <= x;i++){if(x % i == 0) return 0;}return 1;}
int a,b,c;
int main(){
// 	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> a >> b >> c;
	if(a+b+c>=22) puts("bust");
	else puts("win");
	return 0;
}
//do smt instead of nothing! never give up!
//take care of long long!
//take care of upper or lower case e.g "yes" or "YES"?
//boundary condition! e.g. n = 0?
//brute force is always the first choice!
// print the ans to look for patterns in the data!

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
//BIAR MANTAB LAH YA
#define Willy using
#define Indrayana namespace
#define Komara std
 
Willy Indrayana Komara;

bool besarDulu(const int &a, const int &b)
{
    return a > b;
}

bool tupleSort(tuple<int, int, int> &a, tuple<int, int, int> &b)
{
    return get<2>(a) > get<2>(b);
}

using ll = long long int;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll h, w;
    cin >> h >> w;
    if (h == 1 || w == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    cout << (ll) ceil((double)(h * w) / 2) << endl;
    return 0;
}
//500000000000000000
//500000000000000000

Measured memory_bytes: 256
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	S, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	h := S / 3600
	m := S % 3600
	s := m % 60
	m /= 60

	fmt.Printf("%d:%d:%d\n", h, m, s)
}



Measured memory_bytes: 1112
n=int(input())
txy=[[int(i) for i in input().split()] for _ in range(n)]
ans='Yes'
for t,x,y in txy:
    if (x+y)%2!=t%2:
        ans='No'
        break
    if x+y>t:
        ans='No'
        break
print(ans)

Measured memory_bytes: 21156
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())

names = []
num = []

for i in range(N):
	s = input()
	if not s in names:
		names.append(s)
		num.append(1)
	else:
		ind = names.index(s)
		num[ind] += 1

M = int(input())

for i in range(M):
	s = input()
	if not s in names:
		names.append(s)
		num.append(-1)
	else:
		ind = names.index(s)
		num[ind] -= 1

print(max(max(num),0))


Measured memory_bytes: 4204
#include<iostream>
#include <string.h>
#include<stdio.h>
#include <math.h>

using namespace std;

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

	long long int ans;

	ans = N % K;
	if (K - ans <= ans) ans = K - ans;

	cout << ans;
	
return 0;
}


Measured memory_bytes: 256
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
xy = map(int, read().split())
XY = zip(xy, xy)

max_num = 10 ** 5
delta = 10 ** 5 + 10

graph = [[] for _ in range(max_num + delta + 1)]

for x, y in XY:
    graph[x].append(delta + y)
    graph[delta + y].append(x)

x_used = [False] * (max_num + 1)
y_used = [False] * (max_num + 1)


def dfs(idx):
    x_res = 0
    y_res = 0
    edgenum = 0
    stack = []
    stack.append(idx)
    if idx >= delta:
        y_used[idx % delta] = True
    else:
        x_used[idx] = True
    while stack:
        v = stack.pop()
        if v >= delta:
            # if y_used[v % delta]:
            #     continue
            # y_used[v % delta] = True
            y_res += 1
        else:
            # if x_used[v]:
            #     continue
            # x_used[v] = True
            x_res += 1
        for u in graph[v]:
            if u >= delta:
                if y_used[u % delta]:
                    continue
                y_used[u % delta] = True
            else:
                if x_used[u]:
                    continue
                x_used[u] = True
            edgenum += 1
            stack.append(u)
    res = x_res * y_res
    return res


ans = 0
for i in range(max_num + 1):
    if x_used[i]:
        continue
    temp = dfs(i)
    ans += temp

for i in range(max_num + 1):
    if y_used[i]:
        continue
    i += delta
    temp = dfs(i)
    ans += temp

print(ans - n)


Measured memory_bytes: 43828
from itertools import accumulate
import sys

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

for cnt in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]
    if cnt > 40:
        arr = [n] * n
        print(*arr)
        sys.exit()

print(*arr)

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

using namespace std;

int n;
string str;
int val[2000010][3], ch[2000010][3], tot = 1;
bool laz[2000010];

void build()
{
	for (int i = 1; i <= n + 1; i++) tot *= 3;
	tot = (tot - 1) / 2;
	for (int i = 1; i <= tot; i++)
		if (i * 3 <= tot)
		{
			ch[i][0] = i * 3 - 1, ch[i][1] = i * 3, ch[i][2] = i * 3 + 1;
			val[i][0] = 0, val[i][1] = 1, val[i][2] = 2;
			laz[i] = 0;
		}
}

void pushdown(int p)
{
	if (laz[p])
	{
		int a, b;
		for (int i = 0; i < 3; i++)
		{
			if (val[p][i] == 1) a = i;
			if (val[p][i] == 2) b = i;
		}
		swap(val[p][a], val[p][b]);
		for (int i = 0; i < 3; i++)
			laz[ch[p][i]] ^= 1;
		laz[p] = 0;
	}
}

void add(int p)
{
	if (p * 3 > tot) return;
	pushdown(p);
	int pos = 0;
	for (int i = 0; i < 3; i++)
	{
		val[p][i]++;
		if (val[p][i] == 3)
		{
			val[p][i] = 0;
			pos = ch[p][i];
		}
	}
	add(pos);
}

int arr[2000010], cnt;
int rev[2000010];

void dfs(int p, int cur, int v)
{
	if (p * 3 > tot)
	{
		arr[cnt++] = cur;
		return;
	}
	pushdown(p); 
	for (int i = 0; i < 3; i++)
		dfs(ch[p][i], cur + v * val[p][i], v * 3);
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> str;
	build();
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == 'R') add(1);
		else laz[1] ^= 1;
	}
	dfs(1, 0, 1);
	for (int i = 1; i < cnt; i++)
		rev[i] = rev[i / 3] / 3 + (cnt / 3) * (i % 3);
	for (int i = 0; i < cnt; i++)
		if (i < rev[i])
			swap(arr[i], arr[rev[i]]);
	for (int i = 0; i < cnt; i++)
		cout << arr[i] << ' ';
	cout << endl; 
	return 0;
}


Measured memory_bytes: 15620
import java.util.Scanner;


public class Main{
    public  static void main(String[] args) {
    	try (Scanner sc = new Scanner(System.in)) {
    		String str=sc.next();
    		int turn=0;
    		for(int i=0; i<str.length(); i++) {
    			if(str.charAt(i)=='1') {
    				turn++;
    			}
    		}
    		System.out.println(turn);
    	}
    }
}

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

template<class T> struct BinaryIndexedTree {
private : 
    vector<T> data;
public :
    BinaryIndexedTree(int n) : data(n+1, 0) { }

    T get(int i) {
        T ret = 0;
        for (; i >= 0; i = (i&(i+1))-1) ret += data[i];
        return ret;
    }

    void add (int i, T x) {
        for (; i < data.size(); i |= (i+1)) data[i] += x;
    }

};

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n), s(n+1, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= k;
        s[i+1] = s[i] + a[i];
    }
    
    vector<long long> v = s;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i <= n; i++) {
        s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin();
    }
    
    long long ans = 0;
    BinaryIndexedTree<long long> bit(n+5);
    for (int i = 0; i <= n; i++) {
        ans += bit.get(s[i]);
        bit.add(s[i], 1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

ll f(ll x){
    ll tmp = 0;
    if((x/2)%2 == 1)    tmp = 1;
    if(x%2 == 1)    tmp ^= 1;
    else            tmp ^= x;
    return tmp;
}

int main(){
    ll a, b;    cin>>a>>b;
    ll ans = (a==0)?f(b):f(b)^f(a-1);
    cout << ans << endl;
}


Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template<int Modulo = MOD> struct Mint {
	Int val;
	constexpr Mint(Int v = 0) noexcept : val(v% Modulo) {
		if (val < 0) v += Modulo;
	}
	constexpr int getmod() { return Modulo; }
	constexpr Mint operator - () const noexcept { return val ? Modulo - val : 0; }
	constexpr Mint operator + (const Mint& r) const noexcept { return Mint(*this) += r; }
	constexpr Mint operator - (const Mint& r) const noexcept { return Mint(*this) -= r; }
	constexpr Mint operator * (const Mint& r) const noexcept { return Mint(*this) *= r; }
	constexpr Mint operator / (const Mint& r) const noexcept { return Mint(*this) /= r; }
	constexpr Mint& operator += (const Mint& r) noexcept {
		val += r.val;
		if (val >= Modulo) val -= Modulo;
		return *this;
	}
	constexpr Mint& operator -= (const Mint& r) noexcept {
		val -= r.val;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr Mint& operator *= (const Mint& r) noexcept {
		val = val * r.val % Modulo;
		return *this;
	}
	constexpr Mint& operator /= (const Mint& r) noexcept {
		Int a = r.val, b = Modulo, u = 1, v = 0;
		while (b) {
			Int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % Modulo;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr bool operator == (const Mint& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const Mint& r) const noexcept {
		return this->val != r.val;
	}
	friend ostream& operator << (ostream& os, const Mint<Modulo>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream& is, Mint<Modulo>& x) noexcept {
		Int tmp; is >> tmp;
		x = Mint<Modulo>(tmp);
		return is;
	}
	friend constexpr Mint<Modulo> modpow(const Mint<Modulo>& a, Int n) noexcept {
		Mint res(1), tmp = a;
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};

using mint = Mint<>;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	vector<Int> h(N + 1);
	for (Int i = 0; i < N; i++) {
		cin >> h[i];
	}

	vector<Int> dp(N + 1, INF);
	dp[0] = 0;

	for (Int i = 0; i < N-1; i++) {
		dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
		dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
	}

	cout << dp[N - 1] << "\n";

}

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


#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <functional>
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


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

	string s;
	cin >> s;

	bool f = true;
	rep(i, s.size()) {
		repr(j,i+1, s.size()) {
			if (s[i] == s[j]) f = false;
		}
	}

	if (f) {
		cout << "yes" << endl;
	}
	else {
		cout << "no" << endl;
	}

	return 0;
}

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

using namespace std;

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

    double p = pow(0.5, (double)M);
    int ans = (1900.0 * M + 100.0 * (N - M)) / p;
    cout << ans << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 4064
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <queue>
#define ll long long
#define INF (1000000000000)
#define NIL (-1)
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  ll h,w;
  cin >> h >> w;
  string s;
  ll ans1, ans2;
  for(ll i = 0; i < h; i++){
    for(ll k = 0; k < w; k++){
      cin >> s;
      if(s == "snuke"){
	ans1 = i;
	ans2 = k;
      }
    }
  }
  cout << (char)('A' + ans2) << ans1+1 <<  endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

bool check(int a, int b){
	return abs(a - b) <= 1;
}

int main(){
    int n;
    while(cin >> n,n){
        vector<int> w(n);
        rep(i,n){
            cin >> w[i];
        }

		int dp[300][300] = {{0}};
		range(W,2,n + 1){
			rep(i,n){
				int j = i + W - 1;
				if(i + W - 1 >= 300) break;
				if(check(w[i], w[j]) && dp[i + 1][j - 1] == W - 2){
					dp[i][j] = W;
				}
				range(k,i,j){
					dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
				}
			}
		}
		cout << dp[0][n - 1] << endl;
    }
}

Measured memory_bytes: 3448
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,y,p;
    scanf("%d",&n);
    x = n/500;
    x*=(2*500);
    p = n%500;
    y = p/5;
    y*=5;
    printf("%d\n",y+x);
    return 0;
}


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

int main() {
    ll n, a[100] = {0}; cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    ll money = 1000;
    for(int i=0; i<n; i++) {
        ll cnt = 0;
        if(a[i] < a[i + 1]) cnt = money / a[i];
        money += cnt * (a[i + 1] - a[i]);
    }
    cout << money << endl;
}

Measured memory_bytes: 3596
//  Created by conan1024hao on 2019/11/23.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>P;
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cmp(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//---------------------------------------------------------------------------
vector<int> g[100005];
int dfs(int s,int q){
    int k=0;
    for(int r=0;r<g[s].size();r++){
        if(g[s][r]!=q)
            k^=(1+dfs(g[s][r],s));
    }
    return k;
}
//---------------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if(dfs(0,-1))
        cout<<"Alice"<<endl;
    else
        cout<<"Bob"<<endl;
//-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


Measured memory_bytes: 9216
<?php

$s = trim(fgets(STDIN));
$t = trim(fgets(STDIN));
$c = 0;
if(substr($s, 0, 1) == substr($t, 0, 1)) $c++;
if(substr($s, 1, 1) == substr($t, 1, 1)) $c++;
if(substr($s, 2, 1) == substr($t, 2, 1)) $c++;
echo $c. "\n";

Measured memory_bytes: 4728
def check(learn_total):
  for i in range(m):
    if learn_total[i] < x:
      return False
  return True

def calc_price(bit):
  price_total = 0
  learn_total = [0] * m 

  for i in range(n):
    if (bit >> i) & 1:  
      price_total += c[i]  
      learn = a[i]  
      for j, la in enumerate(learn):
        learn_total[j] += la

  if check(learn_total):
    return price_total
  else:
    return INF 
  
  
if __name__ == '__main__':
  n, m, x = list(map(int, input().split()))
  c = []
  a = [] 

  for i in range(n):
    c_temp, *a_temp = list(map(int, input().split()))
    c.append(c_temp)
    a.append(a_temp)

  INF = float("inf")
  ans = INF

  for bit in range(1 << n):
    price = calc_price(bit)
    ans = min(ans, price) 

  if ans == INF:
    print(-1) 
  else:
    print(ans)

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using VI = vector<int>;
using VVI = vector<VI>;
lint digit_sum(lint n, lint base = 10) {
  lint res = 0;
  while (n) {
    res += n % base;
    n /= base;
  }
  return res;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int k; cin >> k;
  lint n = 1, d = 1;
  for (int i = 0; i < k; i++) {
    cout << n << '\n';
    if ((n + d) * digit_sum(n + d * 10) > (n + d * 10) * digit_sum(n + d)) {
      d *= 10;
    }
    n += d;
  }
  return 0;
}

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

int main() {
	int n,k,d,a;
	cin >> n >> k;
	vector<int> s(n,0);
	for(int i=0;i<k;i++)
	{
		cin >> d;
		for(int j=0;j<d;j++)
		{
			cin >> a;
			s.at(a-1)++;
		}
	}
	int c=0;
	for(int i=0;i<n;i++)
	{
		if(s.at(i) == 0)
		{
			c++;
		}
	}
	cout << c;
	return 0;
}


Measured memory_bytes: 3632
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=1e5+1e3+7;

int n,a[N],val;

int ab(int x)
{
	return x<0?-x:x;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int k=a[n];
	double v=(double)k/2;
	val=a[n];
	int ans=0;
	for(int i=1;i<=n;i++)
		if(abs((double)a[i]-v)<val)
			ans=a[i],val=abs((double)a[i]-v);
	printf("%d %d",a[n],ans);
}

Measured memory_bytes: 640
#include <assert.h>
#include <stdio.h>
typedef long long int lld;

void table(int prev[], int new[]) {
  for (int i = 0; i <= 9; i++) {
    if (prev == NULL) {
      new[i] = 1;
    } else {
      new[i] = 0;
      for (int j = -1; j <= 1; j++) {
        if (i + j < 0 || i + j > 9) {
          continue;
        }
        new[i] += prev[i + j];
      }
    }
  }
}

int main() {
  int k;
  assert(scanf("%d", &k) == 1);

  int cnt[20][10], last;
  lld tmp = k - 1;
  for (int i = 0; i < 20; i++) {
    table(i > 0 ? cnt[i - 1] : NULL, cnt[i]);
    for (int j = 1; j <= 9; j++) {
      if (tmp >= cnt[i][j]) {
        tmp -= cnt[i][j];
      } else {
        last = j;
        printf("%d", last);
        for (int l = i - 1; l >= 0; l--) {
          for (int m = -1; m <= 1; m++) {
            if (last + m < 0 || last + m > 9) {
              continue;
            }
            if (tmp >= cnt[l][last + m]) {
              tmp -= cnt[l][last + m];
            } else {
              last = last + m;
              printf("%d", last);
              break;
            }
          }
        }
        j = 10;
        i = 20;
      }
    }
  }
  puts("");
}


Measured memory_bytes: 128
#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
/*#if !defined(YCM) && 0
#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx,tune=native")
#include <stdio.h>
#endif*/
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(bool);
void precalc();
clock_t start;
int main() {
#ifdef AIM
    freopen("/home/alexandero/ClionProjects/ACM/input.txt", "r", stdin);
    //freopen("/home/alexandero/ClionProjects/ACM/output.txt", "w", stdout);
    //freopen("out.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
    cout.sync_with_stdio(0);
    cin.tie(0);
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cout << "Case #" << testNum++ << ": ";
        //cerr << testNum << endl;
        solve(true);
        //cerr << testNum - 1 << endl;
    }
    cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
    cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

    return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {}

//#define int li
//const int mod = 1000000007;

const int INF = (int)2e9 + 100;

void solve(bool read) {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(all(a), [&](const pair<int, int>& q, const pair<int, int>& w) {
        return q.first + q.second < w.first + w.second;
    });
    vector<vector<int>> dp(2, vector<int>(n + 1, INF));
    int par = 0;
    dp[par][0] = 0;
    for (int pos = 0; pos < n; ++pos) {
        dp[par ^ 1] = dp[par];
        for (int used = 0; used <= pos; ++used) {
            if (a[pos].first >= dp[par][used]) {
                relax_min(dp[par ^ 1][used + 1], dp[par][used] + a[pos].second);
            }
        }
        par ^= 1;
    }

    for (int used = n; used >= 0; --used) {
        if (dp[par][used] < INF) {
            cout << used << endl;
            return;
        }
    }

}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll  long long int
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define pb push_back
#define Max(x,y,z) max(x,max(y,z))
#define f first
#define s second
#define lbd lower_bound
#define sz(x)       (ll)x.size()
#define pi 3.1415926536
#define mod 1000000007
using namespace std;
/*const int inf=1e9+5;
ll n,k,y,x;
const int N = 1e5+5;*/
/*bool vis[N];
ll a[N];*/
/*bool sortinrev(const pair<ll,ll> &a,
               const pair<ll,ll> &b)
{
     return (a.f>b.f);
}*/
void solve()
{   ll n,m,res=0,l,r,cnt0=0,z,sum1=0,cnt1=0,h,res1,ans=0,sum=0,cnt=0;
    cin>>n;
    ll ar[n];
    rep(i,0,n) cin>>ar[i];
    rep(i,1,n-1)
    {
        if((ar[i]>ar[i+1] && ar[i]<ar[i-1]) || (ar[i]<ar[i+1] && ar[i]>ar[i-1]))
            cnt++;
    }
    cout<<cnt;


}
int main()
{   speed_up
    ll t;
   //cin>>t;
    t=1;
    while(t--)
        solve();

}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    double count = 0;
    double output;
    int num;
    scanf("%d",&num);
    for(int i = 1; i <= num; i++){
        if(i%2==1){
            count++;
        }
    }
    output = count/num;
    printf("%f\n",output);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<int(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
typedef int Weight;
Weight INF = 1000000000;

struct Edge{
  int src, dest;
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest) {
  g[src].push_back((Edge){src, dest});
}

struct Recipe {
  int g;
  vector<int> s;
};

Weight weight(Recipe r, Array& ary) {
  vector<int> vs;
  for(int s:r.s) {
    vs.emplace_back(ary[s]);
  }
  sort(ALL(vs),greater<int>());
  int mx = 0;
  REP(i,vs.size()) {
    mx = max(mx, vs[i] + i);
  }
  return mx;
}

int main() {
  int n,e,t;
  cin>>n>>e>>t;
  --t;
  queue<int> que;
  Array d(n, INF);
  Graph graph(n);
  REP(i,n) {
    que.push(i);
    int w;
    cin>>w;
    if(w) d[i] = 1;
  }
  vector<vector<Recipe>> gr(n);
  REP(i,e) {
    Recipe r;
    int c;
    cin>>r.g>>c;
    --r.g;
    REP(j,c) {
      int s;
      cin>>s;
      --s;
      add_edge(graph, s, r.g);
      r.s.push_back(s);
    }
    gr[r.g].push_back(r);
  }
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    bool update = false;
    for (auto r : gr[v]) {
      if (weight(r, d) < d[v]) {
        d[v] = weight(r, d);
        update = true;
      }
    }
    if (update) {
      REP(i, graph[v].size()) {
        que.push(graph[v][i].dest);
      }
    }
  }
  if (d[t] < INF) {
    cout << d[t] << endl;
  } else {
    cout << -1 << endl;
  }
  return 0;
}

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

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
// #define int long long

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

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define eprintf(...) 42
#define dump(x) 42
#define debug(x) 42
#endif

typedef long long ll;

const ll MOD = 1e9 + 7;

void solve(int n, vector<int>& p) {
    int answer = 0;
    REP(i,1,n-1) {
        if ((p[i-1] < p[i] && p[i] <= p[i+1]) || (p[i+1] < p[i] && p[i] <= p[i-1])) answer++;
    }

	stringstream ss;
    ss << answer;
	cout << ss.str() << '\n';

    return;
}

signed main() {
    int N;
    cin >> N;
    
    vector<int> A(N);
    REP(i,0,N) cin >> A[i];
    
    solve(N, A);
    
    return 0;
}



Measured memory_bytes: 256
// Author:: MOHAMMAD FAISAL
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin >> s;
  if(s=="MON")
    cout<<"6";
  else if(s=="TUE")
    cout<<"5";
  else if(s=="WED")
    cout<<"4";
  else if(s=="THU")
    cout<<"3";
  else if(s=="FRI")
    cout<<"2";
  else if(s=="SAT")
    cout<<"1";
  else
    cout<<"7";
 return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>

struct Rectangle {
  size_t l, r, d, u;
  std::string name;
  int children=0;
  Rectangle(size_t l, size_t r, size_t d, size_t u, const std::string &name):
    l(l), r(r), d(d), u(u), name(name)
  {}
  bool contains(size_t x, size_t y) const {
    return x-l <= r-l && y-u <= d-u;
  }
};

std::vector<Rectangle> parse(const std::string &s) {
  std::map<std::string, int> children;
  std::stack<std::string> opened;
  std::vector<Rectangle> res;
  size_t i=0;
  while (i < s.length()) {
    assert(s[i] == '<');
    ++i;
    if (s[i] == '/') {
      while (s[i++] != '>') {}
      opened.pop();
      continue;
    }
    std::string tag(1, s[i]);
    while (isalnum(s[++i])) tag += s[i];
    assert(s[i] == '>');
    ++i;
    assert(isdigit(s[i]));
    size_t l=s[i]-'0';
    while (isdigit(s[++i])) l = l*10+s[i]-'0';
    assert(s[i] == ',');
    ++i;
    assert(isdigit(s[i]));
    size_t u=s[i]-'0';
    while (isdigit(s[++i])) u = u*10+s[i]-'0';
    assert(s[i] == ',');
    ++i;
    assert(isdigit(s[i]));
    size_t r=s[i]-'0';
    while (isdigit(s[++i])) r = r*10+s[i]-'0';
    assert(s[i] == ',');
    ++i;
    assert(isdigit(s[i]));
    size_t d=s[i]-'0';
    while (isdigit(s[++i])) d = d*10+s[i]-'0';
    assert(s[i] == '<');

    res.emplace_back(l, r, d, u, tag);
    if (!opened.empty())
      ++children[opened.top()];

    opened.emplace(tag);
  }
  assert(opened.empty());

  for (size_t i=0; i<res.size(); ++i) {
    res[i].children = children[res[i].name];
  }
  return res;
}

int testcase_ends() {
  size_t n;
  char buf[1024];
  scanf("%zu %s", &n, buf);
  if (n == 0) return 1;
  std::string s=buf;
  std::vector<Rectangle> rects=parse(s);

  for (size_t i=0; i<n; ++i) {
    size_t x, y;
    scanf("%zu %zu", &x, &y);

    size_t ind=-1;
    for (size_t j=0; j<rects.size(); ++j) {
      if (rects[j].contains(x, y))
        ind = j;
    }

    if (ind+1 == 0) {
      printf("OUT OF MAIN PANEL 1\n");
    } else {
      printf("%s %d\n", rects[ind].name.c_str(), rects[ind].children);
    }
  }
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2872
#include <iostream>
#include <stdio.h>
#include <algorithm> 

using namespace std;

const int MAX_N = 45 * 2 + 4;
const int MAX_V = 10 + 4;
const int INF = 0x3f3f3f3f;

int n;
int v;
struct Edge {
    int from;
    int to;
    int cost;
} edge[MAX_N];

int d[MAX_V];

int Bellman_Ford (int s) {
    int res = 0;
    fill(d, d + MAX_V, INF);
    d[s] = 0;
    while (true) {
        bool update = false;
        for (int i = 0; i < 2 * n; i++) {
            Edge e = edge[i];
            if (d[e.from] != INF && d[e.from] + e.cost < d[e.to]) {
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if (!update) {
            break;
        }        
    }
    for (int i = 0; i <= v; i++) {
        res += d[i];
    }
    return res;
}

int main() {
    while (scanf("%d", &n) && n > 0) {
        int path[MAX_V];                           
        v = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].cost);
            edge[i + n].from = edge[i].to;
            edge[i + n].to = edge[i].from;
            edge[i + n].cost = edge[i].cost;
            v = max(v, edge[i].from);
            v = max(v, edge[i].to);
        }

        for (int i = 0; i <= v; i++) {
            path[i] = Bellman_Ford(i);
        }
        printf("%d %d\n", min_element(path, path + v + 1) - path, *min_element(path, path + v + 1));
    }
    return 0;    
}

Measured memory_bytes: 3136
object Main extends App {
    val in = io.Source.stdin.getLines.map(_.split(" ").map(_.toInt))
    for (Array(n, r) <- in if n > 0 && r > 0) {
        val m = in.take(r).foldRight(0)((r, i) =>
            if (i >= r(0) - 1 + r(1)) i
            else if (i >= r(1)) i - r(1)
            else i + r(0) - 1 
        )
        println(n - m)
    }
}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int n;
    int a,b;
    int m;
    int h[100003];

    Scd3(n,a,b);
    Rep(i,n){
        Scd(m);
        h[i] = m;
    }

    sort(h,h+n);

    ll from = 0;
    ll to = 1000000000;
    ll tmp;
    ll left = 0;

    while( to - from != 1 ){
        tmp = ( from + to ) / 2;
        left = 0;
        Rep(i,n){
            left += ( max<ll>( 0 , h[i] - b*tmp ) + a - b - 1 ) / ( a - b );
        }
        if( tmp >= left ){
            to = tmp;
        }else{
            from = tmp;
        }
    }



    printf ("%lld\n", to);

    return 0;
}



Measured memory_bytes: 640