Submission #229738

#	Time	Username	Problem	Language	Result	Execution time	Memory
229738		Coder	Rack (eJOI19_rack)	C++14	40 / 100	5 ms	384 KiB

rack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define PR(x) cerr << #x << "=" << (x) << endl;
const int MOD = 1000000009;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
const int N = 200001;
int i, j, k, m, n;
int a[N];

int pw[1000001];

int main() {
    //freopen("x.in", "r", stdin);

    ll k;
    cin >> n >> k;
    k--;

    pw[0] = 1;
    F1(i, n) pw[i] = pw[i - 1] * 2 % MOD;

    int ret = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (k % 2 == 1) {
            ret = (ret + pw[i]) % MOD;
        }
        k /= 2;
    }
    cout << ret + 1 << endl;

    return 0;
}

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