Submission #584579

#	Time	Username	Problem	Language	Result	Execution time	Memory
584579		lovrot	Rack (eJOI19_rack)	C++11	100 / 100	7 ms	4308 KiB

rack

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MOD = 1e9 + 7;
const int N = 1e6 + 10;

int n;
ll k;
int eks[N];

int add(int a, int b){
    if(a + b >= MOD)
        return a + b - MOD;
    return a + b;
}

int mult(int a, int b){
    return (a * b) % MOD;
}

int rec(int x, ll y){
    if(x == 0)
        return 0;
    if(y & 1ll)
        return add(eks[x - 1], rec(x - 1, y / 2));
    return rec(x - 1, y / 2);
}

int main(){
    eks[0] = 1;
    for(int i = 1;  i < N; i++)
        eks[i] = mult(eks[i - 1], 2);
    cin >> n >> k;
    k--;
    cout << add(rec(n, k), 1) << "\n";
    return 0;
}

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