akhauriyash/Code-Regression huggingface dataset:
/// Code By t_bone_289 (Tushar Singh)
/// An Immature Programmer.... I'm still developing !!
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define endl '\n'
#define M 1000000007
#define error(x) cout << #x << " = " << x << endl;
#define pi 3.14159265358979323846
typedef long long ll;
typedef long double ld;
template <typename T>
void ContainerError(T &v){cout<<"{";for(auto &x:v){cout<<x<<',';}cout<<"}"<<endl;return;}
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ll powmod(ll base,ll exp,ll MOD){ll res=1;while(exp>0){if(exp%2==1) res=(res*base)%MOD;base=(base*base)%MOD;exp/=2;}return (res%MOD);}
ll mpow(ll base,ll exp){ll res=1;while(exp>0){if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return (res);}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll x,y;
    cin>>x>>y;
    ll b3 = 2*x-y;
    if(b3<0 || b3%3!=0)
    {
        cout<<0;
        return 0;
    }
    ll b = b3/3;
    ll a = x-2*b;
    if(a<0)
    {
        cout<<0;
        return 0;
    }
    ll z = a+b;
    ll ans = 1;
    for(ll i=1;i<=z;i++)
    {
        ans = (ans*i)%M;
    }
    ll bf = 1;
    for(ll i=1;i<=b;i++)
    {
        bf = (bf*i)%M;
    }
    ll af = 1;
    for(ll i=1;i<=a;i++)
    {
        af = (af*i)%M;
    }
    ans = (ans*powmod(af,M-2,M))%M;
    ans = (ans*powmod(bf,M-2,M))%M;
    ans = (ans)%M;
    cout<<ans;
    return 0;
}



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

int main(){
    int n, m; cin >> n >> m;
    vector<ll> routes(n+1, 1);
    set<int> danger;
    for(int i=0; i<m; i++){
        int d; cin>>d;
        danger.insert(d);
    }
    ll mod = 1000000007;
    for(int i=1; i<=n; i++){
        if(danger.find(i)!=danger.end()) routes[i]=0;
        else{
            if(i==1) continue;
            else routes[i] = (routes[i-1] + routes[i-2]) % mod;
        } 
    }
    cout << routes[n] << endl;
}

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

int main(){
  int S;
  cin >> S;
  int h, m, s;
  s = S % 60;
  m = S / 60 % 60;
  h = S / 60 / 60;
  cout << h << ":" << m << ":" << s << endl; 
}



Measured memory_bytes: 3096
import sys
# import math

N = int(input())
A = list(map(int, input().split()))
A.sort()

if A[0] == 0:
    print(0)
    sys.exit()

ans = 1
for i in range(N):
    ans *= A[i]
    if ans > (10**18):
        print(-1)
        sys.exit()

print(ans)

Measured memory_bytes: 21796
N, K = map(int, input().split())
h = [None] * N
for i in range(N):
    h[i] = int(input())

h = sorted(h)

sub_min = h[N-1] - h[0]
for i in range(N-K+1):
    if h[i+K-1] - h[i] < sub_min:
        sub_min = h[i+K-1] - h[i]

print(sub_min)

Measured memory_bytes: 8240
x1, y1, x2, y2 = map(int, input().split())

dx = x1 - x2
dy = y1 - y2

x3 = x2 + dy
y3 = y2 - dx

x4 = x1 + dy
y4 = y1 - dx

print(x3, y3, x4, y4)

Measured memory_bytes: 3060
//be naame khodaa
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
#define F first
#define S second
#define pb push_back
#define sz(x) ((int)(x).size())

inline int in(){ int x, y; y = scanf("%d", &x); return x; }

const int N = 200*1000 + 5;
const int MOD = 1e9 + 7;

ll dp[N];
int c[N], nxt[N];

int main(){
	int n = in();
	for (int i = 0; i < n; i++)
		c[i] = in();
	fill(nxt, nxt + N, -1);
	dp[n] = 1;
	for (int i = n-1; i >= 0; i--){
		if (nxt[c[i]] == -1 || nxt[c[i]] == i+1)
			dp[i] = dp[i+1];
		else
			dp[i] = (dp[nxt[c[i]]] + dp[i+1])%MOD;
		nxt[c[i]] = i;
	}
	cout << dp[0] << endl;
	return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>

#define NUM_RANKING 3
int
main(int argc, char *argv[])
{
    int i;
    unsigned long v, top[NUM_RANKING] = {0, 0, 0};

    while (EOF != scanf("%lu\n", &v)) {
        for (i = 0; i < NUM_RANKING; i++) {
            unsigned long tmp;
            if (v < top[i]) continue;

            tmp = top[i];
            top[i] = v;
            v = tmp;  // shift ranking
        }
    }

    for (i = 0; i < NUM_RANKING; i++) {
        printf("%lu\n", top[i]);
    }
    return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll ans=0;
const ll INF = 1LL << 60;
bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
int main()
{
ll n , x , d ;
cin >> n >> x >> d ;
if(d==0){
cout << ((x==0)?1:n+1) << endl;
return 0;
}
if(d<0){d*=-1;x*=-1;}
map<ll,vector<pair<ll,ll>>> m;
auto mod = [&](ll modx) {modx%=d;modx+=d;modx%=d;return modx; };
rep(i,n+1){
  ll aa=(i*(i-1)/2)*d+i*x;
  ll bb=((n-1+n-i)*i/2)*d+i*x;
  m[mod(i*x)].emplace_back(min(aa,bb),max(aa,bb));
}
for(auto p:m){
auto &vec = p.second;
		pair<ll, ll> pre = {(ll) -5e18, -5e18};
		sort(vec.begin(), vec.end());
		for (auto now : vec) {
			if (now.second <= pre.second) continue;
			ans += (now.second - max(now.first, pre.second)) / abs(d);
			if (pre.second < now.first) {
				ans++;
			}
			pre = now;
		}
}
cout << ans << endl;
return 0;
}


Measured memory_bytes: 22144
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  [h, w] <- getIntList

  let solve0 x y = let x1 = x `div` 3
                       x2 = (x - x1) `div` 2
                       x3 = x - x1 - x2
                       x_max = max x1 (max x2 x3)
                       x_min = min x1 (min x2 x3)
                   in (x_max - x_min) * y


      solve1 x y rx ry = let y1 = (y + ry) `div` 3
                             y2 = y - y1
                             x1 = (x + rx) `div` 2
                             x2 = x - x1
                             s1 = x * y1
                             s2 = x1 * y2
                             s3 = x2 * y2
                             s_max = max s1 (max s2 s3)
                             s_min = min s1 (min s2 s3)
                         in s_max - s_min

      solve' x y = let a0 = solve0 x y
                       a1 = solve1 x y 0 0
                       a2 = solve1 x y 0 2
                       a3 = solve1 x y 1 0
                       a4 = solve1 x y 1 2
                   in minimum [a0, a1, a2, a3, a4]

      solve = min (solve' h w) (solve' w h)

  print $ solve

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


struct mint {
    long long x;
    static const int MOD = 1000000007;
    mint(long long x=0): x(x%MOD) {}

    void operator=(const long long n) {
        x = n % MOD;
    }
    mint operator+(const mint n) {
        mint ret;
        ret.x = (x + n.x) % MOD;
        return ret;
    }
    mint operator-(const mint n) {
        mint ret;
        ret.x = (x - n.x + MOD) % MOD;
        return ret;
    }
    mint operator*(const mint n) {
        mint ret;
        ret.x = (x * n.x) % MOD;
        return ret;
    }
    mint operator/(const mint n) {
        mint ret;
        ret.x = (x * n.inv().x) % MOD;
        return ret;
    }

    mint inv() const {
        mint ret;
        long long a = x, b = MOD, u = 1, v = 0;
        while(b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= MOD;
        if (u < 0) u += MOD;
        ret.x = u;
        return ret;
    }
};

mint mpow(mint a, int n) {
    mint ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * a;
        a = a * a;
        n >>= 1;
    }
    return ret;
}

void factorial(vector<mint>& fact) {
    for (int i = 0; i < fact.size(); i++) {
        if (i == 0 || i == 1) fact[i] = 1;
        else fact[i] = fact[i-1] * i;
    }
}

mint c(int n, int a, vector<mint>& fact) {
    return fact[n]/(fact[a]*fact[n-a]);
}

void p(int n, int max_a, vector<mint>& perm) {
    for (int i = 0; i <= max_a; i++) {
        if (i == 0) perm[i] = 1;
        else perm[i] = perm[i-1] * (n-i+1);
    }
}

ostream& operator<<(ostream& os, const mint& n)
{
    os << n.x;
    return os;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);


    int n, a, b;
    cin >> n >> a >> b;

    vector<mint> fact(max(a, b)+1, 0);
    factorial(fact);

    vector<mint> perm(max(a, b)+1, 0);
    p(n, max(a, b), perm);

    mint na = perm[a] / fact[a];
    mint nb = perm[b] / fact[b];
    cout << mpow(2, n) - na - nb - 1 << endl;


    return 0;
}



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

int main() {
    string s, t;
    cin >> s >> t;
    int count = 0;
    rep(i, 3) {
        if (s[i] == t[i]) {
            count++;
        }
    }
    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
  long long n;
  std::vector<signed long long> A;

  cin >> n;
  A.resize(n);
  for (long long i=0;i<n;++i) {
    cin >> A[i];
  }
  sort(A.begin(), A.end(), [](auto a, auto b) {
    return abs(b) < abs(a);
  });
  
  for (unsigned long long i=0;i<n-1;++i) {
    if (A[i]<0) {
      A[i] = -A[i];
      A[i+1] = -A[i+1];
    }
  }
  /*
  for (int i=0;i<n;++i) {
    cout << A[i] << " ";
  }
  cout << endl;
  */

  unsigned long long MAX = 0;
  for (int i=0;i<n;++i) {
    MAX += A[i];
  }
  cout << MAX << endl;

  return 0;
}

Measured memory_bytes: 1024
def main():
    N, M = map(int, input().split())
    *A, = map(int, input().split())

    A.sort()
    tot = A[-1] - A[0]

    B = [a1 - a0 for a0, a1 in zip(A, A[1:])]
    B.sort()

    for _ in range(N - 1):
        if not B: break
        tot -= B.pop()
        if tot is 0: break

    print(tot)


if __name__ == '__main__':
    main()


Measured memory_bytes: 13968
# coding: utf-8
# Your code here!
import sys,math
(A,B,H,M) = map(int,input().split())
print(A,B,H,M,file=sys.stderr)

# 2針の回転角度
rad1 = H*(30) + M*(0.5)
rad2 = M*(6)

# 内角
rad = abs(rad1 - rad2)
ans = 0

# 対辺の長さ
'''
if rad == 180:
    ans = A+B
else:
    #rad = rad % 180
    ans = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(rad)))
'''
ans = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(rad)))

print(rad1,rad2,rad,ans,file=sys.stderr)
print(ans)


Measured memory_bytes: 9508
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

ans = sum(d) if flag == 0 else -1
ans = -1 if n == 0 and a[0] > 1 else ans
ans = -1 if a[n] != d[n] else ans
print(ans)

Measured memory_bytes: 680636
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

#define MAX_V 10000

vector<int> G[MAX_V];
list<int> out;
bool V[MAX_V];
int N;//頂点数
int indeg[MAX_V];

void bfs(int s){
    queue<int> q;
    q.push(s);
    V[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        out.push_back(u);
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            indeg[v]--;
            if(indeg[v] == 0 && !V[v]){
                V[v] = true;
                q.push(v);
            }
        }
    }
}

void tsort(){
    for(int i = 0; i < N; i++){
        indeg[i] = 0;
    }

    for(int u = 0; u < N; u++){
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            indeg[v]++;
        }
    }
    
    for(int u = 0; u < N; u++){
        if(indeg[u] == 0 && !V[u]) bfs(u);
    }

}

signed main(){
    int M;
    cin >> N >> M;
    int s,t;
    REP(i,M){
        cin >> s >> t;
        G[s].push_back(t);
    }
    tsort();
    for(list<int>::iterator it = out.begin(); it != out.end(); it++){
        cout << *it << endl;
    }
}


Measured memory_bytes: 4048
<?php

class Inputs
{
    public static function d()
    {
        fscanf(STDIN, '%d', $a);
        return $a;
    }
}

$a = Inputs::d();
$b = Inputs::d();
for ($i =1; $i <= 3; $i++) {
    if ($a !== $i && $b !== $i) {
        echo $i . PHP_EOL;
    }
}


Measured memory_bytes: 4728
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a;
    cin>>a;
    for(int i=0;i<100;i++)
    {
        if(pow(2,i)==a){cout<<pow(2,i)<<endl;return 0;}
        if(pow(2,i)>a){cout<<pow(2,i-1)<<endl;return 0;}
    }
    return 0;
}

Measured memory_bytes: 512
// Aizu 2281: Swap Cipher
// 2017.9.23 bal4u@uu

#include <stdio.h>

char msg[101];
int a[100], b[100];

// ?°??????? x ????????????k??????????????????????????????????????????
// ex: x = 'x', k = 3 ???????????? 'a' ?????????
char nPosChar(char x, int k)
{
	int p = x - 'a' + k;
	if (p >= 26) p %= 26;
	return p + 'a';
}

int main()
{
	int n, i;
	char *p, *q, x, y;

	while (scanf("%d", &n) && n > 0) {
		scanf("%s", msg);
		for (i = 0; i < n; i++) scanf("%d%d", a+i, b+i);

		// ??????????????????????????¨??????
		for (i = n-1; i >= 0; i--) {
			p = msg + a[i] - 1, q = msg + b[i] - 1;		// ??????????????????????????????
			x = nPosChar(*p, b[i]-a[i]);				// ???????????????????????????????????????
			y = nPosChar(*q, b[i]-a[i]);
			*p = y, *q = x;								// ??????????????§??????
		}

		puts(msg);
	}
	return 0;
}

Measured memory_bytes: 1748
h,w=gets.chomp.split.map(&:to_i)
w+=2
results=[w.times.map{"#"}.join.to_s]
h.times do
  results << "#" + gets.chomp + "#"
end
results << w.times.map{"#"}.join.to_s
results.each do |value|
  puts value
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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; }

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

bool cmp(pii a, pii b){
  return (a.second < b.second);
}

int main(){
  int n,m; cin >> n >> m;
  vector<pii> lr(m);
  rep(i,m) cin >> lr[i].first >> lr[i].second;

  sort(all(lr), cmp);

  //rep(i,m) cout << lr[i].first << " " << lr[i].second << endl;

  int right = 0, ans = 0;
  rep(i,m) {
    if(lr[i].first >= right){
      right = lr[i].second;
      ans++;
    }
  }

  cout << ans << endl;
}


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

void solve(){
    ll x;
    for(ll i = 0; i < 5; i++) {
        cin >> x;
        if(x == 0){
            cout << i+1 << endl;
            return;
        }
    }
}

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


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

main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long i,j,k,l,m,n,p,t;
char s[100];
while(cin>>s){
    if(s[0]<93)cout<<"A"<<endl;
    else cout<<"a"<<endl;
}
return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	int ans=1;
	for(int i=1;i<n;i++){
		if(i*i<=n){
			ans=max(ans,i*i);
		}else if(i*i>n){
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

S = range(N)
for i in S:
    S[i] = i + 1

res = []

for i in S:
    num = i
    count = 0

    while i%2 == 0:

        i = i/2
        count += 1

    res.append((count,num))


res.sort()

Anser = res[-1][1]

print Anser


Measured memory_bytes: 2568
#[allow(dead_code)]
fn is_whitespace(c: &char) -> bool {
    c.is_whitespace()
}

#[allow(dead_code)]
fn is_eol(c: &char) -> bool {
    ['\r', '\n'].contains(c)
}

#[allow(unused_macros)]
macro_rules! input {
    ($var:ident, $($r:tt)*) => {
        input_inner!{$var, $($r)*}
    };

    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        #[allow(unused_mut, unused_variables, bare_trait_objects)]
        let mut next = move |f: &Fn(&char)->bool| -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|f(&c))
                .take_while(|c|!f(&c))
                .collect()
        };
        input_inner!{next, $($r)*};
    };
}

#[allow(unused_macros)]
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)*}
    };

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; eol ]) => {
        $next(&is_eol).split(' ').map(|x| x.parse::<$t>().unwrap()).collect::<Vec<_>>()
    };

    ($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, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

    ($next:expr, parser) => {
        $next
    };

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

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};

#[allow(dead_code)]
struct Edge {
    from: usize,
    to: usize,
}

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;
#[allow(dead_code)]
const M: usize = 1_000_000_007;

fn main() {
    input! {
        k: usize
    }

    let mut q = std::collections::VecDeque::new();
    let mut c = 0;

    for i in 1..10 {
        q.push_back(i as usize);
    }

    while c + 1 < k {
        c += 1;
        let v = q.pop_front().unwrap();
        if v % 10 != 0 {
            q.push_back(v * 10 + v % 10 - 1);
        }
        q.push_back(10 * v + v % 10);
        if v % 10 != 9 {
            q.push_back(v * 10 + v % 10 + 1);
        }
    }
    println!("{}", q.pop_front().unwrap());
}


Measured memory_bytes: 6396
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353

using namespace std;
typedef pair<llint, llint> P;

llint n, s;
llint a[3005];
llint dp[3005][3005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> s;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	dp[0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= s; j++){
			dp[i+1][j] += dp[i][j]*2%mod, dp[i+1][j] %= mod;
			if(j+a[i+1] <= s) dp[i+1][j+a[i+1]] += dp[i][j], dp[i][j+a[i+1]] %= mod;
		}
	}
	cout << dp[n][s] << endl;
	
	return 0;
}

Measured memory_bytes: 74136
import fractions

def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    n = int(input())
    task = [tuple(map(int, input().split())) for _ in range(n)]
    tmp = 0
    task.sort(key=lambda x:x[1])
    for a, b in task:
        tmp += a
        if tmp > b:
            print("No")
            return
    print("Yes")

main()


Measured memory_bytes: 33972
;; -*- coding:utf-8 -*-

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter O3 '(optimize (speed 3) (safety 0) (debug 0)))
  (defparameter O2 '(optimize (speed 3) (safety 1))))


;; Hauptteil

(defmacro print-line (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))

(eval-when (:compile-toplevel :execute)
  (defparameter *maxnum* 100000))
(deftype unum nil '(integer 0 #.*maxnum*))

(defun make-eratosthenes (n)
  (declare #.O3
	   (unum n))
  (let ((max-idx (floor n 2))
	(arr (make-array (+ n 1) :element-type 'bit :initial-element 0)))
    (loop for factor from 3 to max-idx by 2 do
	 (loop for idx from (+ factor factor) to n by factor
	    do (setf (sbit arr idx) 1)))
    (loop for idx from 4 to n by 2
	 do (setf (sbit arr idx) 1))
    (setf (sbit arr 1) 1
	  (sbit arr 0) 1)
    arr))

(defparameter *erato-dict* (make-eratosthenes *maxnum*))

(declaim (inline like-2017-p))
(defun like-2017-p (n)
  (declare (unum n))
  (and (oddp n)
       (zerop (sbit *erato-dict* n))
       (zerop (sbit *erato-dict* (ash (1+ n) -1)))))

(defmacro split-and-bind (arg-lst string &body body)
  (let ((pos1 (gensym "POS"))
	(pos2 (gensym "POS"))
	(str-fixed (gensym "STR")))
    (labels ((make-bind (arg-lst &optional (init-pos1 t))
	       (if (null arg-lst)
		   `(progn ,@body)
		   `(let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
			   (,pos2 (position #\space ,str-fixed :start ,pos1 :test #'char=))
			   (,(car arg-lst) (parse-integer ,str-fixed :start ,pos1 :end ,pos2)))
		      ,(make-bind (cdr arg-lst) nil)))))
      `(let ((,str-fixed ,string))
	 ,(make-bind arg-lst)))))

(defun main ()
  (declare #.O3
   )
  (let* ((q (read))
	 (lefts (make-array q :element-type 'unum))
	 (rights (make-array q :element-type 'unum))
	 (cumul (make-array (1+ *maxnum*) :element-type 'unum)))
    (dotimes (idx q)
      (split-and-bind (l r) (the simple-string (read-line))
	(setf (aref lefts idx) l
	      (aref rights idx) r)))
    (loop for idx from 0 to *maxnum*
       for sum = 0 then (+ sum (if (like-2017-p idx) 1 0))
       do (setf (aref cumul idx) sum))
    (dotimes (idx q)
      (print-line
       (- (aref cumul (aref rights idx))
	  (aref cumul (- (aref lefts idx) 1)))))))


#-swank(main)


;; Für Test
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

(defun test ()
  (with-input-from-string (*standard-input* (delete #\return (get-clipbrd)))
    (main)))


;; Für Benchmark
(defparameter *file-path* *load-pathname*)
(defparameter *dat-path* (merge-pathnames "test.dat" *file-path*))

;; #+swank
;; (with-open-file (out *dat-path*
;; 		     :direction :output :if-exists :supersede)
;;   (print-line 100000 out)
;;   (dotimes (x 100000)
;;     (let* ((l (+ (* 2 (random 50000)) 1))
;; 	   (r (+ (* 2 (random 50000)) 1)))
;;       (when (> l r) (rotatef l r))
;;       (format out "~A ~A~%" l r)))
;;   )

(defun bench ()
  (let ((*standard-output* (make-broadcast-stream)))
    (with-open-file (*standard-input* *dat-path*)
      (time (main)))))


Measured memory_bytes: 64100
# -*- coding: utf-8 -*-
 
N = int(input())
a = list(map(int, input().split(" ")))
c = []
 
for i in a:
  count = 0
  while not(i % 2):
    i = int(i / 2)
    count += 1
  c.append(count)
print(min(c))

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;

#define MOD 998244353


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

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}
  
  

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> h(n);
    
    for(ll i = 0; i<n; i++){
        cin>>h[i];
    }
    if(n <= k){
        cout<< 0 <<endl;
        return 0;
    }
    sort(h.begin(),h.end(),greater<ll>());
    
    ll total = 0;
    for(ll i = 0; i<n-k; i++){
        total += h[i+k];
    }
    
    cout<< total << endl;
    return 0;
}





Measured memory_bytes: 1920
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;
                                                                                                     
ll MOD=1000000007;                                                                                     
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,k,c; cin>>n>>k>>c;
    string s; cin>>s;
    vector<int> dp_l(n,0),dp_r(n,0);
    int cur=0,last=-inf;
    rep(i,n){
        if(s[i]=='x'){
            dp_l[i]=cur; continue;
        }
        if(i-last>c){
            cur++; last=i;
        }
        dp_l[i]=cur;
    }
    cur=0,last=inf;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='x'){
            dp_r[i]=cur; continue;
        }
        if(last-i>c){
            cur++; last=i;
        }
        dp_r[i]=cur;
    }
    rep(i,n){
        if(s[i]=='x') continue;
        int t=0,l=0,r=i-1,ce;
        if(i==0) l=-c;
        else{
            while(l!=r){
                ce=(l+r)/2;
                if(dp_l[ce]==dp_l[i-1]) r=ce;
                else l=ce+1;
            }
            t+=dp_l[i-1];
        }
        if(i==n-1 && t<k){
            cout<<i+1<<endl; break;
        }
        if(l+c+1<n) t+=dp_r[max(l+c+1,i+1)];
        if(t==k-1){
            int T=0;
            if(i>0) T+=dp_l[i-1];
            T+=dp_r[i];
            if(T==k) cout<<i+1<<endl;
        }
    }
}

Measured memory_bytes: 5244
// Code by Denverjin.
#include <bits/stdc++.h>
using namespace std;

using ld = double;
using ll = long long;
using ull = unsigned long long;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;

const int SZ = 1 << 13;
char buff[SZ], *pos = buff + SZ - 1;
#define getchar() (++ pos == buff + SZ ? fread(pos = buff, 1, SZ, stdin), *pos : *pos)

inline ll read() {
	ll x = 0; int f = 1, c = getchar();
	for (;!isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x<<3) + (x<<1) + (c^48);
	return x * f;
}

int main() {
	int n = read(), k = read();
	puts(k > (n + 1) / 2 ? "NO" : "YES");
	return 0;
}


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

int main() {
  double Ans = 0;  // 回答：
  // string Ans = "Yes";  // 回答：
  double L; cin >> L; // 元の値

  cout << fixed << setprecision(7);
  Ans = ( L * L * L ) / 27 ;

  cout << Ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        String[] alphabet = {"a","b","c","d","e","f","g","h","i","j","k","l",
                "m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
        Stack<String> stack = new Stack<String>();

        while(N>26) {
            long remain = N%26;
            if(remain==0) {
                remain=26;
            }
            stack.add(alphabet[(int)(remain-1)]);
            N-=remain;
            N/=26;
        }
        long last_remain = N%26;
        if(last_remain == 0) {
            last_remain=26;
        }
        stack.add(alphabet[(int)(last_remain-1)]);

        while(!stack.isEmpty()) {
            System.out.print(stack.pop());
        }

	}

}

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

int main() {
  ll n,h; cin >> n >> h;
  vector<pair<ll, ll>> p(n);

  for(ll i=0;i<n;i++){
  cin >> p[i].first >> p[i].second;
    }

  sort(p.begin(), p.end());

  vector<ll> bx(n-1);
  rep(i,n-1)bx[i]=p[i].second;
  sort(bx.begin(),bx.end(),greater<ll>());

  ll amax=p[n-1].first; ll cnt=0; ll b=p[n-1].second;
  if(b>=h){
    cout << 1 << endl;
    return 0;
  }

  rep(i,n-1){
    if(bx[i]>=amax){
    h-=bx[i];
    cnt++;
     if(h<=0){
      cout << cnt << endl;
      return 0;
     }
     else if(h>0 && h<=b){
       cout << cnt+1 << endl;
       return 0;
     }
     }
    }



    while(h>b){
      h-=amax;
      cnt++;
    }
    if(h>0 && h<=b)cout << cnt+1 << endl;
    else cout << cnt << endl;

}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

// (a + (b - 1)) / b ceil

int main(){
    int n, k;
    cin >> n >> k;
    int i = k;
    vi p;
    while(i > 1){
        p.emplace_back(i);
        i = (i + 1) / 2;
    }
    p.emplace_back(1);
    reverse(ALL(p));
    long double ans = 0.0;
    rep(j, SZ(p)-1){
        ans += max(min(n-p[j]+1, p[j+1]-p[j]), 0) / pow(2, SZ(p)-1-j);
    }
    ans += max(n-k+1, 0);
    ans /= n;
    cout << setprecision(15) << fixed << ans << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
 
int m,a,b;
int p[205];
 
int main(){
  while(1){
    cin>>m>>a>>b;
    if(m==0&&a==0&&b==0)break;
    for(int i=1;i<=m;i++){
      cin>>p[i];
    }
    int maxm=0,id;
    for(int i=a;i<=b;i++){
      if(maxm<=p[i]-p[i+1]){
        maxm=p[i]-p[i+1];
        id=i;
      }
    }
    cout<<id<<endl;
  }
  return 0;
}

Measured memory_bytes: 3052
#include <iostream>
using namespace std;
int main()
{
	int w, h, x, y;
	cin >> w >> h >> x >> y;
	double s = (double)w * h / 2;
	printf("%.10f ",s);
	if (w == x * 2 && h == y * 2) cout << 1;
	else cout << 0;
	return 0;
}	

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    int N, C;
    cin >> N >> C;
    vector<vector<pair<int,int>>> chan(C);
    rep(i, N){
        i64 s, t, c;
        cin >> s >> t >> c;
        s *= 2,t *= 2; c--;
        chan[c].emplace_back(make_pair(s,t));
    } 

    const int t_max = 2*100000+2;
    vector<int> time_table(t_max, 0);
    for(int c = 0; c < C; c++){
        vector<int> table(t_max, 0);
        for(auto& p : chan[c]){
            table[p.first - 1]++;
            table[p.second + 1]--;
        }
        for(int i = 1; i < t_max; i++) table[i] += table[i-1];
        for(int left = 0; left < t_max; left++){
            if(table[left] == 0) continue;

            int right = left;
            while(right < t_max && table[right] > 0) right++;
            time_table[left]++;
            time_table[right]--;
            left = right - 1;
        }
    }

    for(int i = 1; i < t_max; i++) time_table[i] += time_table[i-1];
    cout << *max_element(all(time_table)) << endl;
}

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

const int MAX = 1e5 + 5;

#define dbg(a) cout << "-> " << __LINE__ << ": " << #a << " = " << a << endl

int main() {
    int n, k;
	scanf("%d %d", &n, &k);
	vector<int> s(n + 1, 0);
	unordered_map<int, int> mp;
	++mp[0];
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		s[i] = (s[i - 1] + a) % k;
		if (i - k >= 0) {
			--mp[(s[i - k] - i % k + k) % k];
		}
		ans += mp[(s[i] - i % k + k) % k];
		++mp[(s[i] - i % k + k) % k];
	}
	printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 9288
package main

import (
	"fmt"
	"math"
)

func main(){
	var N,A int
	fmt.Scan(&N)

	r := 0
	for i:=0;i<N;i++{
		fmt.Scan(&A)
		if i==0{
			r=A
		}

		if A%2!=0{
			r = 0
			break
		}else{
			c:=0
			for x:=1;x<A;x++{
				if A%int((math.Exp2(float64(x))))!=0{
					break
				}
				c=x
			}
			//fmt.Println("A, c :",A,c)
			if r>c{
				r=c
			}
		}
	}
	fmt.Print(r)
}

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

int main(){
    
    string s;
    cin>>s;
    ll c=0;
    for(int i=0;i<s.length();i++)
        c+='0'-s[i];
    
    if(c%9==0) cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 3724
#include <stdio.h>
long long lcm(long long a, long long b)
{
	long long remain;
	long long ta = a, tb = b;
	while (1)
	{
		remain = ta % tb;
		if (!remain) break;
		ta = tb, tb = remain;
	}
	return a * b / tb;
}
int main(void)
{
	long long a, b;
	if (scanf("%lld %lld", &a, &b) == 2) printf("%lld", lcm(a, b));
}

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

int main(){
   int a,b,n,count=0;cin>>a>>b>>n;
   int m=min(a,b);
   vector<int> v(b);
   rep1(i,m+1){
       if(a%i==0 && b%i==0){
           count++;
           v[count]=i;
       }
   }
   cout<<v[count-n+1]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

int a[5];

int main() {
	inc(i, 5) { cin >> a[i]; }
	
	int sum = 0, ma = 0;
	inc(i, 5) {
		sum += ce(a[i], 10) * 10;
		setmax(ma, (10 - (a[i] % 10)) % 10);
	}
	
	cout << sum - ma << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl


signed main(void){
    string S,T;
    int Q;
    cin >> S;
    cin >> Q;
    int mode=0;
    REP(i,Q){
        int com,F;
        char C;
        cin >> com;
        if(com==1){
            mode=1-mode;
        }else{
            cin >> F >> C;
            if((F==1 && mode==0)||(F==2 && mode==1)){
                T.push_back(C);
            }else{
                S.push_back(C);
            }
        }
    }
    if(mode==0){
        reverse(T.begin(),T.end());
        cout << T << S << endl;
    }else{
        reverse(S.begin(),S.end());
        cout << S << T << endl;
    }
    return 0;
}



Measured memory_bytes: 960
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

vint d;
vpair edges[200005];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P>> que;
    d[s] = 0;
    que.push(P(0, s));

    while (que.size()) {
        P p = que.top();
        que.pop();
        int v = p.se;
        if (d[v] < p.fi) continue;
        for (auto e : edges[v]) {
            if (d[e.fi] > d[v] + e.se) {
                d[e.fi] = d[v] + e.se;
                que.push(P(d[e.fi], e.fi));
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edges[a].emplace_back(b, 1);
        edges[b].emplace_back(a, 1);
    }

    d.resize(n, INF);
    dijkstra(0);

    if (d[n-1] <= 2) puts("POSSIBLE");
    else puts("IMPOSSIBLE");
    return 0;
}

Measured memory_bytes: 15080
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

int main() {
    int n,a,b,c,d;
    string s;
    cin >> n >> a >> b >> c >> d;
    a--,b--,c--,d--;
    cin >> s;
    for (int i = a; i < c-1; ++i) {
        if(s[i] == '#' && s[i+1] == '#'){
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = b; i < d-1; ++i) {
        if(s[i] == '#' && s[i+1] == '#'){
            cout << "No" << endl;
            return 0;
        }
    }

    if(c < d){
        cout << "Yes" << endl;
        return 0;
    }
    else{
        for (int i = b; i <= d; ++i) {
            if(s[i-1] == '.' && s[i] == '.' && s[i+1] == '.'){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 640
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def failure(): Unit = {
    out.println(-1)
  }

  def solve(): Unit = {
    val S = ns()
    val N = S.length
    val A = Array.ofDim[Boolean](N + 1)
    rep(N) { i =>
      A(i + 1) = S(i) == '1'
    }

    rep(N, 1) { i =>
      val j = N - i
      if (A(i) != A(j)) {
        failure()
        return
      }
    }

    val ms = A.lastIndexOf(true, N / 2)
    if (ms == -1) {
      failure()
      return
    }

    case class Edge(v: Int, u: Int)
    def mkTree(parent: Int, nodeCnt: Int, tree: List[Edge]): Option[List[Edge]] = {
      val top = parent + 1
      val newTree = Edge(parent, top) :: tree
      if (nodeCnt == 1) Some(newTree)
      else {
        val next = A.lastIndexOf(true, nodeCnt - 1)
        if (next == -1) None
        else {
          mkTree(top, next, add1(newTree, nodeCnt - next - 1, top, top + next + 1))
        }
      }
    }

    def add1(tree: List[Edge], cnt: Int, rt: Int, from: Int): List[Edge] = {
      (from until from + cnt).foldLeft(tree){ (acc, i) =>
        Edge(rt, i) :: acc
      }
    }

    mkTree(1, ms, Nil) match {
      case None => failure()
      case Some(t) =>
        add1(t, N - ms - 1, 1, 1 + ms + 1) foreach { e =>
          out.println(s"${e.v} ${e.u}")
        }
    }
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int): Array[Int] = map(n)(_ => ni())
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def rep(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def rep_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  def sumL(as: Array[Int]): Long = {
    var s = 0L
    rep(as.length)(i => s += as(i))
    s
  }
}


Measured memory_bytes: 56120
object Main extends App {

  val Array(r, d, x2000) = scala.io.StdIn.readLine().split(" ").map(_.toInt)


  def solve() =  {
    val arr = Array.fill(10)(0)
    for(i <- 0 to 9) {
      if(i == 0) arr(i) = r * x2000 - d
      else arr(i) = r * arr(i-1) - d
    }
    arr.mkString("\n")
  }

  println(solve)

}


Measured memory_bytes: 27208
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
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; }
const ll INF = 1LL << 60;
int main(){
    int k;
    string s;
    cin >> k >> s;
    if(s.size()<=k) {
        cout << s << endl;
        return 0;
    }
    rep(i,k){
        cout << s[i];
    }
    cout << "..." << endl;
    return 0;
}

Measured memory_bytes: 3572
#include<iostream>
#include<fstream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<complex>
using namespace std;

const int MAX_N = 100000;

struct BIT{
    int bit[MAX_N + 1];
    int n;

    BIT(const int n): n(n){
        for (int i=0;i<MAX_N;i++) bit[i] = 0;
    }

    void printBIT(){
        for (int i=0;i<n;i++){
            cout << bit[i] << " ";
        }
        cout << endl;
    }

    int sum(int i){
        int S = 0;
        while(i > 0){
            S += bit[i];
            i -= i & -i;
        }
        return S;
    }

    void add(int i, int x){
        while(i <= n){
            bit[i] += x;
            i += i & -i;
        }
    }

};

int main(){
    int n, q;
    cin >> n >> q;
    BIT bit(n);
    int c, x, y;
    for (int i=0;i<q;i++){
        cin >> c >> x >> y ;
        if(c == 0){
            bit.add(x, y);
        }else{
            cout << bit.sum(y) - bit.sum(x-1) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3460