akhauriyash/Code-Regression huggingface dataset:
package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
  "strings"
)

var graph [][]int
var used []bool

func main() {
  var n,m int = NextInts()
  graph = make([][]int,n)
  used = make([]bool,n)
  for i:=0;i<m;i++ {
    var a,b int = NextInts()
    graph[a-1] = append(graph[a-1],b-1)
    graph[b-1] = append(graph[b-1],a-1)
  }
  var to,fm,path []int
  to = dfs(0,to)
  fm = dfs(0,fm)
  for i:=len(to)-1;i>0;i-- {
    path = append(path,to[i])
  }
  path = append(path,1)
  for i:=1;i<len(fm);i++ {
    path = append(path,fm[i])
  }
  fmt.Println(len(path))
  fmt.Print(path[0])
  for i:=1;i<len(path);i++ {
    fmt.Print(" ")
    fmt.Print(path[i])
  }
  fmt.Println()
}

func dfs(v int,p []int) []int {
  p = append(p,v+1)
  used[v] = true
  for _,e := range graph[v] {
    if used[e] { continue }
    return dfs(e,p)
  }
  return p
}

var reader = bufio.NewReaderSize(os.Stdin,1000000)
func NextLine() string {
  var line,buffer []byte
  var isPrefix bool = true
  var err error
  for isPrefix {
    line,isPrefix,err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
  }
  return string(buffer)
}
func NextInts() (int,int) {
  var s []string = strings.Split(NextLine()," ")
  a,_ := strconv.Atoi(s[0])
  b,_ := strconv.Atoi(s[1])
  return a,b
}

Measured memory_bytes: 36736
import java.util.*
import kotlin.*

import java.io.InputStream
import java.lang.NumberFormatException
import java.lang.StringBuilder


fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = FastScanner()
        val x = sc.nextLong()
        val y = sc.nextLong()
        var ans = 0
        var t = x
        while (t <= y){
            t *=2
            ans++
        }
        println(ans)
    }
}


class FastScanner {
    companion object {
        val input: InputStream = System.`in`
        val buffer = ByteArray(1024) { 0 }
        fun isPrintableChar(c: Int): Boolean = c in 33..126
    }

    var ptr = 0
    var buflen = 0
    private fun hasNextByte(): Boolean {
        if (ptr < buflen) {
            return true
        } else {
            ptr = 0
            buflen = input.read(buffer)
            if (buflen <= 0) {
                return false
            }
        }
        return true
    }

    private fun readByte(): Int = if (hasNextByte()) buffer[ptr++].toInt() else -1

    private fun skipUnprintable() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr].toInt())) ptr++
    }

    fun hasNext(): Boolean {
        skipUnprintable()
        return hasNextByte()
    }

    fun next(): String {
        if (!hasNext()) throw NoSuchElementException()
        val sb = StringBuilder()
        var b = readByte()
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b)
            b = readByte()
        }
        return sb.toString()
    }

    fun nextInt(): Int {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0
        var b = readByte()
        // '-' = 45
        val minus = b == 45
        if (minus) {
            b = readByte()
        }

        // '0' = 48 '9' = 57
        if (b !in 48..57) {
            throw NumberFormatException()
        }

        while (true) {
            if (b in 48..57) {
                n *= 10
                n += b - 48
            } else if (b == -1 || !isPrintableChar(b)) {
                return if (minus) -n else n
            } else {
                throw NumberFormatException()
            }
            b = readByte()
        }
    }

    fun nextLong(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var b = readByte()
        // '-' = 45
        val minus = b == 45
        if (minus) {
            b = readByte()
        }

        // '0' = 48 '9' = 57
        if (b !in 48..57) {
            throw NumberFormatException()
        }

        while (true) {
            if (b in 48..57) {
                n *= 10
                n += b - 48
            } else if (b == -1 || !isPrintableChar(b)) {
                return if (minus) -n else n
            } else {
                throw NumberFormatException()
            }
            b = readByte()
        }
    }

    fun nextDouble(): Double = next().toDouble()
}


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

class UnionFind {
private:
  vector<int> par;  // 隕ェ
  vector<int> rank; // 譛ィ縺ョ豺ア縺?

public:
  // n隕∫エ?〒蛻晄悄蛹?
  UnionFind(int n) {
    par.resize(n);
    rank.resize(n);
    for(int i = 0; i < n; ++i) {
      par[i] = i;
      rank[i] = 0;
    }
  }
  
  // 譛ィ縺ョ譬ケ繧呈アゅａ繧?
  int find(int x) {
    if(par[x] == x) {
      return x;
    } else  {
      return par[x] = find(par[x]);
    }
  }

  // x縺ィy縺悟酔縺倬寔蜷医↓螻槭☆繧九°蜷ヲ縺?
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  
  // x縺ィy縺ョ螻槭☆繧矩寔蜷医ｒ菴オ蜷?
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    
    if(rank[x] < rank[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if(rank[x] == rank[y]) ++rank[x];
    }
  }
};

const int INF = 1<<28;

struct Edge {
  int a, b, w;
  bool operator < (const Edge &e) const {
    return w < e.w;
  }
};

int main() {
  for(int n, m; cin >> n >> m && (n|m);) {
    vector<Edge> es;
    for(int i = 0; i < m; ++i) {
      int a, b, w; cin >> a >> b >> w;
      es.push_back((Edge){--a, --b, w});
    }
    sort(es.begin(), es.end());
    int res = INF;
    for(int i = 0; i < es.size(); ++i) {
      int low = es[i].w, high = low, cnt = 0;
      UnionFind uf(n);
      for(int j = i; j < es.size(); ++j) {
        int a = es[j].a, b = es[j].b, w = es[j].w;
        if(!uf.same(a, b)) {
          uf.unite(a, b);
          high = w;
          ++cnt;
        }
      }
      if(cnt == n-1) {
        res = min(res, high - low);
      }
    }
    if(res == INF) res = -1;
    cout << res << endl;
  }
  return 0;
}

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

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

    int x;
    cin >> x;
    int ans = 0;
    ans += x / 500 * 1000;
    x %= 500;
    ans += x / 5 * 5;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define maxheap priority_queue<int>
#define minheap priority_queue<int, vector<int>, greater<int> >
#define ll long long
const int INF = 1e8;
const int MAXN = 3e5 + 200;
const  long double eps = 1e-16;
const long double pi = acos(-1.0);
using namespace std;

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


int n, k;
bool bad[10];
bool check(int x){
    string s = to_string(x);
    for (int i = 0; i < s.length(); i++)
        if (bad[s[i] - '0']) return false;
        return true;
}
void solve(){
    cin >> n >> k;
    for (int i = 0; i < k; i++){
        int x;
        cin >> x;
        bad[x] = true;
    }
    for (int i = n; i <= 10 * n + 1; i++){
        if (check(i)){
            cout << i << endl;
            return;
        }
    }
}
/*
 4 4
 abdc
 defg
 aefg
 bdce
 */
int main(){
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(7);
    //freopen("inevit.in", "r", stdin);
    //freopen("inevit.out", "w", stdout);
    int step;
    step = 1;
    //cin >> step;
    for (int i = 1; i <= step; i++)
        solve();

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define sz(x) (int)(x).size()
#define _USE_MATH_DEFINES
using namespace std;
typedef long long int lli;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

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

    int n;
    cin >> n;
    vi v(n);
    rep(i, 0, n) cin >> v[i];
    ll oc = 0, sum1 = 0, ec = 0, sum2 = 0;
    rep(i, 0, n) {
        sum1 += v[i];
        if (i % 2 == 0) {
            while (0 <= sum1) {
                sum1--;
                oc++;
            }
        }
        else {
            while (sum1 <= 0) {
                sum1++;
                oc++;
            }
        }
    }
    rep(i, 0, n) {
        sum2 += v[i];
        if (i % 2 == 0) {
            while (sum2 <= 0) {
                sum2++;
                ec++;
            }
        }
        else {
            while (0 <= sum2) {
                sum2--;
                ec++;
            }
        }
    }
    cout << min(oc, ec) << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int inf = 10001;
int main() {
  int n;
  cin >> n;
  vector<bool> v(inf);
  v[0] = true;
  rep(_,n){
    int s;
    cin >> s;
    vector<bool> v2 = v;
    rep(i,inf-s) if(v[i]) v2[i+s] = true;
    v = v2;
  }
  int ans = 0;
  rep(i,inf) if(v[i]&&i%10>0) ans = i;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define REP(i,n) for(ll i=0;i<n;i++)
#define SZ(v) (ll)v.size()
#define endl "\n"
#define ff first
#define ss second
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const ll INF=1e29;
const ll MOD=1e9+7;
const ll nxm=2e7+5;
bool c(pair<ll,ll> a,pair<ll,ll> b){    return a.ss>b.ss;    }
bool sgn(ll a){ if(a>=0) return 1 ;return 0;}
void solve()
{
ll x,y;
cin>>x>>y;
ll t=(y-2*x)/2;
ll c=x-t;
if((y-2*x)%2==0)
{
    if(t>=0 && c>=0)
    {
        cout<<"Yes";
    }
    else
        cout<<"No";
}
else
    cout<<"No";
}
int main(){
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t=1;
//	cin>>t;
	while(t--){
		solve();
	}


	return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <time.h>

#define rep(num)      for (long long _ = 0; _ < num; _++)
#define loop(i, num)  for (long long i = 0; i < num; i++)

using namespace std;

int n;

vector<bool> vis;

vector<vector<int>> nei, dis;

void bfs(int from, int mem) {
    
    queue<int> cur;
    
    cur.push(from);
    
    dis[mem][from] = 0;
    
    while (!cur.empty()) {
        
        int c = cur.front();
        
        vis[c] = 1;
        
        cur.pop();
        
        loop (i, nei[c].size()) {
            
            if (!vis[nei[c][i]]) {
                
                cur.push(nei[c][i]);
                
                dis[mem][nei[c][i]] = min(dis[mem][nei[c][i]], dis[mem][c] + 1);
                
            }
            
        }
        
    }
    
}

int main() {
    
    cin >> n;
    
    nei.resize(n + 1);
    
    vis.resize(n + 1);
    
    dis.resize(2, vector<int>(n + 1, 1e9));
    
    loop (i, n - 1) {
        
        int p1, p2;
        
        cin >> p1 >> p2;
        
        nei[p1].push_back(p2);
        
        nei[p2].push_back(p1);
        
    }
    
    bfs(1, 0);
    
    loop (i, n + 1) {
        
        vis[i] = 0;
        
    }
    
    bfs(n, 1);
    
    int f = 0, s = 0;
    
    for (int i = 1; i <= n; i++) {
        
        if (dis[0][i] > dis[1][i]) {
            
            ++s;
            
        } else {
            
            ++f;
            
        }
        
    }
    
//    loop (i, n + 1) {
//
//        cout << dis[0][i] << ' ';
//
//    }
//
//    cout << endl;
//
//    loop (i, n + 1) {
//
//        cout << dis[1][i] << ' ';
//
//    }
//
//    cout << endl;
    
//    cout << f << ' ' << s << endl;
    
    if (s >= f) {
        
        cout << "Snuke" << endl;
        
    } else {
        
        cout << "Fennec" << endl;
        
    }
    
}


Measured memory_bytes: 6540
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define add push_back
#define endl "\n"
const double PI = acos(-1);
using ll = long long;
using namespace std;

int n, a[101], d;
ll sm;
int main() {
    cin >> n;
    a[0] = 1e9;
    for (int i = 0; i < n-1; ++i) {
        cin >> d;
        a[i] = min(a[i], d);
        a[i+1] = d;
        sm += a[i];
    } 
    sm += a[n-1];
    cout << sm << endl;

    return 0;
}





Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <cmath>
#include <functional>
#include <set>
#include <string>
#include <stdlib.h>
#include <iomanip>
#include <utility>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define ii pair<int,int>
#define mp make_pair
#define pb push_back
#define iii pair<ii,int >
#define ff first
#define ss second
#define vi vector<int>
#define vc vector<char>
 
using namespace std;
const int MOD = 1000000007;
int matrix[30][30];
const int MAXN = 21;
int n;
ll dp[MAXN][(1<<(MAXN)) +1];

ll DP(int ID,int usable_mask){
	if(ID == n)return 1;
	//cout << "lal : " << dp[ID][usable_mask] << endl;
	if(dp[ID][usable_mask] != -1)return dp[ID][usable_mask];
	ll sum = 0;
	FOR(i,n){
		//cout << "d" << endl;
		if((usable_mask&(1<<i))>0){
			//cout << "why" << endl;
			if(matrix[ID][i] == 1){
				//cout << " hha" << endl;
				sum += DP(ID+1,usable_mask^(1<<i));
				sum%=MOD;
			}
		}
	}
	dp[ID][usable_mask] = sum;
	return sum;
}


int main(){
	
	cin >> n;
	FOR(i,n)FOR(j,n)cin >> matrix[i][j];
	FOR(i,n){
		FOR(j,(1<<(MAXN)))dp[i][j] = -1;
	}
	//cout << ((1 << (n)) - 1 )<< endl;
	cout << DP(0,(1<<(n))-1) << endl;
	return 0;
}


Measured memory_bytes: 344320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>

#define ABS(x) ((x)>0?(x):-(x))

using namespace std;
unsigned long long int newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}
int main()
{
	queue<pair<int,int> > q;
	int H,W,i,j,k;
	char s[1024][1024] = {0};
	cin >> H >> W;
	for(i=0;i<H;++i)
	{
		cin >> s[i];
	}
	int pos;
	for(i=0;i<H;++i)
	{
		pos = i*W;
		for(j=0;j<W;++j)
		{
			if(s[i][j] == '#')
			{
				q.push(make_pair(pos+j,0));
			}
		}
	}
	int mx = 0,act;
	int x,y;
	while(!q.empty())
	{
		pos = q.front().first;
		act = q.front().second;
		if(act > mx)
			mx = act;
		x = pos % W;
		y = pos / W;
		q.pop();
		if(y > 0)
		{
			if(s[y - 1][x]=='.')
			{
				s[y - 1][x] = '#';
				q.push(make_pair((y-1)*W+x, act+1));
			}
		}

		if(y < H-1)
		{
			if(s[y + 1][x]=='.')
			{
				s[y + 1][x] = '#';
				q.push(make_pair((y+1)*W+x, act+1));
			}
		}

		if(x > 0)
		{
			if(s[y][x - 1]=='.')
			{
				s[y][x - 1] = '#';
				q.push(make_pair(y*W+x-1, act+1));
			}
		}

		if(x < W-1)
		{
			if(s[y][x+1]=='.')
			{
				s[y][x+1] = '#';
				q.push(make_pair(y*W+x+1, act+1));
			}
		}
	}
	cout << mx << endl;
	return 0;
}









Measured memory_bytes: 9488
#include<bits/stdc++.h>
using namespace std;
int64_t f(int64_t x,int64_t y){
int64_t m=min(x,y);
  int64_t M=max(x,y);
  if(M%m==0)
    return 2*M-m;
  else{
  return 2*(M/m)*m+f(m,M%m);
  }

}
int main(){
int64_t N,X;
  cin>>N>>X;
  int64_t ans=N+f(X,N-X);
  cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<algorithm>
#include<cstdint>

//RAQ 
class LazySegmentTree{
private:
    using Int = int_fast64_t;
    std::vector<Int> arr;
    std::vector<Int> lazy;
    size_t size;
public:
    LazySegmentTree(size_t range){
        size = 1;
        while(size < range) size <<= 1;
        arr.assign(2*size-1, 0);
        lazy.assign(2*size-1, 0);
    }
    LazySegmentTree(const std::vector<Int>& vec){
        size = 1;
        while(size < vec.size()) size <<= 1;
        arr.assign(2*size-1, 0);
        lazy.assign(2*size-1, 0);
        for(size_t i = 0; i < vec.size(); ++i) arr[i+size-1] = vec[i];
        for(size_t i = size-2; i >= 0; i--) arr[i] = arr[2*i+1] + arr[2*i+2];
    }

    void eval(size_t idx, size_t l, size_t r){
        if(lazy[idx] == 0) return;
        arr[idx] += lazy[idx];
        if(r - l > 1){
            lazy[2*idx+1] += lazy[idx] / 2;
            lazy[2*idx+2] += lazy[idx] / 2;
        };
        lazy[idx] = 0;
    }

    void add(size_t L, size_t R, Int x, size_t idx=0, size_t l=0, size_t r=1e9+7){
        if(r > 1e9) r = size;

        eval(idx, l, r);
        if(r <= L || R <= l) return;
        if(L <= l && r <= R) {
            lazy[idx] += (r - l) * x;
            eval(idx, l, r);
        } else {
            add(L, R, x, 2*idx+1, l, (l+r)/2);
            add(L, R, x, 2*idx+2, (l+r)/2, r);
            arr[idx] = arr[2*idx+1] + arr[2*idx+2];
        }
    }

    Int sumQuery(size_t L, size_t R, size_t idx=0, size_t l=0, size_t r=1e9+7){
        if(r > 1e9) r = size;
        if(r <= L || R <= l) return 0;

        eval(idx ,l ,r);
        if(L <= l && r <= R) return arr[idx];
        Int sum = 0;
        sum += sumQuery(L, R, 2*idx+1, l, (l+r)/2);
        sum += sumQuery(L, R, 2*idx+2, (l+r)/2,r);
        return sum;
    }
};
#include<iostream>
using namespace std;
int main(){
    int N,Q;
    cin >> N >> Q;

    LazySegmentTree LazySeg(N);
    for(size_t q = 0; q < Q; q++){
        size_t com, s, t, x;
        cin >> com >> s >> t;
        s--, t--;
        if(!com) {
            cin >> x;
            LazySeg.add(s, t+1, x);
        } else {
            cout << LazySeg.sumQuery(s, t+1) << endl;
        }
    }
}



Measured memory_bytes: 7068
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;

int main()
{
	string s;
	cin >> s;
	vector<int> alp(26);
	int n = s.size();
	string ext = "";
	deque<int> xsum;
	int cnt = 0;
	rep(i, n)
	{
		if (s[i] != 'x')
		{
			ext.push_back(s[i]);
			xsum.push_back(cnt);
			cnt = 0;
		}
		else
		{
			cnt++;
		}
	}

	xsum.push_back(cnt);

	bool ok = true;
	int m = ext.size();

	rep(i, ext.size() / 2)
	{
		if (ext[i] != ext[m - 1 - i])
		{
			ok = false;
		}
	}
	if (ok)
	{
		if (m == 0)
		{
			cout << 0 << endl;
		}
		else
		{
			int ans = 0;
			m = xsum.size();
			//	cout<<m<<endl;
			rep(i, m / 2)
			{
				ans +=abs(xsum[i]-xsum[m - 1 - i]);
			}
			cout << ans << endl;
		}
	}
	else
	{
		cout << -1 << endl;
	}
}


Measured memory_bytes: 896
#include<algorithm> 
#include<cstdio>
#include<iostream>
#define inver(a) power(a,mod-2)
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int fac[2050];
int fac_inv[2050];
int add(int x)
{
	return x>=mod?x-mod:x; 
}
LL power(LL x,LL y)
{
	LL re=1;
	while(y)
	{
		if(y&1) re=re*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return re;
}
LL C(int x,int y)
{
	return (LL)fac[x]*fac_inv[y]%mod*fac_inv[x-y]%mod;
}
int n,m;
int p2[2050];
bool mark[2050];
LL X;
LL v[2050];
namespace us
{
	int fa[1050];
	void init()
	{
		for(int i=1;i<=n;++i)
		{
			fa[i]=i;
		}
	}
	int find(int a)
	{
		return fa[a]==a?a:fa[a]=find(fa[a]); 
	}
	bool merge(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(a==b)
		{
			return false;
		}
		fa[a]=b;
		return true;
	}
}
struct edge
{
	int u,v,w;
	bool operator <(const edge &other) const
	{
		return w<other.w;
	}
} e[2050];
LL kruskal(int ban)
{
	LL MST=0;
	us::init();
	if(ban)
	{
		us::merge(e[ban].u,e[ban].v);
		MST+=e[ban].w;
	}
	for(int i=1;i<=m;++i)if(i!=ban)
	{
		if(us::merge(e[i].u,e[i].v))
		{
			MST+=e[i].w;
			if(ban==0)
			{
				mark[i]=1;
			}
		}
	}
	return MST;
}
void init(int n)
{
	p2[0]=1;
	for(int i=1;i<=n;++i)
	{
		p2[i]=add(p2[i-1]<<1);
	}
	fac[0]=1;
	for(int i=1;i<=n;++i)
	{
		fac[i]=(LL)fac[i-1]*i%mod;
	}
	fac_inv[n]=inver(fac[n]);
	for(int i=n;i>=1;--i)
	{
		fac_inv[i-1]=(LL)fac_inv[i]*i%mod;
	} 
}
int calc()
{
	int p=n-1;
	int re=0;
	for(int i=1;i<p;++i)
	{
		re=add(re+C(p,i));
	}
	re=(LL)re*p2[m-p]%mod;
	return re;
}
int solve()
{
	init(m);
	for(int i=0;i<=m;++i)
	{
		v[i]=kruskal(i);
	}
	int an=0;
	if(v[0]==X)
	{
		an=calc();
	}
	for(int i=1;i<=m;++i) if(!mark[i])
	{
		if(v[i]==X)
		{
			int t=1;
			for(int j=1;j<=m;++j) if(!mark[j])
			{
				if(v[j]>v[i]||(v[j]==v[i]&&j>i))
				{
					++t;
				}
			}
			an=add(an+p2[t]);
		}
	}
	return an;
}
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%lld",&X);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+m+1);
	printf("%d\n",solve());
	return 0;
}

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

using namespace std;

int main(){
  int N; cin>>N;
  string S(N,'A'); 
  bool check=true;
  for(int i=0;i<N;i++) cin>>S[i];
  for(int i=0;i<S.size();i++){
    if(S[i]=='Y') check=false;
  }

  if(check) cout<<"Three"<<endl;
  else cout<<"Four"<<endl;

  return 0;
}


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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int P[7] = {0};

int main(int argc, char* argv[]){
	int N;

	cin >> N;
	for(int i=1; i<=N; i++){
		string str;
		cin >> str;
		char c = str.at(0);
		if(c == 'M'){ P[0]++; }
		else if(c == 'A'){ P[1]++; }
		else if(c == 'R'){ P[2]++; }
		else if(c == 'C'){ P[3]++; }
		else if(c == 'H'){ P[4]++; }
	}

	long long ans = 0;
	for(int b = 1; b < (1<<5); b++){
		int bitc = 0;
		long long tmp = 1;
		for(int j=0; j<5 && bitc<=3 ; j++){
			if( b & (1<<j) ){
				bitc++;
				tmp = tmp * (long long)P[j];
			}
		}
		if(bitc == 3){
			ans += tmp;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    int N; cin >> N;
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int counter = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) {
                counter++;
            }
        }
        if (i % 2 == 1 && counter == 8) {
            ans++;
        }
    }
    cout << ans << endl;
}


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

int main(){
    int a, b;
    cin >> a >> b;
    while(!(a==0 && b==0)){
        if(a<=b)
            cout << a << " " << b << endl;
        else
            cout << b << " " << a << endl;
        cin >> a >> b;
    }
    return 0;
}


Measured memory_bytes: 3012
s = input()

def reverse(string):
  return ''.join(reversed(string))

def split_and_join(string, word):
  return ''.join(string.split(word))

s_r = reverse(s)
ls = ["eraser", "erase", "dreamer", "dream"]
ls_r = []
for item in ls:
  ls_r.append(reverse(item))

for word_r in ls_r:
  s_r = split_and_join(s_r, word_r)
  
ans = "YES" if s_r == '' else "NO"

print(ans)

Measured memory_bytes: 3956
#include<iostream>
#include<string>
#include<cctype>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
	int n;
	char x, c;
	string s;
	int cnt_a=0,cnt_b=0,cnt_o=0,cnt_ab=0;
	while(cin >> n >> x >> s){
//	cout << n << x << s << endl;
//	transform(s.begin(),s.end(),s.begin(),toupper)
	if(s=="A"){
		cnt_a++;
	}
	else if(s=="B"){
		cnt_b++;
	}
	else if(s=="O"){
		cnt_o++;
	}
	else if("AB"){
		cnt_ab++;
	}
}
	cout<<cnt_a <<endl<<cnt_b<<endl<<cnt_ab<<endl<<cnt_o<<endl;

}

Measured memory_bytes: 1204
object methods {
  def solver: Unit = {
    val scanner = new java.util.Scanner(System.in)
    val tempList: Seq[Seq[String]] = {
      for(line <- io.Source.stdin.getLines()) yield {
        line.split(' ').toSeq
      }
    }.toSeq

    val num: Int = tempList(0)(0).toInt
    
    val calc: Int = num + num*num + num*num*num  


    println(calc)
  }
}

object Main extends App {
  methods.solver
}

Measured memory_bytes: 55528
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))


int main(){
	int n,t,f;
	int h[101];
	for(;;){
		scanf("%d",&n);
		if(!n)break;
		n++;
		rep(i,n)scanf("%d",i+h);
		rep(i,n){
			f=1;
			t=h[1+(i<2)]-h[i==0];
			rep(j,n-2){
				if(t!=h[j+1+(j+1>=i)]-h[j+(j>=i)]){
					f=0;
					break;
				}
			}
			if(f){
				printf("%d\n",h[i]);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1192
#include <stdio.h>
 
int main()
{
 
  int x, y, r, d;
 
  scanf("%d %d", &x,&y);
 
  if(x<y){
    d = x;
    x = y;
    y = d;
  }
 
  r = x % y;
  while(r!=0){
    x = y;
    y = r;
    r = x % y;
  }
 
  printf("%d\n", y);
 
  return 0;
}

Measured memory_bytes: 592
import java.util.*;

public class Main {
	long K, A, B;

	long calc() {
		long result = 0;
		if ((double) (B - A) / 2 > 1.0) {
			long times = K - (A - 1);
			if (times <= 0) {
				result = 1 + K;
			} else {
				result = A + (times / 2 * (B - A)) + (times % 2) * 1;
			}
		} else {
			result = K + 1;
		}
		return result;
	}

	Main() {
		Scanner in = new Scanner(System.in);
		String[] tokens = in.nextLine().split(" ");
		K = Long.parseLong(tokens[0]);
		A = Long.parseLong(tokens[1]);
		B = Long.parseLong(tokens[2]);
		in.close();
	}

	public static void main(String[] args) {
		Main ins = new Main();
		System.out.println(ins.calc());
	}

}

Measured memory_bytes: 26708
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = LI()
B = LI()
C = LI()

ans = sum(B)
pre = -1
for a in A:
    if pre + 1 == a:
        ans += C[pre-1]
    pre = a

print(ans)


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

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

using namespace std;

/////////////////////////////////////////////////////
ll N,M;
ll k[20], s[20][20], p[20];
ll i, j;
ll onf[20];
ll ans;
bool ck(){
    ll i, j;
    fornum(i,0,M){
        ll ct = 0;
        fornum(j,0,k[i]){
            ct += onf[s[i][j]];
        }
        
        if(ct%2!=p[i]){
            //printf("%lld,%lld,%lld\n", i, onf[0], onf[1]);
            return false;
        }
    }
    return true;
}
void znts(ll ii){
    if(ii>N){
        if(ck()){
            ans++;
        }
        return;
    }
    znts(ii + 1);
    onf[ii] = 1;
    znts(ii + 1);
    onf[ii] = 0;
}
int main(){
    scanf("%lld%lld", &N,&M);
    fornum(i,0,M){
        scanf("%lld", &k[i]);
        fornum(j,0,k[i]){
            scanf("%lld", &s[i][j]);
        }
    }
    fornum(i,0,M){
        scanf("%lld", &p[i]);
    }
    znts(1);
    printf("%lld", ans);
    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);
		String[] s = sc.next().split("");
		int indexA = 0;
		int indexZ = 0;
		boolean top = true;
		for (int i = 0; i < s.length; i++) {
			if (s[i].equals("A") && top) {
				indexA = i;
				top = false;
			}
			if (s[i].equals("Z"))
				indexZ = i;
		}
		System.out.println(indexZ - indexA + 1);
	}
}

Measured memory_bytes: 53476
#include <iostream>

using namespace std;

int main(){
    int R, G, B, N;
    cin >> R >> G >> B >> N;

    int count = 0;
    int max_r, max_g, max_b;
    max_r = N / R;
    max_g = N / G;
    max_b = N / B;

    for (int i = 0; i < max_r + 1; i++){
        for (int j = 0; j < max_g + 1; j++){
            if ((N - (R * i + G * j)) % B == 0 and N - (R * i + G * j) >= 0)
            {
                count++;
            }
            
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 256
import java.io.PrintWriter
val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val nums = listOfInt()
    val max = nums.max()!!

    val k = nextInt()
    println((max * Math.pow(2.0, k.toDouble()) + nums.sum() - max).toInt())
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { it.toInt() }

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 36048
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define in insert
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n, q;
    cin >> n >> q;
    int a[n];
    int cnt = 0;
    string s;
    cin >> s;
    int l, r;
    for(int i = 0; i < n; i++){
        if(s[i] == 'C' && s[i-1] == 'A') cnt++;
        a[i] = cnt;
    }
    forn(i, q){
        cin >> l >> r;
        cout << a[r-1]- a[l-1] << endl;
    }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
struct P
{
    int x,y,z;
    bool operator<(const P &a)const{
        //if(y!=a.y) return y<a.y;
        return y>a.y;
    }
};
vector<P> v1,v2;
vector<int> v;
//bitset<4001000> b;
int i,n,d,m,k,a,b,c,e;
int o[211111];
int l[211111];
int j[1];

int dx[10]={0,1,0,-1,1,1,-1,-1},dy[10]={1,0,-1,0,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};
int px[10]={-1,1,1,-1,1,1,-1,-1},py[10]={1,1,-1,-1,1,-1,1,-1};
long long mod=1000000007,mod2=1000000009,mod3=2017;
long long x,z,y;
double pi=3.14159265;
P u[1];
stack<int> s;
//set<int> s,s1;

priority_queue<P> q;
//queue<int> q;
//string r;

char r[211111],r2[1];
//2147483647
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,int> p;
//v.resize(unique(v.begin(),v.end())-v.begin());

bool as(P a,P b)
{

    return a.y<b.y;
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//rng();



int main()
{
    scanf("%d %s",&a,r+1);
    for(int t=1;t<=a;t++)
        if(r[t]=='.') o[t]++;
        else l[t]++;
    for(int t=1;t<=a;t++)
        l[t]+=l[t-1];
    for(int t=a;t>0;t--)
        o[t]+=o[t+1];
    k=l[a];
    for(int t=1;t<=a;t++)
        k=min(k,l[t-1]+o[t]);
    printf("%d",k);
}



Measured memory_bytes: 2048
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstdint>
using namespace std;

#define REP(i,n) for (int i = 0; i < n; i++)
typedef long long ll;

int main () {

	ll N,M,X,Y;
	cin >> N >> M >> X >> Y;
	vector < ll > x(N),y(M);
	REP(i,N) cin >> x[i];
	REP(i,M) cin >> y[i];

	for (ll Z = X + 1; Z <= Y; Z++) {
		bool flag = true;
		REP(i,x.size()) {
			if (x[i] >= Z) flag = false;
		}
		REP(i,y.size()) {
			if (y[i] < Z) flag = false;
		}
		if (flag) {
			cout << "No War" << endl;
			return 0;
		}
	}

	cout << "War" << endl;

	return 0;
}

Measured memory_bytes: 256
k = 0
a = input().split(" ")
b = input().split(" ")
g = int(a[0])
f = int(a[1])
i = 0
d = []
while i < g :
    d.append(int(b[i]))
    i = i + 1
x = sorted(d)
i = 0
while i < f :
    k = k + x[i]
    i = i + 1
print(k)

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

int main() {
  ll x, k, d;
  cin >> x >> k >> d;
  x = abs(x);
  ll f = min(k, x / d);
  k -= f;
  x -= f * d;
  
  if(k & 1) cout << d - x << endl;
  else cout << x << endl;
}

Measured memory_bytes: 3592
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
// #include<boost/multiprecision/cpp_int.hpp>
// namespace multiprecisioninteger = boost::multiprecision;
// using cint=multiprecisioninteger::cpp_int;
using namespace std;
using ll=long long;
#define double long double
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
// using llset=tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>;
#define For(i,a,b) for(i=a;i<(ll)b;++i)
#define bFor(i,b,a) for(i=b,--i;i>=(ll)a;--i)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N,0)
#define brep1(i,N) bFor(i,N,1)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define eb emplace_back
#define print(v) cout<<v<<endl
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define printYES cout<<"YES"<<endl
#define printNO cout<<"NO"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
#define matoutput(v) do{for(auto outimat:v)output(outimat);}while(0)
const ll mod=1000000007;
// const ll mod=998244353;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}
using P=pair<int,vector<int>>;
int main(){
  startupcpp();
  int i,j,bit,N,K;
  ll ans=0;
  cin>>N;
  string s;
  cin>>s;
  map<P,int> mp;
  vector<int> v(N);
  K=1<<N;
  while(K--){
    i=0;j=N-1;
    rep(bit,N){
      if(K&(1<<bit)){
        v[i]=s[bit];
        i++;
      }else{
        v[j]=s[bit];
        j--;
      }
    }
    ++mp[P(i,v)];
  }
  reverse(all(s));
  K=1<<N;
  while(K--){
    i=0;j=N-1;
    rep(bit,N){
      if(K&(1<<bit)){
        v[i]=s[bit];
        i++;
      }else{
        v[j]=s[bit];
        j--;
      }
    }
    ans+=mp[P(i,v)];
  }
  print(ans);
}

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

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


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x, y) make_pair(x, y)

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    string s, t; cin >> s >> t;
    ll m = s.size(), n = t.size();
    ll ans = 2050;
    rep(i, m-n+1) {
        ll tmp = 0;
        rep(j, n) {
            if(s[i+j] != t[j]) tmp++;
        }
        if(ans > tmp) ans = tmp;
    }
    cout << ans << endl;
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


Measured memory_bytes: 3636
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String[] s = sc.next().split("");
    if(s.length==2){
      System.out.print(s[0]);
      System.out.print(s[1]);
    }else{
      System.out.print(s[2]);
      System.out.print(s[1]);
      System.out.print(s[0]);
    }   
  } 
}

Measured memory_bytes: 23764
let () = Scanf.scanf "%d\n" @@ fun n ->
  let abs = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun a b -> a, b in
  if Array.fold_right (fun (a, b) -> ( && ) (a = b)) abs true then
    print_endline "0"
  else
    Printf.printf "%d\n" @@
      Array.fold_right (fun (a, _) -> ( + ) a) abs 0
      - Array.fold_right (fun (a, b) -> min (if a > b then b else max_int)) abs max_int


Measured memory_bytes: 5504
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(){
    ll n,k;
    cin>>n>>k;
    ll a[n];
    ll b[n];
    for(ll i=0;i<n;++i){
        cin>>a[i]>>b[i];
    }
    vector<pair<ll, ll>> p(n);
    for(ll i=0;i<n;++i){
        p[i]=make_pair(a[i], b[i]);
    }
    sort(p.begin(), p.end());

    ll flag=0;
    ll ans;
    for(ll i=0;i<n;++i){
        flag += p[i].second;
        if(flag >= k){
            ans = p[i].first;
            break;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3328
let w, h, n = Scanf.scanf " %d %d %d" @@ fun a b c -> a, b, c
let l, r, d, t = ref 0, ref w, ref 0, ref h
let xyas = Array.init n @@ fun _ -> Scanf.scanf " %d %d %d" @@ fun a b c -> a, b, c
let _ = Array.iter (fun (x, y, a) -> match a with 1 -> l := max !l x | 2 -> r := min !r x | 3 -> d := max !d y | _ -> t := min !t y) xyas;
  Printf.printf "%d\n" @@ max 0 (!r - !l) * max 0 (!t - !d)

Measured memory_bytes: 512
n, k, q = map(int, input().split())
a = []
for i in range(q):
    a.append(int(input()))

point = [0 for i in range(n)]
for i in range(q):
    point[a[i] - 1] += 1

for i in range(n):
    if q - point[i] < k:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 85964
n = int(input())
ab_ls = []
for i in range(n):
    ab_ls.append(list(map(int, input().split())))
ab_ls.sort(key=lambda x:x[1])
hoge = 0
result = True
for i in ab_ls:
    hoge = hoge + i[0]
    if hoge > i[1]:
        result = False
if result:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 53720
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define FILL(Itr,n) fill((Itr).begin(),(Itr).end(),n)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))
typedef long long ll;
#define MOD 1000000007

struct LCA {
    int n,ln;
    vector<vector<int> > parent;
    vector< vector<int> > G;
    vector<int> depth;
    
    LCA(int _n) : n(_n), depth(_n),G(_n+10){
        ln=0;
        while(n>(1<<ln)) ln++;
        parent = vector<vector<int> >(ln, vector<int>(n));
    }
    
    void dfs(int v, int p, int d){
        parent[0][v]=p;
        depth[v]=d;
        for(int i=0;i<G[v].size();i++) if(G[v][i]!=p) dfs(G[v][i], v, d+1);
    }
    
    int dist(int a, int b){
        int par=getParent(a,b);
        return depth[a]+depth[b]-depth[par]*2;
    }
    
    void init(int root){
        dfs(root, -1, 0);
        for(int k=0; k+1<ln; k++){
            for(int v=0; v<n; v++){
                if(parent[k][v] < 0) parent[k+1][v] = -1;
                else parent[k+1][v] = parent[k][parent[k][v]];
            }
        }
    }
    
    void add_edge(int a, int b){
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    int getParent(int u, int v){
        if(depth[u] > depth[v]) swap(u,v);
        for(int k=0; k<ln; k++){
            if((depth[v]-depth[u])>>k & 1) v = parent[k][v];
        }
        if(u==v) return u;
        
        for(int k=ln-1; k>=0; k--){
            if(parent[k][u] != parent[k][v]){
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};


int main(){
    
    int n; cin>>n;
    
    LCA inst(100010);
    REP(i,n){
        int k; cin>>k;
        REP(j,k){
            int t; cin>>t;
            inst.add_edge(i,t);
        }
    }
    
    inst.init(0);
    
    int q; cin>>q;
    REP(i,q){
        int a,b; cin>>a>>b;
        cout<<inst.getParent(a,b)<<endl;
    }
   
    
    return 0;
}

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

#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define mod 998244353
#define debug(x) cerr<<#x<<"="<<x<<'\n'

const int maxn=2e5+10;

int n,m;
pii bomb[maxn];
int l[maxn],r[maxn];
vector <pii> edge[maxn];
bool vis[maxn];
vector <int> ans;

int dfs(int u,int lst) {
	vis[u]=true;
	for (int i=0;i<SZ(edge[u]);i++) {
		int v=edge[u][i].fi,e=edge[u][i].se;
		if (vis[v]) continue;
		if (dfs(v,e)) {
			bomb[u].se^=1;
			bomb[v].se^=1;
		}
	}
	if (bomb[u].se) {
		if (lst==-1) {
			puts("-1");
			exit(0);
		}
		ans.pb(lst+1);
	}
	return bomb[u].se;
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++) scanf("%d%d",&bomb[i].fi,&bomb[i].se);
	sort(bomb,bomb+n);
	for (int i=0;i<m;i++) {
		scanf("%d%d",&l[i],&r[i]);
		l[i]=lower_bound(bomb,bomb+n,MP(l[i],0))-bomb;
		r[i]=upper_bound(bomb,bomb+n,MP(r[i],1))-bomb;
		if (l[i]==r[i]) continue;
		edge[l[i]].pb(MP(r[i],i));
		edge[r[i]].pb(MP(l[i],i));
	}
	bomb[n].se=bomb[n-1].se;
	for (int i=n-1;i>0;i--) bomb[i].se^=bomb[i-1].se;
	for (int i=0;i<n;i++)
		if (!vis[i]) dfs(i,-1);
	sort(ans.begin(),ans.end());
	printf("%d\n",SZ(ans));
	for (int i=0;i<SZ(ans);i++) printf("%d ",ans[i]);
	return 0;
}

Measured memory_bytes: 20860
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a+b==c+d)cout<<"Balanced"<<endl;
  else if(a+b>c+d)cout<<"Left"<<endl;
  else cout<<"Right"<<endl;
}

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


int main(){
    int n;
    cin>>n;
    long long a,t;
    long long x=1,y=1;
    long long ans;
    for(int i=0;i<n;i++){
        cin>>t>>a;
        x+=(t-x%t)%t;
        y+=(a-y%a)%a;
        long long k=max(x/t,y/a);
        x=k*t;
        y=k*a;
    }
    cout<<x+y<<endl;
}

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

int main()
{
	int N, sum = 0;
	cin >> N;
	vector<int> x(N);
	for (int i = 0; i < N; i++)
	{
		cin >> x[i];
		sum += x[i];
	}
	if (sum % N != 0) {
		sum /= N;
		int sum1 = sum + 1;
		long long int ans = 0;
		for (int i = 0; i < N; i++)
		{
			ans += ((long long int)x[i] - sum) * ((long long int)x[i] - sum);
		}
		long long int ans1 = 0;
		for (int i = 0; i < N; i++)
		{
			ans1 += ((long long int)x[i] - sum1) * ((long long int)x[i] - sum1);
		}
		cout << min(ans1, ans) << endl;

	}
	else {
		sum /= N;
		long long int ans = 0;
		for (int i = 0; i < N; i++)
		{
			ans += ((long long int)x[i] - sum) * ((long long int)x[i] - sum);
		}
		cout << ans << endl;
	}
	return 0;
}

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

int main() {
    int n;
    int m;
 
   cin >> n >> m;
  
   int ans = n + m;
  
   if (ans < 24){
     
      cout << ans << endl;
 
   }else {
     
      ans = ans - 24;
      cout << ans << endl;
   }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define US unordered_set
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
int main(){
  string S; cin>>S;
  ll cnt=0; for(char c:S) if(c=='p') cnt++;
  cout<<S.length()/2-cnt<<endl;
}


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

int main(void){
	int N, M;
	ll K;
	cin >> N >> M >> K;

	ll A[N];
	ll B[M];
	rep(i, N) cin >> A[i];
	rep(i, M) cin >> B[i];

	ll At[N+2];
	ll Bt[M+2];
	At[0] = 0;
	Bt[0] = 0;
	rep(i,N) At[i+1] = At[i] + A[i];
	rep(i,M) Bt[i+1] = Bt[i] + B[i];

	int ans = 0;
	int j = M;
	rep(i,N+1){
		if (At[i]>K) break;
		while (Bt[j] > K - At[i]) j--;
		ans = max(ans, i+j);
	}
	cout << ans << endl;

	return 0;
}


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

int main() {
  int a[2][100], n;

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

  int now, tmp, ans = 0;
  for (int i = 0; i < n; i++) {
    tmp = 0;
    now = 0;
    while (now <= i) {
      tmp += a[0][now];
      now++;
    }
    tmp += a[1][now-1];
    while (now < n) {
      tmp += a[1][now];
      now++;
    }
    
    ans = max(ans, tmp);
  }

  cout << ans << endl;

  return 0;

}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

int p[MAXN];

void solve(){
	int n;
	scanf("%d", &n);
	REPN(i, 1, n){
		scanf("%d", &p[i]);
	}
	int ans = 0;
	REPN(i, 1, n){
		if (p[i] == i){
			swap(p[i], p[i + 1]);
			ans++;
		}
	}
	printf("%d\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 640