Submission #441637

#	Time	Username	Problem	Language	Result	Execution time	Memory
441637		nots0fast	Rack (eJOI19_rack)	C++17	100 / 100	33 ms	31616 KiB

rack

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define mt make_tuple
#define MAX (int)(2*pow(10,6) + 5)
// #define cout out
// #define cin in
ll inf = pow(10, 18) + 100;
ll INF = pow(10, 9);
ll modulo = pow(10, 9) + 7;
double eps = 1e-10;

// start time 18 : 23
ll seg[MAX];
vector<ll> sira;

void determine(ll id, ll l, ll r){
	seg[id]++;
	if(l == r){
		sira.pb(l);
		return;
	}
	if(seg[2*id] > seg[2*id+1]){
		determine(2*id+1, (l+r)/2+1, r);
	}
	else{
		determine(2*id, l, (l+r)/2);
	}
}

ll pv[MAX];
ll act[MAX];

void pre(){
	pv[0] = 1;
	act[0] = 1;
	for(ll i = 1; i<MAX; i++){
		pv[i] = pv[i-1]*2;
		if(pv[i] >= modulo){
			pv[i] -= modulo;
		}
		act[i] = act[i-1]*2;
		if(act[i] > inf){
			act[i] = inf;
		}
	}
}

void go(ll n){
	fori(1<<n){
		determine(1, 1, (1<<n));
	}
	for(ll i = 0; i<(ll)sira.size(); i++){
		cout<<bitset<11>(sira[i])<<endl;
	}
}

void deal(){
	pre();
	
	ll n, k;
	cin>>n>>k;
//	go(n);
	
		ll pl = 0;
		ll sv = k;
		if(k == act[n]){
			pl = pv[n];
		}
		else{
			ll bit = 1;
			for(ll i = n-1; i>=0; i--){
				ll cur;
				if(k <= act[i]){
					cur = 0;
				}
				else{
					cur = 1;
					k -= act[i];
				}
				if(bit == 1){
					if(cur == 0){
						pl += pv[n-1-i];
						if(pl >= modulo){
							pl -= modulo;
						}
						bit = 0;
					}
				}
				else{
					if(cur == 1){
						pl += pv[n-1-i];
						if(pl >= modulo){
							pl -= modulo;
						}
					}
				}
	//			cout<<"k now "<<k<<" real "<<act[i]<<" "<<pl<<endl;
			}
		}
//		cout<<pl<<" "<<sira[sv-1]<<endl;
//		assert(pl == sira[sv-1]);
		cout<<pl;
	
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();  
}

Compilation message (stderr)

rack.cpp: In function 'void deal()':
rack.cpp:80:6: warning: unused variable 'sv' [-Wunused-variable]
   80 |   ll sv = k;
      |      ^~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60