Submission #456271

#	Time	Username	Problem	Language	Result	Execution time	Memory
456271		SamAnd	Rack (eJOI19_rack)	C++17	100 / 100	6 ms	4044 KiB

rack

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1000006, M = 1000000007;

int ast[N];

void solv()
{
    ll n, k;
    cin >> n >> k;

    ast[0] = 1;
    for (int i = 1; i <= n; ++i)
        ast[i] = (ast[i - 1] * 2) % M;

    if (k == 1)
    {
        cout << "1\n";
        return;
    }
    if (k == 2)
    {
        cout << (ast[n - 1] + 1) % M << "\n";
        return;
    }

    for (int i = 1; ; ++i)
    {
        if (k > (1LL << i) && k <= (1LL << (i + 1)))
        {
            k -= (1LL << i);
            int ans = 0;
            for (int j = 0; ; ++j)
            {
                if (k == 1)
                {
                    ans = (ans + 1) % M;
                    break;
                }
                if (k % 2 == 0)
                {
                    ans = (ans + ast[n - j - 1]) % M;
                    k /= 2;
                }
                else
                {
                    k /= 2;
                    ++k;
                }
            }
            ans = (ans + ast[n - i - 1]) % M;
            cout << ans << "\n";
            break;
        }
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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