oj.uz

Submission #441637

# Submission time Handle Problem Language Result Execution time Memory
441637 2021-07-05T15:44:00 Z nots0fast Rack (eJOI19_rack) C++17
100 / 100
 33 ms 31616 KB 
#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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31564 KB Output is correct
2 Correct 29 ms 31504 KB Output is correct
3 Correct 31 ms 31544 KB Output is correct
4 Correct 29 ms 31552 KB Output is correct
5 Correct 28 ms 31556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31564 KB Output is correct
2 Correct 29 ms 31504 KB Output is correct
3 Correct 31 ms 31544 KB Output is correct
4 Correct 29 ms 31552 KB Output is correct
5 Correct 28 ms 31556 KB Output is correct
6 Correct 27 ms 31564 KB Output is correct
7 Correct 27 ms 31556 KB Output is correct
8 Correct 28 ms 31616 KB Output is correct
9 Correct 31 ms 31532 KB Output is correct
10 Correct 31 ms 31504 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31564 KB Output is correct
2 Correct 29 ms 31504 KB Output is correct
3 Correct 31 ms 31544 KB Output is correct
4 Correct 29 ms 31552 KB Output is correct
5 Correct 28 ms 31556 KB Output is correct
6 Correct 27 ms 31564 KB Output is correct
7 Correct 27 ms 31556 KB Output is correct
8 Correct 28 ms 31616 KB Output is correct
9 Correct 31 ms 31532 KB Output is correct
10 Correct 31 ms 31504 KB Output is correct
11 Correct 28 ms 31580 KB Output is correct
12 Correct 32 ms 31600 KB Output is correct
13 Correct 29 ms 31544 KB Output is correct
14 Correct 28 ms 31540 KB Output is correct
15 Correct 33 ms 31584 KB Output is correct