akhauriyash/Code-Regression huggingface dataset:
#import <Foundation/Foundation.h>

int main(void){

     NSAutoreleasePool* pool = [NSAutoreleasePool new];
  	 {
    
        NSStringEncoding enc = NSUTF8StringEncoding;
        NSFileHandle *stdin = [NSFileHandle fileHandleWithStandardInput];
        NSFileHandle *stdout = [NSFileHandle fileHandleWithStandardOutput];
        
        NSData *indata = [stdin readDataToEndOfFile];
        NSMutableString *str = [NSMutableString alloc];
        [str initWithBytes:indata.bytes length:indata.length encoding:enc];
        
        NSScanner *scan = [NSScanner alloc];
        [scan initWithString:str];
        
        NSString *n_str = [NSString alloc];
        [scan scanUpToString:@"\n" intoString:&n_str];
        NSInteger n = [n_str integerValue];
        NSInteger r = 48 - n;
      	
       	NSMutableString *r_str = [NSMutableString new];
        
        [r_str appendFormat:@"%d", r];
        
        [stdout writeData:[r_str dataUsingEncoding:enc]];
    }
    [pool release];
    return 0;
}

Measured memory_bytes: 2404
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


int main(){
    ll N, R;
    cin >> N >> R;

    if(N >= 10){
        cout << R << endl;
    }else{
        cout << R + 100 * (10 - N) << endl;
    }

    return 0;
}

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

int d[8] = {1, 2, 1, 2, 1, 4, 1, 4};

void func(int *p, int k)
{
	for (int i = 0; i < 8; i++){
		p[i] = d[(i+k) % 8];
	}
	return;
}

int main(void)
{
	int p[8], res, t, td[8];
	long long m, tt;
	while (scanf("%d%d%d%d%d%d%d%d",&p[0],&p[1],&p[2],&p[3],&p[4],&p[5],&p[6],&p[7])!=EOF){
		res = INT_MAX;
		m = 59999 * 100000;
		for (int i = 0; i < 8; i++){
			func(td, i);
			t = tt = 0;
			for (int j = 0; j < 8; j++){
				t += max(p[j]-td[j],0);
				tt = tt * 10 + td[j];
			}
			if (t < res) {
				res = t;
				m = tt;
			}
			if(res == t && tt < m) {
				res = t;
				m = tt;
			}
		}
		for (int i = 0; i < 8; i++){
			p[7-i] = m % 10;
			m /= 10;
		}
		for (int i = 0; i < 8; i++){
			cout << p[i];
			if (i+1==8) puts("");
			else cout << " ";
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

def solve(num, c, d):
  l=lcm(c,d)
  g=gcd(c,d)
  z=l-c//g-d//g+1
  left=(num//l)*l
  ret=(num//l)*z
  ret+=(num-left)-(num-left)//c-(num-left)//d
  return ret

a,b,c,d=map(int,input().split())
print(solve(b,c,d)-solve(a-1,c,d))

Measured memory_bytes: 3064
while(True):
    a,b = map(int, input().split())
    if a==0 and b==0:
        break

    n = int(input())
    #初期化
    dp = [[0 for y in range(b)] for x in range(a)]
    memo = [[False for y in range(b)] for x in range(a)]
    
    for i in range(n):
        input_x,input_y = map(int, input().split())
        memo[input_x-1][input_y-1] = True #工事中

    dp[0][0] = 1 #(1,1)に到達できる通り数は１
    for x in range(a):
        for y in range(b):
            if memo[x][y]: #工事中なら
                continue
            if (0<=x-1 and x-1<a):
                dp[x][y] += dp[x-1][y]
            if (0<=y-1 and y-1<b):
                dp[x][y] += dp[x][y-1]

    print(dp[a-1][b-1])





Measured memory_bytes: 5608
#include <stdio.h>
#include <string.h>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <math.h>
#include <iostream>
using namespace std;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int T;
	int p,q;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&p,&q);
		int cnt = 0;
		int tmp = (int)sqrt((double)p*p + q*q);
		tmp++;
		//cout<<tmp<<endl;
		for(int x = -tmp;x <= tmp;x++)
			for(int y = -tmp;y <= tmp;y++)
			{
				if(x == 0 &&  y == 0)continue;
				if((x == 1 && y == 0)|| (x == 0 && y == 1)|| (x == -1 && y == 0) ||(x == 0 && y == -1))continue;
				if((x == p && y == q) || (x == -q && y == p)||(x == -p && y == -q)||(x == q && y == -p))
					continue;
				int t1 = x*x + y*y;
				int t2 = x*p + y*q;
				int t3 = x*q - y*p;
				//printf("%d %d %d\n",t1,t2,t3);
				if((p*x + q*y)%(x*x+y*y) != 0)continue;
				if((x*q - y*p)%(x*x + y*y) != 0)continue;
				/*
				if(y == 0)
				{

					if((p%x != 0)|| (q%x)!= 0)continue;
					cnt++;
					continue;
				}
				int m = (p*x + q*y)/(x*x + y*y);

				if((m*x - p)%y != 0)continue;

				*/
				cnt++;
			}
		if(cnt == 0)
			printf("P\n");
		else printf("C\n");
	}
    return 0;
}

Measured memory_bytes: 1168
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
0 0 2 0
3
-1 0
0 0
3 0

output:
ONLINE_BACK
ON_SEGMENT
ONLINE_FRONT
"""

import sys

EPS = 1e-9


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def calc_distance(p_info):
    for point in p_info:
        p2_real, p2_imag = map(int, point)
        p2 = p2_real + p2_imag * 1j
        a, b = p1 - p0, p2 - p0
        if cross(a, b) > EPS:
            print('COUNTER_CLOCKWISE')
        elif cross(a, b) < -1 * EPS:
            print('CLOCKWISE')
        elif dot(a, b) < -1 * EPS:
            print('ONLINE_BACK')
        elif abs(a) < abs(b):
            print('ONLINE_FRONT')
        else:
            print('ON_SEGMENT')
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    base_line = tuple(map(int, _input[0].split()))
    p0, p1 = (x + y * 1j for x, y in zip(base_line[::2], base_line[1::2]))

    q_num = int(_input[1])
    q_list = map(lambda x: x.split(), _input[2:])
    calc_distance(q_list)

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int N = nextInt();
  int K = nextInt();
  int ans = 0;
  while (N > 0) {
    N /= K;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 256
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(1,n):
  a[i] += a[i-1]
a += [0]
d = Counter(a)
for i in d:
  cnt += d[i]*(d[i]-1)//2
print(cnt)


Measured memory_bytes: 36984
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String nmi = br.readLine();
		String[] nm = nmi.split(" ");
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);
		int[][] a = new int[m][2];
		int[] num = new int[55];
		for(int i=0;i<m;i++) {
			String abi = br.readLine();
			String[] ab = abi.split(" ");
			num[Integer.parseInt(ab[0])]++;
			num[Integer.parseInt(ab[1])]++;
		}
		for(int i=1;i<=n;i++) {
			System.out.println(num[i]);
		}
	}
}





Measured memory_bytes: 22612
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10001];
int main()
{
	int N, X;
	cin >> N >> X;
	vector <int> m;
	for (int i = 0 ; i < N ; ++i)
	{
		int temp;
		cin >> temp;
		m.push_back(temp);
		X -= temp;
	}
	int total = N;
	sort(m.begin(), m.end());
	int c = 0;
	while (X > 0 && c < N)
	{
		if (X / m[c] == 0)
			break;
		else
		{
			int temp = X / m[c];
			total += temp;
			X = X % m[c];
			c++;
		}
	}
	cout << total << "\n";
    return 0;
}

Measured memory_bytes: 256
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
#define chmax(x,y) (x = max(x, y))
void solve(); int main() { solve(); return 0; }

void solve() {
  vector<int> A(3);
  loop(i,0,3) cin >> A[i];
  sort(A.begin(), A.end());
  if (A[0] == A[1] and A[1] == 5 and A[2] == 7) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main() {
    ll H,W;
    cin>>H>>W;
    vector<vector<string>> data(H,vector<string>(W));
    rep0(i,H){rep0(j,W){cin>>data[i][j];}}
    rep0(i,H){
        rep0(j,W){
            if(data[i][j]=="snuke"){
                cout<<(char)('A'+j)<<i+1<<endl;
                break;
            }
        }
    }
}


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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

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

    char a, b;
    cin >> a >> b;

    string s1, s2;

    for (int i = 0; i < b - '0'; i++) {
        s1 += a;
    }
    for (int i = 0; i < a - '0'; i++) {
        s2 += b;
    }

    string ans = min(s1, s2);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
	int N; 
	cin >> N; 
	string S; 
	cin >> S; 
	long long int P = 1e9 + 7;  
	long long int dp[3010][3010] = {}; // dp[左からi文字][1からiの置換と見て右端がj]
	long long int DP[3010][3010] = {}; // 右端がj以下の累積和
	dp[1][1] = 1; DP[1][1] = 1; 
	for(int i = 2; i <= N; i++){
		for(int j = 1; j <= N; j++){
			if(S.at(i-2) == '<'){
				dp[i][j] = DP[i-1][j-1]; 
			}
			if(S.at(i-2) == '>'){
				dp[i][j] = (P + DP[i-1][i-1] - DP[i-1][j-1]) % P; 
			}
			DP[i][j] = (DP[i][j-1] + dp[i][j]) % P; 
        }
	}
	cout << DP[N][N] << endl; 
}

Measured memory_bytes: 141824
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int	flg[1000001],gen[1000001];
int main(void)
{
	int n,x,j,i,kazu[30],ff;
// ??¨??????????????????????????????????´???°	
	for(i=2;i<=1000000;i++) flg[i]=1;
	for(i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(j=2;j*i<1000000;j++) flg[i*j]=0;
		}
	}
	while(1){
		scanf("%d %d",&n,&x);
		if(n==0 && x==0) break;
		for(i=0;i<n;i++) scanf("%d",&kazu[i]);
		for(i=0;i<=x;i++) gen[i]=0;
		gen[0]=1;
		for(i=0;i<n;i++){
			for(j=0;j<x;j++){
				if(gen[j]==1){
					if(j+kazu[i]<=x) gen[j+kazu[i]]=1;
				}
			}
		}
		ff=0;
		for(i=x;i>=2;i--){
			if(gen[i]==1 && flg[i]==1){
				ff=1;
				break;
			}
		}
		if(ff==0) printf("NA\n");
		else printf("%d\n",i);
	}
	return 0;
}
	

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

int main(){
    int r,c,x,tmp,total;
    cin >> r >> c;
    int data[r][c];
    total = 0;
    for (int i = 0; i < r; i++){
        tmp = 0;
        for (int j = 0; j < c; j++){
            cin >> data[i][j];
            cout << data[i][j] << ' ';
            tmp += data[i][j];
        }
        cout << tmp << '\n';
        total += tmp;
    }
    for (int i = 0; i < c; i++){
        tmp = 0;
        for (int j = 0; j < r; j++){
            tmp += data[j][i];
        }
        cout << tmp << ' ';
    }
    cout << total << '\n';
}



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

if n==1 && m==0
  puts "0"
  exit
end

conds = []
m.times do
  conds.push(gets.split.map(&:to_i))
end

ans = Array.new(n)
possible = true

conds.each do |cond|
  if ans[cond[0]-1] == nil || ans[cond[0]-1] == cond[1]
    ans[cond[0]-1] = cond[1]
    #puts "a"
  else
    puts "-1"
    exit
  end
end

count = -1
ans.map! do |num|
  count += 1
  if num == nil
    if count == 0
      1
    else
      0
    end
  else
    num
  end
end
#print ans

if ans[0] == 0 && ans.length > 1
  puts "-1"
  exit
end

#print ans

puts ans.join("")

Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int X,Y,Z,K;
long a[1000],b[1000],c[1000];
vector<long>t;
int id[1000];
long s[1000];
main()
{
	cin>>X>>Y>>Z>>K;
	for(int i=0;i<X;i++)cin>>a[i];
	for(int i=0;i<Y;i++)cin>>b[i];
	for(int i=0;i<X;i++)for(int j=0;j<Y;j++)t.push_back(a[i]+b[j]);
	t.push_back(-1e18);
	sort(t.begin(),t.end());
	for(int i=0;i<Z;i++)
	{
		cin>>c[i];
		id[i]=t.size()-1;
	}
	for(;K--;)
	{
		for(int i=0;i<Z;i++)s[i]=c[i]+t[id[i]];
		int mi=0;
		for(int i=0;i<Z;i++)if(s[mi]<s[i])mi=i;
		cout<<s[mi]<<endl;
		id[mi]--;
	}
}

Measured memory_bytes: 10604
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, d = li()
x = [list(li()) for _ in range(n)]

SQUARE = set([i * i for i in range(10000)])
ans = 0

for i in range(n):
    for j in range(i+1, n):
        dist = 0
        for k in range(d):
            dist += (x[i][k] - x[j][k])**2

        if dist in SQUARE:
            ans += 1

print(ans)


Measured memory_bytes: 4084
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <float.h>
#include <random>

#define repeat(i,n) for (int i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
#define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

struct UnionFind {
  vector<int> par;
  UnionFind(int size) : par(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (par[y] < par[x]) swap(x, y);
      par[x] += par[y]; par[y] = x;
    }
    return x != y;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return par[x] < 0 ? x : par[x] = root(par[x]);
  }
  int size(int x) {
    return -par[root(x)];
  }
};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,M;cin>>N>>M;
  UnionFind UF(N);
  repeat(i,M){
    int X,Y,Z;cin>>X>>Y>>Z;
    X--;Y--;
    UF.unionSet(X,Y);
  }
  vector<bool> used(N);
  ll ans = 0;
  repeat(i,N){
    if(used[UF.root(i)])continue;
    used[UF.root(i)]=true;
    ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
import java.util.*;

class Main {
    public static void main(String... args) {
        int H = IN.nextInt();
		int W = IN.nextInt();
		boolean[][] G = new boolean[H + 1][W + 1];
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				G[i][j] = IN.nextInt() % 2 == 1;
			}
		}

		List<String> log = new ArrayList<>();
        for (int i = 1; i < H; i++) {
			for (int j = 0; j <= W; j++) {
                if (G[i][j]) {
					G[i + 1][j] = !G[i + 1][j];
					log.add(i + " " + j + " " + (i + 1) + " " + j);
				}
			}
		}
		
		for (int j = 1; j < W; j++) {
			if (G[H][j]) {
				G[H][j + 1] = !G[H][j + 1];
				log.add(H + " " + j + " " + H + " " + (j + 1));
			}
		}
        puts(log.size());
		for (String line: log) {
			puts(line);
		}
	}
    static final Scanner IN = new Scanner(System.in);
    static <T> void puts(T arg) { System.out.println(arg); }
}


Measured memory_bytes: 100912
/*

                         YATIN KWATRA                   _03_08_14


Let's Hoop..

------------------------------------------------

           o
 /|   o         o
 \|=--            o
    ##
                    \\
                 /   \O
                O_/   T
                T    /|
                |\  | |
 _______________|_|________

------------------------------------------------

o- - -  \o          __|
   o/   /|          vv`\
  /|     |              |
   |    / \_            |
  / \   |               |
 /  |                   |


------------------------------------------------

HOOPER_4_LYF..

*/

// AC BAKSHI RABBA

// #pragma GCC optimize "trapv"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define FIO                     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pbds                    tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll                      long long
#define ld                      long double
#define ull                     unsigned long long
#define endl                    "\n"
#define fo(i,a,b)               for(int i = a; i<=b ; i++)
#define rfo(i,a,b)              for(int i = a; i>=b ; i--)
#define vii                     vector<int>
#define vll                     vector<ll>
#define pq                      priority_queue
#define uom                     unordered_map
#define all(v)                  v.begin(),v.end()
#define mp                      make_pair
#define pb                      push_back
#define pob                     pop_back
#define ff                      first
#define ss                      second
#define pii                     pair<int,int>
#define pll                     pair<ll,ll>
#define mll                     map<ll,ll>
#define mii                     map<int,int>
#define vvii                    vector<vii>
#define vvll                    vector<vll>
#define mod                     1000000007
#define MIN                     -1e9
#define pi                      3.1415926535897932384626433832795

using namespace std;
using namespace __gnu_pbds;

void INPUT()
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

/*
----------------------------------------------------------------

   -> Check For Overflows
   -> Out of Bounds
   -> Initialisations of global arrays and variables
   -> Read the Question and the sample test cases carefully
   -> Its not Always Complex, Try to simplify
   -> write it down and try to solve
   -> Have Faith in urself and in ur approach
   -> If it seems totally out of reach, switch to next :)
   -> And Come Back later, if possible ..

----------------------------------------------------------------*/

ll n, t, x, y, z;
string s, s1, s2;

void solve()
{
  cin >> s;

  ll sum = 0;

  for (auto &i : s)
  {
    sum += (i - '0');
  }

  if (!(sum % 9)) cout << "Yes\n";
  else cout << "No\n";
}

int main() {

  FIO
  INPUT();

  int t;
  t = 1;
// cin >> t;

  fo(i, 0, t - 1)
  {
    solve();
  }
  return 0;
}

Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, K;
  cin >> N >> K;
  vector<ll> neg, pos;
  ll z = 0, n = 0, p = 0;
  rep(i, N) {
    ll a;
    cin >> a;
    if(a == 0) z++;
    else if(a > 0) pos.push_back(a);
    else neg.push_back(-a);
  }
  sort(all(neg));
  sort(all(pos));
  n = neg.size(), p = pos.size();
  ll cnt1 = n*p;
  ll cnt2 = z*(z-1)/2 + z*(N-z);
  ll cnt3 = n*(n-1)/2 + p*(p-1)/2;
  assert(cnt1 + cnt2 + cnt3 == N*(N-1)/2);

  auto solve1 = [&]() {
    auto test = [&](ll k) {
      ll cnt = 0;
      int j = p;
      rep(i, n) {
        while(j>0 && neg[i]*pos[j-1]>=k) j--;
        cnt += p - j;
      }
      return cnt < K;
    };

    ll ng = 0, ok = longinf;
    while(abs(ok-ng) > 1) {
      ll mid = (ok+ng)/2;
      (test(mid) ? ok : ng) = mid;
    }
    cout << -ok+1 << endl;
  };

  auto solve2 = [&]() {
    auto test = [&](ll k) {
      ll cnt = 0;
      int j = n;
      rep(i, n) {
        while(j>0 && neg[i]*neg[j-1]>k) j--;
        cnt += j-(i<j);
      }
      j = p;
      rep(i, p) {
        while(j>0 && pos[i]*pos[j-1]>k) j--;
        cnt += j-(i<j);
      }
      assert(cnt%2==0);
      return cnt/2 < K-cnt1-cnt2;
    };

    ll ng = longinf, ok = 0;
    while(abs(ok-ng) > 1) {
      ll mid = (ok+ng)/2;
      (test(mid) ? ok : ng) = mid;
    }
    cout << ok+1 << endl;
  };

  if(K <= cnt1) {
    solve1();
  } else if(K <= cnt1 + cnt2) {
    cout << 0 << endl;
  } else {
    solve2();
  }
  return 0;
}


Measured memory_bytes: 2420
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  char a, b;
  cin >> a >> b;

  if (a > b) swap(a, b);
  string s;
  for (ll i = 0; i < (b - '0'); i++) {
    s += a;
  }

  cout << s << endl;
  return 0;
}


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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	ll X, K, D; cin >> X >> K >> D;
	ll ans = 0;
	X = abs(X);
	ll temp = min(K, X/D);
	if ((K-temp) %2 == 0)
		cout << X-temp*D << endl;
	else
		cout << (temp+1)*D - X << endl;
}
template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

int main() {
  ll a, b;
  cin >> a >> b;

  cout << (b % a == 0 ? a + b : b - a) << "\n";
}

Measured memory_bytes: 3616
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<int, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };
#define MAX 1000000
int all[MAX];
int odd[MAX];
int main()
{
	int cnt = 1;
	ivec A;
	while (true)
	{
		int d = cnt * (cnt + 1) * (cnt + 2) / 6;
		if (d < MAX)
		{
			A.push_back(d);
		}
		else break;
		cnt++;
	}
	for (int j = 0; j < MAX; j++)
	{
		all[j] = j;
		odd[j] = j;
	}

	for (int i = 1; i < A.size(); i++)
	{
		for (int j = A[i]; j < MAX; j++)
		{
			all[j] = min(all[j], all[j - A[i]] + 1);
			if (A[i] % 2 == 0)continue;
			odd[j] = min(odd[j], odd[j - A[i]] + 1);
		}
	}
	


	while (true)
	{
		int s;
		scanf("%d", &s);
		if (s == 0)break;
		printf("%d %d\n", all[s], odd[s]);
	}
	return 0;
}

Measured memory_bytes: 11032
import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n=int(input())

s=input().strip()

ans=s[1:].count('E')
t=ans

for i in range(1,n):
    if s[i-1]=='W': t+=1
    if s[i]=='E': t-=1
    ans=min(ans,t)
print(ans)


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

/* typedef */
/* long系 */
typedef long long ll;   // long long
typedef long double ld; // long double
/* vector系 */
typedef vector<int> vi;                    // intのvector
typedef vector<double> vd;                 // doubleのvector
typedef vector<ll> vll;                    // llのvector
typedef vector<ld> vld;                    // ldのvector
typedef vector<pair<int, int>> vi_i;       // i_iのvector
typedef vector<pair<double, double>> vd_d; // d_dのvector
typedef vector<pair<ll, ll>> vl_l;         // l_lのvector
typedef vector<pair<ld, ld>> vld_ld;       // ld_ldのvector
typedef vector<string> vs;                 // stringのvector
/* pair系 */
typedef pair<int, int> i_i;       // int同士のpair
typedef pair<double, double> d_d; // double同士のpair
typedef pair<ll, ll> l_l;         // ll同士のpair
typedef pair<ld, ld> ld_ld;       // ld同士のpair

/* define */
#define all(v) v.begin(), v.end() // コンテナ全体
#define PI (acos(-1))             // 円周率pi

/* stringstream */
stringstream ss;
stringstream init_ss; // save default formatting

/* main */
void Main(void)
{
    int t[4][13];
    memset(t, 0, sizeof(t));
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        char c;
        int rank, suit;
        cin >> c >> rank;
        if (c == 'S')
            suit = 0;
        else if (c == 'H')
            suit = 1;
        else if (c == 'C')
            suit = 2;
        else if (c == 'D')
            suit = 3;
        rank--;
        t[suit][rank]++;
    }
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 13; j++)
        {
            if (t[i][j] == 0)
            {
                if (i == 0)
                    cout << 'S' << " ";
                else if (i == 1)
                    cout << 'H' << " ";
                else if (i == 2)
                    cout << 'C' << " ";
                else if (i == 3)
                    cout << 'D' << " ";
                cout << j + 1 << endl;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();

    return 0;
}



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

using namespace std;

#define pb push_back
#define sz(x) ((int)x.size())
#define sqr(x) ((x)*(x))
#define mem(a) memset(a,0,sizeof(a))
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

const int mn = 305;
const int mod = 998244353;
#define P mod

ll powmod(ll a, ll b, ll P) {
    ll t = 1;
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1) t = t * a % P;
    return t;
}

int n, m;
int a[mn];
ll d[2][mn * mn];
int s[mn];

int main() {
    //cin.sync_with_stdio(0);
#ifdef trote
    freopen("../1.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
    size_t bg = clock();
#endif

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
    bool p = 1;
    memset(d, 0, sizeof d);
    d[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= s[i + 1]; j++) d[p][j] = 0;
        for (int j = 0; j <= s[i + 1]; j++) {
            d[p][j] = (d[p][j] + d[p ^ 1][j] * 2) % mod;
            d[p][j + a[i + 1]] = (d[p][j + a[i + 1]] + d[p ^ 1][j]) % mod;
        }
        p ^= 1;
    }
    ll ans = powmod(3, n, P);
    ll ss = 0;
    //printf("%lld\n", ans);
    for (int i = 0; i <= s[n]; i++) {
        ss += d[p ^ 1][i];

        //printf("%d %d\n", i, d[p ^ 1][i]);
        if (s[n] - i <= i) ans -= d[p ^ 1][i] * 3;
        //if (s[n] - i == i) ans += d[p ^ 1][i] * powmod(3, P - 2, P) % mod;
    }
    memset(d, 0, sizeof d);
    p = 1;
    d[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= s[i + 1]; j++) d[p][j] = 0;
        for (int j = 0; j <= s[i + 1]; j++) {
            d[p][j] = (d[p][j] + d[p ^ 1][j]) % mod;
            d[p][j + a[i + 1]] = (d[p][j + a[i + 1]] + d[p ^ 1][j]) % mod;
        }
        p ^= 1;
    }
    //printf("%lld\n", d[p ^ 1][s[n] / 2]);
    if (s[n] % 2 == 0) ans += d[p ^ 1][s[n] / 2] * 3;

    ans = (ans % mod + mod) % mod;
    //printf("%lld\n", ss);
    printf("%lld\n", ans);

#ifdef trote
    printf("-------------------------------------------\ntime: %f\n", (double) (clock() - bg) / CLOCKS_PER_SEC);
#endif
    return 0;
}


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



int main()
{
    int N,digit,temp=0;
    cin >> N;
    while (N != 0)
    {
        digit = N % 10;
        if (digit == 7)
        {
            temp=1;
            break;
        }
        N = N / 10;
    }
    if (temp == 1)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
}


Measured memory_bytes: 3640
x,y = map(int,input().split())
a_group = [1,3,5,7,8,10,12]
b_group = [4,6,9,11]
c_group = [2]

if x in a_group and y in a_group:
    print('Yes')
elif x in b_group and y in b_group:
    print('Yes')
elif x in c_group and y in c_group:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdint>
#include<cstdio>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

uint64_t getZ() {
  uint64_t v = 0; int c;
  while((c = getchar_unlocked()) >= '0') v=v*10+c-'0';
  return v;
}

int const MAXM = 1000;
int const MAXS = 1<<12;
int const INF = 1e9;
int a[MAXM], u[MAXM], N, M, states;

int dp[MAXM+1][MAXS];

int main() {
  N = getZ(); M = getZ();
  states = 1<<N;
  for(int i = 0; i < M; ++i) {
    a[i] = getZ(); int b = getZ();
    u[i] = 0;
    for(int j = 0; j < b; ++j) u[i] |= 1 << getZ()-1;
  }
  std::fill_n(dp[0], states, INF);
  dp[0][0] = 0;
  for(int i = 1; i <= M; ++i) {
    std::copy_n(dp[i-1], states, dp[i]); // don't use i-th key
    for(int s = 0; s < states; ++s) {
      dp[i][s|u[i-1]] = std::min(dp[i][s|u[i-1]], dp[i-1][s] + a[i-1]); // use i-th key
    }
  }
  int ans = dp[M][states-1];
  if(ans < INF) fin(ans); else fin(-1);
  return 0;
}


Measured memory_bytes: 16256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
/*
a[n]の種類数をmとするとき、答えansは
ans=m  (m∈奇数)
ans=m-1  (m∈偶数)
となることを以下に証明する
数列aが今
b[1]*k1個,b[2]*k2個,b[3]*k3個,...b[m]*km個
で構成されているとする。
ここで(k1<=k2<=...<=km)として一般性を失わない
ここでi=1からi=m-1に関し、
b[i]から1個、b[i+1]から2個を選び、問題の操作をb[i]が1個になるまで繰り返す
こうすることで数列は
b[1]*1個,b[2]*1個,...b[m-1]*1個,b[m]*r個　　-(※)
という状態を作れる
ここからはb[m]を3個選んでrを2個ずつ減らしていくことを考える
この時、rが奇数であれば結局操作を限界までやったときにb[m]は1個
rが偶数であればb[m]は0個残ることになる

(※)の状態に関し、m-1+rと最初の数列の要素数nは一致する。
なぜなら操作一回ごとに必ず数列の要素は2個ずつ減るからである
このため、mが奇数であればrは奇数であり、ダブリをなくすような一連の
操作終了時にb[m]は1個残りmが偶数であればrは偶数であり操作終了時に
b[m]は1個も残らない。

(QED)
 */
int main(){
    int n;cin>>n;
    vector<int> a(n);
    set<int> s;
    rep(i,n){
        cin>>a[i];
        s.insert(a[i]);
    }    
    int ans=s.size();
    if(ans%2==0) ans--;
    cout<<ans<<endl;
    return 0;   
}

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

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vstr;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define asd cout << "ok" << endl;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define trav(it, m) for(auto it = m.begin(); it it!= m.end(); it++)

const char nl = '\n';
const int MOD = 1e9 +7;
const ll INF = 1e19;
const ld PI = acos((ld)-1);
const int MX = 2e5 + 5;

int main(){

  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, t; cin >> n >> t;
  vector<pii> v;
  for(int i = 0; i < n; i++)
  {
    int x, y;
    cin >> x >> y;
    v.pb(mp(x,y));
  }
  sort(all(v));
  for(auto u : v)
  {
    if(u.second <= t)
    {
      cout << u.fi;
      return 0;
    }
  }
  cout << "TLE" <<nl;








  return 0;
}



Measured memory_bytes: 3604
/**
  * Partision
  *
  */

#include <stdio.h>
#define MAX 100000

/* prototype */
int partition(int*, int, int);

int main(){
  int i,n,pivot;
  
  /* input the number of A[] */
  scanf("%d",&n);
  
  int A[n];

  /* input datas */
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  
  pivot = partition(A, 0, n-1); //partition(A, p, r): p??????????????????, r??????????????????(key)??¨?????????
  
  for(i=0;i<n-1;i++){
    if(i==pivot){
      printf("[%d] ",A[i]);
    }else{
      printf("%d ",A[i]);
    }
  }//??????????????§i=n-1(????????????)
  printf("%d\n",A[i]); //??????
  
  return 0;
}
//
//int partition(int *A, int p, int r){
//  int i,k,x,swap;
//  
//   x = A[r]; //A[r]?????????
//   i = p-1; //?????????-1 (????????????????????????i+1?????????)
//   for(k=p;k<r-1;j++){
//     if(A[j] <= x){
//       i = i+1; //x>??????????????§
//       swap = A[i]; //A[i]??¨A[j]?????????
//       A[i] = A[j];
//       A[j] = swap;
//     }
//   }
//    swap = A[i+1]; //A[i]??¨A[j]?????????
//    A[i+1] = A[r];
//    A[r] = swap;
//   return i+1;
//}

//int partition(int *A, int p, int r){
//  int i,j,k,x,swap;
//  
//  x = A[r]; //A[r]?????????
//  i = p-1; //x>A[i]??????
//  j = p-1; //x<A[i]??????  
//   for(k=0;k<r;k++){
//     if(A[k] <= x){
//       i++; //+=1?????????????????????
//       swap = A[i]; //A[i]??¨A[k]?????????
//       A[i] = A[k];
//       A[k] = swap;
//       j++; //x<??????????????§
//     }else if(A[k] > x){
//       j++;
//     }
//   }
//  i++;
//  swap = A[i]; //x(A[r])???????´?
//  A[i] = A[r];
//  A[r] = swap;
//  j++;
//  
//  return i;
//}

int partition(int *A, int p, int r) {
  int i,j,x,swap;

  x = A[r]; //key.????????¨????¬?????????????????????¨?????????
  i = p-1;  //'<x'??????
  /* 'x<'?????????????????????j????????¨????????°?????? */
  for(j=p;j<r;j++) { //'r'???key????????¢?´¢?????????
    if(A[j]<=x){ //A[j]???'<x'????????????????????\??????
      i++;
      swap = A[i];
      A[i] = A[j];
      A[j] = swap;
    }
    //else?????´????????????'x<'???????????????????????????j++??§???????????????????????????????????????????¬????for??????
  }

  /* key(A[r])???'<x'????????????????????\?????? */
  i++; //'<x'???????????????????????????
  swap = A[i];
  A[i] = A[r];
  A[r] = swap;
  
  return i;
}

Measured memory_bytes: 988
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000001;
constexpr ll INF= 1e18;
constexpr ll MOD = 998244353;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int main() {
    string S;
    cin >> S;
    int N = S.size();
    if(S.at(0) == '0' || S.at(N - 1) == '1' || S.at(N - 2) == '0') {
        cout << -1 << endl;
    }
    else {
        bool ret = true;
        vector<int> cnt;
        for(int i = 0;i < N / 2;i++) {
            if(S.at(i) != S.at(N - 2 - i)) {
                ret = false;
            }
            else if(S.at(i) == '1' && i != 0) {
                cnt.push_back(i + 1);
            }
        }
        if(ret == false) {
            cout << -1 << endl;
        }
        else {
            reverse(cnt.begin(),cnt.end());
            cnt.push_back(1);
            vector<P> ret;
            ret.push_back(P(1,2));
            int cnt2 = 2;
            int cnt3 = 3;
            for(int i = 0;i < cnt.size() - 1;i++) {
                int cnt4 = cnt.at(i) - cnt.at(i + 1);
                for(int j = 0;j < cnt4;j++) {
                    ret.push_back(P(cnt2,cnt3));
                    cnt3++;
                }
                cnt2 = cnt3 - 1;
            }
            for(int i = cnt.at(0) + 2;i <= N;i++) {
                ret.push_back(P(1,i));
            }
            for(int i = 0;i < ret.size();i++) {
                cout << ret.at(i).first << " " << ret.at(i).second << endl;
            }
        }
    }
}

Measured memory_bytes: 3376
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 5100000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i=2; i<MAX; i++){
    fac[i] = fac[i-1]*i%MOD;
    inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i] = finv[i-1]*inv[i]%MOD;
  }
}

// 二項係数計算
ll COM(int n, int k){
  if (n<k) return 0;
  if (n<0||k<0) return 0;
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int main() {
  ll X, Y;
  cin >> X >> Y;
  // どうあがいても無理なとき
  if ((2*Y-X)%3!=0||(2*X-Y)%3!=0) {
    cout << 0 << endl;
    return 0;
  }
  COMinit();
  cout << COM((X+Y)/3, (2*X-Y)/3) << endl;
  return 0;
}

Measured memory_bytes: 123156
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N               200005
#define ff              first
#define ss              second
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define mii             map<ll,ll>
#define pq_max          priority_queue<ll>
#define pq_min          priority_queue<ll,vi,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define inp(arr,n)      for(ll x=0;x<n;x++) cin>>arr[x];
#define w(x)            ll x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void fio(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

ll pow_exp(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

int main(){
    fio();

    ll n;
    cin>>n;

    if(n == 1) cout<<0;
    else{
        ll tot = pow_exp(10, n);
        ll nr = ((2 * pow_exp(9, n)) % mod - pow_exp(8, n) + mod) % mod;
        ll res = (tot - nr + mod) % mod;

        cout<<res;
    }

    return 0;
}

Measured memory_bytes: 3660
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vs s(n);
    rep(i, n) cin >> s[i];

    vvi field(n+1, vi(m+1)), side(n+1, vi(m+1));
    vvi yoko(n, vi(m+1)), tate(m, vi(n+1));
    rep(i, n) rep(j, m) {
        field[i+1][j+1] = field[i][j+1] + field[i+1][j] - field[i][j] + (s[i][j] == '1');
        side[i+1][j+1] = side[i+1][j] + side[i][j+1] - side[i][j];
        if(i and s[i][j] == '1' and s[i-1][j] == '1') {
            side[i+1][j+1]++;
            tate[j][i]++;
        }
        if(j and s[i][j] == '1' and s[i][j-1] == '1') {
            side[i+1][j+1]++;
            yoko[i][j]++;
        }
        yoko[i][j+1] += yoko[i][j];
        tate[j][i+1] += tate[j][i];
    }

    while(q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << field[c][d]-field[a-1][d]-field[c][b-1]+field[a-1][b-1] - (side[c][d]-side[a][d]-side[c][b]+side[a][b] + yoko[a-1][d-1]-yoko[a-1][b-1] + tate[b-1][c-1]-tate[b-1][a-1]) << '\n';

    }
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;
long long int n,cnt=0,ans=0,a[60],b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

bool check(){
  ll ma=0;
  rep(i,n){
    ma=max(ma,a[i]);
  }
  if(ma==n-1)return true;
  else return false;
}

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

      
      cin>>n;
      rep(i,n)cin>>a[i];
      while(1){
        if(check())break;
        sort(a,a+n);
        reverse(a,a+n);
        pos=a[0];
        a[0]-=(pos/n)*n;
        pos=pos/n;
        ans+=pos;
        rrep(i,1,n)a[i]+=pos;
        //rep(i,n)Cout(a[i]);
      }
      Cout(ans);
     

       
return 0;
}


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

using namespace std;

const int N = 1e5 + 10;
typedef long long ll;




int n,x;
int a[N];
map< vector < int > , int > mp;


void preP(int n){
    int idx = 1;
    do{
        vector < int > tmp;
        for(int i = 1 ; i <= n ; ++i)
            tmp.push_back(a[i]);
        mp[tmp] = idx++;
    }while(next_permutation(a+1 , a+n+1));


}


int main()
{


    scanf("%d",&n);
    vector < int > v1 , v2;
    for(int i = 1 ; i <= n ; ++i)
        a[i] = i;
    preP(n);
    for(int i = 0 ; i < 2 ; ++i){

        for(int j = 0 ; j < n ; ++j){
            scanf("%d",&x);
            if(i == 0)
                v1.push_back(x);
            else
                v2.push_back(x);
        }
    }
    int frst = 0 , sec = 0;

    for(auto it = mp.begin() ; it != mp.end(); ++it){
        if( (it->first  == v1) && !frst)
            frst = (it->second);
        if( (it ->first == v2) && !sec)
            sec = (it->second);
        if(frst && sec)
            break;
    }
    //cout << sec << " " << frst << "\n";

    printf("%d\n",abs(sec-frst));


    return 0;
}


Measured memory_bytes: 5248
<?php

fscanf(STDIN, "%d %d %d %d", $N, $A, $B, $C);
$L = [];
for ($i = 0; $i < $N; ++$i) {
    $L[] = intval(trim(fgets(STDIN)));
}

function dfs($n, $a, $b, $c) {
    global $N, $A, $B, $C, $L;

    if ($n == $N) {
        if (count($a) === 0 || count($b) === 0 || count($c) === 0) return PHP_INT_MAX;
        return sum($A, $a) + sum($B, $b) + sum($C, $c);
    }

    $min = PHP_INT_MAX;
    $d1 = dfs($n + 1, $a, $b, $c);
    $d2 = dfs($n + 1, array_merge($a, [$L[$n]]), $b, $c);
    $d3 = dfs($n + 1, $a, array_merge($b, [$L[$n]]), $c);
    $d4 = dfs($n + 1, $a, $b, array_merge($c, [$L[$n]]));

    return min($d1, $d2, $d3, $d4);
}

function sum($target, $arr) {
    $sum = 0;

    if (count($arr) > 1) {
        $sum = (count($arr) - 1) * 10;
    }

    $sum += abs($target - array_sum($arr));

    return $sum;
}

echo dfs(0, [], [], []);


Measured memory_bytes: 4604
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
int main(){
  ll n,k;cin>>n>>k;
  map<ll,ll>M;
  rep(i,n){
    ll a,b;cin>>a>>b;
    M[a]+=b;
  }
  vector<P>vec;
  for(auto p:M){
    vec.push_back(p);
  }
  sort(vec.begin(),vec.end());
  ll i=0;
  ll ans;
  ll count=0;
  for(int i=0;i<n;i++){
    count+=vec[i].second;
    if(count>=k){
      cout<<vec[i].first<<endl;
      return 0;
    }
  }
}
    

Measured memory_bytes: 5368
H, W = map(int, input().split())

S = [list(input()) for _ in range(H)]  # .を0に置換しておく。文字列にしか置換できないので注意

# #の座標(i,j)を与え、隣接している#があるならばTrue、そうでなければNoを出力して終了する
def exist_neighbor_black_cell(i,j):
    if "#" in [S[max(0,i-1)][j], S[min(H-1,i+1)][j], S[i][max(0,j-1)], S[i][min(W-1,j+1)]]:
        return True
    else:
        print("No")
        exit()

# どの#にも隣接していない#マスがあれば不可。そうでなければ可
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            exist_neighbor_black_cell(i, j)

print("Yes")

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

#define ul unsigned long long
#define ll long long

int main()
{
  ll n;
  string s;

  cin>>n>>s;

  char dc[3];
  size_t dp[2];
  ul ct=0;
  for (ll i=0;i<1000;i++) {
    dc[0] = '0'+(char)(i % 10);
    dc[1] = '0'+(char)((i/10) % 10);
    dc[2] = '0' + (char)((i / 100) % 10);
    if ((dp[0]=s.find_first_of(dc[0]))!=string::npos) {
      if ((dp[1]=s.find_first_of(dc[1],dp[0]+1))!=string::npos) {
        ct+=s.find_first_of(dc[2],dp[1]+1)!=string::npos;
      }
    }
  }
  cout<<ct<<endl;

  return 0;
}




Measured memory_bytes: 256