oj.uz

Submission #456271

# Submission time Handle Problem Language Result Execution time Memory
456271 2021-08-06T10:11:27 Z SamAnd Rack (eJOI19_rack) C++17
100 / 100
 6 ms 4044 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 6 ms 4044 KB Output is correct