Submission #1188525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188525		andrei_n	Rack (eJOI19_rack)	C++20	40 / 100	1 ms	528 KiB

rack

#include <bits/stdc++.h>
#define int long long

using namespace std;

int v[400000],s;
bitset<1000005> bit;

void multiply(int x)
{
    s += 5;
    int r = 0;
    for(int i=0; i<s; ++i)
    {
        v[i] = v[i] * x + r;
        r = v[i] / 10;
        v[i] %= 10;
    }
    while(s && !v[s-1]) --s;
}

void substract(int x)
{
    int r = 0;
    v[0] -= x;
    for(int i=0; i<s; ++i)
    {
        if(v[i] >= 0) break;
        v[i+1] -= (-v[i]+9) / 10;
        v[i] += (-v[i]+9) / 10 * 10;
    }
    while(s && !v[s-1]) --s;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k; cin>>n>>k;
    --k;
    for(int i=n; i>=1; --i)
        if(i >= 64 || !(k & (1<<i-1)))
            bit[i] = 1;
    v[s++] = 1;
    for(int i=1; i<=n; ++i)
    {
        multiply(2);
        if(bit[i]) substract(1);
    }
    for(int i=s-1; i>=0; --i)
        cout<<v[i];
    return 0;
}

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