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

int main() {
  int n;
  cin>>n;
  vector<double> v(n);
  for(int i=0;i<n;i++) cin>>v.at(i);
  while(v.size()!=1){
    sort(v.begin(),v.end());
    double k;
    k=(v.at(0)+v.at(1))/2.0;
    v.erase(v.begin());
    v.erase(v.begin());
    v.push_back(k);
  }
  cout<<v.at(0)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(long long i = 0; i < (long long)(n); ++i)

using namespace std;

int main() {
	double n;
	cin >> n;
	n = 2 * n * acos(-1);
	cout << n << endl;
	return 0;
}


Measured memory_bytes: 3776
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vb v(n,false);
    rep(_,k) {
        int d;
        cin >> d;
        rep(i,d) {
            int a;
            cin >> a;
            a--;
            v[a] = true;
        }
    }
    int ans = 0;
    rep(i,n) if(!v[i]) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 3648
#include <stdio.h>

int main(void){

	int num,i,tsum=0,hsum=0,cmp,f;
	char line[101],line1[101];		/* ????????????????????????????????????100??\??? */

	scanf("%d\n",&num);				/* ???????????????????????°n????±???? */
	for(i=0;i<num;i++){
		scanf("%s %s",line,line1);	/* ??¢??????????????????????°??????????????????? */
		f=strcmp(line,line1);		/* num?????°?????????????????±????????? */
		if(!f){
			tsum++;
			hsum++;
		}							/* line???line1?????´??????tsum??¨hsum??????????????? */
		else if(f>0)
			tsum+=3;				/* tsum??????????????? */
		else
			hsum+=3;				/* hsum??????????????? */
	}

	printf("%d %d\n",tsum,hsum);

	return 0;
}

Measured memory_bytes: 604
#include<stdio.h>
#include<string.h>

#define M 1000000
#define NIL -1
#define L 14

char H[M][L];

int getChar(char ch)
{
    if(ch=='A') return 1;
    else if(ch=='C') return 2;
    else if (ch=='G') return 3;
    else if(ch=='T') return 4;
    else return 0;
}

long long getKey(char str[])
{
    long long sum=0,p=1,i;
    for(i=0;i<strlen(str);i++)
    {
        sum+=p*(getChar(str[i]));
        p*=5;
    }
    return sum;
}
int h1(int key){
    return key%M;
}
int h2(int key)
{
    return 1+(key%(M-1));
}

void insert(char str[])
{
    long long key=0,i,h;
    key =getKey(str);
    for(i=0;;i++)
    {
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0) return ;
        else if(strlen(H[h])==0) 
        {
            strcpy(H[h],str);
            return ;
        }
    }
    return ;
}
int find(char str[])
{
    long long key,i,h;
    key=getKey(str);
    for(i=0;;i++)
    {
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0) return 1;
        else if(strlen(H[h])==0) return 0;
    }
    return 0;
}

int main()
{
    int i,n,h;
    char str[L],com[9];
    for(i=0;i<M;i++) H[i][0]=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s %s",com,str);
        if(com[0]=='i')
        insert(str);
        else
        {
            if(find(str))
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
    }
    return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long n;
    cin>>n;
    vector<long>v(n);
    long long sum = 0;
    vector<long int>count(100001,0);
    for(long i=0;i<n;i++)
    {
        cin>>v[i];
        sum = sum+v[i];
        count[v[i]]++;
    }
    int q;
    cin>>q;
    while(q--)
    {
        long int b,c;
        cin>>b>>c;
        long cb = count[b];
        count[b] = 0;
        count[c] = count[c] + cb;
        long sum_s = cb*b;
        long sum_a = c*cb;
        sum = sum + sum_a - sum_s;
        cout<<sum<<"\n";
    }
    return 0;
}

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

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

    int n;
    cin >> n;

    int a[2][n];
    REP(i, n) cin >> a[0][i];
    REP(i, n) cin >> a[1][i];

    int ans = 0;
    REP(i, n) ans += a[0][i];
    ans += a[1][n-1];
    int sum = ans;
    for(int i = n - 1; i > 0; --i) {
        sum = sum - a[0][i] + a[1][i-1];
        ans = max(sum, ans);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException {
        Reader.init();
        int A=Reader.nextInt();
        int B=Reader.nextInt();
        HashMap<String, Integer> map=new HashMap<>();
        map.put("12", 3);
        map.put("21", 3);
        map.put("13", 2);
        map.put("31", 2);
        map.put("23", 1);
        map.put("32", 1);
        println(map.get(A+""+B));
    }

    static int mod=1000000007;
    public static void read(int arr[], int N) throws IOException{ for(int i=0;i<N;i++){ arr[i]=Reader.nextInt(); } }
    public static void read(long arr[], int N) throws IOException{ for(int i=0;i<N;i++){ arr[i]=Reader.nextLong(); } }
    public static void read(String arr[], int N) throws IOException{ for(int i=0;i<N;i++){ arr[i]=Reader.next(); } }
    public static void print(Object O){ System.out.print(O); }
    public static void println(Object O){ System.out.println(O); }
    public static void display(int arr[]){ System.out.println(Arrays.toString(arr)); }
    public static void display(int arr[][], int N){ for(int i=0;i<N;i++){ System.out.println(Arrays.toString(arr[i])); } }
}


class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init() {
        reader=new BufferedReader(new InputStreamReader(System.in));
        tokenizer=new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) {
            tokenizer=new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException { return Integer.parseInt(next()); }
    static double nextDouble() throws IOException { return Double.parseDouble(next()); }
    static long nextLong() throws IOException { return Long.parseLong(next()); }
    static String nextLine() throws IOException { return reader.readLine(); }
}

Measured memory_bytes: 21332
/*
首先特判掉M = 1的情况 
对于一个区间[l, r]是回文串的性质，可以写出floor((r - l + 1) / 2)个限制：S[a] = S[b](a != b)，对于这样的限制连一条无向边(a, b)
设A数组中有s1个奇数，那么连了(N - s1) / 2条边；B数组有s2个奇数，那么连了(N - s2) / 2条边。那么一共连了N - (s1 + s2) / 2条边
要求所有字符必须相同，那么需要满足整个图是联通的，故N - (s1 + s2) / 2 >= N - 1   =>   s1 + s2 <= 2。当s1 > 2时一定无解 
当s1 <= 2时，存在这么一种构造方法。把A的奇数放在两端，令B[1] = A[1] - 1   B[M] = A[M] + 1   B[2 <= i <= M - 1] = A[i]即可
这样可以让整张图至少包含一条连接所有点的链，也就完成了构造 
*/

#include <cstdio>
#include <algorithm>

using namespace std;
const int Max_M(105);

int N, M, A[Max_M], B[Max_M];

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 1;i <= M;++i)
		scanf("%d", A + i), A[0] += (A[i] & 1);
	if (M == 1)
	{
		if (A[1] == 1)
			printf("%d\n%d\n%d", 1, 1, 1);
		else
			printf("%d\n%d\n%d %d", A[1], 2, A[1] - 1, 1);
		return 0;
	}
	if (A[0] > 2)
	{
		puts("Impossible");
		return 0;
	}
	for (int i = 1;i <= M;++i)
		if (A[i] & 1)
		{
			swap(A[1], A[i]);
			break;
		}
	for (int i = M;i >= 1;--i)
		if (A[i] & 1)
		{
			swap(A[M], A[i]);
			break;
		}
	if (A[1] - 1)
		B[++B[0]] = A[1] - 1;
	for (int i = 2;i <= M - 1;++i)
		B[++B[0]] = A[i];
	B[++B[0]] = A[M] + 1;
	for (int i = 1;i <= M;++i)
		printf("%d ", A[i]);
	printf("\n");
	printf("%d\n", B[0]);
	for (int i = 1;i <= B[0];++i)
		printf("%d ", B[i]);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
//#define DEBUG
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template <class T>
void print_vect(std::vector<T> v){
    for(int i = 0 ; i < v .size(); i++) cout << v[i] << " ";
    cout << endl;
}

void solve(){
    int n, a, b;
    string S;
    cin >> n >> a >> b;
    cin >> S;
    int count_japanese = 0;
    int count_foreigner = 0;
    int i;
    for(i = 0 ; i < S.size() && count_foreigner + count_japanese < a + b ; i++){
        if( S[i] == 'a'){
            cout << "Yes\n";
            count_japanese++;
        }else if(S[i] == 'b'){
            if(count_foreigner < b){
                cout << "Yes\n";
                count_foreigner++;
            }else{
                cout << "No\n";
            }
        }else{
            cout << "No\n";
        }
    }
    for(; i < S.size() ; i++){
        cout << "No\n";
    }
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/

    #ifdef DEBUG
    int TEST_CASES = 2;
    while(TEST_CASES--){
    #endif // DEBBUG

    solve();

    #ifdef DEBUG
    }
    #endif // DEBUG
    
    return 0;
}



Measured memory_bytes: 3792
function main(arg) {
	arg = arg.split("\n").map(Number)
	var k = arg[5]
	var data = [
		arg[0],arg[1],arg[2],arg[3],arg[4]
	]
	var flag = true
	for (var i  = 0; i < data.length; i++) {
		for (var j = i + 1; j < data.length; j++) {
			var ans = Math.abs(data[j] - data[i])
			// console.log(ans)
			if (ans > k) {
				flag = false
			}
		}
	}
	if (flag) {
		console.log('Yay!')
	} else {
		console.log(':(')
	}
	// console.log(data)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<algorithm>
using namespace std;
int sovle(){
    int a,b,c;
    cin>>a>>b>>c;
    int sum=0;
    sum = a+b+c;
    if(sum>=22){
        cout<<"bust"<<endl;
        return 0;
    }
    cout<<"win"<<endl;
    return 0;
}


int main(){
    int T = 1;
    while(T--){
        int re = sovle();
        // cout<<re<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct point{int x;int y;};
int i,j,k,count1=0,count2=0;

int main(){
    int n,m;
    cin>>n>>m;
    int l,r,lmax,rmin;
    rep(i,m){
        cin>>l>>r;
        if(i==0){
            lmax=l;
            rmin=r;
        }
        lmax=max(lmax,l);
        rmin=min(rmin,r);
    }
    int ans=rmin-lmax+1;
    cerr<<ans<<endl;
    cout<<((ans>=0)?ans:0)<<endl;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, c;
    cin >> a >> b >> c;

    bool flag = false;
    if (a+b == c) {
        flag = true;
    } else if (b+c == a) {
        flag = true;
    } else if (c+a == b) {
        flag = true;
    }

    if (flag) {
        Yes;
    } else {
        No;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (true) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}

			boolean[][] visited = new boolean[n][n];
			Point[][] dist = new Point[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					dist[i][j] = new Point(sc.nextInt(), sc.nextInt());
				}
			}
			int loopCount = 0;
			Set<Point> currentLoopLocs = new HashSet<Point>();
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (visited[i][j]) {
						continue;
					}
					currentLoopLocs.clear();
					currentLoopLocs.add(new Point(j, i));
					Point nextPoint = dist[i][j];
					
					while (!visited[nextPoint.y][nextPoint.x]) {
						visited[nextPoint.y][nextPoint.x] = true;
						currentLoopLocs.add(nextPoint);
						nextPoint = dist[nextPoint.y][nextPoint.x];
						if(currentLoopLocs.contains(nextPoint)) {
							loopCount++;
							break;
						}
						
					}
					visited[i][j] = true;
				}
			}
			System.out.println(loopCount);

		}

	}

	static class Point {
		final int x;
		final int y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Point other = (Point) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}

}

Measured memory_bytes: 13000
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-12;

	int n;
	int[] pow;
	String[] names;
	HashSet<String>[] sets;

	@SuppressWarnings("unchecked")
	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			names=new String[n];
			pow=new int[n];
			sets=new HashSet[n];
			for(int j=0; j<n; j++){
				names[j]=sc.next();
				pow[j]=sc.nextInt();
				sets[j]=new HashSet<String>();
				int m=sc.nextInt();
				for(int i=0; i<m; i++){
					sets[j].add(sc.next());
				}
			}
			solve();
		}
	}

	long[] g;
	int ans;

	void solve(){
		HashMap<String, Integer> map=new HashMap<String, Integer>();
		for(int i=0; i<n; i++){
			map.put(names[i], i);
		}
		g=new long[n];
		for(int i=0; i<n; i++){
			for(String s : sets[i]){
				int j=map.get(s);
				g[i]|=1L<<j;
			}
		}
		ans=0;
		// mis(1, 1, pow[0]);
		mais(1, 1|g[0], pow[0]);
		println(ans+"");
	}

	void mais(long choosed, long removed, int sum){
		int k=-1;
		long remained=~removed&((1L<<n)-1);
		for(; remained!=0;){
			int i=Long.numberOfTrailingZeros(remained);
			if(Long.bitCount(g[i]&~removed)==0){
				k=i;
				break;
			}
			if(k==-1||Long.bitCount(g[i]&~removed)>Long.bitCount(g[k]&~removed))
				k=i;
			remained^=1L<<i;
		}
		if(k==-1){
			// String s=Long.toBinaryString(choosed);
			// for(; s.length()<n; s="0"+s);
			// debug(s, sum);
			ans=max(ans, sum);
			return;
		}
		if(Long.bitCount(g[k]&~removed)>=1)
			mais(choosed, removed|(1L<<k), sum);
		mais(choosed|(1L<<k), removed|(1L<<k)|g[k], sum+pow[k]); // choose k
	}

	void mis(int k, long choosed, int sum){
		if(k==n){
			// TODO
			ans=max(ans, sum);
			return;
		}
		if((choosed&g[k])==0){
			mis(k+1, choosed|(1L<<k), sum+pow[k]);
			long rem=0;
			for(int i=k+1; i<n; i++)
				if((choosed&g[i])==0)
					rem|=g[i];
			if((rem>>>k&1)==0)
				return;
		}
		mis(k+1, choosed, sum);
	}

	void mis_(int k, long choosed, int sum){
		if(k==n){
			// TODO
			ans=max(ans, sum);
			return;
		}
		if((choosed&g[k])==0){
			mis(k+1, choosed|(1L<<k), sum+pow[k]);
			long rem=0;
			for(int i=k+1; i<n; i++)
				if((choosed&g[i])==0)
					rem|=g[i];
			if((rem>>>k&1)==0)
				return;
		}
		mis(k+1, choosed, sum);
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

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

Measured memory_bytes: 13000
import bisect

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    idx_a = bisect.bisect_left(A, b)
    idx_c = bisect.bisect(C, b)
    ans += idx_a * (N - idx_c)
print(ans)


Measured memory_bytes: 23156
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
int main()
{
	int x1, y1, x2, y2,dx,dy;
	cin >> x1 >> y1 >> x2 >> y2;
	dx = x2 - x1; dy = y2 - y1;
	cout << x2 - dy << " " << y2 + dx << " ";
	cout << x2 - dy - dx << " " << y2 + dx - dy << endl;
	return 0;
}

Measured memory_bytes: 256
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>


using namespace std;

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

    if(A*B<=81&&A<=9&&B<=9&&A*B!=0){
        cout<<A*B<<endl;
    }

    else{
        cout << -1 << endl;
    }
}
 

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

int main()
{
	int a,b,c,d;
    double sum=0;
	string s;

    cin>>a;
    double w[10][100];
    string ms[10];
    for(int i=0;i<a;i++)
    {
        cin>>w[i][100];
        string ss;
        cin>>ss;
        ms[i]=ss;
    }
    for(int i=0;i<a;i++)
    {
        if(ms[i]=="JPY")
            sum+=w[i][100];
        else
        {
            sum+=w[i][100]*380000;
        }
        
    }
    cout<<sum;
	return 0;
}
	

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
      	long b = sc.nextInt();
      	long c = sc.nextInt();
      	long d = sc.nextInt();
      	
      	long result[] = new long[4];
      	result[0] = a*c;
      	result[1] = a*d;
      	result[2] = b*c;
      	result[3] = b*d;
      
      	for(int i = 1;i < 4;i++){
         if(result[0] < result[i]){
         	result[0] = result[i];
         }
        }
      
      	System.out.print(result[0]);
    }
}

Measured memory_bytes: 35816
#include <iostream>
#include <cstdlib>
#include <list>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int main(void)
{
    int64_t N, K;
    cin >> N >> K;
    int64_t p[1000];
    for (int64_t i = 0; i < N; ++i)
    {
        cin >> p[i];
    }

    sort(p, p+N);

    int64_t ans = 0;
    for (int64_t i = 0; i < K; ++i)
    {
        ans += p[i];
    }

    cout << ans;
    
    return 0;
}


Measured memory_bytes: 3184
N,M = map(int,input().split())
target = list()
for i in range(N):
	target_list = list(map(int,input().split()))
	target_list.pop(0)
	target.append(target_list)

# print(target)

ans = dict()
for i in range(0,len(target)):
	for j in range(len(target[i])):
		if i == 0:
			ans[target[i][j]] = 1
		else:
			if target[i][j] in ans:
				ans[target[i][j]] += 1

ans_num = 0
for k in ans.keys():
	if ans[k] == N:
		ans_num += 1
print(ans_num)


Measured memory_bytes: 62624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[6];
int main(){
    cin>>s;
   // sort(s,s+4);
    if((s[0]==s[1]&&s[1]==s[2])||(s[1]==s[2]&&s[2]==s[3]))
        printf("Yes\n");
    else printf("No\n");
}




Measured memory_bytes: 256
fun main(args:Array<String>):Unit {
    readLine()!!.toInt()
    val array = readLine()!!.split(' ').map(String::toInt).toIntArray()
    repeat(readLine()!!.toInt()){
        val (b, m, e) = readLine()!!.split(' ').map(String::toInt)
        (0 until (e - b)).map{k -> array[b + k]}.forEachIndexed { index, i ->
            array[b + ((index + e - m) % (e - b))] = i
        }
    }
    println(array.joinToString(" "))
}

fun swap(array:IntArray, a:Int, b:Int):Unit {
    val (f, t) = Pair(array[a], array[b])
    array[a] = t
    array[b] = f
}


Measured memory_bytes: 44100
#include <iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

typedef long long ll;
#define rep(i, n) for(int i=0; i < (int)(n); i++)
#define rep1(i, n) for(int i=1; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define fill(x,y) memset(x,y,sizeof(x))
#define debug1(i) cout << i << '\n'
#define debug2(i,j) cout << i << j << '\n'
#define MAX 1000000

using namespace std;


ll n,m,l,a,b=0,c,ans=0;
ll box[MAX];
vector<ll> vec,vec2;

int main(){
    cin >> n >> m;
    if(m<=n){
        cout << 0 <<endl;
        return 0;
    }
    
    rep(i,m){
        cin >> a;
        vec.push_back(a);
    }
    sort(all(vec));
    
    
    rep1(i,m){
        vec2.push_back(abs(vec[i-1]-vec[i]));
    }
    
    sort(all(vec2));
    rep(i,m-n)ans+=vec2[i];
    debug1(ans);
    
    /*for(int j=1;j<abs(vec[0]-vec[m-1]);j++){
        b=0;
        rep(i,m-1){
            if(vec2[i]<=j)b++;
        }
        if(b>m-n){
            sort(all(vec2));
            rep(i,m-n)ans+=vec2[i];
            debug1(ans);
            return 0;
        }
        
    }
    
    /*fill(box,0);
    
    b=abs(vec[0]-vec[m-1]);
    
    for(int p=1;p<n;p++){
        box[p]=box[p-1];
        while(abs(vec[box[p-1]]-vec[box[p]])<1)box[p]++;
    }
    for(int i=1;i<b/n+1;i++){
        for(int p=1;p<n;p++){
            while(abs(vec[box[p-1]]-vec[box[p]])<abs(vec[box[p]]-vec[box[p]-1]))box[p]++;
        }
        if(abs(vec[box[n-1]]-vec[m-1])<abs(vec[box[n-1]]-vec[box[n-1]-1])){
            rep1(i,n){
                ans +=abs(vec[box[i-1]]-vec[box[i]-1]);
                //debug1(vec[box[i]-1]);
            }
            ans+=abs(vec[box[n-1]]-vec[m-1]);
            cout << ans << '\n';
    
            return 0;
        }
    }*/
}



Measured memory_bytes: 2548
from collections import defaultdict
N,m=map(int,input().split())
graph=defaultdict(list)
edges=[]
passages=[[] for i in range(N-1)]
for _ in range(m):
    u,v=map(int,input().split())
    passages[u-1].append(v-1)
prob=[0]*N
prob[0]=1
for n,dest in enumerate(passages):
    #print(n,dest,'ndest')
    for d in dest:
        prob[d]+=prob[n]/len(dest)
# no blocking
e=[0]*N
#print(prob)
for n,dest in list(enumerate(passages))[::-1]:
    #print(dest,n,'n dess t')
    e[n]=sum(e[d] for d in dest)/len(dest)+1
min_e=e[0]
#with blocking
for n,dest in enumerate(passages):
    if len(dest)==1:
        continue
    new_e=((e[n]-1)*len(dest)-max(e[d] for d in dest))/(len(dest)-1)+1
    min_e=min(min_e,e[0]-(e[n]-new_e)*prob[n])
print(min_e)
    

        



Measured memory_bytes: 9792
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;


int main(){
 int K, result = 0;
 cin >> K;
 for(int i = 1; i <= K; i++){
  for(int j = 1; j <= K; j++){
    if(i % 2 == 0 && j % 2 != 0){
      result++;
    }
  }
 }
 cout << result << endl;
}


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

divisors = []
for i in range(1, int(m**0.5)+1):
    if m % i == 0:
        divisors.append(i)
        if i != m // i:
            divisors.append(m // i)
divisors.sort()

print([i for i in divisors if i <= m/n][-1])


Measured memory_bytes: 9312
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
    int N,M;
    cin >> N >> M;
    int a,b;
    int c[N];
    REP(i,N){
        c[i] = 0;
    }
    REP(i,M){
        cin >> a >> b;
        c[a-1] += 1;
        c[b-1] += 1;
    }
    REP(i,N){
        cout << c[i];
        if(i!=N-1){
            cout << "\n";
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void read(int &x){
    char ch=getchar();x=0;
    for (;ch==' '||ch=='\n';ch=getchar());
    for (;ch!=' '&&ch!='\n';x=x*10+ch-'0',ch=getchar());
}
int t;
struct fl{
    int l,r,c;
}str[200004];
void pop_(){
    t--;
}
void push_(fl x){
    str[t]=x;
    t++;
}
int lb(int x){
    int l=-1,r=t;
    while (r>l+1){
    	int mid=(l+r)/2;
    	if (str[mid].r>=x) r=mid;
    	else l=mid;
    }
    return r;
}
int n;
int s[200004];
int check(int x){
    t=0;
    push_((fl){1,s[1],1});
    for (int i=2;i<=n;i++){
    	if (s[i]>s[i-1]){
    		if (str[t-1].c==1) str[t-1].r=s[i];
    		else push_((fl){s[i-1]+1,s[i],1});
    	}else{
    		int lb_=lb(s[i]);
    		t=lb_+1;
    		str[lb_].r=s[i];
    		if (t==1 && str[0].c==x) return 0;
    		if (str[t-1].c!=x){
    			if (str[t-1].l==str[t-1].r){
    				str[t-1].c++;
    				if (t>1 && str[t-1].c==str[t-2].c) str[t-2].r++,pop_();
    			}else{
    				str[t-1].r--;
    				push_((fl){str[t-1].r+1,s[i],str[t-1].c+1});
    			}
    			continue;
    		}
    		if (str[t-2].c!=x){
    			if (str[t-2].l==str[t-2].r){
    				str[t-2].c++;
    				if (x>3 && str[t-2].c==str[t-3].c){
    					str[t-3].r++;str[t-2]=str[t-1];pop_();
					}
					pop_();
					push_((fl){str[t-1].r+1,s[i],1});
				}else{
					str[t-2].r--;pop_();
					push_((fl){str[t-1].r+1,str[t-1].r+1,str[t-1].c+1});push_((fl){str[t-1].r+1,s[i],1});
				}
    		}
    	}
    }
    return 1;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(s[i]); 
    int l=0,r=n+1;
    while (r>l+1){
    	int mid=(l+r)/2;
    	if (check(mid)) r=mid;
    	else l=mid;
    }
    cout<<r;
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
const ll MOD = 1000000007;
#define rep(i,n) for (int i = 0; i < (n); ++i)

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

	if (N >= 30){
		cout << "Yes" << "\n";
	} else {
		cout << "No" << "\n";		
	}


	return 0;
}


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

using namespace std;

int main() {
	char c;
	cin >> c;
	if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') cout << "vowel" << endl;
	else cout << "consonant" << endl;
	return 0;
}

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

const int nm = 2e5;
int n, k, c, l[nm], r[nm];
string s;

int main() {
	cin >> n >> k >> c >> s;

	for (int i = 0, count = 0; i < n; i++) {
		if (s[i] == 'o') {
			count++;
			l[count] = i;
			i += c;
		}
	}
	for (int i = n - 1, count = 0; i >= 0; i--) {
		if (s[i] == 'o') {
			count++;
			r[count] = i;
			i -= c;
		}
	}
	l[0] = l[1] - c;
	r[0] = r[1] + c;

	for (int i = 0, inf, sup, mid, left, right; i < n; i++) {
		if (s[i] == 'x')
			continue;
		inf = 0;
		sup = k + 1;
		while (sup - inf > 1) {
			mid = (sup + inf) / 2;
			if (l[mid] < i)
				inf = mid;
			else
				sup = mid;
		}
		left = inf;
		inf = 0;
		sup = k + 1;
		while (sup - inf > 1) {
			mid = (sup + inf) / 2;
			if (r[mid] > i)
				inf = mid;
			else
				sup = mid;
		}
		right = inf;
		if (left + right < k)
			cout << i + 1 << endl;
		else if (left + right == k) {
			if (r[right] - l[left] <= c)
				cout << i + 1 << endl;
		}

	}

}


Measured memory_bytes: 2564
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll,ll> pll;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define MOD 1000000007
#define ARRAY_MAX 100005

const int INF = 1e9+7;


int main(){

    int n;
    while(cin >> n,n){

        vector<int> p(n);//配列のインデックス
        vector<string> f(n);
        vector<int> w(n),s(n),ans(n);
        int mini = INF;

        for(int i = 0;i < n;i++){
            p[i] = i;
        }

        for(int i = 0;i < n;i++){
            cin >> f[i] >> w[i] >> s[i];
        }

        do{

            bool flag = true;
            int cnt = 0,g = 0;

            for(int i = 0;i < n;i++){

                flag &= (cnt <= s[p[i]]);//上から見る
                cnt += w[p[i]];
                g += (n-i)*w[p[i]];
            }

            if(flag == true && g < mini){
                ans = p;
                mini = g;
            }

        }while(next_permutation(p.begin(),p.end()));

        for(int i = n-1;i >= 0;i--){
            cout << f[ans[i]] << endl;
        }
    }


    return 0;
}


Measured memory_bytes: 3180
#!/usr/bin/env python3
n = int(input())
a = [int(x) for x in input().split()]

v = sum(a[i] * (-1) ** (i % 2) for i in range(n))

ans = [0] * n

for i in range(n):
    ans[i] = v
    v = -v + 2 * a[i]

print(" ".join(str(x) for x in ans))


Measured memory_bytes: 19148
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        struct SAYING
        {
            public int men;
            public int isLie;

        }


        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            List<SAYING>[] say = new List<SAYING>[N];
            for (int i = 0; i < N; i++)
            {
                say[i] = new List<SAYING>();
            }

            for (int i = 0; i < N; i++)
            {
                int num = int.Parse(Console.ReadLine());

                for (int j = 0; j < num; j++)
                {
                    string[] s0 = Console.ReadLine().Split(' ');

                    SAYING t;
                    t.men = int.Parse(s0[0]) - 1;
                    t.isLie = int.Parse(s0[1]);

                    say[i].Add(t);
                }
            }

            int ans = 0;
            int maxnum = (int)Math.Pow(2, N);
            for (int i = 0; i < maxnum; i++)
            {
                int localans = 0;
                bool valid = true;

                for (int j = 0; j < N; j++)
                {
                    int bit = 1 << j;

                    // 1＝正直者を検査
                    if(0 != (i & bit))
                    {
                        bool testOK = true;
                        foreach(SAYING st in say[j])
                        {
                            int bit2 = 1 << st.men;

                            if(
                                ((st.isLie == 0) && (0 != (i & bit2))) ||
                                ((st.isLie != 0) && (0 == (i & bit2)))
                                )
                            {
                                testOK = false;
                                break;
                            }
                        }

                        if(!testOK)
                        {
                            valid = false;
                            break;
                        }
                    }
                }

                if(valid)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if(0 != (i & (1<<j)))
                        {
                            localans++;
                        }
                    }

                    ans = Math.Max(ans, localans);
                }
            }

            Console.WriteLine(ans);
        }
    }
}



Measured memory_bytes: 13268
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN=int(1e5),INF=int(1e9);
vector<int> lnk[MAXN+5];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
int ans[MAXN+5];
int n,m;
int main()
{
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
		scanf("%d%d",&u,&v),
		lnk[u].push_back(v),
		lnk[v].push_back(u);
	scanf("%d",&m);
	fill(ans,ans+MAXN+5,INF);
	for(int i=0,x,y;i<m;i++)
		scanf("%d%d",&x,&y),
		que.push(make_pair(y,x)),
		ans[x]=y;
	while(!que.empty())
	{
		int u=que.top().second,val=que.top().first;
		que.pop();
		for(int i=0;i<lnk[u].size();i++)
		{
			int v=lnk[u][i];
			if(ans[v]==INF)
				ans[v]=val+1,que.push(make_pair(ans[v],v));
			if(fabs(ans[v]-ans[u])!=1)
			{
				printf("No\n");
				return 0;
			}
		}
	}
	printf("Yes\n");
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}


Measured memory_bytes: 7924
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
ll sum[N],a[N],m,n;

int main()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(ll i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    ll l=0,r=2e5+1,ans,res,cnt;
    while(l<=r){
        ll mid=(l+r)>>1;
        res=cnt=0;
        for(ll i=1;i<=n;i++){
            ll pos=lower_bound(a+1,a+n+1,mid-a[i])-a;
            cnt+=n-pos+1;
            res+=sum[n]-sum[pos-1]+a[i]*(n-pos+1);
        }
        if(cnt>=m){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%lld\n",res-(cnt-m)*ans);
}

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

int N, K, Q;
int A[100005] = {};
void solve() {
	scanf("%d %d %d\n", &N, &K, &Q);

	for(int i=0; i<Q; i++) {
		int a;
		scanf("%d", &a);
		A[--a]++;
	}

	for(int i=0; i<N; i++) {
		if(K-Q+A[i]<=0) printf("No\n");
		else printf("Yes\n");
	}

}

int main() {
	solve();
	return 0;
}


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

int main(){
  string S;
  cin >> S;
  
  char c;
  int judge = 0;
  
  c = S.at(0);
  for(int i=1; i < 4; i++){
    if(c == S.at(i)){
      judge = 1;
      S.erase(i,1);
      S.erase(0,1);
      break;
    }
  }

  if(c == S.at(0)){
    judge = 0;
  }
  
  if(judge == 1){
    if(S.at(0) == S.at(1)){
      judge = 2;
    }
  }

  if(judge == 2){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
//const int mod=998244353;
using P = pair<int,int>;
using Pll = pair<ll,ll>;
using ld=long double;
using V=vector<int>;
using Vl=vector<ll>;
using VV=vector<vector<int>>;
using VVl=vector<vector<ll>>;

int main(){
    VV a(3,V(3));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >>a[i][j];
        }
    }
    int n;cin >>n;
    map<int,int>mp;
    for (int i = 0; i < n; ++i) {
        int b;cin >>b;
        mp[b]++;
    }
    VV c(3,V(3,0));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if(mp[a[i][j]])c[i][j]=1;
        }
    }
    bool ok=false;
    for (int i = 0; i < 3; ++i) {
        bool flg=true;
        for (int j = 0; j < 3; ++j) {
            if(c[i][j]==0)flg=false;
        }
        if(flg)ok=true;
    }
    for (int i = 0; i < 3; ++i) {
        bool flg=true;
        for (int j = 0; j < 3; ++j) {
            if(c[j][i]==0)flg=false;
        }
        if(flg)ok=true;
    }
    if(c[0][0] and c[1][1] and c[2][2])ok=true;
    if(c[0][2] and c[1][1] and c[2][0])ok=true;
    if(ok)puts("Yes");
    else puts("No");
}


Measured memory_bytes: 3572
import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
    
Q, K = map(int, input().split())
visited = [0 for _ in range(N)]

def DFS(a, b, c):
    for i, j in graph[b]:
        if(i != a):
            visited[i] = c+j
            DFS(b, i, c+j)
DFS(-1, K-1, 0)
             
for _ in range(Q):
    x, y = map(int, input().split())
    print(visited[x-1]+visited[y-1])

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int N,A,B;
    cin>>N>>A>>B;

    if(A>B||(N==1&&A!=B))cout<<0<<endl;
    else cout<<(B-A)*(N-2)+1<<endl;
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  
  int f, l;
  for(int i=0; i<s.size(); i++){
    if(s.at(i) == 'A'){
      f=i;
      break;
  	}
  }
  for(int i=s.size()-1; i>=0; i--){
    if(s.at(i) == 'Z'){
      l=i;
      break;
  	}
  }
  cout << l - f + 1 << endl;
  return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
using namespace std;
typedef long long ll;

ll lcm(ll a, ll b) {
    ll x = a*b;
    ll r;
    if (a < b) {
        ll tmp = a;
        a = b;
        b = tmp;
    }

    r = a % b;
    while (r!=0) {
        a = b;
        b = r;
        r = a % b;
    }

    return x/b;
}

int main() {
    ll A, B, C, D, E;
    ll N, n1, n2, na, nb;

    scanf("%lld %lld %lld %lld", &A, &B, &C, &D);

    E = lcm(C, D);

    n1 = A/E;
    n2 = B/E;

    if (A%E==0) {
        N = n2 - n1 + 1;
    } else {
        N = n2 - n1;
    }

    n1 = A/C;
    n2 = B/C;

    if (A%C==0) {
        na = n2 - n1 + 1;
    } else {
        na = n2 - n1;
    }

    n1 = A/D;
    n2 = B/D;

    if (A%D==0) {
        nb = n2 - n1 + 1;
    } else {
        nb = n2 - n1;
    }

    printf("%lld\n", B-A+1-((na+nb)-N));

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<sstream>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	ll n;
	cin >> n;
	string s;
	cin >> s;
	int w[n],e[n];
	w[0] = 0;
	e[n-1] = 0;
	rep(i,0,n){
		if( i > 0 ) w[i] = w[i-1];
		if( s[i] == 'W' ) w[i]++;
	}

	rrep(i,n-1,0){
		if(i < n-1 ) e[i] = e[i+1];
		if( s[i] == 'E' ) e[i]++;
	}

	ll ans = INF;
	rep(i,0,n){
		ans = min( ans ,ll(w[i]+e[i]-1) );
	}

	cout << ans << endl;
	ret 0;
}

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

using namespace std;
int mod = 1046527;

int genhash(string str){
    int h = 0;

    for(auto ch : str){
        h *= 5;
        if(ch == 'A'){
            h += 1;
        } else if(ch == 'C'){
            h += 2;
        } else if(ch == 'G'){
            h += 3;
        } else {
            h += 4;
        }
    }
    return h;
}

void insert_dict(int* dict, string str){
    int h = genhash(str);
    int h1 = h%mod;
    int h2 = 1+(h%(mod-1));
    int i = 0;
    while(dict[(h1+h2*i)%mod]){
        if(dict[(h1+h2*i)%mod] == h){
            break;
        }
        ++i;
    };
    dict[(h1+h2*i)%mod] = h;
}

bool find_dict(int* dict, string str){
    int h = genhash(str);
    int h1 = h%mod;
    int h2 = 1+(h%(mod-1));
    int i = 0;
    while(dict[(h1+h2*i)%mod]){
        if(dict[(h1+h2*i)%mod] == h){
            return true;
        }
        ++i;
    }
    return false;
}
int main(){
    cin.sync_with_stdio(false);
    int dict[mod];
    char command[10];
    string str {};
    int n;
    cin >> n;
    while(n--){
        cin >> command >> str;
        if(command[0] == 'i'){
            insert_dict(dict, str);
        } else {
            cout << (find_dict(dict, str) ? "yes" : "no") << "\n";
        }
    }
}

Measured memory_bytes: 5272
#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
	if(b==0)
		return a;
	else 
		return gcd(b,a%b);
}
int main()
{
	long long a,b;
	while(cin>>a>>b)
	{
		long long i;
		if(a<b)
			swap(a,b);
		i=gcd(a,b);
		long long t=a*b/i;
		cout<<i<<" "<<t<<endl;
	}
	return 0;
}


Measured memory_bytes: 3008
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;
const lli inf = 3e18;

int main(){
    lli n,t,q;
    cin >> n >> t >> q;
    vector<lli> a(n), d(n);
    for(int i=0; i<n; i++){
        cin >> a[i] >> d[i];
        if(d[i]==2) d[i]=-1;
    }

    for(int i=0; i<q; i++){
        int p;
        cin >> p;
        p--;
        lli same;
        bool stop = false;
        for(int i=p; i>=0 && i<n; i+=d[p]){
            if(d[i] == d[p]){
                same = a[i];
            }else{
                stop = true;
                lli stopx = (same +a[i])/2;
                if(abs(a[p]-stopx) <= t){
                    cout << stopx << endl;
                }else{
                    cout << a[p] +d[p]*t << endl;;
                }
                break;
            }
        }
        if(!stop){
            cout << a[p] +d[p]*t << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 4344
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 2000000000;

int solve(vector<int>& a) {
    vector<int> dp(a.size(), INF);
    for (int i = 0; i < a.size(); i++) {
        *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
   return distance(dp.begin(), lower_bound(dp.begin(), dp.end(), INF));
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = solve(a);
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3592
#![allow(non_snake_case)]
#[allow(unused_imports)]
use std::io::{self, Write};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, char) => {
        read_value!($next, String).chars().collect::<Vec<char>>()[0]
     };
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
     };
    ($next:expr, isize1) => {
        read_value!($next, isize) - 1
    };
     ($next:expr, $t:ty) => {
         $next().parse::<$t>().expect("Parse error")
    };
}
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}
#[allow(dead_code)]
const MOD: usize = 1000000007;
#[allow(dead_code)]
fn to_num(c: char) -> i64 {
    c as i64 - 48
}


fn main() {
    input!{
        N: usize,
        S: chars,
    }
    let mut x = 0;
    let mut ans = 0;
    for c in S.into_iter() {
        x += if c == 'I' {1} else {-1};
        ans = max(ans, x);
    }
    println!("{}", ans);
}

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

using namespace std;
using ll = long long;

class UF{
private:
    std::vector<long long> data; //data[i] : 頂点iの親
public:
    UF(int n){
        data.resize(n,-1);
    }
    //頂点iの親を返す
    int root(int i){
        if(data[i] < 0)return i;
        else return data[i] = root(data[i]);
    }
    //連結
    void unit(int i,int j){
        i = root(i);j = root(j);
        if(i != j){
            data[i] += data[j];
            data[j] = i;
        }
    }

    //頂点iの属する集合の頂点数
    int size(int i){
        i = root(i);
        return -data[i];
    }
};

int main()
{
    int n, m, k; 
    cin >> n >> m >> k;
    UF tree(n);
    vector<vector<int>> blc(n);
    vector<int> fr(n);


    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; a--, b--;
        tree.unit(a, b);
        fr[a]++, fr[b]++;
    }

    for(int i = 0; i < k; i++) {
        int a, b; cin >> a >> b;
        a--, b--;
        blc[a].push_back(b), blc[b].push_back(a);
    }

    for(int i = 0; i < n; i++) {
        int res = tree.size(i) - fr[i] - 1;
        for(auto j : blc[i]) {
            if(tree.root(i) == tree.root(j))res--;
        }
        cout << res << endl;
    }

}

Measured memory_bytes: 10820
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
#define ll long long
#define ld long double
using namespace std;

int N;
ll mod=1000000007, b2[200010];
int num[200010];
bool looked[200010];

int dfs(int key, vector<vector<int>> &v, vector<vector<int>> &f){
	looked[key]=1;
	for(int i=0; i<v[key].size(); ++i){
		if(!looked[v[key][i]]){
			f[key].push_back(dfs(v[key][i], v, f)+1);
			num[key] += f[key].back();
		}
	}
	f[key].push_back(N-1-num[key]);
	return num[key];
}

void fill_b2(){
	b2[0]=1;
	for(int i=1; i<200010; ++i){
		b2[i]=(b2[i-1]*2)%mod;
	}
}

ll modpow(ll a, ll b, ll m){
    ll res=1, p=0, now=a;
    b %= (m-1);
    for(int i=0; b>p; ++i){
        if(b&((ll) 1<<i)){
            res=(res*now)%m;
            p |= ((ll) 1<<i);
        }
        now=(now*now)%mod;
    }
    return res;
}
ll modinv(ll a, ll m){
    return modpow(a, m-2, m);
}
ll moddiv(ll a, ll b, ll m){
    return (a*modinv(b, m))%m;
}


int main() {
	cin >> N;
	vector<vector<int>> G(N+1), fromt(N+1);
	for(int i=1; i<N; ++i){
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1, G, fromt);
	fill_b2();
	ll ans=0;
	for(int i=1; i<=N; ++i){
		ll sz=fromt[i].size();
		ans=(ans+b2[N-1]+sz-1);
		for(int j=0; j<fromt[i].size(); ++j){
			ans=(ans+mod-b2[fromt[i][j]])%mod;
		}
	}
	cout << moddiv(ans, b2[N], mod) << endl;
	return 0;
}

Measured memory_bytes: 33536