akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int n, m;
    cin >> n >> m;
    vec a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];

    vec job[100050];
    rep(i, n) {
        job[a[i]].push_back(b[i]);
    }

    lint res = 0;

    priority_queue<int> que;

    for (int d = 1; d <= m; d++) {
        for (auto&& j : job[d]) que.push(j);
        if (!que.empty()) {
            res += que.top();
            que.pop();
        }
    }

    cout << res << endl;
    return 0;
}

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

/* Segment Tree -----------*/
template <typename M>
class SegmentTree {
    using F = std::function< M(M, M) >;
private:
    int n;
    F func;
    M M_init;
    std::vector<M> t;
public:
    // constructor
    SegmentTree(int &n, F func, const M &M_init): n(n), func(func), M_init(M_init) { t.assign(2*n, M_init); }
    SegmentTree(std::vector<M> &vec, F func, const M &M_init): n(vec.size()), func(func), M_init(M_init) {
        t.assign(2*vec.size(), M_init);
        for(int i = 0; i < vec.size(); ++i) t[i+vec.size()] = vec[i];
    }

    void build() {  // build segment tree
        for(int i = n-1; i > 1; --i) t[i] = func(t[i<<1], t[i<<1|1]);
    }
    void modify(int p, M val) {  // update value at position p
        for(t[p += n] = val; p > 1; p >>= 1) t[p>>1] = func(t[p], t[p^1]);
    }
    M query(int l, int r) {  // reply to query [l, r)
        M resl = M_init, resr = M_init;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) resl = func(resl, t[l++]);
            if(r & 1) resr = func(t[--r], resr);
        }
        return func(resl, resr);
    }
    M &operator[](const int &k) &{return t[k+n];}
    const M &operator[](const int &k) const& {return t[k+n];}
};



int GCD(int a, int b) { return (b ? GCD(b, a%b) : a); }

signed main(){
    using namespace std;

    // input and build
    int n; cin >> n;
    SegmentTree<int> a(n, [](int p, int q){ return (q ? GCD(q, p%q) : p);}, 0LL);
    for(int i = 0; i < n; ++i) cin >> a[i];
    a.build();

    // solve
    int ans = -1;
    for (int i = 0; i < n; ++i) {
        if(i == 0) ans = max(ans, a.query(1, n));
        else if(i == n-1) ans = max(ans, a.query(0, n-1));
        else ans = max(ans, GCD(a.query(0,i), a.query(i+1, n)));
    }

    // output
    cout << ans << '\n';
}

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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    i64 n = input();

    string ans;
    while (n > 0) {
        ans += ((n - 1) % 26) + 'a';
        n = (n - 1) / 26;
    }

    whole(reverse, ans);
    cout << ans << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 3652
#include<iostream>

using namespace std;
int main(){
    int N,M,C;
    cin>>N>>M>>C;
    int B[M];
    for(int a=0;a<M;a++){
        cin>>B[a];
    }
    int A[M];
    int l=0;
    for(int b=0;b<N;b++){
        for(int d=0;d<M;d++){
            cin>>A[d];
        }
        int sum=0;
        for(int e=0;e<M;e++){
            int s=A[e]*B[e];
             sum=s+sum;

        }
        if((sum+C)>0){
            l++;
        }
    }
    int ans=l;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

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

using namespace std;

int main() {
  int n;
  cin>>n;
  REP(i,n){
    string cmd;
    cin>>cmd;
    string str;
    cin>>str;
    reverse(begin(cmd),end(cmd));
    for(char c:cmd){
      switch(c){
        case 'C': {
          string body=str.substr(1);
          string head=str.substr(0,1);
          str = body + head;
          break;
        }
        case 'J': {
          string body=str.substr(0,str.size()-1);
          string head=str.substr(str.size()-1);
          str = head + body;
          break;
        }
        case 'E': {
          int mid=str.size()/2;
          string fwd=str.substr(0,mid);
          string bwd=str.substr(str.size()-mid);
          if((str.size()%2)==1){
            str=bwd+str[mid]+fwd;
          }else{
            str=bwd+fwd;
          }
          break;
        }
        case 'A': {
          reverse(begin(str),end(str));
          break;
        }
        case 'M': {
          for(char& d:str){
            if('0' <= d && d < '9')
              ++d;
            else if(d == '9')
              d = '0';
          }
          break;
        }
        case 'P': {
          for(char& c:str){
            if('0' < c && c <= '9')
              --c;
            else if(c == '0')
              c = '9';
          }
          break;
        }
      }
    }
    cout<<str<<endl;
  }
  return 0;
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string s;
	long long k, ans = 0, end = 0, cnt = 0, d = 0, f = 0;

  	cin >> s >> k;
  	long long l = s.size();
	if(s[0] == s[l-1]) end = 1;
    if(1<l){
      for(int i=l-1;1<=i;i--){
          if(s[l-1]==s[i]){
              d++;
          }else{
              break;
          }
      }
    }
    if(1<l&&end == 1){
      for(int i=0;i<l-d;i++){
          if(s[l-1]==s[i]){
              f++;
          }else{
              break;
          }
      }
    }
	int c=1;
	if(end == 0){
		while(c < l){
			if(s[c-1] == s[c]){
				cnt++;
				c+=2;
			}else{
				c++;
			}
		}
	}else{
		c = f;
		while(c < l-d){
			if(s[c-1] == s[c]){
				cnt++;
				c+=2;
			}else{
				c++;
			}
		}	
	}
	if(end == 0){
		ans = cnt*k;
	}else{
		ans = cnt*k+((d+f)/2)*(k-1);
	}
	if(1<d*end){
		ans+=(d/2);
	}
	if(1<f*end){
		ans+=(f/2);
	}
	if(d+end==l) ans = k*l/2;
		
	cout << ans <<endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import Counter
 
n = int(input())
a = [int(item) for item in input().split()]
comb = [0] * (n + 1)
cnt = Counter(a)
 
for key in cnt.keys():
    comb[key] = cnt[key] * (cnt[key] - 1) // 2
total = sum(comb)
 
for item in a:
    if comb[item] <= 1:
        diff = comb[item]
    else:
        diff = comb[item] - (comb[item] * (cnt[item] - 2)) // cnt[item]
    print(total - diff)

Measured memory_bytes: 26232
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pll = pair<long long, long long>;
const int INF = 1<<29;

const int MOD = 1000000007;
long long ruizyou(long long m,long long n){
  if(m == 0)return 0;
  if(m == 1)return 1;
  long long ans = 1;
  long long tmp = m;
  for(int i=0;i<=30;i++){
    if(n & (1<<i)){
      ans *= tmp;
      ans %= MOD;
    }
    tmp *= tmp;
    tmp %= MOD;
  }
  return ans;
}
long long kaizyou(long long x){
  if(x == 0)return 1;
  return x * kaizyou(x-1) % MOD;
}
long long comb(long long x,long long y){
  long long bunsi = kaizyou(x);
  long long bunbo = kaizyou(x-y) * kaizyou(y) % MOD;
  return bunsi * ruizyou((int)bunbo,MOD-2) % MOD;
}
struct unionfind{
  vector<int> par;
  unionfind(int n){
    par = vector<int>(n);
    for(int i=0;i<n;i++){
      par.at(i) = i;
    }
  }
  int root(int x){
    if(par.at(x) == x)return x;
    return root(par.at(x));
  }
  void unite(int x,int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry)return;
    par.at(ry) = rx;
  }
  bool same(int x,int y){
    return root(x) == root(y);
  }
};

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(m),b(m);
  for(int i=0;i<m;i++){
    cin >> a.at(i) >> b.at(i);
  }
  int ans = 0;
  for(int i=0;i<m;i++){
    unionfind tree(n);
    bool flag = false;
    for(int j=0;j<m;j++){
      if(i != j){
        tree.unite(a.at(j)-1,b.at(j)-1);
      }
    }
    for(int j=1;j<n;j++){
      if(!tree.same(0,j))flag = true;
    }
    if(flag)ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

inp = Is()
lis = [abs(inp[0]-inp[1]),abs(inp[0]-inp[2]),abs(inp[1]-inp[2])]
print(sum(lis)-max(lis))


Measured memory_bytes: 3444
a, b = map(int, input().split())
s = list(input())
if len(s) != a + b + 1:
    print("No")
elif s[a] != "-":
    print("No")
else:
    for i in range(a):
        if not s[i].isdecimal():
            print("No")
            exit()
    for i in range(a + 1, len(s)):
        if not s[i].isdecimal():
            print("No")
            exit()
    print("Yes")

Measured memory_bytes: 3064
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    mxi = -1
    mxa = 0
    for i, a in enumerate(A):
        if abs(a) >= abs(mxa):
            mxa = a
            mxi = i
    ans = []
    for i in range(N):
        if A[i] * mxa < 0:
            ans.append((mxi + 1, i + 1))
            A[i] += mxa
    if mxa > 0:
        for i in range(1, N):
            if A[i] < A[i - 1]:
                ans.append((i, i + 1))
                A[i] += A[i - 1]
    else:
        for i in range(N - 2, -1, -1):
            if A[i] > A[i + 1]:
                ans.append((i + 2, i + 1))
                A[i] += A[i + 1]
    print(len(ans))
    for a in ans:
        print(*a)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)


Measured memory_bytes: 62424
import sys

def main(inp):
    N,A,B=map(int,next(inp).split())
    mini=0
    maxi=0
    
    mini=min([A,B])
    if(N>A+B):
        maxi=0
    else:
        maxi=A+B-N
    
    ans=str(mini)+" "+str(maxi)
    
    return ans
  
print(main(sys.stdin))

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int m, d;
    string day[] = {"Sunday", "Monday", 
                    "Tuesday", "Wednesday", "Thursday",
                    "Friday", "Saturday"};

    while (cin >> m >> d) {
        if (!m && !d)
            break;

        int year = 2004, h;
        if (m == 1 || m == 2) {
            year--;
            m += 12;
        }
        h = (year + year / 4 - year / 100 + year / 400 + (13 * m + 8) / 5 + d) % 7;
        
        cout << day[h] << endl;
    }

    return 0;
}

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

int main(void) {
    int n;
    cin >> n;
    int a[300010];
    for (int i = 0; i < n * 3; i++) {
        cin >> a[i];
    }

    ll left_sum = 0;
    priority_queue<ll, vector<ll>, greater<ll> > left_pq;
    for (int i = 0; i < n; i++) {
        left_sum += a[i];
        left_pq.push(a[i]);
    }
    ll right_sum = 0;
    priority_queue<ll> right_pq;
    for (int i = 2 * n; i < n * 3; i++) {
        right_sum += a[i];
        right_pq.push(a[i]);
    }

    ll left_p_sums[n + 1];
    left_p_sums[0] = left_sum;
    for (int i = 0; i < n; i++) {
        left_pq.push(a[i + n]);
        left_sum += a[i + n];
        left_sum -= left_pq.top();
        left_pq.pop();
        left_p_sums[i + 1] = left_sum;
    }
    ll right_p_sums[n + 1];
    right_p_sums[n] = right_sum;
    for (int i = 0; i < n; i++) {
        right_pq.push(a[2 * n - 1 - i]);
        right_sum += a[2 * n - 1 - i];
        right_sum -= right_pq.top();
        right_pq.pop();
        right_p_sums[n - 1 - i] = right_sum;
    }

    ll ans = left_p_sums[0] - right_p_sums[0];
    for (int i = 1; i <= n; i++) {
        ans = max(ans, left_p_sums[i] - right_p_sums[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4724
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> p(m);
    vector<string> s(m);
    for (size_t i = 0; i < m; i++)
    {
        cin >> p[i] >> s[i];
    }
    
    int counter_ac = 0,counter_wa = 0;
    vector<int> tmpCounterWA(n + 1);
    vector<bool> flag(n);
    for (size_t i = 0; i < m; i++)
    {
        if(flag[p[i]] == false){    //ACされていなかったら
            if(s[i] == "AC"){
                counter_ac++;
                counter_wa += tmpCounterWA[p[i]];
                flag[p[i]] = true;
            }
            if(s[i] == "WA")    tmpCounterWA[p[i]]++;
        }        
    }

    cout << counter_ac << " " << counter_wa << endl;
    

    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
const int INF = 1001001001;

int main(){
    int H,W;
    cin >> H >> W;
    vector<vector<char>> A(H,vector<char>(W));
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> A[i][j];
        }
    }
    vector<vector<int>> dist(H,vector<int>(W,INF));

    queue<pair<int,int>> que;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(A[i][j] == '#'){
                que.push(make_pair(i,j));
                dist[i][j] = 0;
            }
        }
    }

    int ans = 0;
    while(!que.empty()){
        int x = que.front().second,y = que.front().first;
        que.pop();
        for(int i=0;i<4;i++){
            int d_x = x+dx[i],d_y = y+dy[i];
            if(d_x<0 || d_x>=W || d_y<0 || d_y>=H) continue;
            if(dist[d_y][d_x] != INF || A[d_y][d_x]=='#') continue;
            A[d_y][d_x] = '#';
            dist[d_y][d_x] = dist[y][x]+1;            
            que.push(make_pair(d_y,d_x));
        }
        ans = max(ans,dist[y][x]);
    }
    cout << ans << endl;

}


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

int main() {

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    while(1)
    {   
        c -= b;
        
        if (c <= 0) {
            cout << "Yes\n";
            return 0;
        }

        a -= d;

        if (a <= 0) {
            cout << "No\n";
            return 0;
        }
    }

    return 0;
}


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

struct data {
    char C[15];
	  int P;
    int index;
};

int cmp_AAA(struct data* pitem1, struct data* pitem2) {
	return strcmp(pitem1->C, pitem2->C);	//昇順
}

int cmp_BBB(struct data* pitem1, struct data* pitem2) {
	return pitem2->P - pitem1->P;	//降順
}

int cmp(const void *item1, const void *item2)
{
	int(*func[])(struct data* pa, struct data* pb)  = { &cmp_AAA , &cmp_BBB };

	struct data *pitem1 = (struct data*)item1;
	struct data *pitem2 = (struct data*)item2;

	for (int i = 0; i < sizeof(func) / sizeof(func[0]); i++) {
		int ret = func[i](pitem1, pitem2);
		if (ret != 0) {
			return ret;
		}
	}

	return 0;
}

int main(){
  int N;
  scanf("%d", &N);
  int S[N], P[N], i, j;
  struct data res[N];
  for(i=0; i<N; i++){
    scanf("%s %d", &res[i].C, &res[i].P);
    res[i].index = i+1;
  }

  qsort(res, N, sizeof(struct data), cmp);

  int max;
  for(i=0; i<N; i++){

    printf("%d\n", res[i].index);
  }

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i = (a); i < (b); i++)
#define iter(it,c) for(auto it = (c).begin(); it != (c).end(); ++it)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
const ll INF = ~(1<<31);
#define fs first
#define sc second
#define pb push_back

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T> T smod(T a, T b) {
    return (a % b + b) % b;
}

vi A;
ll n;
ll k;

ll memo[100'050];

ll dp(ll at) {
    if(at >= n-1) return 0;
    if(memo[at] != -1) return memo[at];
    ll ans = dp(at+1)+abs(A[at]-A[at+1]);
    for(int i = at+1; i <= min(at+k, n-1); i++) {
        ans = min(ans, dp(i)+abs(A[at]-A[i]));
    }
    return memo[at] = ans;
}

int main() {
    cin.sync_with_stdio(false);
    memset(memo,-1,sizeof(memo));
    cin >> n >> k;
    A = vi(n+5,INF);
    rep(i,0,n) cin >> A[i];
    cout << dp(0) << endl;
    return 0;
}



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

int main(){
  int N,M;
  cin >> N >> M ;
  int favo_n[N];
  vector<vector<int>> favo_in(N,vector<int>(M,0));
  vector<vector<int>> favo_out(N,vector<int>(M,0));

for(int i=0; i<N ;i++){
  cin >> favo_n[i];
  for(int j=0; j< favo_n[i]; j++){
    cin >> favo_in[i][j];
  }
}
  
for(int i=0; i<N ;i++){
  for(int j=0; j< favo_n[i]; j++){
  favo_out[i][favo_in[i][j]-1]=1;  
  }
}
  
  int sum=0;
bool flag= false;
for(int i=0; i<M ;i++){
for(int j=0; j<N; j++){
  flag= true;
 if(favo_out[j][i]==0){
 flag= false;
 break;    
 }
}
if(flag) sum=sum+1 ;
  
}

//  for(int i=0; i<M; i++){
//  cout << favo_in[1][i] ;
//  cout << favo_out[1][i] << endl;
//  }
  
 cout << sum << endl;
}
  

Measured memory_bytes: 256
n = int(input())
A, B, C = [list(sorted(map(int, input().split())))  for _ in range(3)]

cnt = 0

def bs_left(lis, target):
    low, high = 0, len(lis)
    while low<high:
        mid = (low+high)//2
        if lis[mid]<target:
            low = mid+1
        else:
            high = mid
    return low

def bs_right(lis, target):
    low, high = 0, len(lis)
    while low<high:
        mid = (low+high)//2
        if target<lis[mid]:
            high = mid
        else:
            low = mid+1
    return low

for b in B:
    cnt += (bs_left(A, b) * (n-bs_right(C, b)))
print(cnt)

Measured memory_bytes: 24264
#include<stdio.h>
int main()
{
    char s[3];
    scanf("%s",s);
    for(int i=0;i<3;i++)
    {
        if(s[0]==s[1]&&s[1]==s[2]){
            printf("No\n");
        break;
    }
    else
    {
        printf("Yes\n");
        break;
    }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (double i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
typedef pair<double,double> P;
const int INF=1001001001;


// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
    //a^tを求める
    //例：d[i] = mint(k/i).pow(n);
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main(){
  ll n,m;
  cin>>n>>m;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  ll l=0;
  ll r=200005;
//  cout<<c;

    while(l+1<r){
      ll c=(l+r)/2;

    ll cnt=0;
    rep(i,n){
      ll rest=c-a[i];
      ll id=lower_bound(a.begin(),a.end(),rest)-a.begin();
      cnt+=n-id;
    //  cout<<id<<endl;
    //
  //  cout<<cnt<<endl;
    }
    if (cnt<=m)r=c;
    else l=c;
  //  cout<<l<<' '<<r<<endl;
  }

  vector<ll>suma(n+1);
  suma[0]=0;
  suma[1]=a[0];
  rep(i,n-1){
    suma[i+2]=suma[i+1]+a[i+1];
  }

  ll ans=0;
  ll cnt=m;


  rep(i,n){
    ll rest=l-a[i];
    ll id=upper_bound(a.begin(),a.end(),rest)-a.begin();
  //  cout<<id<<endl;
    ans+=suma[n]-suma[id];
    cnt-=n-id;
    ans+=(n-id)*a[i];
  //  cout<<ans<<"ans"<<cnt<<"cnt"<<endl;
  }
  ans+=cnt*l;
  cout<<ans;

}


Measured memory_bytes: 1792
#include<stdio.h> 
int main()
{
	int i,cnt[100],p,n;
	char s1[100],s2[100];
	long long sum,mod=1e9+7;
	while(~scanf("%d",&n))
	{
		scanf("%s",s1);
		scanf("%s",s2);
		p=0;
		for(i=0;i<n;i++)
		{
			if(i+1<n && s1[i]==s1[i+1])
			{
				cnt[p++]=2;
				i++;
			}
			else  cnt[p++]=1;	
		}
		if(cnt[0]==1)
		  sum=3;
		else  sum=6;
		for(i=0;i<p-1;i++)
		{
			if(cnt[i]==1 && cnt[i+1]==1)
			{
				sum*=2;
				sum%=mod;
			}
			if(cnt[i]==1 && cnt[i+1]==2)
			{
				sum*=2;
				sum%=mod;
			}
			if(cnt[i]==2 && cnt[i+1]==1)
			{
				sum*=1;
			}
			if(cnt[i]==2 && cnt[i+1]==2)
			{
				sum*=3;
				sum%=mod;
			}
		}
		sum=sum%mod;
	  printf("%lld\n",sum);
	}
   return 0;
 } 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lp(n) for(int i = 0; i < n; i++)
#define lpp(i, n) for(int i = 0; i < n; i++)
int partition(int A[], int p, int r) {
  int t;
  int x = A[r];
  int i = p - 1;
  for(int j = p; j < r; j++) {
    if(A[j] <= x) {
      i++;
      t = A[i];
      A[i] =  A[j];
      A[j] = t;
    }
  }
  t = A[i+1];
  A[i+1] =  A[r];
  A[r] = t;
  return i+1;
}
using namespace std;
int main() {
  int n;
  int c;
  int *A;
  cin >> n;
  A = (int *)malloc(n *sizeof(int));
  lp(n) cin >> A[i];
  c = partition(A, 0, n-1);
  lp(c) cout << A[i] << " ";
  cout<< '[' << A[c] << "] ";
  for(int i = c+1; i < n-1; i++) cout << A[i] << " ";
  cout << A[n-1] << endl;
  return 0;
}




Measured memory_bytes: 3476
import sys
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [A, B, X] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    if A + B >= X and A <= X:
        print 'YES'
    else:
        print 'NO'

if __name__ == '__main__':
    main()


Measured memory_bytes: 2692
#include <iostream>
#include <vector>
#include <climits>
using edge_to = std::pair<long long, long long>;	// {weight, to}
using edge = std::vector<long long>;				// {weight, from, to}

// return true : detected negative cycle
bool bellman_ford(
	long long V,
	long long E,
	long long r,
	std::vector<edge>& edges,		// set of DIRECTED edges
	std::vector<long long>& dist	// should be sized V, filled with infinity
) {
	dist[r] = 0;
	for (long long i = 0; i < V - 1; i++) {
		for (auto j : edges) {
			if (dist[j[1]] == LLONG_MAX) continue;
			dist[j[2]] = std::min(dist[j[2]], dist[j[1]] + j[0]);
		}
	}
	for (auto i : edges) {
		if (dist[i[1]] == LLONG_MAX) continue;
		if (dist[i[2]] > dist[i[1]] + i[0]) return true;
	}
	return false;
}

int main() {
	long long V, E, r;
	std::cin >> V >> E >> r;
	std::vector<edge> edges(0);
	for (long long i = 0; i < E; i++) {
		long long s, t, d;
		std::cin >> s >> t >> d;
		edges.push_back({d, s, t});
	}
	std::vector<long long> dist(V, LLONG_MAX);
	if (bellman_ford(V, E, r, edges, dist)) {
		std::cout << "NEGATIVE CYCLE" << std::endl;
	} else {
		for (auto i : dist) {
			if (i == LLONG_MAX) std::cout << "INF\n";
			else std::cout << i << '\n';
		}
	}
}


Measured memory_bytes: 3248
# A
S = input()
ans = [0] * (len(S)+1)
for i in range(len(S)):
  if S[i] == "<":
    ans[i+1] = max(ans[i+1],ans[i]+1)
  
for i in range(len(S)-1,-1,-1):
  if S[i] == ">":
    ans[i] = max(ans[i],ans[i+1]+1)

print(sum(ans))


Measured memory_bytes: 29036
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mxn 100005
#define mp make_pair
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long int ll;
int main(){
	int n; cin>>n;
	int arr[n];
	for(int i=0; i<n; i++){
		cin>>arr[i];
	}
	int dp[n+1];
	dp[0]  = 0;
	dp[1]  = abs(arr[1] - arr[0]);
	for(int i=2; i<n; i++){
		dp[i] = min(dp[i-1] + abs(arr[i] - arr[i-1]), dp[i-2] + abs(arr[i] - arr[i-2]));
	}
	cout<<dp[n-1];
}

Measured memory_bytes: 4388
n =int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
H=[]
for i in range(n):
  H.append(abs(a - (t - 0.006*h[i])))
for j in range(n):
  if H[j] == min(H):
    print(j+1)

Measured memory_bytes: 3060
c = [0]*26

while True:
    try:
        a = input()
        a = list(a.lower())
    except:
        break
    
    for i in range(len(a)):
        tmp = ord(a[i])
        if tmp>=97 and tmp <= 123:
            c[tmp-97] += 1

for i in range(ord("a"),ord("z")+1):
    print(chr(i),":",c[i-97])
    



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

long long N, W, w[105], v[105], dp[105][100005];

int main() {
    scanf("%ld%ld", &N, &W);

    for(int i = 1; i <= N; i++) {
        scanf("%ld%ld", &w[i], &v[i]);
    }

    for (int i = 1; i <= N+1; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (w[i] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    printf("%ld\n", dp[N][W]);
}

Measured memory_bytes: 79360
N, M = map(int, input().split())
s = [0] * M
c = [0] * M
for i in range(M):
    s[i], c[i] = map(int, input().split())

def solve():
    for ans in range(1000):
        ans = str(ans)
        if len(ans) != N:
            continue
        ok = True
        for i in range(M):
            if ans[s[i]-1] != str(c[i]):
                ok = False
                break
        if ok:
            print(ans)
            return
    print(-1)
    return

solve()

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define pi 3.14159
using namespace std;

struct ca
{
  int idx,st,et,aidx;
};

int prime[1000001]={};

int power(int x, unsigned int y, int p)  
{  
    int res = 1;     
  
    x = x % p; 
   
    if (x == 0) return 0; 
  
    while (y > 0)  
    {  
         
        if (y & 1)  
            res = (res*x) % p;  
  
        
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
}  

void pr()
{
  prime[1]=0;

 for(int i=2;i*i<1000001;i++)
  if(prime[i]==0)
  for(int j=i*i;j<1000001;j+=i)
  prime[j]=1;

}

int countSetBits( int n) 
{ 
     int count = 0; 
    while (n) { 
        count += n & 1; 
        n >>= 1; 
    } 
    return count; 
} 
  
bool cmp1(ca c1,ca c2)
{
  if(c1.st<c2.st)
   return true;

  if(c1.st==c2.st && c1.idx<c2.idx)
   return true;

  return false;
}

bool cmp2(ca c1,ca c2)
{
  
  if(c1.idx<c2.idx)
  return true;
  return false;
}








int main()
{

  ios_base::sync_with_stdio(false);
    cin.tie(NULL);

   //pr();
  int t;
  // cin>>t;
   t=1;
  int id=1;

  while(t--)
{
     int n;
      cin>>n;

    double d= 2*pi*n;

    cout<<d;
   
}



return 0;
}


Measured memory_bytes: 3804
import kotlin.math.*

private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map(String::toInt) // list of ints
private fun readLongs() = readStrings().map(String::toLong) // list of longs

fun main() {
    val (n, m, x) = readInts()

    val lines = (1..n).map { readInts() }.toList()

    fun f(sum: List<Int>, lines: List<List<Int>>): Int {
        if (lines.isEmpty()) {
            if (sum.drop(1).all { it >= x }) {
                return sum.first()
            }
            return Int.MAX_VALUE
        }
        val ln = lines.first()
        val nextLines = lines.drop(1)

        // この要素を加算する
        val x = f(sum.zip(ln, Int::plus), nextLines)
        // 加算しない
        val y = f(sum, nextLines)
//        println(x)
//        println(y)
        return min(x, y)
    }

    println(f((0..m).map { 0 }.toList(), lines).takeIf { it != Int.MAX_VALUE } ?: -1)
}


Measured memory_bytes: 41964
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i=l;i<=r;i++)
const int maxn=200500;
using namespace std;
int n,a,b,c,d;
char s[maxn];
void gg(){
    puts("No"); exit(0);
}
int main(){
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    scanf("%s",s+1);
    if (c==d) gg();
    if (c<d){
        while (b!=d){
            if (s[b+1]=='.') b++;
            else {
                if (s[b+2]=='.') b+=2;
                else gg();
            }
        }
        while (a!=c){
            if (s[a+1]=='.') a++;
            else {
                if (s[a+2]=='.') a+=2;
                else gg();
            }
        }
        puts("Yes");
    }
    else {
        while (a<b){
            if (a+1==b) {
                if (s[a+2]=='.') a+=2;
                else {
                    if (s[b+1]=='.') b++;
                    else if (s[b+2]=='.') b+=2;
                    else gg();
                }
            }
            if (s[a+1]=='#'&&a+2==b){
                if (s[b+1]=='.') b++;
                else if (s[b+2]=='.') b+=2;
                else gg();
            }
            if (s[a+1]=='.') a++;
            else {
                if(s[a+2]=='.') a+=2;
                else gg();
            }
        }
        while (a!=c){
            if (s[a+1]=='.') a++;
            else {
                if (s[a+2]=='.') a+=2;
                else gg();
            }
        }
        while (b!=d){
            if (s[b+1]=='.') b++;
            else {
                if (s[b+2]=='.') b+=2;
                else gg();
            }
        }
        puts("Yes");
    }
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

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

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

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int n,k;
vector<vector<int> > sum;
int func(int i,int j){
	return sum[i][j] - sum[i-k][j] -sum[i][j-k] + sum[i-k][j-k];
}

int main()
{
	cin>>n>>k;
	int t = 2*k;
	int f=4*k;
	sum.resize(4*k+5,vector<int>(4*k+5,0));
	for (int i = 0; i < n; i++)
	{
		int x,y;
		string c;
		cin>>x>>y>>c;
		x%=t;
		y%=t;
		if(c=="B") x+=k;
		x%=t;
		sum[x][y]++;
		sum[x+t][y]++;
		sum[x][y+t]++;
		sum[x+t][y+t]++;
	}
	
	for (int i = 1; i < f; i++){
		for (int j = 1; j < f; j++){
			sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
		}
	}
	int ans = 0;
	for (int i = 0; i < t; i++)
	{
		for (int j = 0; j < t; j++)
		{
			int tmp = func(i+k,j+k) + func(i+2*k,j+2*k);
			ans = max(ans,tmp);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 63104
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include <functional>
using namespace std;
int main()
{
	int n,k;
	int node[101][101];
	while(cin>>n>>k,n|k){
	
		for(int i=0; i<=n; i++)
			for(int j=0; j<=n; j++)
				node[i][j] = INT_MAX;
		
		while(k--){
			int m;
			cin>>m;
			if( m ){
				int c,d,e;
				cin>>c>>d>>e;
				node[c][d] = node[d][c] = min(node[d][c],e);
			}else{
				int a,b;
				cin>>a>>b;
				int memo[101];
				priority_queue< pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
				for(int i=0; i<=n; i++)memo[i]=INT_MAX;
				pq.push(make_pair(0,a));
				memo[a]=0;
				while( !pq.empty() ){
					pair<int,int> pi = pq.top();
					if( pi.second == b )break;
					pq.pop();
					for(int i=1; i<=n; i++){
						if( node[pi.second][i]!=INT_MAX &&
							 node[pi.second][i]+pi.first < memo[i] ){
							memo[i] = node[pi.second][i] + pi.first;
							pq.push(make_pair(memo[i],i));
						}
					}
				}
				printf("%d\n",memo[b]==INT_MAX?-1:memo[b]);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 952
import java.util.Scanner;

public class Main {

	private void solve() {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int ans = 0;
		int[] ps = new int[N];
		for (int i = 0; i < N; i++) {
			ps[i] = in.nextInt();
		}
		for (int i = 1; i <= N; i++) {
			if(ps[i-1]==i){
				ans ++;
				i++;
			}
		}
		System.out.println(ans);
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}

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

int main()
{
  int N;
  bool res=false;
  cin >> N;

  for(int i=0; i<= N/4; i++){
    if((N-4*i)%7==0) res=true;
  }

  if(res) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
    string s; cin >> s;
    int top, bottom, n=s.size();
    bool a = true;
    rep(i,n){
        if(s[i]=='A' && a){
            top=i;
            a = false;
        }
        if(s[i]=='Z'){
            bottom=i;
        }
    }

    cout << bottom-top+1 << endl;
}


Measured memory_bytes: 640
using System;

namespace _153232
{
    class Program
    {
        static void Main(string[] args)
        {
            string N = Console.ReadLine();
            double n = int.Parse(N);
            double a = -1;
            if (n == 1) { a = 1; }
            else if (n % 2 == 0) { a = 0.5; }
            else { a = (n + 1)/2 / n; }
            Console.WriteLine(a);
        }
    }
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
map<string, ll> pat;

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

    cin >> N;
    REP(i, N) {
        string s;
        cin >> s;
        SORT(s);
        pat[s]++;
    }

    ll ans = 0;
    for(auto& cnt : pat) {
        ans += (cnt.second * (cnt.second - 1)) / 2;
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 11264
import numpy as np
import sys

N, A, B = input().split()
N = int(N)
A = int(A)
B = int(B)

total = 0

for i in range(N):
    N_quotient_1 = 0
    N_quotient_2 = 0
    N_quotient_3 = 0
    N_quotient_4 = 0
    N_quotient_5 = 0

    sum = 0

    j = i + 1
    if j == 10000:
        N_quotient_1 = int(j / 10000)
        if A == 1:
            total += 10000
            print(total)
            sys.exit()
    if j >= 1000:
        N_quotient_2 = int(j / 1000)
    if j >= 100:
        N_quotient_3 = int((j - N_quotient_2 * 1000) / 100)
    if j >= 10:
        N_quotient_4 = int((j - N_quotient_2 * 1000 - N_quotient_3 * 100) / 10)
    if j >= 1:
        N_quotient_5 = int((j - N_quotient_2 * 1000 - N_quotient_3 * 100 - N_quotient_4 * 10) / 1)

    sum = N_quotient_1 + N_quotient_2 + N_quotient_3 + N_quotient_4 + N_quotient_5

    if A <= sum <= B:
        total += j

print(total)

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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

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

const ll INF = 1e10;;


// 入力
string s, t;

// DPテーブル
int dp[3100][3100] = {0}; // 初期値も初期条件も 0

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

    // DPループ
    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < t.size(); ++j) {
            if (s[i] == t[j]) chmax(dp[i+1][j+1], dp[i][j] + 1);
            chmax(dp[i+1][j+1], dp[i+1][j]);
            chmax(dp[i+1][j+1], dp[i][j+1]);
        }
    }

    // 復元
    string res = "";
    int i = (int)s.size(), j = (int)t.size();
    while (i > 0 && j > 0)
    {
        // (i-1, j) -> (i, j) と更新されていた場合
        if (dp[i][j] == dp[i-1][j]) {
            --i; // DP の遷移を遡る
        }

        // (i, j-1) -> (i, j) と更新されていた場合
        else if (dp[i][j] == dp[i][j-1]) {
            --j; // DP の遷移を遡る
        }

        // (i-1, j-1) -> (i, j) と更新されていた場合
        else {
            res = s[i-1] + res; // このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            --i, --j; // DP の遷移を遡る
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 37120
#include <bits/stdc++.h>
using namespace std;
int cnt[100005];
int sum;
int main()
{
    string s;
    cin >>s;
    for(int i='a';i<='z';i++)
    {
        for(int j=0;j<s.size();j++)
        {
            if(s[j]==i)
            {
                break;
            }
            else
            {
                cnt[i]=cnt[i]+1;
            }
        }
        if(cnt[i]==s.size())
        {
            printf("%c",i);
            break;
        }
    }
    for(int i='a';i<='z';i++)
    {
        if(cnt[i]!=s.size())
        {
            sum=sum+1;
        }
    }
    if(sum==26)
    {
        printf("None");
    }
    
    
  
   
    
}



Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
int main() {
	char s[100001];
	int numChi[100001] = {0};
	int numOdd = 0, numEven = 0, pt;
	scanf("%s", s);
	int len = strlen(s);
	for (int i = 0; i < len;) {
		while (i != len && s[i] == 'R') {
			if (i % 2 == 1)
				numOdd++;
			else
				numEven++;
			i++;
		}
		pt = i;
		if (i % 2 == 0) {
			numChi[pt - 1] += numOdd;
			numChi[pt] += numEven;
		} else {
			numChi[pt - 1] += numEven;
			numChi[pt] += numOdd;
		}
		numOdd = numEven = 0;

		while (i != len && s[i] == 'L') {
			if (i % 2 == 1) {
				numOdd++;
			} else {
				numEven++;
			}
			i++;
		}
		if (pt % 2 == 0) {
			numChi[pt - 1] += numOdd;
			numChi[pt] += numEven;
		} else {
			numChi[pt - 1] += numEven;
			numChi[pt] += numOdd;
		}
		numOdd = numEven = 0;
	}
	for (int i = 0; i < len; i++) {
		printf("%d ", numChi[i]);
	}
	return 0;
}

Measured memory_bytes: 896
#[allow(unused_imports)]
use {
   proconio::{fastout, input, marker::*},
   std::cmp::*,
   std::collections::*,
};

#[fastout]
fn main() {
   input! {
      n: usize,
      x: Bytes,
   }
   let mut pc: usize = 0;
   for i in 0..n {
      if x[i] == b'1' {
         pc += 1;
      }
   }

   if pc == 0 {
      for _ in 0..n {
         println!("1");
      }
      return;
   }

   let mut m0: usize = 0;
   let mut m1: usize = 0;
   let mut r0: usize = 1;
   let mut r1: usize = 1;
   for i in (0..n).rev() {
      if x[i] == b'1' {
         m1 += r1 % (pc + 1);
      }
      r1 = (r1 * 2) % (pc + 1);
   }
   if pc > 1 {
      for i in (0..n).rev() {
         if x[i] == b'1' {
            m0 += r0 % (pc - 1);
         }
         r0 = (r0 * 2) % (pc - 1);
      }
   }
   let mut s = vec![0usize; pc + 1];
   let mut ans = vec![0; n];
   r0 = 1;
   r1 = 1;
   for i in (0..n).rev() {
      ans[i] = if x[i] == b'0' {
         f((m1 + r1) % (pc + 1), &mut s) + 1
      } else {
         if pc == 1 {
            0
         } else {
            f((m0 + pc - 1 - r0) % (pc - 1), &mut s) + 1
         }
      };
      if pc > 1 {
         r0 *= 2;
         r0 %= pc - 1;
      }
      r1 *= 2;
      r1 %= pc + 1;
   }
   for i in 0..n {
      println!("{}", ans[i]);
   }
}

fn f(m: usize, s: &mut Vec<usize>) -> usize {
   if m == 0 || s[m] != 0 {
      s[m]
   } else {
      let mut pc = 0;
      for i in 0.. {
         if (m >> i) & 1 == 1 {
            pc += 1;
         }
         if m >> i == 0 {
            break;
         }
      }
      let x = f(m % pc, s) + 1;
      s[m] = x;
      s[m]
   }
}


Measured memory_bytes: 4744
import math

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
per = math.factorial(n - 1)
r = 0
r2 = 0
for k in range(1, n)[::-1]:
    t = p[0]
    c = sum([t > x for x in p])
    r += per * c
    p.remove(t)
    t = q[0]
    c = sum([t > x for x in q])
    r2 += per * c
    q.remove(t)
    per = int(per / k)

print(int(abs(r - r2)))


Measured memory_bytes: 3064
from collections import defaultdict
def main():
    n, k = map(int, input().split(" "))
    a = list(map(int, input().split(" ")))
    s = []
    ord = [-1]*(n+1)
    u = 1
    while ord[u] == -1:
        ord[u] = len(s)
        s.append(u)
        u = a[u-1]
    l = len(s) - ord[u]
    if k < ord[u]:
        print(s[k])
    else:
        print(s[(k-ord[u])%l+ord[u]])

'''
def main():
    n, k = map(int, input().split(" "))
    a = list(map(lambda i: int(i)-1, input().split(" ")))
    s = [0]
    d = defaultdict(lambda:0)
    x = a[0]
    for i in range(n):
        s.append(x)
        x = a[x]

    bb=None
    for i in range(n):
        d[s[i]] += 1
        if d[s[i]] ==2:
            bb=s[i]
            break

    cc = s.index(bb)
    s[cc]=-1
    dd = s.index(bb)
    loop_len = dd-cc
    s[cc]=s[dd]
        
    if bb ==None or k < cc:
        print(s[k]+1)
    else:
        y = (k-cc) % loop_len
        print(s[y+cc]+1)
'''
if __name__ == "__main__":
    main()

Measured memory_bytes: 33820
#include<stdio.h>
#define N 20000000

int A[N];

int partition(int,int);

main(){
  int k,r,mid;
  int i;

  scanf("%d",&k);

  for(i=0; i<k; i++){

    scanf("%d",&A[i]);

  }

  r = k-1;

  mid = partition(0,r);

  for(i=0; i<mid; i++){

    printf("%d ",A[i]);

  }
  printf("[%d] ",A[mid]);

  for(i=mid+1; i<=r; i++){
    printf("%d",A[i]);
    if(i != r)printf(" ");
  }

  printf("\n");

  return 0;

}


int partition(int p,int r){

int i=0,j,e=0;


for(j=p; j<r; j++){
  if(A[j] <= A[r]){
    
    e = A[i];
    A[i] = A[j];
    A[j] = e;
    i++;
  } 
 }

e = A[r];
A[r] = A[i];
A[i] = e;

return i;
}

Measured memory_bytes: 996
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int W = sc.nextInt();
		int[] w = new int[n];
		int[] v = new int[n];
		for(int i = 0; i < n; i++){
		    w[i] = sc.nextInt();
		    v[i] = sc.nextInt();
		}
		long[][] dp = new long[n][W + 1];
		for(int j = 0; j <= W; j++){
		    if(j - w[0] >= 0){
		        dp[0][j] = v[0];
		    }
		}
		for(int i = 1; i < n; i++){
		    for(int j = 0; j <= W; j++){
		        if(j - w[i] >= 0){
		            dp[i][j] = Math.max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
		        }else{
		            dp[i][j] = dp[i - 1][j];
		        }
		    }
		}
		System.out.println(dp[n - 1][W]);
	}

}


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

enum Pos {
	Left, Center, Right
};

Pos retpos(char num)
{
	if (num == '1' || num == '4' || num == '7') {
		return Left;
	}
	else if (num == '2' || num == '8') {
		return Center;
	}
	else {
		return Right;
	}
}

bool leftcheck(Pos left, Pos right)
{
	if (right == Left) {
		if (left != Left) {
			return false;
		}
	}
	else if (right == Center) {
		if (left == Right) {
			return false;
		}
	}

	return true;
}

bool rightcheck(Pos left, Pos right)
{
	if (left == Right) {
		if (right != Right) {
			return false;
		}
	}
	else if (left == Center) {
		if (right == Left) {
			return false;
		}
	}

	return true;
}

int main()
{
	while (true) {
		string str;

		cin >> str;

		if (str == "#") {
			break;
		}

		Pos right = Right;
		Pos left = Left;
		int rightans = 0;
		int leftans = 0;
		bool nextright = true;

		rep(i, str.size()) {
			if (nextright == true) {
				if (rightcheck(left, retpos(str[i])) == true) {
					right = retpos(str[i]);
					nextright = false;
				}
				else {
					left = retpos(str[i]);
					rightans++;
				}
			}
			else {
				if (leftcheck(retpos(str[i]), right) == true) {
					left = retpos(str[i]);
					nextright = true;
				}
				else {
					right = retpos(str[i]);
					rightans++;
				}
			}
		}

		right = Right;
		left = Left;
		nextright = false;

		rep(i, str.size()) {
			if (nextright == true) {
				if (rightcheck(left, retpos(str[i])) == true) {
					right = retpos(str[i]);
					nextright = false;
				}
				else {
					left = retpos(str[i]);
					leftans++;
				}
			}
			else {
				if (leftcheck(retpos(str[i]), right) == true) {
					left = retpos(str[i]);
					nextright = true;
				}
				else {
					right = retpos(str[i]);
					leftans++;
				}
			}
		}

		if (rightans < leftans) {
			cout << rightans << endl;
		}
		else {
			cout << leftans << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3232
import sys
import copy
import string
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table


mod = 10 ** 9 + 7
d = [0] * (10 ** 3 + 1)
n = ni()
for i in range(1, n+1):
    for pn in prime_decomposition(i):
        d[pn] += 1
ans = 1
for i in range(1, len(d)):
    if d[i] != 0:
        ans *= (d[i] + 1)
        ans %= mod
print(ans)








Measured memory_bytes: 3900
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
bool used[10000];
vector<int> vs;
vector<int> ans;
vector<int> es[10000];
vector<int> res[10000];

void add_edge(int u, int v) {
    es[u].push_back(v);
    res[v].push_back(u);
}

void dfs1(int v) {
    used[v] = true;
    for (int i=0; i<es[v].size(); i++) {
        int u = es[v][i];
        if (!used[u]) dfs1(u);
    }
    vs.push_back(v);
}

void dfs2(int v) {
    used[v] = true;
    for (int i=0; i<res[v].size(); i++) {
        int u = res[v][i];
        if (!used[u]) dfs2(u);
    }
    ans.push_back(v);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i=0; i<m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b);
    }

    fill(used, used+n, false);
    for (int i=0; i<n; i++) {
        if (!used[i]) dfs1(i);
    }

    fill(used, used+n, false);
    for (int i=vs.size()-1; i>=0; i--) {
        if (!used[vs[i]]) dfs2(vs[i]);
    }

    for (int i=0; i<ans.size(); i++) {
        printf("%d\n", ans[i]);
    }
}

Measured memory_bytes: 2252