akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template <class T>
struct FenwickTree {
    const int n;
    std::vector<T> bit;

    FenwickTree(int _n = 0) : n(_n), bit(n + 1, 0) {}

    T sum(int r) const {
        T res = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) res += bit[r];
        return res;
    }
    T sum(int l, int r) const { return sum(r) - sum(l); }
    void add(int idx, const T &w) { for (; idx < n; idx |= idx + 1) bit[idx] += w; }
    int size() const { return n; }
};

class ProblemD {
public:
    ProblemD(ll _n) : n(_n), a(_n + 1), s(_n + 1, 0) {}
    void Input() { for (int i = 1; i <= n; ++i) cin >> a[i]; }

    int Solve() {
        const ll lim = ceil(n * (n + 1) / 4.0);

        ll lb = 0, ub = *max_element(a.begin(), a.end()) + 1;
        while (ub - lb > 1) {
            ll mid = 0.5 * (lb + ub), res = Check(mid);

            if (lim <= res) lb = mid;
            else ub = mid;
        }

        return lb;
    }

private:
    ll n;
    vector<int> a;
    vector<ll> s;

    ll Check(const int x) {
        for (int i = 1; i <= n; ++i) s[i] = (x <= a[i] ? 1 : -1) + s[i - 1];

        ll res = 0;
        FenwickTree<int> tree(2 * n + 1);

//        tree.add(s[0] + n, 1);
        for (int i = 0; i <= n; ++i) {
            res += tree.sum(0, s[i] + n + 1);
            tree.add(s[i] + n, 1);
        }

        return res;
    }
};

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

    int n;
    cin >> n;
    ProblemD p(n);
    p.Input();
    cout << p.Solve() << endl;

    return 0;
}


Measured memory_bytes: 2288
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	long long A, B;
	int K;
	cin >> A >> B >> K;

	for(int i=0; i<K; i++){
		if(i%2 == 0){
			if(A%2 == 1)
				A--;

			B += A/2;
			A /= 2;
		}
		else{
			if(B%2 == 1)
				B--;

			A += B/2;
			B /= 2;
		}
	}

	cout << A << " " << B << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int x,y,z;
    cin>>x>>y>>z;
    if(-100<x<100 && -100<y<100 && -100 <z<100){
         if(x==y)
            cout<<z;
        else if(x==z)
            cout<<y;
        else if(z==x)
            cout<<y;
        else if(z==y)
            cout<<x;
    }
    else
    cout<<"error";
    return 0;
}


Measured memory_bytes: 256
S = input()
T = input()
ans = len(T)
for i in range(len(S)-len(T)+1):
    tmp = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            tmp += 1
        # print(S[i+j])
    ans = min(ans, tmp)
print(ans)


Measured memory_bytes: 73212
#include<stdio.h>
int main(void)
{
	int h[10],k[10],a,b,c,d,i,sum,sum1;
	for(i=0;i<2;i++){
		scanf("%d",&h[i]);
	}
	for(i=0;i<2;i++){
		scanf("%d",&k[i]);
	}
	scanf("%d%d%d%d",&a,&b,&c,&d);
	sum=0; sum1=0;
	sum+=h[0]*a; sum1+=k[0]*a;
	sum+=h[1]*b; sum1+=k[1]*b;
	sum+=h[0]/10*c; sum1+=k[0]/10*c;
	sum+=h[1]/20*d; sum1+=k[1]/20*d;
	if(sum<sum1) printf("kenjiro\n");
	else if(sum>sum1) printf("hiroshi\n");
	else printf("even\n");
	// printf("%d %d\n",sum,sum1);
	return 0;
}

Measured memory_bytes: 2680
use v5.18;
use warnings;
sub read_line { chomp(my $s = <>); $s }
sub splited_read_line { split / /, read_line }

my $s = read_line;
my $k = read_line;
my @nums = map { $_ + 0 } split //, $s;

my $current_idx = 0;
my $ans_num;
for my $num (@nums) {
  $current_idx += $num;
  if ($num != 1 || $current_idx >= $k) {
    $ans_num = $num;
    last;
  }
}
say $ans_num;


Measured memory_bytes: 640
import collections
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])
q = collections.deque([1])
mod = (10 ** 9) + 7
w = 1
while(w <= n):
	if w == 0:
		q.append(1)
	else:
		q.append((1 if w not in forbidden else 0) * (sum(q) % mod))
	w += 1
	if len(q) == 3: q.popleft() 
print q[-1]

Measured memory_bytes: 48156
/*************************************************************************
    > File Name: e.cpp
    > Author: Amano Sei
    > Mail: amano_sei@outlook.com 
    > Created Time: 2020年01月02日 星期四 23时03分52秒
 ************************************************************************/

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 100005;

int a[maxn];
long long s[maxn];

int main(){
    int n;
    long long m;
    scanf("%d%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(&a[1], &a[n+1]);
    for(int i = 1; i <= n; i++)
        s[i] = s[i-1]+a[i];
    for(int i = 0; i <= n; i++)
        s[i] = s[n]-s[i];

    register int cl = 2*a[1], cr = 2*a[n];
    register long long ans, cnt;
    int *const ap = &a[n+1];
    while(cl <= cr){
        ans = cnt = 0;
        register int cm = (cl+cr)>>1;
        for(int i = 1; i <= n; i++){
            register long long ci = ap-lower_bound(&a[1], &a[n+1], cm-a[i]);
            cnt += ci;
            ans += ci*a[i]+s[n-ci];
        }
        if(cnt > m)
            cl = cm+1;
        else if(cnt < m)
            cr = cm-1;
        else
            break;
    }
    if(cnt != m)
        ans += cr*(m-cnt);
    printf("%lld\n", ans);
}



Measured memory_bytes: 1280
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll long long
#define pb push_back 
#define ins insert
#define rs resize
#define br break;
#define cont continue;
#define vi vector<int>
#define vll vector<long long>
#define si set<ll>
#define sll set<long long>
#define pii pair<ll,ll>
#define pll pair<long long, long long>
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);
#define vec vector
#define cend cout<<endl;
#define sc second
#define fr first
#define retz return 0;
#define ll_MAX (ll)(1e9*1e9)
#define ll_MIN (ll)(-1e9*1e9)
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b)  for(int i=a; i<=b; i++)
#define repd(i,a,b) for(int i=a; i>=b; i--)
#define ps(arr, n) for(int i=1; i<n; i++)arr[i]+=arr[i-1];
#define inp(arr, n)for(int i=0; i<n; i++)cin>>arr[i];
#define out(arr, n)for(int i=0; i<n; i++)cout<<arr[i];
#define inp1(arr,n,m)for(int i=0; i<n; i++)for(int j=0;j<m;j++)cin>>arr[i][j];
#define out1(arr,n,m)for(int i=0; i<n; i++)for(int j=0;j<m;j++)cin>>arr[i][j];
#define loop(q) for(auto it:q)
#define loop1(q) for(auto&it:q)
#define db1 cout << "*" << endl
#define db2 cout << "YES" << endl
using namespace std;
using namespace __gnu_pbds; 
#define oset(X) tree<X,null_type,less<X>, rb_tree_tag, tree_order_statistics_node_update> 
#define roset(X) tree<X,null_type,greater<X>, rb_tree_tag, tree_order_statistics_node_update>  
#define okey order_of_key //lower_bound_set
#define ofind find_by_order
#define cyes cout << "Yes" << endl; 
#define cno cout << "No" << endl;
#define mod 1000000007
#define mod1 998244353
#define INT_MAX1 900000000


void solve()
{
    int k, x;
    cin >> k >> x;
    if(k*500 >= x)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

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

Measured memory_bytes: 256
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	aa := make([]int, n)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt(scanner)
	}
	g := aa[0]
	for i := 1; i < n; i++ {
		g = gcd(g, aa[i])
	}
	fmt.Fprintln(writer, g)
}

func gcd(m, n int) int {
	if n == 0 {
		return m
	}
	return gcd(n, m%n)
}


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

int main(){
	int n, k, rec, rem;
	long long ans;
	scanf("%d %d",&n,&k);
	if (k == 0){
		printf("%lld\n", 1LL * n * n);
		return 0;
	}
	ans = 0;
	for (int i = k + 1; i <= n; i++){
		rec = n / i;
		rem = n % i;
		ans += 1LL * rec * (i - k) + max(rem - k + 1, 0);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
N, Q = map(int, input().split())
S = input()
qs = [list(map(int, input().split())) for i in range(Q)]
t =[0] * N
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)
def ans(l, r):
    return t[r-1] - t[l-1]
for l, r in qs:
    print(ans(l,r))



Measured memory_bytes: 32304
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        List<Long> list = new ArrayList<>();
        long ans = 0;
        for(int i = 0;i<n;i++){
            long num = sc.nextLong();
            list.add(num);
            ans += num;
        }
        Collections.sort(list);
        Collections.reverse(list);
        if(k > n){
            k = n;
        }
        for(int i = 0;i<k;i++){
            ans -= list.get(i);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 94692
#include "bits/stdc++.h"
using namespace std;

long long MOD = 1000003;
static long long F[1000010] = {}, RF[1000010] = {};

long long Calc(long long A, long long B) {
	if (B == 0) return 1;
	if (B % 2 == 0) {
		long long C = Calc(A, B / 2);
		return (C * C) % MOD;
	}
	return (A * Calc(A, B - 1)) % MOD;
}

int main() {
	F[0] = F[1] = RF[0] = RF[1] = 1;
	for (int i = 2; i < MOD; i++) {
		F[i] = F[i - 1] * i;
		F[i] = F[i] % MOD;
		RF[i] = Calc(F[i], MOD - 2);
	}
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		long long X, D, N;
		cin >> X >> D >> N;
		if (D == 0) {
			cout << Calc(X, N) << endl;
			continue;
		}
		X = (X * Calc(D, MOD - 2)) % MOD;
		if (X + N - 1 >= MOD || X == 0) {
			cout << 0 << endl;
			continue;
		}
		cout << ((F[X + N - 1] * RF[X - 1]) % MOD * Calc(D, N)) % MOD << endl;
	}
}

Measured memory_bytes: 16512
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main() 
{
  int a, b; cin >> a >> b;
  if(a+b >= 10)cout << "error" << endl;
  else cout << a+b << endl;
  system("pause");
}

Measured memory_bytes: 504
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
int vis[333];
int main(){
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	int n,m,a,b;
	cin>>n>>m;
	cin>>a;
	for(int i=1;i<=a;i++)cin>>b,vis[b]=1;
	for(int i=2;i<=n;i++){
		cin>>a;
		int mid[333];
		mem(mid);
		for(int j=1;j<=a;j++)cin>>b,mid[b]=1;
		for(int j=1;j<=30;j++)vis[j]=vis[j]&mid[j];
	}
	int cnt=0;
	for(int i=1;i<=30;i++)cnt+=vis[i];
		cout<<cnt;
	return 0;
}

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


int main(){

	int A , B , C ;
	cin >> A >> B >> C ;
	if( (A == B && B != C) || ( B == C && C != A ) || ( C == A && A != B ) ) puts("Yes");
	else puts("No");

	return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>  // min, max
#include <fstream>  // ifstream
#include <iomanip>  // setprecision
using namespace std;
typedef long long ll;

int main(void)
{
#ifdef FILE_DEBUG
    ifstream inputFile("data/input.txt");
    cin.rdbuf(inputFile.rdbuf());
#endif
    // これより下にコードを書く

    vector<int> data(3);
    cin >> data[0] >> data[1] >> data[2];

    sort(data.begin(), data.end());

    cout << data[0] + data[1] << endl;
    return 0;
}


Measured memory_bytes: 256
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define divup(a,b) ( ( (a) + ( (b) - 1u) ) / (b) ) // a/b の余り切り上げ
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
ll mod = 1000000007;

signed main(){
    ll n,ans;
    scanf("%lld",&n);
    vector<ll> a(n);
    ll c[100009];
    rep(i,100009) c[i]=0;
    rep(i,n){
        scanf("%lld",&a[i]);
        c[a[i]]++;
    }
    sort(a.begin(),a.end());
    ll sp=0,ne=0;
    rep(i,100009){
        if(c[i]>0) ne++;
        if(c[i]>=2) sp += c[i]-1;
    }
    if(sp%2==0) ans = ne;
    else ans = ne-1;
    printf("%lld\n",ans);
}


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

int main(void){
        int i,n,poi[1000];
        while(1){
                double std,ave=0,a=0;
                scanf("%d",&n);
                if(!n)
                        break;
                for(i=0;i<n;i++){
                        scanf("%d",&poi[i]);
                        ave+=poi[i];
                }
                ave/=n;
                for(i=0;i<n;i++)
                        a+=pow((poi[i]-ave),2);
                a/=n;
                std=sqrt(a);
                printf("%f\n",std);
        }
        return 0;
}

Measured memory_bytes: 636
#include<stdio.h>
int main(void){
    long long t,n,sum,max,min,a[10000];
    scanf("%lld",&n);
    for(t=0;t<n;t++){
        scanf("%lld",&a[t]);
    }
    sum=0;
    max=a[0];
    min=a[0];
    for(t=0;t<n;t++){
        sum+=a[t];
        if(max<a[t]){
            max=a[t];
        }else if(min>a[t]){
            min=a[t];
        }
            
    }
    printf("%lld %lld %lld\n",min,max,sum);
    return 0;
}


Measured memory_bytes: 2056
#include <cassert>
#include <array>
#include <algorithm>
#include <iostream>
#include <complex>
#include <vector>
using namespace std;

const double EPS = 1e-10;
template<class T>
bool eq(const T& a, const T& b) {return abs(a - b) < EPS;}

typedef complex<double> point;

// sort/unique用、setではうまく動かないので使うべからず
namespace std {
	bool operator==(const point &a, const point &b){
		return eq(a, b);
	}
	bool operator<(const point& a, const point& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}

double cross(const point& a, const point& b) {
	return imag(conj(a)*b);
}
double dot(const point& a, const point& b) {
	return real(conj(a)*b);
}

typedef array<point, 2> line;

bool intersectLL(const line& l, const line& m) {
	return !eq(cross(l[1]-l[0], m[1]-m[0]), 0.) || // non-parallel
			eq(cross(l[1]-l[0], m[0]-l[0]), 0.);   // same line
}

point crosspoint(const line& l, const line& m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (eq(A, 0.) && eq(B, 0.)) return m[0]; // same line
	if (eq(A, 0.)) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
	return m[0] + B / A * (m[1] - m[0]);
}

vector<line> lines;

int hitCount(const line& s) {
	vector<point> hits;
	for (const auto& t : lines) {
		if (intersectLL(s, t)) {
			point p = crosspoint(s, t);
			if (-100 < p.real() && p.real() < 100 && -100 < p.imag() && p.imag() < 100) {
				hits.push_back(p);
			}
		}
	}
	sort(hits.begin(), hits.end());
	auto it = unique(hits.begin(), hits.end());
	return it - hits.begin();
}

int main() {
	int n;
	while (cin >> n, n) {
		int cnt = 1;
		lines.clear();
		for (int i = 0; i < n; i++) {
			line l;
			for (auto& p : l) {
				int x, y;
				cin >> x >> y;
				p = point(x, y);
			}
			cnt += hitCount(l) + 1;
			lines.push_back(l);
		}
		cout << cnt << endl;
	}
	return 0;
}

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

using namespace std;

int main() {
  int N, M, ans = -1;
  
  cin >> N >> M;
  
  vector<int> divisor;
  
  for (int i = 1; (long long)i * i <= M; i++) {
    if (M % i == 0) {
      if (M >= (long long)i * N) {
        ans = max(ans, i);
      }
      
      if (i >= N) {
        ans = max(ans, M / i);
      }
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reg(i,a,b) for(int i=(a);i<=(b);i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=(b);i>=(a);i--)
typedef long long int lli;
typedef pair<int,int> mp;
typedef pair<char,int> cp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX


int n,m;

vector<int> vs[100005];
int uni[100010];
int ma[100005];
int marked[100005];

void dfs(int no,int p){
	ma[no] = p;
	if(marked[no]>=1)p = no;
	else uni[no] = p;
	
	rep(i,vs[no].size()){
		dfs(vs[no][i],p);
	}
}

int find(int p){
	if(uni[p] == p)return p;
	uni[p] = find(uni[p]);
	return uni[p];
}



int main(void){
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0)break;
		reg(i,1,n){
			vs[i].clear();
			uni[i] = i;
		}
		memset(marked,0,sizeof(marked));
		
		reg(i,2,n){
			int a;
			scanf("%d",&a);
			vs[a].push_back(i);
		}
		
		vector<cp> qs;
		rep(i,m){
			int a;
			char s[5];
			scanf("%s%d",s,&a);
			if(s[0]=='M')marked[a]++;
			qs.push_back(cp(s[0],a));
		}
		
		marked[1] = 1;
		dfs(1,1);
		
		lli ans = 0;
		irep(i,qs.size()){
			int a = qs[i].sec;
			if(qs[i].fir == 'Q'){
				lli na = find(a);
				ans += na;
			}
			else{
				marked[a]--;
				if(marked[a]>0)continue;
				//if(find(a) == find(ma[a]))continue;
				uni[a] = find(ma[a]);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 12644
S = input()

result = [0] * len(S)
temp = "R"
base_point = 0
for idx, s in enumerate(S):
    if s != temp:
        if temp == "R":
            result[idx - 1] += (((idx - 1) - base_point) // 2) + 1
            result[idx] += ((idx - base_point) // 2) + 1
            base_point = idx + 1

        else:
            result[base_point - 2] += (idx - (base_point - 1)) // 2
            result[base_point - 1] += (idx - base_point) // 2
            base_point = idx

        temp = s
else:
    result[base_point - 2] += (len(S) - (base_point - 1)) // 2
    result[base_point - 1] += (len(S) - base_point) // 2


print(" ".join(map(str, result)))


Measured memory_bytes: 10484
from bisect import *
n, k = map(int, input().split())
a = list(map(int, input().split()))

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= nega-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)


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

int main(int argc, const char * argv[]) {
    int  N,a,b;
    string s;
    cin >> N >> a >> b;
    cin >> s;
    
    int lim = a+b;
    int count = 0;
    int foreignC = 0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='c'){
            cout << "No" << endl;
        }else if(s[i] == 'a'){
            if(count < lim) {
                cout << "Yes" << endl;
                count++;
            }
            else cout << "No" << endl;
        }else{
            if(count < lim && foreignC < b){
                count++;
                foreignC++;
            cout << "Yes" << endl;
            }
            else cout << "No" << endl;

        }
    }
    return 0;
}


Measured memory_bytes: 896
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	Main(BufferedReader in) throws IOException {
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		long sum = 0L;
		for (int i = 1; i <= N; ++i) {
			if ((i % 3 != 0) && (i % 5 != 0)) {
				sum += i;
			}
		}
		System.out.println(sum);
	}

	void calc() {
	}

	void showResult() {
	}
}


Measured memory_bytes: 32688
#include <iostream>
#include <utility>
#include <algorithm>
#define llint long long
#define mod 1000000007

using namespace std;
typedef pair<int, int> P;

llint h, w, n;
P p[3005];
llint dp[3005][2];

llint fact[200005], fact_inv[200005];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < 200005; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	for(int i = 0; i < 200005; i++){
		fact_inv[i] = modpow(fact[i], mod-2);
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

int main(void)
{
	make_fact();
	cin >> h >> w >> n;
	
	llint r, c;
	for(int i = 1; i <= n; i++){
		cin >> r >> c;
		p[i] = make_pair(r, c);
	}
	sort(p+1, p+n+1);
	
	p[0] = make_pair(1, 1); dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < i; k++){
				if(p[k].first > p[i].first || p[k].second > p[i].second) continue;
				dp[i][j] += dp[k][1-j] * comb(p[i].first-p[k].first+p[i].second-p[k].second, p[i].first-p[k].first) % mod;
				dp[i][j] %= mod;
			}
		}
	}
	
	llint ans = comb(h+w-2, w-1) % mod;
	for(int i = 1; i <= n; i++){
		ans += dp[i][0] * comb(h-p[i].first+w-p[i].second, h-p[i].first) % mod;
		ans %= mod;
	}
	for(int i = 1; i <= n; i++){
		ans += mod - dp[i][1] * comb(h-p[i].first+w-p[i].second, h-p[i].first) % mod;
		ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
int main(){
    int q;
    cin>>q;
    bool primes[100001];
    memset(primes , true , sizeof(primes));
    primes[0] = primes[1] = false;
    for(int i = 2 ; i*i<=100006 ; i++){
        if(primes[i]){
            for(int j = i*i ; j<=100006 ; j+=i){
                primes[j] = false;
            }
        }
    }
    int pref[100001];
    pref[0] = 0;
    for(int i = 1 ; i<100001 ; i++){
        if(primes[i] && primes[(i+1)/2]){
            pref[i] = pref[i-1]+1;
        }
        else{
            pref[i] = pref[i-1];
        }
    }
    while(q--){
        int l , r;
        cin>>l>>r;
        cout<<pref[r] - pref[l-1]<<"\n";
    }
    return 0;
}

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

const int inf = 1e9;
int n, m, x;
int c[12];
int a[12][12];

int sub(int s) {
  int sum[12] = {};
  int cost = 0;
  for (int i = 0; i < n; ++i) {
    if (!(s & (1 << i))) continue;
    for (int j = 0; j < m; ++j) {
      sum[j] += a[i][j];
    }
    cost += c[i];
  }
  for (int j = 0; j < m; ++j) {
    if (sum[j] < x) return inf;
  }
  return cost;
}

int main() {
  cin >> n >> m >> x;
  for (int i = 0; i < n; ++i) {
    cin >> c[i];
    for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
    }
  }
  
  int mn = inf;
  for (int s = 0; s < (1 << n); ++s) {
    mn = min(mn, sub(s));
  }
  cout << (mn == inf ? -1 : mn) << endl;
}

Measured memory_bytes: 3612
#include<iostream>
using namespace std;
 
int main(){
  int N, a[100000], count = 0;
  cin >> N;
  for(int i = 1; i<N+1; i++){
    cin >> a[i];
  }
 
  for(int i = 1;;){
    if(a[i] == 2){
      count++;
      cout << count << endl;
      return 0;
    }
    else{
      count++;
      i = a[i];
    }
 
    if(count == N){
      cout << -1 << endl;
      return 0;
    }
  }
 
 
  return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main(){
    bool hantei = true;//false:true
    int W,H;
    int x,y,r;
    cin >> W >> H >> x >> y >> r;

    if(W-x<r){
        hantei=false;
    }
    if(r>x){
        hantei=false;
    }
    if(H-y<r){
        hantei=false;
    }
    if(r>y){
        hantei=false;
    }

    if(hantei == true)cout << "Yes" << endl;
    if(hantei == false)cout << "No" << endl;

    return 0;
}

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

int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  	if(a+b>c+d){
      cout<<"Left"<<endl;
    }
  	if(a+b<c+d){
      cout<<"Right"<<endl;
    }
  	if(a+b==c+d){
      cout<<"Balanced"<<endl;
    }
}

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

namespace Atcoder {
    class Program {
        static void Main(string[] args) {
            //var N = int.Parse(Console.ReadLine());
            //var inputList = new List<int>();
            //foreach (var i in Enumerable.Range(0, N))
            //    inputList.Add(int.Parse(Console.ReadLine()));


            //var NK = Console.ReadLine().Split(' ');
            //var N = int.Parse(NK.First());
            //var K = int.Parse(NK.Last());

            //var A = long.Parse(Console.ReadLine());
            //var B = long.Parse(Console.ReadLine());
            //var C = long.Parse(Console.ReadLine());
            //var D = long.Parse(Console.ReadLine());
            var N = int.Parse(Console.ReadLine());
            var DX = Console.ReadLine().Split(' ');
            var D = long.Parse(DX.First());
            var X = long.Parse(DX.Last());
            var Ate = new List<long>();

            foreach (var i in Enumerable.Range(0, N))
                Ate.Add(chocos( long.Parse(Console.ReadLine()),D));

            var sum = X + Ate.Aggregate((n, next) => n + next);
            Console.WriteLine(sum);
                return;
        }

        static long chocos(long a,long d) {
            long counter = 0;
            while (counter * a + 1 <= d) {
                counter++;
            }
            return counter;
        }

        static long max(long left, long right) {
            if (left >= right)
                return left;
            return right;
        }

        static long min(long left, long right) {
            if (left >= right)
                return right;
            return left;
        }
    }
}


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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    for (int i = 0; i < N; i++) {
        if (A[i] % 2) {
            cout << "first" << endl;
            return 0;
        }
    }

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

Measured memory_bytes: 640
/* atcoder */
#include "bits/stdc++.h"
using namespace std;

/* typedef */
/* long系 */
typedef long long ll;   // long long
typedef long double ld; // long double
/* vector系 */
typedef vector<int> vi;                    // intのvector
typedef vector<double> vd;                 // doubleのvector
typedef vector<ll> vll;                    // llのvector
typedef vector<ld> vld;                    // ldのvector
typedef vector<vector<int>> vvi;           // intの2次元vector
typedef vector<vector<double>> vvd;        // doubleの2次元vector
typedef vector<vector<ll>> vvll;           // llの2次元vector
typedef vector<vector<ld>> vvld;           // ldの2次元vector
typedef vector<pair<int, int>> vi_i;       // i_iのvector
typedef vector<pair<double, double>> vd_d; // d_dのvector
typedef vector<pair<ll, ll>> vl_l;         // l_lのvector
typedef vector<pair<ld, ld>> vld_ld;       // ld_ldのvector
typedef vector<string> vs;                 // stringのvector
/* pair系 */
typedef pair<int, int> i_i;       // int同士のpair
typedef pair<double, double> d_d; // double同士のpair
typedef pair<ll, ll> l_l;         // ll同士のpair
typedef pair<ld, ld> ld_ld;       // ld同士のpair

/* define */
#define all(v) v.begin(), v.end() // コンテナ全体
#define PI (acos(-1))             // 円周率pi

/* stringstream */
stringstream ss;
stringstream init_ss; // save default formatting

/* upper, lower */
struct ToUpper
{
    char operator()(char c)
    {
        return toupper(c);
    }
};
struct ToLower
{
    char operator()(char c)
    {
        return tolower(c);
    }
};

/* main */
void Main(void)
{
    string w;
    cin >> w;
    transform(w.cbegin(), w.cend(), w.begin(), ToLower());
    string t;
    int ans = 0;
    while (cin >> t)
    {
        if (t == "END_OF_TEXT")
        {
            break;
        }
        transform(t.cbegin(), t.cend(), t.begin(), ToLower());
        string tmp = "";
        for (int i = 0; i < t.size(); i++)
        {
            if (isalpha(t[i]))
                tmp += t[i];
        }
        if (tmp == w)
            ans++;
    }
    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();

    return 0;
}



Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define F(i,a,b) for(int i=int(a);i<=int(b);i++)
#define endl "\n"
#define ios std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define out(x) cout<<x<<endl,exit(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define I first
#define S second

const int N=1e5+9;
int dp[N];

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

	int a[n+2];
	F(i,1,n) cin>>a[i];

	dp[2]=abs(a[2]-a[1]);

	F(i,3,n){
		dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
	}
	cout<<dp[n];
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws java.lang.Exception{
        Scanner sc = new Scanner(System.in);
        while(true){
            int a = sc.nextInt();
            String op = sc.next();
            int b = sc.nextInt();
            
            if(op.equals("?")){
                break;
            }
            int res = 0;
            switch (op){
            case "+":
                res = a + b;
                break;
            case "-":
                res = a - b;
                break;
            case "*":
                res = a * b;
                break;
            case "/":
                res = a / b;
                break;
            }
            System.out.println(res);
        }
    }
}


Measured memory_bytes: 26312
using System;

class MainClass
{
    public static int[] list;
    public static void Main(string[] args)
    {


        int N = int.Parse(Console.ReadLine());
        list = new int[N + 1];

        Q_int(0);
        list[N] = list[0];
        if(list[0] == 0)
        {
            return;
        }

        int left = 0;
        int right = N;
        int serch = (left + right) / 2;

        while(true)
        {
            Q_int(serch);
            if (list[serch] == 0) { 
                //Console.WriteLine("見つかった");
                return; 
            }

            if ((serch - left - 1) % 2 == 0 && list[left] == list[serch])
            {
                right = serch;
                serch = (serch + left) / 2;
            }
            else if((serch - left - 1) % 2 == 1 && list[left] != list[serch])
            {
                right = serch;
                serch = (serch + left) / 2;
            }
            else if ((right - serch - 1) % 2 == 0 && list[serch] == list[right])
            {
                left = serch;
                serch = (serch + right) / 2;
            }
            else if ((right - serch - 1) % 2 == 1 && list[serch] != list[right])
            {
                left = serch;
                serch = (serch + right) / 2;
            }
            else
            {
                Console.WriteLine("予定外");
            }

        }
        return;
    }

    public static int Q_int(int i)
    {
        Console.WriteLine(i);
        string inputQ = Console.ReadLine();
        if (inputQ == "Vacant")
        {
            list[i] = 0;
            return 0;
        }
        else if(inputQ == "Male")
        {
            list[i] = 1;
            return 1;
        }
        else if(inputQ == "Female")
        {
            list[i] = 2;
            return 2;
        }
        else
        {
            list[0] = 0;
            Console.WriteLine("読み込みミス");
            return 0;
        }
    }

}


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

public class Main {
	public static void main(String args[]) throws Exception {
		double d = Math.sqrt(
				Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine().replace(" ", "")));
		System.out.println((int) d == d ? "Yes" : "No");
	}
}

Measured memory_bytes: 22740
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric> 
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	vector<int> vec;
	for(int i = 0; i < 3; i++)
	{
		int x;
		cin >> x;
		vec.push_back(x);
	}
	sort(vec.begin(), vec.end());
	cout << vec[0] + vec[1] << endl;
	return 0;
}



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


/*
　　　　　　 ＿＿
　　　　　／＞　　 フ
　　　　　|   _　 _l
　 　　　／` ミ＿x ノ   Zzz...
　　 　 /　 　　  |   コード見ちゃだめ！！
　　　 /　 ヽ　　 ﾉ
　 　 │　　|　|　|
　／￣|　　 |　|　 |
　| (￣ヽ＿_ヽ_)__)
　＼二つ
*/



int main(){
    double n;
    cin>>n;
    int k=n/1.08;
    bool f=false;
    int ans=0;
    for(int i=k-2;i<=k+2;i++){
        if(floor(i*1.08)==n) {
            f=true;
            ans=i;
            break;
        }
    }
    if(f) cout<<ans<<endl;
    else cout<<":("<<endl;
    

}

Measured memory_bytes: 256
//https://atcoder.jp/contests/abc158/tasks/abc158_b
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n, a , b ;
    cin >> n >> a >> b ;
    long long rem, ans ;
    ans = n / (a + b)*a ;
    rem = n % (a + b) ;
    ans += min(rem, a);
    cout << ans << endl ;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;

void solve() {
  string s;
  cin >> s;
  if(s.size() == 3) reverse(s.begin(), s.end());
  cout << s << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 256
main=interact$show.f.map read.words;f(n:k:l)=foldl(&)0$[k*(k-1)`div`2|x<-l,y<-l,x>y]++[k|i<-[0..n-1],z<-drop i l,l!!i>z];x&y=rem(x+y)1000000007

Measured memory_bytes: 1276
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <locale>
using namespace std;
#define MS0(I) memset(I, 0, sizeof(I));
#define MS1(I) memset(I, -1, sizeof(I));
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, s, n) for(int i = (s); i < (n); ++i)
#define per1(i, a, b) for(int i = a; i >= b; --i)
#define DRI(A) int A; scanf("%d", &A);
#define DRII(A, B) int A, B; scanf("%d %d", &A, &B);
#define DRIII(A, B, C) int A, B, C; scanf("%d %d %d", &A, &B, &C);
#define DRL(A) long long A; scanf("%lld", &A);
#define DRLL(A, B) long long A, B; scanf("%lld %lld", &A, &B);
#define DRLLL(A, B, C) long long A, B, C; scanf("%lld %lld %lld", &A, &B, &C);
#define SZ(X) ((int)X.size() )
#define MP make_pair 
#define pb push_back
#define F first
#define S second
#define ALL(I) (I).begin(), (I).end()
typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef long double LDB;
typedef pair<int, int> PII; 
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<LL, LL> PLL;
const double eps = 1e-9;
const double PI = acos(-1);
const LL INFF = 1e18;
const int INF = 1e9+1;
const int mod = 1e9+7;
const int MAX = 1e5+7;
inline LL gcd(LL v1, LL v2){
  while(v1){
    LL tmp = v2 % v1;
    v2 = v1;
    v1 = tmp;
  }
  return v2;
}
int main(void){
  DRI(t);
  while(t--){
    DRLL(a, b); DRLL(c, d);
    if(b > a) puts("No");
    else if(b > d) puts("No");
    else if(c >= a) puts("Yes");
    else{
      LL v = a - ((a - c)/b)*b;
      LL gd = gcd(d, b);
      if(v == c) v += d;
      v = v - ((v - c)/gd)*gd;
      if(v == c) v += gd;
      //printf("%lld\n", v);
      if(v < b) puts("No");
      else puts("Yes");
    }
  }
  return 0;
}


Measured memory_bytes: 256
n=int(input())
d=[0]+[1e6]*n
c=[1]*n
M=[[-1]*n for _ in[0]*n]

for _ in[0]*n:
 data=list(map(int,input().split()))
 for i in range(data[1]):k=2*-~i;M[data[0]][data[k]]=data[k+1]

while 1:
 m,u=1e6,-1
 
 for i in range(n):
  if m>d[i]and c[i]:
      m,u=d[i],i
 if u<0:
     break
 c[u]=0
 
 for v in range(n):
  if c[v]and 1+M[u][v]and d[v]>d[u]+M[u][v]:
   d[v]=d[u]+M[u][v]
   
for i in range(n):
    print(i,d[i])


Measured memory_bytes: 5732
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 
 
	public static void main(String[] args) { 
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int A = I.nextInt();
		int B = I.nextInt();
		long ans = 0;
		for (int i = A; i <= B; i++) {
			String S = Integer.toString(i);
			if (S.charAt(0)==S.charAt(4)&&S.charAt(1)==S.charAt(3)) ans++;
		}
		O.pln(ans);
	}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
	}
}


Measured memory_bytes: 31704
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
char s[100005];
int n, cnt[26], sum[1<<26];
int ans = 0;
int main() {
	scanf("%d%s", &n, s);
	for(int i = 0; i < n; i++)
		cnt[s[i]-'a'] ++;
	for(int i = 0; i < 26; i++)
		sum[1<<i] = cnt[i];
	sum[0] = 1;
	for(int i = 1; i < (1<<26); ++i) {
		sum[i] = (long long)sum[i&-i] * sum[i-(i&-i)] % mod;
		ans = (ans+sum[i]) % mod;
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> v(n);
	for(int& x:v) cin >> x;
	set<int> s;
	int i=1,count = 0;
	while(true){
		i=v[i-1];
		count++;
		if(i==2) {cout << count; return 0;}
		else if (!s.count(i)) s.insert(i);
		else break;
	}
	cout << -1;
     
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
int main()
 {
 	string s1,s2;
 	cin>>s1>>s2;
 	s2.pop_back();
 	if(s1==s2)
 		cout<<"Yes"<<endl;
 	else
 		cout<<"No"<<endl;
 	return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  bool ok =false;
  for (int i=0;i<26;i++){
    for(int j=0;j<15;j++){
      if (4*i+7*j==n){
        ok = true;
      }
    }
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
}
        

Measured memory_bytes: 256
/** 
If comrades that you trust gather around you, hope can take physical form and become visible. That’s what I believe.
*/
#include <bits/stdc++.h>
using namespace std;
/**
(▀̿Ĺ̯▀̿ ̿) (ง ͠° ͟ل͜ ͡°)ง
*/
const int N = 1e4 + 7;
int a[N];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    int tt = clock();
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    auto res = accumulate(a + 1, a + 1 + m, 0);
    if (res > n) cout << "-1\n";
    else cout << n - res << '\n';


    cerr << "TIME = " << (double) 1.0 * (clock() - tt) / CLOCKS_PER_SEC << " seconds" << endl;
	return 0;
}


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

int main(){
  int a;
  cin >>a;
  string s;
  cin >>s;
  int ans=0;
  int b=0;
  for(int i=0;i<a;i++){
    if(s.at(i) == 'I'){
      b++;
      ans = max(ans,b);
    }
    if(s.at(i) == 'D'){
      b--;
    }
  }
  cout <<ans<<endl;
}
    
      

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

int N,Q;
struct LazySegmentTree{
  private:
  int n; vector<ll> node,lazy;
  
  public:
  LazySegmentTree(vector<ll> v){
    int sz=(int)v.size();
    n=1;  while(n<sz)n*=2;
    node.resize(2*n-1);
    lazy.resize(2*n-1,0);
    for(int i=0;i<sz;i++)node[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)node[i]=node[2*i+1]+node[2*i+2];
  }
  
  void eval(int k,int l,int r){
    if(lazy[k]!=0){
      node[k]+=lazy[k];
      if(r-l>1){lazy[2*k+1]+=lazy[k]/2; lazy[2*k+2]+=lazy[k]/2;}
      lazy[k]=0;
    }
  }
  void add(int a,int b,ll x,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k,l,r);
    if(b<=l || r<=a)return;
    if(a<=l && r<=b){lazy[k]+=(r-l)*x; eval(k,l,r);}
    else{
      add(a,b,x,2*k+1,l,(l+r)/2);
      add(a,b,x,2*k+2,(l+r)/2,r);
      node[k]=node[2*k+1]+node[2*k+2];
    }
  }
  ll getsum(int a,int b,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k,l,r);
    if(b<=l || r<=a)return 0;
    if(a<=l && r<=b)return node[k];
    ll vl=getsum(a,b,2*k+1,l,(l+r)/2);
    ll vr=getsum(a,b,2*k+2,(l+r)/2,r);
    return vl+vr;
  }
};

int main(){
  cin >> N >> Q;
  LazySegmentTree seg(vector<ll>(N,0));
  for(int i=0;i<Q;i++){
    int q; cin >> q;
    if(q==0){
      int s,t,x; cin >> s >> t >> x;
      seg.add(s-1,t,x);
    }
    else{
      int i; cin >> i;
      cout << seg.getsum(i-1,i) << endl;
    }
  }
}


Measured memory_bytes: 7580
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  100005
ll dp[(1<<16)],n;
vi adj[17];
ll arr[16][16];
vi v;
// ll dps(ll x)
// {

// }
void solve()
{
    cin>>n;
    for(int i=1;i<(1<<n);i++)
    {
        adj[__builtin_popcount(i)].pb(i);
    }
    rep(i,1,n+1)
    {
        for(auto u:adj[i])
            v.pb(u);
    }
    rep(i,0,n)
    rep(j,0,n)
    cin>>arr[i][j];
    for(auto u:v)
    {
        // cout<<u<<endl;
        vi v1;
        ll co=__builtin_popcount(u);
        if(co==1)
            continue;
        rep(j,0,n)
        {
            if(u&(1<<j))
            {
                v1.pb(j);
            }
        }
        rep(i,0,v1.size())
        {
            rep(j,i,v1.size())
            dp[u]+=arr[v1[i]][v1[j]];
        }
        dp[u]=max(dp[u],0ll);
        for(int s=u;s;s=(s-1)&u)
        {
            dp[u]=max(dp[u],dp[s]+dp[s^u]);
        }
    }
    cout<<dp[(1<<n)-1]<<endl;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}

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

int main(){
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(i,3) if(s[i] == t[i]) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 3628
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))


Measured memory_bytes: 13248