akhauriyash/Code-Regression huggingface dataset:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

dp = defaultdict(lambda x:-1)

def main():
	a,b,x = map(int,input().split())
	p = x / (a*a*b)
	if(p > 0.5):
		l = a*a*b - x
		t = 2*l / (a**2)
		print(math.degrees(math.atan(t/a)))
	else:
		l = x
		t = 2*l / (a*b)
		print(90-math.degrees(math.atan(t/b)))

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if temp%i==0:
			cnt=0
			while temp%i==0:
				cnt+=1
				temp //= i
			arr.append([i, cnt])

	if temp!=1:
		arr.append([temp, 1])

	if arr==[]:
		arr.append([n, 1])

	return arr

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()


Measured memory_bytes: 63980
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

c = input()
print(chr(ord(c)+1))

Measured memory_bytes: 38256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

template<typename t1, class t2>
void input(t1 count,t2* array) {
	for(t1 i = 0;i < count;i++) {
		cin >> array[i];
	}
}

template<typename t1, class t2>
void output(t1 count,t2 array) {
	for(t1 i = 0;i < count;i++) {
		cout << array[i].str;
		if(i != count - 1) cout << " ";
	}
	cout << endl;
}

class card{
public:
	char suit;
	int value;
	string str;
	card(string& s) {
		str = s;
		suit = s[0];
		s[0] = '0';
		value = atoi(s.c_str());
	}
	bool operator<(card& e) const {
		return this->value < e.value;
	}
};

void bubbleSort(int n,vector<card>& a) {
	for(int i = 0;i < n;i++) {
		for(int j = n-1;j > i;j--) {
			if(a[j] < a[j-1]) swap(a[j],a[j-1]);
		}
	}
}

void selectionSort(int n,vector<card>& a) {
	for(int i = 0;i < n;i++) {
		int m = i;
		for(int j = i+1;j < n;j++) if(a[j] < a[m]) m = j;
		if(m != i) swap(a[i],a[m]);
	}
}

bool isStable(vector<card>& a,vector<card>& b) {
	for(int i = 1;i <= 9;i++) {
		int ind[2] = {0,0};
		while(ind[0] != a.size() && ind[1] != b.size()) {
			while(a[ind[0]].value != i && ind[0] != a.size()-1) ind[0]++;
			while(b[ind[1]].value != i && ind[1] != b.size()-1) ind[1]++;
			if(a[ind[0]].suit != b[ind[1]].suit && a[ind[0]].value == i && a[ind[1]].value == i) return false;
			ind[0]++;
			ind[1]++;
		}
	}
	return true;
}

int main(int argc,char** argv) {
	int n;
	vector<card> a;
	cin >> n;
	string s;
	for(int i = 0;i < n;i++) {
		cin >> s;
		a.push_back(card(s));
	}
	vector<card> b = a,c = a;
	bubbleSort(n,b);
	output(n,b);
	if(isStable(a,b)) cout << "Stable" << endl;
	else cout << "Not Stable" << endl;
	selectionSort(n,c);
	output(n,c);
	if(isStable(a,c)) cout << "Stable" << endl;
	else cout << "Not stable" << endl;

}



Measured memory_bytes: 3236
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength

#素因数分解
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a



#X = str(input()).split()
#a = [int(x) for x in input().split()]


S = str(input())

ans = "x"

for i in range(len(S)-1):
  ans += "x"

print(ans)



Measured memory_bytes: 38636
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int sheep = sc.nextInt();
        int wolves  = sc.nextInt();

        if(wolves >= sheep) {
        	System.out.println("unsafe");
        }else {
        	System.out.println("safe");
        	}
        }
}

Measured memory_bytes: 35716
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;

#define MOD (1000000000+7)

int main(void)
{
	int n;

	while(scanf("%d", &n)==1)
	{
		vi c(1);
		vll x(200000+2);
		vll ans(n+1);

		scanf("%d", &c[0]);
		for(int i=1;i<n;i++)
		{
			int t;
			scanf("%d", &t);
			if(c.back()!=t) c.push_back(t);
		}

		n=c.size();

		ans[0]=1;
		for(int i=0;i<n;i++)
		{
			ll&mx=x[c[i]];
			ans[i+1]=(ans[i]+mx)%MOD;
			mx=(mx+ans[i])%MOD;
		}
		printf("%lld\n", ans[n]);
	}

	return 0;
}


Measured memory_bytes: 4472
import scala.io.{StdIn => in}

object Main extends App {
  val Array(n, c) = in.readLine.split(" ").map(_.toInt)
  val dcf = Iterator.continually(in.readLine)
    .take(c).map(_.split(" ").map(_.toInt)).toArray
  val pallet = Iterator.continually(in.readLine)
    .take(n).map(_.split(" ").map(_.toInt - 1)).toArray

  val table = Array.ofDim[Int](3,c)
  for {
    k <- 0 until c
    i <- 0 until n
    j <- 0 until n
  } {
    table((i+j)%3)(k) += dcf(pallet(i)(j))(k)
  }

  // debug(table.mkString(" "))

  def dfsEnum(d:Int, n:Int):Int = {
    // d進 n個列挙
    val enum = Array.ofDim[Int](n)
    var ret = Int.MaxValue
  
    def evalute():Unit = {
      if(enum.toSet.size == 3) {
        val res = 
          enum.indices.map(i => table(i)(enum(i))).sum
        ret = math.min(ret, res)
        // debug(enum.mkString(" "), " ", res)
      }
    }
  
    def dfs(cnt:Int):Unit = {
      if(cnt == n) evalute
      else {
        for(i <- 0 until c) {
          enum(cnt) = i
          dfs(cnt+1)
        }
      }
    }
  
    dfs(0)
    ret
  }

  val ans = dfsEnum(c,3)
  println(ans)

  def debug(any:Any*):Unit = {
    if(this.getClass.toString != "class Main$")
      println(any.mkString(" "))
  }
}

Measured memory_bytes: 47756
#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int MAXN = 200005;
const int MOD = 1000000007;

ll fact[MAXN],inv[MAXN],w[MAXN];
int u[MAXN],mn[MAXN],arr[MAXN];
map<int,int> mp[MAXN];

ll mod_pow(ll a,ll b,ll m){
	ll ans = 1;
	for(; b ; b >>= 1){
		if(b & 1) ans = ans * a % m;
		a = a * a % m;
	}
	return ans;
}

void pre(){
	fact[0] = 1; 
	for(int i=1;i<MAXN;i++) fact[i] = fact[i-1] * i % MOD;
	inv[MAXN-1] = mod_pow(fact[MAXN-1],MOD-2,MOD);
	for(int i=MAXN-2;i>=0;i--) inv[i] = inv[i+1] * (i+1) % MOD;
}

int root(int a) { return u[a] == a ? a : u[a] = root(u[a]); }

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	pre();
	ll n,x,y;
	cin >> n >> x >> y;
	for(int i=1;i<=n;i++) u[i] = i;
	int id = 0;
	w[0] = 2e9;
	for(int i=1;i<=n;i++){
		cin >> arr[i] >> w[i];
		if(w[i] < w[id]) id = i;
		if(w[i] < w[mn[arr[i]]]) mn[arr[i]] = i;
	}
	int id2 = 0;
	for(int i=1;i<=n;i++){
		if(arr[id] != arr[i] && w[id] + w[i] <= y) u[root(i)] = root(id); 
		if(w[mn[arr[i]]] + w[i] <= x) u[root(i)] = root(mn[arr[i]]);
		if(arr[id] != arr[i] && w[i] < w[id2]) id2 = i;
	}
	for(int i=1;i<=n;i++) if(arr[i] == arr[id] && w[id2] + w[i] <= y) u[root(i)] = root(id2);
	for(int i=1;i<=n;i++){
		mp[root(i)][arr[i]]++;
	}
	ll ans = 1;
	for(int i=1;i<=n;i++){
		ll cur = 0;
		for(auto j:mp[i]){
			ans = ans * inv[j.second] % MOD;
			cur += j.second;
		}
		ans = ans * fact[cur] % MOD;
	}
	cout << ans << '\n';
	return 0;
}


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

int main() {
    int N, X, Y; cin >> N >> X >> Y;
    vector< vector<int> > G(N+1);
    G[1].push_back(2);
    for (int i = 2; i < N; i++) {
        G[i].push_back(i+1);
        G[i].push_back(i-1);
    }
    G[N].push_back(N-1);
    G[X].push_back(Y);
    G[Y].push_back(X);
    vector<int> ans(N+1);
    queue<int> q;
    int tmp;
    for (int i = 1; i <= N; i++) {
        vector<int> check(N+1, -1);
        check[i] = 0;
        q.push(i);
        while(!q.empty()) {
            tmp = q.front(); q.pop();
            for (int j = 0; j < G[tmp].size(); j++) {
                if (check[G[tmp][j]] == -1) {
                    check[G[tmp][j]] = check[tmp] + 1;
                    ans[check[tmp] + 1]++;
                    q.push(G[tmp][j]);
                }
            }
        }
    }
    for (int i = 1; i < N; i++) {
        cout << ans[i]/2 << endl;
    }
}


Measured memory_bytes: 384
x, y =map( int,input().split())

listA = [1, 3, 5, 7 , 8 , 10 , 12]
listB = [4 , 6, 9, 11]
listC=[2]

if x in listA and y in listA:
    print("Yes")
    
elif x in listB and y in listB:
    print("Yes")
    
elif x in listC and y in listC:
    print("Yes")
    
else:
    print("No")

Measured memory_bytes: 3060
// dile a la jardinera que traigo flores

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define sz(x) int(x.size())
#define all(v) (v).begin(),(v).end()
#define trace(x) cout << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define FER(i,a,b) for(int i = int(a); i < int(b); ++i)
#define IFR(i,a,b) for(int i = int(a); i >= int(b); i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;


ll w[105],v[105],dp[105][100005];

int main(){
  fastio;
  ll n,W;
  cin>>n>>W;
  FER(i,1,n+1) cin>>w[i]>>v[i];
  FER(i,1,1e5+1) dp[0][i]=1e9+5;
  FER(i,1,n+1){
    FER(j,1,1e5+1){
      if(j-v[i]<0) dp[i][j]=dp[i-1][j];
      else
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]] + w[i]);
    }
  }
  ll ans=0;
  IFR(i,1e5,0){
    if(dp[n][i]<=W){
        ans=i;
        break;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 80128
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

dat=[A[i] for i in range(N)]
for i in range(1,N):
    dat[i]+=dat[i-1]

evenf=[0]*N
evenf[0]=A[0]%2
for i in range(1,N):
    t=A[i]%2
    if A[i]==0:
        t=2
    evenf[i]=min(evenf[i-1]+t,dat[i])

evenb=[0]*N
evenb[N-1]=A[-1]%2
for i in range(N-2,-1,-1):
    t=A[i]%2
    if A[i]==0:
        t=2
    if i!=0:
        evenb[i]=min(evenb[i+1]+t,dat[-1]-dat[i-1])
    else:
        evenb[i]=min(evenb[i+1]+t,dat[-1])

oddf=[0 for i in range(N)]
for i in range(1,N):
    t=(1+A[i])%2
    oddf[i]=min(oddf[i-1]+t,evenf[i])

ans=oddf[-1]
for i in range(N-1):
    ans=min(ans,evenb[i+1]+oddf[i])

print(ans)


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

long long int dp[51][51];
int main() {
int N, P; cin >> N >> P;
dp[0][0] = 1;
for(int i=0; i<N; i++) {
int val; cin >> val;
val %= 2;
for(int j=0; j<=N; j++) {
dp[i+1][j] += dp[i][j];
dp[i+1][j+val] += dp[i][j];
}
}

long long int ans = 0;
for(int i=0; i<=N; i++) {
if(i%2 == P) ans += dp[N][i];
}
cout << ans << endl;
return 0;
}

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

auto main() -> int
{
    std::string s;
    std::cin >> s;

    int_fast16_t ans[2] = { 0 };
    int_fast16_t idx = 0;

    for(int_fast16_t i = 0; i < s.length(); ++i)
    {
        if(s[i] == 'R')
        {
            ++ans[idx];
        }
        else
        {
            if(ans[idx] != 0) ++idx;
        }
    }

    std::cout << (ans[0] > ans[1] ? ans[0] : ans[1]) << std::flush;
    
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
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; }
using ll = long long;
using P = pair<ll, ll>;
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }

    void init(int n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for(int i = 0; i < n; ++i) {
            par[i] = i; rank[i] = 0; diff_weight[i] = SUM_UNITY;
        }
    }

    int find(int x) {
        if(par[x] == x) return x;
        else {
            int r = find(par[x]);
            diff_weight[x] += diff_weight[par[x]];  // 累積和を取る
            return par[x] = r;
        }
    }

    Abel weight(int x) {
        find(x);
        return diff_weight[x];
    }

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

    bool unite(int x, int y, Abel w) {
        w += weight(x); w -= weight(y); // xとyそれぞれについて、rootとの重み差分を補正
        x = find(x); y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y]) swap(x, y), w = -w;   // rank[x] >= rank[y]になるようにswap
        if(rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w; // xがyの親になるので、xとyの差分をdiff_weight[y]に記録
        return true;
    }

    // 重みを取得する
    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

int n, m;

int main() {
    while(1) {
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        UnionFind<int> uf(n);
        for(int i = 0; i < m; ++i) {
            char c;
            int a, b, w;
            cin >> c >> a >> b;
            a--; b--;
            if(c == '!') {
                cin >> w;
                uf.unite(a, b, w);
            }else {
                if(uf.same(a, b)) cout << uf.diff(a, b) << endl;
                else cout << "UNKNOWN" << endl;
            }
        }
    }
}


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

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

    queue<int64_t> x;
    int count = 0;
    for (auto i = 1; i < 10; i++) {
        x.push(i);
        count++;
        if(count == k) {
            cout << i << endl;
            return 0;
        }
    }

    while(true){
        int64_t old = x.front();
        x.pop();
        for (auto i = old % 10 - 1; i <= old % 10 + 1; i++) {
            if(i < 0 or i >= 10) continue;
            x.push(old * 10 + i);
            count++;
            if(count == k) {
                cout << old * 10 + i << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 768
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

###具体例###
for _ in range(m):
    x, y, z = [int(x) for x in input().split()]
    unite(x - 1, y - 1)

A = set()

for i in range(n):
    A.add(find(i))

print(len(A))



Measured memory_bytes: 66652
import bisect


def sieve(n):
    a = range(n)
    a[0], a[1] = None, None
    for i in range(2, n):
        if i ** 2 >= n:
            break
        if a[i] is None:
            continue
        for j in range(i ** 2, n, i):
            a[j] = None
    j = 0
    for i in range(n):
        if a[i] is not None:
            a[j] = a[i]
            j += 1
    return a[0:j]

a = sieve(1000000)

try:
    while True:
        print bisect.bisect_right(a, int(raw_input()))
except:
    pass

Measured memory_bytes: 83740
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
using pli=pair<int64_t, int>;
using mii=map<int, int>;

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    if (N % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }
    if (S.substr(0, N / 2) == S.substr(N / 2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 888
def Solve(T):
	H = set()
	T = tuple(T)
	N = 0
	while True:
		if T in H:
			N = -1
			break
		if (T[0] | T[1] | T[2]) & 1:
			break
		H.add(T)
		T = ( (T[1] + T[2]) >> 1, (T[2] + T[0]) >> 1, (T[0] + T[1]) >> 1)
		N += 1
	print(N)

Solve([int(i) for i in input().split()])

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n,m,ans;
	cin>>n>>m;
	int minn=0,maxx=n+1;
	vector<int> l(m), r(m);
	for(int i=0; i<m; i++){
		cin>>l[i]>>r[i];
		minn=max( minn, l[i] );
		maxx=min( maxx, r[i] );
	}
	ans=max(0, maxx-minn+1);
	cout<<ans<<"\n";
	return 0;
}


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

int main(){
	int n,m,x,a[105];
  	cin>>n>>m>>x;
  	for(int i=0;i<m;i++){
		cin>>a[i];
    }
  	sort(a,a+m);
    int ans1=0,ans2=0;
  	for(int i=0;i<m;i++){
      if(a[i]<x) ans1++;
      if(a[i]>x) ans2++;
    }
  	
 	cout<<min(ans1,ans2);
}

Measured memory_bytes: 256
/**
*    created: 27.06.2020 00:54:58
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcountll(bit)
#define mod 1000000007
#define pi acos(-1.0)
using namespace std;
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<int> s(n+1);
    rep(i,m) {
        int a;
        cin >> a;
        s[a] = -1;
    }
    //-1のところには遷移しないようにdp
    vector<int> dp(n+1);
    dp[0] = 1;
    rep(i,n) rep2(t,i+1,min(n,i+2)+1) if (s[t] == 0) {
        dp[t] += dp[i];
        dp[t] %= mod;
    }
    cout << dp[n] << endl;
    return 0;
}

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


//unionfind
//init: union_find name(size)

class union_find{
private:
    //根にはグループの要素数に-1をかけたもの、それ以外には根の値
    //初期値は-1
    vector<int> uni;
public:
    //Constructer
    //uniを必要なサイズで初期化する、初期値は―1
    union_find(int unisize) : uni(unisize,-1){}

    //引数aの根を求める、なければaを根として返す
    int root(int a){
        if(uni[a] < 0) return a;
        return uni[a] = root(uni[a]);  
    }

    //頂点aとbを繋ぐ関数unite
    //戻り値：
    //  元々同じグループであればfalse
    //  連結に成功すればtrue
    bool unite(int a, int b){
        //a, bにそれぞれが属するグループの根を入れる
        //uni[a], uni[b]がa, bがそれぞれが属するグループのサイズになる
        a = root(a);
        b = root(b);
        if(a == b) return false;
        if(uni[a] > uni[b]) swap(a,b); //bの方を大きいものにする
        uni[a] += uni[b];
        uni[b] = a; //大きい方のグループに属するものの親を小さいものの根にする(rootが高速で動くようになる)
        return true;
    }
    //頂点aとbが同じグループかを調べる
    bool isConnected(int a, int b){
        return root(a) == root(b);
    }
    //頂点aを含むグループの頂点数を調べる
    int unisize(int a){
        return -uni[root(a)];
    }
    //グループ数を調べる
    int group_num(void){
        int num = 0;
        int s = uni.size();
        for(int i = 0; i < s; i++) if(uni[i] < 0) num++;
        return num;
    }
};


int main(){
    int n, m; cin >> n >> m;
    vector<int> x(m),y(m); int z;
    union_find u(n);
    rep(i,m){
        cin >> x[i] >> y[i] >> z;
        x[i]--; y[i]--;
        u.unite(x[i],y[i]);
    }
    cout << u.group_num() << endl;
}

Measured memory_bytes: 1408
h,w,d=map(int,input().split())
l=[[0,0]]+[[]for _ in range(h*w)]
for i in range(h):
    for j,a in enumerate(map(int,input().split())):
        l[a]=[i,j]
for i in range(h*w+1):
    if i<d:
        l[i].append(0)
    else:
        a,b=l[i]
        x,y,v=l[i-d]
        l[i].append(abs(x-a)+abs(y-b)+v)
for _ in range(int(input())):
    a,b=map(int,input().split())
    print(l[b][2]-l[a][2])

Measured memory_bytes: 19568
n = gets.to_i

as = []
largest = second_largest = 0

n.times do
  a = gets.to_i

  if a > largest
    largest = a
  elsif a > second_largest
    second_largest = a
  end

  as.push(a)
end

as.each do |a|
  puts a < largest ? largest : second_largest
end


Measured memory_bytes: 5172
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

typedef long long ll;
const ll INF = 1e18;

int main(int argc, char* argv[])
{
  std::string str;
  std::string::iterator it;
  std::cin >> str;

  std::string ans(3, '1');
  for (ll i = 0; i < 3; i++) {
    ans[i] = str[i] == '1' ? '9' : '1';
  }

  std::cout << ans << std::endl;
  
  return 0;
}


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

using namespace std;

#define INF ((1<<30)-1)  //int32_t
#define MOD 1000000007
#define MOD2 98

#define all(a)  (a).begin(),(a).end()

#define mkp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int modpower(int x,int n,int m){
    long long result=x;
    long long ans=1;
    int ans_int;

    while (n!=0){
        if(n%2==0){

            result = ((result%m)*(result%m))%m;
            n >>= 1;

        }else{
            ans = ((ans%m) * (result%m))%m;
            --n;

        }
    }
    ans_int=ans%m;
    return ans_int;
}


int modmul(int p,int q,int m){
    long long ans,pp=p,qq=q;
    int ans_int;
    ans=((pp%m)*(qq%m))%m;
    ans_int=ans%m;
    return ans_int;
}

int moddiv(int p,int q,int m){
    return modmul(p,modpower(q,m-2,m),m);
}

vector<int> modfact(int x,int m){
    vector<int> fact(x+1);
    fact[0]=1;
    
    for(int i = 1; i <= x; i++){
        fact[i] = modmul(fact[i-1],i,m);
    }

    return fact;
}

int modcomb(int n,int r,int m,vector<int> fact){  //aaaaa
    long long ans;
    int ans_int;

    int a = fact[n];
    int div = modmul(fact[r],fact[n-r],m);

    ans_int = moddiv(a,div,m);

    return ans_int;
}

int main(){

    bool flag=false;

    int ans=1,sum=0;

    int n,m,p;
    cin >>n>>m;
    vector<int> fact = modfact(n + 64,MOD);

    map<int,int> div;


    p = m;
    for (int i = 2; i <= sqrt(m); i++){
        while(p%i == 0){
            p /= i;
            div[i]++;
        }
    }

    if(p > 1){
        div[p]++;
    }
    
    for(auto d:div){
        int mul = modcomb(n + d.second - 1,d.second,MOD,fact);
        
        //cout <<d.first<<":"<<d.second<<"  " <<endl;
        //cout <<"mul = "<<mul<<endl;;

        ans = modmul(ans,mul,MOD);
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 1036
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rlcfpoj(x) scanf("%I64d",&x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define plcfpoj(x) printf("%I64d",x)
#define lfd() printf("\n")
#define sp() printf(" ")
#define inrep(x) int x;scanf("%d",&x);while(x--)
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
int n,u,v;
int dist1[100100],dist2[100100];
vector<int> ga[100100];
void dfs1(int u,int p){
	dist1[u]=dist1[p]+1;
	for(int i=0;i<ga[u].size();i++){
		int v=ga[u][i];
		if(v!=p)
			dfs1(v,u);
	}
}
void dfs2(int u,int p){
	dist2[u]=dist2[p]+1;
	for(int i=0;i<ga[u].size();i++){
		int v=ga[u][i];
		if(v!=p)
			dfs2(v,u);
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		ga[u].push_back(v);
		ga[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(n,0);
	int snuke=0,fennec=0;
	for(int i=1;i<=n;i++){
		if(dist1[i]<=dist2[i])
			fennec++;
		else
			snuke++;
	}
	if(snuke>=fennec)
		cout<<"Snuke"<<endl;
	else
		cout<<"Fennec"<<endl;
	return 0;
}


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

#define dbg(x) cerr << #x"=" << x << endl;
typedef long long LL;
LL K,A,B;

int main(){
    //freopen("in.txt", "r", stdin);
    cin >> K >> A >> B;
    LL ans = 0;
    if(A >= B){
        ans = K+1;
    } else {
        // A+1 >= B-A
        if((A+1) >= B){
            ans = K+1;
        } else {
            if(K < (A+1)){
                ans = K+1;
            } else { // 换第一次
                ans += B;
                K -= (A+1);
                LL t = K / 2LL;
                ans += t * (B-A);
                ans += K - t*2LL;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = (1 << 30);
vector<long long> d;
int solve(int pos, long long cur) {
	if (pos == d.size()) return -inf;
	if (cur == 1) return 0;
	int ret = solve(pos + 1, cur);
	if (cur % d[pos] == 0) ret = max(ret, solve(pos, cur / d[pos]) + 1);
	return ret;
}
int main() {
	long long n;
	cin >> n;
	for (int i = 1; i <= 18; ++i) {
		for (int j = 0; j < (1 << i) - 1; ++j) {
			long long cur = 0;
			for (int k = 0; k < i; ++k) {
				cur = cur * 10 + (((j >> k) & 1) ? 8 : 2);
			}
			if (n % cur == 0) {
				d.push_back(cur);
			}
		}
	}
	int ans = solve(0, n);
	cout << (ans >= 0 ? ans : -1) << endl;
	return 0;
}


Measured memory_bytes: 3164
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons;
import std.math, std.numeric;

void main() {
    int n, q; scan(n, q);

    auto uf = UnionFind(n);

    foreach (_ ; 0 .. q) {
        int com, x, y; scan(com, x, y);
        if (com == 0) {
            uf.merge(x, y);
        }
        else {
            writeln(uf.same(x, y) ? 1 : 0);
        }
    }
}


struct UnionFind {
    private {
        int _size;
        int[] _parent;
    }

    this(int N) 
    in {
        assert(N > 0);
    }
    body {
        _size = N;
        _parent = new int[](_size);
        foreach (i ; 0 .. _size) {
            _parent[i] = i;
        }
    }

    int findRoot(int x)
    in {
        assert(0 <= x && x < _size);
    }
    body {
        if (_parent[x] != x) {
            _parent[x] = findRoot(_parent[x]);
        }

        return _parent[x];
    }

    bool same(int x, int y)
    in {
        assert(0 <= x && x < _size);
        assert(0 <= y && y < _size);
    }
    body {
        return findRoot(x) == findRoot(y);
    }

    void merge(int x, int y)
    in {
        assert(0 <= x && x < _size);
        assert(0 <= y && y < _size);
    }
    body {
        int u = findRoot(x);
        int v = findRoot(y);

        if (u == v) return;

        _parent[v] = u;
    }
}





void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}



Measured memory_bytes: 3460
N = int(input())
pref = 'MARCH'
D = {}
for _ in range(N):
    s = input()
    if s[0] in pref:
        if s[0] in D:
            D[s[0]] += 1
        else:
            D[s[0]] = 1

lst = list(D.keys())
if len(lst) < 3:
    print(0)
    exit()
ans = 0
for i in range(len(lst)-2):
    for j in range(i+1, len(lst)-1):
        for k in range(j+1, len(lst)):
            ans += D[lst[i]] * D[lst[j]] * D[lst[k]]

print(ans)


Measured memory_bytes: 43624
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, pdb
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf, eps, mod = 10 ** 20, 1.0 / 10**10, 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def _cumsum(l): return list(itertools.accumulate(l)) 
"""
なかのものと端のもの
両端が一緒かどうか
一緒なら、K-1個変える
中を変える/2切り下げ
まず、端が一緒か
"""
S = input()
K = _I()
ans = 0

if len(set(S)) == 1:
    print(int(math.floor(len(S)*K/2)))
    exit()

S2 = S*2
S3 = S*3

torn_list_1 = []
previous = 'hoge'
for s in S2:
    if s == previous:
        torn_list_1[-1] += 1
    else:
        torn_list_1.append(1)
        previous = s
torn_list_2 = []
previous = 'hoge'
for s in S3:
    if s == previous:
        torn_list_2[-1] += 1
    else:
        torn_list_2.append(1)
        previous = s

ans2 = 0
ans3 = 0
for t in torn_list_1:
    if t>=2:
        ans2+=int(math.floor(t/2))

for t in torn_list_2:
    if t>=2:
        ans3+=int(math.floor(t/2))

diff = ans3-ans2

ans = ans2 + (K-2)*diff
print(ans)


Measured memory_bytes: 77548
#include <iostream>
using namespace std;
int N;
int main() {
    cin>>N;
    if(N>=64)
        cout<<64<<endl;
    else if(N>=32)
        cout<<32<<endl;
    else if(N>=16)
        cout<<16<<endl;
    else if(N>=8)
        cout<<8<<endl;
    else if(N>=4)
        cout<<4<<endl;
    else if(N>=2)
        cout<<2<<endl;
    else
        cout<<1<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_multiset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
//find_by_order(k) - k is the kth element of the multiset
//order_of_key(k) - Number of elements striclty samller than k
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,l;
    cin>>n>>l;
    ll arr[n+1];
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        arr[i]=l+i-1;
        sum+=arr[i];
    }
  //  cout<<sum<<endl;
    ll mmin=10000000000;
    ll ans;
    for(int i=1;i<=n;i++)
    {
        ll x=sum-arr[i];
     //   cout<<x<<endl;
        if(abs(sum-x)<=mmin)
        {
         //   cout<<"here "<<sum-x<<" "<<mmin<<endl;
            mmin=abs(sum-x);
            ans=x;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
s=list(input())
for i in range(len(s)):
    if s[i] == "?":
        s[i] = "D"
#s.replace('?', 'D')
l = ""
for i in s:
    l += i
t = l.count('D')
t += l.count('PD')
#print(t)
print(l)

Measured memory_bytes: 10836
fun main() {
    val (h, w, k) = readInts()

    val grid = Array(h) { readLine()!! }

    var ans = 0
    for (cX in 0 until (1 shl w)) {
        for (cY in 0 until (1 shl h)) {

            var s = 0
            for (x in 0 until w) {
                for (y in 0 until h) {
                    if (cX and (1 shl x) == 0 && cY and (1 shl y) == 0 && grid[y][x] == '#') s++
                }
            }

            if (s == k) ans++
        }
    }
    println(ans)
}

private fun readInt() = readLine()!!.toInt()
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }
private fun readLongs() = readLine()!!.split(" ").map { it.toLong() }


Measured memory_bytes: 36744
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define N 100010
ll n,s[N];
ll solve(ll k){
  vector<ll> L,R;
  for(int i=0;i<n;i+=k)L.push_back(s[i]);
  for(int i=n-1;i>=0;i-=k)R.push_back(s[i]);
  ll ans=0,sum=0;
  for(int i=0;i<L.size()&&i<R.size();i++){
    if(((n-1-i*k)%k==0&&(n-1-i*k)<=i*k)||n-1-i*k<=k)break;
    sum+=L[i]+R[i];
    ans=max(ans,sum);
  }
  return ans;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>s[i];
  ll ans=0;
  for(int k=1;k<n;k++){
    ans=max(ans,solve(k));
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3316
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;

vi p(100001);

int getp(int v) {
  if (p[v] == v) return v;
  return p[v] = getp(p[v]);
}

void join(int a, int b) {
  a = getp(a);
  b = getp(b);
  if (rand() % 2) swap(a, b);
  p[a] = b;
}

int main() {
  for (int i = 0; i < p.size(); ++i) p[i] = i;
  int n, m;
  while (cin >> n >> m) {
    vector<vii> c(1000001);
    for (int i = 0; i < m; ++i) {
      int a,b,col;
      cin >> a >> b >> col;
      --a; --b;
      c[col].push_back(pii(a,b));
    }
    map<pii, int> ind;
    vvi g(n), gr;
    for (int i = 0; i < c.size(); ++i) {
      vi ts;
      for (pii x : c[i]) {
        ts.push_back(x.first);
        ts.push_back(x.second);
        join(x.first, x.second);
      }
      sort(ts.begin(), ts.end());
      ts.resize(unique(ts.begin(), ts.end()) - ts.begin());
      for (int v : ts) {
        pii x(getp(v), i);
        if (!ind.count(x)) {
          ind[x] = gr.size();
          gr.push_back(vi());
        }
        gr[ind[x]].push_back(v);
        g[v].push_back(ind[x]);
//        cerr << v << ' ' << ind[x] << ' ' << p[v] << ' ' << i << endl;
      } 
      for (int v : ts) {
        p[v] = v;
      }
    }
    vi d(gr.size(), 1e9);
    vi was(n, 0);
    vi q;
    for (int v : g[0]) {
      d[v] = 1;
      q.push_back(v);
    }
    for (int it = 0; it < q.size(); ++it) {
      int v = q[it];
      for (int x : gr[v]) {
        if (was[x]) continue;
        was[x] = 1;
        for (int nv : g[x]) {
          if (d[nv] > d[v] + 1) {
            d[nv] = d[v] + 1;
            q.push_back(nv);
          }
        }
      }
    }
    int res = 1e9;
    for (int v : g[n-1]) {
      res = min(res, d[v]);
    }
    if (res <= n) cout << res << endl;
    else cout << -1 << endl;
  }
  return 0;
}

Measured memory_bytes: 62252
#include <complex>
#include <cmath>
#include <stdio.h>
using namespace std;
typedef complex<double> xy_t;

xy_t P[110];

double cross_product(xy_t a, xy_t b){
	return (conj(a)*b).imag();
}

int main(){
	int N = 0;
	double x, y;
	while (~scanf("%lf,%lf", &x, &y)) {
		P[N++] = xy_t(x,y);
	}
	double sum = 0.0;
	for (int i = 0; i+2 < N; i++) {
		xy_t a = P[0], b = P[i+1], c = P[i+2];
		sum += (cross_product(a-b,c-b))/2;
	}
	printf("%.6f\n",abs(sum));
}
 

Measured memory_bytes: 1088
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
const int N=2e5+5;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a>0){
		printf("Positive\n");
		return 0;
	}
	if(a<=0&&b>=0){
		printf("Zero\n");
		return 0;
	}
	if(a<0){
		int x=b-a;
		if(x%2==0){
			printf("Negative\n");
			return 0;
		}
		else{
			printf("Positive\n");
			return 0;
		}
	}
	assert(false);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, x, n) for(int i = x; i < n; i++)
#define repr(i, x, n) for(int i = x; i > n; i--)
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define yes puts("YES")
#define no puts("NO")
#define PI 3.141592653589793238462643383279
const long long iinf = INT64_MAX - 1;
const int inf = INT32_MAX - 1;
const int MOD = (1e6+3);
int dir4[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int dir8[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int knight[8][2] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};
using namespace std;

void solve()
{
    int h[2], s[2];
    cin >> h[0] >> s[0] >> h[1] >> s[1];
    for(int i = 0; i <= 200; i++){
        int rem = i % 2;
        h[!rem] -= s[rem];
        if(h[!rem] <= 0){
            if(rem == 0) cout << "Yes";
            else cout << "No";
            return;
        }
    }

}
#define testcases 0             // 0 -> no test case. 1 -> test case
int main()
{
	int t = 1;

    if(testcases) cin >> t;

	// int i = 1;
	while(t--){
	// cout << "Case #" << i++ << ": \n";
	solve();
	// if(t)printf("\n");
	}
	return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>


int prime(int num) {
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    int i;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0)return 0;
    }
    return 1;
}

int main(){
    int n,i,p,count,j;
    count=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&p);
        j=prime(p);
        if(j==1) count++;
    }
    printf("%d",count);
    printf("\n");
    return 0;
}



Measured memory_bytes: 2040
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<P,int>
#define vpp vector<PP>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    string t;
    cin>>t;
    int ans=0;
    REP(i,t.size()){
        if(t[i]=='1')ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, start, n) for (ll i = (ll)(start); i < (ll)(n); ++i)
static const ll INFTY = 1L << 62L;
ll solver()
{
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll d,t,s;
cin>>d>>t>>s;
if(s*t>=d)cout<<"Yes\n";
else{
    cout<<"No\n";
}
}

Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


template<typename T>
class CumulativeSum{
public:
  int n;
  vector<T> sum;
  vector<T> A;
  int added;
  CumulativeSum():n(-1),added(0){}
  CumulativeSum(int n):n(n), sum(n+1), A(n+1),added(0){}
  CumulativeSum(const vector<T> &B):n(B.size()), sum(n+1), A(n+1),added(0){
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + B[i-1];
  }

  void apply(){
    for(int i=1;i<=n;i++) A[i] = A[i] + A[i-1];
    for(int i=1;i<=n;i++) A[i] = A[i] + A[i-1];
    for(int i=1;i<=n;i++) sum[i] = sum[i] + A[i-1];
    added = 0; A.clear(); A.resize(n+1);
  }

  //[l, r)にxを加算
  void add(int l, int r, T x){
    added = 1;
    assert(l <= r && 0 <= l && r <= n);
    A[l] = A[l] + x;
    A[r] = A[r] - x;
  }

  //[l, r)の和を得る
  T get(int l,int r){
    assert(l<=r && 0<=l && r<=n);
    if(added) apply();
    return sum[r] - sum[l];
  }
};


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N ,M;
  cin>>N>>M;
  CumulativeSum<int> sum(N);

  for(int i=0;i<M;i++){
    int l, r;
    cin>>l>>r; l--, r--;

    sum.add(l, r + 1, 1);
  }

  int ans = 0;
  for(int i=0;i<N;i++) if(sum.get(i, i+1) == M) ans++;

  cout<<ans<<endl;
    

  return 0;
}


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

int main(){
   int n,x,y; cin >> n >> x >> y;
   vector<int> A(n*(n+1)/2);
   int cnt = 0;
   map<int,int> ans;
   for(int i = 1; i <= n; i++){
       for(int j = i+1; j <= n; j++){
           A[cnt] = min((j-i),(abs(x-i)+1+abs(j-y)));
           if(ans.count(A[cnt])){
           ans.at(A[cnt])++;
       }else{
           ans[A[cnt]] = 1;
       }
       cnt++;
       }
   }

   for(int i = 1; i < n; i++){
       if(ans.count(i)){
           cout << ans.at(i) << endl;
       }else{
           cout << 0 << endl;
       }
   }
}




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

using namespace std;

inline void Boost() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
typedef long long int ll;
typedef long double ld;

int main() {
	Boost();

	int n; cin >> n;
	int par = 0;
	vector < pair < ll, ll > > v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i].first >> v[i].second;
		par += abs(v[i].first + v[i].second) % 2;
	}

	if (par != 0 && par != n) {
		cout << -1;
		return 0;
	}

	int m = 35 + (par == 0);
	vector < ll > pwr(m);
	
	if (par == 0) {
		pwr[0] = 1;
	}

	ll P = 1;
	for (int i = (par == 0); i < m; ++i, P *= 2) pwr[i] = P;

	cout << m << "\n";
	for (auto x : pwr) cout << x << " ";
	cout << "\n";

	for (int i = 0; i < n; ++i) {
		ll x, y;
		x = y = 0;

		string moves = "";
		for (int j = m - 1; j >= 0; --j) {
			if (abs(x - v[i].first) >= abs(y - v[i].second)) {
				if (x - v[i].first < 0) {
					moves += "R";
					x += pwr[j];
				} else {
					moves += "L";
					x -= pwr[j];
				}
			} else {
				if (y - v[i].second >= 0) {
					moves += "D";
					y -= pwr[j];
				} else {
					moves += "U";
					y += pwr[j];
				}
			}
		}
		reverse(moves.begin(), moves.end());
		cout << moves << "\n";
	}
	return 0;
}

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

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

    int n, m;
    cin >> n >> m;
    string a[n], b[m];
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];

    bool flg = false;

    rep(i, n-m+1){
        rep(j, n-m+1){
            string sub = a[i].substr(j, m);

            if(sub == b[0]){
                flg = true;
                rep(k, m){
                    sub = a[i+k].substr(j, m);

                    if(sub == b[k]) flg = flg && true;
                    else flg = false;
                }
                if(flg) {
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
}

Measured memory_bytes: 256