akhauriyash/Code-Regression huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
	

N, M = MAP()

language = [[] for _ in range(M)]
for i in range(N):
	K, *L = LIST()
	for l in L:
		language[l-1].append(i)

tree = UnionFind(N)
for x in language:
	if 2 <= len(x):
		tmp = x[0]
		for n in x[1:]:
			tree.union(tmp, n)
			tmp = n

if tree.group_count() == 1:
	print("YES")
else:
	print("NO")

Measured memory_bytes: 22452
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Collections;

public class Main {
	public static long MOD = 1000000007;

	// calcurate n^k
	public static long pow(long n, long k) {
		long ans = 1;
		long tmp = n;
		while(true) {
			if(k==0) {
				return ans;
			}
			if(k % 2 == 1) {
				ans = (ans * tmp) % MOD;
			}
			tmp = (tmp * tmp) % MOD;
			k /= 2;
		}
	}

	public static ArrayList<Integer> divisors(int n) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i=1; i*i <= n; i++) {
			if(n % i == 0) {
				list.add(i);
				if(i != n/i) list.add(n/i);
			}
		}
		Collections.sort(list);
		return list;
	}

	public static void main(String[] args) {
		FS r = new FS();
		int N = r.nextInt();
		int K = r.nextInt();
		ArrayList<Integer> divisor = divisors(N);
		long[] num = new long[divisor.size()];
		long tmpSum = 0;
		for(int i=0; i<divisor.size(); i++) {
			num[i] = pow(K, (divisor.get(i)+1)/2);
			for(int j=0; j<i; j++) {
				if(divisor.get(i) % divisor.get(j) == 0) {
					num[i] -= num[j];
				}
			}
			while(num[i]<0) num[i] += MOD;
			tmpSum += num[i];
			tmpSum %= MOD;
		}
		long ans = 0;
		for(int i=0; i<divisor.size(); i++) {
			if(num[i]<0) num[i] += MOD;
			num[i] = num[i] % MOD;
		}
		for(int i=0; i<divisor.size(); i++) {
			long d = (long)divisor.get(i);
			if(d%2==0) ans += num[i]*d/2;
			else ans += num[i]*d;
			ans = ans % MOD;
		}
		System.out.println(ans);
	}

	// Read Class
	static class FS {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() { return hasNextByte() ? buffer[ptr++] : -1;}
		private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
		private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}

		public boolean hasNext() { skipUnprintable(); return hasNextByte();}
		public String next() {
			if (!hasNext()) throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while(isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
		public int nextInt() {
			return (int)nextLong();
		}
		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();
			}
		}
	}
}


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

int main()
{
  int n;
  cin >> n;
  map<string, int> mp;
  for(int i = 0; i < n; i++){
    string s;
    cin >> s;
    if(mp.find(s) == mp.end()){
      mp[s] = 1;
    }
  }
  int count = 0;
  for(auto p : mp){
    count++;
  }
  cout << count << endl;
  return 0;
}

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

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

    long long a[N+1];
    a[0] = 0;
    for(long long i = 1; i <= N; i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
    }

    long long DP[N+1][N+1];
    for(long long i = 1; i <= N; i++) DP[i][i] = 0;

    for(long long l = 2; l <= N; l++)
    {
        for(long long i = 1; i+l-1 <= N; i++)
        {
            long long j = i+l-1;
            DP[i][j] = 4000000000000000000;
            for(long long k = i; k < j; k++)
                DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j]);
            DP[i][j] += a[j] - a[i-1];
        }
    }
    cout << DP[1][N] << '\n';
    return 0;
}


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

using namespace std;
using ll = long long;
int main(){
    ll a,b,c,d,p,q;
    cin >> a >> b >> c >> d;
    p = max(a*c,a*d);
    q = max(b*c,b*d);
    cout << max(p,q) << endl;
}

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

ll ext_gcd(ll a, ll b, ll &x, ll &y){
	if(b==0){
		x = 1;
		y = 0;
		return a;
	}
	
	ll d = ext_gcd(b, a%b, y, x);
	y -= a/b * x;
	return d;
}

ll mod_inv(ll a, ll m){
	ll x,y;
	ext_gcd(a,m,x,y);
	return (m + x%m)%m;
}

int main(){
	ll s;
	cin >> s;
	
	ll div = s/3;
	
	ll ans = 0;
	const ll mod = (ll)1e9+7;
	FOR(i,1,div+1){
		ll ss = s - i*3;
		ll a = 1;
		// (ss+div-1)!
		// (ss)! (div-1)!
		for(ll j=0; j<ss; j++){
			a = (a*(ss+i-1 - j))%mod;
			a = (a*mod_inv(j+1,mod))%mod;
		}
		ans = (ans+a)%mod;
		
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3592
using System;

namespace SimpleCalc
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			long n = long.Parse (Console.ReadLine ());;
			string[] tmp = Console.ReadLine ().Split (" ".ToCharArray ());
			long max, min,sum;
			max = min = sum = long.Parse (tmp [0]);

			for (int i = 1; i < n; i++) {
				long data = long.Parse (tmp [i]);
				if (max < data)
					max = data;
				if (min > data)
					min = data;
				sum += data;
			}
			Console.WriteLine ("{0} {1} {2}", min, max, sum);
		}
	}
}

Measured memory_bytes: 6304
using System;
using System.Linq;

public class Tree{
  public int value;
  public Tree parent;
  public Tree left;
  public Tree right;
}

class A8{
  public static void Main(){
    Tree root = new Tree();
    int n = int.Parse(Console.ReadLine());
    for(int i = 0;i < n;i++){
      var command = Console.ReadLine().Split(' ');
      if(command[0].Equals("insert")) Insert(root,int.Parse(command[1]));
      else Print(root);
    }
  }
  public static void Insert(Tree tree,int value){
    Tree x = tree;
    Tree y = null;
    while(x != null && x.value != 0){
      y = x;
      if(value < x.value) x = x.left;
      else x = x.right;
    }
    Tree tmp = new Tree();
    tmp.value = value;
    tmp.parent = y;

    if(y == null){
      tree.value = value;
    }else if(value < y.value){
      y.left = tmp;
    }else{
      y.right = tmp;
    }
  }
  public static void Print(Tree tree){
    Inorder(tree);
    Console.WriteLine();
    Preorder(tree);
    Console.WriteLine();
  }

  public static void Inorder(Tree tree){
    if(tree == null) return;
    Inorder(tree.left);
    Console.Write(" " + tree.value);
    Inorder(tree.right);
  }
  public static void Preorder(Tree tree){
    if(tree == null) return;
    Console.Write(" " + tree.value);
    Preorder(tree.left);
    Preorder(tree.right);
  }
}


Measured memory_bytes: 46536
n = int(input().strip())
ab = [tuple(map(int, input().split())) for _ in range(n)]

mid_min = 0
mid_max = 0

ab.sort(key=lambda x: x[0])
if n & 1:
    mid_min = ab[n // 2][0]
else:
    mid_min = (ab[(n - 1) // 2][0] + ab[n // 2][0])

ab.sort(key=lambda x: x[1])
if n & 1:
    mid_max = ab[n // 2][1]
else:
    mid_max = (ab[(n - 1) // 2][1] + ab[n // 2][1])

print(mid_max - mid_min + 1)


Measured memory_bytes: 110408
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;

ll calc(const string& str){
  ll ret = 0;
  ll tmp = 0;
  rep(i,str.length()){
    if(str[i] == '+'){
      ret += tmp;
      tmp = 0;
    }else{
      tmp = 10*tmp + (ll)(str[i]-'0');
    }
  }
  ret += tmp;
  return ret;
}

int main(){
  ios::sync_with_stdio(false);
  string S;
  cin >> S;

  ll ret = 0;
  int n = S.length();
  for(int T=0; T<(1<<(n-1)); T++){
    string str = "";
    str += S[0];
    rep(i,n-1){
      if((T>>i)&1) str += "+";
      str += S[i+1];
    }
    ret += calc(str);
  }
  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = (int)1e9+7;
const double PI = 3.14159265359;
 
ll sum(ll n, ll k){
	ll ans = 0;
	for(int i=k;i<=n;i++){
		ans = (ans + i * (n - i + 1) + 1) % MOD;
	}
	return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n,k;
	cin>>n>>k;
	
	cout<<sum(n,k)+1;
	
	
	
	return 0;
}
 
 

Measured memory_bytes: 3656
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	int n, x;
	cin >> x >> n;
	set<int> mys;
	for(int i = 0, inp; i < n; i++) {
		cin >> inp;
		mys.insert(inp);
	}
	auto fn = [&](int dr) {
		int ret = x;
		while(mys.count(ret)) ret += dr;
		return ret;
	};
	auto a = fn(1), b = fn(-1);
	if(abs(a - x) < abs(b - x)) cout << a << '\n';
	else cout << b << '\n';
}



Measured memory_bytes: 3620
#!/usr/bin/python

import sys

N = int(sys.stdin.readline())
a = [int(w) for w in sys.stdin.readline().split()]
if len(a) != N: raise

n4 = len([n for n in a if n % 4 == 0])
n2 = len([n for n in a if n % 2 == 0 and n % 4 != 0])
n1 = len([n for n in a if n % 2 != 0])

if n2 > 0: n1 += 1
answer = (n1 <= n4 + 1)

print("Yes" if answer else "No")

Measured memory_bytes: 11832
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define MOD 1000000007
#define intt int64_t

int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<int> q;
    rep(i,n) {
        int c;
        cin >> c;
        q.push(c);
    }
    rep(i,m) {
        int c=q.top();
        q.pop();
        c/=2;
        q.push(c);
    }
    intt ans=0;
    while(!q.empty()) {
        int c=q.top();
        q.pop();
        ans+=c;
    }
    printf("%lld\n", ans);
}

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};

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

    return gcd(b, a % b);
}
 
int main(){
  int n;
  cin >> n;
  vector<int> x(n+1);
  cin >> x[0];
  for(int i=1; i<=n; i++){
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  vector<int> diffs(n);
  for(int i=1; i<=n; i++){
    diffs[i-1] = x[i] - x[i-1];
  }
  sort(diffs.begin(), diffs.end());
  int ans = diffs[0];
  for(int i=0; i<n; i++){
    ans = gcd(ans, diffs[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
import sys


def solve(N: int):
    if 1 <= N <= 9:
        return N
    if 10 <= N <= 99:
        return 9
    if 100 <= N <= 999:
        return 9 + N - 99
    if 1000 <= N <= 9999:
        return 9 + 900
    if 10000 <= N <= 99999:
        return 9 + 900 + N - 9999
    else:
        return 9 + 900 + 90000



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    ans = solve(N)
    if ans is not None:
        print(ans)


if __name__ == '__main__':
    main()


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

int main() {
    int n; cin >> n;
    int ans = -1;
    for(int x = 0; x <= 50000; x++){
        if(n == floor(x * 1.08)){
            ans = x;
            break;
        }
    }
    if(ans == -1) cout << ":("<<endl;
    else cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
char s[100];
cin >> s;
int num = strlen(s);
int n=(num-1)/2;
int flg = -1;
REP(i,n) {
  if(s[i]!=s[num-1-i]) flg++;
}
char s_a[n];
char s_b[n];
REP(i,n) {
  s_a[i]=s[i];
  s_b[i]=s[i+n+1];
}
if(n%2==0) {
  REP(i,n/2) {
    if(s_a[i]!=s_a[n-1-i]) flg++;
    if(s_b[i]!=s_b[n-1-i]) flg++;
  }
} else {
  REP(i,(n-1)/2) {
    if(s_a[i]!=s_a[n-1-i]) flg++;
    if(s_b[i]!=s_b[n-1-i]) flg++;
  }
}
if(flg==-1) {
  cout << "Yes" << endl;
} else {
  cout << "No" << endl;
}
return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int a,b;
    
    cin>>a>>b;
    
    if (a > b){
        cout<<"a > b"<<endl;
    }
    else if (a < b){
        cout<<"a < b"<<endl;
    }
    else {
        cout<<"a == b"<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 3092
N = int(input())
C = [int(c) for c in input().split()]
C.sort()
MOD = 10**9+7
p2 = [1]
for i in range(2*N+10):
  p2 += [p2[-1]*2%MOD]

ans = 0
for i in range(N):
  m = (p2[N-1-i]+(N-i-1)*p2[N-i-2])*C[i]
#  print(m)
  m = m*p2[N+i]%MOD
  ans += m
print(ans%MOD)


Measured memory_bytes: 30268
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

	static Scanner scan = new Scanner(System.in);
	static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		while(true){
			int n = si();
			if(n==-1) break;

			String ans = "";
			do{
				ans = n%4 + ans;
				n/=4;
			}while(n!=0);
			out.println(ans);
		}
		out.flush();
	}

	static int si() {
		return Integer.parseInt(scan.next());
	}
}

Measured memory_bytes: 23284
#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>

typedef long long ll;

using namespace std;

int main()
{
    ll s, c;
    cin >> s >> c;

    ll ans = 0;
    if(s * 2 >= c){
        ans= c / 2;
    }
    else
    {
        ans += s;
        c -= s * 2;
        ans += c / 4;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int n,k,m,ans = 0;
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        cin >> m;
        if(m >= k){
            ans++;
        }
    }
    cout << ans << endl;
    return(0);
}


Measured memory_bytes: 256
local s = io.read()

local i = 1
local numa = 0
local all = 0
while(true) do 
	if string.byte(s, i) == 65 then
		i = i + 1
		numa = numa + 1
	elseif string.byte(s, i) == 66 and string.byte(s, i + 1) == 67 then
		i = i + 2
		all = all + numa
	else
		i = i + 1
		numa = 0
	end
	if i > string.len(s) + 1 then
		break
	end
end
print(all)

Measured memory_bytes: 2728
package main

import (
	"fmt"
)

func main() {
	nums := make([][]int,3)
	
	for i := range nums {
		nums[i] = make([]int,3)
		for j := 0; j < 3; j++ {
			fmt.Scan(&nums[i][j])
		}
	}
	var x [3]int
	var y [3]int
	
	x[0] = 0
	
	for i := 0; i < 3; i++ {
		y[i] = nums[0][i] - x[0]
	}
	for i := 1; i < 3; i++ {
		x[i] = nums[i][0] - y[0]
	}
	
	judge := true
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if nums[i][j] != x[i] + y[j] {
				judge = false
				break
			}
		}
	}
	
	if judge {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    vi h(n); for(auto& e : h) cin >> e;

    int res = 1;
    int hmax = h[0];
    rep(i, 1, n){
        if(h[i] >= hmax){
            res++;
            hmax = h[i];
        }
    }

    cout << res << endl;

    return 0;
}


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

using namespace std;
int main()
{
	string str;
	int s[1048576];
	int a[2] = {0,0};
	cin >> str;
	for (unsigned int i = 0; i < str.length(); i++) {
		s[i] = (int)(str[i]-'0');
	}
	//偶数が黒
	for (unsigned int i = 0; i < str.length(); i++) {
		if ((i % 2 == 0 && s[i] == 1) || (i % 2 == 1 && s[i] == 0)) {
			(a[0])++;
		}
	}
	//偶数が白
	for (unsigned int i = 0; i < str.length(); i++) {
		if ((i % 2 == 0 && s[i] == 0) || (i % 2 == 1&& s[i] == 1)) {
			(a[1])++;
		}
	}
	if (a[0] > a[1]) {
		cout << a[1];
	}
	else {
		cout << a[0];
	}
	return 0;
}

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

int main(void){
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) cin >> a[i];
  int max = a[0];
  int min = a[0];
  for(int i = 1; i < n; i++){
    if(max < a[i]) max = a[i];
    if(min > a[i]) min = a[i];
  }
  cout << max - min << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define NCKMAX 100000
using namespace std;
int n,a,b,c,d;
vector<ll> dp(1001),_dp(1001);
ll fact[NCKMAX];
void nckinit(){
    ll x=1;
    fact[0]=1;
    for (int i=1; i<NCKMAX; i++){
        (x*=i)%=MOD;
        fact[i]=x;
    }
}
int modpow(ll x,ll y){
    if (y==0){
        return 1;
    }else if (y==1){
        return x%MOD;
    }else if (y%2==0){
        ll z=modpow(x,y/2);
        return z*z%MOD;
    }else{
        ll z=modpow(x,y/2);
        return (z*z%MOD)*x%MOD;
    }
}
int inv(ll x){
    return modpow(x,MOD-2);
}
int nck(ll x,ll y){
    ll ret=fact[x];
    (ret*=inv(fact[y]))%=MOD;
    (ret*=inv(fact[x-y]))%=MOD;
    return ret;
}
ll solve(int x,int y,int z){
    ll ret=fact[n-z];
    (ret*=inv(fact[n-z-x*y]))%=MOD;
    return ret;
}
ll solve2(int x,int y){
    ll ret=modpow(x,y);
    (ret*=inv(fact[y]))%=MOD;
    return ret;
}
int main(){
    nckinit();
    cin>>n>>a>>b>>c>>d;
    dp[0]=1;
    for (int x=a;x<b+1;x++){    //何人グループまで作るか
        _dp=dp;
        ll xx=inv(fact[x]);
        for (int y=c;y<d+1;y++){    //x人で何グループ作るか
            if (x*y>n) break;
            ll s=solve2(xx,y);
            for (int z=0;z+x*y<n+1;z++){
                (_dp[z+x*y]+=(dp[z]*s%MOD)*solve(x,y,z)%MOD)%=MOD;
            }
        }
        dp=_dp;
    }
    cout<<dp[n]%MOD<<endl;
    return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
constexpr long long LINF = 1000100010001000100LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){ 
    ll x, y; cin >> x >> y;
    if(x == y) cout << 1 << ln;
    else{
        int cnt = 0; ll num = x;
        while(num <= y){
            cnt++;
            num *= 2;
        }
        cout << cnt << ln;
    }
}

Measured memory_bytes: 256
n,m,q=map(int,input().split())
line=[[0]*(n+1) for i in range(n+1)]
for _ in range(m):
  l,r=map(int,input().split())
  line[l][r]+=1
for i in range(n+1):
  for j in range(n):
    line[i][j+1]+=line[i][j]
for i in range(n+1):
  for j in range(n):
    line[j+1][i]+=line[j][i]
for _ in range(q):
  l,r=map(int,input().split())
  print(line[r][r]-line[r][l-1]-line[l-1][r]+line[l-1][l-1])

Measured memory_bytes: 15220
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

int main() {
    int N;
    cin >> N;
    vi data(N);
    for (int i = 0; i < N; i++) {
        cin >> data[i];
    }
    vll count(N + 1, 0);
    for (int x : data) {
        count[x]++;
    }
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        if (count[i] > 1) {
            ll j = count[i];
            ans += j * (j - 1) / 2;
        }
    }
    for (int i = 0; i < N; i++) {
        ll ansa = ans;
        if (count[data[i]] > 1) {
            ll j = count[data[i]];
            ansa -= j * (j - 1) / 2;
            ansa += (j - 1) * (j - 2) / 2;
        }
        cout << ansa << endl;
    }
}


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

bool sw[1050][1050];
int map[1050][1050];
int L[1050][1050];
int R[1050][1050];

int main()
{
	int n, m, h, k;
	while (cin >> n >> m >> h >> k, n||m||h||k)
	{
		int score[n];
		for (int i=0; i<n; i++)
			cin >> score[i];

		
		for (int i=0; i<h; i++)
		for (int j=0; j<n; j++)
		{
			map[j][i] = j;
			L[j][i] = R[j][i] = -1;
		}

		for (int i=0; i<m; i++)
		{
			int a, b;
			cin >> a >> b;
			a--; b--;

			map[a][b] = a+1;
			map[a+1][b] = a;
		}

		int scr[1050];
		for (int i=0; i<n; i++)
		{
			int p = i;
			for (int j=0; j<h; j++)
			{
				if (map[p][j] != p)
				{
					int M = min(map[p][j], p);
					if (L[M][j] == -1) L[M][j] = i;
					else		   R[M][j] = i;

					p = map[p][j];
				}
			}
			scr[i] = score[p];
		}

		for (int i=0; i<n; i++)
		for (int j=0; j<h; j++)
		{
			if (L[i][j] != -1)
			{
				sw[L[i][j]][R[i][j]] = 1;
				sw[R[i][j]][L[i][j]] = 1;
			}
		}

		int sum = 0;
		for (int i=0; i<k; i++)
			sum += scr[i];

		int ret=sum;
		for (int i=0; i<k; i++)
		for (int j=k; j<n; j++)
		{
			if (!sw[i][j]) continue;
			ret = min(ret, sum-scr[i]+scr[j]);
		}

		cout << ret << endl;

	}
	return 0;
}

Measured memory_bytes: 13000
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int n;cin>>n;
  vector<int> v(n, 0);
  int s=0, t=7;
  for(int i=0;i<100000000;i++){
    s=(s+t)%n;
    if(s==0){
      cout<<i+1<<endl;
      break;
    }
    if(v[s]){
      cout<<-1<<endl;
      break;
    }
    v[s]=1;
    t=(t*10)%n;
  }
}

Measured memory_bytes: 6776
using System;
using System.Collections.Generic;
using System.Linq;

namespace B_AGC034
{
    class MainClass
    {



        public static void Main(string[] args)
        {
            string s = Console.ReadLine();
            int n = s.Length;
            s = s+'B';
            long ans = 0;
            long p = 0;
            for(int i = 0;i<n-1;i++){
                if(s[i]=='A'){
                    p++;
                }else if (s[i]=='B'&&s[i+1]=='C'){
                    ans+=p;
                    i++;
                }else{
                    p=0;
                }
            }
            Console.WriteLine(ans);


        }
    }
}


Measured memory_bytes: 13224
#include<stdio.h>

int ice[10];

void init(int i){
  if(i<10){
    ice[i]=0;
    init(i+1);
  }
}

void count(int n){
  if(n!=0){
    int m;
    scanf("%d",&m);
    ice[m]++;
    count(n-1);
  }
}

void prgraph(int n){
  if(n<10){
    if(ice[n]==0){
      printf("-\n");
    }
    else{
      int i;
      for(i=0;i<ice[n];i++){
	printf("*");
      }
      printf("\n");
    }
    prgraph(n+1);
  }
}

void doit(){
  int n;
  scanf("%d",&n);
  if(n!=0){
    init(0);
    count(n);
    prgraph(0);
    doit();
  }
}

int main(){
  doit();
  return 0;
}

Measured memory_bytes: 884
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define all(a) a.begin(),a.end()
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*pi*/double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll i,fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
/*桁数*/ll dig(ll n){ll d=0,i=0;while(n/10>0){i++;d++;}return d;}
llfor;ll ans=0;////////////////////////////////////////////////////////////
int main(){
 ll mod=998244353;
 ll n,m;
 sc(n);sc(m);
 char a[n+10][n+10],b[m+10][m+10];
 rep(i,0,n)sc(a[i]);
 rep(i,0,m)sc(b[i]);

 ll k,l;
 bool flag=false;
 rep(i,0,n-m+1){
  rep(j,0,n-m+1){
   if(a[i][j]==b[0][0]){
    //cout<<"start "<<i<<" "<<j<<endl;
    rep(k,0,m){
     rep(l,0,m){
      flag=false;
     // cout<<"now "<<k<<" "<<l<<endl;
      if(a[i+k][j+l]!=b[k][l]){
       flag=true;break;
      }
      if(k==m-1&&l==m-1){
       py;return 0;
      }
     }
     if(flag)break;
    }
   }
  }
 }
 pn;
 return 0;}


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



int main() {
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	for(int i = 0; i < n ; i++ )
	{
		cin >> h[i];
	}
	sort(h.begin(),h.end());
	k = min(n,k);
	ll ans = 0;
	rep(i,k){
		h.pop_back();
	}

	rep(i,h.size()) ans += h[i];
	cout << ans << endl;

	return 0;
}

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

// n の i ビット目と j ビット目を swap する
void swp(int &n, int i, int j) {
    if ((n >> i & 1) ^ (n >> j & 1) == 0) return;
    n ^= (1 << i);
    n ^= (1 << j);
}

// [0, n) ビット目を使って a を b にする
vector<int> dfs(int n, int a, int b) {
    if (n == 1) return {a, b};

    int highest = n - 1;
    int c = a ^ b;

    if (~c >> highest & 1) {
        for (int i = 0; i < n - 1; i++) {
            if (c >> i & 1) highest = i;
        }
    }
    swp(a, n - 1, highest);
    swp(b, n - 1, highest);

    int na = a & ~(1 << n - 1);
    auto first = dfs(n - 1, na, na ^ 1);
    int nb = b & ~(1 << n - 1);
    auto second = dfs(n - 1, na ^ 1, nb);

    vector<int> res;
    if (a >> (n - 1) & 1) {
        for (auto x : first) res.push_back(x ^ (1 << (n - 1)));
        for (auto x : second) res.push_back(x);
    } else {
        for (auto x : first) res.push_back(x);
        for (auto x : second) res.push_back(x ^ (1 << (n - 1)));
    }

    for (auto& x : res) swp(x, n - 1, highest);
    return res;
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int g = a ^ b;
    if (__builtin_popcount(g) % 2 == 0) {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    auto res = dfs(n, a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << ((i == res.size() - 1) ? "\n" : " ");
    }
}

Measured memory_bytes: 1628
// Package main provides
//
// File:  d.go
// Author: ymiyamoto
//
// Created on Wed Jan  2 23:01:59 2019
//
package main

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

var N, K int
var board [][]int

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func countRegion(y, x int) int {
	limY, limX := y+K-1, x+K-1
	limY = max(limY, 0)
	limY = min(limY, len(board)-1)
	limX = max(limX, 0)
	limX = min(limX, len(board[0])-1)

	minLimY, minLimX := y-1, x-1
	minLimY = max(minLimY, 0)
	minLimY = min(minLimY, len(board)-1)
	minLimX = max(minLimX, 0)
	minLimX = min(minLimX, len(board[0])-1)

	return board[limY][limX] - board[limY][minLimX] - board[minLimY][limX] + board[minLimY][minLimX]
}

var sc = bufio.NewScanner(os.Stdin)

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

func main() {
	fmt.Scan(&N, &K)

	board = make([][]int, 2*K+2)
	for i := range board {
		board[i] = make([]int, 2*K+2)
	}

	for i := 0; i < N; i++ {
		var x, y int
		var c string

		fmt.Sscan(nextLine(), &x, &y, &c)
		if c == "B" {
			y += K
		}
		board[(y%(2*K))+1][(x%(2*K))+1]++
	}

	for i := range board {
		for j := range board[i] {
			if j+1 < len(board[i]) {
				board[i][j+1] += board[i][j]
			}
		}
	}

	for i := range board {
		for j := range board[i] {
			if i+1 < len(board[i]) {
				board[i+1][j] += board[i][j]
			}
		}
	}

	ans := 0
	for i := 1; i < len(board); i++ {
		for j := 1; j < len(board[i]); j++ {
			count := countRegion(i, j)

			count += countRegion(i+K, j+K)
			count += countRegion(i+K, j-K)
			count += countRegion(i-K, j+K)
			count += countRegion(i-K, j-K)

			count += countRegion(i, j-2*K)
			count += countRegion(i-2*K, j)
			count += countRegion(i-2*K, j-2*K)

			ans = max(ans, count)
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 50304
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    int n; cin >> n;
    int a[10010];
    rep(i, n) cin >> a[i];
    int ans[110][110];
    int k = 0;
    rep(i, h) {
        if(i % 2 == 0) {
            rep(j, w) {
                if(a[k] == 0) k++;
                a[k]--;
                int num = k + 1;
                ans[i][j] = num;
            }
        } else {
            RREP(j, w - 1, 0) {
                if(a[k] == 0) k++;
                a[k]--;
                int num = k + 1;
                ans[i][j] = num;
            }
        }
    }
    rep(i, h) {
        rep(j, w) {
            if (j != 0) cout << " ";
            cout << ans[i][j];
        }
        cout << endl;
    }


    return 0;
}


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

using namespace std;

int main() {
	string s;
	char c;
	int i,j,flag =0;
	cin >> s;
	for (i = 0; i < s.length(); i++) {
		for (j = i; j < s.length(); j++) {
			if (s[i] > s[j]) {
				c = s[i];
				s[i] = s[j];
				s[j] = c;
			}
		}
	}
	if (s.length() % 2 == 1) {
		cout << "No" << endl;
	}
	else {
		for (i = 0; i < s.length(); i++, i++) {
			if (s[i] != s[i + 1]) flag++;
		}
		if (flag == 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
from heapq import heappop,heappush
import sys
input = sys.stdin.readline
def resolve():
    N = int(input())
    b = 0
    left = []
    right = []
    sumleft = sumright = mid = 0
    for _ in range(N):
        q = list(map(int,input().split()))
        if q[0]==1:#登録
            a = q[1]
            b = b + q[2]
            if not left or -left[0]>a:
                heappush(left,-a)
                sumleft = sumleft + a
                if (len(left)-len(right))>=2:
                    move = -heappop(left)
                    heappush(right,move)
                    sumleft = sumleft-move
                    sumright = sumright+move
            else:
                heappush(right,a)
                sumright = sumright + a
                if len(left)<len(right):
                    move = heappop(right)
                    heappush(left,-move)
                    sumright = sumright-move
                    sumleft = sumleft+move
            mid = -left[0]
        else:#表示
            ans = (len(left)-len(right))*mid-sumleft+sumright + b
            print(mid,ans)


if __name__ == "__main__":
    resolve()

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

int main()
{
	int InArray[200000] = {0};		// end is linked to start (Baumkuchen is round)
	int N;							// total data input
	int i;							// for counter
	int inputBuffer;				// buffer for input data
	int a1, a2, a3;					// the start index of each region
	long long sum;					// buffer for sum
	long long average, average2;	// sum / 3, (sum - region1) / 2
	long long a1_sum, a2_sum;		// sum of region1, region2
	long long MaxMin;				// final result
	
	scanf("%d", &N);
	for(i = 0; i < N; i++){
		scanf("%d", &inputBuffer);
		InArray[i] = inputBuffer;
		InArray[i + N] = inputBuffer;
	}

	
	// Calculate sum and average
	sum = 0;
	for(i = 0; i < N; i++){
		sum += InArray[i];
	}
	if(sum % 3 == 0){
		average = sum / 3;
	}else{
		average = sum / 3 + 1;
	}
	
	MaxMin = 0;
	for(a1 = 0; a1 < N; a1++){
		a1_sum = 0;
		for(a2 = a1 + 1; a2 < (a1 + N); a2++){
			a1_sum += InArray[a2 - 1];
			if(a1_sum < average) continue;
			
			if((sum - a1_sum) % 2 == 0){
				average2 = (sum - a1_sum) / 2;
			}else{
				average2 = (sum - a1_sum + 1) / 2;
			}
			
			a2_sum = 0;
			for(a3 = a2 + 1; a3 < (a1 + N); a3++){	// left 1 for a3_sum
				a2_sum += InArray[a3 -1];
				if(a2_sum < average2) continue;
								
				if(a2_sum - InArray[a3 -1] > MaxMin){
					MaxMin = a2_sum - InArray[a3 -1];
				}
				if(sum - a1_sum - a2_sum   > MaxMin){
					MaxMin = sum - a1_sum - a2_sum;
				}
				break;
			}
			break;
		}
	}
	
	printf("%lld\n", MaxMin);
	
	return 0;
}

Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
static const double route3=1.7320508075;

vector<pair<double,double> > Coch;

void makecoch(int i,pair<double,double> s,pair<double,double> t){
    if(i==0){
        Coch.push_back(s);
    }
    else {
        pair<double,double> x,y,z;
        x=make_pair((2*s.first+t.first)/3,(2*s.second+t.second)/3);
        y=make_pair((s.first+t.first-(t.second-s.second)/route3)/2
        ,(s.second+t.second+(t.first-s.first)/route3)/2);
        z=make_pair((s.first+2*t.first)/3,(s.second+2*t.second)/3);
        makecoch(i-1,s,x);
        makecoch(i-1,x,y);
        makecoch(i-1,y,z);
        makecoch(i-1,z,t);
    }
}

int main(){
    int n;cin>>n;
    makecoch(n,make_pair(0,0),make_pair(100,0));
    Coch.push_back(make_pair(100,0));
    for(int i=0;i<Coch.size();i++){
        printf("%lf %lf\n",Coch[i].first,Coch[i].second);
    }
}


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

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define endl '\n'
#define MAX

typedef long long ll;
typedef pair<int,int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;


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

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	int n, k;
	cin >> n >> k;
	
	vector<bool> dp(k + 1);
	vector<int> a(n);
	
	for(int i = 0; i < n; i++)
		cin >> a[i];

	for(int i = 1; i <= k; i++)
		for(auto &j : a)
			if(i - j >= 0)
				dp[i] = dp[i] | (!dp[i - j]);

	cout << (dp[k] ? "First" : "Second") << endl;

	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
int main(){
    int s[400], m, i, j, l=0, h;
    while(1){
        int l=0;
        while((s[l++]=getchar())!='\n'){}
        //printf("s[0]=%c\n", s[0]);
        if(s[0]=='-')break;
        scanf("%d", &m);
        for(i=0; i<m; i++){
            scanf(" %d", &h);
            for(j=0; j<l-1; j++)s[l-1+j]=s[j];
            for(j=h; j<h+l-1; j++)s[j-h]=s[j];
        }
        for(i=0; i<l-1; i++)printf("%c", s[i]);
        (void)getchar();
        printf("\n");
    }
    return 0;
}

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

using namespace std;
using i64 = long long int;

struct UnionFind{
    vector<i64> par;
    UnionFind(i64 n){
        par.assign(n, -1);
    };
    i64 root(i64 x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    };
    i64 size(i64 x){
        x = root(x);
        return -1 * par[x];
    };
    bool unite(i64 x, i64 y){
        x = root(x); y = root(y);
        if(x == y) return false;
        if(size(x) > size(y)) par[y] = x;
        else par[x] = y;
        return true;
    }
    bool same(i64 x, i64 y){
        return root(x) == root(y);
    };
};

int main(){
    i64 n, q;
    cin >> n >> q;
    UnionFind uf(n);
    for(i64 i = 0; i < q; ++i){
        i64 com, x, y;
        cin >> com >> x >> y;
        if(com == 0) uf.unite(x, y);
        else cout << uf.same(x, y) << endl;
    }
}


Measured memory_bytes: 3192
#include <iostream>
#include <cmath>
#define ll long long int

using namespace std;

int par[100001];
int r[100001];
ll weight[100001];
int n, m;

void init(){
		for(int i = 0; i < n; i++)par[i] = i;
}

int find(int x){
		if(par[x] == x)return x;
		else {
				int parent = find(par[x]);
				weight[x] += weight[par[x]];
				return par[x] = parent;
		}
}

bool same(int x, int y){
		return find(x) == find(y);
}

// x: left y: right
bool unite(int x, int y, ll w){
		int xp = find(x);
		int yp = find(y);
		w = w - weight[y] + weight[x];
		if(xp == yp){
				if(weight[yp] - weight[xp] == w)return true;
				else return false;
		}
		if(r[xp] > r[yp]){
				par[yp] = xp;
				weight[yp] = w;
		}else{
				par[xp] = yp;
				weight[xp] = -w;
				r[yp]++;
		}
		return true;
}

int main(int argc, char const* argv[])
{
	cin >> n >> m;
	init();
	for(int i = 0; i < m; i++){
			int l, r, d;
			cin >> l >> r >> d;
			l--;
			r--;
			if(!unite(l, r, d)){
					cout << "No" << endl;
					return 0;
			}
	}
	for(int i = 0; i < n; i++){

	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 1920
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
int n;
int a,b;
int t[100006];
string s;
int nai;
int soto;
int main()
{
	cin>>n>>a>>b;
	cin>>s;
	rep(i,n)
	{
		if(s[i]=='a')
		{
			if(nai+soto<a+b)
			{
				t[i]=1;
				nai++;
			}
		}
		if(s[i]=='b')
		{
			if(nai+soto<a+b&&soto<b)
			{
				t[i]=1;
				soto++;
			}
		}
	}
	rep(i,n)
	{
		if(t[i]==1)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;

#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

int main(int argc, char **argv) {
	string s;
	cin >> s;
	cout << s.substr(0, s.length() - 8) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main (void){
    int a,b,d,r;
    double f;
    scanf("%d %d",&a,&b);
    d = a /b;
    r = a%b;
    f = (a/1.0)/(b/1.0);
    printf("%d %d %.5f\n",d,r,f);

    return 0;
}


Measured memory_bytes: 2132
import java.util.*;
public class Main { 
	static int[][] map;
	static int[] dp;
	static int INF = 1 << 24;
	static int n;
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while(true) {
			n = stdIn.nextInt();
			if(n == 0) break;
			map = new int[n][n+1];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n+1; j++) {
					map[i][j] = stdIn.nextInt();
				}
			}
			dp = new int[1 << n];
			Arrays.fill(dp, INF);
			dp[0] = 0;
			dp();
			System.out.println(dp[(1 << n)-1]);
			
		}
	}
	public static void dp() {
		
		for(int i = 0; i < n; i++) {
			for(int j = (1 << n)-1; j >= 0; j--) {
				if(dp[j] < INF) {
					for(int k = 0; k < n; k++) { //つぎはどこ
						if((j & (1 << (k))) == 0) {
							for(int l = 0; l < n; l++) {
								if(l == 0) {
									dp[(j | 1 << k)] = Math.min(dp[j | 1 << k], dp[j] + map[k][l]);
								}
								if((j & (1 << l)) != 0) {
									dp[(j | 1 << k)] = Math.min(dp[(j | 1 << k)], dp[j] + map[k][l+1]);
								}
							}
						}
					}
				}
			}
		}
	}
}

Measured memory_bytes: 35200
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.awt.Point;
import java.util.*;
   
class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str;
while(!(str=br.readLine()).equals("0 0")){
String[] value=str.split(" ");
int h=Integer.parseInt(value[0]);
int w=Integer.parseInt(value[1]);
char[][] map=new char[h][w];
for(int i=0;i<h;i++){
map[i]=br.readLine().toCharArray();
}
Deque <Point> fifo  =new  ArrayDeque<Point>();
  int ans=0;
   for(int m=0;m<h;m++){
   for(int n=0;n<w;n++){
if(map[m][n]!='.'){
ans++;
Point p = new Point(n,m);
fifo.addLast(p);
while(fifo.peekFirst()!=null){
p=fifo.pollFirst();
int x=p.x;
 int y=p.y;
  char crop = map[y][x];
map[y][x]='.';
 int [] dx ={0,1,0,-1};
 int [] dy ={1,0,-1,0};                   
     for(int i=0;i<4;i++){
      int nx =x+dx[i];
   int ny =y+dy[i];
if(nx>=0&&nx<w&&ny>=0&&ny<h&&map[ny][nx]==crop&&map[ny][nx]!='.'){
          Point np = new Point();
                        np.x=nx;
                        np.y=ny;
                     fifo.addLast(np);                       
}
}
}
}
}
}System.out.println(ans);
}
}
}

Measured memory_bytes: 26956