Submission #1191778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191778		peteza	Rack (eJOI19_rack)	C++20	100 / 100	4 ms	8008 KiB

rack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

int n;
ll k;
ll pows[1000005];

ll upd(ll x) {
    if(x >= mod) return x-mod;
    return x;
}

ll rec(int cn, ll ck) {
    if(!ck) return 1;
    if(ck&1) return upd(rec(cn-1, ck>>1) + pows[cn-1]);
    return rec(cn-1, ck>>1);
}

int main() {
    pows[0] = 1;
    for(int i=1;i<=1000002;i++) {
        pows[i] = (pows[i-1] << 1);
        pows[i] = upd(pows[i]);        
    }
    cin >> n >> k; k--;
    cout << rec(n, k);
}

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