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


void update(int node, std::vector<int>& weight, const std::vector<std::map<int, int>> link_list) {
    for (auto && l : link_list[node]) {
        if (weight[l.first] == -1 || weight[node] + l.second < weight[l.first]) {
            weight[l.first] = weight[node] + l.second;
            update(l.first, weight, link_list);
        }
    }
}


int main() {
    int n;
    std::cin >> n;

    std::vector<std::map<int, int>> link_list;
    for (int i = 0; i < n; i++) {
        int u, k;
        std::cin >> u >> k;
        std::map<int, int> map;
        for (int j = 0; j < k; j++) {
            int c, v;
            std::cin >> c >> v;
            map[c] = v;
        }
        link_list.emplace_back(map);
    }

    std::vector<int> weight(n, -1);
    weight[0] = 0;

    auto comp = [] (std::tuple<int, int, int> &lfs, std::tuple<int, int, int> &rhs) {
        return std::get<2>(lfs) > std::get<2>(rhs);
    };
    
    std::priority_queue<std::tuple<int, int, int>, std::vector<std::tuple<int, int, int>>, decltype(comp)> que(comp);
    for (auto && m : link_list[0]) {
        que.push(std::make_tuple(0, m.first, m.second));
    }

    while (!que.empty()) {
        auto val = que.top();
        que.pop();
        auto w = weight[std::get<0>(val)] + std::get<2>(val);
        if (weight[std::get<1>(val)] == -1 || w < weight[std::get<1>(val)]) {
            weight[std::get<1>(val)] = w;
            for (auto && m : link_list[std::get<1>(val)]) {
                que.push(std::make_tuple(std::get<1>(val), m.first, m.second));
            }
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << i << " " << weight[i] << std::endl;
    }
}




Measured memory_bytes: 3428
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) ((vec).begin(),(vec).end())
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
int rat;
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>rat;
	if(rat>=400&&rat<600) cout<<8<<endl;
	if(rat>=600&&rat<800) cout<<7<<endl;
	if(rat>=800&&rat<1000) cout<<6<<endl;
	if(rat>=1000&&rat<1200) cout<<5<<endl;
	if(rat>=1200&&rat<1400) cout<<4<<endl;
	if(rat>=1400&&rat<1600) cout<<3<<endl;
	if(rat>=1600&&rat<1800) cout<<2<<endl;
	if(rat>=1800&&rat<2000) cout<<1<<endl;
	return 0;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
using namespace std;
const ll M = 1e9 + 7;
ll n,ans;
void solve()
{
    ll n;
    cin>>n;
    ll arr[n];
    ll s=0;
    map<ll,ll>f;
    for(ll i=0;i<n;i++)cin>>arr[i],f[arr[i]]++,s=s+arr[i];
    ll k;
    cin>>k;
    for(ll i=0;i<k;i++)
    {
        ll a,b;
        cin>>a>>b;
        s=s-f[a]*a;
        s=s+f[a]*b;
        f[b]=f[b]+f[a];
        f[a]=0;
        cout<<s<<endl;
    }
}
int main()
{
    int t;
    t=1;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 10344
import bisect

n = int(input())
l = list(map(int, input().split()))

l.sort()

ans = 0

for i in range(1, n - 1):
  for j in range(i + 1, n):
    if l[i] * 2 > l[j]:
      idx = bisect.bisect_left(l, l[j] - l[i] + 0.5)
      ans += max(i - idx, 0)

print(ans)

Measured memory_bytes: 43356
import java.util.Scanner;

public class Main {
    static final int MX = 100_000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long a[] = new long[n];
        long allxor = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            allxor ^= a[i];
        }

        for (int i = 0; i < n; i++) {
            System.out.print((allxor ^ a[i]) + " ");
        }
        System.out.println();
    }
}

Measured memory_bytes: 62348
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#define rep(i, n) for(Int (i) = 0; (i) < (n); ++(i))
#define debug(var) cout << #var << ": " << var << endl
using namespace std;
using Int = int64_t;
using Uint = uint64_t;
constexpr Uint mod = 1e9 + 7;
constexpr Int INF = LLONG_MAX;
constexpr Int Int_max = LLONG_MAX;
constexpr Int Int_min = LLONG_MIN;
using Container = vector<Int>;
template<typename T>
using Grid = vector<vector<T>>; // 二次元配列。[y][x]
template<typename T, typename U>
using Umap = unordered_map<T, U>;
template<typename T>
using Uset = unordered_set<T>;
template<typename T>
using P = pair<T, T>;


int main() {

	Int H, A; cin >> H >> A;
	if (H % A == 0)cout << H / A;
	else cout << H / A + 1;

}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main() {
  int N;
  cin >> N;
  vector<int> freq(N, 0);
  rep(i, N) {
    int a;
    cin >> a;
    a--;
    freq[a]++;
  }
  sort(freq.begin(), freq.end());
  vector<int> acc(1, 0);
  copy(freq.begin(), freq.end(), back_inserter(acc));
  rep(i, N) { acc[i + 1] += acc[i]; }

  vector<int> result(N);
  int j = 1;
  rrep(i, N) {
    const int K = i + 1;
    while (true) {
      const int m = lower_bound(freq.begin(), freq.end(), j) - freq.begin();
      bool cond = false;
      if (N - m >= K) {
        cond = true;
      } else {
        int L = K - (N - m);
        if (acc[m] >= j * L) {
          cond = true;
        }
      }

      if (cond) {
        j++;
      } else {
        break;
      }
    }
    result[i] = j - 1;
  }

  rep(i, N) { cout << result[i] << "\n"; }
  return 0;
}

Measured memory_bytes: 4464
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int t, res;
string msg;
vs reslog;

void dfs(int, string, vs);

int main(void){
    for(string num; cin >> t >> num, t;){
        res = -1;
        msg = "error";

        vs log;
        if(t == toInt(num)){
            res = t;
            msg = "ok";

            log.pb(num);
            reslog = log;
        }
        else dfs(0, num, log);
        
        if(msg == "ok"){
            cout << res;
            rep(i, reslog.size()){
                cout << " " << reslog[i];
            }
            cout << endl;
        }
        else{
            cout << msg << endl;
        }
    }

	return 0;
}

void dfs(int sum, string num, vs log){
    if(t < sum){
        return;
    }
    if(num.size() == 0){
        if(res == sum){
            msg = "rejected";
        }
        else if(res < sum){
            res = sum;
            reslog = log;
            msg = "ok";
        }

        return;
    }

    range(i, 1, num.size() + 1){
        string diff = num.substr(0, i);
        string nextnum = num.substr(i);

        //if(i != 1 && diff.at(0) == '0') continue;
        vs nextlog = log;
        nextlog.pb(diff);

        dfs(sum + toInt(diff), nextnum, nextlog);
    }
}

Measured memory_bytes: 1236
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;
//cout << std::fixed << std::setprecision(15) << y << endl;
/*正の整数 Nが与えられます。 
N に対して、以下の操作を繰り返し行うことを考えます。以下の条件を全て満たす正の整数zを選ぶ。
ある素数 pと正の整数 eを用いて、z=p^eと表せる
Nがzで割り切れる以前の操作で選んだどの整数とも異なるNを、N/zに置き換える
最大で何回操作を行うことができるか求めてください。*/
//aでex回割れる
vector<pair<ll,ll>> prime_factorize(ll N){
    vector<pair<ll,ll>> ret;
    for(ll a = 2; a * a <= N; a++){
        if(N % a != 0) continue;
        ll ex = 0;
        while(N % a == 0){
            ex++;
            N /= a;
        }
        ret.push_back({a, ex});
    }
    if(N != 1) ret.push_back({N, 1});
    return ret;
}
 
int main(){
    ll N;
    cin >> N;

    ll ans = 0;
    rep(num,1,N){
      ll n = num;
      ll ab = 1;
      auto v = prime_factorize(n);
      for(auto e : v){
        ab *= e.second + 1;
      }
      ans += ab;
    }
    cout << ans << endl;
    return 0;
}

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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
// constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

//トポロジカルソートO(E+V)
bool tsort(Graph &graph, Array &order) {
    int n = graph.size(), k = 0;
    Array in(n);
    for(auto &es : graph)
        for(auto &e : es)
            in[e.to]++;
    priority_queue<ll, Array, greater<ll>> que;
    REP(i, n)
    if(in[i] == 0)
        que.push(i);
    while(que.size()) {
        int v = que.top();
        que.pop();
        order.push_back(v);
        for(auto &e : graph[v])
            if(--in[e.to] == 0)
                que.push(e.to);
    }
    if(order.size() != n)
        return false;
    else
        return true;
}

void solve() {
    ll n;
    cin >> n;
    vvec<ll> a(n, vec<ll>(n));
    Graph g(n * n);
    REP(i, n) {
        REP(j, n - 1) {
            cin >> a[i][j];
            a[i][j]--;
        }
        REP(j, n - 2) {
            ll u = min(i * n + a[i][j], a[i][j] * n + i);
            ll v = min(i * n + a[i][j + 1], a[i][j + 1] * n + i);
            add_edge(g, u, v, 1, false, 1);
        }
    }
    vec<ll> o;
    if(!tsort(g, o)) {
        cout << -1 << en;
        return;
    }

    Array dp(n * n, 1);
    ll ans = 0;
    for(auto v : o) {
        chmax(ans, dp[v]);
        for(auto e : g[v]) {
            chmax(dp[e.to], dp[v] + 1);
        }
    }
    cout << ans << en;
}

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

    solve();
    // ll t;cin>>t;REP(i,t) solve();

    return 0;
}


Measured memory_bytes: 96712
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <vector>
#include <functional>
#include <cassert>
#include <cmath>
#include <map>
#include <set>
#include <queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	string a, b;
	cin >> a >> b;
	int ret = 0;
	for (int i = 0; i < 3; i++) {
		if (a[i] == b[i]) ret++;
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
t, a = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

temps = [t - h[i]*0.006 for i in range(len(h))]
diffs = [abs(a - temps[i]) for i in range(len(temps))]
print(diffs.index(min(diffs)) + 1)

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

 
int main() {

    int n,k;
    cin >> n >> k;

    ll ans=k;
    if(n==1) {
        cout<<ans<<endl;
        return 0;
    }

    rep(i,n-1) {
        ans*=(ll)(k-1);
    }

    cout << ans << endl;

 return 0;
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.buffer.readline


def solver(N, K, A):
    i = 0
    i_list = [0]
    reached = [False for _ in range(N)]

    while True:
        next_i = A[i]
        if reached[next_i]:
            break

        reached[next_i] = True
        i_list.append(next_i)
        i = next_i

    m = i_list.index(next_i)

    if m >= K:
        return i_list[K] + 1

    le = len(i_list) - m
    K -= m
    ind = K % le

    return i_list[m + ind] + 1


def run():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = [a - 1 for a in A]

    ans = solver(N, K, A)
    print(ans)


run()


Measured memory_bytes: 27900
#include<stdio.h>
#define M 100
#define INFTY (1<<21)
#define WHITE 1
#define BLACK 2
#define GRAY 3

int n;
int G[M][M];

int main(){
  void dijkstra();
  int i;
  int j;
  int u;
  int k;
  int v;
  int c;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      G[i][j] = INFTY;
    }
  }

  for(i=0;i<n;i++){
    scanf(" %d %d",&u,&k);
    for(j=0;j<k;j++){
      scanf(" %d %d",&v,&c);
      G[u][v] = c;
    }
  }
  dijkstra();
  return 0;
}

void dijkstra(){
  int mincost = INFTY;
  int i;
  int u = -1;
  int v;
  int color[M];
  int d[M];

  for(i=0;i<n;i++){
    color[i] = INFTY;
    d[i] = INFTY;
  }

  color[0] = 0;
  d[0] = 0;

  while(1){
    mincost = INFTY;
    u = -1;
    for(i=0;i<n;i++){
      if(mincost > d[i] && color[i] != BLACK){
        u = i;
        mincost = d[i];
      }
    }
    if(u == -1) break;
    color[u] = BLACK;
    for(v=0;v<n;v++){
      if(color[v] != BLACK && G[u][v] != INFTY){
        if(d[v] > d[u] + G[u][v]){
          d[v] = d[u] + G[u][v];
          color[v] = GRAY;
        }
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d ",i);
    if(d[i] == INFTY) printf("-1\n",i);
    else printf("%d\n",d[i]);
  }
}



Measured memory_bytes: 2112
/**   Created by: Marcos Portales
          Codeforces User: marcosportales
          Country: Cuba
          Copyright                    */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
#define vi vector<int>
#define sz(a) int((a).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,n) for(int i=(1);i<=(n);i++)
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 200005;
const int mod = 1000000007;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 2000000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Test.insert(x)late ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return (pwur * pwur) % mod;
}
int modinv(int x){
    return qpow(x,mod-2);
}

/// My Code -------------------------------------------------

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));
    //freopen("a.in","r",stdin);
    //freopen("a.in","w",stdout);
    int n;
    cin>>n;
    vector<ull>v(2);
    v[0]=2,v[1]=1;
    for(int i=2;i<=n;i++){
        v.pb(v[i-1]+v[i-2]);
    }
    cout<<v[n];

    return 0;
}


Measured memory_bytes: 3504
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void print_YES_NO(bool answer){cout<<(answer?"YES":"NO")<<endl;}
void print_Yes_No(bool answer){cout<<(answer?"Yes":"No")<<endl;}
void print_POSSIBLE_IMPOSSIBLE(bool answer){cout<<(answer?"POSSIBLE":"IMPOSSIBLE")<<endl;}

int t[505][505];
priority_queue<P> q1;

int main(){
	int n,m,q;
	int i,j,k;
	int a,b,c;
	cin>>n>>m>>q;
	for(i=0;i<m;i++){
		cin>>a>>b;
		q1.push(make_pair(a,b));
	}
	for(i=n;i>=0;i--){
		while(!q1.empty() && q1.top().first>=i){
			t[i][q1.top().second]++;
			q1.pop();
		}
		for(j=1;j<=n;j++){
			t[i][j]+=t[i+1][j]+t[i][j-1]-t[i+1][j-1];
		}
	}
	for(i=0;i<q;i++){
		cin>>a>>b;
		cout<<t[a][b]<<endl;
	}
}


Measured memory_bytes: 3568
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<u64>();
    let (mut a, mut b, mut c) = (line[0], line[1], line[2]);

    if a%2 == 0 && a == b && b == c{
        println!("-1");
        return;
    }

    let mut cur = 0;
    while a%2 == 0 && b%2 == 0 && c%2 == 0{
        let (pa, pb, pc) = (a, b, c);
        a = pb/2 + pc/2;
        b = pa/2 + pc/2;
        c = pa/2 + pb/2;
        cur += 1;
    }

    println!("{}", cur);
}


Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())
#define mp make_pair

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef pair<int, int> P;
//typedef pair<int, pair<int, int> > PP;
//const int MAX=;



int main(){
	string S;
	cin>>S;
	if(S[0]==S[1] || S[1]==S[2] || S[2]==S[3])cout<<"Bad";
	else cout<<"Good";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vbool vector<bool>
#define umap unordered_map
#define uset unordered_set
#define frw(i, a, b) for(int i = a; i < b; i++)
#define bck(i, a, b) for(int i = a; i > b; i--)
#define fi first
#define se second
#define pow asdihagsiduh
#define pub push_back
#define in insert
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) int(a.size())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define vpll vector<pll>
#define vpii vector<pii>

#define trace(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> 
void ZZ(const char* name, Arg1&& arg1){
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

vector<vbool> vis;
vector<vi> dp;
int n, m;

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	vis.assign(n + 1, vbool (m + 1, 1));
	dp.assign(n + 1, vi (m + 1, 0));
	frw(i, 1, n + 1){
		frw(j, 1, m + 1){
			char c; cin >> c;
			if(c == '.')	vis[i][j] = 0;
		}
	}
	frw(i, 1, m + 1){
		if(vis[1][i])
			break;
		else
			dp[1][i] = 1;
	}
	frw(i, 1, n + 1){
		if(vis[i][1])
			break;
		else
			dp[i][1] = 1;
	}
	frw(i, 2, n + 1){
		frw(j, 2, m + 1){
			if(!vis[i][j])
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			else
				dp[i][j] = 0;
			dp[i][j] %= MOD;
		}
	}
	cout << dp[n][m];
}

Measured memory_bytes: 4352
n,m = map(int,input().split())
h = [int(i) for i in input().split()]
nn = [1]*n
for _ in range(m):
    a,b = map(int,input().split())
    if h[a-1] ==h[b-1]:
        nn[a-1]=0
        nn[b-1]=0
    elif h[a-1] < h[b-1]:
        nn[a-1]=0
    else:
        nn[b-1]=0

print(sum(nn))

Measured memory_bytes: 20116
#include<stdio.h>
int a[100][100];
int flag;
int n,m;
int s[10000];
int dfs(int x,int y){
	if(x==y){
		flag++;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(s[i]==0&&a[x][i]==1){
			s[i]=1;
			dfs(i,y);
			s[i]=0;
		}
	}
}
int main(){
	
	scanf("%d %d",&n,&m);
	int x,y;
	for(int i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		a[x][y]=a[y][x]=1;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==1){
				flag=0;
				s[i]=1;
				dfs(i,j);
				s[i]=0;
				if(flag==1)
				sum+=flag;
			}
		}
	}
	printf("%d",sum/2);
} 

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

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

    vector<int> left;
    vector<int> right;
    int s = 0;
    for(int i = 0; i < m; i++){
        cin >> s;
        if(s <= x){
            left.push_back(s);
        }else{
            right.push_back(s);
        }
    }

    int ans = min(left.size(), right.size());

    cout << ans << endl;

    return 0;
}

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

using namespace std;
using vi = vector<int>;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}


struct Graph {
  vector<vector<int>> edge;
  Graph(int n = 0) {
    resize(n);
  }
  void resize(int n) {
    edge.resize(n, vector<int>());
  }
  void addEdge(int from, int to) {
    edge[from].push_back(to);
  }
};
Graph G;

int main() {
  int in(N); int in(M);

  G.resize(N);
  vi incoming(N, 0);
  rep(i, M) {
    int in(a); int in(b);
    --a, --b;
    G.addEdge(a, b);
    ++incoming[b];
  }

  queue<int> q;
  rep(i, N)
    if (incoming[i] == 0) q.push(i);

  // トポロジカルソート
  vi sorted;
  while (!q.empty()) {
    int p = q.front(); q.pop();
    sorted.push_back(p);
    for (const auto& to : G.edge[p]) {
      --incoming[to];
      if (incoming[to] == 0)
        q.push(to);
    }
  }

  vi dp(N, 0);
  for (const auto& from : sorted)
    for (const auto& to : G.edge[from])
      chmax(dp[to], dp[from] + 1);

  int ans = 0;
  rep(i, N)
    chmax(ans, dp[i]);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 7032
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

char c[]={'3','5','7'};
string n;
int ans=0;
void dfs(int v,string s){
    if(v>=-1){
        bool flag=true;
        rep(i,3)flag&=(s.find(c[i])!=string::npos);
        if(flag&&s.size()<n.size()) ++ans;
        else if(flag&&s<=n)++ans;
    }
    else return;
    rep(i,3){
        dfs(v-1,s+c[i]);
    }
}
int main(){
    cin>>n;
    dfs(n.size()-1,"");
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> xl(n), yl(n), xr(n), yr(n); for (int i = 0; i < n; ++i) cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
  V<> xs, ys;
  for (int i = 0; i < n; ++i) {
    xs.push_back(xl[i]);
    xs.push_back(xr[i]);
    ys.push_back(yl[i]);
    ys.push_back(yr[i]);
  }
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));
  sort(begin(ys), end(ys));
  ys.erase(unique(begin(ys), end(ys)), end(ys));
  int h = xs.size(), w = ys.size();
  VV<> a; assign(a, h, w);
  for (int i = 0; i < n; ++i) {
    xl[i] = distance(begin(xs), lower_bound(begin(xs), end(xs), xl[i]));
    xr[i] = distance(begin(xs), lower_bound(begin(xs), end(xs), xr[i]));
    yl[i] = distance(begin(ys), lower_bound(begin(ys), end(ys), yl[i]));
    yr[i] = distance(begin(ys), lower_bound(begin(ys), end(ys), yr[i]));
    ++a[xr[i]][yr[i]];
    --a[xr[i]][yl[i]];
    --a[xl[i]][yr[i]];
    ++a[xl[i]][yl[i]];
  }
  for (int x = 0; x < h; ++x) for (int y = 0; y < w - 1; ++y) a[x][y + 1] += a[x][y];
  for (int y = 0; y < w; ++y) for (int x = 0; x < h - 1; ++x) a[x + 1][y] += a[x][y];
  lint res = 0;
  for (int x = 0; x < h - 1; ++x) for (int y = 0; y < w - 1; ++y) {
    lint wx = xs[x + 1] - xs[x], wy = ys[y + 1] - ys[y];
    res += !!a[x][y] * wx * wy;
  }
  cout << res << '\n';
}


Measured memory_bytes: 65580
#!/usr/bin/env python3
#AGC17 A

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,p = map(int,sys.stdin.readline().split())
a = list(map(int,sys.stdin.readline().split()))
fact = [1]*51
for i in range(1,51):
    fact[i] = fact[i-1]*i
def comb(n,r):
    return fact[n]//fact[n-r]//fact[r]
x = list(map(lambda x:x % 2,a))
c = x.count(1)
ans = 0
if p:
    for i in range(c+1):
        if i % 2:
            for j in range(n-c+1):
                ans += comb(c,i)*comb(n-c,j)
else:
    for i in range(c+1):
        if i % 2 == 0:
            for j in range(n-c+1):
                ans += comb(c,i)*comb(n-c,j)
print(ans)


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int prise, num;
	int total_prise = 0, total_num = 0, total_kinds = 0;
	while(scanf("%d,%d", &prise, &num) != EOF){
		total_kinds++;
		total_prise += (prise * num);
		total_num += num;
	}
	printf("%d\n", total_prise);
	double average_num = (double)total_num / (double)total_kinds;
	if(average_num - floor(average_num) < 0.5) printf("%d\n", (int)floor(average_num));
	else printf("%d\n", (int)ceil(average_num));
	return 0;
}

Measured memory_bytes: 3176
# https://atcoder.jp/contests/abc099/tasks/abc099_d
# さまざまな合わせ技
# ダイクストラ、全探索

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため



# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations

# from scipy.sparse.csgraph import dijkstra
# from scipy.sparse import csr_matrix, lil_matrix
# 0 まずはダイクストラでX→Yの最小コストを求めておく #えーーーーこれ想定されてないの？
# 1 座標ごとに3つのグループわけができる(n=1のときだけ場合分け
# 2 グループごとに色をカウント
# 3 各グループの色を仮定して全探索

N, C = read_ints()
D = read_matrix(C)
# D = csr_matrix(D)
# D = dijkstra(D)


# 1 座標のグループわけ
Cmap = read_matrix(N)

if N == 1:
    print(0)
    exit()

lsbymod = defaultdict(lambda: [])
for i in range(N):
    for j in range(N):
        lsbymod[(i + j + 2) % 3].append(Cmap[i][j] - 1)

# グループごとに色のカウント
for k, v in lsbymod.items():
    lsbymod[k] = Counter(v)

# 各グループの色を仮定して全探索


# print(D)
# print(lsbymod)


def ret_score(*arg):
    # 各仮定から違和感を計算
    ret = 0
    for i in range(3):
        for k, v in lsbymod[i].items():
            ret += v * D[k][arg[i]]
    return ret


ans = 2**63
for a, b, c in permutations(range(C), 3):
    # print(a, b, c, ret_score(a, b, c))
    ans = min(ans, ret_score(a, b, c))

print(ans)


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

int main() {
  int n,m;
  long long ans=1;
  cin>>n>>m;
  int b[m];
  rep(i,m){
    cin>>b[i];
    if(i>0&&b[i]==b[i-1]+1)
      ans=0;
  }
  if(ans==0)
    cout<<ans<<endl;
  
  
  else{
    long long a[n];

    a[0]=1;a[1]=1;
    rep(i,n-1){
      a[i+2]=a[i]+a[i+1];
      a[i+2]%=1000000007;
    }
  
    rep(i,m+1){
      if(i==0){
        if(m==0)
          ans*=a[n];
        else
          ans*=a[b[0]-1];
      }else if(i==m){
        ans*=a[n-1-b[m-1]];
      }else {
        ans*=a[b[i]-b[i-1]-2];
      }
      ans%=1000000007;
      
    }
    cout<<ans<<endl;
    
  }
  
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int main(){
    int h, w;
    cin >> h >> w;
    if(h==1 || w==1){
        cout << "1\n";
        exit(0);
    }
    int64_t res = (int64_t)h*w;
    if(res%2 != 0)
        res++;
    res /= 2;
    cout << res << '\n';
    return 0;
}


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

int main(void){
	int t, n, s, f, sum;
	while(1){
		cin >> t;
		if (t == 0) break;
		cin >> n;
		sum = 0;
		for(int i = 0; i < n; i++){
			cin >> s >> f;
			sum += f-s;
		}
		if(sum >= t)cout << "OK";
		else cout << t - sum;
		cout << endl; 
	}
	return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int N;
    vector <long long int> v;
    cin>>N;
    for(long long int i=1; i*i<=N; i++)
    {
        if(N%i==0)
        {
            v.push_back(i+N/i-2);

        }
    }

    cout<<*min_element(v.begin(), v.end())<<endl;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf INT_MAX
#define INF 9223372036854775807
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(int *)a-*(int *)b;
}

int main(void){
	char s[201],t[101],u[101];
	int i,j,f=0;
	chin(s);
	if(strlen(s)%2){
		s[strlen(s)-1]=0;
		f=1;
	}
	while(1){
		memset(t,0,sizeof(t));
		memset(u,0,sizeof(u));
		for(i=0;i<strlen(s)/2;i++){
			t[i]=s[i];
		}
		for(j=0;s[i];i++,j++){
			u[j]=s[i];
		}
		if(strcmp(t,u)==0&&f){
			print(strlen(s));
			break;
		}
		f=1;
		s[strlen(s)-2]='\0';
	}
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a.at(i);
  sort(a.begin(),a.end());
  vector<long> res(a.at(n-1)+1);
  for(int i=0;i<a.at(n-1)+1;i++){
    long sum=0;
    for(int j=0;j<n;j++)sum+=pow(a.at(j)-i,2);
    res.at(i)=sum;
  }
  sort(res.begin(),res.end());
  cout<<res.at(0)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
	int sum=0;
	sum=s.length()-1-1;	 //erase前に長さを用いた計算
	s.erase(1,s.length()-2);


	cout<<s[0]<<sum<<s[1]<<endl;
}

Measured memory_bytes: 256
N, X, M = map(int, input().split())

def f(x):
    return (x ** 2) % M

m = [-1] * M

A = []
length = 0
total = 0
while m[X] == -1:
    A.append(X)
    m[X] = length
    length += 1
    total += X
    X = f(X)

# 周期
c = length - m[X]

# 周期の和
s = 0
for i in range(m[X], length):
    s += A[i]

res = 0
# 周期に入る前に終了
if N <= length:
    for i in range(N):
        res += A[i]
else:
    # とりあえず2週目に突入するまでの和を足して回数を減らす
    res += total
    N -= length
    # 周期をフルで使う回数分周期の和をかける
    res += s * (N // c)
    # 周期に満たないあまり
    N %= c
    for i in range(N):
        res += A[m[X] + i]

print(res)


Measured memory_bytes: 13096
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  ll X, Y; cin >> X >> Y;
  string result = (abs(X-Y)>=2) ? "Alice" : "Brown";
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, m;
string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	vector<ll> v;
	cin >> n;
	ll ans = INF;
	rep(i, 2, 1e6){
		if(n%i == 0){
			ans = min(n/i+i-2, ans);
		}	
	}
	if(ans != INF){
		print(ans)
	}
	else{
		print(n-1)
	}
	return 0;
}

Measured memory_bytes: 256
#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;
}

int bin[30];

int main() {
    bin[0] = 1;
    for (int i = 1; i < 30; i++) bin[i] = bin[i - 1] * 2;
    int n = read(), k = read();
    long double ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 28; j >= 0; j--) {
            if (1LL * bin[j] * i < 1LL * k) {
                ans += (long double)1 / (long double)bin[j + 1];
                break;
            }
        }
    }
    if (n >= k) ans += (long double)(n - k + 1);
    printf("%.10Lf\n", (ans / (long double)n - 1e-10));
    return 0; 
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  int ans = 1;
  for(int i=0;i<n;i++) {
    if(ans * 2 > ans + k)
      ans += k;
    else
      ans *= 2;
  }
  cout << ans << endl;

}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = scanner.nextInt();
        ArrayList<Pair> list = new ArrayList<>(n);
        for(int i = 0; i < n; i++) list.add(new Pair(scanner.nextInt(),i));
        Collections.sort(list, Collections.reverseOrder());
        long ans = 0;
        TreeSet<Integer> indices = new TreeSet<>();
        indices.add(list.get(0).b);
        indices.add(n);
        indices.add(-1);
        for(int i =1; i < n; i++) {
            int ind = list.get(i).b;
            int above = indices.ceiling(ind);
            int below = indices.floor(ind);
            if (above != n) {
                int next = indices.ceiling(above+1);
                ans += (long)(ind - below) * (long)(next - above) * list.get(i).a;
            }
            if (below != -1) {
                int next = indices.floor(below - 1);
                ans += (long)(below - next) * (long)(above - ind) * (long) list.get(i).a;
            }
            indices.add(list.get(i).b);
        }
        out.println(ans);
        out.flush();
    }
    static class Pair implements Comparable<Pair> {
        int a,b;
        Pair(int aa, int bb) {
            a = aa; b = bb;
        }
        public int compareTo(Pair o) {
            return a - o.a;
        }
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 47376
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

N = int(input())
lst = [list(map(int,input().split())) for i in range(N)]

lst_min = []
lst_max = []
for i in range(N):
  lst_min.append(lst[i][0])
  lst_max.append(lst[i][1])
lst_min.sort()
lst_max.sort()

if N % 2 == 1: ## 奇数
  median_min = lst_min[(N+1)//2 -1]
  median_max = lst_max[(N+1)//2 -1]
else: ## 偶数
  median_min = (lst_min[N//2 -1] + lst_min[N//2]) / 2.0
  median_max = (lst_max[N//2 -1] + lst_max[N//2]) / 2.0
  
if N % 2 == 1: ## 奇数
  ans = median_max - median_min + 1
else: ## 偶数
  ans = int(2*median_max - 2*median_min + 1)
  
print(ans)

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

int N,K;
string S;

int rot2();
int rot1();

int main()
{
	int h, hp();
	int t, tp();

    cin >> N >> K;
    // 文字列の入力
    cin >> S;

	t = tp();

	if (K*2 >= t) {
		cout << N - 1 << endl;
		return 0;
	}
	h = hp();
	cout << h+K*2 << endl;
	return 0;


	for (int i=0; i<K; i++) {
		if (rot2()) { // 幸福度が2増加する回転
//cout << S << endl;
			continue;
		}
		if (rot1()) { // 幸福度が1増加する回転
//cout << S << endl;
			continue;
		}
	}
    // 出力
    cout << hp() << endl;
    return 0;
}
int tp() {
	int ret=0;

	for (int i=0; i<N-1; i++) {
		if (S[i] != S[i+1]) ret++;
	}
	return ret;
}

int hp() {
	int i;
	int ret=0;

	for (i=0; i<N; i++) {
		switch(S[i]) {
		case 'R':
			if (i<N-1 && S[i] == S[i+1]) ret++;
			break;
		case 'L':
			if (i>0 && S[i] == S[i-1]) ret++;
			break;
		}
	}
	return ret;
}
/*
  反転させる部分の幸福度は変わらない
  反転させる部分の先頭と末尾の人の幸福度が変わる（可能性がある）
  向きが変わる箇所を反転させる部分の先頭・末尾にする

	幸福度が2上がるパターン
        00  ??        1?  1?
  (1) …RL…LR… → …RR…RR…
         ~~~~          ~~~~
        ??  00        ?1  ?1
  (2) …LR…RL… → …LL…LL…
         ~~~~          ~~~~
	幸福度が1上がるパターン
      0  ??      ?  1?
  (1) L…LR… → R…RR…
      ~~~~       ~~~~
      ?  00      0  ?1
  (2) R…RL… → L…LL…
      ~~~~       ~~~~
        ??  0      ?1  ?
  (3) …LR…R → …LL…L
         ~~~~       ~~~~
        00  ?      1?  0
  (4) …RL…L → …RR…R
         ~~~~       ~~~~
*/


Measured memory_bytes: 512
MOD=10**9+7

N=int(input())
alist=list(map(int,input().split()))

#print(alist)
blist=[0]*64
for a in alist:
  bblist=[]
  acopy=a
  while(acopy>0):
    bblist.append(acopy%2)
    acopy//=2
    
  #print(bblist)
  for b in range(len(bblist)):
    blist[-1-b]+=bblist[b]
      
blist.reverse()
#print(blist)
answer=0
pow=1
for i in range(64):
  answer+=blist[i]*(N-blist[i])*pow
  answer%=MOD
  pow*=2
  
print(answer)


Measured memory_bytes: 122936
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	map<int,int> cnt;
	rep(i, 12){
		int x; cin >> x; cnt[x]++;
	}
	for(auto i : cnt) if(i.second % 4){
		cout << "no" << endl;
		return 0;
	}
	cout << "yes" << endl;
	return 0;
}


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

#define int long long
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; }
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define COUT(x) cout << x << endl;
#define PB(x) push_back(x)
#define MP make_pair
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int INF = 1e9;
const int MOD = 1e9+7;

signed main(){
    string s; cin >> s;
    if(s=="AAA") cout<<"No"<<endl;
    else if(s=="BBB") cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define ins insert
#define fi first
#define se second
#define okay ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define llmax 2e18
#define PI 3.14159265
using namespace std;

int main() {
	okay;
//	int t;
//	cin>>t;
//	while(t--)
	{
		string s,t;
		cin>>s>>t;
		int ans=0;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]!=t[i])
			ans++;
		}
		cout<<ans;
	}
}

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

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

    double rate;
    double ans = 0;
    for (int p = 1; p <= n; p++) {
        rate = 1 / n;
        double point = p;
        while (point < k) {
            point *= 2;
            rate /= 2;
        }
        ans += rate;
    }

    cout << setprecision(9) << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
using namespace std;

int		main(void)
{
	int		N;
	cin >> N;
	vector<int> Paper(N);
	for (int i = 0; i < N; i++)
		cin >> Paper.at(i);
	for (auto &i : Paper)
	{
		if (i % 2 == 0)
		{
			if (i % 3 && i % 5)
			{
				cout << "DENIED" << endl;
				return 0;
			}
		}
	}
	cout << "APPROVED" << endl;
}

Measured memory_bytes: 256
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    lint b;
    while(true){
        cin >> b;
        if(b == 0){
            break;
        }
        lint n, m;
        for(m = sqrt(b*2) + 1 ; m > 0 ; m--){
            n = (b - (m * (m - 1)) / 2) / m;
            if(n * m + (m * (m - 1)) / 2 == b && n > 0){
                break;
            }
        }
        cout << n << " " << m << endl;
    }
    return 0;
}


Measured memory_bytes: 3088