akhauriyash/Code-Regression huggingface dataset:
use proconio::input;
use std::collections::BTreeMap;

fn lower_bound(map: &BTreeMap<usize, usize>, target: usize) -> usize {
    *map.range(target..).next().unwrap().clone().1
}

fn main() {
    input! {
        n: usize,
        q: usize,
        query: [(usize, usize); q],
    }

    let mut h_map = BTreeMap::new();
    let mut w_map = BTreeMap::new();

    h_map.insert(n-1, n);
    w_map.insert(n-1, n);

    let mut ans = 0;

    for &(c, x) in query.iter() {
        if c == 1 {
            let t = lower_bound(&h_map, x);
            if t <= 1 {
                continue;
            }
            ans += t-2;
            if let Some(&y) = w_map.get(&(t-1)) {
                *w_map.entry(t-1).or_default() = y.min(x);
            }
            else {
                *w_map.entry(t-1).or_default() = x;
            }
        }
        else {
            let t = lower_bound(&w_map, x);
            if t <= 1 {
                continue;
            }
            ans += t-2;
            if let Some(&y) = h_map.get(&(t-1)) {
                *h_map.entry(t-1).or_default() = y.min(x);
            }
            else {
                *h_map.entry(t-1).or_default() = x;
            }
        }
        // dbg!(c, x, ans);
        // dbg!(h_map.clone());
        // dbg!(w_map.clone());

    }

    println!("{}", (n-2)*(n-2) - ans);
}


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

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

const int MAX_N = 6100000;
ll MOD = 998244353;
ll inv[MAX_N + 10];
ll fac[MAX_N + 10], facInv[MAX_N + 10];
class MATH{
public:
	MATH(){
		inverse();
		factroial();
	}
	ll nCk(ll n, ll k){// n! / k!*(n-k)!
		if(k < 0 || k > n) return 0;
		ll ret = fac[n];
		(ret *= facInv[k]) %= MOD;
		(ret *= facInv[n - k]) %= MOD;
		return ret;
	}
	ll nHk(ll n, ll k){// nHk = n+k-1 C k = (n+k-1)! / k! * (n-1)!
		if(n == 0 && k == 0) return 1;
		ll ret = fac[n + k - 1];
		(ret *= facInv[k]) %= MOD;
		(ret *= facInv[n - 1]) %= MOD;
		return ret;
	}
	ll nPk(ll n, ll k){//nPk = n! / (n-k)!
		if(k < 0 || k > n) return 0;
		ll ret = fac[n];
		(ret *= facInv[n - k]) %= MOD;
		return ret;
	}
private:
	void inverse(void){
		inv[1] = 1;
		for (int i = 2; i <= MAX_N; ++i){
			// inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
			inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
		}
	}
	void factroial(void){
		fac[0] = facInv[0] = 1;
		for (int i = 1; i <= MAX_N; ++i){
			fac[i] = (fac[i - 1] * i) % MOD;
			facInv[i] = (facInv[i - 1] * inv[i]) % MOD;
		}
	}
};

int main(void) {
	ll n, a, b, k;
	cin >> n >> a >> b >> k;
	MATH ma;

	ll ret = 0;
	for (ll i = 0; i <= n; ++i) {
		ll red = i;
		if ((k - red * a) % b != 0) continue;
		ll blue = (k - red * a) / b;
		if (blue > n) continue;
		ll ans = ma.nCk(n, red) * ma.nCk(n, blue) % MOD;
		(ret += ans) %= MOD;
	}
	printf("%lld\n", ret);
	return 0;
}

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

using namespace std;

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

int main() {
	int n;
	scanf("%d", &n);
	vector<int> v;
	
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		a--;
		v.push_back(a);
	}
	
	sort(v.begin(), v.end());
	int index = 0;
	int cnt[n];
	for (int i = 0; i < n; i++) {
		cnt[i] = 0;
	}
	for (int i = 0; i < n - 1; i++) {
		if (v[i] == v[i + 1]) {
			cnt[index]++;
		} else {
			cnt[index]++;
			index++;
		}
	}
	cnt[index]++;

	sort(cnt, cnt + index + 1, greater<int>());
	
	ll ans = 0;
	for (int i = 0; i < index; i++) {
		while(cnt[i] > 1) {
			for (int j = i + 1; j <= index; j++) {
				if (cnt[j] > 1) {
					int dif = min(cnt[i] - 1, cnt[j] - 1);
					cnt[i] -= dif;
					cnt[j] -= dif;
					break;
				}
				if (j == index) {
					cnt[i]--;
					cnt[index]--;
					index--;
					break;
				}
			}
		}
	}
	for (int i = 0; i <= index; i++) {
		if (cnt[i] > 1) {
			cnt[i] %= 2;
		}
	}
	for (int i = 0; i <= index; i++) {
		if (cnt[i] == 1) {
			ans++;
		}
	}
	
	cout << ans << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 1144
import java.util.Scanner;

//日立製作所 社会システム事業部 プログラミングコンテスト2020
//B - Nice Shopping
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		int M = Integer.parseInt(sc.next());
		int[] a = new int[A];
		for (int i = 0; i < A; i++) {
			a[i] = Integer.parseInt(sc.next());
		}
		int[] b = new int[B];
		for (int i = 0; i < B; i++) {
			b[i] = Integer.parseInt(sc.next());
		}
		int[] x = new int[M];
		int[] y = new int[M];
		int[] c = new int[M];
		for (int i = 0; i < M; i++) {
			x[i] = Integer.parseInt(sc.next());
			y[i] = Integer.parseInt(sc.next());
			c[i] = Integer.parseInt(sc.next());
		}
		sc.close();

		int minA = 100000;
		for (int i = 0; i < A; i++) {
			minA = Math.min(a[i], minA);
		}
		int minB = 100000;
		for (int i = 0; i < B; i++) {
			minB = Math.min(b[i], minB);
		}
		int ans = minA + minB;
		for (int i = 0; i < M; i++) {
			ans = Math.min(ans, a[x[i]-1] + b[y[i]-1] - c[i]);
		}

		System.out.print(ans);
	}

}


Measured memory_bytes: 68512
def B():
    n = int(raw_input())
    s = list(raw_input())
    c = 0
    for i in range(0,len(s)-2):
        if str(s[i]) == "A":
            if str(s[i+1]) == "B":
                if str(s[i+2]) == "C":
                    c = c + 1
    print c

if __name__ == '__main__':
    B()

Measured memory_bytes: 2568
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
typedef long long ll;
typedef vector<int> vi;
typedef unsigned long ul;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef set<int> si;
typedef multiset<int> mi;
 
const ll INF = 1e18;
const int MOD = 1e9+7;
 
int main() {
	
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	//ofstream cout ("fileName.txt");
	//ifstream cin ("fileName.txt");
	
	int X, Y;
	cin >> X >> Y;
 	
	int numerator = 4*X-Y;
	
	if(numerator>=0 && numerator%2==0 && numerator/2<=X) cout << "Yes\n";
	else cout << "No\n";
 	
	return 0;
}


Measured memory_bytes: 3612
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int s[100000],t[100000],c[100000]; 
int sm[200002]; 
int tt[200002]; 
/*
typedef struct  a {
  int num;
  int count;
};
*/
int main(void){
  int N, K;
  cin >> N >> K;
  int A[N], count[N+1]={};
  int unique_num =0;
  rep(i, N) {
    cin >> A[i];
    if (count[A[i]] == 0) unique_num++;
    count[A[i]]++;
  }
 
  int sabun = unique_num - K;
  priority_queue<int, vector<int>, greater<int>> a;
  if (sabun > 0){
    rep(i, N+1){
      if (count[i] != 0) a.push(count[i]);
    }
    int kosuu = sabun;
    int ans = 0;
    while(!a.empty() && kosuu>0){
      ans += a.top();
      a.pop();
      kosuu--;
    }
    
    cout << ans << endl;
  } else {
    cout << 0 << endl;
  }
  
}


Measured memory_bytes: 2936
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

ll N, K;
vector<ll> As;
vector<ll> neg;
vector<ll> pos;
vector<ll> zero;

//bool check(ll mid) {
//    ll s = 0;  // mid以下の数
//    REP(i, SIZE(As)) {
//        auto a = As[i];
//        auto it = upper_bound(As.begin(), As.end(), mid / a);
//        auto tmp = it - As.begin() - 1;
//        s += tmp;
//    }
//    return s >= K;
//}

ll check_neg(ll mid) {

    ll s = 0;
    REP(i, SIZE(neg)) {
        auto n = abs(neg[i]);
        auto it = lower_bound(pos.begin(), pos.end(), (abs(mid) + (n - 1)) / n);
        auto tmp = pos.end() - it;
        s += tmp;
    }

    return s;
}

ll solve_neg(ll k) {
    ll ng = -2e18;
    ll ok = 0;

    while (ok - ng > 1) {
        ll mid = (ng + ok) / 2;
        if (check_neg(mid) >= k) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

ll check_pos_sub(vector<ll>& arr, ll mid) {
    ll s = 0;
    REP(i, SIZE(arr)) {
        auto n = arr[i];
        auto it = upper_bound(arr.begin(), arr.end(), mid / n);
        ll tmp = (it - arr.begin());
        tmp -= (i + 1);
        s += max(0LL, tmp);
    }
    return s;
}

ll check_pos(ll mid) {

    ll s = 0;

    // neg同士
    s += check_pos_sub(neg, mid);
    // pos同士
    s += check_pos_sub(pos, mid);

    return s;
}

ll solve_pos(ll k) {
    ll ng = 0;
    ll ok = 2e18;

    while (ok - ng > 1) {
        ll mid = (ng + ok) / 2;
        if (check_pos(mid) >= k) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

int main(void)
{
    cin.sync_with_stdio(false);
    cin >> N >> K;
    As.resize(N);
    REP(n, N) {
        cin >> As[n];
        if (As[n] < 0) {
            neg.pb(abs(As[n]));
        }
        else if (As[n] > 0) {
            pos.pb(As[n]);
        }
        else {
            zero.pb(0);
        }
    }
    sort(ALL(As));
    sort(ALL(neg));
    sort(ALL(pos));

    ll pos_size = SIZE(pos);
    ll neg_size = SIZE(neg);
    ll zero_size = SIZE(zero);

    //ll pos_num =
    //    pos_size * (pos_size - 1) / 2
    //    + neg_size * (neg_size - 1) / 2;
    ll neg_num =
        pos_size * neg_size;
    ll zero_num = zero_size * (pos_size + neg_size)
        + zero_size * (zero_size - 1) / 2;

    if (K <= neg_num) {
        cout << solve_neg(K) << endl;
    }
    else if (K <= neg_num + zero_num) {
        cout << 0 << endl;
    }
    else {
         cout << solve_pos(K - neg_num - zero_num) << endl;
    }
    return 0;

}


Measured memory_bytes: 4084
LAW = 10 ** 9 + 7

N, M, K = map(int, input().split(" "))

def calc_rev(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

def calc_dsum(n, m):
	dx = 0
	for i in range(1, n):
		dx += i * (n - i)
	
	dy = 0
	for i in range(1, m):
		dy += i * (m - i)
	dx *= m * m
	dy *= n * n
	
	return dx + dy

def calc_csum(n, k):
	csum = 1
	for i in range(k):
		csum = (csum * (n - i)) % LAW
	for i in range(1, k + 1):
		csum = (csum * calc_rev(i, LAW)) % LAW
	
#	print(csum)
	
	csum = (csum * k * (k - 1)) % LAW
	csum = (csum * calc_rev(n * (n - 1), LAW)) % LAW
	
	return csum

def c(n, m, k):
	
	return (calc_csum(n * m, k) * calc_dsum(n, m)) % LAW

print(c(N, M, K))


Measured memory_bytes: 3064
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto x = readln.chomp.split.to!(int[]);
  if (x[0]+x[1]<x[2] || x[0] > x[2]) {
    writeln("NO");
  } else {
    writeln("YES");
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll a,b; cin >> a >> b;
  cout << (a+b-3)/(a-1) << endl;
}

Measured memory_bytes: 256
from statistics import median
N = int(input())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
#AB = sorted(AB, key=lambda x: x[0])
#print(AB)
cenA = median(A)
cenB = median(B)


if N % 2 == 1:
    print(int(cenB - cenA + 1))

elif N % 2 == 0:
    print(int((cenB - cenA)*2 + 1))
    
else:
    print('RE')

Measured memory_bytes: 28668
from collections import Counter
n = int(input())
s = [[0]*10 for _ in range(n)]
ans = 0
for i in range(n):
    str_s = input()
    for j in range(10):
        s[i][j] = str_s[j]

dict_s = {}
for i in range(n):
    s[i].sort()
    si = "".join(s[i])
    dict_s.setdefault(si, 0)
    dict_s[si] += 1

for x in dict_s.values():
    ans += x*(x-1)//2
print(ans)

Measured memory_bytes: 135376
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
#include<map>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define mod 1000000007
//#define mod 998244353

//解説
//abc117_d
int N,K;
int A[100005];
int keta[100005][50];
int K_keta[50];
signed main(){
    scanf("%lld %lld",&N,&K);
    int now=K;int K_cnt=0;
    while(now>0){
        K_keta[K_cnt]=now%2;
        now/=2;K_cnt++;
    }
    int A_cnt=0;
    rep(i,N){
        scanf("%lld",&A[i]);
        int now=A[i];
        int cnt=0;
        while(now>0){
            keta[i][cnt]=now%2;
            now/=2;cnt++;
        }
        A_cnt=max(cnt,A_cnt);
    }
    int pow2[50];
    pow2[0]=1;
    rep(i,45)if(i>0)pow2[i]=pow2[i-1]*2;
    int ans=0;
    for(int i=max(K_cnt,A_cnt);i>-1;i--){
        int cnt1=0;
        rep(j,N)if(keta[j][i])cnt1++;
        if(pow2[i]<=K&&cnt1*2<N){
            K-=pow2[i];
            ans+=pow2[i]*(N-cnt1);
        }else{
            ans+=pow2[i]*cnt1;
        }
    }
    printf("%lld\n",ans);
}

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

#define len length()
#define sz size()
#define rep(i, n) for(int i = 0; i < n; i++)
#define sort(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define veci(a, n) vector<int> a(n)
#define vecs(a, n) vector<string> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)

int psnsum(int n){
    int N=n;
    string S;
    S = to_string(N);
    int ans=0;
    rep(i, S.len) ans += S.at(i) - '0';
    return ans;
}

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    int ans=0;

    for(int i = 1; i <= N; i++){
        if((A <= psnsum(i)) && (psnsum(i) <= B)) ans += i;
    }

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

Measured memory_bytes: 256
#![allow(unused)]

use std::{cmp, collections, fmt, io, iter, ops, str};
use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($fmt: expr) => { eprintln!($fmt) };
    ($fmt: expr, $($args: tt)*) => { eprintln!($fmt, $($args)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($fmt: expr) => {};
    ($fmt: expr, $($args: tt)*) => {};
}

macro_rules! vmax {
    ($x: expr, $y: expr) => { cmp::max($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::max($x, vmax!($($args),*)) };
}

macro_rules! vmin {
    ($x: expr, $y: expr) => { cmp::min($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::min($x, vmin!($($args),*)) };
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if buf.len() > 0 {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn main() {
    let month = parse_word::<i32>();
    let day = parse_word::<i32>();

    let ans = month + if day < month { -1 } else { 0 };
    println!("{}", ans);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        //
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
string s1,s2;

int main(){
	cin>>s1>>s2;
	int i;
	for(i=0;s1[i]!=0;++i){
		if(s1[i]!=s2[i]){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	
	
	
	return 0;
}

Measured memory_bytes: 3636
N, M = map(int, input().split())
H = list(map(int, input().split()))
x = [1] * N

for i in range(M):
  A, B = map(int, input().split())
  if H[A-1] <= H[B-1]:
    x[A-1] = 0
  if H[A-1] >= H[B-1]:
    x[B-1] = 0
print(x.count(1))

Measured memory_bytes: 19980
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
char a[200], b[200], c[200];

int main(){
	int n; cin >> n;
	scanf("%s %s",a+1,b+1);
	int ca = 0, cb = 0;
	for(int i = 1; i <= 2*n; i++){
		if(i % 2) c[i] = a[++ca];
		else c[i] = b[++cb];
	}
	printf("%s",c+1);
}

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

using namespace std;

#define ll long long
#define mod 1e9 + 7
#define mx 1000000000
#define endl '\n'

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    deque<int> d(n);
    for(int i = 0;i<n;i++){
        cin>>d[i];
    }
    while(d.size() != 1){
        sort(d.begin(),d.end());
        for(int i = 1;i<d.size();i++){
            d[i] = d[i] % d[0];
        }
        sort(d.begin(),d.end());
        while(d[0] == 0){
            d.pop_front();
        }
    }
    cout<<d[0];
    return 0;
}



Measured memory_bytes: 640
k = int(input())
a, b = map(int, input().split())

if k == 1:
    print('OK')
    exit()

if k > b:
    print('NG')
    exit()

for i in range(a, b + 1):
    if i % k == 0:
        print('OK')
        exit()

print('NG')


Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back 
#define pf push_front 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()
typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;


main()
{
  int n, m;
  while( cin >> n >> m, !(n == 0 && m == 0) ) {
    vector<Pii> v;
    Rep(i, m) v.pb(Pii(0, -i));
    Rep(i, n) Rep(j, m) {
      int a;
      cin >> a;
      v[j].fr += a;
    }

    sort(All(v), greater<Pii>() );
    Rep(i, m-1) cout << -v[i].sc+1 << " ";
    cout << -v[m-1].sc+1 << endl;
  }
  
}

Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    while(cin>>n>>m){
        n%=500;
        if(n<=m)
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
return 0;}


Measured memory_bytes: 256
#include<stdio.h>
#define N 100000
typedef struct rand {
  char c[10];
  int process;
}A;
int head=0,tail=0,n;
void enqueue(A);
A dequeue(void);
A r[N];
int main(){
  int i,q,sum=0,h;
  A s;
  scanf("%d%d",&n,&q);
  for(i=1;i<=n;i++){
    scanf("%s",r[i].c);
    scanf("%d",&r[i].process);
  }
  head=1;
  tail=n+1;
  while(head!=tail){
    s=dequeue();
    h=s.process;
    if((h-q)<=0){
      sum+=s.process;
      printf("%s %d\n",s.c,sum);
    }
    else if((h-q)>0){
      s.process-=q;
      enqueue(s);
      sum+=q;
    }
  }
  return 0;
}

void enqueue(A x){
  r[tail]=x;
  tail=(tail+1)%N;
}
A dequeue(){
  A x=r[head];
  head=(head+1)%N;
  return x;
}



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

typedef complex<double> CMP;

void dft(vector<CMP>& f, int n, bool inverse){
    if(n==1) return;
    const double PI = acos(-1);
 
    vector<CMP> f0, f1;
    for(int i=0; i<n/2; i++){
        f0.push_back(f[2*i]);
        f1.push_back(f[2*i+1]);
    }
 
    dft(f0, n/2, inverse);
    dft(f1, n/2, inverse);
 
    CMP zeta, pow_zeta = 1.0;
    if(inverse){
        zeta = cos(2*PI/n) + sin(2*PI/n) * 1i;
    }else{
        zeta = cos(2*PI/n) - sin(2*PI/n) * 1i;
    }
    for(int i=0; i<n; i++){
        f[i] = f0[i%(n/2)] + pow_zeta * f1[i%(n/2)];
        pow_zeta *= zeta;
    }
}
 
vector<int64_t> convolution(const vector<int>& ff, const vector<int>& gg){
    int fsz = ff.size(), gsz = gg.size();
    vector<CMP> f, g;
    for(int i=0; i<fsz; i++) f.push_back(ff[i]);
    for(int i=0; i<gsz; i++) g.push_back(gg[i]);
    int n = 1;
    while(n <= fsz+gsz) n <<= 1;
	f.resize(n);
	g.resize(n);
    dft(f, n, false);
    dft(g, n, false);
 
    vector<CMP> h(n);
    for(int i=0; i<n; i++) h[i] = f[i] * g[i];
    dft(h, n, true);
 
    vector<int64_t> ret(fsz+gsz-1);
    for(int i=0; i<fsz+gsz-1; i++) ret[i] = round(h[i].real()/n);
    return ret;
}

int main(){
    int N, M, K, L;
    cin >> N >> M >> K >> L;
    vector<int> A(M*M), B(M*M);
    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        for(int j=0; j<N; j++) if(s[j] == 'X') A[i*M+j]++;
    }
    int x = 0, y = 0;
    string S;
    cin >> S;
    for(char c : S){
        if(c == 'U') x--;
        if(c == 'D') x++;
        if(c == 'L') y--;
        if(c == 'R') y++;
        B[x*M+y]++;
    }
    auto V = convolution(A, B);
    int ans = 0;
    for(int i=0; i<M*M; i++) if(V[i] >= K) ans++;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 46432
import javax.print.attribute.HashAttributeSet;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static int[] A;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = sc.nextIntArray(N);

        System.out.println(solve());
    }

    static long solve() {
        long ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        cnt.put(0, 1);
        int r = 0;
        for (int i = 0; i < N; i++) {
            r = (r + A[i]) % M;

            if( cnt.containsKey(r) ) {
                int c = cnt.get(r);
                ans += c;
                cnt.put(r, c+1);

            } else {
                cnt.put(r, 1);
            }
        }

        return ans;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

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

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


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

int main(){

    int N,P;
    cin >> N >> P;

    int m = 0;
    for(int i = 0; i < N;i++){
        int A;cin >> A;
        if(A % 2 == 1)++m;
    }
    if(m==0)cout << (P == 0 ? (1LL<<N):0) << endl;
    else cout << (1LL << (N-1)) << endl;


}



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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define pb push_back

using namespace std;
using ll=long long;
using pii= pair<int, int>;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}

vector<vector<int>> G;
vector<array<ll,2>> dp;
const int mod=1e9+7;
void dfs(int u,int fa){
    for(auto to:G[u]){
        if(to==fa) continue;
        dfs(to,u);
        (dp[u][0]*=(dp[to][0]+dp[to][1])%mod)%=mod;
        (dp[u][1]*=dp[to][0])%=mod;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    if(n==1) return cout<<2,0;
    G.resize(n+1);
    dp.resize(n+1,{1,1});
    forn(i,n-1){
        int x,y;
        cin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }
    for(int i=2;i<=n;i++)
        if(sz(G[i])==1) dp[i][1]=dp[i][0]=1;
    dfs(1,0);
    cout<<(dp[1][0]+dp[1][1])%mod;
    return 0;
}



Measured memory_bytes: 17188
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main() {

  long long n, r = 0, w = 0, ans = 0;
  cin >> n;
  string l;
  cin >> l;
  for(int i = 0;i < n;i++){
    r += (l[i] == 'R');
    w += (l[i] == 'W');
  }
  for(int i = 0;i < r;i++){
    ans += (l[i] == 'W');
  }
  for(int i = r;i < r + w;i++){
    ans += (l[i] == 'R');
  }
  cout << (ans / 2) + ans % 2;
  return 0;
}


Measured memory_bytes: 3732
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define MP make_pair
#define PB push_back
typedef long double ld;
typedef long long ll;

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

int main(){
    ll n,m;
    cin >> n >> m;
    vector<ll>a(n);
    rep(i,n)cin >> a[i];
    vector<ld>p(n);
    rep(i,n){
        int tmp;
        cin >> tmp;
        p[i] = (ld)tmp/(ld)100.0;
    }
    vector<ld> pp(1<<n,(ld)1.0);
    vector<int> s(1<<n);
    vector<ld> dp(n+1);
    dp[0] = (ld)0.0;
    rep(bit,1<<n){
        rep(i,n){
            if((bit>>i)&1){
                pp[bit] *= p[i];
                s[bit]++;
            }else{
                pp[bit] *=((ld)1.0-p[i]);
            }
        }
    }

    for(int i=1;i<=n;i++){
        dp[i] = ((ld)1.0-p[i-1])*dp[i-1];
        
        ld tmp= dp[i-1];
        tmp += (ld)(m/a[i-1]);
        rep(bit,1<<(i-1)){
            if(bit==0)continue;
            ll x = a[i-1];
            bool flag = 0;
            rep(j,i-1){
                if((bit>>j)&1){
                    ll y = gcd(x,a[j]);
                    if((ld)x/(ld)y>(ld)(m+100000)/a[j]){
                        flag = 1;
                        break;
                    }else{
                        x = x/y;
                        x *= a[j];
                    } 
                }
            }
            if(flag)continue;
            ld hoge = (ld)(m/x);
            ld sss = 1.0;
            for(int k = 0;k<i-1;k++){
                if(bit>>k&1){
                    sss *= p[k];
                }
            }
            if(s[bit]%2==0){
                
                tmp += sss*hoge;
            }else{
                tmp -= sss*hoge;
            }
        }
        dp[i] += tmp*p[i-1];
    } 
    cout << fixed << setprecision(15) <<  dp[n] << endl;
    return 0;
}


Measured memory_bytes: 23424
import  math

A, B = [int(x) for x in input().split()]


def prime_factorization(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

C = math.gcd(A, B)




print(len(set(prime_factorization(C))) + 1)



Measured memory_bytes: 9136
#include <stdio.h>

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

Measured memory_bytes: 580
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <set>
#include <map>

int64_t A, B, C, K;

int main(){
  scanf("%lld %lld %lld %lld", &A, &B, &C, &K);
  printf("%d\n", (K & 1) ? (B - A) : (A - B));
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int i, j, N;
    cin>>N;
    vector<int> as(N);
    rep(i, N) cin>>as[i];

    int cnt = 0;
    rep(i, N) {
        int minj = i;
        for(int j = i + 1; j < N; ++j) {
            if (as[j] < as[minj]) {
                minj = j;
            }
        }
        if (minj != i) {
            swap(as[i], as[minj]);
            cnt++;
        }
    }

    rep(i, N - 1) cout<<as[i]<<" ";
    cout<<as[N - 1]<<endl;
    cout<<cnt<<endl;
}


Measured memory_bytes: 3136
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    double a,b;
    cin >> a >> b;
    double c;
    c = (a+b)/2;
    if(c==floor(c)) cout << int(c) << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a, b; cin >> a >> b;
	string s;cin >> s;
	for(int i = 1; i <= a + b + 1; ++i){
		if(i == a + 1){
			if(s[i - 1] != '-'){
				cout << "No\n";
				return 0;
			}
		}else{
			if(!('0' <= s[i - 1] && s[i - 1] <= '9')){
				cout << "No\n";
				return 0;
			}
		}
	}
	cout << "Yes\n";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(inti=a;i<=b;i++)

#define MOD 1000000007
typedef long long int ll;
typedef vector<int>vi;
typedef pair<int,int>pi;


int main(){
string s ;
cin>>s;
if(s[s.size()-1]=='s')
    cout<<s<<"es"<<endl;
else
    cout<<s<<"s"<<endl;
 return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <iostream>
#include <queue>

using namespace std;

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64; // 9e18
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

//const double PI = 3.141592653589793238463;
//const int MAXN = 1000500;
//const int MAXVALUE = 1000000500;
//const long double EPS = 1e-7;
const i64 INF = 1e18;
//i64 mod = 1e9 + 7;


i64 T, n, m, k;
//vector <vector<i64>> a;
//vector <i64> a;
//vector <i64> b;
//vector <i64> dp;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(16);


    //cin >> T;
    T = 1;

    for (i64 tt = 0; tt < T; ++tt) {

        cin >> n;

        vector<i64> a(n);
        for (i64 i = 0; i < n; ++i) {
            cin >> a[i];
        }

        i64 res = 0;
        for (i64 i = 1; i < n; ++i) {
            if (a[i] < a[i - 1]) {
                res += (a[i - 1] - a[i]);
                a[i] += (a[i - 1] - a[i]);
            }
        }

        cout << res << endl;



    }
    return 0;
}

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

int main() {
    using namespace std;
    unsigned long K;
    cin >> K;
    deque<pair<unsigned long, unsigned long>> dfs;
    bitset<100000> visited;
    dfs.emplace_back(1, 1);
    while(!dfs.empty()){
        auto t = dfs.front();
        dfs.pop_front();
        if(t.first == 0)return 0 % printf("%lu\n", t.second);
        visited[t.first] = true;
        if(!visited[(t.first + 1) % K])dfs.emplace_back((t.first + 1) % K, t.second + 1);
        if(!visited[t.first * 10 % K])dfs.emplace_front(t.first * 10 % K, t.second);
    }
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
    fast;
    int n,m,sum=0,cnt=0;
    int a[100001];
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
   // cout<<sum<<endl;
    double x=sum*(1/(4.0*m));
   // cout<<x<<endl;
    for(int i=0;i<n;i++)
    {
        if(a[i]>=x)
        {
            cnt++;
        }
    }
    if(cnt>=m)
    {
        cout<<"Yes"<<endl;
    }
    else
        cout<<"No"<<endl;


        return 0;
    }


Measured memory_bytes: 256
package main

import(
    "bufio"
    "fmt"
    "os"
    )
    
    var r = bufio.NewReader(os.Stdin)
    
func main() {
    var a,b int
    fmt.Fscan(r , &a , &b )
    
    x1 := a * b
    x2 := (a+b) *2
    fmt.Printf("%v %v\n" , x1,x2)
}


Measured memory_bytes: 1144
def f(N, K):
    if N < K:
        if K-N >= N:
            return N
        else:
            return f(K-N, K)
    else:
        if N <= N%K:
            return N
        else:
            return f(N%K, K)


def main():
    N, K = [int(x) for x in input().split()]
    print(f(N, K))


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	int n;
	scanf("%d", &n);
	V a(n);
	SCAN(a);
	std::sort(ALL(a));
	if(n%2==0){
		ll ans = 0;
		REP(i, 0, n/2) ans -= a[i];
		REP(i, n/2, n) ans += a[i];
		ans *= 2;
		ans -= a[n/2];
		ans += a[n/2-1];
		printf("%ld\n", ans);
	}else{
		ll ans1 = 0, ans2 = 0;
		REP(i, 0, n/2) ans1 -= a[i];
		REP(i, n/2, n) ans1 += a[i];
		ans1 *= 2;
		ans1 -= a[n/2];
		ans1 -= a[n/2+1];

		REP(i, 0, n/2+1) ans2 -= a[i];
		REP(i, n/2+1, n) ans2 += a[i];
		ans2 *= 2;
		ans2 += a[n/2];
		ans2 += a[n/2-1];
		printf("%ld\n", std::max(ans1, ans2));

	}
	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    int N; cin >> N;
    vector<int> h(N+1, 0);
    rep(i, 0, N) cin >> h[i];

    int left = 0;
    int res = 0;
    while (left < N+1) {
        if (h[left] == 0) {
            ++left;
            continue;
        }
        
        int right = left;
        int minPart = h[left];
        
        for (int i = left; h[i] != 0; ++i, ++right) {
            minPart = min(minPart, h[i]);
        }

        res += minPart;
        for (int i = left; i < right; ++i) {
            h[i] -= minPart;
        }
    }

    cout << res << "\n";
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		long L = stdIn.nextInt();
		long R = stdIn.nextInt();
		for(long i = L; i <= R; i++) {
			if(i%673 == 0 && ((R-L+1) >= 3 || i-1 >= L)) {
				System.out.println(0);
				System.exit(0);
			}
		}
		
		long min = 2018;
		for(long i = L; i < R; i++) {
			for(long j = i+1; j <= R; j++) {
				if((i*j)%2019 < min) {
					min = (i*j)%2019;
				}
			}
		}
		
		System.out.println(min);

	}

}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);	
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll ,ll> 			pll;
typedef pair<ld,ld> 			pld;
typedef unordered_map<ll,ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5+7;
const ll 	MAX7 	= 	1e+7+7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9+7;
const ll 	N 		= 	2*1e6;


// <------------- Declare Variables Here ------------> //

ll T=1;
ll n,x,y,m;
string s,t;
vll a;
// <------------- Implement Functions Here ----------> //ll prime[1000035];
ll prime[N+25];

// <------------- Implement Functions Here ----------> //

void PRIME() {
	for (ll i = 0; i <= 1000000; i++) {
		prime[i] = i;
	}

	for (ll i = 4; i <= 1000000; i += 2) {
		prime[i] = 2;
	}

	for (ll i = 3; i <= 1000000; i += 2) {
		if (prime[i] == i) {
			for (ll j = i * i; j <= 1000000; j += i) {
				if (prime[j] == j) prime[j] = i;
			}
		}
	}
}


ll factorize(ll x) {
	ll ans = 1;

	while (x > 1) {
		ll m = prime[x];
		ll cou = 0;
		while (x % m == 0) {
			cou++;
			x /= m;
		}
		ans*=(cou+1);
	}
	return ans;
}

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n;
	ll cou = 0;
	for(ll i=1;i<=n-1;i++) {
		ll val = n- i;
		cou += factorize(val);
	}
	cout<<cou;
}

int main() {
	fastio;randomINT;
	//cin>>T;
	PRIME();
	while(T--) {
		MAIN();
	}
	return 0;
}



Measured memory_bytes: 11444
#include <iostream>
#include <stdlib.h>
#include <vector> //vector
#include <algorithm> //sort()

using namespace std;

//uint64_t a, b, c, d, i, j, k, n;

uint64_t patty ( int n , uint64_t x);

uint64_t a[201];
uint64_t p[201];

int main(){
//////////////////////////////////////////////////////

    int n;
    uint64_t x;
    cin >> n >> x;

    p[0] = 1;
    a[0] = 1;

    for ( int i = 1 ; i <= n ; i ++)
    {
        p[i] = p[i-1]*2+1;
        a[i] = a[i-1]*2+3;
        //cout << i << " p:" << p[i] << " a:" << a[i] <<endl;
    }
    
    cout << patty( n , x) << endl;


    // cin >> n;
    // vector<uint64_t> input[n];
    // for (int i = 0 ; i < n ; i ++ )
    // {
    //     cin >> input[i];
    // }




    // uint64_t sum = 0;
    // for ( int i = 0 ; i < n ; i ++ )
    // {
    //     sum += i;
    // }






    // cout <<      << endl;

//////////////////////////////////////////////////////
// Ctrl + Opt + N to make
    return 0;
}

//n : 入れ子の数，x : 下から数えた枚数
uint64_t patty ( int n , uint64_t x)
{
    //cout << "patty : n:" << n << " x:" << x << endl;
    if ( n == 0)
    {
        if ( x == 1)
        {
            //cout << "n:" << n << " x:" << x << " patty1 =" <<1 << endl;
            return 1;
        }
        else if(x == 0)
        {
            //cout << "n:" << n << " x:" << x << " patty1 =" <<0 << endl;
           return 0;
        }
        else
        {
            //cout << "error1" << endl;
            return 0;
        }
    }
    if ( x <= 1 )
    {
        //cout << "n:" << n << " x:" << x << " patty1 =" <<0 << endl;
        return 0;
    }

    if ( x <= a[n - 1] + 1)
    {
        uint64_t pt = patty ( n - 1 , x - 1 );
        //cout << "n:" << n << " x:" << x << " patty2 =" << pt << endl;
        return pt;
    }

    if ( x <= a[n - 1] + 2)
    {
        uint64_t pt = patty ( n - 1 , x - 2 ) + 1;
        //cout << "n:" << n << " x:" << x << " patty3 =" << pt << endl;
        return pt;
    }

    if ( x <= a [n - 1] * 2 + 2)
    {
        uint64_t pt = p[n - 1] + 1 + patty( n - 1 , x - a[n - 1] - 2);
        //cout << "n:" << n << " x:" << x << " patty4 =" << pt << endl;
        return pt; 
    }

    if ( x <= a [n - 1] * 2 + 3)
    {
        uint64_t pt = p[n];
        //cout << "n:" << n << " x:" << x << " patty5 =" << pt << endl;
        return p[n];
    }

    //cout << "error2" << endl;
    return p[n];
}

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

 
int main() {
   int n;
   cin>>n;
   vector<int> H(n);
   rep(i,n)cin>>H[i];

   H[0]--;
   for(int i=1;i<n;i++){
       if(H[i]-1>=H[i-1])H[i]--;
       if(H[i]<H[i-1]){
           cout<<"No"<<endl;
           return 0;
       }
   }
   cout<<"Yes"<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    string N;
    int K;
    cin >> N >> K;
    int n = (int)N.size();
    auto dp = make_vec<ll>(2, K + 1, n + 1);
    dp[true][0][0] = 1;
    /* for (int i = 1; i < n + 1; i++) {
        dp[false][0][i] = 1;
    }*/

    for (int i = 0; i < n; i++) {
        for (int k = 0; k <= K; k++) {
            if (N[i] != '0') {
                dp[false][k][i + 1] += dp[true][k][i];  // 0 になる
                if (k != K) {
                    dp[true][k + 1][i + 1] += dp[true][k][i];                       // ぴったりおなじ
                    dp[false][k + 1][i + 1] += dp[true][k][i] * (int)(N[i] - '1');  // 0でも同じでもない
                }
            } else {
                dp[true][k][i + 1] = dp[true][k][i];  // 0のとき
            }
            if (k != K) dp[false][k + 1][i + 1] += dp[false][k][i] * 9;  // 0以外
            dp[false][k][i + 1] += dp[false][k][i];                      // 0 になる
                                                                         // cout << i << " " << k << " ";
            //debug(dp[false][k][i]);
        }
    }

    //cout << dp[true][K][n] << " " << dp[false][K][n] << " " << dp[false][K][n - 1] << " " << dp[false][K][n - 2] << endl;
    cout << dp[true][K][n] + dp[false][K][n] << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void){
    int S,j,i,I,a[600],b=0;
    scanf("%d",&S);
    a[0]=S;

    for(i=1;i<601;i++){
        if(a[i-1]%2==0){
            a[i]=a[i-1]/2;
        }else{
            a[i]=3*a[i-1]+1;
        }
        for(j=0;j<i;j++){
            if(a[j]==a[i]){
                printf("%d",i+1);
                b=1;
                break;
            }
        }
        if(b==1){
            break;
        }
    }


    return 0;
}

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

#define pb push_back
#define pop_b pop_back
#define pf push_front
#define pop_f pop_front

typedef long long int ll;
typedef pair<int, int> ii; // are aligned to the right like this
typedef vector<ii> vii;  //vector pair
typedef vector<int> vi;   //vector integer
typedef vector<string> vs; //vector string

int main() 
{
    	int d,t,s;
    cin>>d>>t>>s;
    float a=d*1.0;
    float b=t*1.0;
    float c=s*1.0;
    //cout<<a<<b<<c<<a/c;
    if(a/c<=b)
        cout<<"Yes";
    else
        cout<<"No";
        
    
}
 




/*



*/

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main()
{
  int h,w,m;
  cin >> h >> w >> m;
  vector<pair<int,int>> p(m);
  for(int i=0;i<m;i++) cin >> p[i].first >> p[i].second;

  vector<int> bh(h+1),bw(w+1);
  for(int i=0;i<h+1;i++) bh[i] = 0;
  for(int i=0;i<w+1;i++) bw[i] = 0;

  for(int i=0;i<m;i++){
    bh[p[i].first]++;
    bw[p[i].second]++;
  }

  int max_bh = 0;
  int max_bw = 0;
  for(int i=0;i<h+1;i++) max_bh = max(max_bh,bh[i]);
  for(int i=0;i<w+1;i++) max_bw = max(max_bw,bw[i]);

  ll mbh_cnt = 0;
  ll mbw_cnt = 0;
  for(int i=0;i<h+1;i++) mbh_cnt += (bh[i] == max_bh);
  for(int i=0;i<w+1;i++) mbw_cnt += (bw[i] == max_bw);

  bool f = false;
  ll cnt = 0;
  for(int i=0;i<m;i++){
    if(bh[p[i].first] == max_bh && bw[p[i].second] == max_bw){
      cnt++;
    }
  }

  ll ans = max_bh + max_bw;
  if(cnt == mbh_cnt * mbw_cnt) cout << ans - 1 << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 7980
#include <bits/stdc++.h>
#define endl '\n'
#define debug(X) cout << #X << " = " << X << endl

using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	#ifdef UTP
	freopen("input.txt", "r", stdin);
	#endif
	int n, m; cin >> n >> m;
	string a, b; cin >> a >> b;
	map<int, char> mapper;
	long long mcm = (1LL * n * m) / __gcd(n, m);
	for (int i = 0; i < n; i++)
		mapper[i * mcm / n] = a[i];
	int ok = 1;
	for (int i = 0; i < m; i++)
		if (mapper.count(i * mcm / m) && mapper[i * mcm / m] != b[i])
			ok = 0;
	if (ok) cout << mcm << endl;
	else cout << -1 << endl;
	return 0;
}


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

int main()
{
  	string s;
    cin >> s;
  
    unordered_map<string, int> um = {
    {"SUN", 7},
    {"MON", 6},
    {"TUE", 5},
      {"WED", 4},
      {"THU", 3},
      {"FRI", 2},
      {"SAT", 1},
  };
  cout << um.at(s);
  
  
    return 0;
}


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

using namespace std;

int main()
{
    int a,b,c;
	cin >> a >> b >> c;
	int x = a*100+b*10+c;
	(x % 4) ? cout<<"NO" : cout<<"YES"; 
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main()
{
  unsigned short *A, *B;

  int C[VMAX + 1];
  int n, i, j;
  scanf("%d", &n);

  A = (unsigned short *)malloc(sizeof(short) * n + 1);
  B = (unsigned short *)malloc(sizeof(short) * n + 1);

  for (i = 0; i <= VMAX; i++)
  {
    C[i] = 0;
  }

  // カウント
  for (i = 0; i < n; i++)
  {
    scanf("%hu", &A[i + 1]);
    C[A[i + 1]]++;
  }
  // 累積和
  for (i = 1; i <= VMAX; i++)
  {
    C[i] = C[i] + C[i - 1];
  }

  for (j = 1; j <= n; j++)
  {
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

  for (i = 1; i <= n; i++)
  {
    if (i > 1)
    {
      printf(" ");
    }
    printf("%d", B[i]);
  }
  printf("\n");

  return 0;
}


Measured memory_bytes: 10552