akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    map<int, int> A;
    for (int i = 0; i < N; i++) {
        int ai;
        cin >> ai;
        if (A.find(ai) == A.end()) {
            A[ai] = 1;
        } else {
            A[ai]++;
        }
    }

    int reduce_num = max((int) A.size() - K, 0);
    int reduce_count = 0;
    if (reduce_num > 0) {
        map<int, int> A_count;
        for (auto num_count_pair: A) {
            auto count = num_count_pair.second;
            if (A_count.find(count) == A_count.end()) {
                A_count[count] = 1;
            } else {
                A_count[count]++;
            }
        }

        while (reduce_num > 0) {
            reduce_count += A_count.begin()->first;
            reduce_num--;
            if (--A_count.begin()->second == 0) {
                A_count.erase(A_count.begin()->first);
            }
        }
    }

    cout << reduce_count << endl;
    return 0;
};


Measured memory_bytes: 9600
n = int(input())
inf = 10**9 + 7
p = [True for i in range(n+1)]
ret = 1
for i in range(2, n+1):
    if not p[i]:
        continue
    for j in range(n//i + 1):
        p[i*j] = False
    j = 1
    cnt = 1
    while i**j <= n:
        cnt += n//(i**j)
        j += 1
    ret = (ret * cnt) % inf
print(ret)


Measured memory_bytes: 3060
n=list(map(int,input().split()))[0]
h=list(map(int,input().split()))

stair=[float('inf')]*(n)
stair[0]=0
for i in range(n-1):
    stair[i+1]=min(stair[i+1],stair[i]+abs(h[i]-h[i+1]))
    if i<n-2:
        stair[i+2]=min(stair[i+2],stair[i]+abs(h[i]-h[i+2]))

print(stair[-1])

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

int main(void){
    int N;
    cin >> N;
    int A[N];
    int max=0;
    int record=0;
    bool flag = false;
    for(int i = 0; i < N;i++){
        cin >> A[i];
        if(max < A[i]){
            max =A[i];
            record = i;
        }
        
        
    }
    sort(A,A+N,greater<int>());
    int second = A[1];

    for(int i = 0; i < N;i++){
        if(record!=i){
            
            cout << max << endl;
    
        }else{
            
            
            cout <<  second << endl;
    
        }
        
    }
}


Measured memory_bytes: 2432
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define RFOR(i,tptpt,ypypy)  for(LL i=(tptpt);i>=(ypypy);i--)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n;

int main() {
	while (cin >> n&&n) {
		map<int, pair<int, int>> mp;

		mp[0] = make_pair(0, 0);
		REP(i, n - 1) {
			int a, b;
			cin >> a >> b;
			if (b == 0) {
				mp[i + 1] = make_pair(mp[a].first, mp[a].second - 1);
			}
			else if (b == 1) {
				mp[i + 1] = make_pair(mp[a].first + 1, mp[a].second);
			}
			else if (b == 2) {
				mp[i + 1] = make_pair(mp[a].first, mp[a].second + 1);
			}
			else {
				mp[i + 1] = make_pair(mp[a].first - 1, mp[a].second);
			}
		}
		int maxx = 0, maxy = 0, minx = 0, miny = 0;
		REP(i, n) {
			maxx = max(maxx, mp[i].second);
			maxy = max(maxy, mp[i].first);
			minx = min(minx, mp[i].second);
			miny = min(miny, mp[i].first);
		}
		cout << (maxx - minx + 1)<<" "<<(maxy - miny + 1) << endl;
	}
}


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

int main() {
  int n,k,s=0;
  cin >> n >> k;
  for(int c=n;c>0;c--){
    int x;
    cin >> x;
    s += 2*min(k-x,x);
  }
  cout << s;
}
  
      


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

n = int(input())
div = make_divisors(n)

ans = 0
for i in range(len(div)):
    if div[i] == 1:
        continue
    if n // (div[i] - 1) == n % (div[i] - 1):
        ans += div[i] - 1

print(ans)


Measured memory_bytes: 39024
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;

    int A[N];
    map<int, int> mp;
    FOR(i, 1, N){
        cin >> A[i];
        mp[A[i]] = i;
    }

    FOR(i, 1, N){
        cout << mp[i] << " ";
    }
    cout << "\n";
}

Measured memory_bytes: 8568
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD1 1000000007
#define MOD2 998244353
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<ll,ll> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m,ll MOD){if(m==0)return 1;ll t=mpowe(n,m/2,MOD);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;if(n==0) return -1;return logtwo(n/2)+1;}
int main()
{
    fastio();
   
    int t=1;
    //cin>>t;
    while(t--)
    {
        char c;
        cin>>c;
        if(c>='a')
            cout<<'a'<<endl;
        else
            cout<<'A'<<endl;
    }
    
}

Measured memory_bytes: 3596
use std::io::Read;
fn main() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut itr = s.trim().split_whitespace();
    let t1: i64 = itr.next().unwrap().parse().unwrap();
    let t2: i64 = itr.next().unwrap().parse().unwrap();
    let a1: i64 = itr.next().unwrap().parse().unwrap();
    let a2: i64 = itr.next().unwrap().parse().unwrap();
    let b1: i64 = itr.next().unwrap().parse().unwrap();
    let b2: i64 = itr.next().unwrap().parse().unwrap();

    let mut d1: i64 = (a1 - b1) * t1;
    let mut d2: i64 = (a2 - b2) * t2;
    if d1 < 0 {
        d1 *= -1;
        d2 *= -1;
    }

    if d1 + d2 > 0 {
        println!("0");
    } else if d1 + d2 == 0 {
        println!("infinity");
    } else {
        let zure: i64 = d1 / (-d2 - d1);
        let pittari: bool = d1 % (-d2 - d1) == 0;

        let mut ans: i64 = zure * 2 + 1;
        if pittari {
            ans -= 1;
        }
        println!("{}", ans);
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

int main() {

    string S;
    cin >> S;
    rep(i,S.length()) {
        cout << "x";
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
while True:
    H, W = list(map(int, input().split()))
    if H == 0 and W == 0:
        break

    for h in range(H):
        for w in range(W):
            if h == 0 or h == (H - 1) or w == 0 or w == (W - 1):
                if w == (W - 1):
                    print('#')
                else:
                    print('#', end="")
            else:
                print('.', end="")
    print()


Measured memory_bytes: 7000
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
int n, m;
int ans;
vector<int> L[12];
vector<int> p;
int memo[1<<12];
void dfs(int bit, int depth)
{
    if(depth == n) return;
    dfs(bit, depth + 1);
    dfs(bit | (1<<(depth+1)), depth + 1);
    int res = 0;
    for(int i = 0; i < m; i++)
    {
        int cnt = 0;
        for(int j = 0; j < L[i].size(); j++)
        {
            int pos = L[i][j];
            if(bit & (1<<pos)) cnt++;
        }
        if(cnt % 2 == p[i]) res++;
    }
    if(res == m)
    {
        if(not memo[bit]) ans++;
        memo[bit] = 1;
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    memset(memo, 0, sizeof(memo));
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int k; cin >> k;
        for(int j = 0; j < k; j++)
        {
            int x; cin >> x;
            x--;
            L[i].push_back(x);
        }
    }
    for(int i = 0; i < m; i++)
    {
        int x; cin >> x;
        p.push_back(x);
    }
    dfs(0, 0);
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
	char s[11];
	scanf("%s", s);
	int l = strlen(s), flag=0, c=0;
	for(int i = 0; i<l; i++)
	{
		if(i==0 && s[i]!='A')
		{
			flag = 1;
			break;
		}
		if(i==0) continue;
		else if(i>=2 && i<=l-2)
		{
			if(s[i]=='C')
				c++;
			else if(s[i]<91)
			{
				flag = 1;
				break;
			}
		}
		else if(s[i]<91)
		{
			flag = 1;
			break;
		}
	}
	if(flag || c!=1)
		printf("WA\n");
	else printf("AC\n");
}

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

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	if (n == 1 && m == 1) {
		cout << 1 << endl;
	}else if (n < 2 || m < 2) {
		cout << max({ m - 2, n - 2, 0 }) << endl;
	}
	else if (n == 2 || m == 2) {
		cout << 0 << endl;
	}
	else {
		long long ans = (long long)n * m;
		cout << ans - 2 * (n - 2) - 2 * m << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    int ans = a * b / 2;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    ll n,k;cin>>n>>k;
    vll a(n);rep(i,n)cin>>a[i];
    bitset<40> K(k);
    bitset<40> ans(0);
    int zero,one;
    bool less=false;
    for(int i=39;i>=0;i--){
        if(!less&&!K.test(i))continue;
        zero=0;one=0;
        rep(j,n){
            bitset<40> tmp(a[j]);
            if(tmp.test(i))one++;
            else zero++;
        }
        if(!less&&zero<=one&&K.test(i))less=true;
        else if(one<zero&&(less||K.test(i)))ans.set(i);
    }
    ll Ans=0;ll res=1;
    rep(i,40){
        Ans+=ans[i]*res;
        res*=2;
    }
    ll fx=0;
    rep(i,n)fx+=Ans^a[i];
    cout<<fx<<endl;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES


#include <iostream>
#include <vector>
#include <stdio.h>

#include <cmath>

using namespace std;

int main() {
	int a, b;
	string op;

	vector<int> ans_vec;

	while (true)
	{
		cin >> a >> op >> b;
		if (op == "?") break;

		if (op == "+") {
			ans_vec.emplace_back(a + b);
		}
		else if (op == "-") {
			ans_vec.emplace_back(a - b);
		}
		else if (op == "*") {
			ans_vec.emplace_back(a * b);
		}
		else if (op == "/") {
			ans_vec.emplace_back(a / b);
		}
	}

	if (ans_vec.empty()) return 0;

	for (auto&& v : ans_vec) {
		printf("%d\n", v);
	}

	return 0;
}



Measured memory_bytes: 3268
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		double N = sc.nextInt();
		double K = sc.nextInt();
		int  sum = (int)(Math.pow((K-1),(N-1))*K);
		System.out.println(sum);
	}
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++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 SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const long long MOD = 1000000007LL;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

class unionFind{
    template<typename T>
    using vector = std::vector<T>;

    vector<int> par;
    vector<long long> wei;
    int groupCount;

public:
    void init(int n = 0){
        par.resize(n);
        fill(par.begin(), par.end(), -1);

        wei.resize(n);
        fill(wei.begin(), wei.end(), 0LL);

        groupCount = n;

        return;
    }

    unionFind(int n = 0){
        init(n);
    }

    int root(int x){
        if(par[x] < 0){
            return x;
        }
        int r = root(par[x]);
        wei[x] += wei[par[x]];
        return par[x] = r;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int size(int x){
        return -par[root(x)];
    }

    long long weight(int x){
        root(x);
        return wei[x];
    }

    long long diff(int x, int y){
        if(!same(x, y)){
            return LLONG_MIN;
        }
        return weight(y) - weight(x);
    }

    bool unite(int x, int y, long long w = 0){
        w += weight(x) - weight(y);

        x = root(x);
        y = root(y);

        if(x == y){
            return false;
        }

        if(size(x) < size(y)){
            std::swap(x, y);
            w = -w;
        }

        par[x] += par[y];
        par[y] = x;
        wei[y] = w;
        --groupCount;

        return true;
    }

    int number_of_group(void){
        return groupCount;
    }
};

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

    int n, m;
    cin >> n >> m;

    unionFind uf(n);
    rep(i, m){
        int l, r;
        lint d;
        cin >> l >> r >> d;
        --l;
        --r;
        if(uf.same(l, r) && uf.diff(l, r) != d){
            cout << "No" << endl;
            return 0;
        }
        uf.unite(l, r, d);
    }

    cout << "Yes" << endl;

    return 0;
}

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;

struct Node{
  ll b;
  ll c;
  bool operator< (const Node &r) const{
      return c > r.c;
  }
};

int main(){
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  vector<ll> b(m);
  vector<ll> c(m);
  rep(i, m) cin >> b[i] >> c[i];

  vector<Node> list;
  rep(i, m) list.push_back({b[i], c[i]});
  sort(all(list));
  sort(all(a));

  ll idx = 0;
  rep(i, m){
    rep(j, list[i].b){
      if(n <= idx) break;
      if(a[idx] < list[i].c) a[idx] = list[i].c, idx++;
      else break;
    }
    if(n <= idx) break;
  }

  ull sum = 0;
  rep(i, n) sum += a[i];
  cout << sum << endl;


  return 0;
}


Measured memory_bytes: 4852
#include <cstdio>
#define MAX_N 45
int F[MAX_N] = { 0 };

int fib(const int &n) {
	if (F[n] != 0) return F[n];
	if (n == 0 || n == 1) {
		F[n] = 1;
		return F[n];
	}

	F[n] = fib(n - 1) + fib(n - 2);
	return F[n];
}

int main() {
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fib(n));
	return 0;
}

Measured memory_bytes: 2716
package main

import "fmt"

func main() {
	var n, change, count int
	var a [100]int
	fmt.Scan(&n)

	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	k := 1
	flag := true
	for flag == true {
		flag = false
		for j := n - 1; j >= k; j-- {
			if a[j] < a[j-1] {
				change = a[j]
				a[j] = a[j-1]
				a[j-1] = change
				count++
				flag = true
			}
		}
		k++
	}
	for i := 0; i < n-1; i++ {
		fmt.Printf("%d ", a[i])
	}
	fmt.Println(a[n-1])
	fmt.Println(count)
}



Measured memory_bytes: 1120
#include <cstdio>

typedef long long LL;

LL A, B;

LL Solve(LL l, LL r, LL a, LL b) {
	if (l == a && b == r - 1) return r - l;
	LL mid = (l + r) >> 1;
	if (a <= b) {
		if (b < mid) return Solve(l, mid, a, b);
		if (mid <= a) return Solve(mid, r, a, b);
		LL ans = Solve(l, mid, a, mid - 1);
		if (a - l + mid - b >= 2) ans += Solve(mid, r, a - l + mid, b);
		else ans += r - mid;
		return ans;
	} else {
		if (b >= mid) return r - l;
		if (a < mid) return Solve(l, mid, a, b) + r - mid;
		return Solve(l, mid, l, b) + r - a;
	}
}

int main() {
	scanf("%lld%lld", &A, &B);
	printf("%lld\n", Solve(0, 1ll << 60, A, B));
	return 0;
}

Measured memory_bytes: 1736
#include<bits/stdc++.h>
#define N 100005
using namespace std;

int n,m,cnt,tot,fst[N],pnt[N<<1],nxt[N<<1],ans[N],dp[N][11];
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
int main(){
	scanf("%d%d",&n,&m);
	int i,j,x,y;
	for (i=1; i<=m; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	scanf("%d",&cnt);
	for (i=1; i<=cnt; i++){
		scanf("%d%d%d",&x,&y,&ans[i]); dp[x][y]=i;
	}
	for (i=9; i>=0; i--)
		for (x=1; x<=n; x++){
			dp[x][i]=max(dp[x][i],dp[x][i+1]);
			for (j=fst[x]; j; j=nxt[j]) dp[x][i]=max(dp[x][i],dp[pnt[j]][i+1]);
		}
	for (i=1; i<=n; i++) printf("%d\n",ans[dp[i][0]]);
	return 0;
}


Measured memory_bytes: 7296
import java.util.*;
  
public class Main {
    Scanner sc = new Scanner(System.in);
  
    public static void main(String[] args) {
        new Main(); 
    }
  
    public Main() {
        new B().doIt();
    }
    class B{
    	void doIt(){
    		int n = sc.nextInt();
    		String str = sc.next();
    		char ctr[] = str.toCharArray();
    		int m = sc.nextInt();
    		int num = n;
    		StringBuilder sb = new StringBuilder();
    		for(int i = 0;i < n;i++){
    			if(m == 0){
    				sb.append(ctr[i]);
    			}
    			else if(m < num){
    				if(ctr[i] == '0'){
    					sb.append(1);
    					m--;
    				}else{
    					sb.append(1);
    				}
    			}else{
    				if(ctr[i] == '0')sb.append(1);
    				else sb.append(0);
    			}
    			num--;
    		}
    		System.out.println(sb);
    	}
    }
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int a, b;
  cin >> a >> b;
  int ans = 0;
  for (int i = a; i <= b; ++i)
    if (i / 10000 == i % 10 && (i / 1000) % 10 == (i % 100) / 10) ans++;

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


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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;
typedef tuple<long long, long long, long long> tllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
bool compTuple(const tllint& arg1, const tllint& arg2) { return get<2>(arg1) > get<2>(arg2); }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    int ans = 0;
    for(int in=0;in<s.size();++in) {
        if(in%2==0) {
            if(s[in]=='g') ;
            else ans--;
        }
        else {
            if(s[in]=='g') ans++;
            else ;
        }
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3760
from collections import Counter
from sys import stdin

def main():
    N = int(input())
    S = stdin.read().splitlines()

    S = [''.join(sorted(s)) for s in S]
    cnt = Counter(S)
    ans = 0
    for s in S:
        ans += cnt[s] - 1
        cnt[s] -= 1
    print(ans)

input = lambda: stdin.readline().rstrip()
main()


Measured memory_bytes: 21724
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)

int main(){
	int n;
	cin>>n;
	vector<int> v(n);
	rep(i,n){
		int a;
		cin>>a;
		v[i] = a%3;
	}
	
	int zero=0,one=0,two=0;
	rep(i,n){
		if(v[i]==0)zero++;
		if(v[i]==1)one++;
		if(v[i]==2)two++;
	}
	
	if(one==0&&two==0){
		cout<<1<<endl;
		return 0;
	}
	
	int ans = 0;
	
	if(one>=1){
		if(one-1< two)ans = max( ans , 1 + zero + (one-1)*2 );
		if(one-1> two)ans = max( ans , 1 + zero + two*2 + 1 );
		if(one-1==two)ans = max( ans , 1 + zero + two*2 );
	}
	
	if(two>=1){
		if(one< two-1)ans = max( ans , 1 + zero + one*2+1 );
		if(one> two-1)ans = max( ans , 1 + zero + (two-1)*2 );
		if(one==two-1)ans = max( ans , 1 + zero + (two-1)*2 );
	}

	if(ans<n)ans++;
	cout<<ans<<endl;
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

ll  fct[200200], inv[200200];
ll bin_pow(ll x, ll n){
	ll res = 1LL;
	for(; n > 0; n >>=1, x = x*x %mod) if(n & 1) res = res * x %mod;
	return res;
}
void init(int cmx){
	fct[0] = fct[1] = inv[1] = 1;
	for(int i=2;i<cmx+3;i++) fct[i] = fct[i-1] * i % mod;
	inv[cmx] = bin_pow(fct[cmx], mod-2);
	for(int i=cmx;i>=1;i--) inv[i-1] = inv[i] * i % mod;
}
ll nCk(ll n, ll k) {
	ll ret =fct[n] * inv[k] % mod * inv[n-k] % mod;
	return ret;
}
map<ll, int> fctm( ll x ){
	map<ll, int> fmp;
	for( ;x>=4 && x%2==0; x/=2)  fmp[2]++;
	for(ll d=3, q=x/d; q>=d ; q=x/d){if(x%d==0) fmp[d]++, x=q; else d +=2;}
	if(x!=1) fmp[x]++;    //note: if x==1: {{1,1}}
	return fmp;
}

int main(){

	ll n,m, ans=1LL;
	cin >>n >>m;
	init(200010);
	auto fc = fctm(m);
	for(auto x: fc){
		(ans *= nCk(x.second + n-1, n-1) )%=mod;
		//dbg(x.first,x.second);
	}
	cout << ans <<"\n";
}


Measured memory_bytes: 3328
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;


//mod演算ライブラリ
//mod=1000000007

LL add(LL a,LL b){
  return (a+b)%mod;
}

LL sub(LL a,LL b){
  return (a+mod-b)%mod;
}

LL mul(LL a,LL b){
  return ((a % mod) * (b % mod)) % mod;
}

LL power(LL x,LL y){//繰り返し二乗法 単品利用可
  if(y==0)return 1;
  else if(y==1)return x%mod;
  else if(y%2==0){
    LL tmp=power(x, y/2) % mod;
    return tmp*tmp%mod;
  }else {
    LL tmp=power(x, y/2) % mod;
    return ((tmp*tmp)%mod)*x%mod;
  }
}

LL dvs(LL a,LL b){
  return mul(a,power(b,mod-2));
}

const int SIZE_mod=200005;
int invfact[SIZE_mod];
int fact[SIZE_mod];

LL factset(int a){//aまでの階乗%mod表を作成
  fact[0]=1;
  FORQ(i,1,a){
    fact[i]=mul(fact[i-1],i);
  }
}

LL cmbset(int a){//1~aまでの階乗と階乗数の逆元のmod(mod)を用意 O(a)
  factset(a);
  invfact[a]=power(fact[a],mod-2);
  invfact[0]=1;
  FORD(i,a,1){
    invfact[i]=mul(invfact[i+1],i+1);
  }

}

LL cmb(int n,int r){//nCr%mod  (cmbset後に使用)
  if(n<r||r<0||n<0)return 0;
  return mul(fact[n],mul(invfact[r],invfact[n-r]));
}

LL prm(int n,int r){//nPr%mod
    return mul(cmb(n,r),fact[n]);
}

LL homo(int n,int r){//nHr%mod
  return cmb(n+r-1,r);
}


int main(){
	int b,w;
	cin>>b>>w;
	cmbset(b+w+1);
  vector<LL> pw(b+w+1,0);
  vector<LL> pb(b+w+1,0);
  vector<LL> bb(b+w+1,1);
  FORQ(i,1,b+w+1){
    bb[i]=dvs(bb[i-1],2);
  }
  pw[w]=bb[w];
  pb[b]=bb[b];
  FOR(i,w+1,b+w){
    pw[i]=add(pw[i-1],dvs(mul(cmb(i-1,w-1),bb[i-1]),2));
  }
  FOR(i,b+1,w+b){
    pb[i]=add(pb[i-1],dvs(mul(cmb(i-1,b-1),bb[i-1]),2));

  }
  FOR(i,0,b+w){
      cerr<<" pb[i]:"<<pb[i]<<endl;
      cerr<<" pw[i]:"<<pw[i]<<endl;
    cout<<mul(sub(1+pw[i],pb[i]),bb[1])<<endl;
  }

    return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	int x, y;
	cin >> x >> y;
	yorn((y - x * 2) % 2 == 0 && 4 * x >= y && 2 * x <= y);
	return 0;
}

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

#include <bits/stdc++.h>

int main() {
  int n, p;
  cin >> n >> p;
  bool flag = false;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    flag |= (a % 2 == 1);
  }

  if (flag) {
    cout << static_cast<ll>(pow(2, n - 1)) << endl;
  } else {
    if (p == 0)
      cout << static_cast<ll>(pow(2, n)) << endl;
    else
      cout << 0 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<'\n';}}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
const int max_n=10000000;
ll fac[max_n], finv[max_n], inv[max_n];
// テーブルを作る前処理 O(max_n)
void init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < max_n; 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;
    }
}
// 二項係数計算 O(1)
long long modcom(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;
}
ll solve(ll n,ll r,ll k){
    if(k==0)return 0;
    ll res=modcom(n,r);
    ll b=res;
    rep(i,k-1){
        b=(b*2+modcom(n+i,r-1)+modcom(n+i,r+i+1))%mod;
        res+=b;
        res%=mod;
    }
    return res;
}
int main() {
    init();
    ll a,b,c,d;cin>>a>>b>>c>>d;
    ll ans=solve(a+b,b,c+d-a-b+1)-solve(b+c+1,b,d-b)-solve(a+d+1,d+1,c-a);
    ans%=mod;
    ans=(ans+mod)%mod;
    out(ans);
}

Measured memory_bytes: 234624
#include <vector>
#include <iostream>
using namespace std;
int main()
{
	
	int n = 0;
	long long int result = 0;
	cin >> n;
	vector <int> a(n + 1);
	vector <int> b(n + 1);
	vector <int> left(n + 2);
	vector <int> right(n + 2);
	left[0] = -1;
	right[n + 1] = -1;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		b[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		int s = b[i];
		result += (((long long)left[s] + 1) * ((long long)right[s + right[s] + 1] + 1) + ((long long)right[s] + 1) * ((long long)left[s - left[s] - 1] + 1)) * i;
		left[s + right[s] + 1] += (left[s] + 1);
		right[s - left[s] - 1] += (right[s] + 1);
	}
	cout << result;
	
	
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long int ll;

vector<int> pos,neg;

int main(){
    int n; cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    if(a[0]>0){
        cout << -1 << endl;
        return 0;
    }
    for(int i=1;i<n;i++){
        if(a[i]-a[i-1]>1){
            cout << -1 << endl;
            return 0;
        }
    }
    ll ans=0;
    for(int i=1;i<n;i++){
        if(a[i]==0){
            continue;
        }
        else if(a[i]-a[i-1]==1){
            ans++;
        }
        else{
            ans+=a[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRT(v) sort(v.begin(),v.end())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    //入力
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    //処理
    //出力
    if((abs(a-b)<=d && abs(b-c)<=d) || abs(a-c)<=d) cout << "Yes" << ENT;
    else cout << "No" << ENT;
    return 0;
}

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


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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int di2[] = {1, 1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1};
const int dj2[] = {1, -1, 1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;


int main(){
  int n, u, v;
  cin >> n >> u >> v;
  vector<vector<int>> g(n+1);
  rep(i, n-1) {
    int a, b; cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> dist1(n+1, INF), dist2(n+1, INF);
  queue<int> q;

  dist1[u] = 0;
  q.push(u);
  while(!q.empty()) {
    int now = q.front(); q.pop();

    for(auto next : g[now]) {
      if(chmin(dist1[next], dist1[now]+1)) q.push(next);
    }
  }

  dist2[v] = 0;
  q.push(v);
  while(!q.empty()) {
    int now = q.front(); q.pop();

    for(auto next : g[now]) {
      if(chmin(dist2[next], dist2[now]+1)) q.push(next);
    }
  }

  int ans = 0;
  for(int x = 1; x <= n; ++x) {
    if(dist1[x] >= dist2[x]) continue;
    chmax(ans, dist2[x]-1);
  }
  cout << ans << endl;
}

Measured memory_bytes: 9576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122



int main() {
    int n, m;
    cin >> n >> m;
    int s[m], c[m];
    rep(i, 0, m) {
        cin >> s[i] >> c[i];
        s[i]--;
    }
    rep(i, 0, 1000) {
        string x = to_string(i);
        if ((int)x.size() != n) continue;
        bool ok = true;
        rep(i, 0, m) {
            if (x[s[i]] - '0' != c[i]) ok = false;
        }
        if (ok) {
            cout << x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 3696
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << endl; }

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

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


#line 2 "tmp.cpp"

// -1,0,1のいずれか. 0は未着色
bool isBipartite(int v, int par, int color, vector<int> &data, const vector<vi> &g) {
  if (data[v] != 0)
    return data[v] == color;
  data[v] = color;
  for (auto u : g[v]) {
    if (u == par)
      continue;
    if (!isBipartite(u, v, -color, data, g))
      return false;
  }
  return true;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<vi> g(n);
  REP(i, n) {
    string s;
    cin >> s;
    REP(j, n) {
      if (s[j] == '1') {
        g[i].push_back(j);
      }
    }
  }

  vi data(n, 0);
  if (!isBipartite(0, -1, 1, data, g)) {
    cout << -1 << endl;
    return 0;
  }

  int ans = 0;
  REP(i, n) {
    queue<pair<int, int>> q;
    vector<bool> visited(n, false);
    visited[i] = true;
    int tmp = 1;
    q.push({i, 1});
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      chmax(tmp, p.second);
      for (const auto el : g[p.first]) {
        if (!visited[el]) {
          q.push({el, p.second + 1});
          visited[el] = true;
        }
      }
    }
    chmax(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

int n;
int main()
{
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> n;
    cout <<(n-1)/2 << endl;
}


Measured memory_bytes: 256
/**
 * author  : UshanGhosh
 * created : 2020-08-07 11:39:18
**/ 

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

#define    ll      long long
#define    pii     pair<int,int>
#define    vii     vector<int>
#define    vcc     vector<char>
#define    pll     pair<long long, long long>
#define    mem     memset
#define    sof     sizeof
#define    co1     __builtin_popcountll
#define    PB      push_back
#define    UB      upper_bound
#define    LB      lower_bound
#define    MP      make_pair
#define    TS      to_string
#define    F       first
#define    S       second
#define    endl    '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long a,b,c,d,e,f,i=0,j,k,m,n,o,x,y;
    cin>>n;
    if(__gcd(n,(ll)10)!=1){
        cout<<-1<<"\n";
        return 0;
    }
    ll v=0;
    while(1){
        i++;
        v=(v*10+7)%n;
        if(v==0){
            cout<<i;
            break;
        }
    }
}

Measured memory_bytes: 3624
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

int main(int argc, const char * argv[]) {
  ll n, m;
  cin >> n >> m;

  ll x[n], y[m];
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> y[i];
  }

  ll sumx = 0, sumy = 0;
  for (int i = 0; i < n; i++) {
    sumx = (sumx + (1 - n + 2 * i) * x[i]) % mod;
  }
  for (int i = 0; i < m; i++) {
    sumy = (sumy + (1 - m + 2 * i) * y[i]) % mod;
  }
  cout << sumx * sumy % mod << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>

using namespace std;
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
//typedef boost::multiprecision::cpp_int bigint;

ll N,L;
queue<ll> ans;

int main() {
	cin >> N >> L;
		ll prev;
		cin >> prev;
		for (ll n = 1; n <= N-1; n++) {
			ll a;
			cin >> a;
			if (prev + a >= L) {
				cout << "Possible" << endl;
				for (ll f = 1; f < n; f++)cout << f << endl;
				for (ll f = N - 1; f >= n; f--)cout << f << endl;
				return 0;
			}
			prev = a;
		}
		cout << "Impossible" << endl;
		return 0;
}


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


int main() {
	int want = 0, hi = 0, low = 0;
	cin >> want >> low >> hi;

	bool ans = false;

	while (low <= hi) {
		if (low % want == 0) {
			ans = true;
			break;
		}

		low++;
	}

	if (ans) {
		cout << "OK" << endl;
	}

	else {
		cout << "NG" << endl;
	}
}

Measured memory_bytes: 3632
/** Author: Dwai
 *  Omae wa mou shindeiru!
**/

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

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define all(a) (a).begin(),(a).end()
#define fr(i,a,b) for (i = a; i <= b; i++)
#define frr(i,a,b) for (i = a; i >= b; i--)
#define rep(i,n) for (i = 0 ; i < n; i++)
#define repr(i,n) for (i = n - 1; i >= 0; i--)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
#define flushinput   cin.ignore(numeric_limits<streamsize>::max(),'\n');

void debug_out() { cerr << endl; }

void clock_out(){
  cerr<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
}

void fileio(){
  freopen("/home/dwai/Desktop/cp/input.txt","r", stdin);
  freopen("/home/dwai/Desktop/cp/output.txt", "w", stdout);
  freopen("/home/dwai/Desktop/cp/debug.txt", "w", stderr);
}

void ofileio(){
  freopen("input.txt","r", stdin);
  freopen("output.txt", "w", stdout); 
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << H;
  debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define fio() fileio()
#define ofio() fileio()
#define clock() clock_out()
#else
#define debug(...) 42
#define fio() 42
#define ofio() ofileio()
#define clock() 42
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef map<ll,ll> mll;

int IT_MAX = 1 << 20;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;


ll factorial(ll n){
	ll i;
	ll ans=1;
	fr(i,1,n)
	{
		ans*=i;
	}
	return ans;
}

void solve()
{
	ll n;cin>>n;
	ll a[n],b[n];
	ll i;
	rep(i,n) cin>>a[i];
	rep(i,n) cin>>b[i];

	ll c1=1,c2=1;
	vector<ll> ind;
	fr(i,1,n) ind.eb(i);
	rep(i,n)
	{
		auto itr=lower_bound(all(ind),a[i]);
		int x=itr-ind.begin();
		c1+=x*factorial(n-i-1);
		ind.erase(itr);
	}
	fr(i,1,n) ind.eb(i);
	rep(i,n)
	{
		auto itr=lower_bound(all(ind),b[i]);
		int x=itr-ind.begin();
		c2+=x*factorial(n-i-1);
		ind.erase(itr);
	}

	cout<<abs(c1-c2);
}

int main()
{
//	fio();
	fast
	ll t=1;
	//cin>>t;

	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int main(){
	int N, M;
	while(cin >> N >> M){
		vector<vector<int>> init(2, vector<int>(N+1, 0));
		auto dp = init;
		for(int i=0;i<=N;i++) dp[i==0?1:0][i] = 1;
		for(int turn=0;turn<M;turn++){
			auto next = init;
			for(int j=0;j<2;j++){
				for(int i=0;i<=N;i++){
					if(i > 0){
						next[i==1?1:j][i-1] = (next[i==1?1:j][i-1]+dp[j][i])%MOD;
						next[i==1?1:j][i  ] = (next[i==1?1:j][i  ]+dp[j][i])%MOD;
					}
					if(i < N){
						next[j][i  ] = (next[j][i  ]+dp[j][i])%MOD;
						next[j][i+1] = (next[j][i+1]+dp[j][i])%MOD;
					}
				}
			}
			dp = next;
		}
		int res = 0;
		for(int i=0;i<=N;i++) res = (res+dp[1][i])%MOD;
		cout << res << endl;
	}
}


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


const double EPS = 1e-5;

struct P3{
  double x,y,z;
  P3(){}
  P3(double x,double y, double z):x(x),y(y),z(z) {}
  P3 operator + (const P3 &a) const{ return (P3){x+a.x, y+a.y, z+a.z}; }
  P3 operator - (const P3 &a) const{ return (P3){x-a.x, y-a.y, z-a.z}; }
  P3 operator / (double c) const{ return (P3){x/c, y/c, z/c}; }

};
P3 operator * (double c, const P3 &a){ return (P3){c * a.x, c * a.y, c * a.z}; }
P3 operator * (const P3 &a, double c){ return (P3){c * a.x, c * a.y, c * a.z}; }
//???????????°????????¨
ostream& operator<<(ostream& os,const P3& p) {
  os << "(" << p.x << "," <<p.y << "," << p.z << ")";
  return os;
}


struct L3{
  P3 a,b;
  L3(P3 a,P3 b):a(a),b(b){}
};


double norm(P3 a){ return a.x*a.x + a.y*a.y + a.z*a.z; }
double abs(P3 a){ return sqrt(norm(a)); }
double dot(P3 a, P3 b){ return a.x*b.x+ a.y*b.y + a.z*b.z; }
P3 cross(P3 a, P3 b){
  return (P3){a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x};
}

// ????????¨???????????¢
double distSP(L3 S, P3 p){
  double a = dot(S.b-S.a, S.b-S.a);
  double b = dot(S.b-S.a, S.a- p );
  double c = dot(S.a- p , S.a- p );
  double t = -b / a;
  if(t < 0) return abs(S.a - p);
  if(t > 1) return abs(S.b - p);
  return sqrt(a * t * t + 2 * b * t + c);
}

int N,Q;
P3 c[55];
double r[55];
long long l[55];

int main(){
  cin >> N >> Q;
  for(int i=0;i<N;i++){
    int x,y,z,rx; cin >>  x>> y >> z >> rx >> l[i];
    c[i] = P3( x, y, z );
    r[i] = rx;
  }
  for(int i=0;i<Q;i++){
    long long res = 0;
    int x1,y1,z1,x2,y2,z2;
    cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
    L3 s = L3( P3( x1, y1, z1 ), P3( x2, y2, z2 ) );
    for(int j=0;j<N;j++)
      if( r[j]+EPS > distSP( s, c[j] ) )
        res += l[j];    
    cout << res << endl;
  }  
}

Measured memory_bytes: 1172