akhauriyash/Code-Regression huggingface dataset:
//
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define ll long long
#define DE(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG(a) DE("DEBUG: %d\n",a)
int read() {
	int x=0,f=1,ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=10+10;

char s[MAXN];
int a[MAXN],len;
ll ans;

ll calc() {
	ll x=0,b=0;
	a[len]=1;
	REP(i,1,len) {
		if(!a[i]) x=x*10+s[i]-'0';
		else {x=x*10+s[i]-'0';b+=x;x=0;}
	}
	return b;
}

int count() {
	int x=0;
	REP(i,1,len-1) x=x*2+a[i];

	return x;
}

int len2,have[10000+10];

void dfs(int k) {
	if(k>len) return ;

	if(!have[count()]) {
		//REP(i,1,len) printf("%d ",a[i]);
		//puts("");
		have[count()]=1;

		ans+=calc();
	}

	for(int i=0; i<=1; i++) {
		a[k]=i;
		dfs(k+1);	
	}
}

int main() {
	scanf("%s",s+1);
	len=strlen(s+1);
	len2=len-1;
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
import bisect,copy,heapq,itertools,string
from collections import *
from math import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

w,h,x,y = MAP()
print(w*h/2, 1 if x==w/2 and y==h/2 else 0)

Measured memory_bytes: 10120
N,X = gets.strip.split.map(&:to_i)
bounds = gets.strip.split.map(&:to_i)

state = []
state[0] = 0
count = 0

N.times do |i|
    state[i+1] = bounds[i] + count
    count = state[i+1]
end

result = 0

state.length.times do |m|
    if state[m] <= X
        result += 1
    end
end

puts result

Measured memory_bytes: 1788
import sys

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


table = [0]*26

letters = "abcdefghijklmnopqrstuvwxyz"
input_str = sys.stdin.read()

for A in input_str:
    index = 0
    for B in letters:
        if A == B or A == B.upper():
            table[index] += 1
            break
        index += 1

for i in range(len(letters)):
    print("%s : %d"%(letters[i],table[i]))



Measured memory_bytes: 5572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	int a,b,c;
	cin>>a>>b>>c;
	if((c>a && c<b) || (c>b && c<a))
		cout<<"Yes";
	else
		cout<<"No";

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for(ll (i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for(ll (i) = (m); (i) < (n); (i)++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

int main()
{	
    string s;
    cin >> s;
    int l = s.size();
    vector<ll> v(l+1, 0);
    
    REP(i, l){
        if(s[i] == '<'){
            v[i+1] = v[i]+1;
        }
    }
    
    REPR(i, l-1){
        if(s[i] == '>'){
            v[i] = max(v[i], v[i+1]+1);
        }
    }

    ll ans = 0;
    for (ll x : v) ans += x;
    
    cout << ans << endl;
}


Measured memory_bytes: 7600
#include <iostream>
using namespace std;
int main(){
 int a, b, x[100][100], y=0, z[100], n=0;
 cin >> a >> b;
 for(int h=0; h<a; h++){
  for(int i=0; i<b; i++){
   cin >> x[h][i];
  }
 }
 for(int j=0; j<a; j++){
  for(int k=0; k<b; k++){
   cout << x[j][k] << ' ';
   if(k > 0)
    y += x[j][k];
   else
    y = x[j][k];
   if(j > 0)
    z[k] += x[j][k];
   else
    z[k] = x[j][k];
  }
  cout << y;
  y = 0;
  cout << endl;
 }
 for(int l=0; l<b; l++){
  cout << z[l] << ' ';
  n += z[l];
 }
 cout << n << endl;
 return 0;
}

Measured memory_bytes: 3148
a,b=map(int, input().split()) 
x=b-a+1

if a%2==0:
    if x%2==0:
        if x//2%2==0:
            print(0)
        else:
            print(1)
    
    else:
        if (x-1)//2%2==0:
            print(b)
        
        else:
            print(b^1)

else:
    if (x-1)%2==0:
        if (x-1)//2%2==0:
            print(a)
        else:
            print(a^1)
    else:
        if (x-2)//2%2==0:
            print(a^b)
        else:
            print(a^b^1)
        
    
    
        
    
    

        
        
        


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

ll modfact(ll n){
    ll ans = 1;
    for (ll i = 1; i <= n; i++){   
        ans *= i;
        ans %= MOD;
    }
    return ans;
}

ll modcomb(ll n, ll k){
    ll tmp = modfact(n);
    tmp *= modpow(modfact(n-k), MOD-2);
    tmp %= MOD;
    tmp *= modpow(modfact(k), MOD-2);
    tmp %= MOD;
    return tmp;
}

ll modcomb2(ll n, ll k){
    // ll tmp = modfact(n);
    // tmp *= modpow(modfact(n-k), MOD-2);
    // tmp %= MOD;
    // tmp *= modpow(modfact(k), MOD-2);
    // tmp %= MOD;
    ll ans = 1;
    for (ll i = n; i >= n-k+1; i--){
        ans *= i;
        ans %= MOD;
    }
    for (ll i = 1; i <= k; i++){
        ans *= modpow(i, MOD-2);
        ans %= MOD;
    }
    return ans;
}


int main(){
    int n, a, b;
    cin >> n >> a >> b;

    cout << (modpow(2, n) - modcomb2(n, a) - modcomb2(n, b)-1+(ll)MOD*MOD)%MOD << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
	stack<char> q;
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == 'S')
		{
			q.push(s[i]);
		}
		else
		{
			if (!q.empty() && q.top() != 'T')
			{
				q.pop();
			}
			else
			{
				q.push(s[i]);
			}
		}
	}
	printf("%d", q.size());


	return 0;
}


Measured memory_bytes: 644
from fractions import gcd
 
d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    f = False
    while d % i == 0:
        f = True
        d //= i
    if f: r += 1
    i += 1
print(r + (d > 1))

Measured memory_bytes: 5048
#include <stdio.h>

#define N 246912

static int p[ N + 1 ] = { 0 };

/** Application main entry point. */
int
main (
  int     argc,
  char  * argv[ ]
  )
{
  int i, j;

  for ( i = 2; i * i <= N; ++i )
  {
    if ( p[ i ] ) continue ;

    for ( j = i * i; j <= N; j += i )
    {
      p[ j ] = 1;
    }
  }
  for ( i = 2; i <= N; ++i )
  {
    p[ i ] = p[ i - 1 ] + !( p[ i ] );
  }

  for ( ; ; )
  {
    int n;

    scanf ( "%d", &n );
    if ( !( n ) ) break ;

    printf ( "%d\n", p[ n * 2 ] - p[ n ] );
  }

  return ( 0 );
}

Measured memory_bytes: 0
import numpy as np
n, m, v, p = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = -np.sort(-a)
rest = a[p-1:]
sa = np.cumsum(rest)
nr = len(sa)
ans = p
r0 = rest[0]

for i, (sl, ai) in enumerate(zip(sa, rest)):
    if i == 0:
        continue
    nsmalls = nr-i
    nlarges = i
    rm = max(v-nsmalls-(p-1), 0)
    slarges = sl+rm*m-ai
    mean_larges = slarges/nlarges
    aim = ai+m
    if mean_larges <= aim and r0 <= aim:
        ans += 1
    else:
        break
print(ans)


Measured memory_bytes: 23144
GCD = [[-1] * 210 for _ in range(210)]


def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if GCD[a][b] == -1:
        if b == 0:
            return a
        GCD[a][b] = gcd(b, a % b)
    return GCD[a][b]


def main():
    K = int(input())
    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            tmp = gcd(i, j)
            for k in range(1, K+1):
                ans += gcd(tmp, k)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 69388
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;


int main(){
	//freopen("input.txt","r",stdin);
	int n,x;
	cin>>n;
	int a[1000005];
	cin>>x;
	int res = x;
	for(int i=1; i<n; i++){
		int tmp; cin>>tmp;
		res = __gcd(res,tmp);
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 384
using System;
					
public class my
{
	public static void Main()
	{
		string s;
		
		while( null != ( s = Console.ReadLine()) ) {
			var v = double.Parse(s);
			
			var y = 4.9 *  Math.Pow( v/9.8, 2);
			
			int N = (int)Math.Ceiling( (y+5) / 5.0);
			
			Console.WriteLine(N);
		}
	}
}

Measured memory_bytes: 9300
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

#define PI (acos(-1))
int main(){
    double a, b, x;
    cin >> a >> b >> x;
    a/=1.0;
    b/=1.0;
    x/=1.0;
    
    double s = (a*a*b);
    double h;
    double ans;
    if(x <= s/2.0){
        h = (2.0*x)/(a*b*b);
        ans = atan(h);
        printf("%.12f", (PI/2.0-ans)*57.2957795131);
    }
    else {
        h = 2*(s-x)/(a*a*a);
        ans = atan(h);
        printf("%.12f", ans*57.2957795131);
    } 
    // printf("%.12f", 0.45/0.785398163397);
    // printf("%.12f", atan(1.0));
    
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

vector<vector<int>> to;
vector<int> odd;

bool dfs(int id,int col)
{
	col++;
	col%=2;
	if(odd[id]==-1)
		odd[id]=col;
	else
	{
		if(odd[id]!=col)
			return false;
		else
			return true;
	}
	for(int i=0;i<to[id].size();i++)
	{
		if(!dfs(to[id][i],col))
			return false;
	}

	return true;
}

vector<int> dist;
vector<bool> done;

void bfs(int id,int d)
{
	dist[id]=d;
	
	queue<int> que;
	que.push(id);
	
	int cnt=0;
	while(!que.empty())
	{
		cnt++;
		int i=que.front();
		que.pop();
		done[i]=true;
		for(int j=0;j<to[i].size();j++)
		{
			int nxid=to[i][j];
			if(dist[nxid]!=-1)continue;
			que.push(nxid);
			dist[nxid]=dist[i]+1;
		}
		if(cnt>100000007)
			dist[1000000]=0;
	}
}
			



int main()
{
	int n;
	cin >> n;
	to=vector<vector<int>>(n);
	for(int i=0;i<n;i++)
	{
		string s;
		cin >> s;
		for(int j=0;j<n;j++)
		{
			if(s[j]=='1')
				to[i].push_back(j);
		}
	}

	odd=vector<int>(n,-1);
	if(!dfs(0,0))
	{
		cout << -1 << endl;
		return 0;
	}

	dist=vector<int>(n,-1);
	done=vector<bool>(n,false);
	bfs(0,0);
	int idd=0;
	int mx=0;
	for(int i=0;i<n;i++)
		if(mx<dist[i])
		{
			mx=dist[i];
			idd=i;
		}
	//cerr << idd << endl;
	dist=vector<int>(n,-1);
	done=vector<bool>(n,false);
	bfs(idd,0);
	mx=0;
	for(int i=0;i<n;i++)
		if(mx<dist[i])
		{
			mx=dist[i];
			idd=i;
		}
	//cerr << idd << endl;

	mx=0;
	for(int i=0;i<n;i++)
	{
		dist=vector<int>(n,-1);
		done=vector<bool>(n,false);
		bfs(i,0);
		for(int j=0;j<n;j++)
		if(mx<dist[j])
		{
			mx=dist[j];
			idd=j;
		}
	}
	

	

	cout << mx+1 << endl;




}

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

int main() {
  
  int N; cin >> N; int sum = 0; int maxPrice = 0;
  
  for (int i = 0; i < N; i++) {
    int p; cin >> p;
    sum += p;
    maxPrice = max(maxPrice, p);
  }
  
  cout << sum - maxPrice / 2 << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int num;
	int where;
};
int cmp(Node a,Node b)
{
	return a.num>b.num;
}
int main()
{
	int n;
	cin>>n;
	Node x[n];
	int print[n];
	for(int i=0;i<n;i++)
	{
		cin>>x[i].num;
		x[i].where=i;
	}
	sort(x,x+n,cmp);
	int l1=x[n/2-1].num,l2=x[n/2].num;
	for(int i=0;i<n;i++)
	{
		if(i<=n/2-1) print[x[i].where]=l2;
		else print[x[i].where]=l1;
	}
	for(int i=0;i<n;i++) cout<<print[i]<<"\n";
	return 0;
}

Measured memory_bytes: 4480
use proconio::input;

const M: usize = 300000;

fn main() {
    input! {
        n: usize,
        k: usize,
    }

    let mut st = SegTree::new(M, std::cmp::max);
    let mut ans = 0;
    for _ in 0..n {
        input! {a: usize}
        let l = if a > k {a - k} else {0};
        let r = (a + k).min(M);
        let m = st.get(l, r + 1, None) + 1;
        st.set(a, m);
        ans = ans.max(m);
    }

    println!("{}", ans);
}


struct SegTree {
    tree: Vec<u64>,
    leaf_size: usize,
    op: fn(u64, u64) -> u64,
}

impl SegTree {
    fn new(n: usize, op: fn(u64, u64) -> u64) -> Self {
        let mut ls = 1;
        while ls < n {
            ls <<= 1;
        }
        Self {
            tree: vec![0; 2 * ls - 1],
            leaf_size: ls,
            op,
        }
    }

    fn set(&mut self, mut i: usize, v: u64) {
        i += self.leaf_size - 1;
        self.tree[i] = v;
        while i > 0 {
            i = (i - 1) / 2;
            self.tree[i] = (self.op)(self.tree[2 * i + 1], self.tree[2 * i + 2]);
        }
    }

    fn get(&self, s: usize, e: usize, rng: Option<(usize, usize, usize)>) -> u64 {
        let (i, l, r) = if let Some(rng) = rng { rng } else { (0, 0, self.leaf_size) };
        if l >= e || r <= s {
            0
        } else if l >= s && r <= e {
            self.tree[i]
        } else {
            let m = (l + r) / 2;
            let vl = self.get(s, e, Some((2 * i + 1, l, m)));
            let vr = self.get(s, e, Some((2 * i + 2, m, r)));
            (self.op)(vl, vr)
        }
    }
}


Measured memory_bytes: 8816
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true){
    int n=Integer.parseInt(sc.next());
    int x=Integer.parseInt(sc.next());
    if(n==0&&x==0)break;
int count=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
    if(i==j)break;
for(int k=1;k<=n;k++){
    if(j==k)break;
if(i+j+k==x)count++;
}
}}
System.out.println(count);
}}
}


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

namespace ABC106C_cs
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var k = long.Parse(Console.ReadLine());
            var x = new InfinityString(s);
            Console.WriteLine(x.GetNumberOf(k));
        }
    }
    public class InfinityString
    {
        private readonly string v;

        public InfinityString(string v)
        {
            this.v = v;
        }

        public int GetIndexNumberOfFinal1()
        {
            int x = 0;
            for (; x < this.v.Length && this.v[x] == '1'; x++) { }

            return x;
        }

        public int GetNumberOf(long v)
        {
            if (this.GetIndexNumberOfFinal1() == this.v.Length)
            {
                return 1;
            }
            if (this.GetIndexNumberOfFinal1() < v)
            {
                return int.Parse(this.v[GetIndexNumberOfFinal1()].ToString());
            }
            return 1;
        }
    }

}


Measured memory_bytes: 13140
using System;
using System.Collections.Generic;
using System.Numerics;
using System.Linq;
using System.Text;
using static System.Math;

class MainClass
{

    public static void Main(string[] args)
    {
        var N = LnInt();
        var As = LnInts();
        foreach(var i in As)
        {
            if (i % 2 == 1) { continue; }
            if (i % 6 != 0 && i % 10 != 0)
            {
                print("DENIED");
                return;
            }
        }
        print("APPROVED");
    }

public static long PowLite(long n, long p, int mod = (int)1e9 + 7){long ans = 1;long now = n;for (; p > 0; p >>= 1){if ((p & 1) == 1){ans *= now;ans %= mod;}now *= now;now %= mod;}return ans;}
public static void print(object obj) { Console.WriteLine(obj); }
public static long Gcd(long a, long b) { if (a > b) { var r = a % b; if (r == 0) return b; else return Gcd(b, r); } else { var r = b % a; if (r == 0) return a; else return Gcd(a, r); } }
public static int Gcd(int a, int b) { if (a > b) { var r = a % b; if (r == 0) return b; else return Gcd(b, r); } else { var r = b % a; if (r == 0) return a; else return Gcd(a, r); } }
public static int[] LnInts() { var vs = Console.ReadLine().Trim().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); var ins = new int[vs.Length]; for (int i = 0; i < vs.Length; i++) ins[i] = int.Parse(vs[i]); return ins; }
public static int LnInt() { var vs = Console.ReadLine().Trim(); return int.Parse(vs); }
public static long[] LnLngs() { var vs = Console.ReadLine().Trim().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); var ins = new long[vs.Length]; for (int i = 0; i < vs.Length; i++) ins[i] = long.Parse(vs[i]); return ins; }
public static long LnLng() { var vs = Console.ReadLine().Trim(); return long.Parse(vs); }
public static string[] LnStrs() { var vs = Console.ReadLine().Trim().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); return vs; }
public static string LnStr() { var vs = Console.ReadLine().Trim(); return vs; }
public static List<T[]> AllPermutation<T>(params T[] array) where T : IComparable{var a = new List<T>(array).ToArray();var res = new List<T[]>();res.Add(new List<T>(a).ToArray());var n = a.Length;var next = true;while (next){next = false;int i;for (i = n - 2; i >= 0; i--){if (a[i].CompareTo(a[i + 1]) < 0) break;}if (i < 0) break;var j = n;do{j--;} while (a[i].CompareTo(a[j]) > 0);if (a[i].CompareTo(a[j]) < 0){var tmp = a[i];a[i] = a[j];a[j] = tmp;Array.Reverse(a, i + 1, n - i - 1);res.Add(new List<T>(a).ToArray());next = true;}}return res;}}



Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n, y;
		n = sc.nextInt();
		y = sc.nextInt();
		
		sc.close();
		
		y /= 1000;

		int x = -1, z = -1, ans = -1;
		
		for(int i = 0; i <= n; ++i) {
			for(int j = 0; j + i <= n; ++j) {
				int tmp = y - 5 * i - 10 * j;
				if(tmp + i + j == n && tmp >= 0) {
					x = i;
					z = j;
				}
			}
		}
		if(x != -1)ans = y - 5 * x - 10 * z;
		System.out.println(z + " " + x + " " + ans);
	}

}


Measured memory_bytes: 23124
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    S=input()
    T=input()
    print(sum(s!=t for s, t in zip(S, T)))




main()



Measured memory_bytes: 10028
S = input()
for i in range(len(S) - 2):
    if S[i] == S[i + 2]:
        print(i + 1, i + 3)
        exit()
    elif S[i] == S[i + 1]:
        print(i + 1, i + 2)
        exit()
if S[len(S) - 2] == S[len(S) - 1]:
    print(len(S) - 1, len(S))
    exit()
print(-1, -1)

Measured memory_bytes: 39408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

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 (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

struct UnionFind {
    vector< int > data;

    UnionFind(int sz) {
        data.assign(sz, -1);
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return (false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }

    int find(int k) {
        if(data[k] < 0) return (k);
        return (data[k] = find(data[k]));
    }

    int size(int k) {
        return (-data[find(k)]);
    }
};



int main() {
    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    rep (i, n) {
        cin >> p[i];
        p[i]--;
    }
    UnionFind uf(n);
    rep (i, m) {
        int x, y;
        cin >> x >> y;
        uf.unite(--x, --y);
    }
    int ans = 0;
    rep (i, n) {
        if (uf.find(i) == uf.find(p[i])) {
            ans++;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 3988
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};
 

int main() {
  int A, B, X;
  cin >> A >> B >> X;
  if (X < A || A + B < X) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

template<int mod>
struct ModInt {
    int x;

    ModInt() : x(0) {}
    ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const{
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return ModInt(u);
    }

    friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt<mod> &a) {
        long long x;
        is >> x;
        a = ModInt<mod>(x);
        return (is);
    }
};

const int mod = 1e9 + 7;
using modint = ModInt< mod >;

modint f[201010];

modint nCr(int n, int r){
    return f[n] / (f[r] * f[n-r]);
}

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

    f[0] = 1;
    rep1(i, 200010) f[i] = f[i-1]*i;
    modint ansx = 0, ansy = 0;
    rep1(i, n) ansx += nCr(n*m-2, k-2)*m*m*(n-i)*i;
    rep1(i, m) ansy += nCr(n*m-2, k-2)*n*n*(m-i)*i;
    cout << ansx+ansy << endl;
}

Measured memory_bytes: 1024
<?php

fscanf(STDIN, "%d", $n);
$x_input = explode(' ', fgets(STDIN));
$x = [];
for ($i = 0; $i < $n; $i++) {
	$x[] = (int)$x_input[$i];
}

sort($x);
//var_dump($x);

$larger = $x[$n/2];
$smaller = $x[$n/2 - 1];

//echo $larger, " ", $smaller, "\n";

foreach ($x_input as $input) {
	if ((int)$input <= $smaller) {
		echo $larger, "\n";
		continue;
	}
	echo $smaller, "\n";
}

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

//long long
using ll = long long;

// pair<int, int>
using PII = pair<int, int>;

//最大値、mod
const int MOD = 1000000007;
const int INF = 1000000000;
const long long LINF = 1e18;

//出力系
#define print(x) cout << x << endl
#define prints(x) cout << fixed << setprecision(10) << x << endl
#define printc(x) cout << setw(2) << setfill('0') << x << endl;
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

// 最小公倍数
unsigned lcm(unsigned a, unsigned b){
    return a / gcd(a, b) * b; 
}

// a = max(a, b), a = min(a, b)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int main(){
    int N;
    cin >> N;
    ll ans = 0;
    ll sum = 0;
    REP(i, N){
        int a;
        cin >> a;
        if(a == 0){
            ans += sum / 2;
            sum = 0;
            continue;
        }
        sum += a;

    }
    ans += sum / 2;
print(ans);
}

Measured memory_bytes: 256
INF = 30000000000
N = int(input())
points = list(map(int, input().split()))
sums = [0]
for index in range(len(points)):
  sums.append(points[index]+sums[index])
ans = INF
last = sums[-1]
for s in sums[1:-1]:
  ans = min(ans, abs(last -s - s))
print(ans)

Measured memory_bytes: 23792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
pair<int,int>p[100002];
int arr[100002]={0};
map<int,int>mp;
int main(){
    int n,m,x,y,ans;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d %d",&p[i].first,&p[i].second);
        mp[p[i].second]=p[i].first;
    }
    map<int,int>::iterator it;
    for(it=mp.begin();it!=mp.end();it++){
        //v[it->second].push_back(it->first);
        arr[it->second]++;
        mp[it->first]=arr[it->second];
    }
    for(int i=0;i<m;i++){
        x=p[i].first;
        y=0;
        while(x){
            x/=10;
            y++;
        }
        for(int j=0;j<6-y;j++){
            printf("0");
        }
        printf("%d",p[i].first);

        x=mp[p[i].second];
        y=0;
        while(x){
            x/=10;
            y++;
        }
        for(int j=0;j<6-y;j++){
            printf("0");
        }
        printf("%d\n",mp[p[i].second]);
    }
    return 0;
}


Measured memory_bytes: 7424
import java.util.Scanner
import scala.collection.Searching._

import scala.annotation.tailrec

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {

  def solve(sc: => Scanner): Unit = {
    val N, M = sc.nextInt
    val A = Array.fill[Set[Int]](N)(Set[Int]())
    for (i <- 0 until N) {
      A(i) = A(i) ++ Set(i)
    }
    val B = Array.fill(M)((sc.nextInt, sc.nextInt)).sorted
    for (i <- 0 until M) {
      A(B(i)._2) = A(B(i)._2) ++ A(B(i)._2 - 1)
      A(B(i)._2 - 1) = A(B(i)._2)
    }
    println(A.map(x => x.size).mkString(" "))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)

    solve(sc)
  }
}

Measured memory_bytes: 311716
#include<stdio.h>

int main()
{
	int K,N,A[200000],i,l,lx;

	scanf("%d%d",&K,&N);
	for (i = 0;i < N;i++)
	{
		scanf("%d",&A[i]);
	}


	lx = A[0] + K - A[N - 1];

	for (i = 1;i < N;i++)
	{
		l = A[i] - A[i - 1];
		if (l > lx)
		{
			lx = l;
		}

	}

	printf("%d\n",K - lx);
	return 0;

}


Measured memory_bytes: 896
n = int(input())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(key=lambda x: x[0]+x[1], reverse=True)
A, B = [], []
for i in range(n):
    a, b = AB[i]
    if i % 2 == 0:
        A.append(a)
    else:
        B.append(b)
print(sum(A)-sum(B))


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

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

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    long long ans = 0;

    for(int i = 0; i < n; i++){
        ans += (distance(a.begin(), lower_bound(a.begin(), a.end(), b[i])) * (distance(upper_bound(c.begin(), c.end(), b[i]), c.end())));

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


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s,t,ans;
	cin>>s>>t;
	int a=s.size()+t.size(),count=1,i=0,j=0;
	while(count<=a){
		if(count%2){
			ans+=s[i];
			++i;
		}
		else{
			ans+=t[j];
			++j;
		}
		++count;
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
Int INF = 1e18;
double EPS = 0.00000001;
//Int mod = 998244353;

int main() {
    Int n;
    cin >> n;
    vector<Int> p(n);
    for (Int i = 0; i < n; i++) cin >> p[i];
    Int cnt = 0;
    for (Int i = 0; i < n; i++) {
        if (i + 1 != p[i]) cnt++;
    }
    dump(cnt <= 2 ? "YES" : "NO");
    return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
typedef unsigned long long u64;
typedef signed long long l64;
u64 over = 1000000007;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  u64 n, a, b;
  cin >> n >> a >> b;
  u64 c = a-b;
  u64 h[n];
  for (u64 i = 0; i < n; ++i) cin >> h[i];
  u64 bottom = 0, top = 100000000000000;
  u64 prev = (bottom+top)/2;
  while (top-bottom > 1) {
    u64 over = 0;
    for (u64 i = 0; i < n; ++i) {
      if (h[i] > prev * b) over += (h[i] - prev*b - 1) / c + 1;
    }
    if (over > prev) {
      bottom = prev;
    } else {
      top = prev;
    }
    prev = (bottom + top) / 2;
  }
  cout << top << endl;
  return 0;
}


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

int ans,cnt;
string s;

int main(){

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

    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='A'||s[i]=='G'||s[i]=='C'||s[i]=='T')cnt++;
        else cnt=0;
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
n, p = map(int,input().split())

if n == 1:
    print(p)
else:
    l = 10**6 + 5
    A = [0] * l
    for i in range(2, l):
        while p%i == 0:
            p //= i
            A[i] += 1
        if p == 1:
            break

    # print(A[:10])

    if sum(A) == 0:
        print(1)
    else:
        ans = 1
        for i in range(l):
            ans *= i ** (A[i]//n)
        print(ans)

Measured memory_bytes: 48876
#include<iostream>
#include<cmath>
using namespace std;
#define EPS 1e-10
long double naiseki(long double ax, long double ay, long double bx, long double by) { return ax * bx + ay * by; }
long double gaiseki(long double ax, long double ay, long double bx, long double by) { return ax * by - ay * bx; }
int main() {
	long double N, X1, X2, Y1, Y2, X3, X4, Y3, Y4;
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3 >> X4 >> Y4;
		long double G = naiseki(X2 - X1, Y2 - Y1, X4 - X3, Y4 - Y3);
		long double H = gaiseki(X2 - X1, Y2 - Y1, X4 - X3, Y4 - Y3);
		if (fabs(G) < EPS) { cout << "1" << endl; }
		else if (fabs(H) < EPS) { cout << "2" << endl; }
		else { cout << "0" << endl; }
	}
}

Measured memory_bytes: 1216
n = int(input())
a = list(map(int, input().split()))

m = 10 ** 18

ans = 1
ex = False
for i in range(n):
    if a[i] == 0:
        print(0)
        ex = True

if not ex:
    for i in range(n):
        ans *= a[i]
        if ans > m:
            ans = -1
            break

    print(ans)


Measured memory_bytes: 21788
def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()    

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  
  if(a < b){
    if(a < c && c < b){
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
  else {
    if ( b < c && c < a ) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;

int n,ans,sum[N];
char s[N];

int main() {
	cin>>n;
	scanf("%s",s+1);
	for (int i=1;i<=n;i++) {
		sum[i]=sum[i-1]+(s[i]=='E');
	}
	ans=0x3f3f3f3f;
	for (int i=1;i<=n;i++) {
		int tx=sum[n]-sum[i]+(i-1)-(sum[i-1]);
		ans=min(ans,tx);
	}
	cout<<ans;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 9007199254740997;
const ll INF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

const int w=5;
const int k=700;
const int n=26;
int ww;
int d;

VI c(n);
VVI s(365,VI(n));

struct st{
	VI a;
	ll score;
	bool operator<(const st &another) const {return score < another.score;};
};

vector<st> f(st p){
	VI a=p.a; ll score=p.score;
	int now=a.size()+1;
	VI last(n,0);
	REP(i,a.size())
		last[a[i]]=i+1;
	VI down(n); ll downsum=0;
	REP(i,n){
		down[i]=c[i]*(now-last[i]);
		downsum+=down[i];
	}
	a.push_back(-1);
	vector<st> tmp;
	REP(i,n){
		a[now-1]=i;
		tmp.push_back({a,score-downsum+down[i]+s[now-1][i]});
	}
	sort(ALL(tmp));
	vector<st> ret;
	REP(i,ww)
		ret.push_back(tmp[n-1-i]);
	return ret;
}

int main(){
	cin >> d;
	REP(i,n) cin >> c[i];
	REP(i,d)REP(j,n) cin >> s[i][j];
	priority_queue<st> q;
	VI a(0);
	q.push({a,0});
	REP(i,d){
		priority_queue<st> next;
		ww=w+1;
		REP(j,k){
			if(j%140==0)
				ww--;
			if(q.empty())
				break;
			for(auto nx:f(q.top()))
				next.push(nx);
			q.pop();
		}
		q=next;
	}
	REP(i,d)
		cout << q.top().a[i]+1 << endl;
	//cout << q.top().score << endl;
	return 0;
}

Measured memory_bytes: 18288
using System;

namespace C___Next_Prime
{
    class Program
    {
        static void Main (string[] args)
        {
            var x = int.Parse (Console.ReadLine ());
            for (var i = x; i <= 1000000; i++)
            {
                var count = 0;
                for (var j = 2; j <= i; j++)
                {
                    if (i % j == 0)
                        count++;
                }
                if (count == 1)
                {
                    Console.WriteLine (i);
                    break;
                }
            }
        }
    }
}

Measured memory_bytes: 13140
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


def main():
    q = int(input())
    ls = [[0,0] for _ in range(q)]
    for i in range(q):
        l,r = map(int,input().split())
        ls[i][0],ls[i][1] = l,r
    
    primes = seachPrimeNum(10**5)
    prime_ls1 = [0 for _ in range(10**5+1)]

    for prime in primes:
        prime_ls1[prime] =1


    prime_ls2 = [0 for _ in range(10**5+1)]

    for prime in primes:
        N = (prime+1)//2
        if prime_ls1[N]==1:
            prime_ls2[prime] = 1
        else:
            pass

    
    for i in range(1,10**5+1):
        prime_ls2[i] += prime_ls2[i-1]
    
    for i in range(q):
        l,r = ls[i]
        print(prime_ls2[r]-prime_ls2[l-1])    

    

if __name__ == "__main__":
    main()

Measured memory_bytes: 34340
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String find = "x";
        int count = 0;
        int index = 0;

        while(index != -1){
            index = S.indexOf(find, index);

            if(index != -1){
                index ++;
                count ++;
            }
        }
        if(8 <= count){
            System.out.print("NO");
        }else{
            System.out.print("YES");
        }
    }
}



Measured memory_bytes: 21716
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        nn: [u64;3]
    }
    let mut nn = nn;
    let mut cnt = 0;
    loop {
        nn.sort();
        if nn[0] == nn[1] && nn[0] == nn[2] {
            break;
        } else if nn[0] == nn[1] {
            nn[0] += 1;
            nn[1] += 1;
        } else {
            nn[0] += 2;
        }
        cnt += 1;
    }
    println!("{}", cnt);
}


Measured memory_bytes: 4352
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = map(int, raw_input().split())

sz = [1] * (N + 1)
num = [1] * (N + 1)

for i in range(N):
    sz[i + 1] = sz[i] * 2 + 3
    num[i + 1] = num[i] * 2 + 1

def func(lv, id):
    mid = (sz[lv] + 1) / 2
    if lv == 0:
        return 1
    if id == 1:
        return 0
    if id == mid:
        return (num[lv] - 1) / 2 + 1
    if id == sz[lv]:
        return num[lv]
    if 1 < id < mid:
        return func(lv - 1, id - 1)
    if mid < id < sz[lv]:
        return func(lv - 1, id - sz[lv - 1] - 2) + num[lv - 1] + 1

print func(N, X)


Measured memory_bytes: 2808
#include <iostream>
using namespace std;
int main()
{
    char c;
    cin >> c;
    if(c == 'a'){
        cout << 'b' << endl;
    }else if(c == 'b'){
        cout << 'c' << endl;
    }else if(c == 'c'){
        cout << 'd' << endl;
    }else if(c == 'd'){
        cout << 'e' << endl;
    }else if(c == 'e'){
        cout << 'f' << endl;
    }else if(c == 'f'){
        cout << 'g' << endl;
    }else if(c == 'g'){
        cout << 'h' << endl;
    }else if(c == 'h'){
        cout << 'i' << endl;
    }else if(c == 'i'){
        cout << 'j' << endl;
    }else if(c == 'j'){
        cout << 'k' << endl;
    }else if(c == 'k'){
        cout << 'l' << endl;
    }else if(c == 'l'){
        cout << 'm' << endl;
    }else if(c == 'm'){
        cout << 'n' << endl;
    }else if(c == 'n'){
        cout << 'o' << endl;
    }else if(c == 'o'){
        cout << 'p' << endl;
    }else if(c == 'p'){
        cout << 'q' << endl;
    }else if(c == 'q'){
        cout << 'r' << endl;
    }else if(c == 'r'){
        cout << 's' << endl;
    }else if(c == 's'){
        cout << 't' << endl;
    }else if(c == 't'){
        cout << 'u' << endl;
    }else if(c == 'u'){
        cout << 'v' << endl;
    }else if(c == 'v'){
        cout << 'w' << endl;
    }else if(c == 'w'){
        cout << 'x' << endl;
    }else if(c == 'x'){
        cout << 'y' << endl;
    }else{
        cout << 'z' << endl;
    }
    return(0);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void READ()
{
#define R READ();
#define INFI 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mem0(x) memset(x,0,sizeof(x))
#define prln(x) cout<<#x<<"="<<x<<endl;
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout<<fixed<<setprecision(11);
}
///////////////////////////
const int N=5+    1e6;

long long n,m;
int main()
{
    
    cin>>n>>m;
    if(n==1&&m==1)cout<<1;
    else if(n==1)cout<<m-2;
    else if(m==1)cout<<n-2;
    else
    cout<<(n-2)*(m-2);

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
    string s = "CODEFESTIVAL2016";
    string S;
    cin >> S;
    int a = 0;
    for (int i = 0; i < S.length(); i++) {
        if (s[i] != S[i]) {
            a++;
        }
    }
    cout << a << endl;
}

Measured memory_bytes: 256
H,W,D = map(int, input().strip().split(' '))
A = [list(map(int, input().strip().split(' '))) for _ in range(H)]

a2pos = [None]*(H*W+1)
for h in range(H):
  for w in range(W):
    a2pos[A[h][w]] = [h,w]

def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

a2dist = [0]*(H*W+1)
for i in range(1,(H*W)-D+1):
  a2dist[i+D] = a2dist[i]+dist(a2pos[i],a2pos[i+D])
  
q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  print(a2dist[r]-a2dist[l])

Measured memory_bytes: 62044
class UnionFind():
    def __init__(self, n):
        self.size = n
        self.data = [-1 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


N, M = map(int, input().split())
p = [int(s) - 1 for s in input().split()]
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x - 1, y - 1)
ans = [uf.connected(i, v) for i, v in enumerate(p)].count(True)
print(ans)


Measured memory_bytes: 13812