akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define nMax 10000
#define qMax 500

int linearSearch(int key,int S[],int n){
  int i;
  i=0;
  S[n] = key;
  while(S[i] != key){
    i++;
    if(i>=n){
      return 0;
    }
  }
  return 1;
}
  
int main(){

  int n,i,j,q,z,count=0;
  int S[nMax],T[qMax];

  scanf("%d",&n);

  if(n <= nMax){
    for(i=0;i<n;i++){
      scanf("%d",&S[i]);
    }
  }
  else printf("Not found\n");
  
    scanf("%d",&q);

    if(q <= qMax){
      for(j=0;j<q;j++){
	scanf("%d",&T[j]);
	if(linearSearch(T[j],S,n))
	  count++;	  
      }
    }
    else printf("Not found\n");

   

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

    return 0;
}



Measured memory_bytes: 2144
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, 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
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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 ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
T = LIST()
A = LIST()

h = [0]*N
ma = -1
for i, t in enumerate(T):
	if t > ma:
		h[i] = t
		ma = t

ma = -1
for i, a in enumerate(A[::-1]):
	if a > ma:
		if h[-i-1] and a != h[-i-1]:
			print(0)
			exit()
		h[-i-1] = a
		ma = a

acc_t = list(accumulate(h, max))
acc_a = list(accumulate(h[::-1], max))[::-1]

if acc_t != T or acc_a != A:
	print(0)
	exit()

mi = [min(t, a) for t, a in zip(T, A)]

ans = 1
for i in range(N):
	if h[i] == 0:
		ans *= mi[i]
		ans %= mod
print(ans)


Measured memory_bytes: 20540
package main

import (
	"fmt"
	"math"
)

func max(nums ...int) int {
	res := math.MinInt32
	for _, num := range nums {
		if num > res {
			res = num
		}
	}
	return res
}

func main() {
	s, t := "", ""
	fmt.Scan(&s, &t)

	memo := make([][]int, len(s)+1)
	for i := 0; i <= len(s); i++ {
		memo[i] = make([]int, len(t)+1)
	}
	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(t); j++ {
			if s[i-1] == t[j-1] {
				memo[i][j] = memo[i-1][j-1] + 1
				continue
			}
			memo[i][j] = max(memo[i-1][j], memo[i][j-1])
		}
	}

	bestLen := memo[len(s)][len(t)]
	// Go backward to construct the solution
	solution := ""
	for i, j := len(s)-1, len(t)-1; len(solution) != bestLen; {

		if s[i] == t[j] {
			solution, i, j = s[i:i+1]+solution, i-1, j-1
			continue
		}
		if memo[i][j+1] > memo[i+1][j] {
			i--
		} else {
			j--
		}
	}
	fmt.Println(solution)
}


Measured memory_bytes: 80512
using System;

namespace ABC167
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var s = Console.ReadLine().ToCharArray();
            var r = Console.ReadLine().ToCharArray();

            for(int i = 0; i < s.Length; i++)
            {
                if (s[i] == r[i]) continue;
                Console.WriteLine("No");
                return;
            }
            Console.WriteLine("Yes");
        }
    }
}


Measured memory_bytes: 25764
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
			StringBuilder answer = new StringBuilder();
			int n = Integer.parseInt(input.readLine());
			for (int i = 3; i <= n; i++) {
				if (i % 3 == 0) {
					answer.append(" ").append(String.valueOf(i));
				} else {
					int tmp = i;
					while (tmp != 0) {
						if (tmp % 10 == 3) {
							answer.append(" ").append(String.valueOf(i));
							break;
						}
						tmp /= 10;
					}
				}
			}
			System.out.println(answer.toString());
		} catch (Exception e) {
			e.printStackTrace();
		}

	}
}

Measured memory_bytes: 21048
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

const ll INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vi a(n); rep(i, n) cin >> a[i];

  int sign = 0;
  int ans = 1;
  rep(i, n-1){
    if(a[i] == a[i+1]) continue;
    if(a[i] > a[i+1]){
      if(sign == 0) sign++;
      if(sign > 0) continue;
      if(sign < 0) {ans++; sign = 0;}
    }
    if(a[i] < a[i+1]){
      if(sign == 0) sign--;
      if(sign < 0) continue;
      if(sign > 0) {ans++; sign = 0;}
    }
  }

  std::cout << ans << '\n';
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

bool b[2001];
const int INF = int(1e9);
int L[2001];
int R[2001];

int solve(deque<bool> &a, int cyc) //we need to move right cyc steps c(# of right - # of left)
{
	int n=a.size();
	//cerr<<"SOLVE : "<<cyc<<'\n';
	vi vec;
	for(int i=0;i<n;i++)
	{
		if(b[i]) vec.pb(i);
	}
	if(vec.empty())
	{
		for(int i=0;i<n;i++)
		{
			if(a[i]!=b[(i+cyc)%n]) return INF;
		}
		return min(cyc,n-cyc);
	}
	int ext=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]!=b[(i+cyc)%n]) ext++;
	}
	//there exist at least one flipping spot
	for(int i=0;i<n;i++)
	{
		if(a[i]!=b[(i+cyc)%n]) //needs to flip
		{
			//find min h s.t. b[i-h] is good
			int z = upper_bound(vec.begin(),vec.end(),i) - vec.begin();
			z--;
			if(z>=0)
			{
				L[i] = i - vec[z];
			}
			else
			{
				L[i] = i + n - vec.back();
			}
			//find min h s.t. b[i+h] is good
			z = lower_bound(vec.begin(),vec.end(),i) - vec.begin();
			if(z<int(vec.size()))
			{
				R[i] = vec[z] - i;
			}
			else
			{
				R[i] = n - i + vec.front();
			}
		}
		else
		{
			L[i]=R[i]=0;
		}
	}
	vector<ii> V;
	for(int i=0;i<n;i++)
	{
		V.pb(mp(L[i],R[i]));
		//cerr<<i<<' '<<L[i]<<' '<<R[i]<<'\n';
	}
	sort(V.begin(),V.end());
	int mx=0;
	int ans=INF;
	for(int i=n-1;i>=-1;i--)
	{
		//equal no problem
		int l = 0;
		if(i>=0)
		{
			l = V[i].fi;
		}
		int steps,pos;
		if(mx==0)
		{
			steps = l;
			pos = -l;
		}
		else
		{
			steps = mx + 2*l;
			pos = mx;
		}
		int diff = (cyc - pos)%n;
		if(diff<0) diff+=n;
		//cerr<<mx<<' '<<steps<<' '<<diff<<'\n';
		ans = min(ans, steps + min(diff,n-diff));
		if(i>=0) mx = max(mx, V[i].se);
	}
	for(int i=0;i<n;i++)
	{
		swap(V[i].fi,V[i].se);
	}
	sort(V.begin(),V.end());
	mx=0;
	for(int i=n-1;i>=-1;i--)
	{
		//equal no problem
		int l = 0;
		if(i>=0)
		{
			l = V[i].fi;
		}
		int steps,pos;
		if(mx==0)
		{
			steps = l;
			pos = l;
		}
		else
		{
			steps = mx + 2*l;
			pos = -mx;
		}
		int diff = (cyc - pos)%n;
		if(diff<0) diff+=n;
		//cerr<<mx<<' '<<steps<<' '<<diff<<'\n';
		ans = min(ans, steps + min(diff,n-diff));
		if(i>=0) mx = max(mx, V[i].se);
	}
	//cerr<<ans<<' '<<ext<<'\n';
	return (ans+ext);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string a,B;
	cin>>a>>B;
	int n=a.length();
	for(int i=0;i<n;i++)
	{
		if(B[i]=='1') b[i]=1;
		else b[i]=0;
	}
	int ans=INF;
	deque<bool> dq;
	for(int i=0;i<n;i++)
	{
		if(a[i]=='1') dq.pb(1);
		else dq.pb(0);
	}
	for(int i=0;i<n;i++)
	{
		//go right i steps
		ans=min(ans,solve(dq,i)); 
	}
	if(ans>=INF)
	{
		cout<<-1<<'\n';
	}
	else
	{
		cout<<ans<<'\n';
	}
}


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

#define ll long long



void solve(){
    int n;cin>>n;
    vector<int>p(n);for(int i=0; i<n; i++)cin>>p[i];
    
    int cnt=0;
    for(int i=1; i<n-1; i++){
        int mini=min(p[i-1], min(p[i], p[i+1]));
        int maxi=max(p[i-1], max(p[i], p[i+1]));
        if(mini!=p[i] && maxi!=p[i]){
            cnt++;
        }
    }
    cout<<cnt<<endl;
}   

signed main(){
    //while(1)
    solve();
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Twins
{
    class Program
    {
        static void Main(string[] args)
        {
            if (!Console.ReadLine().Equals("ani"))
            {
                Console.WriteLine("e869120");
            }
            else
            {
                Console.WriteLine("square1001");
            }
        }
    }
}



Measured memory_bytes: 13816
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x,y,z;
	cin>>x>>y>>z;
	int c1=max(x-y,y-x);
	int c2=max(x-z,z-x);
	int c3=max(z-y,y-z);
	int ans;
	ans=min(c1+c2,c2+c3);
	ans=min(ans,c3+c1);
	cout<<ans<<endl;
	return 0;
 } 

Measured memory_bytes: 256
//Author: A_S_M_M@sud_P@rvez
#include<bits/stdc++.h>
using namespace std;
#define    MP ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define    For(i,n) for(int i=0;i<n;i++)
#define    forn(i,n) for(int i=1;i<=n;i++)
#define    fors(i,s) for(int i=0;i<s.size();i++)
#define    all(v) v.begin(),v.end()
#define    gcd(a, b) __gcd(a , b)
#define    lcm(a,b) (a*(b/__gcd(a,b)))
#define    test   int t;cin>>t;for(int l=0;l<t;l++)
#define    min3(a,b,c)     min(a,min(b,c))
#define    max3(a,b,c)     max(a,max(b,c))
#define    min4(a,b,c,d)   min(min(a,b),min(c,d))
#define    max4(a,b,c,d)   max(max(a,b),max(c,d))
#define    nl     "\n"
#define    End    return 0 
#define    gt     greater<int>()
#define    ll     long long 
#define    mp     make_pair
#define    pb     push_back
#define    vi     vector<int>
#define    vl     vector<ll>
#define    mod    1000000007
#define    sp(n)  fixed<<setprecision(n)
#define    pi     acos(-1)

int main()
{
MP;
    //test
    {
        int n;
        cin>>n;
        if(n>=30)cout<<"Yes";
        else cout<<"No";
    }
    
End;
}


Measured memory_bytes: 3648
//#include <bits/stdc++.h>
//#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>

using namespace std;
using ll=long long;
using intpair=pair<int,int>;
using intpv=vector<intpair>;
using llpair=pair<ll,ll>;
using llpv=vector<llpair>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;
using pairmat=vector<llpv>;

template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

#define PI 3.141592653589793
#define INTINF 1<<30
#define LLINF 1LL<<60
#define MPRIME 1000000007
#define MPRIME9 998244353

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())
#define matin(mat,H,W) for(int i__=0; i__<H; i__++)for(int j__=0; j__<W; j__++) cin>>mat[i__][j__]
#define out(n) cout<<n<<endl

template<class T>
inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
inline void outmat(T& a, int y, int x) {
	for(int i=0; i<y; i++) {
		for(int j=0; j<x; j++) cout<<a[i][j]<<" ";
		cout<<endl;
	}
}

template<class T>
inline void init(T& v) {
	for(auto &a__: v) cin>>a__;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a__: v) cin>>a__;
}

template<class N> void resiz(N n) {} // empty
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

ll GCD(ll a, ll b) { //最大公約数
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	ll tmp = a%b;
	while(tmp!=0) {
		a = b;
		b = tmp;
		tmp = a%b;
	}
	return b;
}

ll binpow(ll a, ll ex, ll p) { //繰り返し二乗法
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}

ll Fact(ll x, ll p) { //階乗
	ll f=1;
	for(ll i=2; i<=x; i++) {
		f*=i;
		f%=p;
	}
	return f;
}

int DigitNum(ll n) { //桁数
	int digit=0;
	ll div=1LL;
	while(n/div) {
		digit++;
		div*=10;
	}
	return digit;
}


int X,N;
intvec P;
int d=INTINF,res;

void input() {
	cin>>X>>N;
	init(P,N);
}

bool check(int n) {
	for(int i=0; i<N; i++) {
		if(P[i]==n) return false;
	}
	return true;
}

void solve() {
	intq q;
	q.push(X); q.push(X-1); q.push(X+1);
	while(1) {
		int now=q.front(); q.pop();
		if(check(now)) {
			cout<<now<<endl;
			return;
		}
		if(X == now) continue;
		if(X > now) q.push(now-1);
		else q.push(now+1);
	}
}

int main() {
	while(1) {
		input();
		solve();
		break;
	}
}


Measured memory_bytes: 3632
package main

import (
	"bufio"
	"container/list"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := nextInt()
	Q := nextInt()

	graph := make([][]int, N+1)
	parents := make([]int, N+1)
	query := make([]int64, N+1)
	ans := make([]int64, N+1)

	for i := 0; i < N-1; i++ {
		a := nextInt()
		b := nextInt()

		graph[a] = append(graph[a], b)
		graph[b] = append(graph[b], a)
	}

	// 親を決める
	queue := list.New()
	queue.PushBack(1)
	for queue.Len() > 0 {
		e := queue.Front()
		s := e.Value.(int)
		queue.Remove(e)

		for i := 0; i < len(graph[s]); i++ {
			if graph[s][i] == parents[s] {
				continue
			}
			n := graph[s][i]
			parents[n] = s
			queue.PushBack(n)
		}
	}

	for i := 0; i < Q; i++ {
		p := nextInt()
		x := int64(nextInt())
		query[p] += x
	}

	// fmt.Println(query)
	queue.PushBack(1)
	ans[1] = query[1]
	for queue.Len() > 0 {
		e := queue.Front()
		s := e.Value.(int)
		queue.Remove(e)

		for i := 0; i < len(graph[s]); i++ {
			if graph[s][i] == parents[s] {
				continue
			}
			n := graph[s][i]
			ans[n] += query[n] + ans[parents[n]]
			queue.PushBack(n)
		}
	}
	for i := 1; i <= N; i++ {
		fmt.Print(ans[i])

		if i != N {
			fmt.Print(" ")
		}
	}
	fmt.Println()
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 35072
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl '\n'
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
   int a,b,k;
   cin>>a>>b>>k;
   for(int i=a;i<=min(b,a+k-1);i++)cout<<i<<endl;
   for(int i=max(b-k+1,a+k);i<=b;i++)cout<<i<<endl;
}
int32_t main(){
  IOS;
  solve();
  //debug();
 #ifdef LOCAL_DEFINE
 cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
 #endif	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

int main()
{
    string s;
    cin>>s;
    int n=s.length();
    vector<int>a(n+1,0);
    int t=0;
    a[0]=0;
    char prev;
    int small=0,large=0;
    rep(i,n)
    {
        if(s[i]=='<')
        {
            a[i+1]=a[i]+1;
        }
        
    }
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='>')
        {
            a[i]=max(a[i],a[i+1]+1);
        }
    }

    ll ans=0;
    rep(i,n+1)
    {
        ans+=a[i];
    }
    cout<<ans;
}

Measured memory_bytes: 2820
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin >> N;
  double Q = 0.5000000000;
  double R = N;
  double ans = (N/2+1)/R;
  if(N%2==0){
    cout << fixed << setprecision(10);
    cout << Q << endl;
  }
  else{
    cout << fixed << setprecision(10);
    cout << ans << endl;
  }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  set<int> s;
  vector<int> x(3);
  rep(i, 3) {
    cin >> x[i];
    s.insert(x[i]);
  }
  cout << s.size() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long 
const int MAX = 510000;
const ll mod = 1000000007;
int main() {
  ll n;
  cin >> n;
  ll cn;
  ll res;
  if(n==1){
    cout << 0;
  }else{
    ll total = 1;
    ll znai = 1;
    ll knai = 1;
    ll rnai = 1;
    for(int i = 0;i<n;i++){
      total *= 10;
      total %= mod;
      znai *= 9;
      znai %= mod;
      knai *= 9;
      knai %= mod;
      rnai *= 8;
      rnai %= mod;
    }
    //cout << total << " " << znai <<knai << rnai<< endl;
    res = total + mod + mod - znai -knai +rnai;
    res %= mod;
       
    cout << res;
  }
}

Measured memory_bytes: 3604
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

typedef pair<int, int> P;
#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb1 push_back
#define mod 1000000007LL
#define INF 1234567890

const int maxn = 2e5 + 10;


//initialization here
//
ll dp[55][55][3000]; //i番目までのカードからj枚使って総和をkにできる総数
//
//initialization finish


// your function is here
//



//
// your function finished



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

	// your code is here
	//
	int n; cin >> n;
	ll pret,prea; cin >> pret >> prea;
	rep(i, n-1)
	{
		ll t, a;
		cin >> t >> a;
		ll bai = max((pret+t-1) / t, (prea+a-1) / a);
		if (bai == 0) {
			pret = t;
			prea = a;
			continue;
		}


		pret = t*bai;
		prea = a*bai;
		
	}

	Print(pret + prea);

	//
	// your code finished

	return 0;
}

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

int main(){
  int n, d;
  cin >> n >> d;
  double a, b;
  int res = 0;
  for(int i = 0; i< n; i++){
    cin >> a >> b;
    double x = a*a+b*b;
    if(sqrt(x) <= d) res++;
  }
  cout << res << endl;
}

Measured memory_bytes: 3748
# Mister様のblogを参考にいたしました
# https://misteer.hatenablog.com/entry/ARC094-D
Q = int(input())
for q in range(Q):
    A, B = map(int, input().split())
    A, B = min(A, B), max(A, B)

    ok, ng = 0, 10 ** 9 + 1
    while abs(ok - ng) > 1:
        K = (ok + ng) // 2
        m = (A + K) // 2

        # コーナーケース
        if K == A:
            m -= 1

        if m * (A + K - m) < A * B:
            ok = K
        else:
            ng = K

    print(A + ok - 2)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define D(x) cerr << #x << " = " << (x) << '\n'
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, max_w;
	cin >> n >> max_w;
	vector<ll> w(n), v(n), dp(max_w + 1, INT64_MIN);
	for(int i = 0; i < n; ++ i) cin >> w[i] >> v[i];
	dp[0] = 0;
	for(int i = 0; i < n; ++ i) {
		for(int j = max_w; j >= w[i]; -- j) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	cout << *max_element(all(dp)) << '\n';
}


Measured memory_bytes: 1024
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : list(map(int, stdin.readline().split()))
ni = lambda : int(sn())

n = ni()
xyz = [0] * n
for i in range(n):
  xyz[i] = an()

xyz.sort(key = lambda x: x[2])

sx, sy, sh = xyz[-1]
for Cy in range(101):
  for Cx in range(101):
    H = sh + abs(sx - Cx) + abs(sy - Cy)
    if all(h == max(H - abs(x - Cx) - abs(y - Cy), 0) for x, y, h in xyz):
      print(Cx, Cy, H)
      exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;
const int mod1=998244353;

bool cmp(pair<pair<string,int>,int> a,pair<pair<string,int>,int> b){
	if(a.first.first==b.first.first) return a.first.second>b.first.second;
	return a.first.first<b.first.first;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<pair<pair<string,int>,int>> s(n);
	rep(i,n){
		cin >> s.at(i).first.first >> s.at(i).first.second;
		s.at(i).second=i+1;
	}
	sort(s.begin(),s.end(),cmp);
	rep(i,n) cout << s.at(i).second << endl;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	public void run() throws Exception {
		Scanner sc = new Scanner();
		String S = sc.next();
		String T = sc.next();
		int n = S.length();
		boolean ans = true;
		int[] pre = new int[26];
		int[] next = new int[26];
		Arrays.fill(pre, -1);
		Arrays.fill(next, -1);
		for (int i = 0; i < n; ++i) {
			int ns = S.charAt(i) - 'a';
			int nt = T.charAt(i) - 'a';
			if (next[ns] != nt && next[ns] >= 0) {
				ans = false;
			}
			if (pre[nt] != ns && pre[nt] >= 0) {
				ans = false;
			}
			next[ns] = nt;
			pre[nt] = ns;
		}
		System.out.println(ans ? "Yes" : "No");
	}

	class Scanner {
		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() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -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 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();
			}
		}

		int nextInt() {
			return (int) nextLong();
		}
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 25812
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    long n = scan.nextLong();
    long count = 0;
    while (true){
      if (fast(count) > n){
        break;
      }
      count += 1;
    }
    System.out.println(fast(count)-1);
  }

  static long fast(long i){
    long ret = 1;
    long base = 2;
    while (i>0){
      if ((i & 1) == 1){
        ret *= base;
      }
      base = base*base;
      i >>= 1;
    }
    return ret;
  }
}


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

int main(int argc, char *argv[]) {
	char s[7];
	scanf("%s", s);
	int len = strlen(s);
	if (len > 1) {
		switch (s[0]) {
			case 'S':
				printf("Cloudy");
				break;
			case 'C':
				printf("Rainy");
				break;
			case 'R':
				printf("Sunny");
				break;
			default:
				break;
		}
	} else {
		switch (s[0]) {
			case 'S':
				printf("C");
				break;
			case 'C':
				printf("R");
				break;
			case 'R':
				printf("S");
				break;
			default:
				break;
		}
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
using Graph = vector<vector<int>>;
int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin>>s;
    int cnt=0;
    rep(i,s.size()/2){
        if(s[i]!=s[s.size()-1-i])cnt++;
    }
    cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    cout << x2 - (y2 - y1) << " ";
    cout << y2 + (x2 - x1) << " ";
    cout << x1 - (y2 - y1) << " ";
    cout << y1 + (x2 - x1) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main() {
	double A, B, H, M;
	scanf("%lf%lf%lf%lf", &A, &B, &H, &M);
	printf("%.15lf\n", sqrt(A * A + B * B - 2 * A * B * cos(M_PI / 6 * H + M_PI / (6 * 60) * M - M_PI / 30 * M)));
}


Measured memory_bytes: 2588
#include<iostream>
using namespace std;
int main()
{
    string x;int a=0;
    cin>>x;
    for(int i=0;i<x.size();i++)
    {
    	if(x[i]=='C')a=1;
    	if(x[i]=='F'&&a==1){cout<<"Yes";return 0;}
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
def main():
    # 下、右、上、左
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    H, W = map(int, input().split())
    s = [input() for i in range(H)]
    for y in range(H):
        for x in range(W):
            if s[y][x] == '.':
                continue
            cnt = 0
            for i, j in zip(dy, dx):
                ny = y + i
                nx = x + j
                if ny < 0 or H <= ny\
                        or nx < 0 or W <= nx\
                        or s[ny][nx] == '.':
                    continue
                cnt += 1
            if cnt == 0:
                print("No")
                return
    print("Yes")
    return


main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LI list<int>
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ff first
#define ss second
#define bg begin()
#define sf(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define sff(a,b) scanf("%d%d",&a,&b);
#define sfffl(a,b) scanf("%lld%lld",&a,&b);
#define nwln() printf("\n");
#define prd(a) printf("%d",a);
#define prld(a) printf("%lld",a);
#define space printf(" ");
#define ft cout<<"for test"<<endl;
#define read(v) for(auto &it:v)cin>>it;
#define PI 2*acos(0.0)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
    FIO;
    string s;
    cin>>s;
    (s=="ABC")?cout<<"ARC"<<endl:cout<<"ABC"<<endl;
}


Measured memory_bytes: 3564
var obj = init();
Main();
function nextInt(){return myconv(next(),1);}
function nextStrArray(){return myconv(next(),2);}//半角スペース分割
function nextIntArray(){return myconv(next(),4);}//半角スペース + 数値化
function nextCharArray(){return myconv(next(),6);}//1文字分割
function next(){return obj.next();}
function hasNext(){return obj.hasNext();}
function myin(){return require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");}
function init(){
  var inputFile = myin();
  var returnObj = {
    "list" : inputFile, "index" : 0, "max" : inputFile.length,
    "hasNext" : function(){return (this.index < this.max);},
    "next" : function(){if(!this.hasNext()){return "";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(t){console.log(t);}//標準出力
function myerr(t){console.error(t);}//標準エラー出力
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す　1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}
function Main(){
  var k = nextInt();
  var list = nextIntArray();
  if(list[k - 1] != 2){
    myout(-1);
    return;
  }
  var min = 2;
  var max = 3;
  for(var i = k - 1; i >= 0; i--){
    if(list[i] > max){
      myout(-1);
      return;
    }
    min = list[i] * Math.ceil(min / list[i]);
    max = list[i] * (Math.floor(max / list[i]) + 1) - 1;
    if(min > max){
      myout(-1);
      return;
    }
  }
  myout(min + " " + max);
}

Measured memory_bytes: 28248
// D - XOR World

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

ll g(ll k) {
	ll result = 0;
	for (int i=1; i<63; i++) {
		ll p = pow(2, i);
		ll n = (k + 1) / p * p / 2 + max(0LL, ((k + 1) % p) - p / 2);
		//cout << n << " " << (n % 2) * pow(2, i-1) << endl; // **** debug ****
		result += (n % 2) * pow(2, i-1);
	}
	//cout << k << " : " << result << endl; // **** debug ****
	return result;
}

ll f(ll A, ll B) {
	return g(B) ^ g(max(0LL, A-1));
}

int main() {
	ll A, B;
	cin >> A >> B;

	ll ans = f(A, B);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3992
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long ll;
typedef vector<bool>    vecbool;
typedef vector<int>     vecint;
typedef vector<ll>      vecll;
typedef vector<string>  vecstr;
typedef vector<vecint>  vec2int;
typedef vector<vecbool> vec2bool;
int dx[4] {-1,+1, 0, 0};
int dy[4] { 0, 0,-1,+1};
int cal(string s, char key){
  int i = 0;
  bool ok = true;
  while(true){
    // cout << s << endl;
    int m = s.size();
    ok = true;
    REP(i,m){
      if(s[i] != key){
	ok = false;
	break;
      }
    }
    if(ok)break;
    ////////////////
    string t = s.substr(0,m - 1);
    for(int j = 1; j < m - 1; j ++){
      if(t[j] == key) t[j - 1] = key;
    }
    s = t;
    i ++;
  }
  return i;
}
int main()
{
  string s; cin >> s;
  int n = s.size();
  int ans = 100;
  REP(i,n){
    ans = min(ans, cal(s,s[i]));
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int a, b, c, d, e, k;

  std::cin >> a >> b >> c >> d >> e >> k;

  std::cout << (e - a > k ? ":(" : "Yay!") << std::endl;

  return 0;
}


Measured memory_bytes: 632
from fractions import gcd
A, B = map(int, input().split())
g = gcd(A, B)
ans = 1
n = 2
while g > 1:
  if n * n > g:
    ans += 1
    break
  if g % n == 0:
    ans += 1
  while g % n == 0:
    g //= n
  n += 1
print(ans)


Measured memory_bytes: 77576
class UnionFind:

    def __init__(self, n):
        self.par = [-1] * n


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True


    def root(self, x):
        path = []
        while self.par[x] >= 0:
            path.append(x)
            x = self.par[x]
        for y in path:
            self.par[y] = x
        return x


    def same(self, x, y):
        return self.root(x) == self.root(y)


    def size(self, x):
        return -self.par[self.root(x)]


n, m, k = map(int, input().split())

friends = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].append(b)
    friends[b].append(a)

blocks = [[] for _ in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    blocks[c].append(d)
    blocks[d].append(c)

uni = UnionFind(n)
for i, v in enumerate(friends):
    for j in v:
        uni.unite(i, j)

for i in range(n):
    ans = uni.size(i) - len(friends[i]) - 1
    for block in blocks[i]:
        if uni.same(i, block):
            ans -= 1
    print(ans, end=' ')

Measured memory_bytes: 43520
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
    int n, m;
    int i, j;
    
    cin >> n >> m;
    
    m = 2*m;
    
    int a[m];
    int count[51] = {0};
    
    for(i = 0; i < m; i++) {
        cin >> a[i];
        count[a[i]]++;
    }
    
    for(j = 1; j <= n; j++) {
        cout << count[j] << "\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
x = int(input())

flag = 0

for a in range(x):
    b5 = a**5 - x
    for b in range(120):
        if abs(b5) == int(b**5):
            if b5 < 0:
                b = -b
            flag = 1
            break
    if flag:
        break

print(a, int(b))


Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M;
    cin >> N >> M;
    vi A(M);
    cin >> A;
    sort(all(A));

    int num[10] = {-1, 2,5,5,4,5,6,3,7,6};
    vector<int> dp(N + 10, -1);
    dp[0] = 0;
    rep(i, 0, N + 1) {
        if (dp[i] == -1) continue;
        rep(j, 0, M) {
            chmax(dp[i + num[A[j]]], dp[i] + 1);
        }
    }

    int x = N;
    string ans = "";
    rep(i, 0, dp[N]) {
        rrep(j, 0, M) {
            if (x - num[A[j]] >= 0 && dp[x - num[A[j]]] == dp[x] - 1) {
                ans += to_string(A[j]);
                x -= num[A[j]];
                break;
            }
        }
    } 
    cout << ans << endl;
    return (0^_^0);
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
//Optimisations
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("O2")
//shortcuts for functions
#define pb push_back
#define mp make_pair
#define ff first 
#define ss second
#define all(v) v.begin(),v.end()
#define prec(n) fixed<<setprecision(n)
#define n_l '\n'
// make it python 
#define gcd __gcd
#define append push_back
#define str to_string
// utility functions shortcuts
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sswap(a,b) {a=a^b;b=a^b;a=a^b;}
#define swap(a,b) {auto temp=a; a=b; b=temp;}
#define init(dp) memset(dp,-1,sizeof(dp));
#define set0(dp) memset(dp,0,sizeof(dp));
#define bits(x) __builtin_popcount(x)
#define SORT(v) sort(all(v))
#define endl "\n"
#define forr(i,n) for(ll i=0;i<n;i++)
// declaration shortcuts
typedef long long int ll;
#define int ll
// Constants
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr ll INF = 1999999999999999997; 
constexpr int inf= INT_MAX;
constexpr int MAXSIZE = int(1e6)+5;
constexpr auto PI  = 3.14159265358979323846L;
constexpr auto oo  = numeric_limits<int>::max() / 2 - 2;
constexpr auto eps = 1e-6;
constexpr auto mod = 998244353;
constexpr auto MOD = 1000000007;
constexpr auto MOD9 = 1000000009;
constexpr auto maxn = 100006;
//void IOfile(){
//freopen(file_name, reade_mode, stdin);
//freopen(file_name, write_mode, stdout);
//}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}

int fen[2*maxn];

void add(int ind, int val){
	for(int i = ind; i < 2 * maxn; i += ( i & ( - i))){
		fen[i] += val;
		fen[i] = (fen[i] + mod) % mod;
	}
}

int get(int ind){
	int res = 0;
	for(int i = ind; i > 0; i -= (i & ( -i))){
		res += fen[i];
		res = (res + mod) % mod;
	}
	return res;
}
int dp[2*maxn];

int32_t main(){
	fastio();
	int n;
	cin >> n;
	int k;
	cin >> k;
	vector<pair<int,int>>v;
	for(int i = 0; i < k; i++){
		int l,r;
		cin >> l >> r;
		v.push_back({l,r});
	}
	sort(all(v));
	dp[1] = 1;
	for(int  i = 1; i <= n; i++){
		if(i != 1) dp[i] = get(i);
		dp[i] = (dp[i] + mod) % mod;
		for(int j = 0; j < k; j++){
			if(v[j].ff + i <  2*maxn)
				add(v[j].ff + i , dp[i]);
			if(v[j].ss + i + 1 <  2 * maxn)
				add(v[j].ss + i + 1, -dp[i]);
		}
		//cout << dp[i] << "\n";
	}
	cout << get(n);
}

Measured memory_bytes: 6696
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i=(a); i<(n); ++i)
#define rrep(i,a,n) for(ll i=(a); i>(n); --i)
#define erep(i,a,n) for(ll i=(a); i<=(n); ++i)
#define rerep(i,a,n) for(ll i=(a); i>=(n); --i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp make_pair
#define sz(x) ((int) x.size())
#define print(X) cout << (X) << endl
#define _ << " " <<
static const int INF = 1e+9+7;
ll n,m,l;
str s,t;

int main(){

  cin >> n;
  vi vec;
  rep(i,0,n){
    int x;
    cin >> x;
    vec.pb(x);
  }

  vi vec_sort;
  vec_sort = vec;
  
  sort(all(vec_sort));

  int ans1 = vec_sort[n/2];
  int ans2 = vec_sort[n/2-1];

  rep(i,0,n){
    if(vec[i]>=ans1) print(ans2);
    else print(ans1);
  }


  return 0;
}





Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
string s;
vector<string> cand;
char a[22];
bool used[26];
void dfs(int k) {
    if(k == s.size()) {
        cand.push_back(string(a));
    } else {
        if(s[k] != 'z' && !used[s[k] - 'a']) {
            used[s[k] - 'a'] = true;
            a[k] = s[k] + 1;
            dfs(k + 1);
            used[s[k] - 'a'] = false;
        }
        if(s[k] == 'a' || used[s[k] - 'a' - 1]) {
            a[k] = s[k];
            dfs(k + 1);
        }
    }
}

int main(){
    while(cin >> s && s != "#") {
        a[s.size()] = '\0';
        cand.clear();
        dfs(0);
        sort(cand.begin(), cand.end());
        cout << cand.size() << endl;
        if(cand.size() <= 10) {
            for(string b : cand) {
                cout << b << endl;
            }
        } else {
            for(int i = 0; i < 5; i++) {
                cout << cand[i] << endl;
            }
            for(int i = 0; i < 5; i++) {
                cout << cand[cand.size() - 5 + i] << endl;
            }
        }
    }
    return 0;
}

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

const double PI = acos(-1);

int main()
{
    double a,b,x;
    std::cin>>a>>b>>x;
    x /= a;
    double res;

    if(x < a*b/2){
        res = atan2(2*x/b,b);
    }else{
        res = atan2(a,(a*b-x)*2.0/a);
    }
    res = res*180.0/PI;
    res = 90.0 - res;
    std::cout<<std::fixed<<std::setprecision(10)<<res<<std::endl;
}

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

typedef long long ll;

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

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int a,b,h;
	cin >> a >> b >> h;
	cout << (a+b)*h/2 << "\n";
	return 0;
}


Measured memory_bytes: 256
import math

a, b, x = [int(v) for v in input().split(' ')]


if a * a * b / 2.0 <= x:
    l = b - (x / (a * a))
    tan = l / (a / 2)
    print(math.degrees(math.atan(tan)))
else:
    tan = (2 * x) / (a * b * b)
    print(90-math.degrees(math.atan(tan)))

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<numeric>
#include<sstream>
#include<cmath>
using namespace std;

int main(){

  long long int a, b; cin >> a >> b;
  a--;
  a = max(0LL, a);

  vector<long long int> z;
  z.push_back(0);
  if(a%2 == 1) {
    if(a%4 == 1) z.push_back(1);
  }else{
    if(a%4 == 2) z.push_back(1);
    z.push_back(a);
  }
  if(b%2 == 1) {
    if(b%4 == 1) z.push_back(1);
  }else{
    if(b%4 == 2) z.push_back(1);
    z.push_back(b);
  }

  long long int ans = z[0];
  for(int i=1; i<z.size(); i++){
    ans = (ans ^ z[i]);
  }
  cout << ans << endl;

  return 0;
}


//


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main()
{
  long long int nn, mm;
  scanf("%lld %lld", &nn, &mm);
  for(int ii = 0;ii <= nn;ii++)
  {
    for(int jj = 0;jj <= nn - ii;jj++)
    {
      int kk = nn - ii - jj;
      if(kk >= 0 && mm == (long long int)(ii * 10000 + jj * 5000 + kk * 1000))
      {
        printf("%d %d %d\n", ii, jj, kk);
        return 0;
      }
    }
  }
  puts("-1 -1 -1\n");
  return 0;
}

Measured memory_bytes: 128
H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
for div in range(1<<(H-1)):
  ID = [0]*H
  g = 0
  for i in range(H):
    ID[i] = g
    if div>>i&1:
      g += 1
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)

Measured memory_bytes: 48732
import itertools

N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]

INF = 10**18
ans = INF

for ptn in itertools.product([0,1,2,3], repeat=N):
    x = [0] * 4
    MP = 0
    for take, length in zip(ptn, L):
        if take == 3:  # 使わない
            continue
        if x[take] != 0:
            MP += 10
        x[take] += length
    if x[0]==0 or x[1]==0 or x[2]==0:
        continue
    MP += abs(A-x[0])
    MP += abs(B-x[1])
    MP += abs(C-x[2])
    if ans > MP:
        ans = MP
print(ans)

Measured memory_bytes: 3064
import sys
n = int(input())
d = {}
lines = sys.stdin.readlines()
ans = [None] * n
for i in range(n):
    q, *arg = lines[i].split()
    if q == '0':    # insert
        d[arg[0]] = arg[1]
    elif q == '1':  # get
        ans[i] = d[arg[0]] if arg[0] in d else 0
    elif q == '2':  # delete
        if arg[0] in d:
            del d[arg[0]]

[print(x) for x in ans if x is not None]


Measured memory_bytes: 59572
#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
main() {
	int a, b, c, r;
	double d;

	scanf("%d %d", &a, &b);
	c = a / b;
	r = a % b;
	d = (double)a / (double)b;
	printf("%d %d %.5f\n", c, r, d);

	return 0;
}


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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB emplace_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

int main(){
    ll n;
    cin >> n;
    string c, tmp;
    cin >> c;
    tmp = c;
    sort(ALL(c));
    ll ans = 0;
    REP(i, n) if(c[i] != tmp[i]) ans++;
    cout << ans/2;
    return 0;
}

Measured memory_bytes: 3932