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

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 1e5 + 10;
struct Edge { int v, next;} edge[N * 4];
bool vis[N];
int n, m, cnt, head[N];
inline void add(int u, int v) {
    edge[++cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++;
    edge[++cnt].v = u; edge[cnt].next = head[v]; head[v] = cnt++;
}
void dfs(int u) {
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (!vis[v]) dfs(v);
    }
}

int main() {
    n = read(), m = read();
    for (int i = 0; i < m; i++) {
        int a = read(), b = read(); int c = read();
        add(a, b);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 10180
import java.util.Scanner;
public class Main {

	
	public static void main(String[]args) {
		
		Scanner tc = new Scanner(System.in);
		
		int x = tc.nextInt();
		int y = tc.nextInt();
		
		if(x <= 5)
			System.out.println("0");
		else if(x >= 6 && x <= 12) {
			y = (int)(y/2);
			System.out.println(y);
		}
		else 
			System.out.println(y);
			
	}
}


Measured memory_bytes: 22612
import * as fs from 'fs';

namespace AtCoder.abc097 {

    class ProgramA {
        args: string[];

        /**
         * 4 7 9 3
         * Yes
         */
        constructor(args: string[]) {
            this.args = args;
        }

        main(): void {

            const [a, b, c, d]: number[] = this.args[0].split(' ').map(Number);
            let wk1: number = Math.abs(a - c);
            if (wk1 <= d) {
                console.log('Yes');
                return;
            }
            let wk2: number = Math.abs(a - b);
            let wk3: number = Math.abs(b - c);

            if (wk2 <= d && wk3 <= d) {
                console.log('Yes');
                return;
            }
            console.log("No");


        }
    }

    new ProgramA(fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n')).main();
}

Measured memory_bytes: 7372
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;

const vector<int> dx = {1,0,-1,0};
const vector<int> dy = {0,1,0,-1};

int main() {
  int h,w;
  cin >> h >> w;
  vector<string> a(h);
  for(int i=0;i<h;i++) cin >> a[i];

  queue<pair<int,int>> que;
  vector<vector<int>> dist(h,vector<int>(w));
  for(int i=0;i<h;i++) dist[i].assign(w,-1);

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j] == '#'){
        que.push(make_pair(i,j));
        dist[i][j] = 0;
      }
    }
  }

  while(!que.empty()){
    pair<int,int> v = que.front();
    que.pop();

    int x = v.first;
    int y = v.second;

    for(int dir=0;dir<4;dir++){
      int nx = x + dx[dir];
      int ny = y + dy[dir];

      if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
      if(a[nx][ny] == '#') continue;

      if(dist[nx][ny] != -1){
        if(dist[nx][ny] > dist[x][y] + 1){
          dist[nx][ny] = dist[x][y] + 1;
        }else{
          continue;
        }
      }else{
        dist[nx][ny] = dist[x][y] + 1;
      }

      que.push(make_pair(nx,ny));
    }

  }

  int ans = 0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      ans = max(ans,dist[i][j]);
    }
  }
  cout << ans << endl;

}

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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL<<60;
const ll mod =1000000007;


ll pow_mod(ll n, ll k, ll m) {
	ll r = 1;
	for (; k > 0; k >>= 1) {
		if (k & 1)r = (r*n) % m;
		n = (n*n) % m;
	}
	return r;
}



int main() {
	
	string s;
	cin >> s;

	int n = s.size();

	bool b = true;

	ll ans = 3;

	int cnt = 2;

	FOR(i, 1, n) {
		if (s[i] == '1') {
			ans *= 3;
			
			cnt++;
			ans %= mod;
			b = true;
		}
		else {
			ans *= 3;
			ans -= pow_mod(2, cnt, mod);
			ans += mod;
			ans %= mod;
			b = false;
		}
	}
	cout << ans << endl;


	
}


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

using namespace std;

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

int main(){
    string a, b, c;
    cin >> a >> b >> c;
    cout << (char)toupper(a[0]) << (char)toupper(b[0]) << (char)toupper(c[0]) << endl;
}


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

int main(){
    string s;
    cin>>s;
    int flag=0;
    int l=s.length()-1;
    if(l<2){
        cout<<"0";
        return 0;
    }
    if(l%2==0){
        //even
        int len=l;
        for(int i=0;i<(len/2);i++){
            if(s[i]!=s[(len/2)+i]){
                len-=2;
                i=-1;
            }else{
                if(i==(len/2)-1){
                    flag=len;
                }
                
            }
        }
        if(flag>0){
            cout<<flag;
        }
    }else{
        //odd
        int len=l-1;
        for(int i=0;i<(len/2);i++){
            if(s[i]!=s[(len/2)+i]){
                len-=2;
                i=-1;
            }else{
                if(i==(len/2)-1){
                    flag=len;
                }
            }
        }
        if(flag>0){
            cout<<flag;
        }
    }
}


Measured memory_bytes: 256
# E = 右向き, W = 左向き
n = int(input())
s = input()
we = s.count('E')
ww = s.count('W')
ew = 0
ee = 0
ans = 3 * (10 ** 5)
for i in range(n):
    if s[i] == 'W':
        ww -= 1
    else:
        we -= 1
    ans = min(ans,we+ew)
    if s[i] == 'W':
        ew += 1
    else:
        ee += 1
print(ans)

Measured memory_bytes: 9732
using System;
using System.Linq;

namespace A_RoundUpTheMean
{
    class Program
    {
        static void Main(string[] args)
        {
            var nums = Console.ReadLine().Split(' ').Select(s => int.Parse(s));

            var ans = Math.Round(nums.Average(), MidpointRounding.AwayFromZero);

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
signed main(){
  int N,H;
  cin>>N>>H;
  cout<<(N+H-1)/H-N/H;
  }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ctime>
#include <sstream>
#define weewoo ios::sync_with_stdio(false);cin.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define ll long long
#define se second
#define fi first
#define ctoi(x) (x-'0')
#define pi (acos(-1))
#define llputin(a,n) for(int i=0;i<n;i++){ll x;cin >> x;a.push_back(x);}
#define iputin(a,n) for(int i=0;i<n;i++){int x;cin >> x;a.push_back(x);}

#define MOD ((ll) 1e9 + (ll) 7)
using namespace std;

ll pw(ll x,ll a){
    if(a==0)
        return 1;
    ll t = pw(x,a/2);
    if(a%2==0)
        return (t*t);
    else
        return (t*t*x);
}

bool prime(int x)
{
    if(x < 2) return false;
        for(int i=2; i<= sqrt(x); i++) {
            if ((x%i) == 0) return false;
        }
    return true;
}

map<ll,int>m;

int main()
{
    weewoo;
    bool ok=1;
    ll n;
    cin >> n;
    for(int i=0;i<n;i++){
        ll x;cin >> x;
        m[x]++;

        if(m[x]>1)
            ok=0;
    }
    if(ok)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define vsort(v) sort(v.begin(),v.end())
#define asort(a,n) sort(a, a + n)
#define vi vector<int>
#define vd vector<double>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vi a(N);
    vi b(N);
    vi c(N);
    rep(i, N){
        cin >> a[i];
    }
    rep(i, N){
        cin >> b[i];
    }
    rep(i, N){
        cin >> c[i];
    }

    vsort(a);
    vsort(b);
    vsort(c);
    /*
    rep(i, N){
        cout << a[i] << ", ";
    }
    cout << endl;
    rep(i, N){
        cout << b[i] << ", ";
    }
    cout << endl;
    rep(i, N){
        cout << c[i] << ", ";
    }
    cout << endl;
    */

    long long ans = 0LL;

    rep(i, N){
        ans += (lower_bound(a.begin(), a.end(), b[i]) - a.begin()) * (c.end() - upper_bound(c.begin(), c.end(), b[i]));
    }
    cout << ans << endl;

    return 0;
}

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

int main(void){
  int N,c[505],s[505],f[505],i,j,time;
  char str[100],*p;
  
  fgets(str,sizeof(str),stdin);
  N=atoi(str);
  
  for(i=1;i<N;i++){
    fgets(str,sizeof(str),stdin);
    p=strtok(str," \n");
    c[i]=atoi(p);
    p=strtok(NULL," \n");
    s[i]=atoi(p);
    p=strtok(NULL," \n");
    f[i]=atoi(p);
  }
  
  for(i=1;i<N;i++){
    time=s[i]+c[i];
    for(j=i+1;j<N;j++){
      if(s[j]>time){
        time=s[j]+c[j];
      }else if(time%f[j]!=0){
        time+=(f[j]-time%f[j])+c[j];
      }else{
        time+=c[j];
      }
    }
    printf("%d\n",time);
  }
  
  printf("0\n");
  
  
  return 0;
}

Measured memory_bytes: 128
#include<iostream>


//
struct vec {
	int x, y;
	vec() :x{}, y{} {}
	vec(int xv, int yv) :x{ xv }, y{yv}{}
	auto turnedL()const {
		return vec{ -y, x };
	}
	auto turnedR()const {
		return vec{ y,-x };
	}
	auto turned()const {
		return vec{ -x,-y };
	}

	friend auto& operator>>(std::istream&is, vec&v) {
		return is >> v.x >> v.y;
	}
	auto operator-(const vec&v) const{
		return vec{ x - v.x,y - v.y };
	}
	auto operator+(const vec&v) const{
		return vec{ x + v.x, y + v.y };
	}
};

int main() {
	vec p1, p2;
	std::cin >> p1>> p2;

	auto v1 = p2 - p1;
	auto p4 = p1 + v1.turnedL();
	auto p3 = p2 + v1.turnedL();

	std::cout << p3.x << " " << p3.y << " " << p4.x << " " << p4.y << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;

vector<ll> a,b,c;
int main(void){
	ll x,y,z,k;
	cin>>x>>y>>z>>k;
	a = vi(x);
	b = vi(y);
	c = vi(z);
	for(int i = 0; i <x; i++){
		cin>>a[i];
	}
	for(int i = 0; i < y; i++){
		cin>>b[i];
	}
	for(int i = 0; i < z; i++){
		cin>>c[i];
	}
	sort(a.begin(), a.end(), greater<ll>());
	sort(b.begin(), b.end(), greater<ll>());
	sort(c.begin(), c.end(), greater<ll>());
	priority_queue<vi> q;
	q.push(vi({a[0] + b[0] + c[0], 0, 0, 0}));
	set<vi> seen;
	while(k--){
		vi t = q.top(); q.pop();
		cout<<t[0]<<'\n';
		int ai = t[1], bi = t[2], ci = t[3];
		vi tt(4);
		vi ttt(3);
		if(ai + 1 < x){
			ttt[0] = ai + 1;
			ttt[1] = bi;
			ttt[2] = ci;
			if(!seen.count(ttt)){
				seen.insert(ttt);
				tt[0] = t[0] - a[ai] + a[ai+1];
				tt[1] = ai + 1;
				tt[2] = bi;
				tt[3] = ci;
				q.push(tt);
			}
		}
		if(bi + 1 < x){
			ttt[1] = bi + 1;
			ttt[0] = ai;
			ttt[2] = ci;
			if(!seen.count(ttt)){
				seen.insert(ttt);
				tt[0] = t[0] - b[bi] + b[bi+1];
				tt[2] = bi + 1;
				tt[1] = ai;
				tt[3] = ci;
				q.push(tt);
			}
		}
		if(ci + 1 < x){
			ttt[2] = ci + 1;
			ttt[0] = ai;
			ttt[1] = bi;
			if(!seen.count(ttt)){
				seen.insert(ttt);
				tt[0] = t[0] - c[ci] + c[ci+1];
				tt[3] = ci + 1;
				tt[2] = bi;
				tt[1] = ai;
				q.push(tt);
			}
		}
	}
	return 0;
}


Measured memory_bytes: 4616
import java.util.Scanner

import scala.collection.mutable.ArrayBuffer


object Main {
  case class Edge(x: Int, y: Int, z: Long)
  // 経路圧縮と(経路圧縮+ランク)で計算時間がほとんど変わっていないが...(実装ミスってる？)
  class UnionFind(val n: Int) {

    sealed trait Node

    final case class Root(count: Int, rank: Int) extends Node

    final case class NonRoot(parentIndex: Int) extends Node

    private val nodes: ArrayBuffer[Node] = ArrayBuffer.fill(n)(Root(count = 1, rank = 0))

    private def rootNode(index: Int): (Int, Root) = {
      nodes(index) match {
        case root: Root => (index, root) // nodes(index) == root
        case nonRoot: NonRoot =>
          val (rootIndex, root) = rootNode(nonRoot.parentIndex)
          nodes(index) = NonRoot(parentIndex = rootIndex) // 経路圧縮
          (rootIndex, root)
      }
    }
    def countRoot() = nodes.count(node => node.isInstanceOf[Root])

    private def root(index: Int): Int = rootNode(index)._1

    def sameCount(x: Int): Int = rootNode(x)._2.count

    def same(x: Int, y: Int): Boolean = root(x) == root(y)


    def unite(x: Int, y: Int): Unit = {
      if (same(x, y)) return

      val (xRootIndex, xRoot) = rootNode(x)
      val (yRootIndex, yRoot) = rootNode(y)

      if (xRoot.rank < yRoot.rank) {
        // xRootの親をyRootとする
        nodes(xRootIndex) = NonRoot(parentIndex = yRootIndex)
        nodes(yRootIndex) = yRoot.copy(count = xRoot.count + yRoot.count)
      } else {
        // yRootの親をxRootとする
        nodes(yRootIndex) = NonRoot(parentIndex = xRootIndex)
        val nextXRootRank = xRoot.rank + (if (xRoot.rank == yRoot.rank) 1 else 0)
        nodes(xRootIndex) = Root(count = xRoot.count + yRoot.count, rank = nextXRootRank)
      }
    }

  }

  def read() = {
    val sc = new Scanner(System.in)
    val n, m = sc.nextInt()
    //0-index化
    val edges = IndexedSeq.fill(m)(Edge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt()))

    (n, m, edges)
  }

  def solve(n:Int, m:Int, edges: IndexedSeq[Edge]): Int = {
    val uf = new UnionFind(n)
    for(edge <- edges){
      uf.unite(edge.x, edge.y)
    }
    // 連結成分数を求める
    uf.countRoot()
  }

  def main(args: Array[String]): Unit = {
    val (n, m, edges) = read()
    println(solve(n, m,edges))
  }
}

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

int main(void){
    int n;
    cin>>n;
    int res=100;
    rep(i,n){
        int a,cnt=0;
        cin>>a;
        while(a%2==0){
            a/=2;
            cnt++;
        }
        res=min(cnt,res);
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
#define int ll
#define N 100005
#define pb push_back
#define pv(x) cout<<#x<<": ";for(auto k:x){ cout<<k<<" "; }cout<<endl;
#define dbg(x) cout<<#x<<": "<<x<<endl;

int n,m,ni,mi;
string s;
// int num[N];
int ok=false;

void solve(){
	cin >> s ;
	if(s[2]==s[3] && s[5]==s[4]){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
	cout<<endl;
}

int32_t main(){cin.tie(0);ios_base::sync_with_stdio(NULL);
	
	int t=1;
	while(t--) solve();
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
long gcd(int n,int m){
    if(n%m==0) return m;
    else return gcd(m,n%m);
}
int main(void){
    int x,i,j,k;
    long ans=0;
    scanf("%d",&x);
    for(i=1;i<=x;i++){
        for(j=1;j<=x;j++){
            long tmp = gcd(i,j);
            for(k=1;k<=x;k++){
                ans += gcd(tmp,k);
            }
        }
    }
    printf("%ld",ans);
    return 0;
}


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

int main(void){
    char a[200001], b[200001];
    int s=0, i=0;
 
    scanf("%s",a);
    scanf("%s",b);
 
    while(a[i]!='\0'){
        if(a[i] != b[i]){
            a[i] = b[i];
            s++;
        }
        i++;
    }
    printf("%d",s);
  
    return 0;
}

Measured memory_bytes: 2096
import java.io.*
import java.util.*

const val YES = "Yes"
const val NO = "No"
fun solve(s: String, t: String){
    val s_ = s.toList().sorted().joinToString(separator = "")
    val t_ = t.toList().sortedDescending().joinToString(separator = "")
    if (s_ < t_) println(YES)
    else println(NO)
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val s = sc.next()
    val t = sc.next()
    solve(s, t)
}



Measured memory_bytes: 36264
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >>a >>b;
  if(a==1 && b==3)cout << 2 <<endl;
  if(a==1 && b==2)cout << 3 <<endl;
  if(a==2 && b==1)cout << 3 <<endl;
  if(a==2 && b==3)cout << 1 <<endl;
  if(a==3 && b==1)cout << 2 <<endl;
  if(a==3 && b==2)cout << 1 <<endl;
}

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

using namespace std;

using ll = long long;

string s, t;
vector<vector<int>> memo;
vector<vector<int>> sol;

// s[i, ), t[j, ) の共通部分列で最大のサイズを求める
int Solve(size_t i, size_t j) {
    if (s.size() <= i || t.size() <= j) return memo[i][j] = 0;
    if (memo[i][j] != -1) return memo[i][j];

    int res = 0;
    if (s[i] == t[j]) {
        res = 1 + Solve(i + 1, j + 1);
        sol[i][j] = (int)(s[i] - 'a');
    }
    else res = max(Solve(i + 1, j), Solve(i, j + 1));

    return memo[i][j] = res;
}

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

    cin >> s >> t;
    memo.resize(s.size() + 1, vector<int>(t.size() + 1, -1));
    sol.resize(s.size() + 1, vector<int>(t.size() + 1, -1));

    Solve(0, 0);
    string ans;
    for (int i = 0, j = 0; i < s.size() && j < t.size(); ) {
        if (s[i] == t[j]) {
            ans += s[i];
            ++i; ++j;
        }
        else {
            if (memo[i + 1][j] < memo[i][j + 1]) ++j;
            else ++i;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 71168
#include<iostream>
#include<string>
#include<algorithm>
#include<cctype>

#define all(c) (c).begin(),(c).end()

using namespace std;

void J(string &s){
  string a="";
  a+=s.substr(1,s.size()-1);
  a+=s[0];
  s=a;
}

void C(string &s){
  string a="";
  a+=s[s.size()-1];
  a+=s.substr(0,s.size()-1);
  s=a;
}

void E(string &s){
  string a="";
  if(s.size()%2==1){
    a+=s.substr(s.size()/2+1,s.size()/2);
    a+=s[s.size()/2];
    a+=s.substr(0,s.size()/2);
  }
  else {
    a+=s.substr(s.size()/2,s.size()/2);
    a+=s.substr(0,s.size()/2);
  }
  s=a;
}

void A(string &s){
  reverse(all(s));
}

void P(string &s){
  for(int i=0;i<s.size();i++){
    if(s[i]=='9')s[i]='0';
    else if(isdigit(s[i]))s[i]++;
  }
}

void M(string &s){
  for(int i=0;i<s.size();i++){
    if(s[i]=='0')s[i]='9';
    else if(isdigit(s[i]))s[i]--;
  }
}

int main(void){
  int n;
  string s,com;
  cin >> n;
  while(n--){
    cin >> com >> s;
    A(com);
    for(int i=0;i<com.size();i++){
      if(com[i]=='J')C(s);
      else if(com[i]=='C')J(s);
      else if(com[i]=='E')E(s);
      else if(com[i]=='A')A(s);
      else if(com[i]=='P')M(s);
      else P(s);
    }
    cout << s << endl;
  }
  
  
  return 0;
}

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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

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


int main(){
    vi x(5);
    for(int i=0; i<5; i++) cin >> x[i];
    int k; cin >> k;
    sort(all(x));
    bool ans=false;
    for(int i=0; i<5; i++){
        for(int j=i+1; j<5; j++){
            if(x[j]-x[i] > k) ans=true;
        }
    }
    cout << (ans?":(":"Yay!") << endl;
    return 0;
}

Measured memory_bytes: 3656
#include<iostream>
#include<iomanip>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	cout << a / b << endl;
	cout << a%b << endl;
	cout << fixed;
	cout << setprecision(10) << (double)a / (double)b << endl;
	
}

Measured memory_bytes: 3260
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		Scanner sc = new Scanner(System.in);
//		Scanner sc = new Scanner(new BufferedReader(new FileReader("/workspace/AOJ/src/section1/in38.txt")));

		int n = sc.nextInt();
		int[] r = new int[n];
		for (int t = 0; t < n; t++) {
			r[t] = sc.nextInt();
		}

		int min = Integer.MAX_VALUE;
		int ans = Integer.MIN_VALUE;


		for (int i = 0; i < n; i++) {
			ans = Math.max(ans, r[i] - min);
			if (min > r[i]) {
				min = r[i];
			}
		}
		System.out.println(ans);
	}
}



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

int main() {
	int n,i,k,cur=0,ans=0;
	cin >> n;
	vector<int> a(100000);
	for(i=0; i<n; i++){
		cin >> k;
		a[k]++;
	}
	cur=a[0]+a[1]+a[2]; ans=cur;
	for(i=3; i<100000; i++){
		cur+=a[i]-a[i-3];
		ans=max(ans,cur);
	}
	cout << ans;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;
typedef long long ll;
  
int main( int argc, char* argv[]) {
  ll N;
  cin >> N;
  vector<ll> a(N), b(N);
  vector<ll> d(N);
  for( int i=0; i<N; ++i ){
      cin >> b[i];
      d[i] = i+1-b[i];
      if( d[i] < 0 ){
          cout << "-1" << endl;
          return 0;
      }
  }
  for( int n=0; n<N; n++ ){
      auto p = find( d.rbegin(), d.rend(), 0 );
      if( p == d.rend() ){
          cout << "-1" << endl;
          return 0;
      }
      for( auto q = p.base(); q != d.end(); q++ ){
          (*q)--;
      }
      a[N-n-1] = distance( d.begin(), p.base() );
      d.erase(p.base()-1);
      //cerr << "d"; for( auto x : d ) cerr << " " << x; cerr << endl;
      //cerr << "a"; for( auto x : a ) cerr << " " << x; cerr << endl;
  }
  for( auto x : a ) cout << x << endl;
  return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize, x: i64,
        a: [i64; n],
    }
    let mut tot: i64 = 0;
    let mut a = a;
    if a[0] > x {
        tot += a[0] - x;
        a[0] = x;
    }
    for i in 1..n {
        let r = max(a[i - 1] + a[i] - x, 0);
        a[i] -= r;
        tot += r;
    }
    puts!("{}\n", tot);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include <stdio.h>
#define mod 1000000007

long long calc(long long a,long long b){
  if(b == 0) return 1;
  if(b%2 == 0){
    long long d = calc(a,b/2);
    return (d*d)%mod;
  }
  return (a*calc(a,b-1))%mod;
}

long long comb(long long n,long long r){
  long long tmp = 1,ttmp = 1;
  for(int i = n;i >= n-r+1;i--) tmp = (tmp*i)%mod;
  for(int i = 1;i <= r;i++) ttmp = (ttmp*i)%mod;
  return (tmp*calc(ttmp,mod-2))%mod;
}

int main(void){
  int N,M;
  scanf("%d%d",&N,&M);

  int insu[100000];
  for(int i = 0;i < 100000;i++) insu[i] = 0;

  int cnt = 0;
  for(int i = 2;i*i <= M;i++){
    if(M%i == 0){
      while(M%i == 0){
        insu[cnt]++;
        M /= i;
      }
      cnt++;
    }
  }
  if(M > 1) insu[cnt]++;

  long long ans = 1;
  for(int i = 0;i <= cnt;i++){
    ans *= comb(insu[i]+N-1,insu[i]);
    ans %= mod;
  }

  printf("%lld\n",ans);

  return 0;
}

Measured memory_bytes: 512
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int x[114514];
int main()
{
	int n,m,a,b;
	memset(x,0,sizeof(x));
	cin>>n>>m;
	rep(i,m){
		cin>>a>>b;a--;b--;
		x[a]++;x[b]++;
	}
	rep(i,n){
		if(x[i]%2>0){
			cout<<"NO"<<endl;return 0;
		}
	}
	cout<<"YES"<<endl;
}


Measured memory_bytes: 640
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
import math

a, b = LI()

# a & bが平方数か判定せよ

num = float(str(a) + str(b))

sq = int(math.sqrt(num))

# print(num, sq)

if sq ** 2 == num:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 62408
a, b = map(int, input().split())
s = input()
ans = "No"
num = [i for i in range(10)]

if len(s) == a+b+1:
    if s[a] == "-":
        s = list(s)
        s.pop(a)
        s = "".join(s)
        if s.isdigit():
            ans = "Yes"
print(ans)


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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()
#define MP(n, m) make_pair(n, m);
#define COUT(d) cout<<std::setprecision(10)<<d<<endl;
#define CIN(n) getline(cin,n);

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;
using ul = unsigned long;

typedef long long ll;

template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

const int mod=1e9+7;


void printv(VI& v){
  REP(i,v.size()) cout << v[i] << " ";
  cout << endl;
}

int vtotal(VI& v){
  int total=0;
  REP(i,v.size()) total+=v[i];
  return total;
}

int main()
{
  cin.tie( 0 );
  ios::sync_with_stdio( false );
	
  //init(); // mint初期化

  ll a,b;
  cin>>a>>b;

  ll ans=0;
  if(a>b){
    ans+=a;a--;
  }
  else{
    ans+=b;b--;
  }
  if(a>b)ans+=a;
  else ans+=b;

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 256
N,C = gets.chomp.split(" ").map(&:to_i)
d = C.times.map{gets.chomp.split(" ").map(&:to_i)}
c = N.times.map{gets.chomp.split(" ").map(&:to_i)}
cc = Array.new(3).map{Array.new(C,0)}
for i in 0..N-1
  for j in 0..N-1
    cc[(i+j+2)%3][c[i][j]-1] += 1
  end
end
ans = 10**10
for i in 0..C-1
  for j in 0..C-1
    for k in 0..C-1
      if i != j && j != k && k != i
        temp = 0
        for m in 0..C-1
          temp += d[m][i]*cc[0][m]
          temp += d[m][j]*cc[1][m]
          temp += d[m][k]*cc[2][m]
        end
        if ans > temp
          ans = temp
        end
      end
    end
  end
end
puts ans


Measured memory_bytes: 4348
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int dp[N], n, k;
vector<int> v(N);
int res(int id)
{
		if(id == n -1)
    	return 0;
    int &ans = dp[id];
    if(ans != -1)
    	return ans;
    ans = 1e9;
    for(int i = 1; i  <= k; i++){
    	if(id + i >= n)
             break;
        ans = min(ans, abs(v[id + i] - v[id]) + res(id + i));
    }
     return ans;
}

int32_t main() 
{
    cin>>n>>k;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++)
    {
    	cin>>v[i];
    }
    cout<<res(0);
}

Measured memory_bytes: 9568
while True:
    

    l = input().split()
    h = int(l[0])
    w = int(l[1])
    
    if h == 0 and w == 0:
        break
    
    element = h*(w+1)

    for i in range(element):
        if (i+1)%(w+1) == 0:
            print("")
            if i == element-1:
                print("")
        elif i+1 < w or i+1 > element-w-1:
            print("#", end="")
        else:
            if (i+1)%(w+1) == 1 or (i+1)%(w+1) == w:
                   print("#", end="")
            else:
                   print(".", end="")

Measured memory_bytes: 8980
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const ll MOD = 1000000007;
const int PRIME_NUM[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

void factoring(vector<int> &v, int x) {
    int i = 0;
    while (x>1 || i<25) {
        if(x%PRIME_NUM[i]==0) {
            v[i]++;
            x/=PRIME_NUM[i];
        }
        else i++;
    }
    return;
}

int main() {
    int n; cin >> n;
    vector<int> f(25,1);
    FOR(i,2,n+1) {
        factoring(f, i);
    }
    int ans = 0;
    REP(i,25) {
        if(f[i]==1) continue;
        ans += (f[i]>=75);
        FOR(j,i+1,25) {
            ans += (f[i]>=3 && f[j]>=25);
            ans += (f[i]>=5 && f[j]>=15);
            ans += (f[i]>=25 && f[j]>=3);
            ans += (f[i]>=15 && f[j]>=5);
            if(f[j]==1) continue;
            FOR(k,j+1,25) {
                if(f[k]==1) continue;
                ans += (f[i]>=3 && f[j]>=5 && f[k]>=5);
                ans += (f[i]>=5 && f[j]>=3 && f[k]>=5);
                ans += (f[i]>=5 && f[j]>=5 && f[k]>=3);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
} ;

typedef struct node *Node;
#define NIL NULL

Node root;

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->r = NIL;
  z->l = NIL;

   while(x != NIL){
    y = x;
    if(z->key < x->key){
      x = x->l;
      
    }else{
      x = x->r;
    }
  }
  z->p = y;
  if(y == NIL){
    root = z;
  }else{
    if(z ->key < y->key){
      y->l = z;
      
    }else{
      y->r = z;
    }
  }
}
    
void inorder(Node u){
    if(u == NIL){
  return;
}
  inorder(u->l);
  printf(" %d",u->key);
  inorder(u->r);
}

void preorder(Node u){
 if(u == NIL)return;
  printf(" %d",u->key);
  preorder(u->l);
  preorder(u->r);
}

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

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);

    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}



Measured memory_bytes: 25296
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc123
{
    class ProgramD
    {
        public int K;
        public long[] A;
        public long[] B;
        public long[] C;

        static void Main(string[] args)
        {
            var program = new ProgramD();
            program.InitializeByConsole();
            // program.InitializeSample2();

            var outputs = program.GetOutput();

            foreach (var output in outputs)
            {
                Console.WriteLine(output);
            }
        }

        public void InitializeByConsole()
        {
            var nums = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

            this.K = nums[3];
            this.A = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
            this.B = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
            this.C = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
        }

        private IEnumerable<long> GetOutput()
        {
            Array.Sort(this.A);
            Array.Sort(this.B);
            Array.Sort(this.C);

            Array.Reverse(this.A);
            Array.Reverse(this.B);
            Array.Reverse(this.C);

            var abcList = new List<long>();

            var numa = Math.Min(this.K, this.A.Length);
            var numb = Math.Min(this.K, this.B.Length);
            var numc = Math.Min(this.K, this.C.Length);

            for (var ia = 0; ia < numa; ia++)
            {
                for (var ib = 0; ib < numb; ib++)
                {
                    if ((ia + 1) * (ib + 1) > this.K) break;

                    for (var ic = 0; ic < numc; ic++)
                    {
                        if ((ia + 1) * (ib + 1) * (ic + 1) > this.K) break;

                        abcList.Add(this.A[ia] + this.B[ib] + this.C[ic]);
                    }
                }
            }

            abcList.Sort();
            abcList.Reverse();

            return abcList.Take(this.K);
        }

        public void InitializeSample1()
        {
            this.K = 8;
            this.A = new long[] {4, 6};
            this.B = new long[] {1, 5};
            this.C = new long[] {3, 8};
        }

        public void InitializeSample2()
        {
            this.K = 5;
            this.A = new long[] {1, 10, 100};
            this.B = new long[] {2, 20, 200};
            this.C = new long[] {1, 10, 100};
        }

        public void InitializeSample3()
        {
            this.K = 20;
            this.A = new[] {7467038376, 5724769290, 292794712, 2843504496, 3381970101, 8402252870, 249131806, 6310293640, 6690322794, 6082257488};
            this.B = new[] {1873977926, 2576529623, 1144842195, 1379118507, 6003234687, 4925540914, 3902539811, 3326692703, 484657758, 2877436338};
            this.C = new[] {4975681328, 8974383988, 2882263257, 7690203955, 514305523, 6679823484, 4263279310, 585966808, 3752282379, 620585736};
        }
    }
}


Measured memory_bytes: 15584
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n,k;
    cin >> n >> k;
    vector <ll> h(n);
    for(ll i=0;i<n;++i) cin >> h[i];
    sort(h.begin(),h.end(),greater<ll>());
    if(n>=k) {
        for(ll i=0;i<k;++i) h[i]=0;
    }
    else {
        for(ll i=0;i<n;++i) h[i]=0;
    }
    ll sum=0;
    for(ll i=0;i<n;++i) sum+=h[i];
    cout << sum << endl;
    return 0;
}


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

int main () {
  int a, b, c, x;
  cin  >> a >> b >> c;
  
  if (a != b) {
    x ++;
  }
  if (b != c) {
    x ++;
  }
  if (c != a) {
    x ++;
  }
  if (x == 2) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 50;
int A[maxn + 1];
LL C[maxn + 1][maxn + 1];
int cnt[1 << 18];
int main(){
    int N, K, S, T;
    cin >> N >> K >> S >> T;
    for(int i = 1; i <= N; i += 1){
        cin >> A[i];
        if((A[i] & S) != S or (A[i] | T) != T) A[i] = -1;
    }
    for(int i = 0; i <= N; i += 1)
        for(int j = 0; j <= i; j += 1)
            C[i][j] = j ? C[i - 1][j] + C[i - 1][j - 1] : 1;
    for(int i = 1; i <= N; i += 1)
        for(int j = 2; j <= N; j += 1)
            C[i][j] += C[i][j - 1];
    LL ans = 0;
    for(int i = 0; i < (1 << 18); i += 1){
        if((i & S) or (i & T) != i) continue;
        for(int j = 1; j <= N; j += 1) if(~A[j]) cnt[A[j] & i] += 1;
        LL pans = 0;
        for(int j = 1; j <= N; j += 1) if(~A[j]){
            pans += C[cnt[A[j] & i]][K];
            cnt[A[j] & i] = 0;
        }
        if(__builtin_parity(i)) ans -= pans;
        else ans += pans;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 4680
mod = 10**6+3
max = 10**6+2
g1 = [1, 1]
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
def rev(a):
    return pow(a,mod-2,mod)
def f(x,d,n):
    if d==0:
        return pow(x,n,mod)
    else:
        d_r = rev(d)
        xdr = d_r * x % mod
        if xdr==0:
            return 0
        elif (xdr+n-1)>=mod:
            return 0
        else:
            return (g1[xdr+n-1]*rev(g1[xdr-1]%mod)*pow(d,n,mod))%mod
ans = []
q = int(input())
for _ in range(q):
    x,d,n = map(int,input().split())
    ans.append(f(x,d,n))
for i in ans:
    print(i)

Measured memory_bytes: 47136
import math
import itertools
N = int(input())
p = [tuple(map(int, input().split())) for _ in range(N)]
num = [int(i) for i in range(N)]
d_sum = 0
for per in itertools.permutations(num):
    # print(per)
    for i in range(len(per) - 1):
        d_sum += math.sqrt((p[per[i]][0] - p[per[i+1]][0])**2 + (p[per[i]][1] - p[per[i+1]][1])**2)
        # print(d_sum)
ans = d_sum / math.factorial(N)

print(ans)

Measured memory_bytes: 3188
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>

using namespace std;
using ll = long long int; 

void prime(vector<int> &num, int n){
    for(int i=0;i<=n;i++){
        num[i] = 1;
    }
    num[0] = 0;
    num[1] = 0;
    num[2] = 1;

    for(int i=2;i<=sqrt(n);i++){
        if(num[i] == 1){
            for(int j=2;j<=n/i;j++){
                num[i*j] = 0;
            }
        }
    }
}


ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}
 
ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}

ll keta(ll a){
  ll ans = 1;
  while(1){
    if(a/10 > 0){
      ans++;
      a = a/10;
    }
    if(a<10) break;
  }
  return ans;
}

const int MAX = 50;
const int MOD = 1000000007;

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

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

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

#define REP(i,n) for(ll i=0;i<(ll)(n);i++) //REP(i, 5) cout<<i;
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)

int main(void){
  
  ll n, k;
  cin>>n>>k;
  vector<ll> a(n);

  REP(i, n){
    ll x;
     cin>>x;
     a[i] = x-1;
  }

  vector<pair<ll, ll>> v(n);
  REP(i, n){
    v[i].first = -1;
    v[i].second = -1;
  }
  ll count = 0;
  ll start = 0; 
  ll piv;

  REP(i, k){
   // cout<<start<<endl;
    if(v[start].first == -1) v[start].first = count;
    else{
      v[start].second = count;
      piv=(k-v[start].first)%(v[start].second-v[start].first);
      // cout<<v[start].first<<(v[start].second-v[start].first)<<endl;
      // cout<<piv<<endl;
      i = k+1;
      break;
    }
    start = a[start];
    count++;
  }
  //cout<<start<<piv<<endl;
 if(count==k){
   cout<<start+1<<endl;
   return 0;
 }
  REP(i, piv){
    start = a[start];
  }
  cout<<start+1<<endl;
  return 0;
}

Measured memory_bytes: 8076
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.append(x)
a.sort(reverse=True)
b=[]
for i in range(n):
    b.append(a[i]-a[i+1])
import fractions as f
maxi=float('inf')
if len(b)==1:
    print(b[0])
    exit()
for i in range(n-1):
    tmp=f.gcd(b[i],b[i+1])
    maxi=min(maxi,tmp)
print(maxi)


Measured memory_bytes: 14252
n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)


Measured memory_bytes: 7112
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e9)
using namespace std;
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    ll a[1010], b[1010], c[1010];
    ll wa[110][110] = {};
    cin >> N >> M;
    rep(i,0,N){
        rep(j,0,N){
            wa[i][j] = 1e9;
            if(i == j){
                wa[i][j] = 0;
            }
        }
    }
    rep(i,0,M){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        wa[a[i]][b[i]] = c[i];
        wa[b[i]][a[i]] = c[i];
    }
    rep(k,0,N){
        rep(i,0,N){
            rep(j,0,N){
                wa[i][j] = min(wa[i][j], wa[i][k] + wa[k][j]);
            }
        }
    }
    bool is_pass[1010];
    rep(i,0,M){
        is_pass[i] = false;
    }
    rep(i,0,N){
        rep(j,0,N){
            if(i != j){
                rep(k,0,M){
                    if(wa[i][j] == wa[i][a[k]] + c[k] + wa[b[k]][j]){
                        is_pass[k] = true;
                    }
                }
            }
        }

    }
    ll ans = 0;
    rep(i,0,M){
        if(!is_pass[i]) ans++;
    }
    print(ans);
}


Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>

int main(void)
{
    int N;
    if(scanf("%d", &N) == EOF) exit(1);

    int i, count = 0;

    int A[N];

    for(i=0;i<N;i++){
        if(scanf("%d", &A[i]) == EOF) exit(1);
        if( ((i+1)%2 !=0) && (A[i]%2 != 0)) count++;
    }
    printf("%d", count);

    return 0;
}

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


int main(){
	int next[6][2]={{1,2},{-1,3},{1,-1},{4,5},{5,2},{2,1}}; 
	string s;
	while(cin>>s&&s!="#"){
		int p=0;
		for(int i=0;p!=-1&&i<s.size();i++){
			p=next[p][s[i]-'0'];
		}
		cout<<(p==5?"Yes":"No")<<endl;
	}
	return 0;
}

Measured memory_bytes: 1180
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int days = sc.nextInt();
		int[][] activities = new int[days][3];
		for (int i = 0; i < days; i++) 
			 for (int j = 0; j < 3; j++) 
				 activities[i][j] = sc.nextInt();
		
		System.out.println(solve(activities, days));
	}

	private static int solve(int[][] activities, int days) {
		// TODO Auto-generated method stub
		int[][] dp = new int[days][3];
		
		dp[0][0] = activities[0][0];
		dp[0][1] = activities[0][1];
		dp[0][2] = activities[0][2];
		
		for (int day = 1; day < days; day++) {
			dp[day][0] = activities[day][0] + Math.max(dp[day - 1][1], dp[day - 1][2]);
			dp[day][1] = activities[day][1] + Math.max(dp[day - 1][0], dp[day - 1][2]);
			dp[day][2] = activities[day][2] + Math.max(dp[day - 1][0], dp[day - 1][1]);
		}
		
		return Math.max(dp[days - 1][0], Math.max(dp[days - 1][1], dp[days - 1][2]));
	}

}


Measured memory_bytes: 54856
/*
  AUTHOR:SOURABH
  CREATED:01:05:20
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<pll , null_type, less< pll >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

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

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    ll t,a,b,n,x;
    t=1;
    //cin>>t;
    W(t--)
    {
        cin>>a>>b>>n;
        x=min(b-1,n);
        cout<<(a*x)/b;
    }
    return 0;
}















Measured memory_bytes: 3652
#include <stdio.h>

#define N 2000001

int B[N], C[N];

void countingSort(int A[], int B[], int k, int n){
  int i, j;

  for(i = 0; i <= k; i++){
    C[i] = 0;
  }
  for(j = 1; j <= n; j++){
    C[A[j]]++;
  }   
  for(i = 1; i <= k; i++){
    C[i] = C[i] + C[i - 1];
  } 
  for(j = n; j >= 1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

  for(i = 1; i <= n; i++){
    printf("%d", B[i]);
    if(i != n) printf(" ");
  }
  printf("\n");

}

int main(){
  int A[N];
  int i, j, n, k = 0;

  scanf("%d", &n); 
  for(i = 1; i <= n; i++){
    scanf("%d", &A[i]);
    if(k < A[i]) k = A[i];
  }

  countingSort(A, B, k, n);

  return 0;
}


Measured memory_bytes: 17368