Submission #441634

#	Time	Username	Problem	Language	Result	Execution time	Memory
441634		nots0fast	Rack (eJOI19_rack)	C++17	0 / 100	28 ms	31620 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 = 998244353;
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 deal(){
	pre();
	/*
	ll n;
	cin>>n;
	fori(1<<n){
		determine(1, 1, (1<<n));
	}
	for(ll i = 0; i<(ll)sira.size(); i++){
		cout<<bitset<11>(sira[i])<<endl;
	}
	*/
	ll n, k;
	cin>>n>>k;
	
	ll pl = 1;
	if(k == act[n]){
		pl = pv[n];
	}
	else{
		ll bit = 0;
		if(k > act[n-1]){
			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(cur != bit){
				pl += pv[n-1-i];
				if(pl >= modulo){
					pl -= modulo;
				}
			}
//			cout<<"k now "<<k<<" real "<<act[i]<<" "<<pl<<endl;
		}
	}
	cout<<pl;
}


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

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