akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define LAST(x) (x)[(x).size() - 1]
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(LAST(v));
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head) << " ";
  print(tail...);
}

int gcd(int a, int b) {
  if (a < b)
    swap(a, b);
  int r;
  while (r = a % b) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  GI(N);
  GVI(A, N);
  vector<int> left(N);
  vector<int> right(N);
  left[0] = A[0];
  right[N - 1] = A[N - 1];
  FORIN(i, 1, N) {
    left[i] = gcd(left[i - 1], A[i]);
    right[N - i - 1] = gcd(right[N - i], A[N - i - 1]);
  }
  int max_gcd = 0;
  FOR(i, N) {
    int tmp_gcd = gcd(i > 0 ? left[i - 1] : right[i + 1],
                      i < N - 1 ? right[i + 1] : left[i - 1]);
    max_gcd = max(max_gcd, tmp_gcd);
  }
  print(max_gcd);
  return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>
#define MAX 2000001
void Heep(int);
int n,A[MAX];

void Heep(int i) {
  int l,r,large,ala;

  l = 2 * i;
  r = 2 * i + 1;

  if(l <= n && A[l] > A[i])
    large = l;
  else large = i;
  if(r <= n && A[r] > A[large])
    large = r;
  if (large != i) {
    ala = A[i];
    A[i] = A[large];
    A[large] = ala;
    Heep(large);
  }
}
int main() {
  int i;

  scanf("%d",&n);
  for(i = 1 ; i <= n ; i++) {
    scanf("%d",&A[i]);
  }
  
  for(i = n / 2 ; i >= 1 ; i--) {
    Heep(i);
  }
  
  for(i = 1 ; i <= n ; i++) {
    printf(" %d", A[i]);
  }
  
  printf("\n");
  
  return 0;
}




Measured memory_bytes: 3664
'use strict';

function Main(inputs) {
  // 1行目がinput[0], 2行目がinput[1], …に入る
  const input = inputs.split("\n");
  const n = Number(input[0]);
  const abc = input.slice(1, n + 1).map((t) => {
    const a = t.split(' ');
    return {
      a: Number(a[0]),
      b: Number(a[1]),
      c: Number(a[2])
    }
  });
  const dp = {
    a: [0],
    b: [0],
    c: [0]
  };
  for(let i = 0; i < n; i++){
    dp.a.push(Math.max(dp.b[i] + abc[i].a, dp.c[i] + abc[i].a));
    dp.b.push(Math.max(dp.a[i] + abc[i].b, dp.c[i] + abc[i].b));
    dp.c.push(Math.max(dp.a[i] + abc[i].c, dp.b[i] + abc[i].c));
  }
  console.log(Math.max(dp.a.pop(), dp.b.pop(), dp.c.pop()));
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 51152
#include <bits/stdc++.h>
#define mod 1000000007
#define ull unsigned ll
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi acos(-1)
#define nui 100
#define INF 100000000000
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define F(i,a,n) for(ll i=a;i<n;i++)
#define B(i,a,n) for(ll i=n-1;i>=a;i--)
#define tc int t;cin>>t;while(t--)
#define tcf int t;cin>>t;for(int w=1;w<=t;w++)



using namespace std;

void dex(int a)
{
    if (a == 1)
    {
        cout << "1\n";
    }
    else if (a == -1)
    {
        cout << "-1\n";
    }
    else if (a == 0)
    {
        cout << "0\n";
    }
    else if (a == 2)
    {
        cout << "YES\n";
    }
    else if (a == 3)
    {
        cout << "NO\n";
    }

}

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
       a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}




int main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

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

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

    ll n;
    cin >> n;
    ll a[n];
    ll sum = 0;
    ll csum = 0;
    F(i, 0, n)
    {
        cin >> a[i];
        sum += a[i];
        csum += (a[i] % mod) * (a[i] % mod);
        csum %= mod;
        sum %= mod;
    }
    sum = ((sum % mod) * (sum % mod)) % mod;
    cout << ((mod + sum - csum) * binpow(2,mod-2) ) % mod << "\n";

	//cout << binpow(2,mod-2) << '\n';



    return 0;


    return 0;

}

Measured memory_bytes: 5208
import sys
S=input()
T=input()
start=[-1 for i in range(26)]
goal=[-1 for i in range(26)]
alp=[i for i in "abcdefghijklmnopqrstuvwxyz"]
for i in range(len(S)):
  ind_s=alp.index(S[i])
  ind_t=alp.index(T[i])

  if start[ind_s]!=-1 or goal[ind_t]!=-1:
    if start[ind_s]!=ind_t or goal[ind_t]!=ind_s:
      print("No")
      sys.exit()
  else:
    start[ind_s]=ind_t
    goal[ind_t]=ind_s
print("Yes")

Measured memory_bytes: 3632
while n = gets do
  break if n == nil
  n = n.to_i
  sum = 0

  (0..9).each do |a|
    (0..9).each do |b|
      (0..9).each do |c|
        (0..9).each do |d|
          if  a + b + c + d == n then
            sum +=1
          end
        end
      end
    end
  end
  puts sum
end



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

typedef long long ll;

int main(){
    string s;
    cin >> s;
    int ans=0;
    for(int i = 1; i < (int)s.size(); i++)
    {
        if(s[i]!=s[i-1]) ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}

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

int main () {
    string s;
    if (getline(cin, s)) {
        for (int i = 0; i < s.size(); i++) {
            if (islower(s[i])) {
                s[i] = toupper(s[i]);
            } else {
                s[i] = tolower(s[i]);
            }
        }
        cout << s << endl;
    }
}


Measured memory_bytes: 3208
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
string IntToString(int);
int StringToInt(string);
int main(){
  while(1){
    int n;
    cin >> n;
    if(n == 0)break;
    vector<int> M(n);
    vector<bitset<101> > P(n,bitset<101>(0));
    for(int i = 0;i < n;i++){
      cin >> M[i];
      for(int j = 0;j < M[i];j++){
	int tmp;
	cin >> tmp;
	bitset<101> tmp_bit(1);
	tmp_bit =(tmp_bit << (tmp-1));
	P[i] = (P[i] | tmp_bit);
      }
    }

    int more_n;
    cin >> more_n;
    bitset<101> more(0);
    for(int i = 0;i < more_n;i++){
      int tmp;
      cin >> tmp;
      bitset<101> tmp_bit(1);
      tmp_bit =(tmp_bit << (tmp-1));
      more = (more | tmp_bit);
    }
    int flag = 0;
    int ans;
    for(int i = 0;i < n;i++){
      if((P[i] & more) == more){
	ans = i+1;
	flag++;
      }
    }
    if(flag == 1)cout << ans << endl;
    else cout << "-1" << endl;
    
  }
  return 0;   
}
string IntToString(int number){
  stringstream ss;
  ss << number;
  return ss.str();
}
int StringToInt(string number){
  stringstream ss;
  ss << number;
  int numInt;
  ss >> numInt;
  return numInt;
  
}

Measured memory_bytes: 1204
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
C = [int(a) for a in input().split()]

ans = sum(B)
pre_A = -1
for i in range(N):
    if pre_A + 1 == A[i]:
        ans += C[pre_A - 1]
    pre_A = A[i]

print(ans)

Measured memory_bytes: 38420
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

class UnionFind(n: Int) {
    private val rank = IntArray(n) { 0 }
    private val parent = IntArray(n) { -1 }

    fun find(x: Int): Int {
        if (parent[x] < 0) {
            return x
        }
        parent[x] = find(parent[x])
        return parent[x]
    }

    fun unite(x: Int, y: Int) {
        val x1 = find(x)
        val y1 = find(y)
        if (x1 == y1) {
            return
        }
        if (rank[x1] < rank[y1]) {
            parent[y1] += parent[x1]
            parent[x1] = y1
        } else {
            parent[x1] += parent[y1]
            parent[y1] = x1
            if (rank[x1] == rank[y1]) {
                rank[x1]++
            }
        }
    }

    fun same(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }

    fun size(x: Int): Int {
        return -parent[find(x)]
    }
}

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val m = sc.nextInt()
    val p = Array(n) { sc.nextInt() - 1 }
    val uf = UnionFind(n)
    for (i in 0 until m) {
        val x = sc.nextInt() - 1
        val y = sc.nextInt() - 1
        uf.unite(x, y)
    }
    var count = 0
    for (i in 0 until n) {
        if (uf.same(p[i], i)) count++
    }
    println(count)
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 56844
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong();
		run(n);
		scan.close();
		System.exit(0);
	}

	private static void run(long n) {
		System.out.print(n + ":");
		double max = Math.sqrt(n);
		for (long i = 2; i <= max;) {
			if (n == 1)
				break;
			if (n % i == 0) {
				System.out.print(" " + i);
				n /= i;
			} else
				i++;
		}
		if (n == 1)
			System.out.println();
		else
			System.out.println(" " + n);
	}

}

Measured memory_bytes: 26336
#include<stdio.h>
#include<string.h>
int main()
{
char ch[2982],c,s ;
int ac=0,wa=0,tle=0,re=0,n,count,i ;
scanf("%d",&n)  ;
for(i=1 ; i<=n ; i++)
{
    scanf("%s",ch) ;
    count=strlen(ch) ;
    if(count==3)
        tle++ ;
    else
    {
        if(ch[0]=='A')
            ac++ ;
        else if(ch[0]=='W')
            wa++ ;
        else
            re++ ;
    }

}
printf("AC x %d\n",ac) ;
printf("WA x %d\n",wa) ;
printf("TLE x %d\n",tle) ;
printf("RE x %d\n",re) ;
return 0 ;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define BIP __builtin_popcount

const int B = 16;
const int N = 1<<B;

using namespace std;

int n, ord[N];
ll dp[N], a[B][B];

struct{
	bool operator()(int a, int b){
		return BIP(a) < BIP(b);
	}
} cmp;

int main(){

	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++) cin >> a[i][j];
	}

	for(int i=0; i<(1<<n); i++) ord[i] = i;
	sort(ord, ord+(1<<n), cmp);

	for(int i=1; i<(1<<n); i++){
		int c = ord[i];
		vector<int> v;
		for(int j=0; j<n; j++) if((c>>j)&1) v.pb(j);
		int z = v.size();
		for(int j=1; j<(1<<(z-1)); j++){
			ll nc1 = 0, nc0 = 0;
			for(int k=0; k<z; k++){
				if((j>>k)&1) nc1 += 1<<v[k];
				else nc0 += 1<<v[k];
			}
			dp[c] = max(dp[c], dp[nc0]+dp[nc1]);
		}

		ll nsum = 0;
		for(int j=0; j<z; j++){
			for(int k=0; k<j; k++){
				nsum += a[v[j]][v[k]];
			}
		}

		dp[c] = max(dp[c], nsum);
	}

	cout << dp[(1<<n)-1] << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	double time1;
	double time2;
	
	while(scanf("%lf %lf", &time1, &time2) != EOF){
		if (time1 < 35.5 && time2 < 71){
			printf("AAA\n");
		}
		else if (time1 < 37.5 && time2 < 77){
			printf("AA\n");
		}
		else if (time1 < 40 && time2 < 83){
			printf("A\n");
		}
		else if (time1 < 43 && time2 < 89){
			printf("B\n");
		}
		else if (time1 < 50 && time2 < 105){
			printf("C\n");
		}
		else if (time1 < 55 && time2 < 116){
			printf("D\n");
		}
		else if (time1 < 70 && time2 < 148){
			printf("E\n");
		}
		else {
			printf("NA\n");
		}
	}
	
	return (0);
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define gap ' '
#define L(i) ((i) - (&i))

const int inf = 1e9 + 7;
const int MAXN = 1e5 + 5;

	
int main(){		
	int n; cin >> n;
	cout << pow(n,3);



	return 0;
}


Measured memory_bytes: 4132
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i < (n); i++)

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

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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 40;

map <pair<string, string>, LL> dp[MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	int n;
	string S;
	cin >> n >> S;
	dp[0][MP("", "")] = 1;
	FOR(i, 0, SZ(S))
	{
		ITER(it, dp[i])
		{
			string R = it->first.first, B = it->first.second;
			//cout << i << " " << R << " " << B << " " << it->second << endl;
			if(SZ(R) < n && (SZ(B) <= n - 1 - SZ(R) || B[n - 1 - SZ(R)] == S[i]))
			{
				//cout << "here" << endl;
				dp[i + 1][MP(R + S[i], B)] += it->second;
			}
			if(SZ(B) < n && (SZ(R) <= n - 1 - SZ(B) || R[n - 1 - SZ(B)] == S[i]))
			{
				//cout << "here" << endl;
				dp[i + 1][MP(R, B + S[i])] += it->second;
			}
		}
	}
	LL ans = 0;
	ITER(it, dp[SZ(S)])
		ans += it->second;
	cout << ans;
	return 0;
}

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

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N;

  cin >> N;
  vector< pair< int, int > > st(N);
  for(int i = 0; i < N; i++) {
    cin >> st[i].first >> st[i].second;
  }
  sort(begin(st), end(st), [&](pair< int, int > x, pair< int, int > y)
  {
    return (x.first - y.second < y.first - x.second);
  });


  int dp[5001];
  fill_n(dp, 5001, INF);
  dp[0] = 0;
  int ret = 0;
  for(int i = 0; i < N; i++) {
    for(int j = N - 1; j >= 0; j--) {
      if(dp[j] <= st[i].first) {
        dp[j + 1] = min(dp[j + 1], dp[j] + st[i].second);
        ret = max(ret, j + 1);
      }
    }
  }

  cout << ret << endl;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

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

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

int gcd(int a, int b){
	if (b == 0)return a;
	return gcd(b, a % b);
}


int main(void){
    int d;
    cin >> d;

    if(d == 25){
        cout << "Christmas" << endl;
    } else if(d == 24){
        cout << "Christmas Eve" << endl;
    } else if(d == 23){
        cout << "Christmas Eve Eve" << endl;
    } else {
        cout << "Christmas Eve Eve Eve" << endl;
    }
    
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define mod 1000000007
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
ll power(ll a,ll b) {
    if (b==0) return 1;
    ll c = power(a,b>>1);
    c = (c*c)%mod;
    if (b&1) return (c*a)%mod;
    return c;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)1e5+5;
const int Q = 301;

string verdict[N];
void solve() {
	int n,m,p;
	string s;
	cin>>n>>m;
	REP(i,1,n) {
        verdict[i] = "";
	}
	REP(i,1,m) {
        cin>>p>>s;
        verdict[p] += (char)('0'+(s=="AC"));
	}
	int ans = 0;
	int cor = 0;
	REP(i,1,n) {
	    int cnt = 0;
	    bool ch = false;
        for (auto it:verdict[i]) {
            if (it=='0') cnt++;
            else {
                ch = true;
                break;
            }
        }
        if (ch) cor++, ans += cnt;
	}
	cout<<cor<<" "<<ans;
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

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

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        cout<<"\n";
    }
}


Measured memory_bytes: 5760
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

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

    vector<tuple<int, int, int>> x(n * 2);
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        x[i*2] = make_tuple(a, i, 0);
        x[i*2+1] = make_tuple(b, i, 1);
    }
    sort(x.begin(), x.end());

    bool a, b;
    a = b = false;
    int ans = 0;
    bool dup = false;
    set<int> s;
    rep(i, n){
        int id = get<1>(x[i]);
        if(s.find(id) != s.end()){
            dup = true;
        }
        s.insert(id);

        int type = get<2>(x[i]);
        if(type){
            b = true;
        }else{
            a = true;
        }

        ans += get<0>(x[i]);
    }

    if(not a || not b || dup){
        cout << ans << endl;
        return 0;
    }

    ans = 0;
    s = set<int>();
    dup = false;
    rep(i, n-1){
        s.insert(get<1>(x[i]));
        ans += get<0>(x[i]);
    }

    if(s.find(get<1>(x[n-1])) != s.end()){
        cout << ans + get<0>(x[n-1]) << endl;
        return 0;
    }

    if(s.find(get<1>(x[n])) != s.end()){
        cout << ans + get<0>(x[n]) << endl;
        return 0;
    }

    ans -= get<0>(x[n-2]);

    ans = min(ans + get<0>(x[n-2]) + get<0>(x[n+1]), ans + get<0>(x[n-1]) + get<0>(x[n]));
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 9600
h,w=map(int,input().split())
g=[[*input()] for _ in range(h)]
from collections import *
a=0
for sx in range(h):
  for sy in range(w):
    if g[sx][sy]=='#': continue
    d=[[-1]*w for _ in range(h)]
    d[sx][sy]=0
    q=deque([(sx,sy)])
    while q:
      x,y=q.popleft()
      for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
          d[nx][ny]=d[x][y]+1
          q.append((nx,ny))
    a=max(a,max(max(i for i in l) for l in d))
print(a)

Measured memory_bytes: 9404
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<double> d(3);
  while(cin>>d[0]>>d[1]>>d[2],d[0]+d[1]+d[2]){
    int n;cin>>n;
    sort(d.begin(),d.end());
    double taikaku;
    taikaku=sqrt(((d[0]*d[0])+(d[1]*d[1])));
    //   cout<<d[0]<<" "<<d[1]<<endl;
    for(int i=0;i<n;i++){
      double a;cin>>a;
      a*=2;
      if(a>taikaku)
	cout<<"OK"<<endl;
      else
	cout<<"NA"<<endl;
    }
  }
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> d(N);
    for (int i = 0; i < N; i++)
    {
        cin >> d.at(i);
    }
    set<int> l(d.begin(), d.end());
    cout << l.size() << endl;
}

Measured memory_bytes: 256
# def makelist(n, m):
#     return [[0 for i in range(m)] for j in range(n)]

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

dic = {}

for e in A:
    if e not in dic:
        dic[e] = 1
    else:
        dic[e] += 1

ans = 0
for k, v in dic.items():
    if k > v:
        ans += v
    elif k < v:
        ans += v - k
print(ans)


Measured memory_bytes: 18172
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=300005;
int n,a[N];

bool check(int l,int r)
{
	int mn=n+1,mx=0;
	rep(i,l,r) mn=min(mn,a[i]),mx=max(mx,a[i]);
	if(mn!=l || mx!=r) return 0;
	int x=0,y=0;
	for(int i=l; i<=r; i+=2)
		if(x<a[i] && y<a[i]) y=a[i];
		else if(x<a[i]) x=a[i];
		else return 0;
	return 1;
}

int main()
{
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
	for(int i=1; i<=n; ++i)
	{
		if(a[i]==i) continue;
		int p=i;
		while(p<=n-2)
		{
			if(a[p+1]!=p+1) break;
			if(a[p+2]==p+2) break;
			p+=2;
		}
		if(!check(i,p)) return puts("No"),0;
		i=p;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<vector>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=2e18;
const double EPS=1e-7;

ll N;
string c[500];
int main(){
    cin>>N;
    for(ll i=0;i<N;i++){
        cin>>c[i];
    }
    ll ans=0;
    for(ll a=0;a<N;a++){
        for(ll i=0;i<N;i++){
            char tmp=c[i][0];
            for(ll j=0;j<N-1;j++){
                c[i][j]=c[i][j+1];
            }
            c[i][N-1]=tmp;
            //cout<<c[i]<<endl;
        }
        bool isSame=true;
        for(ll i=0;i<N;i++){
            string tmp1,tmp2;
            tmp1=c[i].substr(i+1,N-(i+1));
            for(ll j=i+1;j<N;j++){
                tmp2+=c[j][i];
            }
            if(tmp1!=tmp2){
                isSame=false;
                break;
            }
        }
        if(isSame){
            ans+=N;
        }
    }
    cout<<ans<<endl;

    
}

Measured memory_bytes: 384
#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 fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main() {
  int n, p = 0, q = 0, r, s;
  scanf("%d", &n);
  v1i v(n);
  rep(i, n) scanf("%d", &v[i]);
  rep(i, n){
    if(p <= v[i]){
      p = v[i];
      r = i+1;
    }
    if(q >= v[i]){
      q = v[i];
      s = i+1;
    }
  }
  if(q >= 0){
    int m = n-1;
    printf("%d\n", m);
    rep(i, m) printf("%d %d\n", i+1, i+2);
  }
  else if(p <= 0){
    int m = n-1;
    printf("%d\n", m);
    rrep(i, m) printf("%d %d\n", i+2, i+1);
  }
  else if(p > -1*q){
    int m = 2*n-1;
    printf("%d\n", m);
    rep(i, m/2+1) printf("%d %d\n", r, i+1);
    rep(i, m/2) printf("%d %d\n", i+1, i+2);
  }
  else{
    int m = 2*n-1;
    printf("%d\n", m);
    rep(i, m/2+1) printf("%d %d\n", s, i+1);
    rrep(i, m/2) printf("%d %d\n", i+2, i+1);
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin>>n;
  while(n--){
    string s;
    cin>>s;
    bool f=s[0]=='>';
    int l=s.size();
    f&=l>5;
    if(s[1]=='\''){
      int x=0;
      int i;
      for(i=2;i<l;i++){
	if(s[i]=='=') x++;
	else{
	  f&=s[i]=='#';
	  break;
	}
      }
      for(i++;i<l;i++){
	if(s[i]=='=') x--;
	else{
	  f&=s[i]=='~';
	  break;
	}
      }
      f&=i==l-1&&x==0;
    }else if(s[1]=='^'){
      int i;
      for(i=2;i<l;i+=2){
	if(!(i+1<l)){
	  f=0;
	  break;
	}
	if(s[i]=='Q'&&s[i+1]=='=') continue;
	if(i+2==l&&s[i]=='~'&&s[i+1]=='~') continue;
	break;
      }
      f&=i==l;
    }else f=0;
    cout<<(f?(s[1]=='^'?"B":"A"):"NA")<<endl;
  }
  return 0;
}

Measured memory_bytes: 3220
#include<bits/stdc++.h>
const double PI = 3.141592653589793238463;
using namespace std;
int main()
{
    double a;
    cin>>a;
    //double b=3.141592653589793238;
    cout<<fixed<<setprecision(14)<<2.0*22/7*a<<endl;
}


Measured memory_bytes: 3780
N,K=map(int,input().split())
A=list(map(int,input().split()))

ans=10**100
for i in range(2**(N-1)):
  bit=format(i,'0'+str(N)+'b')
  bit=list(map(int,bit))
  maxh=A[0]
  price=0
  color=1
  for n in range(N):
    if n==0:continue
    elif bit[n]==0:
      if A[n]>maxh:
        color+=1
        maxh=A[n]
    else:
      if A[n]<=maxh:
        maxh+=1
        price+=maxh-A[n]
        color+=1
      else:
        color+=1
        maxh=A[n]
  if color>=K and price<=ans:
    ans=price
print(ans)
      

Measured memory_bytes: 3188
#include <stdio.h>
 

int main(void) {
    int k;
    int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    scanf("%d", &k);

    printf("%d\n", a[k-1] );
    
    return 0;
}



Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


//CODE
void solve(void)
{
  int N;
  cin>>N;
  vector<int> vec(N);
  vector<int> svec(N);
  for (int i = 0; i < N; i++)
  {
    cin>>vec[i];
  }
  
  svec = vec;
  sort(ALL(svec));
  int MA = svec[N/2-1];
  int MB = svec[N/2];
  for (int i = 0; i < N; i++)
  {
    int X = vec[i];
    if(X < MB)
    {
      cout<<MB<<endl;
    }
    else
    {
      cout<<MA<<endl;
    }
    
  }
  
  
  
  

  return;
}


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

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();
  

 
  return 0;
}


Measured memory_bytes: 5376
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			int h = sc.nextInt();
			int w = sc.nextInt();
			String[] S = new String[h];
			char[][] s = new char[h+2][w+2];
			
			for(int i=0;i<h;i++) {
				S[i] = sc.next();
				for(int j=0;j<w;j++) {
					s[i+1][j+1]=S[i].charAt(j);
				}
			}
			
			for(int i=1;i<h+2;i++) {
				for(int j=1;j<w+2;j++) {
					if(s[i][j]=='#') {
						if(s[i-1][j]!='#'&&s[i+1][j]!='#'&&s[i][j+1]!='#'&&s[i][j-1]!='#') {
							
							System.out.println("No");
							return;
						}
					}
				}
			}
			
			System.out.println("Yes");
			
			
			
			
		}
	}

Measured memory_bytes: 21844
import math

n = int(input())
a = list(map(int,input().split()))

lefGcd = [0]*100100
rigGcd = [0]*100100

lefGcd[0] = a[0]
rigGcd[n-1] = a[n-1]

#左側からGCDを計算した値を保持する。
for i in range(1,n):
	lefGcd[i] = math.gcd(lefGcd[i-1],a[i])

#右側からGCDを計算した値を保持する。
for i in reversed(range(0,n-1)):
	rigGcd[i] = math.gcd(rigGcd[i+1],a[i])

#一番左か一番右の値を除去したGCDの値を初期値にする。
ans = max(rigGcd[1],lefGcd[n-2])

#左からのGCD,1個飛ばし,右からのGCDを計算し、比較する。
for i in range(1,n-1):
	ans = max(ans,math.gcd(lefGcd[i-1],rigGcd[i+1]))

print(ans)


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

int main() {
	int x,n;
	cin>>x>>n;
	vector<int>p(105,0);
	for(int i=0; i<n; i++){
	    int tm;
	    cin>>tm;
	    p[tm]=1;
	}
	int diff=1e5;
	int ans=0;
	for(int i=0; i<105;i++){
	    //cout<<i<<" "<<p[i]<<" "<<abs(x-i)<<endl;
	    if(p[i]==0){
	        //cout<<i<<" "<<diff<<" "<<abs(x-i)<<endl;
	        if(diff>abs(x-i)){
	            ans=i;
	            diff=abs(x-i);
	        }
	    }
	}
	cout<<ans<<endl;
}



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

int main() {
  ll a,b; cin >> a >> b;
  if(a!=3 && b!=3) cout << 3 << endl;
  else if(a!=2 && b!=2) cout << 2 << endl;
  else if(a!=1 && b!=1) cout << 1 << endl;
  
  return 0;
}

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

int main(){
    int N,X;
    cin>>N>>X;
    int ans=1;
    int c=0;
    for(int i=0;i<N;i++){
        int L;
        cin>>L;
        c+=L;
        if(c<=X) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
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...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while (1) {
        c -= b;
        if (c <= 0) {
            cout << "Yes\n";
            return 0;
        }
        a -= d;
        if (a <= 0) {
            cout << "No\n";
            return 0;
        }
    }
}


Measured memory_bytes: 3572
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
res = 0
for i in range(n):
    res += b[i]
    if(i and a[i - 1] == a[i] - 1):
        res += c[a[i - 1] - 1]
print(res)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int n, count = 0;
  bool flag = 0;
  vector<int> a;
  vector<int> b;
  cin >>n;
  for(int i=0; i<n; i++)
  {
    int x,y;
    cin >> x >> y;
    a.push_back(x);
    b.push_back(y);
  }
  for(int i=0; i<n; i++)
  {
    if(count == 3)
    {
      flag = 1;
      break;
    }
    if(a[i] == b[i])
    {
      count++;
      if(count == 3)
      {
        flag = 1;
        break;
      }
    }
    else
      count = 0;
  }
  if(flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3132
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>

#define ll long long
#define ld long double

using namespace std;

ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
ll ans = 0, mx = 0, mn = 1e9, sum = 0, cnt = 0, avr = 0, index = -1;

//map<char, int>freq;
vector<int>vec;
vector<int>freq(10000 + 5, 0);
vector<int>cFreq(150, 0);

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		for (int j = 0; j < t; j++)
		{
			cin >> x;
			freq[x]++;
		}
	}
	for (int i = 0; i <= m; i++)
	{
		if (freq[i] >= n)ans++;
	}
	cout << ans << endl;
	return 0;
}

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

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = int.Parse(Console.ReadLine());
			var inputList = Console.ReadLine().Split(' ');

			var inputDictionary = new Dictionary<string, long>();

			foreach(var value in inputList)
			{
				if(inputDictionary.ContainsKey(value))
				{
					inputDictionary[value]++;
				}
				else
				{
					inputDictionary.Add(value, 1);
				}
			}

			var normalAnswer = new Dictionary<string, long>();
			var lessAnswer = new Dictionary<string, long>();

			foreach(var keyValuePair in inputDictionary)
			{
				if(keyValuePair.Value < 2)
				{
					normalAnswer.Add(keyValuePair.Key, 0);
					lessAnswer.Add(keyValuePair.Key, 0);
				}
				else if(keyValuePair.Value == 2)
				{
					normalAnswer.Add(keyValuePair.Key, 1);
					lessAnswer.Add(keyValuePair.Key, 0);
				}
				else
				{
					var normal = (keyValuePair.Value * (keyValuePair.Value - 1)) / 2;
					normalAnswer.Add(keyValuePair.Key, normal);
					var less = ((keyValuePair.Value - 1) * (keyValuePair.Value - 2)) / 2;
					lessAnswer.Add(keyValuePair.Key, less);
				}
			}

			var outputDictionary = new Dictionary<string, long>();

			var sum = normalAnswer.Values.Sum();

			foreach (var key in inputDictionary.Keys)
			{
				outputDictionary.Add(key, sum - normalAnswer[key] + lessAnswer[key]);
			}

			foreach(var key in inputList)
			{
				Console.WriteLine(outputDictionary[key]);
			}
		}
	}
}


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

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> A.at(i).at(j);
        }
    }

    vector<pair<int, pair<int, int>>> a;
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            a.push_back({A.at(i).at(j), {i, j}});
        }
    }
    sort(a.begin(), a.end());

    A = vector<vector<int>>(N, vector<int>(N, -1));
    for (int i = 0; i < N; i++)
    {
        A.at(i).at(i) = 0;
    }

    int64_t res = 0;
    for (auto p : a)
    {
        int c = p.first, i = p.second.first, j = p.second.second;
        int mn = INT_MAX;
        for (int k = 0; k < N; k++)
        {
            if (A.at(i).at(k) < 0 || A.at(k).at(j) < 0)
            {
                continue;
            }
            mn = min(mn, A.at(i).at(k) + A.at(k).at(j));
        }
        if (c > mn)
        {
            cout << -1 << endl;
            return 0;
        }
        if (c < mn)
        {
            res += c;
        }
        A.at(i).at(j) = c;
        A.at(j).at(i) = c;
    }
    cout << res << endl;
}

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

template <long long mod, long long primitive_root>
struct NTT {
private:
    static long long mod_pow(long long n, long long p, long long m) {
        long long ret = 1;
        while (p > 0) {
            if (p & 1) ret = ret * n % m;
            n = n * n % m;
            p >>= 1;
        }
        return ret;
    }

    static pair<long long, long long> extgcd(long long a, long long b) {
        long long s = a, sx = 1, sy = 0, t = b, tx = 0, ty = 1;
        while (t) {
            long long q = s / t;
            s -= t * q;
            swap(s, t);
            sx -= tx * q;
            swap(sx, tx);
            sy -= ty * q;
            swap(sy, ty);
        }
        return {sx, sy};
    }

    static long long mod_inv(long long a, long long m) {
        long long inv = extgcd(a, m).first;
        return (inv % m + m) % m;
    }

    static void ntt(vector<long long>& f, int sign) {
        int n = f.size();
        if (n == 1) return;
        vector<long long> a, b;
        for (int i = 0; i < n / 2; i++) {
            a.push_back(f[2 * i]);
            b.push_back(f[2 * i + 1]);
        }
        ntt(a, sign);
        ntt(b, sign);
        long long cur = 1;
        long long omega = mod_pow(primitive_root, (mod - 1) * mod_inv(n, mod) % mod, mod);
        if (sign == -1) omega = mod_inv(omega, mod);
        for (int i = 0; i < n; i++) {
            f[i] = (a[i % (n / 2)] + cur * b[i % (n / 2)]) % mod;
            cur = cur * omega % mod;
        }
    }

public:
    static vector<long long> convolution(const vector<long long>& a, const vector<long long>& b) {
        int size = a.size() + b.size() - 1;
        int n = 1;
        while (n < size) n <<= 1;

        vector<long long> na = a, nb = b;
        na.resize(n);
        nb.resize(n);

        ntt(na, 1);
        ntt(nb, 1);
        for (int i = 0; i < n; i++) na[i] = na[i] * nb[i] % mod;
        ntt(na, -1);
        na.resize(size);
        const long long n_inv = mod_inv(n, mod);
        for (int i = 0; i < size; i++) na[i] = na[i] * n_inv % mod;
        return na;
    }
};

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

    int N, M;
    cin >> N >> M;
    vector<ll> a(N), b(M);
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < M; i++) cin >> b[i];
    vector<ll> c = NTT<998244353, 3>::convolution(a, b);
    for (int i = 0; i < N + M - 1; i++) cout << c[i] << (i < N + M - 2 ? " " : "\n");
}

Measured memory_bytes: 44316
import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline

num, person = map(int, input().split())
arr = []

for i in range(num):
    s, t, x = map(int, input().split())
    arr.append((s - x - 0.5, 1, x, i))
    arr.append((t - x - 0.5, -1, x, i))

for i in range(person):
    d = int(input())
    arr.append((d,))

arr.sort()

heap = []
done = set()

for elem in arr:
    if len(elem) == 1:
        d = elem[0]
        while heap and heap[0][1] in done:
            heappop(heap)
        if heap:
            print(heap[0][0])
        else:
            print(-1)
        continue

    time, kind, x, i = elem
    if kind == 1:
        heappush(heap, (x, i))
    elif kind == -1:
        done.add(i)

Measured memory_bytes: 108068
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

const int V_MAX = 100000;
int n, W;
int v[101], w[101];
ll dp[101][100001];

ll rec(int i, int j) {
    if (j == 0) return 0;
    if (i == 0) return linf;
    if (dp[i][j] != -1) return dp[i][j];
    if (j - v[i] >= 0) {
        ll a = min(rec(i - 1, j), rec(i - 1, j - v[i]) + w[i]);
        if (a > W) return dp[i][j] = linf;
        return dp[i][j] = a;
    }
    return dp[i][j] = rec(i - 1, j);
}
int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> W;
    reps(i, n) cin >> w[i] >> v[i];
    rreps(i, V_MAX) {
        if (rec(n, i) != linf) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 82500
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

struct edge{
  int to;
  int cost;
};
int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<vector<edge>> to(n);
  rep(i,n-1){
    int a,b,c; cin >> a >> b >> c;
    --a;  --b;
    to[a].push_back({b,c});
    to[b].push_back({a,c});
  }
  int q,k; cin >> q >> k;
  queue<int> que;
  que.push(--k);
  vector<ll> dist(n);
  while(!que.empty()){
    int now = que.front(); que.pop();
    for(auto next : to[now]){
      if(dist[next.to] != 0) continue;
      dist[next.to] += dist[now]+next.cost;
      que.push(next.to);
    }
  }
  rep(i,q){
    int x,y; cin >> x >> y;
    cout << dist[--x]+dist[--y] << "\n";
  }
  // cout << "\n";
  return 0;
}


Measured memory_bytes: 10652
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
using ll = long long int;

int main() {
  ll N, H;
  cin >> N >> H;

  priority_queue<ll, vector<ll>> A;
  priority_queue<ll, vector<ll>> B;
  for (ll i = 0; i < N; i++) {
    ll ai, bi;
    cin >> ai >> bi;
    A.push(ai);
    B.push(bi);
  }

  ll ans = 0;
  while (H > 0) {
    if (B.empty() || B.top() < A.top()) {
      ans += (H + A.top() - 1) / A.top();
      break;
    } else {
      H -= B.top();
      B.pop();
      ans++;
    }
  }
  cout << ans << endl;
}

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

int main()
{
  int n, i, x;
  int count = 0;
  int a[100000] = {};
  cin >> n;
  //
  for(i=1; i<=n; i++)
  {
    cin >> a[i];
  }
  //
  x = a[1];
  count++;
  for(i=1; i<=n; i++)
  {
    if(x != 2)
    {
      x = a[x];
      count++;
    }
    else
    {
      cout << count;
      break;
    }
  }
  if(i >= n)
  {
    cout << "-1";    
  }

  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{

	 int n,k;cin>>n>>k;
	 int vis[200];
	 for(int i=1;i<=n;i++)vis[i]=0;
	 for(int i=1;i<=k;i++)
	 {
	 	int d;cin>>d;
	 	for(int j=1;j<=d;j++)
	 	{
	 		int x;cin>>x;vis[x]=1;
		 }
	 }
	 int num=0;
	 for(int i=1;i<=n;i++)
	 if(!vis[i])num++;
	 cout<<num<<endl;
	
	return 0;
}

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

int main()
{
ll n , q ;
cin >> n >> q ;
vector<ll> a(n);
vector<ll> sum;
sum.push_back(0);
vector<ll> half;
half.push_back(0);
rep(i, n){
  cin >> a[i];
  sum.push_back(a[i] + sum[i]);
  half.push_back((i%2?0:a[i]) + half[i]);
}
vector<ll> x(q);
rep(i, q){
  cin >> x[i];
}
rep(i,q){
  auto judge = [&](ll val) { 
    if(val==1)return true;
    //cout << x[i]-a[n-2*val+2] <<" " << a[n-val+1]-x[i] << endl;
    if(x[i]-a[n-2*val+1]>a[n-val]-x[i])return false;
    else return true;
  };
  auto binarysearch = [&](ll lowerbound, ll upperbound) {
    if (!judge(lowerbound)) return -1LL;
    ll lower = lowerbound, upper = upperbound;
    while (1){
      if (judge((lower + upper) / 2)) lower = (lower + upper) / 2;
      else upper = (lower + upper) / 2;
      if (abs(upper - lower) <= 1){
        if (judge(upper)) return upper;
        else return lower;
      }
    }
  };
  ll ind=binarysearch(1,(n+1)/2);
  ll ans;
  if(n%2)ans=sum[n]-sum[n-ind]+half[n-2*ind+1];
  else ans=sum[n]-sum[n-ind]+sum[n-2*ind+1]-half[n-2*ind+1];
  cout << ans << endl;
}
return 0;
}

Measured memory_bytes: 5100
//shivamkr21
#include<bits/stdc++.h>
#define lli long long int
#define endl "\n"
using namespace std;
int main()
{
  lli n,c=0,w=0;
  cin>>n;
  lli ar[n+1];
  for(lli i=1;i<n;i++)
  {
    cin>>ar[i];
    if(ar[i]==i)
    {
      c++;
    }
    else
    {
      w++;
    }
  }
  if(w>2)
  {
    cout<<"NO"<<endl;
  }
  else
  {
    cout<<"YES"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

const ll MOD=1000000007;

ll dp[105][100005];
ll n,k;
ll sump[105][100005];
ll a[105];

ll f(ll x, ll y){
	ll &r=dp[x][y];
	if(r>=0)return r;
	if(x==n){
		if(y==0){
			r=1; return r;
		}
		r=0; return r;
	}
	r=(sump[x+1][y+1]-sump[x+1][max(0ll,y-a[x])]+MOD)%MOD;
	return r;
}

int main(){FIN;
	cin>>n>>k;
	fore(i,0,n)cin>>a[i];
	mset(dp,-1);
	fore(i,0,n+1){
		fore(j,1,k+2){
			sump[n-i][j]=f(n-i,j-1)+sump[n-i][j-1];
			if(sump[n-i][j]>MOD)sump[n-i][j]-=MOD;
		}
	}
	/*fore(i,0,n+1){
		fore(j,0,k+2){
			cout<<sump[i][j]<<" ";
		}
		cout<<"\n";
	}
	fore(i,0,n+1){
		fore(j,0,k+1){
			cout<<f(i,j)<<" ";
		}
		cout<<"\n";
	}*/
	cout<<f(0,k);
	return 0;
}

Measured memory_bytes: 162304
fn main() -> Result<(), Box<dyn std::error::Error>>{
  let mut n = String::new();
  let mut x = String::new();
  std::io::stdin().read_line(&mut n)?;
  std::io::stdin().read_line(&mut x)?;
  
  let n: usize = n.trim().parse()?;
  let x: Vec<u8> = x.trim().as_bytes().to_vec();
  let popcount: usize = x.iter().filter(|&b| *b == b'1').count();

  let (mod1, score1, dp1) = prepare(n, popcount + 1, &x);
  let (mod2, score2, dp2) = prepare(n, popcount - 1, &x);
  
  for i in 1 ..= n {
    if x[i - 1] == b'0' {
      let z = (score1 + dp1[n - i]) % mod1;
      println!("{}", f(z)+ 1);
    } else if popcount == 1 {
      println!("{}", 0);
    } else {
      let z = (score2 - dp2[n - i] + mod2) % mod2;
      println!("{}", f(z) + 1);
    }
  }
  
  Ok(())
}


fn f(mut n:i32) -> usize {
  for i in 0 .. 100 {
    if n == 0 {
      return i;
    } else {
      let z = n.count_ones() as i32;
      n %= z
    }
  }
  unreachable!();
}

fn prepare(n: usize, m: usize, x: &Vec<u8>) -> (i32, i32, Vec<i32>) {
  let m = m as i32;
  let mut score = 0;
  let mut dp = vec![1; n];

  if m == 0 {
    return (m, score, dp);
  }
  
  for i in 1 .. n {
    dp[i] = (dp[i - 1] * 2) % m;
  }
  
  for i in 1 ..= n {
    if x[i - 1] == b'1' {
      score = (score + dp[n - i]) % m;
    }
  }
  (m, score, dp)
}


Measured memory_bytes: 4080