akhauriyash/Code-Regression huggingface dataset:
#abc_155_d
import numpy as np
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.array(a)
a.sort()

plus = a[a>0]
zero = a[a==0]
minus= a[a<0]

left = -10**18
right = 10**18

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
        
print(right)

Measured memory_bytes: 32300
#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;


int main(){
	set<int> t;
	int a; cin >> a; t.insert(a);
	cin >> a; t.insert(a);
	for(int i = 1; i<=3; i++) if (t.count(i)==0) {cout << i << endl; return 0;}
	
	return 0;
}


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

int main(){

    int n; cin >> n;
    double ans = 0;
    for(int i = 0; i < n; i++){
        double x; string s; cin >> x >> s;
        ans += x * (s == "JPY" ? 1.0 : 380000.0);
    }

    printf("%.10f\n", ans);
    return 0;
}

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

namespace ConsoleApplication1
{
    class GetLargestSquare
    {
        readonly int N;

        int[,] dp;

        public GetLargestSquare(int n)
        {
            N = n;
            dp = new int[N, N];
        }

        public void MakeDP(string source, int h)
        {
            for (int i = 0; i < N; i++)
            {
                dp[h, i] = source[i] == '.' ? 1 : 0;
            }
        }

        public int GetMaxLength()
        {
            int ret = 0;

            for (int i = 1; i < N; i++)
            {
                for (int j = 1; j < N; j++)
                {
                    if (dp[i, j] == 0) continue;

                    dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]);
                    dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j - 1]) + 1;

                    ret = Math.Max(ret, dp[i, j]);
                }
            }
            return ret;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            while (true)
            {
                int n = int.Parse(Console.ReadLine());

                if (n == 0) break;

                GetLargestSquare LS = new GetLargestSquare(n);

                for (int i = 0; i < n; i++)
                {
                    LS.MakeDP(Console.ReadLine(), i);
                }
                sb.AppendLine(LS.GetMaxLength().ToString());
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 24428
#include<bits/stdc++.h>
#define int           long long
#define pb            push_back
#define ppb           pop_back
#define si            set <int>
#define endl          '\n'
#define fr            first
#define sc            second     
#define rep(i,a,b)    for(int  i=a;i<b;i++)
#define repr(i,a,b)      for(int i=b-1;i>=a;i--)
#define trav(it,v)      for(auto it=v.begin();it!=v.end();it++)
#define all(v)        v.begin(),v.end()
#define srt(v)        sort(all(v))
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define bs            binary_search
#define sp(n)         setprecision(n)
#define spl           " "
#define arr(a,n)      rep(i,0,n) cin>>a[i]
#define mod           998244353
#define MAXN             10001

using namespace std;

bool sortinrev(const pair<int,int> &a,  
               const pair<int,int> &b) 
{ 
       return (a.first > b.first); 
} 


//int dx[4]={0,0,1,-1};
//int dy[4]={1,-1,0,0};
void solve()
{
    
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c<<" "<<a<<" "<<b;

    
    
}	
	


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
    //cin>>t;
    while(t--)
    {
    	solve();
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pi pair<int,int>
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define dbg(x) cout<<#x<<": "<<x<<endl
#define clr(x,v) memset(x, v, sizeof(x))
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;

void cp()
{
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> arr(n);
    for(ll &x : arr)
        cin >> x;
    ll lo = 1, hi = INT_MAX;
    ll ans = *max_element(all(arr));
    while(lo <= hi)
    {
        ll cuts = 0;
        ll mid = (hi + lo) / 2;
        for(int i = 0; i < n; i++)
        {
            ll req = (arr[i] > mid ? arr[i] / mid : 0);
            cuts += req;
        }
        if(cuts <= k)
            ans = mid, hi = mid - 1;
        else
            lo = mid + 1;
    }
    cout << ans;
}

int main()
{
    FASTIO;
    int t;
    t = 1;
    // cin >> t;
    while(t--)
    {
        cp();
    }
    return 0;
}

Measured memory_bytes: 4780
#include<iostream>
using namespace std;
int main() {
	int n;
	while (cin >> n)
	{
		if (n == 0)break;
		int ice[10] = { 0 };
		for (int i = 0; i < n; i++){
			int a;
			cin >>a;
			ice[a]++;
		}
		for (int i = 0; i < 10; i++){
			if (ice[i] == 0){
				cout << '-';
			}
			else{
				for (int j = 0; j < ice[i]; j++) {
					cout << '*';
				}
			}
			cout << endl;
		}
	}
}

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

ll f(ll to, ll n) {
  return to / n;
}

int main() {
  ll A, B, C, D, tmp;
  cin >> A >> B >> C >> D;

  ll c = C, d = D, r = C % D;
  while (r != 0) {
    c = d;
    d = r;
    r = c % d;
  }

  ll lcm = C * D / d;

  ll q1 = f(B, C);
  ll q2 = f(B, D);
  ll q3 = f(B, lcm);
  ll Q = B - q1 - q2 + q3;

  ll p1 = f(A - 1, C);
  ll p2 = f(A - 1, D);
  ll p3 = f(A - 1, lcm);
  ll P = A - 1 - p1 - p2 + p3;

  ll ans = Q - P;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int r = sc.nextInt();
        int g = sc.nextInt();
        int b = sc.nextInt();
        int n = sc.nextInt();

        int ans = 0;
        for (int i = 0; i*r <= n; i++) {
            for (int j = 0; j*g <= n; j++) {
                int num = i * r + j * g;
                if (num > n)
                    break;
                else
                    num = n - num;
                if (num % b == 0)
                    ans++;
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 23636
A=[]
gets.to_i.times{
a=gets.split.map &:to_i
if a[0]==0
A.send(a[1]==0 ? :unshift : :push,a[2])
elsif a[0]==1
p A[a[1]]
elsif a[1]==0
A.shift
else
A.pop
end
}


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

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];

    int MIN = 100;
    int res=0;
    for(int i=0; i<n; i++){
        if(i == 0){
            MIN = p[i];
            res++;
        }else{
            if(MIN >= p[i]){
                MIN = p[i];
                res++;
            }
        }
    }

    cout << res << endl;
    return 0;
}


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

int main() {
  int n,x;
  cin>>n>>x;
  vector<int> s(n);
  s[0]=0;
  for(int i=1; i<=n; i++) {
    int h; cin>>h;
    s[i]=s[i-1]+h;
  }
  for(int i=0; i<=n; i++){
    if(s[i]>x) {
      cout<<i;
      return 0;
    }
  }
  cout<<n+1;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
string s,t;
  bool flag=false;
cin >>s>>t;
  int p;
  for(int j=0;j<101;j++){
    int p=s.at(s.size()-1);
  for(int i=s.size()-1;i>0;i--){
    s.at(i)=s.at(i-1);
  }
  s.at(0)=p;
  if(s==t){flag=true;
          break;}}
if(flag)cout << "Yes" <<endl;
  else cout << "No" <<endl;
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  string a, b;
  while(cin >> a >> b) {
    if(a == "0") break;
    map<char, int> mp;
    int hit = 0;
    int br = 0;
    rep(i, 0, 4) {
      if(a[i] == b[i]) hit++;
      else {
        if(mp[a[i]]) {
          mp[a[i]] = 0;
          br++;
        }else mp[a[i]] = 1;
        if(mp[b[i]]) {
          mp[b[i]] = 0;
          br++;
        }else mp[b[i]] = 1;
      }
    }

    cout << hit << " " << br << endl;
  }
}

Measured memory_bytes: 2992
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int sol = 700;
    for (char c : s)
        if (c == 'o')
            sol += 100;
    cout << sol;
}


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

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second
#define pb push_back

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

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

int main() { _
	string s; cin >> s;
	for (int i = 0; i < s.size(); i++) if (s[i] == 'A')
		for (int j = s.size()-1; j+1; j--) if (s[j] == 'Z')
			return cout << j-i+1 << endl, 0;
	exit(0);
}


Measured memory_bytes: 720
#include <iostream>

using namespace std;

int main()
{
        const int MAX = 101;
        int num[MAX];
        for (int i = 1; i < MAX; i++) {
                num[i] = 0;
        }
        int a;
        while (cin >> a) {
                num[a]++;
        }
        int cnt = 0, max = 0;
        int mode[100];
        for (int i = 1; i < MAX; i++) {
                max = (max < num[i]) ? num[i] : max;
        }
        for (int i = 1; i < MAX; i++) {
                if (num[i] == max) {
                        mode[cnt++] = i;
                }
        }
        for (int i = 0; i < cnt; i++) {
                cout << mode[i] << endl;
        }

        return 0;
}

Measured memory_bytes: 3064
//Be Name Khoda
/*
tane adami sharifast be jane adamiat
na hamin lebase zibast neshane adamiat
agar adami be cheshmasto dahano goosho bini
che miane naghshe divaro miane adamiat
khoro khabo khashmo shahvat shaghab asto jahlo zolmat
hayavan khabar nadarad ze jahane adamiat
be haghighat adami bash vagarna morgh bashad
ke hami sokhan begooyad be zabane adamiat
*/
#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;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long LL;
typedef LL ll;
typedef long double ld;
typedef string str;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef stringstream strs;
 
 
#define X first
#define Y second
#define PB push_back
#define For(i,a,b) for (ll i=a;i<b;++i)
#define Ford(i,a,b) for (ll i=a;i>=b;--i)
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define SZ(a) ((ll)a.size())
#define ER(a) cout << #a << ' ' << a << endl
#define LB(a,n,x) (lower_bound(a,(a)+(n),x)-(a))
#define RET(x) { cout << x; exit(0); }
#define MKP make_pair
#define RETD(x) { cout << fixed << setprecision(15) << x; } //exit(0); }
#define GEI(x) scanf("%d",&x)
#define GEL(x) scanf("%lld",&x)
#define ALL(x) x.begin(),x.end()
const ll M=50+5,LG=30,SM=1000,inf=1e9+5;
ll mod=1e9+7;
ll pw(ll a,ll n) { return (n==0?1:pw(a*a%mod,n/2)*(n%2?a:1)%mod); }
#define MOK(x) if (x>mod) x-=mod;

ll chsn[M];

bool cnn[M];
ll n,a[M],b[M];

bool cn(ll x,ll y)
{
    memset(cnn,0,sizeof cnn);
    cnn[x]=1;
    Ford(i,M-1,1)
    {
        if (!chsn[i]) continue;
        For(j,i,M) if (cnn[j]) cnn[j%i]=1;
    }
    return (cnn[y]);
}

bool check()
{
    For(i,0,n)
    {
        if (!cn(a[i],b[i])) return 0;
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    For(i,0,n) cin >> a[i];
    For(i,0,n) cin >> b[i];
    For(i,0,M) chsn[i]=1;
    if (!check()) { cout << "-1\n"; return 0; }
    ll res=0;    
    Ford(i,M-1,1)
    {
        chsn[i]=0;
        if (!check())
        {
            chsn[i]=1;
            res+=(1LL<<i);
        }
    }
    cout << res << '\n';
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    int a[n + 1], b[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = 0;
    }
    vector<int> ans;
    for (int i = n; i >= 1; i--) {
        int cnt = 0;
        for (int j = 2 * i; j <= n; j += i) {
            if (b[j]) {
                cnt++;
            }
        }
        if (cnt % 2 != a[i]) {
            b[i] = 1;
            ans.push_back(i);
        }
    }
    cout << sz(ans) << "\n";
    for (int &x : ans) {
        cout << x << " ";
    }
    cout << "\n";
}
    

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

using namespace std;

int main(){
    int N;
    string s, t;
    cin >> N >> s >> t;

    int ans = 2 * N;

    int count = 0;
    for (int i = 0; i < N; i++){
        bool f = false;
        if (s[i] == t[0]){
            for (int j = 0; i + j < N; j++){
                if (s[i + j] != t[j]){
                    break;
                }else{
                    count ++;
                }
                if (i + j == N - 1){
                    f = true;
                }
            }
        }
        if (f == false){
            count = 0;
        }else{
            break;
        }
    }
    
    ans = ans - count;
    
    cout << ans << endl;

    return 0;
}

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

int main(){
	vector<int> car, exit;
	int n;
	
	while( cin >> n ){
		
		if(n != 0){
			car.push_back(n);
		}else{
			exit.push_back( car.back() );
			car.pop_back();
		}
	}
	vector<int>::iterator it = exit.begin();

	while( it != exit.end() ){
		cout << *it << endl;
		++it;
	}
	return 0;
}

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

#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define allg(a) (a).begin(), (a).end(), greater<int>()

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;

const int INF = 1001001001;
const int MOD = 1000000007;
const long long INFL = (1LL << 60);
const double EPS = 1e-9;

int main() {
  int N;
  cin >> N;
  vi a(N);
  rep(i, N) cin >> a[i];

  map<int, int> m;
  rep(i, N) m[a[i]]++;
  int res = 0;
  for (auto p : m) {
    if (p.second % 2) res++;
  }

  cout << res << endl;
}

Measured memory_bytes: 5376
#include <stdio.h>

int a[200010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int d=1;d<=n;d++)if(n%d==0){
		int flag=1;
		for(int i=0;i<n-d;i++)flag&=a[i]==a[i+d];
		if(flag){
			printf("%d\n",n/d);
			return 0;
		}
	}
}


Measured memory_bytes: 2584
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=1000005;
const int MOD=1000003;
int add (int x,int y)   {x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y)   {return (LL)x*y%MOD;}
int dec (int x,int y)   {x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
	if (y==0) return 1;
	if (y==1) return x;
	int lalal=Pow(x,y>>1);
	lalal=mul(lalal,lalal);
	if (y&1) lalal=mul(lalal,x);
	return lalal;
}
int pre[N];
int main()
{
	pre[0]=1;for (int u=1;u<MOD;u++) pre[u]=mul(pre[u-1],u);
	int T;
	scanf("%d",&T);
	while (T--)
	{
		int x,d,n;
		scanf("%d%d%d",&x,&d,&n);
		if (d==0) {printf("%d\n",Pow(x,n));continue;}
		x=mul(x,Pow(d,MOD-2));
		if (x+n-1>=MOD||x==0) {printf("0\n");continue;}
		int now=mul(pre[x+n-1],Pow(pre[x-1],MOD-2));
		now=mul(now,Pow(d,n));
		printf("%d\n",now);
	}
	return 0;
}

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

int main() {
  long long int N;
  cin >> N;
  long long int A[N];
  long long int count[N] = {};

  for(int i = 0; i < N; i++) {
    cin >> A[i];
    count[A[i]-1]++;
  }
  long long int sum = 0;
  for(int i = 0; i < N; i++) {
    sum += count[i] * (count[i] - 1) / 2;
  }
  for(int i = 0; i < N; i++) {
    cout << sum - (count[A[i] - 1] - 1) << endl;
  }
  return 0;
}

Measured memory_bytes: 5760
#include <cstdio>
using namespace std;
int S[1000000],n;
int serch(int key){
  int left=0,right,mid;
  right=n;
  while(left<right){
    mid=(left+right)/2;
    if(key==S[mid])return 1;
    if(key>S[mid])left=mid+1;
    else if(key<S[mid])right=mid;
  }
  return 0;
}
int main(){
  int q,key;
  int i,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(serch(key))sum++;
  }
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 3052
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class BMultiplication2 {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int N;
        cin >> N;
        vector<int> A(N);
        REP(i, N) cin >> A[i];
        int res = 1;
        REP(i, N) {
            if (A[i] == 0) {
                cout << 0 << endl;
                return;
            }
        }
        int sum = 0;
        bool ok = true;
        REP(i, N) {
            int n = A[i];
            while (n >= 10) {
                sum++;
                n /= 10;
            }
            if (n > 1) ok = false;
        }
        if (sum > 18 || (sum == 18 && !ok)) {
            cout << -1 << endl;
            return;
        }
        REP(i, N) {
            res *= A[i];
            if (res > 1000000000000000000) {
                cout << -1 << endl;
                return;
            }
        }
        cout << res << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    BMultiplication2 solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 3976
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int i;
    int ans;
    if (n % 2 == 0) {
        i = n;
    }
    else {
        i = n+1;
    }

    while(1)
    {
        if (i % n == 0) {
            ans = i;
            break;
        }
        i = i+2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin>>a>>b;
    ll ans=0;
    while(a<=b){
    	a*=2;
    	ans++;
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{

  unsigned int key;
  struct node *next;
  struct node *prev;

};

typedef struct node *NodePointer;

NodePointer nil;


NodePointer listSearch(int key)
{
  NodePointer n;

  for( n=nil->next; n != nil; n=n->next )
    {
      if( n->key == key ) return n;
    }
  return nil;
}


void initial()
{
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}


void printList()
{
  NodePointer cur = nil->next;
  int isf = 1;

  while(1)
    {
      if( cur == nil ) break;
      if( isf == 0 ) printf(" ");
      printf("%d", cur->key);
      cur = cur->next;
      isf = 0;
    }
  printf("\n");
}


void deleteNode(NodePointer t)
{
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}


void deleteFirst()
{
  NodePointer t = nil->next;
  
  if( t == nil ) return;
  deleteNode(t);
}


void deleteLast()
{
  NodePointer t = nil->prev;

  if( t == nil ) return;
  deleteNode(t);
 
}


void delete(int key)
{
  NodePointer x;

  if( (x = listSearch(key)) == nil ) return;
  
  x->prev->next = x->next;
  x->next->prev = x->prev;
  free(x);
}

void insert(int key)
{
  NodePointer x;
  
  x = malloc(sizeof(struct node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main()
{
  int key, n, i;
  int size = 0;
  char command[20];
  int np = 0, nd = 0;

  scanf("%d", &n);
  initial();

  for( i=0; i<n; i++ )
    {
      scanf("%s%d", command, &key);

      if( command[0] == 'i' )
	{
	  insert(key);
	  np++;
	  size++;
	}

      else if( command[0] == 'd' )
	{
	  if( strlen(command) > 6 )
	    {
	      if( command[6] == 'F' ) deleteFirst();
	      else if( command[6] == 'L' ) deleteLast();
	    }

	  else
	    {
	      delete(key);
	      nd++;
	    }
	  
	  size--;
	}
    }

  printList();

  return 0;
}

  



Measured memory_bytes: 32964
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    HashMap<String, String> m = new HashMap<String, String>();
    m.put("22", "Christmas Eve Eve Eve");
    m.put("23", "Christmas Eve Eve");
    m.put("24", "Christmas Eve");
    m.put("25", "Christmas");
    String d = sc.next();
    System.out.println(m.get(d));
  }
}


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
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;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}



void solve()
{
  ll D, G; cin >> D >> G;
  vector<ll> p(D), c(D); rep(i, D) cin >> p[i] >> c[i];
  vector<ll> cp(D); rep(i, D) cp[i] = (i + 1) * p[i] * 100 + c[i];
  rep(i, D) cerr << i << " cp:" << cp[i] << endl;
  ll pmin = -1;
  for(ll i = 0; i < (1<<D); i++) {
    ll ttl = 0;
    ll nop = 0;
    for(ll j = 0; j < D; j++) {
      if(i & 1<<j) {
	ttl += cp[j];
	nop += p[j];
      }
    }
    cerr << i << " ttl:" << ttl << endl;
    if(ttl < G) {
      ll mxp ;
      for(mxp = D - 1; mxp >=0 && ((i & 1 << mxp) !=0); mxp--) ;
      cerr << " mxp:" << mxp << endl;
      rep(j, p[mxp] - 1) {
	ttl += (mxp + 1) * 100;
	nop ++;
	if(ttl >= G) break;
      }
    }
    cerr << " nop:" << nop << endl;
    if(ttl >= G &&(pmin < 0 || nop < pmin)) pmin = nop;
  }
    
  cout << pmin << endl;

}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string alice, bob, charlie;
    cin >> alice >> bob >> charlie;
    char prev = 'a';
    int pa = 0, pb = 0, pc = 0;
    while (true) {
        if (prev == 'a') {
            if (!alice[pa]) {
                cout << "A";
                return 0;
            }
            prev = alice[pa ++];
        }
        else if (prev == 'b') {
            if (!bob[pb]) {
                cout << "B";
                return 0;
            }
            prev = bob[pb ++];
        }
        else {
            if (!charlie[pc]) {
                cout << "C";
                return 0;
            }
            prev = charlie[pc ++];
        }
    }
    
}

Measured memory_bytes: 256
n , L = map(int, input().split())
taste = 0

if L >= 0:
    taste = L * (n-1) - n + n*(n+1)/2

elif -L >= n:
    taste = L * (n-1) - (n-1) + n*(n-1)/2

else:
    taste = L * n + n*(n+1)/2 - n

print(int(taste))



Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;

#define INF 1e18
#define int long long
#define MAX 100000

int parent(int i) {return i / 2;}
int left(int i) {return 2 * i;}
int right(int i) {return 2 * i + 1;}

signed main() {
    int h; cin >> h;
    vector<int> v(h + 1);
    for(int i = 1; i <= h; i++) cin >> v[i];

    for(int i = 1; i <= h; i++) {
        cout << "node " << i << ": key = " << v[i] << ", ";
        if(parent(i) >= 1) cout << "parent key = " << v[parent(i)] << ", ";
        if(left(i) <= h) cout << "left key = " << v[left(i)] << ", ";
        if(right(i) <= h) cout << "right key = " << v[right(i)] << ", ";
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define In_The_Name_Of_Allah_The_Merciful ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define Alhamdulillah return 0;
#define debug(n) cerr << "[" << #n << " = " << n << "]" << endl 

void Suhaib_Sawalha (){

    int a , b , c;
    cin >> a >> b >> c;
    cout << (c >= a && c <= b ? "Yes" : "No");
    
}

int main(){
                                In_The_Name_Of_Allah_The_Merciful   /* بسم الله الرحمن الرحيم  */
#ifndef ONLINE_JUDGE
    freopen("SuhaibSawalha1.txt","r",stdin);
#endif
//int _;for(cin>>_;_;--_,cout<<'\n')
        Suhaib_Sawalha();
                                         Alhamdulillah                    /* الحمد لله */
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;
    int n, d, x;
    cin >> n >> d >> x;
    vector<int> A(n);
    rep(i, n) cin >> A.at(i);

    int cnt = 0;
    rep(i, n) {
        int part = A.at(i);
        int weight = 0;
        rep(day, d) {
            if (d >= part * weight + 1)
                cnt++;
            weight++;
        }
    }
    cout << cnt + x << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define pb push_back
#define xx first
#define yy second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define Max(x) max_element(all(x))
#define Min(x) min_element(all(x))
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,k,n) for(int i=k;i<n;i++)
#define reppp(i,k,n,m) for(int i=k;i<n;i+=m)
#define repv(i,n) for(int i=n-1;i=0;i--)
#define vi vector<int> 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> iv;
typedef pair<int,int> iip;
typedef map<int,int> mii;
set<int>s;
int ex=0;
void fill(int a){
	if(a>=1 && a<=399)s.insert(0);
	else if(a>=400 && a<=799)s.insert(1);
	else if(a>=800 && a<=1199)s.insert(2);
	else if(a>=1200 && a<=1599)s.insert(3);
	else if(a>=1600 && a<=1999)s.insert(4);
	else if(a>=2000 && a<=2399)s.insert(5);
	else if(a>=2400 && a<=2799)s.insert(6);
	else if(a>=2800 && a<=3199)s.insert(7);
	else ex++;
}
int main(){
	int n,a,ans,plus;
	cin>>n;
	rep(i,n){cin>>a;
		fill(a);}
	cout<<max(1,(int)s.size())<<" "<<(int)s.size()+ex<<endl;
	return 0;
	}

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

int main() {
	char s[11], t[12];
	scanf("%s\n", s);
	scanf("%s", t);
	if (strlen(t) == strlen(s) + 1) {
		t[strlen(s)] = 0;
		if (strcmp(t, s) == 0) {
			printf("Yes");
			return 0;
		}
		printf("No");
		return 0;
	}
	printf("No");

	return 0;
}

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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

int main(){

  ll n;
  while(cin>>n){
    if(n==0)break;
    lb s[n];rep(i,0,n)cin>>s[i];

    lb avg=(lb)accumulate(s,s+n,0)/n;

    lb alf=0;
    rep(i,0,n){
      alf+=(s[i]-avg)*(s[i]-avg);
    }
    alf/=n;
    out(fixed<<setprecision(10)<<pow(alf,0.5));
  }


  return 0;
}



Measured memory_bytes: 3392
fun main(args: Array<String>) {
    val (n, m) = readInputLine().split(" ").map{it.toLong()}
    
    val bridge = mutableListOf<Pair<Int, Int>>()
    
    for (i in 1..m.toInt()) {
        val (a, b) = readInputLine().split(" ").map{it.toInt() - 1}
        bridge.add(Pair(a, b))
    }
    
    val unionFind = UnionFind(n.toInt())
    val ansReversed = LongArray(m.toInt() + 1)

    ansReversed[0] = n * (n - 1L) / 2L

    for ((i, bridgeTmp) in bridge.reversed().withIndex()) {
        val (a, b) = bridgeTmp
        if (unionFind.isSame(a, b)) {
            ansReversed[i + 1] = ansReversed[i]
        } else {
            ansReversed[i + 1] = ansReversed[i] - unionFind.sizeOf(a).toLong() * unionFind.sizeOf(b).toLong()
            unionFind.unite(a, b)
        }
    }
    
    for (ans in ansReversed.reversed().drop(1)) {
        println(ans)
    }
}

fun readInputLine(): String {
    return readLine()!!
}

class UnionFind(n: Int) {
    private val parent = IntArray(n, {-1})
    private val rank = IntArray(n, {0})
    private val size = IntArray(n, {1})
    private var numTree = n
    
    fun find(x: Int): Int {
        if (parent[x] == -1) {
            return x
        } else {
            parent[x] = find(parent[x])
            return parent[x]
        }
    }
    
    fun isSame(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }
    
    fun getSize(): Int {
        return numTree
    }
    
    fun sizeOf(x: Int): Int {
        return size[find(x)]
    }
    
    fun rankOf(x: Int): Int {
        return rank[find(x)]
    }
    
    fun unite(x: Int, y: Int) {
        val parentX = find(x)
        val parentY = find(y)
        
        if (parentX == parentY) {
            return
        }
        
        numTree--
        
        if (rank[parentX] < rank[parentY]) {
            parent[parentX] = parentY
            size[parentY] += size[parentX]
        } else {
            parent[parentY] = parentX
            size[parentX] += size[parentY]
            if (rank[parentX] == rank[parentY]) {
                rank[parentX]++
            }
        }
    }
}


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

int main(void) {
  string str, st, sr;
  cin >> str;
  for (int i = 2; i < str.length(); i += 2) {
    st = str.substr(0, (str.length() - i) / 2);
    sr = str.substr((str.length()-i )/ 2, (str.length() - i) / 2);
    if (st == sr) {
      cout <<  str.length()-i<< endl;
      return 0;
    }
  }
  return 0;
}



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

using namespace std;
int s[maxn],ans,n;
int main(){
    cin >> n; ans=123456;
    for (int i=1;i<=100000;i++) s[i]=s[i/10]+i%10;
    for (int i=1;i<n;i++) ans=min(ans,s[i]+s[n-i]);
    cout << ans << endl;
}


Measured memory_bytes: 640
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, M, *LRC = map(int, open(0).read().split())

    E = [[] for _ in range(N)]
    for i in range(N - 1):
        E[i + 1].append((i, 0))
    for l, r, c in zip(*[iter(LRC)] * 3):
        E[l - 1].append((r - 1, c))

    D = [INF] * N
    D[0] = 0

    Q = [0]
    while Q:
        dist, cur = divmod(heappop(Q), N)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, cand * N + nxt)

    print(-1 if D[N - 1] == INF else D[N - 1])

main()


Measured memory_bytes: 50252
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
int main(){
    int n,t;
    cin>>n>>t;
    vin v(n),w(n);
    rep(i,n)cin>>v[i]>>w[i];
    vvin dp(n+1,vin(t+1));
    rep(i,n+1)dp[i][0]=0;
    rep(i,t+1)dp[0][i]=0;
    rep2(i,1,n+1){
        rep(j,t+1){
            if(j<w[i-1])dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
        }
    }
    cout<<dp[n][t]<<endl;
}


Measured memory_bytes: 6852
#include<iostream>
#include<iomanip>
#include<math.h>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<set>
#include<vector>
using namespace std;

#define INF 1<<21
#define MOD 1000000007

int c[51][200];

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <iomanip>
#include <stdio.h>
#include <bitset>

typedef long long ll;

constexpr long long INFLL = 1e18;

using namespace std;

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

    vector<int> a(n);
    vector<int> b(m);

    for (int i = 0; i < n; i++)
    {
        cin >> a.at(i);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b.at(i);
    }

    vector<ll> c(n + 1);
    vector<ll> d(m + 1);

    c.at(0) = 0;
    for (int i = 1; i <= n; i++)
    {
        c.at(i) = c.at(i - 1) + a.at(i - 1);
    }

    //cout << " ddddddddddddddddddddddddddddddddddddddd" << endl;

    d.at(0) = 0;
    for (int i = 1; i <= m; i++)
    {
        d.at(i) = d.at(i - 1) + b.at(i - 1);
    }

    ll temp;
    int ans = 0;

    vector<ll>::iterator position;
    int dis;

    for (int i = 0; i <= n; i++)
    {
        temp = k - c.at(i);
        if (temp < 0)
        {
            break;
        }
        position = upper_bound(d.begin(), d.end(), temp);
        dis = distance(d.begin(), position) - 1;
        if (ans < dis + i)
        {
            ans = dis + i;
        }
    }

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


Measured memory_bytes: 7564
#include <bits/stdc++.h>
using namespace std;
void input()
{ 
  #ifndef ONLINE_JUDGE 
  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  #endif
}
typedef long long int ll;
#define rep(i,a,b) for( ll i=a;i<b;i++)
#define rrep(i,a,b)for(ll i=a;i>=b;i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define f first
#define s second
#define mod 1000000007
bool compare(pair<int,int>a,pair<int,int>b)
{
  return a.f<b.f;
}
int main()
{
  //input();
  ios_base::sync_with_stdio(0);
    cin.tie(0);
 int n,k;
 cin>>n>>k;
 int df[n]={},arr[n]={};
 rep(i,0,n)cin>>arr[i];

 rep(i,1,n)
 {
  int min1=INT_MAX;
    rep(j,1,k+1)
    {
      if(i-j>=0)
      {
        //cout<<arr[i];
        min1=min(abs(arr[i]-arr[i-j])+df[i-j],min1);
      }
      else break;
    }
  df[i]=min1;
 //cout<<min1<<endl;
 }
cout<<df[n-1]<<endl;
}

///shubham gupta/


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>

using namespace std;

#define r(i, start, end) for (int(i) = (start); (i) < (end); (i)++)
#define rr(i, end, start) for (int(i) = (end); (i) >= (start); i--)
#define len(ar) (sizeof(ar) / sizeof(ar[0]))

int main() {
  int N, L;
  cin >> N >> L;
  string s[100];
  r(i, 0, N) cin >> s[i];
  sort(s, s + N);
  r(i, 0, N) cout << s[i];
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <map>
#include<queue>

const int INF = 1 << 28;
using namespace std;
using Graph = vector<vector<int>>;

template<class T> bool chmin(T &a, T &b) { if (a > b) { a = b; return 1; }return 0; }
template<class T> bool chmax(T &a, T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T, class U> using P = pair<T, U>;

vector<int> seen(50,-1);
int counter_for_dfs = 0;
void dfs(Graph &G, int v) {
	seen[v] = counter_for_dfs;
	counter_for_dfs++;
	for (auto v_next : G[v]) {
		if (seen[v_next]>=0)continue;

		dfs(G, v_next);
	}
}

void bfs(Graph &G) {
	vector<int> dist(G.size(), -1);
	queue<int> que;
	
	dist[0] = 0;
	que.push(0);
	while (!que.empty()) {
		int v = que.front();
		que.pop();

		for (int g : G[v]) {
			if (dist[g] != -1)continue;
			dist[g] = dist[v] + 1;
			que.push(g);
		}
	}
	for (auto i : dist) {
		cout << i << " ";
	}
}

int main()
{
	std::string s;
	int n;
	std::cin >> n;
	int counter = 0;
	for (int i = 1; i <= n; i++) {
		s = to_string(i);
		counter = s.length() % 2 == 1 ? counter+1 : counter;
	}

	std::cout << counter;
   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;

vector<int> ans[100000];

int main()
{
	int N, num;
	bool ok = false;

	cin >> N;

	for (int i = 1; i * (i + 1) <= 2 * N; i++) {
		if (i * (i + 1) == 2 * N) {
			ok = true;
			num = i;
			break;
		}
	}

	if (!ok) cout << "No" << endl;
	else {
		cout << "Yes" << endl;

		rep(i, num + 1) ans[i].resize(num);

		int offset = 0;
		int h = 0;
		int w = 0;
		repc(i, 1, N) {
			if (w >= num) {
				h++;
				offset++;
				w = offset;
			}
			ans[h][w] = i;
			w++;
		}

		offset = 1;
		h = 1;
		w = 0;

		repc(i, 1, N) {
			if (h >= num + 1) {
				w++;
				offset++;
				h = offset;
			}
			ans[h][w] = i;
			h++;
		}

		cout << num + 1 << endl;
		rep(i, num + 1) {
			cout << num;
			rep(j, num) cout << ' ' << ans[i][j];
			cout << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 4480
n,m = map(int,input().split())
p = list(map(int,input().split()))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.union(x-1,y-1)
ans = 0
for i in range(n):
    if uf.find(i) == uf.find(p[i]-1):
        ans += 1
print(ans)

Measured memory_bytes: 13812
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int n,m,dp[100005],ans;
vector<int>g[100005],cm;
bool vis[100005];
void dfs(int v){
    vis[v]=true;
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(!vis[u])dfs(u);
    }
    cm.PB(v);
}
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[--a].PB(--b);
    }
    for(int i=0;i<n;i++)if(!vis[i])dfs(i);
    for(int i=cm.size()-1;i>=0;i--){
        int v=cm[i];
        for(int j=0;j<g[v].size();j++){
            dp[g[v][j]]=max(dp[g[v][j]],dp[v]+1);
        }
        ans=max(ans,dp[v]);
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 8056
import sys

N = int(sys.stdin.readline().rstrip())  # 節点数

parents = [None] * N
depth = [None] * N
type_ = [None] * N
children = [None] * N

CHs = [None] * N


# ## DFS ## #


def dfs(u, d, r=-1):

    # u を訪れたときの処理
    # parents[u] = r
    depth[u] = d
    c = []
    tmp = "leaf"

    for v in CHs[u]:
        if v == r:
            continue  # 親は無視
        tmp = "internal node"
        dfs(v, d + 1, u)  # 子の探索
        c.append(v)

    # u を離れる前の処理
    if r == -1:
        tmp = "root"
    type_[u] = tmp
    children[u] = c


def main():
    for i in range(N):
        id, k, *ch = map(int, sys.stdin.readline().rstrip().split())
        for p in ch:
            parents[p] = id
        CHs[id] = ch

    # 根を見つける
    u = 0
    while True:
        if parents[u] is None:
            root = u
            parents[u] = -1
            break
        u = parents[u]

    dfs(root, 0)

    for i in range(N):
        print(f"node {i}: parent = {parents[i]}, depth = {depth[i]}, {type_[i]}, {children[i]}")


main()



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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) (a).begin(),(a).end()
#define SORT(a) sort(all(a))
#define rSORT(a, i) sort(all(a),(i))

using ll = long long;
constexpr ll INF = 10000000000;
constexpr ll MOD = 1000000007;
const int MAX_N = 110000; 
constexpr double EPS = 1E-11;

using namespace std;

//fixed << setprecision(10)

int main() {
	ll n, k; cin >> n >> k;
	vector<ll>x(n);
	rep(i, n)cin >> x[i];

	vector<ll>dis;

	rep(i, n - k + 1) {
		ll g = abs(x[i] - x[i + k - 1]) + abs(x[i]);
		dis.push_back(g);
		ll h = abs(x[i + k - 1] - x[i]) + abs(x[i + k - 1]);
		dis.push_back(h);
	}
	/*
	rep(i, dis.size()) {
		cout << dis[i] << endl;
	}
	*/
	sort(all(dis));
	cout << dis[0] << endl;
}

Measured memory_bytes: 2168
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;
  string t;
  int c;
  int max;
  c = 0;
  max = 0;

  cin >> t;

  for(ii=0;ii<3;ii++){
    if(ii != 0 && t[ii-1] == 'R' && t[ii] == 'R'){
      c++;
    }
    else if(ii != 0 && t[ii-1] != 'R' && t[ii] == 'R'){
      c = 1;
    }
    else if(ii == 0 && t[ii] == 'R'){
        c++;
    }

    if(max < c){
      max = c;
    }
  }

  cout << max << endl;
  
  return 0;
}


Measured memory_bytes: 3616
N, K = map(int, input().split())
P = list(map(int, input().split()))

acc = [0] * (N+1)
for i in range(0, N):
    acc[i+1] = acc[i] + P[i]

ans = 0
for i in range(0, N-K+1):
    tmp = acc[i+K] - acc[i]
    if tmp > ans:
        ans = tmp
    
print((ans+K)/2)


Measured memory_bytes: 24804
#include <stdio.h>
#include <algorithm>
using namespace std;

#define INF 1e8

int a[222][222], r[11], check[11], prm[11], R, ans = INF;

void update(void)
{
    int i, sum = 0;

    for (i = 1; i < R; i++)
		sum += a[prm[i]][prm[i + 1]];

    ans = min(ans, sum);
}

void permutation(int lev)
{
	if (lev > R)
	{
		update();
		return;
	}

    int i;

    for (i = 1; i <= R; i++)
		if (!check[i])
		{
			check[i] = 1;
			prm[lev] = r[i];
			permutation(lev + 1);
			check[i] = 0;
		}
}

int main(void)
{
    int N, M, i, j, k;

    scanf("%d %d %d" ,&N, &M, &R);
	for (i = 1; i <= R; i++)
		scanf("%d" ,&r[i]);

    for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
            if (i != j)
				a[i][j] = INF;

    while (M--)
	{
		int x, y, z;

		scanf("%d %d %d" ,&x, &y, &z);

        a[x][y] = a[y][x] = min(a[x][y], z);
	}

    for (k = 1; k <= N; k++)
		for (i = 1; i <= N; i++)
			for (j = 1; j <= N; j++)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

	permutation(1);

	printf("%d" ,ans);
	return 0;
}

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

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
typedef long long ll;
typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> pii;typedef vector<pii> vpii;

void Main() {
  int N;
  scanf("%d", &N);
  vi E, O;
  rep(i, N) {
    int a;
    scanf("%d", &a);
    if (i % 2) O.push_back(a);
    else E.push_back(a);
  }

  sort(ALL(O));
  sort(ALL(E));

  int ans = 0;
  int n = 0;
  int o = 0, e = 0;

  int NO = SZ(O);
  int NE = SZ(E);

  while (o < NO || e < NE) {
    bool turn_o = n % 2;
    bool use_o;

    if (o < NO && e < NE) {
      if (O[o] < E[e]) use_o = 1;
      else use_o = 0;
    }
    else if (o < NO) {
      use_o = 1;
    }
    else if (e < NE) {
      use_o = 0;
    }
    else assert(0);

    if (use_o) {
      o++;
      if (!turn_o) ans++;
    }
    else {
      e++;
      if (turn_o) ans++;
    }
    n++;
  }

  _p("%d\n", ans / 2);
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }


Measured memory_bytes: 892