akhauriyash/Code-Regression huggingface dataset:
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
import java.io.*;

public class Main {

	void tr(Object... os) {
		System.err.println(deepToString(os));
	}
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("src/aoj2105/input.txt"));
			System.setOut(new PrintStream(new FileOutputStream("src/aoj2105/result.txt")));
		} catch (FileNotFoundException e) {
		}
		new Main().run();
	}

	long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	Scanner sc;
	void run() {
		sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (;t-->0;) {
			solve();
		}
	}


	int[] minimize(char[] p) {
		int n = p.length / 2;
		int[] xs = new int[n];
		for (int i = 0; i < n; i++) {
			xs[i] = (p[i*2] - '0') * 16 + (p[i*2+1]-'0');
		}

		int i, j;
		for (int d = n; d > 0; d--) if (n % d == 0) {
			int[] res = new int[n / d];
			for (i = 0; i < res.length; i++) {
				res[i] = xs[i * d];
				for (j = 1; j < d; j++) {
					if (0 != xs[i * d + j])
						break;
				}
				if (j != d)
					break;
			}
			if (i == res.length) return res;
		}

		// don't reach here.
		if (true) throw new RuntimeException();
		return new int[0];
	}

	void solve()
	{
		int n = sc.nextInt();

		int[][] ps = new int[n][];
		for (int i = 0; i < n; i++) {
			char[] p = sc.next().toCharArray();
			ps[i] = minimize(p);
		}

		long lcm = ps[0].length;
		for (int i = 1; i < n; i++) {
			lcm = lcm * ps[i].length / gcd(lcm, ps[i].length);
			if (lcm > 1024) break;
		}
		if (lcm > 1024) {
			System.out.println("Too complex.");
			return;
		}
		for (int t = 0; t < lcm; t++) {
			int cur = 0;
			for (int i = 0; i < n; i++)
				if (t % (lcm / ps[i].length) == 0)
					cur |= ps[i][(int)(t * ps[i].length / lcm)];
			System.out.printf("%02X", cur);
		}
		System.out.println();

	}


}

Measured memory_bytes: 13000
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
          // Initialize
          var iN = cin.ReadInt;
          var iM = cin.ReadInt;
          var aiA = cin.ReadIntArray(iM);
          var iAns = 0;
          // Process
          iAns = iN-aiA.Sum();
          iAns = iAns < 0 ? -1 : iAns ;
          // Output
          WriteLine(iAns);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 29452
r,g,b,n = map(int,input().split())
count = 0
rr = n // r
for i in range(rr+1):
  for j in range((n-i*r)//g+1):
    tmp = n - (i*r + j*g)
    if tmp >= 0 and tmp %  b == 0:
        count += 1
print(count)


Measured memory_bytes: 2940
#include <utility>
#include <stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#define REP(i, n) for (int i = 1; i < (n); i++)
#define YES(b) std::cout<< (b ? "Yes" : "No")
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string n;
	int m;
	cin >> m;
	n = "AB";
	n += 'C' + m / 1000;
	cout << n;
}

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

int main() {
    int a,b,c;cin>>a>>b>>c;
    if(c>a+b)cout<<a+b+1+b;
    else cout<<c+b;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include "unistd.h"
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream&o,const pair<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
template<typename T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
//V<ll>fac,rfac;void setFac(int n,int mod){fac=rfac=V<ll>(++n);fac[0]=1;FOR(i,1,n)fac[i]=fac[i-1]*i%mod;rfac[n-1]=modInv(fac[n-1],mod);FORR(i,n-1,1)rfac[i-1]=rfac[i]*i%mod;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

void RE(){cout<<1/0;}
void TLE(){sleep(100);}
void WA(){cout<<char(0);exit(0);}

const int N = 1e5;
int n, a[N];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(i, 0, n){
    int b;
    cin >> b;
    a[b-1] = i+1;
  }
  FOR(i, 0, n) cout << a[i] << (i==n-1 ? '\n' : ' ');
}

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


int main()
{
    int n;cin >> n;
    vector<int> a(n + 1, 0);
    for(int i = 1; i<= n; i++)cin>>a[i];
    int b = 1;
    int ans = 0;
    for(int i = 1; i<= n; i++){
        b = a[b];
        ans++;
        if(b == 2) break;
    }
    cout << (ans == n ? -1:ans)<<endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll h;cin >>h;
    ll cnt=0;
    while(h>0){
        cnt++;
        h/=2;
    }
    ll ans=0;
    for (int i = 0; i < cnt; ++i) {
        ans=ans*2+1;
//        cout <<ans <<endl;
    }
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
   int a,b,c,d=0;

   scanf("%d%d",&a,&b);

   while(d<2){
      if(a>b){
         c = c+a;
         a--;
      }
      else {
         c = c+b;
         b--;
      }
   d++;
   }

   printf("%d\n",c);

   return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	ll n;
	cin >> n;
	int ans = 0;
	for(ll i = 1; i * i <= n-1; i++){
		if((n-1) % i != 0) continue;
		if(i != 1)ans++;
		ll j = (n-1)/i;
		if(i != j) ans++;
	}
	// cerr << ans << endl;
	for(ll i = 1; i * i <= n; i++){
		if(n % i != 0) continue;
		ll j = n/i;
		ll t = n;
		while(t % j == 0 && t > 1){
			t /= j;
		}
		if(t % j == 1) ans++;
		if(i == 1 || i == j) continue;
		t = n;
		while(t % i == 0 && t > 1){
			t /= i;
		}
		if(t % i == 1) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
// atcoder/abc149/E/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }
template<typename P, typename Q> inline pair<Q, P> reverse(pair<P, Q> p) { return make_pair(p.second, p.first); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr lli mod = 1e9 + 7;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  lli m;
  while (cin >> n >> m) {
    vector<lli> a(n);
    cin >> a;
    sort(a.begin(), a.end());

    const int N = 1e5 + 5;
    lli acc[N];
    fill(acc, acc + N, 0);
    for (int i = 0; i < a.size(); ++i) {
      acc[i + 1] = acc[i] + a[i];
    }

    auto fn = [&] (lli x) {
      lli sum = 0;
      lli z = 0;
      each (i, a) {
        auto itr = lower_bound(a.begin(), a.end(), x - i);
        lli j = itr - a.begin();
        sum += n - j;
        z += (acc[n] - acc[j]) + ((n - j) * i);
      }
      return make_pair(sum, z);
    };

    lli small = 0;
    lli large = 2 * 1e5 + 5;
    while (small + 1 < large) {
      lli mid = (small + large) / 2;
      if (fn(mid).first < m) large = mid;
      else small = mid;
    }

    auto p = fn(small);
    lli q = p.second - (p.first - m) * small;
    cout << q << endl;

    // vector<lli> b;
    // for (int i = 0; i < a.size(); ++i) {
    //   for (int j = 0; j < a.size(); ++j) {
    //     b.push_back(a[i] + a[j]);
    //   }
    // }
    // sort(b.begin(), b.end());
    // reverse(b.begin(), b.end());
    // lli y = 0;
    // for (int i = 0; i < m; ++i) {
    //   y += b[i];
    // }
    // assert(y == q);
  }

  return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
using Pl = pair<ll, int>;

void Main() {
    int n, m;
	cin >> n >> m;
	vi cnt(n+1, 0);
	
    rep(i, m){
        int a, b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b]++;
    }
    
    bool ok = true;
    rep(i, n+1){
        if(cnt[i]&1) {
            ok = false; 
            break;
        }
    }
    
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;
    return;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


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

const ll INF = (ll)1e18 + 1;

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

  sort(a.begin(), a.end());
  ll l = -INF;
  ll r = INF;
  while (r - l > 1) {
    ll mid = (l+r)/2;  

    auto ok = [&](ll x) {
      ll cnt = 0;

      rep(i, n) {
        if (a[i] < 0) {
          ll l = -1;
          ll r = n;
          while (r-l>1) {
            ll ct = (r+l)/2; 
            if (a[i] * a[ct] < x) r = ct;
            else l = ct; 
          }
          cnt += n-r;
        } else {
         ll l = -1;
         ll r = n;
         while (r-l>1) { 
           ll ct = (l+r)/2;
           if (a[i] * a[ct] < x) l = ct;
           else r = ct;
         }
         cnt += r;
        }
        if (a[i]*a[i] < x) cnt--;
      }
      cnt /= 2;
      return cnt < k;
    };

    if (ok(mid)) l = mid;
    else r = mid;
  }
  cout << l << endl;
  return 0;
}

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

#define rep(i,n) for(ll i=0,i##_cond=(n);i<i##_cond;++i)
typedef long long ll;
typedef vector<ll> vi;

int main(){
#define int ll
  int n,m; cin >> n >> m;
  vi a(n+1);
  rep(i,n){
    cin >> a[i+1];
    a[i+1] += a[i];
    a[i+1] %= m;
  }
  map<int,int> c;
  int ans = 0;
  rep(i,n+1){
    ans += c[a[i]];
    c[a[i]]++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4992
//
// Created by cerussite on 6/14/20.
//
#include <algorithm>
#include <iostream>

int main() {
  int x[5] = {};

  for (auto& xx : x) {
    std::cin >> xx;
  }

  for (std::size_t i = 0; i < 5; ++i) {
    if (x[i] == 0) {
      std::cout << (i + 1) << std::endl;
      break;
    }
  }
}


Measured memory_bytes: 3624
while True:
  dic = {"#":-3, ".":-1, "X":-2, "E":0, "N":1, "W":2, "S":3}
  def fix(c):
    return dic[c]
  w, h = map(int, input().split())
  if w == 0:
    break
  mp = [list(map(fix, list(input()))) for _ in range(h)]
  
  persons = []
  for y in range(h):
    for x in range(w):
      if mp[y][x] in (0, 1, 2, 3):
        persons.append([x, y, mp[y][x]])
  
  vx = (1, 0, -1, 0)
  vy = (0, -1, 0, 1)
  
  time = 0
  while time < 180:
    if not persons:
      print(time)
      break
    reserve = {}
    for index, state in enumerate(persons):
      x, y, d = state
      for i in range(d - 1, d + 3):
        dx, dy = vx[i % 4], vy[i % 4]
        if mp[y + dy][x + dx] in (-1, -2):
          persons[index][2] = i % 4
          if (x + dx, y + dy) in reserve:
            if reserve[(x + dx, y + dy)][1] > (i + 2) % 4:
              reserve[(x + dx, y + dy)] = (index, (i + 2) % 4, mp[y + dy][x + dx])
          else:
            reserve[(x + dx, y + dy)] = (index, (i + 2) % 4, mp[y + dy][x + dx])
          break
    
    reserve = sorted(reserve.items(), key=lambda a:-a[1][0])
    for k, v in reserve:
      nx, ny = k
      index, nd, panel = v
      px, py, _ = persons[index]
      mp[py][px] = -1
      if panel == -1:
        persons[index] = [nx, ny, (nd + 2) % 4]
        mp[ny][nx] = (nd + 2) % 4
      else:
        persons.pop(index)
    
    time += 1
  
  else:
    print("NA")


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

typedef vector<int> vi;
#define ll long long
#define loop(i,n) for(int i=0; i<n; i++)
#define loop1(i,n) for(int i=1; i<=n; i++)
#define loopi(i,s,e) for(int i=s; i < e; i++)
#define loopiRev(i,s,e) for(int i=s; i >= e; i--)
#define PI 3.14159265359
#define x first
#define y second
#define point pair<double,double>
#define len(s)   (int)s.length()
#define sz(v)    (int)v.size()
#define all(a)   a.begin(),a.end()
#define clr(x, val)	memset((x), (val), sizeof(x))

void initialize(vector<int> &F, int n){
    F = vector<int> (n+1, 0);

    for(int i=2; i*i  <= n; i++){
        if(F[i] == 0)
            for(int k=i*i; k <=n ; k+= i)
                if(F[k] == 0) F[k] = i;
    }
}

//you don't know math, unless you can do math!
int l,n;
vector<int> cuts;
ll dp[1100][1100];

ll solve(int i, int j){
    ll &ret= dp[i][j];
    if(ret != -1)
        return ret;

    int cur= lower_bound(cuts.begin(), cuts.end(), i+1) - cuts.begin();
    if(cur == cuts.size() || cuts[cur] >= j)
        return ret= 0;



    ret= 10000000;
    while(cur < n && cuts[cur] < j){
        ret = min(ret, solve(i, cuts[cur]) + solve(cuts[cur], j) + j - i);
        cur++;
    }

    return ret;
}
int main() {
    //freopen("input.txt" , "r" , stdin) ;
    //freopen("output.txt" , "w" , stdout) ;

    cin.tie(0);
    cin.sync_with_stdio(0);

    int n; cin>>n;
    vector<ll> a(n);

    loop(i,n) cin>>a[i];

    //first choice making the first element positive
    vector<ll> tmp = a;
    ll operations1=0;
    if(a[0] <= 0){
        operations1+= abs(a[0]) + 1;
        a[0]+= abs(a[0]) + 1;
    }

    loop1(i, n-1){
        ll newSum = a[i] + a[i-1];
        if(newSum < 0 && a[i-1] < 0){
            operations1+= abs(newSum) + 1;
            newSum= 1;
        }

        else if(newSum > 0 && a[i-1] > 0){
            operations1+= newSum + 1;
            newSum = -1;
        }

        if(newSum == 0){
            operations1++;
            if(a[i-1] > 0)  newSum=-1;
            else newSum = 1;
        }

        a[i]=newSum;
    }

    //making the first element negative
    ll operations2=0;
    a= tmp;

    if(a[0] >= 0){
        operations2+= a[0] + 1;
        a[0]=-1;
    }

    loop1(i, n-1){
        ll newSum = a[i] + a[i-1];
        if(newSum < 0 && a[i-1] < 0){
            operations2+= abs(newSum) + 1;
            newSum= 1;
        }

        else if(newSum > 0 && a[i-1] > 0){
            operations2+= newSum + 1;
            newSum = -1;
        }

        if(newSum == 0){
            operations2++;
            if(a[i-1] > 0)  newSum=-1;
            else newSum = 1;
        }

        a[i]=newSum;
    }

    cout<<min(operations1, operations2);

}


Measured memory_bytes: 1792
n,m,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

def make_sumlist(book_list):
    sumnum=0
    container=[0]
    for i in book_list:
        container.append(sumnum+i)
        sumnum+=i
    return container

total_a=make_sumlist(a)
total_b=make_sumlist(b)

# print(n,m,k)
# print(total_a)
# print(total_b)


#r個読めるか
def readable(r):
    #全部読んでも無理
    if r>n+m:
        return False
    if r==0:
        return True
    max_book=100000000000
    for a_n in range(max(0,r-m),min(n,r)+1):
        b_n=r-a_n
        # print(a_n,b_n)
        book_sum=total_a[a_n]+total_b[b_n]
        # print(book_sum)
        max_book=min(max_book,book_sum)
    if max_book<=k:
        return True
    return False

def nibuntansaku(start,end):
    if start==end:
        return start
    middle=(start+end)//2+1
    if readable(middle):
        start=middle
    else:
        end=middle-1
    return nibuntansaku(start,end)

print(nibuntansaku(0,k))


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

typedef long long ll;

int max(int a, int b){
  if(a > b) return a;
  else return b;
}
int min(int a, int b){
  if(a < b) return a;
  else return b;
}

int sort(const void *a ,const void *b){
  return *(int*)a - *(int*)b;
}

int main(){

  int a,b,c;
  scanf("%d%d%d",&a,&b,&c);

  int flag5 = 0, flag7 = 0;
  if(a == 5)flag5 ++;
  if(a == 7)flag7 ++;
  if(b == 5)flag5 ++;
  if(b == 7)flag7 ++;
  if(c == 5)flag5 ++;
  if(c == 7)flag7 ++;

  if(flag5 == 2 && flag7 ==1)printf("YES");
  else printf("NO");

  return 0;

}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
  
int main()
{
    int h,n;
    cin>>h>>n;
    int a=0,g=0;
    for(int i=0;i<n;i++)
    {
        cin>>g;
        a+=g;
    }
    if(a>=h)
        cout<<"Yes";
    else 
        cout<<"No";
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
string s;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    ll n=s.length();
    s=s.c_str();
    bool abc=false;
    ll a=0;
    ll ans=0;
    for(int i=0;i<n-1;i++){
        if(s[i]=='B'&&s[i+1]=='C'){
            ans+=a;
            i=i+1;
        }
        else if(s[i]=='A'){
            a++;
        }
        else{
            a=0;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 720
n, m = gets.split.map(&:to_i)

edge = Array.new(n+1) {[]} 

m.times do
    x, y, z = gets.split.map(&:to_i)
    edge[x] << y
    edge[y] << x
end

c = Array.new(n+1)
ans = 0
1.upto(n) do |i|
    next if c[i]
    ans += 1
    c[i] = 1
    que = [i]

    while now = que.shift
        edge[now].each do |y|
            next if c[y]
            c[y] = 1
            que << y
        end
    end
end

p ans

Measured memory_bytes: 12540
#include<stdio.h>
int main(){
int a,max,min,i;
scanf("%d",&a);
  int b[a];
  scanf("%d",&b[0]);
  max=b[0];
  min=b[0];
for(i=1;i<a;++i)  
  {scanf("%d",&b[i]);
   if(b[i]>max) max=b[i];
   if(b[i]<min) min=b[i];
  }
printf("%d",max-min);



return 0;
}

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

const int MAX_N = 200005;
int N, M;
std::vector<int> adj[MAX_N];
bool seen[MAX_N];

int dfs(int n) {
  int count = 0;
  for (int next_n : adj[n]) {
    if (seen[next_n]) continue;
    seen[next_n] = true;
    count += dfs(next_n) + 1;
  }
  return count;
}

int main() {
  scanf("%d %d", &N, &M);
  for (int i = 0; i < M; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int max_num = 0;
  int num_comp = 0;
  for (int i = 0; i < N; ++i) {
    if (seen[i]) continue;
    num_comp++;
    seen[i] = true;
    max_num = std::max(max_num, dfs(i) + 1);
  }
  printf("%d\n", max_num);
}


Measured memory_bytes: 24332
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <set>
#include <functional>
#include <cmath>


//マクロ
/*動かない・・・
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _roverload3(_1,_2,_3,name,...) name
#define _rrep(i,n) repi(i,0,n)
#define rrepi(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(...) _roverload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
//*/
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)
//*/
#define All(a) (a).begin(),(a).end()
#define dump(x)  cerr << #x << " = " << (x) << endl;

//定数
#define INF 1e9
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
//*/
using namespace std;
using Graph = vector<vector<int>>;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数
int h,a;

//使用する関数
template<class T>bool chmax(T &a, const T &b) {
	if (a < b) { a = b; return 1; }
	return 0;
}
template<class T>bool chmin(T &a, const T &b) {
	if (a > b) { a = b; return 1; }
	return 0;
}

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

	cin >> h >> a;
	cout << (h + a - 1) / a << endl;
}

Measured memory_bytes: 256
def solve():
    N, HP  = map(int, input().split())
    score = 0

    f = []
    n = []
    for i in range(N):
        a, b = map(int, input().split())
        f.append(a)
        n.append(b)

    #最後まで使う刀保存
    lastf = max(f)
    lastid = f.index(lastf)
    lastn = n[lastid]
    n.sort(reverse = True)


    for i in range(len(n)):
        mn = n[0]
        id = 0
        if lastf < mn:
            HP -= mn
            n.pop(id)
            score += 1
            if HP <= 0:
                return score
        else:
            break

    score += -(-HP // lastf)
    return score


print(solve())


Measured memory_bytes: 11364
W, H, x, y, r = map(int,input().split())
x_min = x - r
x_max = x + r
y_min = y - r
y_max = y + r
if x_min >= 0 and x_max <= W and y_min >= 0 and y_max <= H:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 5596
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define SINV(t) greater<t>()
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP2(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

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

typedef long long ll;
#define vv(t) vector<t>

template<typename T>
void SV(vector<T> v){
    REP(i,v.size()){
        #ifdef LOCAL
            cout << i << " : " << v[i] << endl;
        #endif
    }
}

int bitCount(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16);
}


int main(){
    int N;
    cin >> N;
    ll sum = 0;
    REP2(a, N){
        REP2(b, N){
            REP2(c, N){
                sum += __gcd(a, __gcd(b, c));
            }
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define ll long long
#define rep(cnt,a,n) for(ll cnt=a;cnt<n+a;cnt++) //aから始めてn回ループ
#define vector2(type,name,a,b) vector<vector<type>> name(a, vector<type>(b))
#define PI 3.141592653589793
int main()
{
    double a;
    double b;
    double x;

    cin >> a;
    cin >> b;
    cin >> x;
    double ans;
    if (2*x <= a * b * a) {
        ans = atan2(b, 2 * x / a / b) * 180.0 / PI;
    }
    else{
        ans = atan2(2*(a*a*b-x)/a/a, a) * 180.0 / PI;
    }

    printf("%0.10f", ans);


    return 0;
}

Measured memory_bytes: 640
while 1:
    m,n_min,n_max = map(int,input().split())
    if m == 0 and n_min == 0 and n_max == 0:
        break
    p  = [int(input()) for i in range(m)]
    p.sort()
    p.reverse()
    lists = list(range(n_min,n_max+1))
    ans = []
    Max = -9999999999
    ans = -9999999999
    for i in lists:
        if Max <= abs(p[i-1]-p[i]):
            Max = abs(p[i-1] - p[i])
            ans = max(ans,i)
    print(ans)


Measured memory_bytes: 5620
#include <stdio.h>

int main(void) {
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	if (x-r >= 0 && x+r <= w &&
	    y-r >= 0 && y+r <= h
	   ) {
	    printf("Yes\n");	
	} else {
	    printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 584
<?php
$a = explode(" ", trim(fgets(STDIN)));
$p = INF;

for ($i = 0; $i < 3; $i++) {
  for ($j = 1; $i + $j < 3; $j++) {
    if ($p > $c = $a[$i] + $a[$i + $j]) {
        $p = $c;
    }
  }
}

echo $p . "\n";

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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX

const double EPS = 1e-14;
const double PI  = acos(-1.0);


typedef pair<LL, LL> p;

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

  LL w, v;
  vector<p> x(n + 1);
  x[0] = make_pair(0, 0);
  REP (i, n) {
    cin >> w >> v;
    x[i + 1] = make_pair(w, v);
  }

  LL dp[n + 1][k + 1];
  REP (i, n + 1) REP (j, k + 1) dp[i][j] = 0;

  FOR (i, 1, n + 1) {
    FOR (j, 1, k + 1) {
      if (0 <= j - x[i].first) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - x[i].first] + x[i].second);
      else dp[i][j] = dp[i - 1][j];
    }
  }

  cout << dp[n][k] << endl;
}


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


int main(){
    int A,B,K;
    cin>>A>>B>>K;

    if(B-A+1<=K){
        for(int i = A; i <= B; i++)
            cout << i << endl;
        return 0;
    }
    int n = K;
    while(n--){
        cout << A << endl;
        A++;
    }
    int m = B - K + 1;
    for(int i = m; i <= B; i++){
        if(i < A) continue;
        cout << i << endl;
    }
}

Measured memory_bytes: 256
n = int(input())

stick = list(map(int, input().split()))

total = sum(stick)
mid = total // 2

cum = 0
midi = 0
for i, block in enumerate(stick):
    cum += block
    if cum >= mid:
        midi = i
        break

l1 = stick[:midi]
r1 = stick[midi:]
diff1 = abs(sum(l1) - sum(r1))
 
l2 = stick[:midi+1]
r2 = stick[midi+1:]
diff2 = abs(sum(l2) - sum(r2))
 
print(min(diff1, diff2))

Measured memory_bytes: 26220
#include<stdio.h>
#define INFTY 1000000000
#define N 500000

void merge(int *, int ,int ,int);
void mergeSort(int *, int, int);

int n,count=0;

int main(){
  int A[N],i;
  scanf("%d",&n);
  for(i=0 ; i<n ; i++){
    scanf("%d",&A[i]);
  }
  mergeSort(A,0,n);
  
  for(i=0 ; i<n ; i++){
    if(i<n-1)
      printf("%d ",A[i]);
    else
      printf("%d\n",A[i]);
  }
  printf("%d\n",count);
  return 0;
}

void merge(int *A,int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  int L[n1];
  int R[n2];
  int i,j,k;
  for (i = 0 ; i< n1 ; i++){
    L[i] = A[left + i];
  }
  for (i = 0 ; i<n2 ; i++){
    R[i] = A[mid + i];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = 0;
  j = 0;
  for(k=left; k < right ; k++){
    if (L[i] <= R[j]){
      A[k] = L[i];
      i=i+1;
    }
    else{
      A[k] = R[j];
      j=j+1;
    }
    count++;
  }
}

void mergeSort(int *A, int left, int right){
  int mid;
  if (left+1 < right){
    mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}



Measured memory_bytes: 5632
/////jdjs
#include<stdio.h>
int main()
{
    long long a,b,c,d;
    scanf("%lld %lld %lld",&a,&b,&c);
    if(c<=a)
    {
        printf("%lld %lld",a-c,b);
    }
    else if(c>a)
        {
        d=c-a;
        if(d<=b) printf("0 %lld",b-d);
        else printf("0 0");
    }
        
        
        
        
    
    
    return 0;
}

Measured memory_bytes: 1700
package main

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

var sc *bufio.Scanner

func nextInt() (r int) {
	sc.Scan()
	r, _ = strconv.Atoi(sc.Text())
	return r
}

func main() {
	var n, m int
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n = nextInt()
	d := make(map[int]int, n)
	for i := 0; i < n; i++ {
		d[nextInt()]++
	}
	m = nextInt()
	t := make(map[int]int, m)
	for i := 0; i < m; i++ {
		t[nextInt()]++
	}
	ans := "YES"
	for k, v := range t {
		// 難易度kの問題がv個必要
		// d[k]がv以上ならばOK、そうでなければだめ
		if d[k] < v {
			ans = "NO"
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 15232
#include<stdio.h>
  
void qsort(int a[],int left,int right){
      
    int p=(left+right)/2;
    int pivot=a[p];
    int i,temp;
    if(left<right){
        p=left;
        pivot=a[p];
        for(i=left+1;i<=right;i++){
            if(a[i]<pivot){
                p++;
                temp=a[i];a[i]=a[p];a[p]=temp;//swap
            }
        }
        temp=a[left];a[left]=a[p];a[p]=temp;//swap
        qsort(a,left,p-1);
        qsort(a,p+1,right);
    }
  
}
  
int search(int key,int a[],int n){
    int i;
    for(i=0;i<n;i++){
        if(key==a[i])return i;
    }
      
    return i;
}
  
int isVisited(int v[],int n){
    int i;
    for(i=0;i<n;i++){
        if(v[i]!=1)return -1;
    }
    return 1;
}
      
int min(int a,int b){
    if(a<b)return a;
    return b;
}
  
  
int main(void){
    int n,i,j,minW,cost=0,w;
    int a[1000],b[1000],v[1000];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
        v[i]=0;
    }
    qsort(b,0,n-1);
      
    for(i=0;i<n;i++){    
        int x=i;
        int sum=0;
        int count=0;
        minW=10000;
        while(v[x]==0){
            v[x]=1;
            sum+=a[x];
            count++;
            if(minW>a[x])minW=a[x];
            x=search(a[x],b,n);
        }
        if(count<2)continue;
          
        cost+=min(b[0]*(count+1)+sum+minW,sum+(count-2)*minW);
        if(isVisited(v,n)==1)break;
    }
    printf("%d\n",cost);
    return 0;
}


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

int main(){
	int n;
	while(cin>>n,n){
		string s[1000];
		rep(i,n){
			cin>>s[i];
			rep(j,s[i].size()){
				if(s[i][j]=='.'){
					s[i][j]=' ';
				}else{
					if(j){
						s[i][j-1]='+';
						int t=i;
						while(s[--t][j-1]==' ')s[t][j-1]='|';
					}
					break;
				}
			}
		}
		rep(i,n)cout<<s[i]<<endl;
	}
}

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

int main(){
    int h, w;
    cin >> h >> w;
    int C[10][10];
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            cin >> C[i][j];
        }
    }
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            for(int k = 0; k < 10; k++){
                C[j][k] = min(C[j][k], C[j][i] + C[i][k]);
            }
        }
    }
    int cost = 0;
    for(int i = 0; i < h * w; i++){
        int a;
        cin >> a;
        if(a == -1 or a == 1);
        else{
            cost += C[a][1];
        }
    }
    cout << cost << endl;

    return 0;
}

Measured memory_bytes: 256
K,N = list(map(int, input().split(' ')))
A_list = list(map(int, input().split(' ')))
max_distance = 0
for i in range(N):
    if i == 0:
        temp_distance = K - A_list[N - 1] + A_list[0]
    else:
        temp_distance = A_list[i] - A_list[i - 1]
    max_distance = max(max_distance, temp_distance)
print(K - max_distance)


Measured memory_bytes: 32312
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long int

int main(void)
{
    int a, b, d, g, count =0;

    cin >> a >> b;
     vector<ll >A(a, 0);
     vector<ll >B(a);

     for (int i = 0; i < b; i++)
     {
         cin >> d;
         for (int j = 0; j < d; j++)
         {
             cin >> g;
             A[g-1]++;
            // cout << A[g-1] << endl;
         }

     }

     for (int i = 0; i < a; i++)
     {
         if (A[i] == 0)
         {
             count++;
         }
     }
     cout <<count<< endl;
    
   

    
}

    

Measured memory_bytes: 3632
N,K=map(int,input().split())
S=input()
slist = list(S)
if slist[K-1] == "A":
  slist[K-1] = "a"
elif slist[K-1] == "B":
  slist[K-1] = "b"
elif slist[K-1] == "C":
  slist[K-1] = "c"
print("".join(slist))



Measured memory_bytes: 3060
N = int(input())
P = list(map(int,input().split()))
P = sorted([(P[i],i) for i in range(N)],key=lambda x:x[0])
cnt = 1
imin = P[0][1]
for i in range(1,N):
    ind = P[i][1]
    if ind<imin:
        cnt += 1
        imin = ind
print(cnt)

Measured memory_bytes: 108160
#include <stdio.h>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
	string input;
	cin >> input;
	bool In_9;
	rep (i, 2){
		if (input[i] == '9') {
			In_9 == true;
			printf("Yes\n");
			exit(0);
		}
		else{
			continue;
		}
	} 
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void) 
{
	int i, len;
	char s[4096];  /* 1200バイト以上 */
	for(i = 0; i < 4096; i++) {
    		int ans = 0;
    		scanf("%s", s); // セキュリティ上よろしくないけど仕方がない
    		if (s[0] == '0')
			break;
    		len = strlen(s);   // 文字列の長さをえる
    		for(i = 0; i < len; i++) {
    			ans += s[i] - '0';
    		}
    		printf("%d\n", ans);
	}

	return 0;
}



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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int a,b,c,n;
void solve(){
	cin >> a >> b >> c >> n;
	
	int cnt = 0;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j+i <= n; j++){
			int ab = a*i+b*j;
			if(n < ab) break;
			if((n-ab)%c == 0) cnt++;
		}
	}
	cout << cnt << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


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

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

using namespace std;
using lint=long long;

template<class G>
class Fenwick_tree{
	vector<G> a;
public:
	Fenwick_tree(int n):a(n){}
	void add(int i,G val){
		for(i++;i<=a.size();i+=i&-i) a[i-1]+=val;
	}
	G sum(int l,int r)const{
		if(l==0){
			G res{};
			for(;r>0;r-=r&-r) res+=a[r-1];
			return res;
		}
		return sum(0,r)-sum(0,l);
	}
	int lower_bound(G val)const{
		if(val<=G{}) return 0;
		int x=0,k;
		for(k=1;k<=a.size();k<<=1);
		for(k>>=1;k>0;k>>=1) if(x+k<=a.size() && a[x+k-1]<val) val-=a[x+k-1], x+=k;
		return x;
	}
	int upper_bound(G val)const{
		if(val<G{}) return 0;
		int x=0,k;
		for(k=1;k<=a.size();k<<=1);
		for(k>>=1;k>0;k>>=1) if(x+k<=a.size() && a[x+k-1]<=val) val-=a[x+k-1], x+=k;
		return x;
	}
};

lint calc(const string& s,const string& t){
	int n=s.length();

	deque<int> D[26];
	rep(i,n) D[s[i]-'a'].emplace_back(i);

	Fenwick_tree<int> F(n);
	rep(i,n) F.add(i,1);

	lint res=0;
	rep(i,n){
		int p=D[t[i]-'a'][0]; // move s[p] -> t[i]
		D[t[i]-'a'].pop_front();
		res+=F.sum(0,p);
		F.add(p,-1);
	}
	return res;
}

int main(){
	string s; cin>>s;
	int n=s.length();

	vector<vector<int>> cnt(26,vector<int>(n+1));
	rep(c,26) rep(i,n) cnt[c][i+1]+=cnt[c][i]+(s[i]==c+'a'?1:0);

	int odd=-1;
	rep(c,26) if(cnt[c][n]%2==1) {
		if(odd==-1) odd=c;
		else return puts("-1"),0;
	}
	if(n%2==0 && odd!=-1) return puts("-1"),0;

	vector<int> L,M,R;
	rep(i,n){
		int c=s[i]-'a';
		int k=cnt[c][i+1];
		if(cnt[c][n]%2==1 && k==(cnt[c][n]+1)/2){
			M.emplace_back(i);
		}
		else if(k<=cnt[c][n]/2){
			L.emplace_back(i);
		}
		else{
			R.emplace_back(i);
		}
	}

	string t;
	for(int i:L) t+=s[i];
	for(int i:M) t+=s[i];
	for(int i:R) t+=s[i];

	string r=t.substr((n+1)/2);
	reverse(r.begin(),r.end());

	cout<<calc(s,t)+calc(t.substr(0,n/2),r)<<'\n';

	return 0;
}


Measured memory_bytes: 23668
#include <stdio.h>

/*
	ax + by = c
	dx + ey = f

	ax = c - by
	x = (c - by) / a

	dx = f - ey
	x = (f - ey) / d

	(c - by) / a = (f - ey) / d
	d(c - by) = a(f - ey)
	dc - bdy = af - aey
	aey - bdy = af - dc
	y(ae - bd) = af - dc
	y = (af - dc) / (ae - bd)
*/

int main() {
	double a, b, c, d, e, f, x, y;
	while (scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF) {
		y = (a * f - d * c) / (a * e - b * d);
//		x = (f - e * y) / d + 0.0001;
		x = (c - b * y) / a + 0.0001;

//		if (x > (double)-0.001 && x <= (double)0) x = 0;
//		if (y > (double)-0.001 && y <= (double)0) y = 0;

		printf("%.3lf %.3lf\n", x, y);
	}
	return 0;
}

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

struct foo{
	int down,down_,left,left_;
};

int main(){
	int w,h;
	while( cin >> w >> h , w||h ){
		struct foo m[101][101] = {0};
		m[0][1].left_ = 1;
		m[1][0].down_ = 1;

		for(int y=0 ; y < h ; y++ ){
			for(int x=0 ; x < w ; x++ ){
				if( x == 0 && y == 0 ) continue;
				if( x == 1 && y == 0 ) continue;
				if( x == 0 && y == 1 ) continue;
				m[y][x].down  = (y>0)? m[y-1][x].left_ : 0 ;
				m[y][x].left  = (x>0)? m[y][x-1].down_ : 0 ;
				m[y][x].down_ = (y>0)? (m[y-1][x].down + m[y-1][x].down_)%100000 : 0 ;
				m[y][x].left_ = (x>0)? (m[y][x-1].left + m[y][x-1].left_)%100000 : 0 ;
			}
		}
		int ans = (m[h-1][w-1].left + m[h-1][w-1].left_ + m[h-1][w-1].down + m[h-1][w-1].down_)%100000;
		cout << ans << endl;
	}
}

Measured memory_bytes: 0
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ans = 0
for i in reversed(range(N)):
    ans += min(A[i + 1], B[i])
    A[i + 1], B[i] = max(0, A[i + 1] - B[i]), max(0, B[i] - A[i + 1])

    ans += min(A[i], B[i])
    A[i], B[i] = max(0, A[i] - B[i]), max(0, B[i] - A[i])

print(ans)


Measured memory_bytes: 82020
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <map>

using namespace std;
int main()
{
	int x;
	cin>>x;
	int ans=0,i;
	for(i=1;;i++)
	{
		if(ans+i<x)
		ans+=i;
		else
		break;
	}
	cout<<i<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


void solve( int d ) {
    bool T[d][d];
    int r = d - 1, c = 0;
    const int dr[4] = { -1, 0, 1, 0 };
    const int dc[4] = { 0, 1, 0, -1 };
    int k = 0;
    fill( (bool*)T, (bool*)T+d*d, false );

    for ( int lpc = 0; lpc < d * d; ++ lpc ) {
        T[r][c] = true;
        bool flag = false;
        for ( int i = 0; i < 2; ++ i ) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if ( nr < 0 || nr >= d || nc < 0 || nc >= d ) {
                k = ( k + 1 ) % 4;
                continue;
            }
            int nnr = r + dr[k] * 2;
            int nnc = c + dc[k] * 2;
            if ( nnr < 0 || nnr >= d || nnc < 0 || nnc >= d ) {
                r = nr;
                c = nc;
                flag = true;
                break;
            }
            if ( T[nnr][nnc] ) {
                k = ( k + 1 ) % 4;
                continue;
            }
            r = nr;
            c = nc;
            flag = true;
            break;
        }
        int cnt = 0;
        for ( int i = 0; i < 4; ++ i ) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if ( nr < 0 || nr >= d || nc < 0 || nc >= d ) continue;
            if ( T[nr][nc] ) cnt ++;
        }
        if ( cnt > 1 ) break;
    }

    for ( int i = 0; i < d; ++ i ) {
        for ( int j = 0; j < d; ++ j ) {
            cout << ( T[i][j] ? '#' : ' ' );
        }
        cout << endl;
    }
}

int main() {
    int n;
    cin >> n;
    for ( int i = 0; i < n; ++ i ) {
        int d;
        cin >> d;
        solve( d );
        if ( i + 1 < n ) cout << endl;
    }
    return 0;
}

Measured memory_bytes: 0
N,a,b=map(int,input().split())
mod=10**9+7

def cmb(N,K):
    r=1

    for i in range(K):
        r=r*(N-i)*pow(i+1,mod-2,mod)%mod

    return r
ans=((pow(2,N,mod)-1)%mod-cmb(N,a)-cmb(N,b))%mod
#逆元の割り算のmodは、分子*逆元（分母)%modと等価　フェルマーの小定理から、 逆元はpow(b,mod-2,mod)となる
print(ans)

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

int n,page[50],front,back,a;

void check(int);

int main(){
  
  while(1){
    
    cin >>n;
    if(n == 0)break;
    
    for(int i=0 ; i < 50 ; i++)page[i]=-999999;
    
    for(int i=0 ; i < n ; i++)cin >>page[i];
    
    for(int i=1 ; i <= n ; i++){
      if(page[i-1] == page[i]-1){
	front=page[i-1];
	check(i-1);
	cout<<front<<"-"<<back;
	if(a != n-1)cout <<" ";
      }else{
	if( page[i-1] != -999999){
	  cout <<page[i-1];
	  if(i-1 != n-1)cout <<" ";
	}
      }
    }
    cout <<endl;
    
  }
  
  return 0;
}
void check(int i){
  
  if(i < n-1){
    
    page[i]=-999999;
    back=page[i+1];
    
    if(page[i+1] == page[i+2]-1){
      check(i+1);
    }else{
      page[i+1]=-999999;
      a=i+1;
    }
    
  }
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for(int i =0; i < n ;i++)
using namespace std;

//int a[100002];

int main(){
    int N, K,  ans=1;
    cin >> N >> K;

    //rep(i, N){
    //    cin >> a[i];
        //(a[i]==1) p=a[i];
    //}
    N -= K;

    while(N > 0){
        N -= K-1;
        ans++;

    }
        
        

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=6005,INF=1<<30;
ll cnt[MAX][MAX];
ll inv[MAX],fac[MAX],finv[MAX];

void make(){
    
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    
    for(int i=2;i<MAX;i++){
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        fac[i]=fac[i-1]*(ll)i%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
    
}

ll comb(ll a,ll b){
    if(a<b) return 0;
    return fac[a]*(finv[b]*finv[a-b]%mod)%mod;
}


int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    make();
    int N,X;cin>>N>>X;
    ll sum=0;
    
    for(int i=0;i<X;i++){
        for(int j=0;j<=N;j++){
            if(i<j) continue;
            
            int rem=i-j;
            cnt[i][j]=comb(j,rem);
            
            sum+=cnt[i][j]*comb(N,j);
            sum%=mod;
        }
    }
    
    for(int i=X+1;i<=2*N;i+=2){
        if(i==2){
            sum+=N;
            sum%=mod;
            continue;
        }
        if(i==3) continue;
        int rd=(i-(X-1))*2;
        if(i-rd<0){
            if(X%2==1){
                int c=(i+1)/2;
                sum+=comb(N,c);
                sum%=mod;
            }
        }else{
            for(int j=0;j+rd/2<=N;j++){
                sum+=cnt[i-rd][j]*comb(N,j+rd/2);
                sum%=mod;
            }
        }
    }
    
    cout<<sum<<endl;
}



Measured memory_bytes: 279680