akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

ll bin_pow(ll a,ll n,ll mod)
{
  ll res=1;
  while(n>0)
  {
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;        
  }
  return res;
}

vector<ll> ans(2e5+10,0);

int main()
{
  for (int i = 0; i < ans.size(); ++i)
  {
    ll tmp=0;
    ll j=i;
    while(j!=0)
    {
      j%=__builtin_popcount(j);
      tmp++;
    }
    ans[i]=tmp;
  }

  ll n;
  cin>>n;
  string x;
  cin>>x;
  ll pop_x=0;
  for_each(x.begin(), x.end(),[&](auto e){
    if(e=='1') pop_x++;
  });
  ll pop_one=pop_x-1,pop_zero=pop_x+1;
  bool flag=false;
  if(pop_one==0) 
  {
    flag=true;
    pop_one=1;
  }
  ll num_x_one=0,num_x_zero=0;
  for (int i = 0; i < n; ++i)
  {
    if(x[i]=='0') continue;
    num_x_one+=bin_pow(2,n-1-i,pop_one);
    num_x_one%=pop_one;
    num_x_zero+=bin_pow(2,n-1-i,pop_zero);
    num_x_zero%=pop_zero;
  }
  for (int i = 0; i < n; ++i)
  {
    if(x[i]=='1')
    {
      if(flag)
      {
        cout<<0<<endl;
        continue;
      }
      ll idx=(num_x_one+pop_one
        -bin_pow(2,n-i-1,pop_one))%pop_one;
      cout<<1+ans[idx]<<endl;
    }
    else
    {
      ll idx=(num_x_zero+2*pop_zero
        +bin_pow(2,n-i-1,pop_zero))%pop_zero;
      cout<<1+ans[idx]<<endl;
    }
  }
}

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

void solve() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n + 1), b(m + 1);
    long long sum = 0;
    for (int i  = 1; i <= n; i++) {
        long long x;
        cin >> x;
        sum += x;
        a[i] = sum;
    }
    sum = 0;
    for (int i = 1; i <= m; i++) {
        long long x;
        cin >> x;
        sum += x;
        b[i] = sum;
    }

    int ans = 0;
    for (int i = 0, j = m; i <= n; i++) {
        if(a[i] > k) {
            break;
        }
        while(b[j] > k - a[i]) {
            j--;
        }
        ans = max(ans, i + j);
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}


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

using namespace std;

int main(){
  long long  n,k;
  cin >> n >> k;
  vector<int> v(n);
  vector<int> kai(n,-1);
  vector<int> kita(2*n);
  for(long long i=0;i<n;i++){
    cin >> v[i];
    v[i] -= 1;
  }
  long long ind = 0;
  long long i;
  for(i=0;i<2*n;i++){
    kita[i] = ind;
    ind = v[ind];
  }
  if(k<2*n){
    cout << kita[k]+1 << endl;
    return 0;
  }
  int syuki = 0;
  for(int i=2*n-2;i>=0;i--){
    if(kita[i]==kita[2*n-1]){
      syuki = 2*n-1 - i;
      break;
    }
  }
  k = k%syuki;
  int start = 2000000;
  for(int i=0;i<n;i++){
    if(kita[i+syuki]==kita[i]){
      start = i;
      break;
    }
  }
  while(k<start) k+=syuki;
  cout << kita[k] + 1 << endl;
}

Measured memory_bytes: 6428
#include  <functional>
#include  <algorithm>
#include  <exception>
#include  <stdexcept>
#include  <streambuf>
#include  <iterator>
#include  <string.h>
#include  <stdlib.h>
#include  <typeinfo>
#include  <valarray>
#include  <iostream>
#include  <sstream>
#include  <istream>
#include  <stdio.h>
#include  <climits>
#include  <clocale>
#include  <complex>
#include  <csetjmp>
#include  <csignal>
#include  <cstdarg>
#include  <cstddef>
#include  <ctype.h>
#include  <cassert>
#include  <cstdlib>
#include  <utility>
#include  <cstring>
#include  <numeric>
#include  <ostream>
#include  <cwctype>
#include  <fstream>
#include  <iomanip>
#include  <math.h>
#include  <bitset>
#include  <cctype>
#include  <string>
#include  <vector>
#include  <limits>
#include  <locale>
#include  <memory>
#include  <cerrno>
#include  <time.h>
#include  <iosfwd>
#include  <cfloat>
#include  <cstdio>
#include  <cwchar>
#include  <cmath>
#include  <ctime>
#include  <deque>
#include  <queue>
#include  <stack>
#include  <list>
#include  <ios>
#include  <map>
#include  <set>
#include  <new>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
using namespace std;
int n,m;
int main()
{
    string s;
    cin>>s;
    bool flag=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='9')
        {
            flag=1;
            break;
        }
    }
    if(flag)
    cout<<"Yes";
    else
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

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

    vector<ll> dp(n + 1, 0);
    ll tmp = 0, acc = 0;
    for (int i = 0; i < n; i++) {
        tmp = tmp * 10 + (s[i] - '0') * (1 << i);
        dp[i + 1] += acc + tmp;
        acc += dp[i + 1];
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 256
A = [int(input()) for _ in range(5)]
cnt = 0
Max = 10
Max_i = 0
for i in range(len(A)):
    if 0 < A[i]%10 < Max:
        Max = A[i]%10
        Max_i = i
for i in range(len(A)):
    if i != Max_i:
        cnt += A[i]
    while cnt%10 != 0:
        cnt += 1
print(cnt+A[Max_i])

Measured memory_bytes: 38384
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

from heapq import heapify, heappush, heappop, heappushpop, heapreplace
from bisect import bisect_left, bisect_right

x, y, z = map(int, input().split())
tmp = x
x = y
y = tmp
tmp = x
x = z
z = tmp
print(x, y, z)

Measured memory_bytes: 3444
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        InputStreamScanner in = new InputStreamScanner(System.in);
        new Main().solve(in, out);
        out.flush();
    }

    private void solve(InputStreamScanner in, PrintWriter out) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);

        long total = a[0];
        int bottom = 0;
        for (int i = 1; i < n; i++) {
            if (total * 2 < a[i]) {
                bottom = i;
            }
            total += a[i];
        }

        out.println(n - bottom);
    }

    static class InputStreamScanner {

        private InputStream in;

        private byte[] buf = new byte[1024];
        private int len = 0;
        private int off = 0;

        InputStreamScanner(InputStream in)	{
            this.in = in;
        }

        String next() {
            StringBuilder sb = new StringBuilder();
            for (int b = skip(); !isSpace(b);){
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char nextChar() {
            return (char)skip();
        }

        int skip() {
            for (int b; (b = read()) != -1;) {
                if (!isSpace(b)) {
                    return b;
                }
            }
            return -1;
        }

        private boolean isSpace(int c) {
            return c < 33 || c > 126;
        }

        private int read() {
            if (len == -1) {
                throw new InputMismatchException("End of Input");
            }
            if (off >= len){
                off = 0;
                try {
                    len = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException(e.getMessage());
                }
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[off++];
        }
    }
}


Measured memory_bytes: 39068
#include <iostream>

int main() {
    std::string S;
    std::cin >> S;
    int amount = 700;
    for (int i = 0; i < 3; ++i) {
        if (S[i] == 'o') {
            amount += 100;
        }
    }
    std::cout << amount << std::endl;
    return 0;
}


Measured memory_bytes: 760
N = int(input())
A = list(map(int, input().strip().split()))
Q = int(input())
ans = sum(A)
num = [0] * (10**5+1) 
for i in A:
    num[i] += 1
for i in range(Q):
    B,C =  (int(x) for x in input().split())
    ans += (C-B) * num[B]
    num[C] += num[B]
    num[B] = 0
    print(ans)

Measured memory_bytes: 21060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

int N;

string S[200005];

long long ans;

struct Trie{
    int total, word;
    Trie *next[26];
    Trie(){
        total = word = 0;
        for(int i = 0; i < 26; i++)
            next[i] = NULL;

    }
};

Trie* Root = new Trie();
int Cnt[30];

void insert(Trie* node, int index, int pos){
    if(pos == S[index].size()){
        node -> total = 1;
        node -> word = 1;
        return;
    }
    if(node -> next[S[index][pos] - 'a'] == NULL){
        node -> next[S[index][pos] - 'a'] = new Trie();
    }
    insert(node -> next[S[index][pos] - 'a'], index, pos + 1);
}

void DFS(Trie* node){
    for(int i = 0; i < 26; i++){
        if(node -> next[i] == NULL)
            continue;
        DFS(node -> next[i]);
        node -> total += node -> next[i] -> total;
    }
}

void DFS2(Trie* node, int p){
    int v[30];
    for(int i = 0; i < 26; i++)
        v[i] = Cnt[i];
    if(p != -1)
        Cnt[p] = 0;
    if(node -> word){
        for(int i = 0; i < 26; i++)
            ans -= Cnt[i];
    }
    for(int i = 0; i < 26; i++){
        if(node -> next[i] == NULL)
            continue;
        if(node -> next[i] -> word){
            ans += node -> total - node -> word - 1;
            Cnt[i]++;
        }
    }
    for(int i = 0; i < 26; i++){
        if(node -> next[i] == NULL)
            continue;
        DFS2(node -> next[i], i);
    }

    for(int i = 0; i < 26; i++){
        Cnt[i] = v[i];
    }
}

void Read(){
    cin >> N;
    cin.get();
    for(int i = 1; i <= N; i++){
        cin >> S[i];
        reverse(S[i].begin(), S[i].end());
        insert(Root, i, 0);
    }
}


int main()
{
    Read();
    DFS(Root);
    DFS2(Root, -1);
    cout << ans << '\n';
    return 0;
}


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

signed main(void)
{
	long long n, sum;
	cin >> n;
	vector<long long> s(n);

	sum = 0;
	rep(i, n)
	{
		cin >> s[i];
		sum += s[i];
	}
	sort(s.begin(), s.end());
	rep(i, n)
	{
		if (sum % 10 != 0)
			break;
		else
		{
			if (s[i] % 10 != 0)
				sum -= s[i];
		}
	}
	if (sum % 10 == 0)
		cout << 0 << endl;
	else
		cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <climits>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <set>

using namespace std;
using ll = long long;

template<typename T> void print(T t) { cout << t << endl; }
ll MOD = 1000000007;


int main() {
	string S, T;
	cin >> S >> T;
	int ans = INT_MAX;
	for (int i = 0; i < S.size() - T.size() + 1; i++) {
		int n = 0;
		for (int j = 0; j < T.size(); j++) {
			if (T[j] != S[j + i])n++;
		}
		ans = min(ans, n);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3628
import sys
input = sys.stdin.readline

N,W=map(int,input().split())

dp=[[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
    w,v=map(int,input().split())

    for j in range(1,W+1):
        if j>=w:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]

print(dp[N][W])

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

typedef long long ll;
int dp[1000001][2];

int main() {
  string s; cin >> s;
  int n = s.size();
  vector<int> ld(n);
  for (int i = 0; i < n; ++i) {
    ld[i] = s[i]-'0';
  }
  dp[0][1] = 1;
  for (int i = 0; i < n; ++i) {
    int d = ld[i];
    dp[i+1][0] = min(dp[i][0]+d, dp[i][1]+10-d);
    dp[i+1][1] = min(dp[i][0]+d+1, dp[i][1]+9-d);
  }
  cout << dp[n][0] << endl;
}



Measured memory_bytes: 13060
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, a[55];
int ma = -inf, mi = inf, an1, an2;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
		if (a[i] >= ma) {
			ma = a[i];
			an1 = i;
		}
		if (a[i] <= mi) {
			mi = a[i];
			an2 = i;
		}
	}
	cout << 2 * n - 1 << endl;
	if (ma >= abs(mi)) {
		rep(i, n) {
			cout << an1 + 1 << " " << i + 1 << endl;
		}
		rep(i, n - 1) {
			cout << i + 1 << " " << i + 2 << endl;
		}
	}
	else {
		rep(i, n) {
			cout << an2 + 1 << " " << i + 1 << endl;
		}
		for (int i = n - 1; i > 0; i--) {
			cout << i + 1 << " " << i << endl;
		}
	}
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
    char s[11];
    scanf("%s", s);
    int n = strlen(s);
    int a[11] = {};
    int i;
    for (i = 0; i < n; i++)
        a[i] = s[i] - '0';
    unsigned long long int ans = 0;
    unsigned long long int x;
    int j;
    int p[12] = {};
    for (i = 0; i < pow(2, n - 1); i++)
    {
        x = a[0];
        for (j = 0; j < n; j++)
        {
            if (p[j] == 0)
            {
                ans += x;
                x = a[j + 1];
            }
            else
            {
                x *= 10;
                x += a[j + 1];
            }
        }
        p[0]++;
        j = 0;
        while (p[j] > 1)
        {
            p[j] = 0;
            p[j + 1]++;
            j++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 128
from collections import defaultdict
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = map(int,stdin.readline().split())
S,T = map(int,stdin.readline().split())
S,T = S-1,T-1
 
E = defaultdict(list)
lines = stdin.readlines()
for line in lines:
  u,v,d = map(int,line.split())
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))
 
dS = [None]*N
dT = [None]*N
 
Q = [(0,S,False),(0,T,True)]
 
D = float('inf')
 
 
while Q:
  d,v,f = hq.heappop(Q)
  if d*2 > D:
    break

  dM = dT if f else dS
  dN = dS if f else dT
  if dM[v] is None:
    dM[v] = d
    for u,dd in E[v]:
      if dM[u] is None and (d+dd)*2 <= D:
        hq.heappush(Q,(d+dd,u,f))
 
  if dN[v] is not None:
    D = min(dN[v]+d,D)
 
del Q

def helper(start,dist):
  cnts = [0]*N
  cnts[start] = 1

  for d,v in sorted((d,v) for v,d in enumerate(dist) if d is not None):
    c = cnts[v]
    for u,dd in E[v]:
      if dd+d == dist[u]:
        cnts[u] = (cnts[u]+c) % MOD

  return cnts

Sn = helper(S,dS)
Tn = helper(T,dT)


def it():
  for v in range(N):
    if dS[v] is not None:
      ds = dS[v]
      if dT[v] == ds and ds*2 == D:
        yield Sn[v]*Tn[v] % MOD
      else:
        for u,d in E[v]:
          if dT[u] is not None and abs(dT[u]-ds) < d and ds+d+dT[u] == D:
            yield Sn[v]*Tn[u] % MOD


X = list(it())

 
total = reduce(lambda a,b:(a+b)%MOD, X,0)
total = total*total % MOD
 
sub = reduce(lambda a,b:(a+b)%MOD, map(lambda x: x*x % MOD, X),0)
print((total-sub)%MOD)

Measured memory_bytes: 111316
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int a, b;
  cin >> a >> b;
  if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
    cout << "Possible" << endl;
  } else {
    cout << "Impossible" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>

int f[1000005][2];
char s[1000005];

int main() {
    scanf("%s", s);
    int n = strlen(s);
    f[n + 1][1] = 100000000;
    for (int i = n; i; --i) {
        int x = s[i - 1] - 48;
        f[i][0] = std::min(f[i + 1][0], f[i + 1][1] + 1) + x;
        f[i][1] = std::min(f[i + 1][0], f[i + 1][1] - 1) + 10 - x;
    }
    printf("%d\n", std::min(f[1][0], f[1][1] + 1));
    return 0;
}


Measured memory_bytes: 8960
#include<stdio.h>

#define N 100

int main(){
  int M[N][N];
  int n,u,k,v;
  int i,j;
  
  scanf("%d",&n);

  for(i = 0;i < n;i++){
    for(j = 0;j < n;j++){
      M[i][j] = 0;
    }
  }

  for(i = 0;i < n;i++){
    scanf("%d%d",&u,&k);
    u--;
    for(j= 0;j < k; j++){
      scanf("%d",&v);
      v--;
      M[u][v] = 1;
    }
  }

  for(i = 0;i < n; i++){
    for(j = 0;j < n; j++){
      if(j)printf(" ");
       printf("%d",M[i][j]);
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define loop1(n, i) for(int i=1;i<=n;i++)
#define rloop(n, i) for(int i=n;i;i++)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;

int main() {
    int n, k; cin >> n >> k;
    V<int> P(n);
    loop (n, i) cin >> P[i];

    int pos = -1;
    set<int> S;
    int ans = 0;
    int sorted = 0;
    loop (k, i) {
        S.insert(P[i]);
        if (P[i - 1] > P[i]) pos = i;
    }
    if (pos == -1) sorted = 1;
    else ans++;

    for (int i = k; i < n; i++) {
        int h = *prev(S.end());
        int l = *S.begin();
        if (P[i] < h || (P[i - k] != l && pos > i - k + 1)) ans++;

        // if (P[i] < h || (P[i - k] != l && pos > i - k + 1)) {
        //     cout << i << ", " << P[i] << ", " << ans << endl;
        // }

        S.erase(P[i - k]);
        S.insert(P[i]);

        if (P[i - 1] > P[i]) {
            pos = i;
        }
        if (pos <= i - k + 1) sorted = 1;
    }

    if (sorted) ans++;
    cout << ans << endl;
    return 0;
}



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

#define MOD (int)(1e9 + 7)

typedef long long ll;

inline int f(int n) {
  ll res = (1LL * n * (n + 1)) >> 1LL;
  return res % MOD;
}

void solve() {
  int n, k;
  cin >> n >> k;
  if (k > n) {
    cout << 1 << '\n';
    return;
  }
  ll res = 0;
  for (int i = k - 1; i <= n; i++) {
    ll l = f(i), r = f(n) - f(n - i - 1);
    l %= MOD;
    r %= MOD;
    res %= MOD;
    res += (r - l + 1) % MOD;
    res %= MOD;
  }
  while (res < 0) res += MOD;
  cout << res % MOD << '\n';
}

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

Measured memory_bytes: 3660
import sys
from pprint import pprint
import math

def is_prime(x):
    if x == 1: return False

    for k in range(2, int(math.sqrt(x)) + 1):
        if x % k == 0:
            return False

    return True

def solve(x):
    for i in range(x, 10**6):
        if is_prime(i):
            print(i)
            return

if __name__ == '__main__':
    x = int(sys.stdin.readline().strip())
    solve(x)

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

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

int main(){
  int N, ans = 0;
  cin >> N;
  
  vector<int> A(N);
  
  rep(i, N) cin >> A.at(i);
  
  while(true){
    rep(i,N)
      if(A.at(i) % 2 > 0){
        cout << ans << endl; 
        return 0;
      }
    rep(i,N)
      A.at(i) /= 2;
    ans ++;
  }
}
    
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int main() {
	int N,M;
	cin>>N>>M;
	vector<ll> A(N);
	rep(i,N)cin>>A[i];
	std::map<ll, ll> map;
	ll sum = 0;
	map[0]++;
	for (int i = 0; i < N; ++i){
		sum+=A[i];
		sum%=M;
		map[sum]++;
	}
	ll ans = 0;
	for (auto x: map){
		cerr<<x.first<<" "<<x.second<<endl;
		ans+= (ll)(x.second)*(x.second-1)/2;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4992
n = int(input())
a,b = map(int,input().split())
p = list(map(int,input().split()))
cnt = [0]*3
for i in range(n):
    if p[i]<=a:
        cnt[0] += 1
    elif a<p[i]<=b:
        cnt[1] += 1
    else:
        cnt[2] += 1
print(min(cnt))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

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

    ll ans = 0LL;
    for(int b=1; b<=N; b++){
        ll p = N/b;
        ll q = N%b;

        ans += max(p*(b-K), 0LL);
        ans += max(q-K+1, 0LL);
    }

    if(K == 0) ans -= N;

    cout << ans << endl;
}

Measured memory_bytes: 256
N=int(input())
def factorization(n):
    arr = []
    for i in range(1, int(-(-n**0.5//1))+1):
        if n%i==0:
            arr.append(n//i+i-2)
#            arr.append([i,n//i])
    return arr

print(min(factorization(N) ))


Measured memory_bytes: 3060
#import <iostream>
using namespace std;
int main(){
	int N,min=1000000000,Max=1;
	cin>>N;
	int A[N];
	for(int i=0;i<N;i++){
		cin>>A[i];
		if(A[i]>Max)Max=A[i];
		if(A[i]<min)min=A[i];
	}
	int x;
	x=Max-min;
	cout<<x<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

void insertionSort(vector<int> &a, int n)
{
  for (int i = 1; i < n; ++i)
  {
    for (int j = 0; j < n; ++j)
      cout << a[j] << (j + 1 == n ? "\n" : " ");
    int v = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > v)
    {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = v;
  }
}

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &e : a)
    cin >> e;
  insertionSort(a, n);
  for (int j = 0; j < n; ++j)
    cout << a[j] << (j + 1 == n ? "\n" : " ");

  return 0;
}



Measured memory_bytes: 3080
#include<bits/stdc++.h>
#define pb push_back
#define mod int(1e9+7)
#define N int(2e5+100)
#define ll long long int
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define si second
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
   int n;
   cin>>n;
   ll sum=0*1ll;
   for(int i=1;i<=n;i++){
      if(i%3&&i%5){
         sum+=1ll*i;
      }
   }
   cout<<sum<<'\n';
   return 0;
}


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

int main(){
    long A,B,N;
    long c,d;
    cin >> N >> B >> A;
    c = N/(A+B);
    d = N%(A+B);
    if(d>=B) cout << c*B + B << endl;
    else cout << c*B + d << endl;
    return 0;
}

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

using namespace std;

#define ll long long 
#define gcd(a,b) __gcd(a,b)
#define endl '\n'
const int N=2e5+10;
const int inf=1e9;
const int mod=1e9+7;

vector<int>adj[N];
bool vis[N];
int dis[N];

int  main(int argc, char const *argv[])
{
	#ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);

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

    for(int i=0; i<m; i++)
    {
    	int u, v;
    	cin >> u >> v;

    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    for(int i=1; i<=n; i++)
    	dis[i]=inf;

    queue<int>q;
    q.push(1);
    vis[1]=1;
    dis[1]=0;

    while(!q.empty())
    {
    	int u=q.front();
    	//cout << u << endl;
    	q.pop();

    	for(auto v: adj[u])
    	{
    		if(vis[v]==0)
    		{
    			dis[v]=dis[u]+1;
    			//cout << v <<  " " << dis[v] << endl;
    			vis[v]=1;
    			q.push(v);
    		}
    	}
    }

    //cout << dis[n] << endl;

    if(dis[n]<=2)
    	cout << "POSSIBLE" << endl;
    else
    	cout << "IMPOSSIBLE" << endl;
	
	return 0;
}

Measured memory_bytes: 16308
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define pub push_back
#define sec second
#define fir first

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	bool C = false;
	REP(i,SZ(s)){
		if(s[i] == 'C')C = true;
		if(C&&s[i]=='F'){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<vector>
#include<set>
using namespace std;

#define ll long long
#define in ({ll x=0;int o=0,c=getchar();for(;!isdigit(c);c=getchar()) o=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';o?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})
#define instring ({string s;char c=getchar();while(c==' '||c=='\n') c=getchar();while(c!=' '&&c!='\n') s+=c,c=getchar();s;})

#define FOR(i,a,b) for(auto i=a;i<=b;i++)
#define ROF(i,a,b) for(auto i=b;a<=i;i--)
#define rr(x) " "<<#x<<'='<<x<<" "

#define bitnum(x) __builtin_popcountll(x)
#define bitl(x) (64-__builtin_clzll(x))
#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

#define mt make_tuple
#define pi pair<int,int>
#define x first
#define y second

#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define allv(a) a.begin(),a.end()
#define endv(a) (int)a.size()-1

#define ifnot(x) if(!(x))
#define middle(a,b) (a+(b-(a))/2)
#define bp(x) ((x)*(x))
#define pw2(x) (1ll<<x)

#define Min(a,b) ({bool o=false;if(a>b) {a=b;o=true;};o;})
#define Max(a,b) ({bool o=false;if(a<b) {a=b;o=true;};o;})
////////////////////////////////////////// HUX
const int N=1e5+5;
int n;
pi a[N];
main()
{
    n=in;
    FOR(i,1,n) a[i]={in,i};
    sort(a+1,a+n+1);
    FOR(i,1,n) cout<<a[i].y<<" ";
}


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

int main(){
	int k,x;
	cin>>k>>x;
	for(int i=x-k+1;i<x;i++){
		cout<<i<<" ";
	}
	for(int j=x;j<k+x-1;j++){
		cout<<j<<" ";
	}
	cout<<k+x-1;
}


Measured memory_bytes: 3640
#define _USE_MATH_DEFINES 
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <math.h>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <set>
#include <locale>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
ll Lgcd(ll a, ll b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
ll Llcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
using Graph = vector<vector<int>>;
//cout << fixed << setprecision(6);
//cout << setfill('0') << right << setw(2);


int main() {
	double n, k, ans = 0;
	cin >> n >> k;
	for(int i = 1; i < min(n + 1, k); i++) {
		double m = log(k / i) / log(2);
		ans += pow(0.5, ceil(m)) / n;
	}
	if (n >= k) ans += (n - k + 1) / n;
	cout << fixed << setprecision(10);
	cout << ans << endl;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

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

    int N;
    cin >> N;

    vector<double> x(N);
    vector<string> u(N);
    rep (i, N) {
        cin >> x[i] >> u[i];
    }

    double ans = 0;
    rep (i, N) {
        if (u[i] == "JPY") {
            ans += x[i];
        } else {
            ans += 380000*x[i];
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define unless(flg) if ( !(flg) )
#define read cin<<
#define echo cout<<
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
#define cinf(n,x) for(int UNCH=0;UNCH<(n);UNCH++) cin >> x[UNCH];
#define fcin(n,x) for(int UNCH=1;UNCH<=(n);UNCH++) cin>> x[UNCH];
#define memmin(x) memset((x),-1,sizeof((x)))
#define memzer(x) memset((x), 0,sizeof((x)))
#define meminf(x) memset((x),0x3f,sizeof((x)))
#define int long long
typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
typedef map < string , int > mstit;
typedef vector < pii > vpi ;
typedef greater < pii > gpi;
typedef priority_queue < pii , vpi , gpi > dijk ;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
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 qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int n,m,h,w,a,b,c,d;
string str;

signed main(){

  cin >>a >> b>> c;
  if(a+b ==c || a+c==b || b+c==a) cout <<"Yes\n";
  else cout <<"No\n";

  return 0;
}



struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;



Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define print(v) cout<<v<<endl
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define printYES cout<<"YES"<<endl
#define printNO cout<<"NO"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-10;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}
struct Point{double x,y;};
double dis(Point a,Point b){
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
Point tri(Point a, Point b, Point c){
  double a1,a2,b1,b2,c1,c2;
  a1=2*(b.x-a.x);
  b1=2*(b.y-a.y);
  c1=a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y;
  a2=2*(c.x-a.x);
  b2=2*(c.y-a.y);
  c2=a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y;
  Point p;
  p.x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
  p.y=(c1*a2-c2*a1)/(a1*b2-a2*b1);
  return p;
}
int main(){
  startupcpp();
  // ll test;cin>>test;while(test--){
  ll i,j,k,l,N;
  cin>>N;
  double ans=inf,fir;
  vector<Point> v(N);
  Point x;
  rep(i,N)cin>>v[i].x>>v[i].y;
  sort(all(v),[](auto a,auto b){if(a.x!=b.x){return a.x<b.x;}else{return a.y<b.y;}});
  rep(i,N)For(j,i+1,N){
    double res=dis(v[i],v[j])*0.5;
    fir=res;
    x.x=(v[i].x+v[j].x)/2;
    x.y=(v[i].y+v[j].y)/2;
    rep(k,N){
      if(i==k||j==k)continue;
      if(dis(x,v[k])>fir+eps){
        res=inf;
        break;
      }
    }
    chmin(ans,res);
  }
  rep(i,N)For(j,i+1,N)For(k,j+1,N){
    if((v[i].x-v[k].x)*(v[j].y-v[k].y)!=(v[i].y-v[k].y)*(v[j].x-v[k].x)){
      x=tri(v[i],v[j],v[k]);
      fir=dis(x,v[i]);
      rep(l,N){
        if(dis(x,v[l])>fir+eps){
        fir=inf;
        break;
        }
      }
      chmin(ans,fir);
    }
  }
  print(ans);
  return 0;
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_imports)]
 
use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;

pub fn prime_factorize(mut n: usize) -> Vec<(usize, usize)> {
    let mut res: Vec<(usize, usize)> = Vec::new();

    let mut i: usize = 2;

    while i * i <= n {
        if n % i == 0 {
            let mut ex: usize = 0;

            while n % i == 0 {
                ex += 1;
                n = n / i;
            }
            res.push((i, ex));
        }
        i += 1;
    }

    if n != 1 {res.push((n, 1))}

    res
}



#[fastout]
fn main() {
    input!{
        n: usize,
    }
    if n == 1 {
        println!("0");
    } else {
        let map = prime_factorize(n);
        // dbg!(&map);
        let mut ans = 0;

        for v in map.iter() {
            let mut v_mut: isize = v.1 as isize;
            let mut cnt = 1;
            loop {
                // dbg!(&v_mut, &cnt);
                v_mut -= cnt;
                if v_mut > cnt {
                    cnt += 1;
                }  else {
                    break;
                }
                
            }
            // &dbg!(&cnt);
            ans += cnt;
        }

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



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

int main() {
  int a,b;
  bool flag = true;
  cin >> a >> b;
  if(a>9) {
    flag = false;
  }else if(b > 9) {
    flag = false;
  }
  if(flag) {
    cout << a*b << endl;
  }else {
    cout << -1 << endl;
  }
  return 0;
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

const int M = 100010;
const int MLV = 18; 
vector<int> G[M];
int root;
int n,q;
int parent[MLV][M];
int depth[M];

void dfs(int v,int p,int d){
	parent[0][v] = p;
	depth[v] = d;
	for(int i = 0;i < G[v].size();i++){
		if(G[v][i] != p) dfs(G[v][i],v,d + 1);
	}
}

void init(int V){
	dfs(root,-1,0);
	for(int k = 0;k+1 < MLV;k++){
		for(int v = 1;v <= V;v++){
			if(parent[k][v] < 0) parent[k+1][v] = -1;
			else parent[k+1][v] = parent[k][parent[k][v]];
		}
	}
}

int lca(int u,int v){
	if(depth[u] > depth[v]) swap(u,v);
	for(int k = 0;k < MLV;k++){
		if((depth[v] - depth[u]) >> k & 1){
			v = parent[k][v];
		}
	}
	if(u == v)return u;
	for(int k = MLV-1;k >= 0;k--){
		if(parent[k][u] != parent[k][v]){
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return parent[0][u];
}

class RootedNode{
public:
	int parent;
	ll depth,dist;
	RootedNode():depth(0),parent(-1),dist(0){}
};

class RootedTree{
public:
	vector<RootedNode> node;

	RootedTree(int node_num){
		node.resize(node_num);
	}
	void AddNode(int p,int c,ll d=1){
		if(node[c].parent!=-1){
			int ndis = node[p].dist+d;
			int ndep = node[p].depth+1;
			int oc = c;
			while(node[oc].parent!=-1){
				node[oc].depth += ndep;
				node[oc].dist += ndis;
				oc = node[oc].parent;
			}
			node[oc].parent = p;
		}
		else{
			node[c].parent = p;
			node[c].dist = node[p].dist+d;
			node[c].depth = node[p].depth+1;
		}
	}
	RootedNode FindLCA(int a,int b){
		RootedNode left=node[a],right=node[b];
		while(left.depth!=right.depth){
			if(left.depth<right.depth) left = node[left.parent];
			else right = node[right.parent];
		}
		return left;
	}
};

vector<vector<pair<int,int>>> graph;
int length[M];
void dfs2(int v,int p,int d,int dist){
	parent[0][v] = p;
	depth[v] = d;
	length[v] = dist;
	for(int i = 0;i < graph[v].size();i++){
		if(graph[v][i].first != p) dfs2(graph[v][i].first,v,d + 1,dist+graph[v][i].second);
	}
}

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

	int N=in();
	graph.resize(N);
	REP(i,N-1){
		int u=in(),v=in(),w=in();
		graph[u-1].emplace_back(v-1,w);
		graph[v-1].emplace_back(u-1,w);
	}
	dfs2(0,-1,0,0);

	REP(i,N){
		if(length[i]%2) cout << 1 << endl;
		else cout << 0 << endl;
	}

	return 0;
}


Measured memory_bytes: 13696
from collections import deque

class Dinic:
    class edge:
        def __init__(self,to,cap,rev):
            self.to,self.cap,self.rev=to,cap,rev

    def __init__(self,v):
        self.numv=v
        self.G=[[] for _ in xrange(self.numv)]

    def add(self,fr,to,cap):
        self.G[fr].append(self.edge(to,cap,len(self.G[to])))
        self.G[to].append(self.edge(fr,0,len(self.G[fr])-1))

    def bfs(self,s):
        self.level=[-1]*self.numv
        self.level[s]=0
        que=deque()
        que.append(s)
        while len(que)!=0:
            v=que.popleft()
            for i in xrange(len(self.G[v])):
                e=self.G[v][i]
                if e.cap>0 and self.level[e.to]<0:
                    self.level[e.to]=self.level[v]+1
                    que.append(e.to)

    def dfs(self,v,t,f):
        if v==t:return f
        for i in xrange(self.iter[v],len(self.G[v])):
            self.iter[v]=i
            e=self.G[v][i]
            if e.cap>0 and self.level[v]<self.level[e.to]:
                d=self.dfs(e.to,t,min(f,e.cap))
                if d>0:
                    e.cap-=d
                    self.G[e.to][e.rev].cap+=d
                    return d
        return 0

    def max_flow(self,s,t):
        flow=0
        inf=float('inf')
        while 1:
            self.bfs(s)
            if self.level[t]<0:return flow
            self.iter=[0]*self.numv
            f=self.dfs(s,t,inf)
            while f>0:
                flow+=f
                f=self.dfs(s,t,inf)

V,E=map(int,raw_input().split())
MF=Dinic(V)
for i in xrange(E):
    u,v,c=map(int,raw_input().split())
    MF.add(u,v,c)
print(MF.max_flow(0,V-1))

Measured memory_bytes: 7228
def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = int(raw_input())
S = map(int, raw_input().split())

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Measured memory_bytes: 52808
def judge(str):
    for i in range(len(str) - 2):
        if str[i] == str[i + 2]:
            print(i + 1, i + 3)
            return
    
    for i in range(len(str) - 1):
        if str[i] == str[i + 1]:
            print(i + 1, i + 2)
            return

    print(-1, -1)
    return

s = input()
judge(s)

Measured memory_bytes: 3188
/* c++---code_marshal
*/

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;cin>>n>>m;int c=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++)c++;
    }
    for(int i=0;i<m;i++){
        for(int j=i+1;j<m;j++)c++;
    }
    cout<<c;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    string ans="YAKI";
    if(s.length()<ans.length()){
        cout<<"No"<<endl;
        return 0;
    }
    bool check=true;
    for(int i=0;i<ans.length();i++){
        if(ans[i]!=s[i])check=false;
    }
    if(check){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

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

AB_count = 0
A_end = 0
B_start = 0
B_start_and_A_end = 0
for i in range(N):
    string = input()
    AB_count += string.count("AB")
    
    if string[0] == "B":
        B_start += 1
    if string[-1] == "A":
        A_end += 1
    if string[0] == "B" and string[-1] == "A":
        B_start_and_A_end += 1
    
new_AB = min(A_end,B_start)
if B_start_and_A_end == A_end and B_start_and_A_end == B_start and B_start_and_A_end != 0:
    new_AB -= 1

print(AB_count+new_AB)

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std; 
#define vll vector<long long>
#define mll map<long long,long long>
#define pb push_back
typedef  long long ll;
typedef long double ld;
long double pi=3.14159265358979323846;

vll al[500005];
ll vis[500005],color[500005],I[101][101];

ll gcd(ll a,ll b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}

bool isPrime(int n)
{
    if (n<=1) return false; 
    if (n<=3) return true; 
    if (n%2==0||n%3==0) return false; 
    for (int i=5;i*i<=n;i=i+6) if (n%i==0||n%(i+2)==0) return false; 
    return true; 
}

ll bpow(ll n, ll po)
{
	ll res=1;
	while(po>0)
	{
		if(po%2)
		{
			res*=n;
			po--;
		}
		else
		{
			n*=n;
			po/=2;
		}
	}
	return res;
}

ll binpow(ll n, ll po, ll mod)
{
	ll res=1;
	while(po>0)
	{
		if(po%2)
		{
			res=(res*n)%mod;
			po--;
		}
		else
		{
			n=(n*n)%mod;
			po/=2;
		}
	}
	return res;
}

ll swap(ll a, ll b)
{
	a=a+b;
	b=a-b;
	a=a-b;
}

ll fact(ll n) { 
   if ((n==0)||(n==1))
      return 1;
   else
      return n*fact(n-1);
}

ll C(ll n, ll r) {
    if(r > n - r) r = n - r; 
    ll ans = 1;
    ll i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
        ans=ans%1000000007;
    }

    return ans;
}

//bool bipartite_dfs(ll node, ll flag)
//{
//	vis[node]=1;
//	ll cflag=flag;
//	color[node]=cflag;
//	for(ll child : al[node])
//	{
//		if(!vis[child])
//		{
//			bool n=bipartite_dfs(child,1-cflag);
//			if(n==false) return false;
//		}
//		else if(color[child]==color[node]) return false;
//	}
//	return true;
//}

void mmul(ll A[][101], ll B[][101], ll dim)
{
	ll res[dim][dim];
	for(ll i=0;i<dim;i++) for(ll j=0;j<dim;j++)
	{
		res[i][j]=0;
		for(ll k=0;k<dim;k++) res[i][j]=(res[i][j]+A[i][k]*B[k][j])%1000000007;
	}
	for(ll i=0;i<dim;i++) for(ll j=0;j<dim;j++) A[i][j]=res[i][j];
}

void mpow(ll A[][101],ll dim, ll po)
{
	for(ll i=0;i<dim;i++) for(ll j=0;j<dim;j++)
	{
		if(i==j) I[i][j]=1;
		else I[i][j]=0;
	}
	while(po>0)
	{
		if(po%2==1)
		{
			mmul(I,A,dim);
			po--;
		}
		else
		{
			mmul(A,A,dim);
			po/=2;
		}
	}
	for(ll i=0;i<dim;i++) for(ll j=0;j<dim;j++) A[i][j]=I[i][j];
}


int main()
{
	ll n;
	cin>>n;
	n=n%10;
	if(n==2||n==4||n==5||n==7||n==9) cout<<"hon";
	else if(n==0||n==1||n==6||n==8) cout<<"pon";
	else cout<<"bon";
}

Measured memory_bytes: 15292
#include<iostream>
#include<algorithm>
#include<limits>
#include<numeric>
#include<cstdint>
#include<set>

int main() {
  int N; int64_t M; std::cin >> N >> M;
  int64_t l = 1;
  std::set<int64_t> s;
  for(int i = 0; i < N; ++i) {
    int64_t A; std::cin >> A; A/=2;
    if(s.count(A) > 0) continue;
    (l /= std::__gcd(l, A)) *= A;
    if(l > M) goto ZERO;
    s.insert(A);
  }
  for(auto A: s) if((l/A)%2 == 0) goto ZERO;

  {
    int64_t ans = M/l; ans = (ans+1)/2;
    std::cout << ans << std::endl;
  }
  return 0;
ZERO:
  std::cout << "0" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int X[200010];
    rep(i, N) cin >> X[i];
    int x[200010];
    rep(i, N) x[i] = X[i];
    sort(X, X + N);
    int midL = X[N / 2 - 1];
    int midR = X[N / 2];
    rep(i, N) {
        if(x[i] <= midL) {
            cout << midR << endl;
        } else {
            cout << midL << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int main(){
    int n;
    vector<int> a;
    cin>>n;
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        a.push_back(tmp);
    }

    double sum = 0;
    double ans = 0;
    for(int i=0;i<n;i++){
        sum += (double)1/a[i];
    }
    ans =(double)1/sum;
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define forn(i,n)for(ll i=0;i<(n);i++)
#define forn_rev(i,n)for(ll i=(n)-1;i>=0;i--)
#define for1n(i,n) for(ll i=1;i<=(n);i++)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(*a)
#define INF 1e9+5
using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    ll N,M=3;
    cin>>N;
    vector<vector<ll>> arr(N,vector<ll>(M));
    forn(i,N) forn(j,3)cin>>arr[i][j];
    vector<vector<ll>> dp(N,vector<ll>(M));
    dp[0][0]=arr[0][0];
    dp[0][1]=arr[0][1];
    dp[0][2]=arr[0][2];
    for(ll i=1;i<N;i++){
        dp[i][0]=max(dp[i-1][1]+arr[i][0],dp[i-1][2]+arr[i][0]);
        dp[i][1]=max(dp[i-1][0]+arr[i][1],dp[i-1][2]+arr[i][1]);
        dp[i][2]=max(dp[i-1][1]+arr[i][2],dp[i-1][0]+arr[i][2]);
    }

    cout<<max(dp[N-1][0],max(dp[N-1][1],dp[N-1][2]));

    return 0;
}

Measured memory_bytes: 11264