akhauriyash/Code-Regression huggingface dataset:
n = int(input())
mod = 10**9 + 7
li = [0] * (10**3 + 10)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for i in range(1,n+1):
    li2 = factorization(i)
    for j in li2:
        li[j[0]] += j[1]

ans = 1

for i in li[2:]:
    if i != 0:
        ans *= (i+1)
        ans %= mod

print(ans)


Measured memory_bytes: 3064
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

int main() {
    int N;
    cin >> N;
    vi T(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }
    int M;
    cin >> M;
    vector<vi> drink(M, vi(2));
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> drink[i][j];
        }
    }
    int time = 0;
    for (int x : T) {
        time += x;
    }
    for (int i = 0; i < M; i++) {
        int d = drink[i][1] - T[drink[i][0] - 1];
        cout << time + d << endl;
    }
}


Measured memory_bytes: 3648
#include <stdio.h>

int main(void)
{
	int a,b;
	
	scanf("%d %d", &a, &b);
	
	if(a < b){
		printf("a < b\n");
	}
	else if(a > b){
		printf("a > b\n");
	}
	else{
		printf("a == b\n");
	}
	
	return 0;
}

Measured memory_bytes: 580
from collections import deque

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

def make_dict(x,y):
    for i in ll:
        if i[x] in d.keys():
            d[i[x]]+=[i[y]]
        else:
            d[i[x]]=[i[y]]

cnt=0
for i in range(m):
    ll=l[:i]+l[i+1:]
    d={}
    make_dict(0,1)
    make_dict(1,0)
    k_l=list(d.keys())
    x=0
    sk=k_l[x]
    dq=deque()
    dq.append(sk)
    seen=[]
    while dq:
        k=dq.pop()
        k_ll=d[k]
        seen.append(k)
        for i in k_ll:
            if i not in seen:
                dq.append(i)
        x+=1
    if len(set(seen))!=n:
        cnt+=1
print(cnt)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }

// gcc拡張マクロ
#define gcd __gcd
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll n, k; cin >> n >> k;
    cout << n - k + 1 << endl;
    
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
// #include "lib.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define LLINF 1234567890//987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define MAXN 100006
#define MAXK 200006
#define MAXX 15000006
#define rep(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define bg(ms) *ms.begin()
#define ed(ms) *prev(ms.end(), 1)
#define addedge(a, b, c) v[a].pb(pi(b, c)); v[b].pb(pi(a, c))
#define ph push
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
ll a, b, c;
string lltostr(ll x)
{
	stringstream s;
	s << x;
	return s.str();
}
ll strtoll(string x)
{
	stringstream s(x);
	ll temp;
	s >> temp;
	return temp;
}
int main()
{
	for(ll i = 0; i < 3; i++)
	{
		char ch;
		cin >> ch;
		if(i==0)a = ch-48;
		if(i==1)b = ch-48;
		if(i==2)c = ch-48;
	}
	if(b < a)swap(a, b);
	if(c < b)swap(b, c);
	ll temp = strtoll( lltostr(c) + lltostr(b) );
	cout << temp + a << '\n';
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>

#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

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

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

    uint64_t divA = a / x;
    uint64_t divB = b / x;
//    cout << divA << " " << divB <<  " " << divB - divA << endl;
    int ret = 0;
    if(a%x == 0) {
        ret = 1;
    }

    cout << divB - divA + ret << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cfloat>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

#define ITER( c ) __typeof( (c).begin() )
#define IREP( c, it ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

	while ( true )
	{
		int n;
		cin >> n;

		if ( !n )
		{
			break;
		}

		int res1 = 0, res2 = 0;

		REP( i, 0, n )
		{
			int a, b;
			cin >> a >> b;

			if ( a == b )
			{
				res1 += a;
				res2 += b;
			}
			else if ( a < b )
			{
				res2 += a + b;
			}
			else
			{
				res1 += a + b;
			}
		}
		
		cout << res1 << ' ' << res2 << endl;
	}

	return 0;
}

Measured memory_bytes: 1192
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

X = INT()
i = int ((2*X)**0.5 - 1)

while i*(i+1)//2 < X:
	i += 1
print(i)

Measured memory_bytes: 13596
//入力マクロここから
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
//入力マクロここまで

fn main() {
    input! {
        n: usize,
        a:[i64;n],
    }

    let mut a = a;
    a.sort();

    for i in 0..n - 1 {
        if (a[i] <= 0 && a[i + 1] <= 0)
            || (a[i] < 0 && 0 <= a[i + 1] && a[i].abs() > a[i + 1].abs())
        {
            a[i] *= -1;
            a[i + 1] *= -1;
        }
    }

    println!("{}", a.iter().sum::<i64>());
}


Measured memory_bytes: 4352
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<set>
#include<iomanip>
using namespace std;

int main()
{
	int a[110],n,m,x;
	cin>>n>>m>>a[0];
	x=a[0];
	for(int i=1;i<=m;i++)cin>>a[i];
	sort(a,a+m+1);
	for(int i=1;i<=m+1;i++)
	{
		if(a[i-1]==x)
		{
			cout<<min(i-1,m+1-i)<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 384
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B "How many ways?" ????§£??????
# 
import itertools
while True:
    n, x = map(int, input().split())
    if not n:
        break
    print(list(map(sum, itertools.combinations(range(1, n + 1), 3))).count(x))

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

int main() {
  int n;
  cin >> n;
  if ((n - (n / 1000) * 1000) % 111 == 0 || (n / 10) % 111 == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

int main()
{
  int n;
  cin>>n;
  
  ll arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  
  ll count=0;
  for(int i=0;i<n-2;i++)
  {
    for(int j=i+1;j<n-1;j++)
    {
      if(arr[i]==arr[j])
        continue;
      for(int k=j+1;k<n;k++)
      {
        if(arr[k]==arr[i]||arr[k]==arr[j])
          continue;
        if((arr[i]+arr[j]>arr[k])&&(arr[j]+arr[k]>arr[i])&&(arr[k]+arr[i]>arr[j]))
           count++;
       }
           }
           }
           cout<<count<<endl;
           }

Measured memory_bytes: 3624
import java.util.HashSet;
import java.io.*;

public class Main {
	public static void main(String[] args)throws NumberFormatException, IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		HashSet<String> dic=new HashSet<String>();
		int n=Integer.parseInt(br.readLine());
		for (int i=0;i<n;i++){
			String[] str=(br.readLine().split(" "));
			if (str[0].equals("insert")){
				dic.add(str[1]);
			} else if (str[0].equals("find")){
				if (dic.contains(str[1])){
					System.out.println("yes");
				}else System.out.println("no");
			}
		}
	}
}

Measured memory_bytes: 190492
from collections import deque
import sys
sys.setrecursionlimit(200000)


def read():
    K = int(input())
    return K,


def dfs(i, d, s, q):
    if i == 1:
        q.append(s + str(d))
        return
    if d >= 1:
        dfs(i-1, d-1, s+str(d), q)
    dfs(i-1, d, s+str(d), q)
    if d < 9:
        dfs(i-1, d+1, s+str(d), q)


def solve(K):
    q = deque()
    for i in range(1, 11):
        for d in range(1, 10):
            dfs(i, d, "", q)
    return q[K-1]
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Measured memory_bytes: 17516
#include<bits/stdc++.h>
using namespace std;
int a,b,c,x,ans;//a为500元,b为100元,
//c为50元
int main(){
	scanf("%d%d%d%d",&a,&b,&c,&x);
	for(int i=0;i<=a;i++){
		for(int k=0;k<=b;k++){
			for(int j=0;j<=c;j++){
				if(i*500+k*100+j*50==x)ans++;
				if(i*500+k*100+j*50>x) break;
			}
		} 
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n,m;
int a[1010];
int main()
{
	cin >>n>>m;
	for (int i=0;i<n;i++) cin >>a[i];
	sort(a,a+n);
	int res=0;
	for (int i=0;i<m;i++) res+=a[i];
	cout <<res;
	return 0;
}

Measured memory_bytes: 3636
A,B,C,X,Y = map(int, input().split())
mn = min((A+B)/2, C)
ans1 = 0
ans1 += min(X,Y)*2*mn
if X > Y:
    ans1 += A*(X-Y)
elif Y> X:
    ans1 += B*(Y-X)
ans2 = 0
ans2 += C*max(X, Y)*2
print(int(min(ans1,ans2)))

Measured memory_bytes: 3064
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
ind = 0
ans = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    if i % 2 == 0:
        for j in range(h-1, -1, -1):
            if a[ind] == 0:
                ind += 1
            ans[j][i] = ind+1
            a[ind] -= 1

    else:
        for j in range(h):
            if a[ind] == 0:
                ind += 1
            ans[j][i] = ind+1
            a[ind] -= 1

for i in range(h):
    print(" ".join(map(str, ans[i])))


Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;

int main() {
    
int X;
cin >>X;
vector <bool > expo(X+1);
expo[1] = 1;
  
for(int b=2;b<=X;b++){
  
int v = b*b;
  
while(v<=X){
  
expo[v] = 1;
v *= b;
}
  
}
  
for(int i=X;i>=1;i--) if(expo[i]){
cout <<i<<endl;
return 0;
}
  
 
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	long long ans=0,a[n];
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		a[i] -= i+1;
	} 
	sort(a,a+n);
	for(int i=0;i<n;i++)
		ans += abs(a[n/2]-a[i]);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

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

  if (s.at(k - 1) == 'A') s.at(k - 1) = 'a';
  if (s.at(k - 1) == 'B') s.at(k - 1) = 'b';
  if (s.at(k - 1) == 'C') s.at(k - 1) = 'c';

  cout << s << endl;
}

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

int main(void){
  string s;
  cin>>s;
  for(int i=0;i<s.length();i++){
    if(s[i]=='A'&&s[i+1]=='C'){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  int cnt;
  
  cnt = scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  int cnt;
  
  cnt = scanf("%lld %lld", n, k);

  return;
}

void get_N1234 (int64 *n1, int64 *n2, int64 *n3, int64 *n4)
{
  int cnt;

  if (n2 == NULL) {
    cnt = scanf("%lld", n1);
    return;
  }
  if (n3 == NULL) {
    cnt = scanf("%lld %lld", n1, n2);
    return;
  }
  if (n4 == NULL) {
    cnt = scanf("%lld %lld %lld", n1, n2, n3);
    return;
  }
  cnt = scanf("%lld %lld %lld %lld", n1, n2, n3, n4);
  return;
}

void omit_LF (void)
{
  char c;
  int  cnt;
  
  cnt = scanf("%c", &c);
  return;
}

char *get_S (int64 n)
{
  char *buf;
  int  i;
  int  cnt;

  buf = malloc((size_t)(n * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  return buf;
}

char *get_SN (int64 max, int64 *size)
{
  char *buf;
  int  i;
  int  n;
  int  cnt;

  buf = malloc((size_t)(max * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  n = strlen(buf);

  *size = n;
  
  return buf;
}

int64 *get_NSeq (int64 n)
{
  int64 *buf;
  int64 i;

  buf = malloc((size_t)(n * sizeof(int64)));
  for (i=0; i<n; i++) {
    get_N(&buf[i]);
  }

  return buf;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;

typedef int64 simple_t;

int compare_simple(const void *a, const void *b)
{
  simple_t *x;
  simple_t *y;

  x = (simple_t *)a;
  y = (simple_t *)b;

  if (x > y) return 1;
  if (y < x) return -1;

  return 0;
}
void qsort_simple (simple_t *array, int size)
{
  qsort(array, size, sizeof(simple_t), compare_simple);
}

int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}

long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}

int main()
{
  int64 N;
  int64 a,b,c;
  int64 total = 0;

  get_N(&N);

  for (a=1;a<=N;a++) {
    for (b=1;b<=N;b++) {
      for (c=1;c<=N;c++) {
        total += llgcd(llgcd(a,b),c);
      }
    }
  }
  
  printf("%lld", total);
  return 0;
}



Measured memory_bytes: 1736
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>

#define ll long long int
#define mod 1000000007

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    ll sum = 0;
    for(int i = 0; i < m; i++){
        ll x;
        cin >> x;
        sum += x;
    }
    ll ans = sum > n ? -1 : n - sum;
    cout << ans;
    
}









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

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n)  for(int i=0;i<(n);++i)
#define REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1e9+7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

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

template<class T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
///////////////////////////////////////////////
/*🍈( '-'  🍈*/

int main(){
	int right = 0;
	ll N,M;
	cin >> N >> M;
	vector<int> S(N);
	vector<int> T(M);

	REP(i,N){
	    cin >> S[i];
	}
	REP(i,M){
	    cin >> T[i];
	}

	static ll dp[2003][2003] = {};
	dp[0][0] = 1;
	REP(i,N){
	    REP(j,M){
	    	if (i==0 and j==0) {
	    		if (S[0] == T[0]) dp[0][0] = 2;
	    		else dp[0][0] = 1;
	    		continue;
	    	}else if (i == 0){
				if (S[i] == T[j]){
					dp[i][j] = (dp[i][j-1]+1) % MOD;
				}else{
					dp[i][j] = (dp[i][j-1]+1-1) % MOD;
				}

				if (dp[i][j] < 0) dp[i][j] += MOD;
				continue;
	    	}else if (j==0){
				if (S[i] == T[j]){
					dp[i][j] = (1+dp[i-1][j]) % MOD;
				}else{
					dp[i][j] = (1+dp[i-1][j]-1) % MOD;
				}
				if (dp[i][j] < 0) dp[i][j] += MOD;
				continue;
	    	}
	        if (S[i] == T[j]){
	        	dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % MOD;
	        }else{
	        	dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]) % MOD;
	        }
			if (dp[i][j] < 0) dp[i][j] += MOD;
	    }
	}


	cout << dp[N-1][M-1] % MOD << endl;
	return 0;
}


Measured memory_bytes: 31616
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
mx = max(a)
mn = min(a)
c = mx + 0
b = 0
s = 0
if mx == mn and (mx != N - 1):
  mn -= 1
if mx >= N:
  print("No")
  exit(0)
for i in range(N):
  if abs(a[i] - mx) > 1:
    print("No")
    exit(0)
  if a[i] == mn:
    c = a[i] + 1
    s += 1
  else:
    b += 1
if s >= c and (b != 0 and s != 0):
  print("No")
  exit(0)
elif s > c:
  print("No")
  exit(0)
if b == 1:
  print("No")
  exit(0)
if b // 2 < c - s:
  print("No")
else: print("Yes")

Measured memory_bytes: 52880
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();
            int M = sc.nextInt();

            boolean[] check = new boolean[N];
            int[] W = new int[N];

            int a = 0;
            int w = 0;

            for (int i = 0; i < M; i++) {
                int p = sc.nextInt() - 1;
                String s = sc.next();

                if (s.equals("AC")) {
                    if (!check[p]) {
                        a++;
                        w += W[p];
                        check[p] = true;
                    }
                } else if (s.equals("WA")) {
                    W[p]++;
                }
            }

            System.out.println(a + " " + w);
        }
    }

}


Measured memory_bytes: 63232
class Dice():
    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
    def setNumber(self,n0,n1,n2,n3,n4,n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5
    def roll(self,loc):
        for i in range(6):
            self.work[i] = self.number[i]
        if loc == 'E':
            self.setNumber(self.work[3],self.work[1],self.work[0],self.work[5],self.work[4],self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1],self.work[5],self.work[2],self.work[3],self.work[0],self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4],self.work[0],self.work[2],self.work[3],self.work[5],self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2],self.work[1],self.work[5],self.work[0],self.work[4],self.work[3])
    def equal(self,another):
      ret=False
      for loc in "NNNNWNNNWNNNENNNENNNWNNN":
        self.roll(loc)
        if self.number==another.number:
          ret=True
          break
      return ret         
dices=[]
n=int(input())
for _ in range(n):
  dice=Dice()
  table = list(map(int,input().split()))
  dice.setNumber(table[0], table[1], table[2], table[3], table[4], table[5])
  dices.append(dice)
for i in range(n-1):
  for j in range(i+1,n):
    if dices[i].equal(dices[j]):
      print("No")
      exit()
print("Yes")


Measured memory_bytes: 5620
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        x: i64,
    }
    for i in 0..100000 {
        if i * 100 <= x && x <= i * 105 {
            puts!("1\n");
            return;
        }
    }
    puts!("0\n");
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include<stdio.h>

void mergeSort(int,int,int*);
void merge(int,int,int,int*);
int count=0;
int ans[500000];

int main(void){
  int data;
  int i;

  scanf("%d",&data);

  for(i = 0;i < data;i++){
    scanf("%d",&ans[i]);
  }
    mergeSort(0,data,ans);
  for(i = 0;i < data;i++){
if(i==data-1){printf("%d",ans[i]);
break;
}
      printf("%d ",ans[i]);
  }
  printf("\n%d\n",count);
  return 0;
}

void merge(int left,int mid,int right,int ans[]){
  int i;
  int j = 0;
  int k;

  int n1 = mid - left;
  int n2 = right - mid;
  int L[n1];
  int R[n2];

  for(i = 0;i < n1;i++){
    L[i] = ans[left + i];
  }
  for(i = 0;i < n2;i++){
    R[i] = ans[mid + i];
  }
  L[n1] = R[n2] = 1000000000;
  i = 0;
  j = 0;
  for(k = left;k < right;k++){
    count++;
    if(L[i] <= R[j]){
      ans[k] = L[i];
      i = i + 1;
    }
    else{
      ans[k] = R[j];
      j = j + 1;
    }
  }
}

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



Measured memory_bytes: 5636
#include <iostream>

#include <fstream>

#include <vector>
#include <set>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>

#include <algorithm>
#include <iomanip>
#include <cmath>
#include <random>
#include <cstdlib>
#include <ctime>
#include <utility>

using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define F first
#define S second
#define forcin(n, a) for(int i = 0; i < n; ++i) {cin >> a[i];}
#define forcout(n, a) for(int i = 0; i < n; ++i) {cout << a[i] << " ";}
#define PI acos(-1)
#define forup(st, fin) for(int i = st; i < fin; ++i)
#define fordown(st, fin) for(int i = st; i >= fin; --i)
#define reverse_all(v) reverse(v.begin(), v.end())
#define sort_all(v) sort(v.begin(), v.end())
#define sort_allr(v) sort(v.rbegin(), v.rend())

///#define cin in
///#define cout out
///#define int long long

const ll MAXL = 1e18;
const int N = 10005000;

vector<ll> add, h, d;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    int kek;
    cin >> kek;
    //cout << 2 + 3 + 5 + 7 + 11 << "\n";
    int n = 55555;
    vector<bool> prime (n + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; ++i)
        if (prime[i])
            if (i * 1ll * i <= n)
                for (int j = i * i; j <= n; j += i)
                    prime[j] = false;
    int cnt = 0;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
    vector<int> ans;
    for (int i = 0; i < 55555; ++i) {
        cnt += prime[i];
        if (prime[i]) {
            if (i % 5 == 1) {
                cnt1++;
                ans.push_back(i);
            }
            if (i % 5 == 2) {
                cnt2++;
            }
            if (i % 5 == 3) {
                cnt3++;
            }
            if (i % 5 == 4) {
                cnt4++;
            }
        }
    }
    for (int i = 0; i < kek; ++i) {
        cout << ans[i] << " ";
    }
    cout << "\n";
//    cout << "cnt1 = " << cnt1 << "\n";
//    cout << "cnt2 = " << cnt2 << "\n";
//    cout << "cnt3 = " << cnt3 << "\n";
//    cout << "cnt4 = " << cnt4 << "\n";
//    cout << cnt << "\n";
    return 0;
}
/*
 2 1 1
10 15
6 1

3 0 3
10 8
7 11
5 2
 */

Measured memory_bytes: 256
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=list(itertools.permutations(list(range(2,n+1))))
ans=0
for i in p:
    tmp=1
    for j in range(n-1):
        if [tmp,i[j]] in l or [i[j],tmp] in l:
            tmp=i[j]
        else:break
        if j==n-2:ans+=1
print(ans)

Measured memory_bytes: 3572
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  string S;
  cin >> S;
  map<char, bool> mp;
  rep(i, S.size()) mp[S[i]] = true;
  if (mp.size() < 26) {
    rep(i, 26) {
      if (!mp[i+'a']) {
        S += char(i+'a');
        cout << S << endl;
        return 0;
      }
    }
  }
  for (int i=S.size()-1; i>0; i--) {
    if (S[i-1] < S[i]) {
      char mn = S[i];
      for (int j=i+1; j<S.size(); j++) {
        if (S[j] > S[i-1])
          chmin(mn, S[j]);
      }
      S.erase(i, S.size()-i);
      S[S.size()-1] = mn;
      cout << S << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,c=0,m,mi,r,h;
  cin>>n;
  vector<int> a(n);
  bool f=false,ff=true;
  for(int i=0;i<n;i++) cin>>a[i];
  for(;;){
  m=101;
  for(int i=0;i<n;i++){
    if(a[i]>0){
      ff=false;
      if(f){
        m=min(m,a[i]);
      }else{
        r=i;
        f=true;
        m=min(m,a[i]);
      }
    }else{
      if(f){
        for(int j=r;j<i;j++){
          a[j]-=m;
        }
        c+=m;
        f=false;
      }
    }
  }
  if(f){
    for(int j=r;j<n;j++){
      a[j]-=m;
    }
    c+=m;
  }
  if(ff){
    cout<<c;
    break;
  }
  ff=true;
  f=false;
  }
}

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

int main() {
  long long money = 1000;
  int n; cin >>n;
  vector<long long> a(n), bs(n, 0);
  for (int i = 0; i < n; i++) cin >> a[i];

  long long k = 0;
  for (int i = n-2; i > 0; i--) {
    // 売り条件
    if (a[i-1]<=a[i] && a[i]>a[i+1]) bs[i] = 1;

    // 買い条件
    if (a[i-1]>=a[i] && a[i]<a[i+1]) bs[i] = -1;
  }
  if (a[0] < a[1]) bs[0] = -1;
  if (a[n-2] < a[n-1]) bs[n-1] = 1;

  for (int i = 0; i < n; i++) {
    if (bs[i] == -1 && money > a[i]) {k += money / a[i]; money -= k * a[i];}
    if (bs[i] ==  1) {money += k * a[i]; k = 0;}
  }
  money += a[n-1] * k; // last 4, 100, 110, 110, 110

  cout << money << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int INF=3;
int main(){
  int n,m;
  int min_cost[200005];
  vector<int>node[200005];
  cin>>n>>m;
  for(int i=0;i<=n;i++){
    min_cost[i]=INF;
  }
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    node[a].push_back(b);
    node[b].push_back(a);
  }
  
  queue<int>que;
  que.push(1);
  min_cost[1]=0;
  while(!que.empty()){
    int pos=que.front();que.pop();
    for(int i=0;i<node[pos].size();i++){
      int next=node[pos][i];
      if(min_cost[pos]+1<min_cost[next]){
	min_cost[next]=min_cost[pos]+1;
	que.push(next);
      }
    }
  }
  
  if(min_cost[n]==2){
    cout<<"POSSIBLE"<<endl;
  }else{
    cout<<"IMPOSSIBLE"<<endl;
  }
  return(0);
}

Measured memory_bytes: 13168
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(int i = 0;i < n;++i)
#define LONGINF 1000000000000000000
map<pair<int, int>,int> tizu;
long long h, w, n;
long long ans[100] = {};
pair<int, int> go_through[9] = { pair<int,int>(-1,-1),pair<int,int>(1,-1),pair<int,int>(0,-1),pair<int,int>(-1,0),pair<int,int>(0,0),pair<int,int>(1,0),pair<int,int>(-1,1),pair<int,int>(0,1),pair<int,int>(1,1) };
bool suit(pair<int, int> a) {
	if (a.first+1 <= h&&a.second+1 <= w&&a.first-1 > 0&&a.second-1 > 0) return true;
	return false;
}
int main() {
	scanf("%d%d%d", &h,&w,&n);
	REP(i, n) {
		int a, b;
		scanf("%d%d", &a, &b);
		for (int i = 0;i < 9;++i) {
			a += go_through[i].first;
			b += go_through[i].second;
			pair<int, int> hoge = pair<int,int>(a,b);
			if (suit(hoge) == true) {
				ans[tizu[hoge]]--;
				tizu[hoge]++;
				ans[tizu[hoge]]++;
			}
			a -= go_through[i].first;
			b -= go_through[i].second;
		}
	}
	long long cal = (h-2)*(w-2);
	for (int i = 1;i <= 9;++i) {
		cal -= ans[i];
	}
	ans[0] = cal;
	for (int i = 0;i <= 9;++i) {
		printf("%lld\n", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 56448
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{	
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
struct edge
{
	int to;
	int next;
}e[666666];
int pe=222222;
void insert(int a,int to)
{
	e[pe]=(edge){to,e[a].next};
	e[a].next=pe++;
}
int f[222222],g[222222];
int top[555555];
void dfs(int o,int fa)
{
	int s=0;
	int min=-1;
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa)
		{
			dfs(e[p].to,o);
			cmax(min,top[s&g[e[p].to]]);
			s|=g[e[p].to];
		}
	for(register int i=min+1;i<=20;++i)
		if(!(s&1<<i)){f[o]=i;break;}
	g[o]=1<<f[o];
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa)g[o]|=g[e[p].to]&~((1<<f[o])-1);
}
int main()
{
	top[0]=-1;
	for(register int i=2;i<=524287;++i)
		top[i]=top[i>>1]+1;
	if(1)
	{
		int n=io::F();
		if(n==0)
		{
			puts("0");
			return 0;
		}
		for(register int i=1;i<n;++i)
		{
			int x=io::F(),y=io::F();
			insert(x,y);
			insert(y,x);
		}
		dfs(1,0);
		int max=0;
		for(register int i=1;i<=n;++i)cmax(max,f[i]);
		printf("%d\n",max);
		pe=222222;
		for(register int i=1;i<=n;++i)e[i].next=0;
	}	
	return 0;
}

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

int main(){
char a,b;
cin >> a >> b;
if (a == 'H'){
  if (b == 'H'){
    cout << 'H' <<endl;
  }
  else cout << 'D' << endl;
}
else {
  if (b == 'H'){
    cout << 'D' << endl;
  }
  else cout << 'H' << endl;
}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main (){
  int N;
  vector <int64_t> vec(90);
  vec.at(0) = 2;
  vec.at(1) = 1;    
  cin >> N;
  for (int i = 0;i < N;i++){
   cin >> vec.at(i) >> vec.at(i+1) >> vec.at(i+2);
    vec.at(i+2) = vec.at(i+1) + vec.at(i);
  }
  cout << vec.at(N) << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100000
#define SEN 2000000000

struct Card{
  char suit;
  int value;
};

struct Card L[MAX/2+2],R[MAX/2+2];



void merge(struct Card A[],int n, int left,int mid,int right){
  int i,j,k;
  int n1 = mid - left;
  int n2 = right - mid;

  for(i=0;i<n1;i++)
    L[i] = A[left + i];
  for(i=0;i<n2;i++)
    R[i] = A[mid + i];

  L[n1].value = R[n2].value = SEN;

  i = j = 0;
  for(k=left;k<right;k++){
    if(L[i].value <= R[j].value)A[k] = L[i++];
    else A[k] = R[j++];
  }
}

void mergeSort(struct Card A[],int n,int left,int right){
  int mid;

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

int partition(struct Card A[],int n ,int p,int r){
  int i,j;
  struct Card t,x;

  x = A[r];
  i = p - 1;
  for(j=p;j<r;j++){
    if(A[j].value <= x.value){
      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;
}

void quickSort(struct Card A[],int n, int p, int r){
  int q;

  if(p < r){
    q = partition(A,n,p,r);
    quickSort(A,n,p,q-1);
    quickSort(A,n,q+1,r);
  }
}

int main(){
  int n,i,v;
  struct Card A[MAX],B[MAX];
  char s[10];
  int stable = 1;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s %d",s,&v);
    A[i].suit = B[i].suit = s[0];
    A[i].value = B[i].value = v;
  }

  mergeSort(A,n,0,n);
  quickSort(B,n,0,n-1);

  for(i=0;i<n;i++)
    if(A[i].suit != B[i].suit)stable = 0;

  if(stable == 1)printf("Stable\n");
  else printf("Not stable\n");

  for(i=0;i<n;i++)
    printf("%c %d\n",B[i].suit,B[i].value);

  return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define allsort(v) sort(v.begin(),v.end())
const ll mod = 1e9 + 7;
const int inf = 1e9;

int main() {
	cin.sync_with_stdio(false);
	string S;
	cin >> S;
	int count = 0;
	reps(i,1, S.size()) {
		if (S[i] != S[i - 1])count++;
	}
	cout << count << endl;
	return 0;
}

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

X.sort()
d = [0]*(M-1)

for i in range(M-1):
    d[i] = X[i+1]-X[i]

d.sort()

for i in range(N-1):
    if len(d) > 0:
        d.pop(-1)

print(sum(d))

Measured memory_bytes: 13960
import sys
sys.setrecursionlimit(10**6)

N, A, B, C, D = map(int, input().split())
S = list(input())
S[A-1] = '#'; S[B-1] = '#'
S.extend(['#']*3)
def dfs(a = A, b = B):
    if a == C and b == D:
        return 'Yes'

    if S[a] == '.' and a != C:
        S[a] = '#'; S[a-1] = '.'
        return dfs(a+1, b)
    if S[a+1] == '.' and a != C:
        S[a+1] = '#'; S[a-1] = '.'
        return dfs(a+2, b)
    if S[b] == '.' and b != D:
        S[b] = '#'; S[b-1] = '.'
        return dfs(a, b+1)
    if S[b+1] == '.' and b != D:
        S[b+1] = '#'; S[b-1] = '.'
        return dfs(a, b+2)
    return 'No'
print(dfs())


Measured memory_bytes: 156824
MOD = 10**9+7
MAX = 2*10**5
n, a, b, c = map(int, input().split())

fact = [1]*(MAX+1)
pa, pb, pab = [1]*(MAX+1), [1]*(MAX+1), [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%MOD
    pa[i] = (pa[i-1]*a)%MOD
    pb[i] = (pb[i-1]*b)%MOD
    pab[i] = (pab[i-1]*(a+b))%MOD
    
finv = [1]*MAX + [pow(fact[-1], MOD-2, MOD)]
pabinv = [1]*MAX + [pow(pab[-1], MOD-2, MOD)]
for i in range(MAX, 0, -1):
    finv[i-1] = (finv[i]*i)%MOD
    pabinv[i-1] = (pabinv[i]*(a+b))%MOD

def comb(n, r):
    return ((fact[n]*finv[n-r])%MOD*finv[r])%MOD

ans = 0
for m in range(n):
    ans = (ans \
           + comb(n+m-1, n-1)\
           *((pa[n]*pb[m]%MOD + pa[m]*pb[n]%MOD)%MOD)*pabinv[n+m]%MOD\
           *(n+m)%MOD*100%MOD*pow(100-c, MOD-2, MOD)%MOD
           )%MOD

print(ans)


Measured memory_bytes: 52060
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll somme(vector<int> v, int x, int y)
{
    ll sum = 0;
    for (int i=x; i<=y; i++)
        sum += v[i];
    return sum;
}

int main() 
{
    int n, min, best;
    cin >> n;
    vector<int> v(n);
    best = 0;
    min = 10000;
    for (int i=0; i<n; i++)
        cin >> v[i];
    for (int t=0; t<n; t++)
    {
        ll sum1 = somme(v, 0, t);
        ll sum2 = somme(v, t+1, v.size()-1);
        if (abs(sum1-sum2)<=min)
            min = abs(sum1-sum2);
    }
    cout << min;
    return 0;
}

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

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

  double m = (double)n;
  double ans = 0.0;
  double half=1.0;
  while(n>0){
    if(k>n){
      k=(k+1)/2;
      half /=2.0;
    }
    else{
      ans+=(n-k+1)*(1/m)*half;
      n=k-1;
      k=(k+1)/2;
      half/=2.0;
    }
  }
  printf("%.12f",ans);
}

Measured memory_bytes: 256
"use strict";

function Main(input) {
    input=input.split(" ");
    for(var i=0;i<input.length;i++)
        input[i]=parseInt(input[i],10);
    input.sort(function(a,b){return a-b;});
    console.log(input.join(" "));
}

function debug(){
	var input = document.getElementById("input").value;
	Main(input);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 15552
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <iomanip> 
#include <math.h>
#include <unordered_map>
#include <set>
#include <stack>
#include <functional> 

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define all(x) x.begin(),x.end() 
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

using namespace std;

int a[188888];


int main() {

	int n;
	cin >> n;


	rep(i, n) {
		cin >> a[i];
	}

	if (a[n - 1] != 2)
	{
		cout << -1 << endl;
	}
	else {
		int flag = 1;
		ll min = 2, max = 2;
		for (int i = n - 1; i >= 1; i--) {
			max += a[i];

			max = a[i - 1] * (max / a[i - 1] - 1 * (max % a[i - 1] == 0));
			
			min = a[i - 1] * (min / a[i - 1] + 1 * (min % a[i - 1] != 0));
			
			if (min > max) flag = 0;

		}
		max = a[0] - 1 + max;
		if (flag == 0) {
			cout << -1 << endl;
		}
		else cout << min << " " << max << endl;
	}
	return 0;
}

Measured memory_bytes: 640
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	if ((tmp & ma0) ^ ma0) {
		int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
		tmp = tmp << dig & ma1;
		tmp = tmp * 10 + (tmp >> 8) & ma2;
		tmp = tmp * 100 + (tmp >> 16) & ma3;
		tmp = tmp * 10000 + (tmp >> 32) & ma4;
		ci += (72 - dig >> 3);
	}
	else {
		tmp = tmp & ma1;
		tmp = tmp * 10 + (tmp >> 8) & ma2;
		tmp = tmp * 100 + (tmp >> 16) & ma3;
		tmp = tmp * 10000 + (tmp >> 32) & ma4;
		ci += 8;
		if ((ct = *ci++) >= '0') {
			tmp = tmp * 10 + ct - '0';
			if (*ci++ == '0') {
				tmp = tmp * 10;
				ci++;
			}
		}
	}
	return tmp;
}
const int mod = 1e9 + 7;
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);

	int N = getint();
	int A[200000];
	ll kei = 0;
	__int128 kei2 = 0;
	rep(i, N) {
		kei += (A[i] = getint());
		kei2 += (ll)A[i] * A[i];
	}
	kei %= mod;
	kei = kei * kei % mod;

	int kari = kei2 % mod;
	kei = (kei - kari + mod) % mod;

	kei = kei * (mod / 2 + 1) % mod;

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


	Would you please return 0;
}

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

n = int(input())
s = list(input())

x = 0
max_x = 0

for i in range(len(s)):
    if s[i] == "I":
        x += 1
    elif s[i] == "D":
        x -= 1
    max_x = max(max_x,x)

print(max_x)


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> edge;
ll k,n=50;
ll i,j;
ll out[50];

void printout(){
    cout << "50" << "\n";
for(i = 0; i < n; i++){
        if(i != 49)
        cout << out[i] << " ";
        else cout << out[i] << "\n";
    }
}

int main(){
    cin >> k;
    ll r = (k) % 50;
    ll d = (k) / 50;
    for(i = 0; i < n; i++){
        out[i] = 48;
    }
    out[49] = 49;
        for(j = 0; j < n; j++){
            out[j] = out[j] + d;
        }
    for(i = 0; i < r; i++){
        out[i] = out[i] + 50;
        for(j = 0; j < n; j++){
            if(j!= i){
                out[j]--;
            }
        }
    }
    printout();
    return 0;
}


Measured memory_bytes: 256