akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		long sum = 0;
		for(int i=0;i<n;i++) {
			sum += sc.nextLong();
		}
		System.out.println(sum/n);
	}

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

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

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

int main(){
	int n,A,ans=0;
	vector<int> a;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>A;
		a.push_back(A);
	}
	for(int i=0;i<n;i++){
		int minj=i;
		for(int j=i;j<n;j++) if(a[j]<a[minj]) minj=j;
		if(a[i]!=a[minj]){
			A=a[i];
			a[i]=a[minj];
			a[minj]=A;
			ans++;
		}
	}
	for(int i=0;i<n;i++){
		if(i==n-1) cout<<a[i]<<endl<<ans<<endl;
		else cout<<a[i]<<" ";
	}
	return 0;
}



Measured memory_bytes: 3136
#include <bits/stdc++.h>
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;
  

int main(){
    int n, i;
    long key;
    char com[20];
    scanf("%d", &n);

    list<long> num_array;
    for ( i = 0; i < n; i++ ){
        scanf("%s%ld", com, &key);
        if ( com[0] == 'i' ){
            num_array.push_front(key);
        }else if ( com[0] == 'd' ) {
            if (strlen(com) > 6){
	        if ( com[6] == 'F' ) num_array.pop_front();
	        else if ( com[6] == 'L' ) num_array.pop_back();
            }else{
                auto itr = find(num_array.begin(),num_array.end(),key);
                if (itr != num_array.end()) num_array.erase(itr);
            }
        }
    }

    auto itr = num_array.begin();
    int size = (int)num_array.size();
    for(int i = 0; i < size;i++){
        cout << *itr;
        if(i < size-1) cout << " ";
        itr++;
    }
    cout << "\n";
  return 0;
}


Measured memory_bytes: 34400
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {
	    String[] lines = Io.read();

	    int[] parsed = parse(lines);

	    int a = parsed[0];
	    int e = parsed[4];
	    int k = parsed[5];

	    if (e - a > k) {
	        Io.write(":(");
        } else {
	        Io.write("Yay!");
        }
    }

    private static int[] parse(String[] lines) {
        int[] parsed = new int[lines.length];

        for (int i = 0; i < lines.length; i++) {
            parsed[i] = Integer.parseInt((lines[i]));
        }

        return parsed;
    }
}

class Io {

    /**
     * 標準入力から1行ずつ受け取る
     * @return
     * @throws IOException
     */
    public static String[] read() throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> inputs = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null) {
            if (line.equals(""))
                break;

            inputs.add(line);
        }
        br.close();
        return inputs.toArray(new String[0]);
    }

    /**
     * 標準出力
     * @param answer
     */
    public static void write(String answer)
    {
        System.out.println(answer);
    }
}


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

int main(){
  int D,N;cin>>D>>N;
  int ans;
  if(D==0) ans=1;
  if(D==1) ans=100;
  if(D==2) ans=10000;
  if(N!=100)cout<<ans*N<<endl;
  else cout<<ans*(N+1)<<endl;
}



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

int main()
{
    int n,m;
    cin>>n>>m;
    if(m == 1)
    {
        cout<<0;
        return 0;
    }
    if(n == 2)
    {
        cout<<m-1<<endl;
        return 0;
    }
    if(n>m){
        cout<<1<<endl;
        return 0;}
        if(m%(n-1)>1)
        {
            cout<<m/(n-1)+1;
        }
        else
        {
            cout<<m/(n-1);
        }


}

Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <complex>

int main(){
  long long int N, K, tmp;
  std::vector<long long int> p;

  scanf("%lld%lld", &N, &K);
  for(long long int i = 0; i < N; i++){
    scanf("%lld", &tmp);
    p.push_back(tmp);
  }

  long long int psum_max = 0, psum_tmp = 0;
  for(long long int i = 0; i < K; i++){
    psum_tmp += p[i];
  }
  psum_max = psum_tmp;

  for(long long int i = 1; i < N-K+1; i++){
    psum_tmp = psum_tmp - p[i-1] + p[i+K-1];
    psum_max = std::max(psum_tmp, psum_max);
  }

  std::cerr << "Answer: " << std::endl;
  std::cout << std::setprecision(15) << (psum_max+K)/2.0 << std::endl;

  return 0;
}


Measured memory_bytes: 2420
#include<iostream>

char *chr, *peo;
int n,m;

void sitA(int i){
	for(int k=0; k<n; k++){
		if(chr[k] == '#'){
			chr[k] = 'A';
			return;
		}
	}
}

void sitB(int i){
	if(chr[n-1] == '#' && chr[n-2] != 'A'){
		chr[n-1] = 'B';
		return;
	}
	for(int k=n-2; k>0; k--){
		if(chr[k] == '#' && chr[k-1] != 'A' && chr[k+1] != 'A'){
			chr[k] = 'B';
			return;
		}
	}
	for(int k=0; k<n; k++){
		if(chr[k] == '#'){
			chr[k] = 'B';
			return;
		}
	}
}

void sitC(int i){
	if(i==0){
		if(n%2 == 0)
			chr[n/2] = 'C';
		else
			chr[(n-1)/2] = 'C';
		return;
	}
	for(int k=0; k<n; k++){
		if(chr[k] == '#')
			continue;
		if(k<n-1){
			if(chr[k+1] == '#'){
				chr[k+1] = 'C';
				return;
			}
		}
		if(k>0){
			if(chr[k-1] == '#'){
				chr[k-1] = 'C';
				return;
			}
		}
	}
}

void sitD(int i){
	if(i==0){
		chr[0] = 'D';
		return;
	}
	int ans,tmp=0,tmp1,tmp2;
	for(int k=0; k<n; k++){
		if(chr[k] != '#')
			continue;
		tmp1=0;
		tmp2=0;
		for(int t=k; t<n; t++){
			if(chr[t] != '#')
				break;
			tmp1++;
			if(t == n-1)
				tmp1 = n+1;
		}
		if(k == n-1)
			tmp1 = n+1;
		for(int t=k; t>=0; t--){
			if(chr[t] != '#')
				break;
			tmp2++;
			if(t == 0)
				tmp2 = n+1;
		}
		if(k == 0)
			tmp2 = n+1;
		if(tmp1 > tmp2)
			tmp1 = tmp2;
		if(tmp1 > tmp){
			tmp = tmp1;
			ans = k;
		}
	}
	chr[ans] = 'D';
}

void solve(){
	char tmp;
	for(int i=0; i<m; i++){
		tmp = peo[i];
		switch(tmp){
		case 'a':
		case 'A':
			sitA(i);
			break;
		case 'b':
		case 'B':
			sitB(i);
			break;
		case 'c':
		case 'C':
			sitC(i);
			break;
		case 'd':
		case 'D':
			sitD(i);
			break;
		}
	}
	std::cout << chr << std::endl;
}

int main(){
	while(true){
		std::cin >> n >> m;
		if(!n && !m)
			return 0;
		chr = new char[n+1];
		peo = new char[m];
		for(int i=0; i<n; i++){
			chr[i] = '#';
			if(i<m)
				std::cin >> peo[i];
		}
		chr[n] = '\0';
		solve();
		delete[] chr;
		delete[] peo;
	}
}

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

using namespace std;

const int MAXN = 1e5 + 10;

int a[MAXN], b[MAXN];

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		a[i] = 1, b[i] = 0;
	}
	b[1] = 1;
	for(int i = 1; i <= m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		a[x]--, a[y]++;
		b[y] |= b[x];
		if (a[x] == 0)
			b[x] = 0;
		/*
		if (a[x] == 1){
			a[x] = 0;
			if (b[x] == 0){
				if (b[y] == 1)
					b[y] = 2;
				else if (b[y] == 0)
					b[y] = 0;
				else
					b[y] = 2;
				a[y]++;
			}
			else{
				if (b[y] == 1)
					b[y] = 1;
				else if (b[y] == 2)
					b[y] = 2;
				else{
					if (a[y] == 0)
						b[y] = 1;
					else
						b[y] = 2;
				}
				a[y]++;
			}
			b[x] = 0;
		}
		else{
			if (b[x] == 0){
				a[y]++;
				if (b[y] != 0)
					b[y] = 2;
			}
			else if (b[x] == 1){
				
			}
		}*/
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++)
		if (a[i] && b[i])
			cnt++;
	cout<<cnt<<endl;
	return 0;		
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

//ここから書き始める
int main(int argc, char const *argv[])
{
    int N,C;
    scanf("%d %d", &N, &C);
    int D[C][C];
    int x[N][N];
    REP(i,C)
    {
        REP(j,C)
        {
            // D[i][j]はiからjに色を変えたときの違和感
            int tmp;
            scanf("%d", &tmp);
            D[i][j] = tmp;
        }
    }

    REP(i,N)
    {
        REP(j,N)
        {
            int tmp;
            scanf("%d", &tmp);
            x[i][j] = tmp - 1;
        }
    }

    LL min_score = LINF;

    LL costmemo[3][C];
    REP(i,3)
    {
        REP(j,C)
        {
            costmemo[i][j] = 0;
        }
    }


    REP(i,C)
    {
        REP(l,N)
        {
            REP(m,N)
            {
                if((l+m)%3 == 0) costmemo[0][i]+= D[x[l][m]][i];
                if((l+m)%3 == 1) costmemo[1][i]+= D[x[l][m]][i];
                if((l+m)%3 == 2) costmemo[2][i]+= D[x[l][m]][i];
            }
        }
    }


    REP(i,C)
    {
        REP(j,C)
        {
            if(j == i) continue;
            REP(k,C)
            {
                if(k == i || k == j) continue;
                LL score = 0;

                score = costmemo[0][i] + costmemo[1][j] + costmemo[2][k];

                if(score < min_score) min_score = score;

            }
        }
    }
    cout << min_score << endl;

}


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

int main(void) {
    int a, b;
    cin >> a >> b;
    a = a == 1 ? 14 : a;
    b = b == 1 ? 14 : b;
    if(a > b) {
        cout << "Alice" << endl;
    }
    else if(a < b) { 
        cout << "Bob" << endl;
    }
    else {
        cout << "Draw" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b){
    ll r;
    while(a%b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return b;
}
int main(){
    ll K;
    ll i,j,k;
    ll ans=0;
    cin >> K;
    for(i=1;i<=K;i++){
        for(j=1;j<=K;j++){
            for(k=1;k<=K;k++){
                 ans+=gcd(i,gcd(j,k));
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3188
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

int ver,edge,ans=0; 
vi g[55]; 
int deg[55]; 
stack <int> s;

signed main()
{
    cin >> ver >> edge ; 
    for (int i=1;i<=edge;i++){
        int u,v; cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    } 
    for (int i=1;i<=ver;i++){
        deg[i] = sz(g[i]);
        if (deg[i]==1) s.push(i);
    }
    while (s.size()){
        int x=s.top();
        s.pop();
        if (deg[x]==1) ans++;
        deg[x] = 0; 
        for (auto &it: g[x]){
            if (deg[it]>0){
                deg[it]--;
                if (deg[it]==1){
                    s.push(it);
                }
            }
        }
    }
    cout << min(edge,ans) << endl;
    return 0;
}


Measured memory_bytes: 3608
from operator import sub
s = list(map(int,input()))
l0 = [0] * len(s)
l1 = [0] * len(s)
for i in range(len(s)):
    if (i & 1) == 1: l0[i] += 1
    else: l1[i] += 1
c0 = list(map(sub,s,l0))
c1 = list(map(sub,s,l1))
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if c0[i] == 0: pass
    else: cnt0 += 1
    if c1[i] == 0: pass
    else: cnt1 += 1
print(min(cnt0,cnt1))

Measured memory_bytes: 56028
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

using ll = long long;
using ull = unsigned long long;

ll n, m;
ll a[100000];
ll b[100001];

bool is_ok(ll x) {
    ll cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += n - (lower_bound(a, a + n, x - a[i]) - a);
    }
    if (cnt >= m)
        return true;
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a, a + n);
    ll l = 0, r = 200000, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        if (is_ok(mid)) { // m以上ある→midが小さすぎる
            l = mid + 1;
        }
        else { // m以上ない→midが大きすぎる
            r = mid - 1;
        }
    }
    // l-1がm以上存在できる最小の境界
    // (l-1+1=l)がm以下になる
    // 残りは丁度l-1の数
    
    for (int i = 1; i <= n; ++i) {
        b[i] += b[i - 1] + a[i - 1];
    }
    ll cnt = 0, sum = 0;
    for (int i = 0; i < n; ++i) {
        int s = lower_bound(a, a + n, l - a[i]) - a;
        cnt += n - s;
        sum += b[n] - b[s] + (n - s) * a[i];
    }
    if (m > cnt) {
        sum += (m - cnt) * (l - 1);
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int a[2][N];
for(int i=0;i<2;i++){
  for(int j=0;j<N;j++){
    cin>>a[i][j];
  }
}
int res;
int temp;
int s=a[0][0];
for(int j=0;j<N;j++)s+=a[1][j];
res=temp=s;
for(int j=0;j<N-1;j++){
temp+=a[0][j+1]-a[1][j];
res=max(res,temp);
}
cout<<res;
return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define SIZE 100001

int main(){
  int x[3];
  scanf("%d", &x[0]);
  scanf("%d", &x[1]);
  scanf("%d", &x[2]);

  //  int x[SIZE];
  while(1){
    int flag = 1;
    for(int i=1; i<3; i++){
      if(x[i-1]<x[i]){
	int tmp = x[i-1];
	x[i-1] = x[i];
	x[i] = tmp;
	flag = 0;
      }
    }
    if(flag) break;
  }

  int ans = x[0]*10+x[1]+x[2];
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define P pair<ll, ll>
#define VI vector<ll>
#define int long long
using namespace std;

string S;
int w;

void solve() {
  for (int i = 0; i < S.size(); i++) {
    if (i % w == 0) {
      cout << S[i];
    }
  }
  cout << endl;
}

signed main() {
  cin >> S;
  cin >> w;

  solve();
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)
const ll mod = 1000000007;
const double pi = 3.14159265358979;

int main() {
    ll H, W;
    cin >> H >> W;
    vector<vector<str>> S(H, vector<str>(W));
    rep(i, H) {
        rep(j, W) {
            cin >> S.at(i).at(j);
        }
    }
    str al ="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    rep(i, H) {
        rep(j, W) {
            if (S.at(i).at(j) == "snuke") {
                cout << al[j] << i + 1 << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int A[25] , B[25] , C[25];

int main(){
    int N , i , Ans = 0;
    scanf( "%d" , &N );

    for( i = 1 ; i <= N ; ++i )
        scanf( "%d" , A + i );
    for( i = 1 ; i <= N ; ++i )
        scanf( "%d" , B + i );
    for( i = 1 ; i < N ; ++i )
        scanf( "%d" , C + i );

    Ans  += B[A[1]];

    for( i = 2 ; i <= N ; ++i ){
        Ans += B[A[i]];
        if( A[i] == A[i - 1] + 1 ) Ans += C[A[i - 1]];  
    }

    printf( "%d\n" , Ans );
    return 0;
}

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

int main() {
    long long N, A, B; cin >> N >> A >> B;
    long long ans;
    if (A > B) ans = 0;
    else if (N == 1) {
        if (A == B) ans = 1;
        else ans = 0;
    }
    else ans = (N - 2) * (B - A) + 1;
    cout << ans << endl;
}

Measured memory_bytes: 256
from collections import Counter

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

dic = Counter(a)

l = []
for i, j in dic.items():
    if j >= 4:
        l.append(i)
        l.append(i)
    elif j >= 2:
        l.append(i)

if len(l) < 2:
    print(0)
else:
    l.sort()
    print(l[-1] * l[-2])

Measured memory_bytes: 101484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

int N;
vector<int> A(100010, 0);

int main(void){
    
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    
    vector<int> sum(N + 3, 0);
    int current = 0;
    for(int i = 1; i <= N; ++i){
        sum[i] = sum[i - 1] + abs(current - A[i]);
        current = A[i];
    }
    sum[N + 1] = sum[N] + abs(current - 0);
    
    for(int i = 1; i <= N; ++i){
        int num = abs(A[i - 1] - A[i + 1]);
        printf("%d\n", sum[N + 1] - (sum[i + 1] - sum[i - 1]) + num);
    }
    
    return 0;
}

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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); return os;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    cout << (n >= 30 ? "Yes\n" : "No\n");
    return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;

using namespace std;

int main()
{
  ll H, W;
  cin >> H >> W;
  vector<vector<ll>> as(H, vector<ll>(W));
  vector<string> res;
  for (auto i = 0; i < H; i++) {
    for (auto j = 0; j < W; j++) {
      cin >> as[i][j];
    }
  }
  for (auto i = 0; i < H; i++) {
    for (auto j = 1; j < W; j++) {
      if (as[i][j-1] % 2 == 1) {
        as[i][j]++;
        ostringstream os;

        os << i+1 << " " << j << " " << i+1 << " " << j+1;
        res.push_back(os.str());
      }
    }
  }

  for(auto i = 1; i < H; i++) {
    if (as[i-1][W-1] % 2 == 1) {
      as[i][W-1]++;
      ostringstream os;
      os << i << " " << W << " " << i+1 << " " << W;
      res.push_back(os.str());
    }
  }

  cout << res.size() << endl;
  for (auto s : res) {
    cout << s << endl;
  }

  return 0;
}


Measured memory_bytes: 12916
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse

// Nの桁数
int calc_digit(long long N) {
    int res = 0;
    while (N) {
        ++res;
        N /= 10;
    }
    return res;
}

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
    return a / GCD(a, b) * b;
}

// ax + by = gcd(a, b) となるような (x, y) を求める
// 多くの場合 a と b は互いに素として ax + by = 1 となる (x, y) を求める
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    // 再帰的に解く (x, y を入れ替えておく)
    long long d = extGCD(b, a % b, y, x); 
    y -= a / b * x;
    return d;
}


vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

const int MAX = 1000010;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// int main() {
//     // 前処理
//     COMinit();

//     // 計算例
//     cout << COM(100000, 50000) << endl;
// }

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

    COMinit();

    const auto &pf = prime_factorize(m);

    ll ans = 1;

    for (auto p : pf) {
        ans*=COM(n-1+p.second,p.second);
        ans%=MOD;
    }

    cout<<ans<<endl;

}

Measured memory_bytes: 23680
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> children;
vector<int> X;
int f(int v) {
	if (children[v].empty()) return 0;
	vector<pair<int,int>> a;
	int N = X[v];
	vector<int> dp(N+1, 1<<30);
	dp[0] = 0;
	for (int x : children[v]) {
		int a = X[x];
		int b = f(x);
		if (b < 0) return -1;
		vector<int> dp2(N+1, 1<<30);
		for (int i = 0; i+a <= N; ++ i) dp2[i+a] = min(dp2[i+a], dp[i]+b);
		for (int i = 0; i+b <= N; ++ i) dp2[i+b] = min(dp2[i+b], dp[i]+a);
		dp.swap(dp2);
	}
	auto r = *min_element(dp.begin(), dp.end());
	if (r == 1<<30) return -1;
	return r;
}
int main() {
	int N;
	cin >> N;
	children.resize(N+1);
	X.resize(N+1);
	for (int i = 2; i <= N; ++ i) {
		int x;
		cin >> x;
		children[x].push_back(i);
	}
	for (int i = 1; i <= N; ++ i) cin >> X[i];
	int r = f(1);
	if (r < 0) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		cout << "POSSIBLE" << endl;
	}
}


Measured memory_bytes: 5752
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int n;
    cin >> n;
    int f[n][10];
    int p[n][11];
    rep(i, n) rep(j, 10) {
        cin >> f[i][j];
    }
    rep(i, n) rep(j, 11) {
        cin >> p[i][j];
    }
    int ans = -INF;
    rep(i, 1<<10) {
        if (i==0) continue;
        int score = 0;
        vint cnt(n, 0);
        rep(j, n) {
            rep(k, 10) {
                if (i>>k&f[j][k]) cnt[j]++;
            }
        }
        rep(k, n) {
            score += p[k][cnt[k]];
        }
        ans = max(ans, score);
    }

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

Measured memory_bytes: 256
/*
	Copyright: razouq (c)
	Author: Anass BENDARSI
	Date: 28-Mar-20 11:05:24 PM
	flamers will **** you
*/
//#include<flamers.h>

#include "bits/stdc++.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define PB push_back
#define POB pop_back

using namespace std;

int main(){
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	string str;
	cin>>str;
	if(str[2] == str[3] && str[4] == str[5]) {
		cout<<"Yes"<<endl;
	} else {
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        var count = 0;
        while (true)
        {
            for (int i = 0; i < n; i++)
                if (a[i] % 2 == 0) a[i] /= 2;
                else goto end;
            count++;
        }
        end:;
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 13140
N, K = map(int, input().split())
t = 0
i = 1
while(i < K):
    t += 1
    i *= 2
under = 2**t

p = 0
for i in range(1, N+1):
    c = 0
    while(i < K):
        c += 1
        i *= 2
    p += 2**(t-c)
print(p/((2**t)*N))

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

int main(void){
    long long N;cin>>N;
    long long A,B,C;A=2;B=1;C=1;
    for(long long i=0;i<N-1;i++){
        C=A+B;
        A=B;
        B=C;
    }
    cout<<C<<endl;
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    int res = 0;
    rep(i, n) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    for (int i=0; i<n-2; i++) {
        for (int j=i+1; j<n-1; j++) {
            for (int k=j+1; k<n; k++) {
                if (a[i]+a[j] > a[k] && a[i] != a[j] && a[j] != a[k]) {
                    res++;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3564
import operator
def makecode(n):
	m = n
	s = str(n)
	while m < 100000:
		s = '0' + s
		m = m * 10
	return s
N, M = map(int, raw_input().split())
data = []
serial = []
for i in range(0, N):
	data.append([])
for i in range(0, M):
	P, Y = map(int, raw_input().split())
	data[P-1].append([i+1, Y])
for i in range(0, N):
	data[i].sort(key=operator.itemgetter(1))
for i in range(0, N):
	for j in range(0, len(data[i])):
		s = makecode(i+1) + makecode(j+1)
		serial.append([data[i][j][0], s])
serial.sort(key=operator.itemgetter(0))
for i in range(0, M):
	print serial[i][1]

Measured memory_bytes: 53532
#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)
#define LL long long

const int MAXSSTN = 100010;
class StarrySkyTree{
public:
  int size=0;
  int depth=0; // the depth of the tree
  int best=0;  // the index of maximum element
  int start=0; // the initial index of inputs
  long long dat_add[4 * MAXSSTN];
  long long dat[4 * MAXSSTN];
  
  StarrySkyTree(int n,long long* v){
    size=n;
    while((1<<depth)<n)depth++;
    start=(1<<depth)-1;
    for(int i=start;i<(1<<(depth+1));i++){
      if(i<start+n)
	dat[i]=v[i-start];
      else
	dat[i]=1e15;
    }
    for(int i=start;i<start+n;i++){
      int tmp=i;
      while(par(tmp)!=-1){
	dat[par(tmp)]=min(dat[tmp],dat[(tmp+1)/2*4-1-tmp]);
	tmp=par(tmp);
      }
    }
    int i=0;
    while(i<start)i=(dat[i]==dat[2*i+1])?2*i+1:2*i+2;
    best=i-start;
  }
  long long max_element(int a, int b){ return max_element(a, b, 0, 0, (1<<depth)); }
  void add(int s, int t, int x){ add(s, t, 0, 0, (1<<depth), x); }
  void add(int i, int x){ add(i, i + 1, 0, 0, (1<<depth), x); }

  int par(int i){
    if(i==0)
      return -1;
    return (i-1)/2;
  }

  void update(int d,long long x){
    int i=d+start;
    dat[i]=x;
    while(par(i)!=-1){
      dat[par(i)]=min(dat[i],dat[(i+1)/2*4-1-i]);
      i=par(i);
    }
    i=0;
    while(i<start){
      i=(dat[i]==dat[2*i+1])?2*i+1:2*i+2;
    }
    best=i-start;
  }
  void dump(){
    for(int i=0;i<(1<<(depth+1));i++){
      cerr<<dat[i]<<" ";
    }
    cerr<<endl;
  }
private:
  long long max_element(int a, int b, int k, int l, int r){
    if(b <= l || r <= a) return 1e15;
    if(a <= l && r <= b) return dat[k] + dat_add[k];

    long long vl = max_element(a, b, k * 2+1, l, (l + r) / 2);
    long long vr = max_element(a, b, k * 2+2, (l + r) / 2, r);
    return min(vl, vr) + dat_add[k];
  }
  void add(int a, int b, int k, int l, int r, long long x){
    if(b <= l || r <= a) return;
    if(a <= l && r <= b){
      dat_add[k] += x;
    }else{
      add(a, b, k * 2+1, l, (l + r) / 2, x);
      add(a, b, k * 2+2, (l + r) / 2, r, x);
      dat[k] = min(dat[k * 2+1] + dat_add[k * 2+1], dat[k * 2 + 2] + dat_add[k * 2 + 2]);
    }
  }
};

int n,q;
LL a[100000];

int main(){
  cin>>n>>q;
  REP(i,n)
    a[i]=(1LL<<31)-1;
  StarrySkyTree sst(n,a);
  int tmp;
  LL x,y;
  REP(i,q){
    cin>>tmp>>x>>y;
    if(tmp)cout<<sst.max_element((int)x,(int)y+1)<<endl;
    else sst.update((int)x,y);
  }
  return 0;
}



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

int main(){

 int a, b;
 cin >> a >> b;
  
 int amari = (a * b) % 2;
   
 if(amari == 1){
  cout << "Odd" << endl;
 }
  
 else{
  cout << "Even" << endl;
 }
  
}

Measured memory_bytes: 3592
from typing import List
import sys
import math


def distance(x: int, y: int):
    return math.sqrt(pow(x, 2) + pow(y, 2))


def solution(inp: List) -> int:
    ans: int = 0
    D: int = int(inp[1])
    for i in range(2, len(inp), 2):
        dis = distance(int(inp[i]), int(inp[i + 1]))
        if dis <= D:
            ans += 1
    return ans


inp: List = []
for j in sys.stdin:
    inp += j.split()

print(solution(inp))


Measured memory_bytes: 38572
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define rep(i, s, g) for (i = s; i < g; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1e9 + 7;

int main(void)
{
    string n;
    static int dp[1000010][2];

    cin >> n;

    dp[0][1] = 1;

    for (int i = 0; i < n.size(); i++)
    {
        int d = n[i] - '0';

        dp[i + 1][0] = min(dp[i][0] + d, dp[i][1] + 10 - d);
        dp[i + 1][1] = min(dp[i][0] + d + 1, dp[i][1] + 10 - d - 1);
    }

    cout << dp[n.size()][0] << endl;
}

Measured memory_bytes: 9220
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef vector<ll> vl;
typedef pair<vl,vl> t;

int n;
ll a[505],k,sum;

int main(){
	cin >> n >> k;
	rep(i,n) {cin >> a[i]; sum+=a[i];}
	vector<ll>vec;
	for(ll i=1;i*i<=sum;i++){
		if(sum%i != 0) continue;
		vec.pb(i); vec.pb(sum/i);
	}
	SORT(vec); ERASE(vec);
	reverse(vec.begin(),vec.end());
	rep(i,vec.size()){
		ll v = vec[i];
		vector<ll>rem;
		ll S = 0;
		rep(i,n){
			rem.pb(a[i]%v);
			S += a[i]%v;
		}
		SORT(rem);
		ll need = 0;
		rep(i,n-S/v) need += rem[i];
		rep(i,S/v) need += v-rem[n-1-i];
		if(need/2 <= k){
			cout << v << endl;
			return 0;
		}
	}
	assert(0);
}

Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <stack>
#include <cstring>

using namespace std;

int main(){
	int n;
	pair<double,double> input[4];
	double kata1,kata2;
	cin >> n;
	while(n--){
		for(int i = 0; i < 4; i++){
			cin >> input[i].first >> input[i].second;
		}

		kata1 = (input[1].second - input[0].second) / (input[1].first - input[0].first);
		kata2 = (input[3].second - input[2].second) / (input[3].first - input[2].first);

		if(kata1 == kata2){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}

	}
	return 0;
}

Measured memory_bytes: 1224
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _2199 {
    class Program {
        static void Main(string[] args) {
            int yNum = 256;
            int MAX_VAL = int.MaxValue/10;
            while(true) {
                var nm = Console.In.ReadLine().Split(' ').Select(int.Parse).ToArray();
                var n = nm[0];
                var m = nm[1];
                if(n == 0 && m == 0) { break; }
                var c = new List<int>();
                var x = new List<int>();
                x.Add(128);
                for(int i = 0; i < m; i++) {
                    c.Add(int.Parse(Console.In.ReadLine()));
                }
                for(int i = 0; i < n; i++) {
                    x.Add(int.Parse(Console.In.ReadLine()));
                }
                //var values = new int[n + 1, yNum];
                var values = new int[2][];
                for(int i=0; i<values.Length; ++i) { values[i] = new int[yNum]; }
                for(int i = 0; i < 2; i++) {
                    for(int j = 0; j < yNum; j++) {
                        values[i][j] = MAX_VAL;
                    }
                }
                values[0][128] = 0;
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < yNum; j++) {
                        for(int k = 0; k < m; k++) {
                            if((0 <= j + c[k]) && (j + c[k] <= 255)) {
                                values[1][j + c[k]] = Math.Min(values[1][j + c[k]], values[0][j] + (j + c[k] - x[i+1]) * (j + c[k] - x[i+1]));
                            }
                            else if(0 > j + c[k]) {
                                values[1][0] = Math.Min(values[1][0], values[0][j] + (0 - x[i+1]) * (0 - x[i+1]));
                            }
                            else {
                                values[1][255] = Math.Min(values[1][255], values[0][j] + (255 - x[i+1]) * (255 - x[i+1]));
                            }
                        }
                    }
                    for(int j=0; j<yNum; j++) {
                        values[0][j] = values[1][j];
                        values[1][j] = MAX_VAL;
                    }
                }
                Console.Out.WriteLine(values[0].Min());
            }
        }
    }
}

Measured memory_bytes: 6420
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 1000000007;
const int N = 200010;
ll fact[N], invf[N];

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    x %= mod;
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

ll divll(ll x, ll y){
    x %= mod;
    return (x * powll(y,mod-2)) % mod;
}

ll nPr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(fact[n], invf[n-r]);
}

ll nCr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(mul(fact[n], invf[r]), invf[n-r]);
}

void init_f(){
    fact[0] = 1;
    FOR(i,1,N-1){
        fact[i] = (fact[i-1] * i) % mod;
    }
    invf[N-1] = divll(1, fact[N-1]);
    FORR(i,N-1,1){
        invf[i-1] = (invf[i] * i) % mod;
    }
}

int main(void){
    ll n, k;
    cin >> n >> k;
    VL cnt(k + 1);
    FORR(d,k,1){
        ll c = k / d;
        ll all = powll(c, n);
        for (ll e = 2 * d; e <= k; e += d){
            all = (all + mod - cnt[e]) % mod;
        }
        cnt[d] = all;
    }
    ll ans = 0;
    FOR(d,1,k) ans = (ans + cnt[d] * d) % mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4052
#include <stdio.h>

int main(){
    int i, j, k, n, c, x;
	
	scanf("%d %d", &n, &x);
	while(!(n == 0 && x == 0)){
		c = 0;
    	for(i = 1; i <= n - 2; i++){
	    	for(j = i + 1; j <= n - 1; j++){
		    	for(k = j + 1; k <= n; k++){
					if(x == i + j + k){
						c++;
					}
		       	}   
		    }
	   	}
		printf("%d\n", c);
		scanf("%d %d", &n, &x);
	}
	
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
template <typename T > void read(T &t) {
	char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	t=0;
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9');
}
typedef long long ll;
const ll INF=1LL<<50;
const int mx=3000;
int n,sz;
map<ll,int> M;
map<ll,int> cnt;
ll ans;
bool ip[3010];
vector<int> p;
void init() {
	memset(ip,1,sizeof(ip));
	ip[0]=ip[1]=0;
	for (int i=2;i<=mx;i++)
		if (ip[i]) {
			p.push_back(i);
			for (int j=i*i;j<=mx;j+=i)
				ip[j]=0;
		}
	sz=p.size();
}
ll solve(ll x) {
	for (ll i=0;i<sz;i++) {
		ll t=p[i]*p[i]*p[i];
		if (t>x) break;
		while (x%t==0) x/=t;
	}
	return x;
}
ll S(ll x) {
	return (ll)floor(sqrt(x));
	ll l=1,r=100000;
	while (l<r) {
		ll mid=(l+r+1)>>1;
		if (mid*mid<=x) l=mid;
		else r=mid-1;
	}
	return l;
}
ll T(ll x) {
	ll A=1,B=1;
	for (ll i=0;i<sz;i++) {
		if (p[i]*p[i]*p[i]>x) break;
		int ss=0;
		while (x%p[i]==0) {
			x/=p[i]; ss++;
		}
		if (ss==1) A*=p[i]; else if (ss==2) B*=p[i];
	}
	ll tmp=S(x);
	if (tmp*tmp==x) B*=tmp;
	else A*=x;
	ll res=A*B;
	if (res>INF/A+1) res=INF; else res*=A;
	return res;
}

int main() {
	//freopen("2.txt","r",stdin);
	init();
	read(n);
	for (int i=1;i<=n;i++) {
		ll x; read(x);
		x=solve(x);
		//printf("%lld\n",x);
		M[x]++;
	}
	ans=0;
	for (map<ll,int>::iterator it=M.begin();it!=M.end();it++) {
		ll x=it->first;
		if (cnt[x]) continue;
		ll t=T(x);
		if (x!=t) ans+=max(it->second,M[t]);
		else ans++;
		cnt[t]++;
	}
	printf("%lld\n",ans);
	return 0;
}
 

Measured memory_bytes: 20864
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

namespace mp = boost::multiprecision;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 100005;
int N;
int A[MAX_N][3];

int dp[MAX_N][3];

signed main()
{
  cin >> N;
  REP(n,N) {
    cin >> A[n][0] >> A[n][1] >> A[n][2];
  }

  REP(n,N) {
    REP(j,3) {
      REP(k,3) {
        if(j==k) {
          continue;
        }
        dp[n+1][k] = max(dp[n+1][k], dp[n][j] + A[n][k]);
      }
    }
  }

  cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << endl;

  return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#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++)
typedef int64_t llong;
char moji[26]={'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'};
char moji2[26]={'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'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define ld PRId64
#define H_max 100
#define W_max 100

int main(){
    int h,w,n;
    int A[H_max][W_max];
    cin >> h >> w >> n;
    int color,tmp_h=0,tmp_w=0,cnt;
    REP(i,n){
        cnt=0;
        scanf("%d",&color);
        while(1){
            if(tmp_w==w){
                tmp_w=w-1;
                tmp_h+=1;
            }
            if(tmp_w==-1){
                tmp_w=0;
                tmp_h+=1;
            }
            if(tmp_h%2==0){
                A[tmp_h][tmp_w]=i+1;
                cnt+=1;
                tmp_w+=1;
                if(cnt == color) break;
            }
            else{
                A[tmp_h][tmp_w]=i+1;
                cnt+=1;
                tmp_w-=1;
                if(cnt == color) break;
            }   
        }

    }
    REP(i,h){
        REP(j,w) printf("%d ",A[i][j]);
        printf("\n");
    }
}



Measured memory_bytes: 384
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    ll x,i=1; cin>>x;
    while(1){
        if(i*(i+1)/2>=x) break;
        i++;
    }
    cout<<i<<endl;
}

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

int main(){
  vector<vector<int>> a(3,vector<int>(3));
  vector<vector<int>> cnt(3,vector<int>(3));
  rep(i,3)rep(j,3)cin >> cnt[i][j];
  int n;
  cin >> n;
  vector<int> b(n);
  rep(i,n){
    cin >> b[i];
    rep(j,3){
      rep(k,3){
        if(b[i]==cnt[j][k])a[j][k]++;
      }
    }
  }
  bool ans = false;
  rep(i,3){
    if(a[i][0]>0&&a[i][1]>0&&a[i][2]>0)ans=true;
    if(a[0][i]>0&&a[1][i]>0&&a[2][i]>0)ans=true;
  }
  if(a[0][0]>0&&a[1][1]>0&&a[2][2]>0)ans=true;
  if(a[0][2]>0&&a[1][1]>0&&a[2][0]>0)ans=true;

  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug if(true)
typedef long long ll;
typedef vector<int> vi;
typedef pair<uint64,uint64> ii;
typedef vector<ii> vii;

uint64 a[301];

uint64 firstPile;

ii findAB(ll sum, ll sor) {
	if(sum < sor){
		printf("-1\n");
		exit(0);
	}
    ll A = (sum - sor + 1)/2LL;
  
    ll a = 0, b = 0;
    // printf("sum: %lld sor: %lld\n",sum, sor);

    for(int i=50;i>=0;i--){
    	uint64 Xi = (sor & (1LL << i)); 
        uint64 Ai = (A & (1LL << i));
    	if(Xi == 0 && Ai > 0) {
        	a = ((1LL << i) | a);
        	b = ((1LL << i) | b);
        	// printf("a jadi: %lld\n", a);
        }
    }

    for(int i=50;i>=0;i--){
    	uint64 Xi = (sor & (1LL << i)); 
        uint64 Ai = (A & (1LL << i));
    	if(Xi == 0 && Ai == 0){

        }else if(Xi == 0 && Ai > 0) {

        }
        else if (Xi > 0 && Ai == 0) { 
        	if((a | (1LL<<i)) > firstPile) {
        		b = ((1LL << i) | b);
        		continue;
        	}
            a = ((1LL << i) | a);  
            // printf("a disini: %lld firstPile: %lld\n",a, firstPile);
        } else{
        	// printf("sini\n");
        	printf("-1\n");
        	exit(0);
        }
 
    }
  
    return ii(a,b);
} 

int main(){
	int n,i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		cin>>a[i];
		// scanf("%lld",&a[i]);
	}

	uint64 sor = 0;
	for(i=2;i<n;i++){
		sor ^= a[i];
	}
	// printf("sor: %lld\n",sor);

	uint64 sum = a[0] + a[1];
	firstPile = a[0];
	ii ans = findAB(sum, sor);
	uint64 pertama = ans.first, kedua = ans.second;
	if((a[0] ^ a[1]) == sor){
		printf("0\n");
		return 0;
	}
	// cout<<pertama << " "<<kedua<<endl;
	if (pertama == 0 || pertama > a[0]) {
		printf("-1\n");
	}else{
		cout << a[0] - pertama << endl;
	}
	// printf("%lld %lld\n",pertama, kedua);
	// if(pertama <= a[0] && kedua <= a[0]){
	// 	uint64 maks = max(pertama, kedua);
	// 	if(maks == 0){
	// 		printf("-1\n");
	// 	}else{
	// 		cout<<a[0] - maks<<endl;
	// 		// printf("%lld\n",a[0] - maks);	
	// 	}
	// }else if(pertama > a[0] && kedua <= a[0]){
	// 	if(kedua == 0) {
	// 		printf("-1\n");
	// 	}else{
	// 		cout<<a[0] - kedua<<endl;
	// 		// printf("%lld\n",a[0] - kedua);	
	// 	}
		
	// }else if(pertama <= a[0] && kedua > a[0]){
	// 	if(pertama == 0) {
	// 		printf("-1\n");
	// 		return 0;
	// 	}
	// 	cout<<a[0] - pertama<<endl;
	// 	// printf("%lld\n",a[0] - pertama);
	// }else{
	// 	printf("-1\n");
	// }

	// //2 pertama klo dixor harus sor
	// ll temp = 1000000000000LL;
	// ll bil = temp;
	// string ans;
	// while(bil){
	// 	int mod = bil % 2LL;
	// 	bil /= 2LL;
	// 	if(mod & 1){ans += "1";}
	// 	else{ans += "0";}
	// }
	// reverse(ans.begin(), ans.end());
	// cout<<ans<<" "<<ans.length()<<endl;

	return 0;
};

Measured memory_bytes: 3764