akhauriyash/Code-Regression huggingface dataset:
import collections

def combinations_count(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)
ans = [0]*n
x = 0 #全てのボールから、できる組合せの総数

if len(c) == 1:
    ans = [combinations_count(n-1, 2)]*n
    print(*ans)
    exit()

for i in c.items():
    a = i[0]
    b = i[1]
    if b > 2:
        x += combinations_count(b, 2)
    elif b == 2:
        x += 1

for i in c.items():
    a = i[0]
    b = i[1]
    if b > 2:
        y = x - combinations_count(b, 2) + combinations_count(b-1, 2)
    elif b == 2:
        y = x - 1
    else:
        y = x
    ans[a-1] = y

for i in li:
    print(ans[i-1])


Measured memory_bytes: 26772
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int a = sc.nextInt();
	int b = sc.nextInt();
	int c = sc.nextInt();
	if(a<b){
		if(b<c){
			System.out.printf("%d %d %d\n",a,b,c);
			}else if(a<c){
					System.out.printf("%d %d %d\n",a,c,b);
				
				}else{
				
					System.out.printf("%d %d %d\n",c,a,b);
				}	

}

if(b<a){
		if(a<c){
			System.out.printf("%d %d %d\n",b,a,c);
			}else if(b<c){
					System.out.printf("%d %d %d\n",b,c,a);
				
				}else{
					System.out.printf("%d %d %d\n",c,b,a);
								}
	}
}
}

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

using namespace std;
using VI = vector<int>;
using VPI = vector<pair<int, int>>;
using LL = long long;

#define FOR(a,n) for(int i=a;i<n;i++)
#define rFOR(a,n) for(int i=n-1;i>=a;i--)
#define IN(n,a) for(int i=0;i<n;i++) cin>>a[i]
#define pIN(n,t) for(int i=0;i<n;i++){int a,b; cin>>a>>b; t.emplace_back(a,b);}
#define SORT(a) sort(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()

int main()
{
	LL n;
	cin >> n;

	LL sq = sqrt(n);
	while (n % sq != 0) sq--;

	cout << sq + (n / sq) - 2;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
S = list(input())
if S[K-1] == 'A':
    S[K-1] = 'a'
elif S[K-1] == 'B':
    S[K-1] = 'b'
else:
    S[K-1] = 'c'
print(''.join(S))

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

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n;
  cin>>n;
  vector<int> w(n);
  REP(i,n) cin>>w[i];
  int s=0;
  REP(i,n)s+=w[i];
  int p=0;
  int mn=1000000;
  REP(i,n) {
    p+=w[i];
    mn=min(mn, abs(p-(s-p)));
  }
  cout << mn << endl;
  return 0;
}


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

int main() {
   int n;
   cin >> n;
   deque<int> v;
   for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      if (i % 2 == 0) {
         v.push_back(a);
      } else {
         v.push_front(a);
      }
   }

   if (n&1) reverse(v.begin(), v.end());

   for (int i = 0; i < n-1; i++) {
      cout << v[i] << " ";
   }
   cout << v[n-1] << endl;


   return 0;
}

Measured memory_bytes: 2944
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

int main(void)
{
  int rate, ans;
  scanf("%d", &rate);
  if (rate >= 400 && rate <= 599)
  {
    ans = 8;
  }
  else if (rate >= 600 && rate <= 799)
  {
    ans = 7;
  }
  else if (rate >= 800 && rate <= 999)
  {
    ans = 6;
  }
  else if (rate >= 1000 && rate <= 1199)
  {
    ans = 5;
  }
  else if (rate >= 1200 && rate <= 1399)
  {
    ans = 4;
  }
  else if (rate >= 1400 && rate <= 1599)
  {
    ans = 3;
  }
  else if (rate >= 1600 && rate <= 1799)
  {
    ans = 2;
  }
  else
  {
    ans = 1;
  }
  printf("%d", ans);
  return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
 
#define mod 1000000007
#define inf 1000000000
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
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;}

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

int main(){
  ll n;
  cin >> n;
  vector<pair<ll, ll>> p(n);
  for(ll i = 0; i < n; i++){
    ll x, l;
    cin >> x >> l;
    p[i] = {x-l, x+l};
  }
  sort(all(p), compare_by_b);


  ll ans = 0;
  ll right = -10000000000;
  for(ll i = 0; i < n; i++){
    if(right > p[i].first) continue;
    ans++;
    right = p[i].second;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
sl=list(input())

n=len(sl) 
al=[];zl=[]
ans=[]
for i in range(n) :
  if sl[i]=="A" :
    al.append(i)
  if sl[i]=="Z" :
    zl.append(i)
#for j in range(min(al),max(zl)+1) :
#  ans.append(sl[j])
print(max(zl)+1-min(al))

Measured memory_bytes: 12604
x, y = $<.readlines.map(&:chomp).chunk {|st| st.empty?}.reject {|a| a.first}
         .map(&:last).map{|a| a.map {|b| b.split(",").first.to_i}}.to_a
h = Hash.new(0)
(x + y).each {|i| h[i] += 1}
(x - (x - y)).uniq.sort.each {|i| puts "#{i} #{h[i]}"}


Measured memory_bytes: 6876
#include<iostream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>

signed main(){

  int n;
  std::cin>>n;
  std::vector<double> x(n),y(n);
  for(auto& xi:x)std::cin>>xi;
  for(auto& yi:y)std::cin>>yi;

  auto manhattan_distance = [](auto const& x,auto const& y)->double{
    int n = x.size();
    double dist = 0.0;
    for(int i=0;i<n;++i){
      dist += std::abs(x[i]-y[i]);
    }
    return dist;
  };
  auto euclidean_distance = [](auto const& x,auto const& y)->double{
    int n = x.size();
    double dist = 0.0;
    double p = 2;
    for(int i=0;i<n;++i){
      dist += std::pow(std::abs(x[i]-y[i]),p);
    }
    dist = std::pow(dist,1.0/p);
    return dist;
  };
  auto chebyshev_distance = [](auto const& x,auto const& y)->double{
    int n = x.size();
    double dist = 0.0;
    for(int i=0;i<n;++i){
      dist = std::max(dist,std::abs(x[i]-y[i]));
    }
    return dist;
  };
  auto minkowski_distance = [](auto const& x,auto const& y,double p)->double{
    int n = x.size();
    double dist = 0.0;
    for(int i=0;i<n;++i){
      dist += std::pow(std::abs(x[i]-y[i]),p);
    }
    dist = std::pow(dist,1.0/p);
    return dist;
  };

  std::cout << std::fixed <<std::setprecision(10);

  std::cout<< minkowski_distance(x,y,1.0) <<std::endl;
  std::cout<< minkowski_distance(x,y,2.0) <<std::endl;
  std::cout<< minkowski_distance(x,y,3.0) <<std::endl;
  std::cout<< chebyshev_distance(x,y) <<std::endl;

}


Measured memory_bytes: 3448
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	var mx, mn, s int = -10000000, 10000000, 0
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scan(&tmp)
		if mx < tmp {
			mx = tmp
		}
		if mn > tmp {
			mn = tmp
		}
		s = s + tmp
	}

	fmt.Printf("%d %d %d\n", mn, mx, s)

	return
}



Measured memory_bytes: 1808
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		String result = "";
		while(sc.hasNext()) {
			String word = sc.next();
			char first = word.charAt(0);
			result += first;
		}
		System.out.println(result.toUpperCase());
	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#include<random>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

vector<vector<ll>> nxt;
vector<vector<ll>> bef;
vector<vector<ll>> cnt;
ll dp[2020][2020];

ll dfs(ll l, ll r) {
	if(l > r) return 0;
	if(dp[l][r] != -1) return dp[l][r];
	vector<ll> c(26);
	REP(i,26) c[i]=cnt[r][i];
	if(l) {
		REP(i,26) c[i]-=cnt[l - 1][i];
	}
	ll ret = 0;
	REP(i,26) if(c[i]) ret++;
	REP(i,26) {
		if(nxt[l][i] <= r && bef[r][i] >= l && nxt[l][i] != bef[r][i]) {
			ret++;
			ret += dfs(nxt[l][i] + 1, bef[r][i] - 1);
		}
	}
	ret %= MOD;
	return dp[l][r] = ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	REP(i,2020) REP(j,2020) dp[i][j] = -1;
	string s;
	cin >> s;
	ll n = (ll)s.size();
	nxt.resize(n, vector<ll>(26, -1));
	bef.resize(n, vector<ll>(26, -1));
	cnt.resize(n, vector<ll>(26, 0));
	REP(i,n) {
		REP(j,26) {
			if(i) cnt[i][j] = cnt[i - 1][j];
		}
		cnt[i][s[i] - 'a']++;
	}
	bef[0][s[0]-'a'] = 0;
	FOR(i,1,n) REP(j,26) {
		if(s[i] - 'a' == j) bef[i][j] = i;
		else bef[i][j] = bef[i - 1][j];
	}
	nxt[n - 1][s[n - 1] - 'a'] = n - 1;
	for(ll i = n - 2; i >= 0; i--) REP(j,26) {
		if(s[i] - 'a' == j) nxt[i][j] = i;
		else nxt[i][j] = nxt[i + 1][j];
	}
	cout << dfs(0, n - 1) << endl;
	return 0;
}




Measured memory_bytes: 36620
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll Mod(ll x) {
    if (x < 0) {
        return (MOD - x % MOD);
    } else {
        return x % MOD;
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> broken(N + 1, 1);
    int a;
    for (int i = 0; i < M; i++) {
        cin >> a;
        broken[a] = 0;
    }
    broken[0] = 0;
    vector<ll> dp(N + 1);
    dp[0] = 1;
    dp[1] = broken[1] == 1 ? 1 : 0;
    for (int i = 2; i <= N; i++) {
        if (broken[i] == 1) {
            dp[i] = Mod(dp[i - 1] + dp[i - 2]);
        } else {
            dp[i] = 0;
        }
    }
    cout << dp[N] << endl;
    return 0;
}


Measured memory_bytes: 1408
package main

import "fmt"

func main() {
	var n,count int
	fmt.Scanf("%d", &n)

	numbers := make([]int, n)

	for i := 0; i < n; i++ {
		fmt.Scan(&numbers[i])
	}

	flag := true

	for flag {
		for i, number := range numbers {
			if number%2 == 0 {
				numbers[i] = number/2
			} else {
				flag = false
			}
		}
		if flag {
			count++
		}
	}

	fmt.Println(count)
}


Measured memory_bytes: 1844
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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 P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;


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

    int n;
    cin>>n;
    vd p(n);
    rep(i,n)cin>>p[i];
    vector<vector<double>> dp(n+1,vector<double> (n+1,0));

    dp[0][0]=1.0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            dp[i+1][j+1]+=dp[i][j]*p[i];
            dp[i+1][j]+=dp[i][j]*(1-p[i]);
        }
    }
    double ans=0;
    for(int i=(n+1)/2;i<=n;i++)ans+=dp[n][i];

    printf("%.10f\n",ans);

    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=n;j++){
    //         printf("%3.3f ",dp[i][j]);
    //     }
    //     printf("\n");
    // }


//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 70784
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] l = new int[n];

		for (int i = 0; i < n; i++) {
			l[i] = sc.nextInt();
		}

		Arrays.sort(l);

		int count = 0;

		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				for (int k = j + 1; k < n; k++) {
					if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i]) {
						continue;
					}
					if (l[k] < l[i] + l[j]) {
						count++;
					}
				}
			}
		}
		System.out.println(count);
	}
}

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

int main()
{
    int64_t n, t;
    std::cin >> n >> t;
    int64_t start{}, prev{};
    for (int i{}; i < n; i++)
    {
        int64_t h;
        std::cin >> h;
        if (h < prev)
        {
            start += h - prev;
            h = prev;
        }
        if (t < start)
            puts("1");
        else
            std::cout << (t - start) / h + 1 << std::endl;
        
        start += h;
        prev = h;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <iostream>

using namespace std;

int main()
{
     int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if(x-r >= 0 && x+r <= w  && y-r >=0 && y+r <=h )
        cout<< "Yes" << endl;
    else
        cout<< "No" << endl;
}



Measured memory_bytes: 3092
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<typename T>
vector<T> gen_v(size_t a) { return vector<T>(a); }
template<typename T, typename ...Ts>
auto gen_v(size_t a, Ts... ts) { return vector<decltype(gen_v<T>(ts...))>(a, gen_v<T>(ts...)); }
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, a, b, c, d; cin >> n >> a >> b >> c >> d;
	a--, b--, c--, d--;
	string s; cin >> s;

	auto f = [&](int x, int y) {
		rep(i, x, y) {
			if (s[i] == '#' && s[i + 1] == '#')return 0;
		}
		rep(i, x, y + 1) {
			if (i - 1 >= 0 && i + 1 < n && s[i - 1] == '.'&&s[i] == '.'&&s[i + 1] == '.') {
				return 2;
			}
		}
		return 1;
	};

	int A = f(a, c);
	int B = f(b, d);

	if (A == 0 || B == 0) {
		cout << "No" << endl;
	}
	else {
		if (c > d) {
			if (B == 2) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
			}
		}
		else {
			cout << "Yes" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 592
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
	if (v.empty())return out;
	constexpr bool is_vector_v = is_vector<T>::value;
	if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
	else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
	return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

int main() {
	IOS;
	ll a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	ll m = max(x, y);
	ll res = LLONG_MAX;
	REP(i, m + 1) {
		ll ta = max(0ll, x - i);
		ll tb = max(0ll, y - i);
		ll tmp = i * 2 * c + ta * a + tb * b;
		chmin(res, tmp);
	}
	put(res);
	return 0;
}

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

const int N = 1e5;

int n,k,r,s,p;
char t[N+5];

char win[3] = {'r','p','s'};
int score[3];

int memo[N+5][6];

int dp(int id, int bef){
	if(id >= n) return 0;
	int &ret = memo[id][bef];
	if(ret!=-1) return ret;
	ret = 0;
	for(int i=0;i<3;i++){
		if(i == bef) continue;
		int tmp = 0;
		if(win[i] == t[id]) tmp+=score[i];
		ret = max(ret,dp(id+k,i) + tmp);
	}
	return ret;
}

int main(){
	scanf("%d%d",&n,&k);
	scanf("%d%d%d",&score[2],&score[1],&score[0]);
	scanf("%s",t);
	memset(memo,-1,sizeof(memo));
	int ans = 0;
	for(int i=0;i<k;i++){
		ans += dp(i,3);
	}
	printf("%d\n",ans);
	return 0;
}


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

bitset<100000001> sieve;
void makeSieve() {
    sieve.set();
    sieve[0] = sieve[1] = false;
    for (int i=4; i<100000001; i+=2) {
        sieve[i] = false;
    }
    for (int i=3; i<10001; i+=2) {
        if ( ! sieve[i]) continue;
        for (int j=i*i; j<100000001; j+=i) {
            sieve[j] = false;
        }
    }
}
int main() {
    makeSieve();
    int n; cin >> n;
    int num = 0;
    while (n--) {
        int a; cin >> a;
        num += (int)sieve[a];
    }
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 13368
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#include <cmath>
#include <string>

#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<
#define X first
#define Y second

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

const int DIM = 60;
const int MAX = 205;

bool can_represent(ll x, vector <ll> &V) {//V is normalized
  for (auto it : V) {
    int last_bit = __builtin_ctzll(it);
    if (x >> last_bit & 1) x ^= it;
  }

  return x == 0;
}

void normalize(vector <ll> &V) {
  int ind=0;

  REP(i, DIM) {
    FOR(j, ind, (int) V.size()) {
      if (V[j] >> i & 1) {
        swap(V[ind], V[j]);
        FOR(k, j+1, (int) V.size())
          if (V[k] >> i & 1)
            V[k] ^= V[ind];

        ind++;
        break;
      }
    }
  }
}

ll p[MAX];
char s[MAX];

int main()
{
  int tt;
  scanf("%d", &tt);
    
  while(tt--) {
    int n;
    scanf("%d", &n);
    REP(i, n) scanf("%lld", &p[i]);
    scanf(" %s", s);

    vector <ll> T = {}; //zero wins in span of this
    bool one = false;

    for (int i=n-1; i>=0; i--) {
      if (s[i] == '0') {
        if (!can_represent(p[i], T)) {
          T.push_back(p[i]);
          normalize(T);
        }
      }
      else {
        if (!can_represent(p[i], T)) {
          one = true;
        }
      }
    }

    if (one) printf("1\n");
    else printf("0\n");

  }

  return 0;
}



Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define PB push_back
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int mod = (int)1e9 + 7;
const int maxn = 1e5 + 4;
const ll inf = 1e18;

int main (){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
		
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a % 2 == 1)
			cnt ++;
	}
	if (cnt % 2 == 0)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
#define ld long double
//a^n modをO(logN)で計算
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//a/bをmodで割った余り、フェルマーの小定理
int64_t div(int64_t a,int64_t b,int64_t mod){
    return (a%mod)*(modpow(b,mod-2,mod)%mod)%mod;
}

map<int,int64_t> rp;
map<int,int64_t> p;

//O(√n)
//素因数分解
void fl(int64_t n){
    p.clear();
    if(n==1){
        return ;
    }
    int tmp = n;
    while(tmp%2==0 ){
        tmp /= 2;
        p[2]++;
    }
    for(int i=3;i*i<=tmp;i++){
        while(tmp % i ==0){
            tmp /= i;
            p[i]++;
        }
    }
    if(tmp!=1){//まだ割り切れてない場合、√Nまでは見てるから
        p[tmp]++;
    }
    for (auto c:p){
        if(rp[c.first]<c.second){
            rp[c.first] = c.second;
        }
    }
}
int main(){
    int n;
    cin>>n;
    vector<int64_t> a(n);
    int64_t ans=0;
    rep(i,n){
        cin>>a[i];
        fl(a[i]);
    }
    /*
    for (auto c:rp){
        cout<<c.first<<" "<<c.second<<endl;
    }
    */
    //cout<<l%big<<endl;
    int64_t l=1;
    for(auto c:rp){
        rep(i,c.second){
            l *= c.first;
            l %=big;
        }
    }
    rep(i,n){
        ans += div(l,a[i],big);
    }
    cout<<ans%big<<endl;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const int inf=1e9;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h,w,d;
  cin>>h>>w>>d;
  map<int,P> cnt;
  rep(i,h)rep(j,w){
    int a;
    cin>>a;
    cnt[a]=P(i,j);
  }
  vector<vector<int>> dp(h,vector<int>(w,-1));
  FOR(i,1,h*w+1){
    P now=cnt[i];
    if(dp[now.fi][now.se]!=-1) continue;
    dp[now.fi][now.se]=0;
    int p=i;
    while(p+d<=h*w){
      p+=d;
      P ne=cnt[p];
      dp[ne.fi][ne.se]=dp[now.fi][now.se]+abs(now.fi-ne.fi)+abs(now.se-ne.se);
      now=ne;
    }
  }
  int q;
  cin>>q;
  rep(i,q){
    int l,r;
    cin>>l>>r;
    cout<<dp[cnt[r].fi][cnt[r].se]-dp[cnt[l].fi][cnt[l].se]<<endl;
  }
}

Measured memory_bytes: 7168
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);

void solve()
{
    ll a , b; cin >> a >> b;
    cout << (a * b) << "\n";
}

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

Measured memory_bytes: 3632
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nya_n "(=^･ω･^=)"
typedef long long ll;
using namespace std;


/*
ll gcd(ll x, ll y) {
if (y == 0) return x;
return gcd(y, x%y);
}
/*
ll lcm(ll x, ll y) {
ll g = gcd(x, y);
return x / g * y;
}
ll pw(int x, int n) {
	ll y = 1;
	ll p = x;
	while (n != 0) {
		if (n % 2) {
			y = y*p%mod;
			n = n - 1;
		}
		else {
			p = p*p%mod;
			n = n / 2;
		}
	}
	return y;
}

ll modinv(ll x) {
	return pw(x, mod - 2);
}*/
string s;
ll k;
int main() {
	cin >> s >> k;
	for (ll i = 0; i < s.size() && i < k; i++) {
		if (s[i] != '1') {
			cout << s[i] << endl;
			return 0;
		}
	}
	cout << 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long mod = 1e9+7;
int mark[2009] = {};
int limit = 0;
long long dp[2050] = {};
long long getSum(long long n)
{
    if(dp[n] != -1)
    {
        return dp[n];
    }
    if(n == 0)
    {
        return 1;
    }
    long long res = 0;
    for(int i = 1; i <= limit; i++)
    {
        if(n-mark[i] >= 0)
        {
            res =(res+getSum(n-mark[i]))%mod;
        }
    }
    return dp[n] = res%mod;
}
void solve()
{
    long long n; cin >> n;
    for(int i = 3; i <= n; i++)
    {
        limit++;
        mark[limit] = i;
    }
    long long sum = getSum(n)%mod;
    cout << sum << endl;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    solve();
    return 0;
}


Measured memory_bytes: 3652
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Ankur Dua
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>


using namespace std;


using ll = long long;
ll mod=1000000007;
ll *fact, *ifact;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


ll modExp(ll base, ll exp, ll mod=::mod){
    ll ans=1;
    while(exp) {
        if (exp & 1) {
            (ans *= base) %= mod;
        }
        (base *= base) %= mod;
        exp>>=1;
    }
    return ans;
}
ll modInv(ll x, ll mod=::mod){
    return modExp(x,mod-2,mod);
}
void modFact(ll n, ll mod=::mod){
    ifact=new ll[n+1];
    fact=new ll[n+1];
    fact[0]=fact[1]=1;
    for(int i=2;i<=n;i++){
        fact[i]=(i*fact[i-1])%mod;
    }
    ifact[n]=modInv(fact[n], mod);
    for(int i=n-1;i>=0;i--){
        ifact[i]=((i+1)*ifact[i+1])%mod;
    }
}
ll ncr(ll n, ll r, ll mod=::mod){
    if(n<r || r<0)
        return 0;
    ll ans=fact[n];
    ans*=ifact[r];
    ans%=mod;
    ans*=ifact[n-r];
    ans%=mod;
    return ans;
}
ll npr(ll n, ll r, ll mod=::mod){
    if(n<r || r<0)
        return 0;
    ll ans=fact[n];
    ans*=ifact[n-r];
    return ans%mod;
}

template <typename T>
void coordinateCompress(vector<T> &v, T start = 1){
    vector<T> cpy = v;
    sort(cpy.begin(), cpy.end());
    map<T,T> mp;
    for(T x:cpy){
        mp[x]=start++;
    }
    for(T &x:v){
        x=mp[x];
    }
}
template<typename T1, typename T2>
istream& operator >>(istream& cin, pair<T1, T2> &p){
	cin>>p.first>>p.second;
	return cin;
}
using namespace std;

class CSkillUp {
public:
	void solve(std::istream& cin, std::ostream& cout) {
		int x,sol=INT_MAX;
		function<void(vector<vector<int> > &v, int n, int m, vector<int> &ans, int amt)> solve=[&](vector<vector<int> > &v, int n, int m, vector<int> &ans, int amt){
			if (n==0){
				for (int i=0;i<m;i++)
					if(ans[i]<x)
						return;
				sol=min(sol,amt);
				return;
			}
			solve(v,n-1,m,ans,amt);
			for (int i=1;i<=m;i++)
				ans[i-1]+=v[n-1][i];
			amt+=v[n-1][0];
			solve(v,n-1,m,ans,amt);
			for (int i=1;i<=m;i++)
				ans[i-1]-=v[n-1][i];
		};
		int n,m,amt=0;
		cin>>n>>m>>x;
		vector<int> v1, ans(m,0);
		vector< vector<int> > v(n,v1);
		for (int i=0;i<n;i++)
		for (int j=0;j<=m;j++){
			int val;
			cin>>val;
			v[i].push_back(val);
		}
		solve(v,n,m,ans,amt);
		if (sol==INT_MAX)
			cout<<-1;
		else
			cout<<sol;

	}
};


int main() {
	CSkillUp solver;
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3588
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

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

a,b = MAP()
print(len(set(prime_factorize(a)) & set(prime_factorize(b)))+1)



Measured memory_bytes: 3440
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>
#include <cstring>
#include <iterator>
#include <map>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
#include <assert.h>
#include <array>

using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mn(x) *min_element((x).begin(),(x).end())
#define mx(x) *max_element((x).begin(),(x).end())
//#define sum(x) accumulate((x).begin(),(x).end(),0ll)
#define eb emplace_back
#define el '\n'
typedef  long long  ll;
typedef  unsigned long long  ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<string> vs;

const ld pi=acos(-1);
const ll inf=(ll)1e9+1;
const int mod=1000000007;
//const int mod=998244353;

int n,m,k;
const int N=2e5+10;


vi P(N);
vi S(N);
void ms(int u){
    P[u]=u;
    S[u]=1;
}
int fs(int u){
    return P[u]=u==P[u]?u:fs(P[u]);
}
void me(int u, int v){
    u=fs(u);
    v=fs(v);
    if(u!=v){
        if(S[u]>S[v])
            swap(u,v);
        P[u]=v;
        S[v]+=S[u];
    }
    
}


int main()
{   ios_base::sync_with_stdio(false);cin.tie(NULL);
    int q,t,u,v,h;
    ll x,a,b,c,d,y,z;
    cin >> n >> m;
    for(int i=0; i<n; i++){
        ms(i);
    }
    for(int i=0; i<m; i++){
        cin >> u >> v;
        me(--u,--v);
    }
    u=0;
    for(int i=0; i<n; i++){
        u=max(u,S[i]);
    }
    cout << u << el;
    
    return 0;
}







Measured memory_bytes: 4692
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100];
ll dp[100000+1][100+1];
ll ps[100];
ll p=1000000000+7;
ll f(ll k,ll n)
{
  if(dp[k][n]!=-1)
  return dp[k][n];
  
  if((n==0))
  {
      dp[k][n]=f(k-1,n);
      
      return dp[k][n];
  }
  
  if(k==0)
  {dp[k][n]=1;
  
  return dp[k][n];}
  
  if(ps[n-1]<k)
  {
      dp[k][n]=f(k-1,n);
      
      return dp[k][n];
  }
  
  if(n==1)
  {
      dp[k][n]=1+f(k-1,n);
      return dp[k][n];
  }
  

  if(k>a[n-1])
  dp[k][n]=(((f(k,n-1)%p-f(k-a[n-1]-1,n-1)%p+p)%p)+(f(k-1,n)%p))%p;
  
  else
  dp[k][n]=((f(k,n-1)%p+f(k-1,n)%p)%p);

  return dp[k][n];
}
int main()
{
    ll n,k;
    cin>>n>>k;
    
    for(ll i=0;i<=100000;i++)
    {
        for(ll j=0;j<=100;j++)
        dp[i][j]=-1;
    }

    
    for(ll i=0;i<n;i++)
    cin>>a[i];
    
    ps[0]=a[0];
    
    for(ll i=1;i<n;i++)
    ps[i]=(a[i]+ps[i-1])%p;
    
    
    f(k,n);
    
    if(k>0)
    cout<<(dp[k][n]%p-dp[k-1][n]%p+p)%p<<endl;
    
    else
    cout<<dp[k][n]%p<<endl;
    
    //cout<<dp[k][n];
    
    
}

Measured memory_bytes: 83968
#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()

int main(){
  string s;cin>>s;
  const int m=1e9+7;
  int ssz=s.size();
  ll dp[ssz+1][4]={};
  dp[0][0]=1;
  rep(i,ssz){
    rep(j,4){
      dp[i+1][j]=dp[i][j];
      dp[i+1][j]%=m;
    }
    if(s[i]=='A'){
      dp[i+1][1]+=dp[i][0];
      dp[i+1][1]%=m;
    }
    else if(s[i]=='B'){
      dp[i+1][2]+=dp[i][1];
      dp[i+1][2]%=m;
    }
    else if(s[i]=='C'){
      dp[i+1][3]+=dp[i][2];
      dp[i+1][3]%=m;
    }
    else{
      dp[i+1][0]+=2*dp[i][0];
      dp[i+1][1]+=2*dp[i][1]+dp[i][0];
      dp[i+1][2]+=2*dp[i][2]+dp[i][1];
      dp[i+1][3]+=2*dp[i][3]+dp[i][2];
      rep(j,4)dp[i+1][j]%=m;
    }
  }
  cout<<dp[ssz][3]<<endl;
}

Measured memory_bytes: 3584
N, X, Y = gets.split.map(&:to_i)

X -= 1
Y -= 1

ans = Array.new(N, 0)

N.times do |sv|
  depths = Array.new(N, Float::INFINITY)
  queue = []

  depths[sv] = 0
  queue.push sv

  until queue.empty? do
    v = queue.shift
    d = depths[v]

    if v + 1 < N && depths[v + 1] == Float::INFINITY
      depths[v+1] = d + 1
      queue.push v + 1
    end

    if v - 1 >= 0 && depths[v - 1] == Float::INFINITY
      depths[v-1] = d + 1
      queue.push v - 1
    end

    if v == X
      if depths[Y] == Float::INFINITY
        depths[Y] = d + 1
        queue.push Y
      end
    end

    if v == Y
      if depths[X] == Float::INFINITY
        depths[X] = d + 1
        queue.push X
      end
    end
  end

  N.times do |i|
    ans[depths[i]] += 1
  end
end

ans[1..(N-1)].each do |a|
  puts a / 2
end


Measured memory_bytes: 27156
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
inline bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
inline bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll k, q;
  cin >> k >> q;
  vll d(k);
  rep(i, k){
    cin >> d[i];
  }
  vll e(k);
  vll es(k+1, 0);
  vll zc(k+1, 0);
  while(q--){
    ll n, x, m;
    cin >> n >> x >> m;
    n--;
    x %= m;
    rep(i, k){
      e[i] = d[i] % m;
    }
    // rounds
    repr(i, 1, k+1){
      es[i] = es[i-1] + e[i-1];
    }
    repr(i, 1, k+1){
      zc[i] = zc[i-1] + (e[i-1] == 0);
    }
    dump(es);
    dump(x, es[k]*(n/k), es[n%k]);
    ll rounds = (x + es[k]*(n/k) + es[n%k])/m;
    ll zerocnt = (zc[k]*(n/k) + zc[n%k]);
    dump(n, rounds, zerocnt);
    print(n-rounds-zerocnt);
  }
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
 
int l,r,d;

 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
  	cin>>l>>r>>d;
  	cout<<(r/d)-(l-1)/d<<endl;



    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;

void show(set<int> s) {
	for (auto e : s) {
		cout << e << " ";
	}
	cout << endl;
}

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

	vector<set<int>> connect(n + 1);
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b;
		connect[a].insert(b);
		connect[b].insert(a);
	}

	vector<int> which(n + 1, 0);
	which[1] = 1;
	which[n] = 2;

	set<int> a_nexts = {1};
	set<int> b_nexts = {n};

	// set<int> as = a_nexts;
	// set<int> bs = b_nexts;

	while(!a_nexts.empty() || !b_nexts.empty()) {
		auto a_checks = a_nexts;
		a_nexts.clear();
		for (auto aa : a_checks) {
			for (auto a_next : connect[aa]) {
				if (which[a_next] == 0) {
					which[a_next] = 1;
					a_nexts.insert(a_next);
					connect[a_next].erase(aa);
					// as.insert(a_next);
				}
			}
			connect[aa].clear();
		}

		auto b_checks = b_nexts;
		b_nexts.clear();
		for (auto bb : b_checks) {
			for (auto b_next : connect[bb]) {
				if (which[b_next] == 0) {
					which[b_next] = 2;
					b_nexts.insert(b_next);
					connect[b_next].erase(bb);
					// bs.insert(b_next);
				}
			}
			connect[bb].clear();
		}
	}


	int na = count(which.begin(), which.end(), 1);
	int nb = count(which.begin(), which.end(), 2);

	cout << (na > nb ? "Fennec" : "Snuke") << endl;
	// show(as);
	// show(bs);

	return 0;
}


Measured memory_bytes: 14720
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        Map<Integer, Integer> freq = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int score = scanner.nextInt();
            if (!freq.containsKey(score)){
                freq.put(score, 1);
            }
            else freq.put(score, 1 + freq.get(score));
        }

        int m = scanner.nextInt();
        boolean can = true;
        for (int i = 0; i < m; i++) {
            int s = scanner.nextInt();
            if (freq.containsKey(s) && freq.get(s) > 0){
                freq.put(s, freq.get(s) - 1);
            }
            else if (freq.containsKey(s) && freq.get(s) == 0){
                can = false;
            }
            else can = false;
        }

        System.out.println(can?"YES":"NO");
    }
}


Measured memory_bytes: 141920
A = input()
B = input()
if len(A) > len(B): print('GREATER')
elif len(A) < len(B): print('LESS')
else:
	for i in range(0, len(A)):
		if A[i] > B[i]:
			print('GREATER')
			break
		if A[i] < B[i]:
			print('LESS')
			break
		if i == len(A)-1:
			print('EQUAL')

Measured memory_bytes: 38256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

map<int, int> dists;

void solve(const int N, const int X, const int Y) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            // i to j
            int d1 = abs(i - j);
            int d2 = abs(i - X) + 1 + abs(j - Y); // use bipass from X
            int d3 = abs(i - Y) + 1 + abs(j - X); // use bipass from Y
            int d = min(min(d1, d2), d3);
            dists[d]++;
        }
    }
}

int main(void) {
    int N, X, Y;
    cin >> N >> X >> Y;

    solve(N, X, Y);

    for (int i = 1; i <= N - 1; i++) {
        cout << dists[i] / 2 << endl;
    }

    return 0;
}


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

using namespace std;

const int N = 100005;

int a[N][3];
int f[N][3];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
  }
  f[0][0] = a[0][0];
  f[0][1] = a[0][1];
  f[0][2] = a[0][2];
  for (int i = 1; i < n; i++) {
    f[i][0] = a[i][0] + max(f[i - 1][1], f[i - 1][2]);
    f[i][1] = a[i][1] + max(f[i - 1][0], f[i - 1][2]);
    f[i][2] = a[i][2] + max(f[i - 1][0], f[i - 1][1]);
  }
  int ans = max(f[n - 1][0], f[n - 1][1]);
  ans = max(ans, f[n - 1][2]);
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 2560
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    s = input()
    n = len(s)
    nm = 0
    for i in s:
        if i == "o":
            nm += 1

    if nm >= 8-(15-n):
        print("YES")
    else:
        print("NO")

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 74888
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

// konoshita kara kaku

int main(void){
	int n=in(),p=in(),a,i,f=0;
	long long ans=1;
	rep(i,n)ans*=2;
	rep(i,n){
		a=in();
		f|=a%2;
	}
	if(f)llprint(ans/2);
	else llprint(p?0:ans);
	return 0;
}

Measured memory_bytes: 128
n,k,*a=map(int,open(0).read().split())
l,r,*b=[[]for _ in range(200003)]
for i,v in enumerate(a):
  b[v]+=i,
  l+=len(b[v]),
s=a[0]
i=c=0
while i<n:
  j=l[i]%len(b[s])
  c+=j<1
  i=b[s][j]+1
  s=a[i%n]
k%=c+1
i=c=0
while i<n:
  j=l[i]%len(b[s])
  if c>k-2and j<1:
    r+=s,
    i+=1
  else:i=b[s][j]+1
  c+=j<1
  s=a[i%n]
print(*r)

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

typedef long long ll;

struct edge{
    int to;
    int cost;
    edge(int t, ll c) : to(t), cost(c) {}
};

vector<edge> v[100000];
bool visit[100000] = {};
ll value[100000] = {};
bool judge = true;

void dfs(int s, ll accum){
    visit[s] = true;
    value[s] = accum;
    for(edge e : v[s]){
        if(!visit[e.to]){
            dfs(e.to, value[s] + e.cost);
        }else{
            if(value[s] + e.cost != value[e.to]){
                judge = false;
                return;
            }
        }
    }
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);

    int l, r, d;
    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &l, &r, &d);
        l--, r--;
        v[l].push_back(edge(r,d));
        v[r].push_back(edge(l,-d));
    }

    for(int i = 0; i < n; i++){
        if(!visit[i]){
            dfs(i, 0);
        }
    }

    if(judge)   cout << "Yes" << endl;
    else        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 11520
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    string s, t;
    cin >> s >> t;
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    sort(s.begin(), s.end());
    if (s < t) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
	int n;
	cin >> n;
	cout << fixed << setprecision(10);
	vector<int>a(n);
	for (int i = 0; i < n; i++)cin >> a.at(i);
	double ans = 0;
	for (int i = 0; i < n; i++)ans += (double)1 / a.at(i);
	ans = 1 / ans;
	cout << ans << endl;
}

Measured memory_bytes: 256