Submission #1280793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280793		silence25	Rack (eJOI19_rack)	C++20	100 / 100	17 ms	23268 KiB

rack

#include "bits/stdc++.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll mod = 1000000007;
const ll INF = 1e18;
void solve(){
	ll n,k;
	cin>>n>>k;
	pair<ll,bool>m[n+5];
	ll m1[n+5];
	m1[0] = 1LL;
	m[0] = {1LL,false};
	for(ll i = 1;i<=n;++i){
		m1[i] = (m1[i-1] * 2LL)%mod;
		m[i].ff = (m[i-1].ff * 2LL);
		m[i].ss = (m[i-1].ss) | (m[i].ff > k);
	}
	ll id,cur;
	id = cur = 1LL;
	for(ll i = 1;i<=n;++i){
		ll x = m[n-i].ff;
		if(m[n-i].ss || x + cur > k)
			continue;
		cur += x;
		id = (id + m1[i-1])%mod;
	}
	cout<<id;
}
int main(){
	// freopen("file.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

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