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


int main(){
	int n;cin>>n;
	map<string , int > ab;
	while(n--){
		string num;
		cin>>num;
		ab[num]++;
	}
	int kmax = INT_MIN;
	for(auto num:ab){
		kmax = max(kmax,num.second);
	}
	for(auto num:ab){
		if(num.second == kmax){
			cout<<num.first<<endl;
		}
	}
	
	return 0;
}


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

bool isOk(int u, vector<vector<int>>& adj, vector<int>& h) {
  for(int v : adj[u]) {
    if (h[u] <= h[v]) return false;
  }
  return true;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> h(n);
  for(auto& x : h) cin >> x;
  vector<vector<int>> adj(n);
  for(int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int ans = 0;
  for(int i = 0; i < n; i++) {
    ans += isOk(i, adj, h);
  }
  cout << ans << endl;
}

Measured memory_bytes: 8780
#include <iostream>
#include <cstring>
#include <algorithm>

#define MAX_INT  100005
#define MAX_N  100000

using namespace std;


//入力
int K;
int N;
int a[MAX_N + 1];




int main() {

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

  long cumsum[N+1];
  long cumsum_pos[N+1];         // 正の整数だけを考えた累積和配列
  memset(cumsum, 0, sizeof(long));
  memset(cumsum_pos, 0, sizeof(long));
  for(int i = 0; i < N; i++) {
    cumsum[i+1]     = cumsum[i]     + a[i];
    cumsum_pos[i+1] = cumsum_pos[i] + max(0, a[i]);
  }

  long long mx = 0;
  long long other;
  for(int i = 0; i < N - K + 1; i++) {
    // 色を確定される部分
    long long all_black = cumsum[i+K] - cumsum[i];

    // それ以外はすべて正数だけ塗る
    other = cumsum_pos[i] + ( cumsum_pos[N] - cumsum_pos[i+K] );

    mx = max( max(all_black, 0LL) + other, mx );
  }

  cout << mx << "\n";
  return 0;

}


Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;

namespace dfs3
{
	struct Edge
	{
		int to;
		int weight;
		Edge(int t, int w) : to(t), weight(w) {}
	};
	vector<vector<Edge>> graph;
	int colors[100001];
	int N;

	//偶数:0
	//奇数:1
	bool dfs(int v, int color = 0)
	{
		colors[v] = color;
		for (Edge edge : graph[v]) {
			if ((edge.weight % 2) == 0) {
				//同じ色にする
				if (colors[edge.to] == -1) {
					dfs(edge.to, colors[v]);
				}
				else if (colors[edge.to] != colors[v]) {
					return false;
				}
			}
			else {
				//違う色にする
				if (colors[edge.to] == -1) {
					dfs(edge.to, (colors[v] + 1) % 2);
				}
				else if (colors[edge.to] == colors[v]) {
					return false;
				}
			}
		}
		return true;
	}
	void exec()
	{
		int N; cin >> N;
		graph.resize(N);
		for (int i = 0; i < N - 1; ++i) {
			int from, to, weight;
			cin >> from >> to >> weight;
			--from;--to;
			graph[from].push_back(Edge(to, weight));
			graph[to].push_back(Edge(from, weight));
		}
		for (int i = 0; i < N; ++i) {
			memset(colors, -1, sizeof(colors));
			if (dfs(i)) break;
		}
		for (int i = 0; i < N; ++i) {
			
			cout << colors[i] << endl;
		}
	}
}

int main()
{
	//dfs1::exec();

	/*
	vector<int> anss;
	for (;;) {
		dfs2::exec();
		if (dfs2::W == 0 || dfs2::H == 0) break;
		anss.push_back(dfs2::ilands);
	}
	for (int i = 0; i < anss.size(); ++i) {
		cout << anss[i] << endl;
	}
	*/
	dfs3::exec();
	return 0;
}


Measured memory_bytes: 8192
#include <iostream>

int main(){
   std::string S, T;
   std::cin >> S >> T;

   int ans = 0;
   for(int i=0; i<S.size(); ++i){
      if(S[i]!=T[i]) ++ans;
   }
   std::cout << ans << std::endl;
   return 0;
}


Measured memory_bytes: 3824
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int main(){
    string s;
    cin>>s;
    int cnt=0;
    int len = s.length();
    for(int i=0;i<len;i++){
        if(s[i]=='1')
            cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch AXBC | diff AXBC.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address AXBC.cpp && ./a.out

/*

 9/19/2020

 5:04-

 */

int N;

void solve() {
  LL res=0;
  for(LL a=1; a<N; ++a) for(int b=1; a*b<N; ++b) {
    int c=N-a*b;
    res+=(1<=c);
  }
  cout<<res<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;

  cin>>N;
  solve();

  return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10;
long long vis[maxn];
int p[maxn];
long long c[maxn];
long long num[maxn], tot;
void dfs(int x)
{
    if (vis[p[x]])
        return;
    ++tot;
    num[tot] = num[tot - 1] + c[p[x]];
    vis[p[x]] = 1;
    dfs(p[x]);
}
int n, k;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    long long ans = -LLONG_MAX;
    for (int i = 1; i <= n; i++)
    {
        tot = 1;
        memset(vis, 0, sizeof(vis));
        num[1] = c[i];
        vis[i] = 1;
        dfs(i);
        for (int i = 1; i <= min((int)k, (int)tot); i++)
            ans = max(ans, max(0ll, (k - i) / tot * num[tot]) + num[i]);
    }
    cout << ans << endl;
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    ll count = 0;
    string S;
    vector<vector<vector<bool>>> dp;
    cin >> N >> S;
    dp.resize(N + 1, vector<vector<bool>>(4, vector<bool>(1000)));
    dp[0][0][0] = true;
    rep(i, N) rep(j, 4) rep(k, 1000) {
        if(!dp[i][j][k]) continue;
        dp[i + 1][j][k] = true;
        if(j <= 2) dp[i + 1][j + 1][k * 10 + S[i] - '0'] = true;
    }
    rep(i, 1000) {
        if(dp[N][3][i]) count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 23040
#include<stdio.h>
#define N 100000
int linearSearch(int* ,int,int);


int main(){

  int A[N],B[N],num1,num2,i,j,k,cnt=0,x;
  scanf("%d",&num1);

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

  scanf("%d",&num2);

  for(i=0;i<num2;i++){
    scanf("%d",&B[i]);
  }

  for(i=0;i<num2;i++){
    x= linearSearch(&A[0],B[i],num1);

   if(x==1)cnt++;
  }


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

}


int linearSearch(int A[],int key,int num){


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

   
    if (A[i]==key)return 1;
  }
return 0;
}

Measured memory_bytes: 644
#include<stdio.h>

int main(){
  int n, m, i;
  while(1){
    scanf("%d %d", &n, &m);
    int board[1000], walk, pos = 0, res = 0;
    if(n == 0)return 0;
    for(i = 0;i < n;i++){
      scanf("%d", board + i);
    }
    for(i = 0;i < m;i++){
      scanf("%d", &walk);
      if(pos >= n - 1)continue;
      pos += walk;
      if(pos < n - 1){
	pos += board[pos];
      }
      if(pos >= n - 1){
	printf("%d\n", i + 1);
      }
    }
  }
}

Measured memory_bytes: 600
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

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)
#define ALL(x) x.begin(),x.end()
using ll = long long;
using lint = long long;
typedef pair<int,int> P;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int m,k;cin>>m>>k;
  if(m==0){
      if(k==0){
          printf("0 0\n");
      }
      else cout<<-1<<"\n";
      return 0;
  }
  if(m==1){
      if(k==0)printf("0 0 1 1\n");
      else cout<<-1<<"\n";
      return 0;
  }
  if(k>(1<<m)-1){
      cout<<-1<<"\n";
      return 0;
  }
  vector<int> t;
  vector<int> r;
  if(k==0){
      rep(i,(1<<m)){
          cout<<i<<" "<<i<<" ";
      }
      cout<<endl;
      return 0;
  }
  rep1(i,(1<<m)-1){
      if(i!=k)t.push_back(i);
  }
  r=t;
  reverse(ALL(r));
  printf("0 ");
  for(auto& val:t){
      cout<<val<<" ";
  }
  cout<<k<<" ";
  for(auto& val:r){
      cout<<val<<" ";
  }
  cout<<0<<" "<<k<<endl;
  return 0;
}

Measured memory_bytes: 4216
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace std::chrono;

#define ll long long
#define ld long double
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define MOD1 998244353
#define MOD2 1000000007

#ifdef LL
const ll INF = 1e18;
#else 
const ll INF = 1e9;
#endif

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

high_resolution_clock::time_point setTime() { return high_resolution_clock::now(); }
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} //Just add this as a third argument to sort() while sorting an array of pairs; NO NEED FOR ANY ARGUMENTS;
template <typename T>
T fact(T a, T mod){ int res = 1, i; for (i = 2; i <= a; i++){ res *= i; res%=mod;} return res; }
template <typename T>
ll powmod(T a,T b,ll m){ ll ans=1; while(b>0){if(b&1){ans*=a;ans%=m;}a*=a;a%=m;b>>=1;} return ans; }
template <typename T>
ll power(T a, T b){ ll ans=1; while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;}
template <typename T>
T max3(T a, T b, T c) { return max((max(a,b), max(b,c))); }
template <typename T>
T min3(T a, T b, T c) { return min((min(a,b), min(b,c))); }
template <typename T>
T mid3(T a, T b, T c) { return a+b+c-max3(a,b,c)-min3(a,b,c); }
template <typename T>
T mid(T a, T b) { return min(a,b)+((max(a,b)-min(a,b))/2); }
template <typename T>
T gcd(T a,T b){ return (b?__gcd(a,b):a); }
template <typename T>
T lcm(T a, T b){ return (a*(b/gcd(a,b))); }
template <typename T>
T cl(T a, T b){ return (a+b-1)/b; }
template <typename T>
T to_upper(T s){ return transform(s.begin(), s.end(), s.begin(), ::toupper); }
template <typename T>
T to_lower(T s){ return transform(s.begin(), s.end(), s.begin(), ::tolower); }

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    auto startTime = setTime();

    int h,w;
    cin>>h>>w;

    ll a[h][w];
    ll b[h][w];
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            char c;
            cin>>c;
            if(c=='#') b[i][j]=0;
            else b[i][j]=1;
            a[i][j]=0;
        }
    }
    a[0][0]=1;
    a[h-1][w-1]=0;

    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(b[i][j]!=0)
            {
                if(i>0) a[i][j]=(a[i][j]+a[i-1][j])%MOD2;
                if(j>0) a[i][j]=(a[i][j]+a[i][j-1])%MOD2;
            }
        }
    }
    cout<<a[h-1][w-1]<<endl;

    auto stopTime = setTime();
    auto duration = duration_cast<microseconds>(stopTime - startTime);
    //cout<<"Program ran for "<<(ld)duration.count()/1e6<<" "<<"seconds"<<endl;
}


Measured memory_bytes: 19148
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    string S;
    int K;
    cin >> K >> S;

    if (K < S.length()) {
        S = S.substr(0, K) + "...";
    }

    cout << S << endl;

    return 0;
}


Measured memory_bytes: 3620
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

ll modinv(ll a,ll m){
  ll b=m,u=1,v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  u%=m; 
  if(u<0) u+=m;
  return u;
}

int main(){
  int n;
  cin>>n;
  
  vector<ll> A(n);
  rep(i,n) cin>>A[i];
  
  ll sum=0,sum2=0;
  
  rep(i,n){
    sum=(sum+A[i])%MOD;
    sum2=(sum2+A[i]*A[i]%MOD)%MOD;
  }
  
  cout<<((sum*sum%MOD-sum2+MOD)%MOD)*modinv(2,MOD)%MOD<<endl;
  
  return 0;
}

Measured memory_bytes: 4840
import numpy as np

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

fu = np.sum(A < 0)

if fu == 0:
    print(np.sum(A))
elif fu%2 == 0:
    print(np.sum(abs(A)))
else:
    b = min(abs(A))
    print(np.sum(abs(A)) - 2*b)

Measured memory_bytes: 23268
#include<iostream>
#include<vector>
using namespace std;
int main ()
{
	int i,n,m,c=0,k;
	vector<int> a;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
	    int k;
	    cin>>k;
	    a.push_back(k);
	}
	for(i=0;i<n;i++)
	{
	    if(a[i]>=m)
	    {
	        c++;
	    }
	}
	cout<<c;
	return 0;
}


Measured memory_bytes: 892
#include <iostream>

class Sarval {
private:
	int attack;
public:
	Sarval(int attack){
		this->attack = attack;
	}

	int Attack(int hp) {
		return hp - attack;
	}

};


class Monster {
private:
	int hp;
public:
	Monster(int hp) {
		this->hp = hp;
	}

	void setHP(int hp) {
		this->hp = hp;
	}

	int getHP() {
		return hp;
	}
};


int main()
{
	int hp, at;
	int count = 0;
	std::cin >> hp >> at;
	Sarval sarvar(at);
	Monster monster(hp);
	while (monster.getHP() > 0) {
		monster.setHP(sarvar.Attack(monster.getHP()));
		count++;
	}

    std::cout << count  << std::endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;



int N, T;
int A[200000];
int M[200000];
int main() {
	cin >> N >> T;
	for (int i = 0; i < N;i++) {
		cin >> A[i];
	}
	int mm = 0;
	for (int i = N - 1; i >= 0;i--) {
		if (mm < A[i]) {
			mm = A[i];
		}
		M[i] = mm;
	}
	int max_benef = 0;
	int times = 0;
	for (int i = 0; i < N;i++) {
		if (max_benef < M[i] - A[i]) {
			times = 0;
			max_benef = M[i] - A[i];
		}
		else if (max_benef == M[i] - A[i]) {
			times++;
		}
	}
	printf("%d\n", times+1);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define pd(a,n) for(int i=0;i<n;i++)cout<<a[i]<<((i==n-1)?"\n":" ");cout<<endl;
#define pdd(a,n,m)for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<a[i][j]<<" ";cout<<endl;}
#define mp make_pair
#define pb push_back
#define ll long long
//#define __int64 lng long
#define P pair<int,int>
#define PP pair<P,int>

int n;

int main(){
  cin>>n;
  cout<<n/2+n%2<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int sum[444444],sum2[444444];
char a[444444];
int main()
{
	int n,i,ans;
	scanf("%d",&n);
	scanf("%s",a+1);
	for(i=1;i<=n;i++)
	{
		sum[i]=sum[i-1];
		if(a[i]=='W')
		{
			sum[i]++;
		}
	}
	for(i=n;i>=1;i--)
	{
		sum2[i]=sum2[i+1];
		if(a[i]=='E')
		{
			sum2[i]++;
		}
	}
	ans=n;
	for(i=1;i<=n;i++)
	{
		ans=min(ans,sum[i-1]+sum2[i+1]); 
	}
	cout<<ans;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
 	return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
int fi[64][64];
int main(void)
{
  int r,c;
  vector<string> field;
  cin >> r >> c;
  field.resize(r);
  for(int i=0;i<r;++i) cin >> field[i];
  for(int i=0;i<64;++i)
    for(int j=0;j<64;++j)
      fi[i][j]=-3;
  int si,sj,gi,gj;
  for(int i=0;i<r;++i)
    for(int j=0;j<c;++j){
      if(field[i][j]=='.') fi[i+10][j+10]=1;
      if(field[i][j]=='#') fi[i+10][j+10]=-3;
      if(field[i][j]=='o') fi[i+10][j+10]=0;
      if(field[i][j]=='x') fi[i+10][j+10]=2;
      if(field[i][j]=='S'){
	fi[i+10][j+10]=1;
	si=i+10;
	sj=j+10;
      }
      if(field[i][j]=='G'){
	fi[i+10][j+10]=1;
	gi=i+10;
	gj=j+10;
      }
    }
  priority_queue<tuple<int,int,int> > dijk;
  set<tuple<int,int> > already;
  // -cost,i,j;
  dijk.push(make_tuple(0,si,sj));
  while(!dijk.empty()){
    int negc,h,w;
    tie(negc,h,w)=dijk.top();
    dijk.pop();
    if(!already.insert(make_tuple(h,w)).second) continue;
    if(h==gi&&w==gj){
      cout << -negc << endl;
      return 0;
    }
    if(fi[h+1][w]/2==0) dijk.push(make_tuple(negc-1-fi[h+1][w],h+1,w));
    if(fi[h-1][w]/2==0) dijk.push(make_tuple(negc-1-fi[h-1][w],h-1,w));
    if(fi[h][w+1]/2==0) dijk.push(make_tuple(negc-1-fi[h][w+1],h,w+1));
    if(fi[h][w-1]/2==0) dijk.push(make_tuple(negc-1-fi[h][w-1],h,w-1));
    for(int i=1;i<=3;++i){
      if(fi[h+i][w]<0) break;
      dijk.push(make_tuple(negc-2-i,h+i,w));
    }
    for(int i=1;i<=3;++i){
      if(fi[h-i][w]<0) break;
      dijk.push(make_tuple(negc-2-i,h-i,w));
    }
    for(int i=1;i<=3;++i){
      if(fi[h][w+i]<0) break;
      dijk.push(make_tuple(negc-2-i,h,w+i));
    }
    for(int i=1;i<=3;++i){
      if(fi[h][w-i]<0) break;
      dijk.push(make_tuple(negc-2-i,h,w-i));
    }
    
  }
}

Measured memory_bytes: 1272
// abc149_b
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    string S, T;
    cin >> S >> T;

    REP(i, S.size()){

        bool same = true;
        REP(j, S.size()){
            if (S[j] != T[(i + j) % S.size()]){
                same = false;
                break;
            }
        }

        if (same){
            print("Yes");
            return 0;
        }
    }

    print("No");


    return 0;
}


Measured memory_bytes: 256
//dont try to understand my code i really dont understand it 
#include<iostream>
#include<fstream>
#include<cmath>
#include<string>
#include<set>
#include <map>
#include<vector>
#include <queue>
#include <stack>
#include<algorithm>
using namespace std;
typedef long long ll;
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
typedef pair<int, int> ii;
const double PI = acos(-1.0);
const ll INF = 1000000000000;
//const ll F = LLONG_MIN;
const int A = 1234567;
// write what you need here : ... 
bool vis[A];
int arr[A];
int main() {
	int a; 
	cin >> a;
	for (int i = 1;i <= a;i++)
		cin >> arr[i];
	int count = 0;
	int start = 1;
	while (true)
	{
		
		if (start == 2)
		{
			cout << count;
			return 0;
		}
		if (vis[start])
		{
			cout << -1; 
			return 0;
		}
		else
		vis[start] = true;
		count++;
		//cout << start <<"asd"<< endl;
			start = arr[start];
	}
	

	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    map<int,int>m;
    int x;
    vector<int>num;
    for(int i=0;i<N;i++){
        cin>>x;
        m[i]=x;
        num.push_back(x);
    }
    sort(num.begin(),num.end());
    int med_1=num[N/2-1];
    int med_2=num[N/2];
    for(int i=0;i<N;i++){
        cout<<(m[i]<=med_1?med_2:med_1)<<endl;
    }
}

Measured memory_bytes: 13684
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 100000
#define MAX 100000
#define INFTY (1<<30)
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1000100011;
class Point { public: double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} Point operator+(Point p) { return Point(x + p.x, y + p.y); } Point operator-(Point p) { return Point(x - p.x, y - p.y); } Point operator*(double a) { return Point(a * x, a * y); } Point operator/(double a) { return Point(x / a, y / a); } double abs() { return sqrt(norm()); } double norm() { return x * x + y * y; } bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; } bool operator==(const Point& p) const { return fabs(x - p.y) < EPS && fabs(y - p.y) < EPS; } };
typedef Point Vector;
double norm(Vector a) { return a.x * a.x + a.y * a.y; }
double abs(Vector a) { return sqrt(norm(a));}
double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
struct Segment { Point p1, p2; };
typedef Segment Line;
// clang-format on

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll K, T;
  cin >> K >> T;
  vector<int> a(T);
  REP(i, T) cin >> a[i];

  priority_queue<P, vector<P>, less<P>> q;
  REP(i, T) { q.push({a[i], i}); }

  ll prev = -1;
  ll ans = 0;
  while (!q.empty()) {
    P p = q.top();
    q.pop();
    queue<P> tmp;
    while (!q.empty() && p.second == prev) {
      tmp.push(p);
      p = q.top();
      q.pop();
    }
    if (prev == p.second) {
      tmp.push(p);
      p = tmp.front();
      tmp.pop();
      ans++;
    }
    while (!tmp.empty()) {
      q.push(tmp.front());
      tmp.pop();
    }
    prev = p.second;
    if (p.first - 1 > 0) {
      q.push({p.first - 1, p.second});
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int ans=0;
int a=0;
for(int i=0;i<n;i++)
{
cin>>a;
if(a>=k)
{
ans++;
}
}
cout<<ans<<endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <numeric>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <utility>

#define repd(i,a,b); for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define ll long long int
 
 
using namespace std;
int main() {
  string s; cin >> s;
  int count0=0; int count1=1;
  
  
  for(int i=0;i<(int)s.size();i++){
   
    if(s[i] == '0'){
      count0++;
    }
  }
 
  cout << (int)s.size() - (max(count0,(int)s.size()-count0) - min(count0,(int)s.size()-count0));
 
 return 0;
}

Measured memory_bytes: 512
from collections import Counter

N = int(input())
S = []
for i in range(N):
    m = input()
    S.append(m)

c = Counter(S)

m = max(c.values())
ans = []

for i, j in c.items():
    if j == m:
        ans.append(i)
ans.sort()

for i in ans:
    print(i)

Measured memory_bytes: 35572
/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define popb pop_back
#define mt make_tuple 
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second 
#define ull unsigned long long  
#define pii pair<int, int>
#define piii pair<int,pii>
#define beg begin
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define fill(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define int ll
using ll = long long;
const int N = 3*1e5 +5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using namespace std;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

#ifdef AaryanS
#define mycout cout
#define mycerr cerr 
#endif

#ifndef AaryanS
#define mycout if(false) cout
#define mycerr if(false) cerr
#endif

int lg2(int n){
	int res = -1;
	while(n) res++ , n >>= 1;
	return res; 
}

void solve()
{
	int a, b;
	cin >> a >> b;
	int k = (a ^ b);
	int klen = lg2(k);
	a &= (1LL << (klen + 1)) - 1;
	b &= (1LL << (klen + 1)) - 1;
	// cout << a << " " << b << "\n" ;
	if(a == 0){
		cout << b + 1; 
		return ;
	}
	if(a == b){
		assert(a == 0LL);
		cout << 1;
		return ;
	}

	int n = (lg2(b)); // x1 + k1 && x2 + k2 
	// cout << n << "\n";
	int k1 = (lg2(a)) + 1;
	int x1 = (n - k1);
	int k2 = (lg2( b ^ (1LL << (n)))) + 1 ;
	int x2 = n - k2 ;
	// cout << x1 << " " << k1 << "\n";
	// cout << x2 << " " << k2 << "\n";
	int c1 = ((1LL << (x1)) - 1) * (1LL << (k1)) + ((1LL << k1) - a);
	int c2 = (1LL << (k2));
	int ans ;
	if(x1 + k2 >= n){
		ans = c1 + c2 + (1LL << (n)) - (1LL << (k2));
	}else{
		ans = (ll)2LL * c1 + c2 ;
		// cout << "x" ;
	}
	cout << ans;
}   

     
int32_t main(int32_t argc, char *argv[])
{
    double t1 = clock() ;
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        //cout << endl ;
    }
    mycerr << "Time : " << 1000 *(clock() - t1)/CLOCKS_PER_SEC << " ms\n" ;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define co(a) cout<<a<<endl
#define sz size
#define bgn begin()
#define en end()
#define pb(a) push_back(a)
#define pop pop_back
template<class T>
 void cou(vector<vector<T>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
//template<>
 void cou(vector<vector<char>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
signed main(){
  int n;
  cin>>n;
  cout<<n*n*n<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,c;
    scanf("%d%d",&a,&b);

    if(((a+b)%2)==0)
    {
        c=(a+b)/2;
        printf("%d\n",c);
    }
    else
    {
        printf("IMPOSSIBLE\n");
    }
    return 0;
}


Measured memory_bytes: 128
/**Bismillahir Rahmanir Rahim.**/
#include<bits/stdc++.h>
#define ll 	 long long
#define pb push_back
#define mp make_pair
using namespace std;

int main() 
{ 

double d, t, s; cin>>d>>t>>s;

double hh= (d/s);

if(hh>t) cout<<"No\n";
else cout<<"Yes\n";

  
    return 0;
} 


Measured memory_bytes: 3672
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <stack>
#include <queue>
#include <numeric>
#include <cstring>

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

using namespace std;

string makeseq(int N){
    int i;
    string seq = "";

    rep(i, N) seq += (rand() % 2) + '0';

    return seq;
}

int main(){
    int N, K, i, j, l, h;
    string seq;
    vector< vector < int > > data;

    cin >> N >> K;
    data.resize(K);
    rep(i, K) data[i].resize(N/2);
    rep(i, K)rep(j, N/2) cin >> data[i][j];

    l = N / 8;
    h = 3 * l;
    
    while(true){
        int sum = 0, count = 0;
        seq = makeseq(N);
        
        rep(i, K){
            sum = 0;
            rep(j, N/2){
                sum += seq[data[i][j] - 1] - '0';
            }
            if(l <= sum && sum <= h) count++;
        }
        if(count == K){
            cout << seq << endl;
            return 0;
        }
    }
}

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

int main(){
  int n; cin >> n;
  vector<int>p(n);
  int ans = 0;
  for(int i=0;i<n;i++){
    cin >> p.at(i);
  }
  for(int i=1;i<n-1;i++){
    if((p.at(i-1) < p.at(i) && p.at(i) < p.at(i+1)) || (p.at(i-1) > p.at(i) && p.at(i) > p.at(i+1)) ){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
x=int(input())
gojo=[]
for i in range(-120,120):
    gojo.append(i**5)
for i in range(len(gojo)-1):
    for j in range(i+1,len(gojo)):
        if x==gojo[j]-gojo[i]:
            ans=[j-120,i-120]
for i in ans:
    print(i,end=" ")


Measured memory_bytes: 9184
# -*- coding: utf-8 -*-
# 整数の入力
import sys
n = int(input())
li = list(map(int, input().split()))
# すの距離を計算
d = []
prev=0
for x in li:
  d.append(abs(x-prev))
  prev=x
d.append(abs(0-prev))
dist = sum(d)

# 各ステップ計算
prev=0
post=0
for i in range(n):
  if i==0:
    prev=0
  else:
    prev=li[i-1]
  if i==n-1:
    post=0
  else:
    post=li[i+1]
  nowe = li[i]

  if prev <= nowe and nowe <= post:
    print(dist)
  elif prev >= nowe and nowe >= post:
    print(dist)
  elif prev >= nowe and nowe <= post:
    print(dist-2*min(d[i], d[i+1]))
  elif prev <= nowe and nowe >= post:
    print(dist-2*min(d[i],d[i+1]))


Measured memory_bytes: 14176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N; cin>>N;
  int X[N],sum=0;
  rep(i,N){
    cin>>X[i];
    sum+=X[i];
  }
  ll ans=0;
  sum/=N;
  rep(i,N){
    ans+=(X[i]-sum)*(X[i]-sum);
  }
  ll tmp=0;
  sum++;
  rep(i,N){
    tmp+=(X[i]-sum)*(X[i]-sum);
  }
  cout<<min(ans,tmp)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
 
int main() {

    int n;
    cin>>n;
    vector<int> h(n);
    rep(i,n)    cin>>h.at(i);

    int ans=0;
    int active=0;
    rep(i,n) {
        if(active>=h[i]) {
            active=h[i];
        }
        else {
            ans+=h[i]-active;
            active=h[i];
        }
    }
    cout<<ans<<endl;
 
 return 0;
}

Measured memory_bytes: 256
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (ll i = (ll)(a); i<(ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;
TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM K, TNM V> using umap = unordered_map<K, V>;
TPL<TNM K, TNM V> using uset = unordered_set<K, V>;

TPL<class T> inline void OUT(const T &x) { cout << x << "\n"; }
void YESNO(bool c) { OUT(c ? "YES" : "NO"); };
void YesNo(bool c) { OUT(c ? "Yes" : "No"); };
void bOUT(bool c, string s, string t) { OUT(c ? s : t); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

TPL<TNM V, TNM H> void resize(vector<V>& v, const H h) { v.resize(h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& v, const H& h, const T ... t) { v.resize(h); for (auto& _v : v) resize(_v, t ...); }
TPL<TNM V, TNM T> void fill(V& x, const T& val) { x = val; }
TPL<TNM V, TNM T> void fill(vector<V>& vec, const T& val) { for (auto& v : vec) fill(v, val); }

int main(void) {
	int N, K;
	cin >> N >> K;
	vec<ll> X(N);

	REP(i, N) {
		cin >> X[i];
	}

	vec<ll> Y(N), Z(N);

	REP(i, N) {
		if (X[i] < 0) {
			Y[i] = 2 * X[i];
			Z[i] = X[i];
		}
		else {
			Y[i] = X[i];
			Z[i] = 2 * X[i];
		}
	}

	ll mn = numeric_limits<ll>::max();
	REP(i, N) {
		if (i + K - 1 >= N) {
			break;
		}
		ll sum;
		if (Y[i] < 0 && Y[i + K - 1] < 0) {
			sum = abs(Y[i]);
		}
		else if (Y[i] < 0 && Y[i + K - 1] >= 0) {
			sum = abs(Y[i]) + Y[i + K - 1];
		}
		else {
			sum = Y[i + K - 1];
		}
		mn = min(sum, mn);
	}

	REP(i, N) {
		if (i + K - 1 >= N) {
			break;
		}
		ll sum;
		if (Z[i] < 0 && Z[i + K - 1] < 0) {
			sum = abs(Z[i]);
		}
		else if (Z[i] < 0 && Z[i + K - 1] >= 0) {
			sum = abs(Z[i]) + Z[i + K - 1];
		}
		else {
			sum = Z[i + K - 1];
		}
		mn = min(sum, mn);
	}

	cout << mn << endl;
	return 0;
}

Measured memory_bytes: 2560
class UnionFind:
    def __init__(self, N:int):
        """N: 大きさ"""
        self.par = [i for i in range(N)]
        self.size = [1]*N
        self.rank = [1]*N
        
    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
        
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        elif self.rank[root_x]<self.rank[root_y]:
            root_x,root_y = root_y,root_x
        # 短いほう(y)を長いほう(x)にくっつける
        self.par[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        self.size[root_y] = 0 # もういらない
        
    def get_size(self, x:int)->int:
        """xの属するグループのサイズ"""
        return self.size[self.root(x)]
    

def main():
    N,M = map(int,input().split())
    ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    uf = UnionFind(N)
    accm = []
    for ai,bi in reversed(ab):
        if uf.is_same(ai,bi):
            accm.append(0)
        else:
            accm.append(uf.get_size(ai)*uf.get_size(bi))
        uf.unite(ai,bi)

    accm = accm[::-1]
    for i in range(1,len(accm)):
        accm[i] += accm[i-1]
    for a in accm:
        print(a)

main()

Measured memory_bytes: 27600
#include<cstring>
#include<cstdio>
#include<cmath>
#include<memory.h>
#include<algorithm>
#include<map>
#define ll long long
#define ld long double
#define maxn 310
#define For(i,j,k)  for(ll i=j;i<=k;++i)
#define FOr(i,j,k)  for(ll i=j;i>=k;--i)
const ll inf=1e9;
const ld eps=1e-7;
using namespace std;
inline ll read(){   ll x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  return x*f; }
inline void wrote(ll x){    if (x<0) putchar('-'),x=-x; if (x>=10) wrote(x/10);   putchar(x%10+'0');  }
void writeln(ll x){ wrote(x);   puts("");   }
ll s,c,ans;
int main(){
	s=read();	c=read();
	ans+=min(s,c/2);	c-=min(s,c/2)*2;
	writeln(c/4+ans);
}

Measured memory_bytes: 128
/*#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <utility>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <deque>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define LL long long
#define ll long long
#define Pair pair<int,int>
#define LOWBIT(x) x & (-x)
using namespace std;*/

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define ll long long

const LL MOD=1e9+7;
const int maxn=1e5+10;

//const int INF=0x7ffffff;
//const int magic=348;
//const int zero=200;

int n;
//LL p,p1;
LL id1,id2;
LL a[100048];
int v[100048];
int cnt[100048];

LL fac[100048],finv[100048],inv[100048];

void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<100010;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}

int main ()
{
	//LL i;
	//cin>>n;
	/*memset(cnt,0,sizeof(cnt));
	for (i=1;i<=n+1;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	p=p1=0;
	for (i=1;i<=n+1;i++)
		if (cnt[a[i]]==2)
			if (p1==0) p1=i; else p=i;*/
	/*	memset(a, 0, sizeof(a));
    memset(v, 0, sizeof(v));
    for(ll i = 1; i <= n + 1; ++i){
        cin >> a[i];
        v[a[i]]++;
    }
    for(ll i = 1; i <= n + 1; ++i){
        if(v[a[i]] == 2 && !id1){
            id1 = i;
        }
        else if(v[a[i]] == 2) {
            id2 = i;
        }
    }
	LL ans;
	make();
	LL L=max(id1-1,0LL),R=max(n+1-id2,0LL);
	for (ll i=0;i<=n;i++)
	{
		ans=C(n+1,(i+1)*1LL);
		ans-=C(L+R,i*1LL);
		if (ans<0) ans+=MOD;
		cout<<ans<<endl;
	}
	return 0;*/
	ll n;
    make();
    ll id1 = 0, id2 = 0;
    cin >> n;
    memset(a, 0, sizeof(a));
    memset(v, 0, sizeof(v));
    for(ll i = 1; i <= n + 1; ++i){
        cin >> a[i];
        v[a[i]]++;
    }
    for(ll i = 1; i <= n + 1; ++i){
        if(v[a[i]] == 2 && !id1){
            id1 = i;
        }
        else if(v[a[i]] == 2) {
            id2 = i;
        }
    }
    ll L = max(id1 - 1LL, 0LL), /*M = id2 - id1 - 1LL*/ R = max(n + 1LL - id2, 0LL);
    ll res = 0;
    for(ll i = 1; i <= n + 1; ++i){
        res = C(n + 1, i * 1LL);
        res -= C(L + R, (i - 1) * 1LL);
        if(res < 0)res += MOD;
        cout << res << '\n';
    }
    return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
//#define mp make_pair
using namespace std;
typedef pair<int, int> pii;

int x, y, gx, gy;

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin>> x >> y;
	if(x == 2 || y == 2) return 0*puts("No");
	if(x == 4 || x == 6 || x == 9 || x == 11)
		gx = 2;
	else
		gx = 1;
	if(y == 4 || y == 6 || y == 9 || y == 11)
		gy = 2;
	else
		gy = 1;
	if(gx == gy)
		puts("Yes");
	else
		puts("No");
	return 0;
}

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

int main(){
    while(true){
        vector<pair<int, int> >term; //solved, time
        int time[100][100];
        int M, T, P, R;
        cin >> M >> T >> P >> R;

        if(M+R+P+R == 0) break;

        for(int i=0; i < 100; i++)for(int j=0; j < 100; j++) time[i][j] = 0;

        for(int i=0; i < T; i++){
            term.push_back(pair<int, int>(0, 0));
        }

        for(int i=0; i < R; i++){
            int m, t, p, j;
            cin >> m >> t >> p >> j;
            t--;
            if(j == 0){
                term[t].first = term[t].first - 1;
                term[t].second = term[t].second + m + time[t][p];
            }
            else {
                time[t][p] += 20;
            }
        }
        vector<pair<int, int> > copyTerm = term;

        sort(term.begin(), term.end());//, pairCompare);

        for(int i=0; i < term.size(); i++){
            for(int j=term.size()-1; j != -1; j--){
                if(i != 0){
                    if(term[i].first == copyTerm[j].first && term[i].second == copyTerm[j].second){
                        if(term[i-1].first != term[i].first || term[i-1].second != term[i].second){
                            cout << "," << j+1;
                            copyTerm[j].first = 100000;
                            break;
                        }
                        else {
                            cout << "=" << j+1;
                            copyTerm[j].first = 100000;
                            break;
                        }
                    }
                }
                else if(term[i].first == copyTerm[j].first && term[i].second == copyTerm[j].second){
                    cout << j+1;
                    copyTerm[j].first = 1000000;
                    break;
                }
            }
        }
        cout << endl;

        term.clear();
    }
}

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

int main(){
  int n,q;
  string s;
  cin >> n >> q >> s;
  int l[q],r[q];
  for(int i=0;i<q;i++){
    cin >> l[i] >> r[i];
  }
  int a[n-1];
  for(int i=0;i<n-1;i++){
    if(s.at(i)=='A'&&s.at(i+1)=='C'){
      a[i]=1;
    }
    else{
      a[i]=0;
    }
  }
  int b[n];
  b[0]=0;
  for(int i=1;i<n;i++){
    b[i]=b[i-1]+a[i-1];
  }
  for(int i=0;i<q;i++){
    cout << b[r[i]-1]-b[l[i]-1] << endl;
  }
}

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


int main(){
    priority_queue<int> H;
    string order;
    while(true){
        cin>>order;
        if(order=="insert"){
            int k;cin>>k;
            H.push(k);
        }else if(order=="extract"){
            cout<<H.top()<<endl;
            H.pop();
        }else{
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 6948
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,R=map(int,input().split())
    print(R+100*max(0,(10-N)))

if __name__ == '__main__':
    main()


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD 998244353

ll N,S;
ll A[3030];
ll dp[3030][3030];

ll i, j, k;
int main(){
    scanf("%lld%lld", &N,&S);
    fornum(i,0,N){
        scanf("%lld", &A[i]);
    }
    ll ans=0;
    dp[0][0] = 1;
    fornum(i,0,N){
        dp[i + 1][0] = 1;
        fornum(j,0,S){
            if(j+A[i]<S){
                dp[i + 1][j + A[i]] += dp[i][j];
                dp[i + 1][j + A[i]] %= MOD;
            }
            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j] %= MOD;
        }
        if(S<A[i])
            continue;
        ans += dp[i][S - A[i]] * (N - i) % MOD;
        ans %= MOD;
    }
    printf("%lld", ans);

    return 0;
}

Measured memory_bytes: 71936
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep (i ,n) for(int i=0;i<(n);i++) 
ll gcd (ll a,ll b) {return b?gcd(b,a%b):a;}   
ll lcm (ll a,ll b) {return a/gcd(a,b)*b;} 


int main(){
	double w,h,x,y;
	cin>>w>>h>>x>>y;
	cout<<(w*h)/2<<" ";
	double mid=w/2;
	double hid=h/2;
	if(mid==x && hid==y){
		cout<<1<<endl;
	}else{
		cout<<0<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
using namespace std;

int main() {
      int N,D,X;
    cin >> N >> D >> X;
  vector<int> A(N);
    for(int i = 0;i< N;i++) cin >> A[i];
  int ans = X;
  for(int i = 0;i<N;i++){
  ans += (D-1)/A[i] + 1;}
  cout << ans << '\n';
}
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
int main()
{
	fast;
	ll x,y,z,k,flag=0;
	cin>>x>>y>>z>>k;
	vector<ll> a(x);
	vector<ll> b(y);
	vector<ll> c(z);
	for(int i=0;i<x;i++)
		cin>>a[i];
	for(int i=0;i<y;i++)
		cin>>b[i];
	for(int i=0;i<z;i++)
		cin>>c[i];
	sort(a.begin(),a.end(),greater<ll>());
	sort(b.begin(),b.end(),greater<ll>());
	sort(c.begin(),c.end(),greater<ll>());
	vector <ll> ans;
	for(int i=0;i<x;i++)
	{
		for(int j=0;j<y;j++)
		{
			for(int m=0;m<z;m++)
			{
				if((i+1)*(j+1)*(m+1)<=k)
					ans.push_back(a[i]+b[j]+c[m]);
				else
					break;
			}
		}
	}
	sort(ans.begin(),ans.end(),greater<ll>());	
	for(int i=0;i<k;i++)
		cout<<ans[i]<<endl;
	return 0;
}


Measured memory_bytes: 4284