Submission #637510

#	Time	Username	Problem	Language	Result	Execution time	Memory
637510		ksu2009en	Rack (eJOI19_rack)	C++17	40 / 100	1 ms	212 KiB

rack

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>

using namespace std;
typedef long long ll;

ll power[100007];

ll solve(ll pos, ll pow){
    if(pos == 1 || pow < 0)
        return 1;
    
    ll res = 0;
    
    if(pos % 2 != 0)
       res = solve((pos + 1) / 2, pow - 1) % (ll)(1e9 + 7);
    else
        res = solve(pos / 2, pow - 1);
    
    
    //cout << pos << ' ' << pow << ' ' << res << endl;
    
    return res + (pos % 2 == 0 ? power[pow] : 0);
}

int main(){
    ll n, k;
    cin >> n >> k;
    
    power[0] = 1;
    
    for(int i = 1; i <= n; i++)
        power[i] = (power[i - 1] * 2) % (ll)(1e9 + 7 );
    
    cout << solve(k, n - 1) << endl;
    
    return 0;
}

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