oj.uz

Submission #466732

# Submission time Handle Problem Language Result Execution time Memory
466732 2021-08-20T14:46:15 Z mtxas Rack (eJOI19_rack) C++14
100 / 100
 15 ms 1316 KB 
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define pll pair<ll, ll>
#define mii map<int, int>
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(x) ((int)x.size())
#define turbo() cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
#define _fre() freopen("input.txt", "r", stdin)
#define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
#define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
#define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
#define _forn(a, b, c) for(int (a) = (b); (a) > (c); (a)--)
using namespace std;
/**********************************************************************************
                                STRUCTS
**********************************************************************************/

/**********************************************************************************
                               VARIABLES
**********************************************************************************/
const int mod = 1e9+7;
/**********************************************************************************
                               FUNCTIONS
**********************************************************************************/

/**********************************************************************************
                                 MAIN
**********************************************************************************/
int main(){
    //_fre();
    //freopen("input.txt", "w", stdout);
    turbo();
    ll n, k; cin>>n>>k;
    stack<char> stek;
    int pow = 0;
    ll g = 1;
    _for(i, 0, n) {
        g*= 2, pow++;
        if(g > k) break;
    }
    _for(i, 0, n-pow) stek.push('L');
    _forneq(h, pow, 1){
        ll mid = g/2;
        if(k > mid) k-= mid, stek.push('R');
        else stek.push('L');
        g/= 2;
    }
    ll v = 1;
    while(!stek.empty()){
        char c= stek.top(); stek.pop();
        if(c == 'L')    v = 2LL*v;
        else if(c=='R') v = 2LL*v+1;
        v%= mod;
    }
    g = 1; _for(i, 0, n) g*= 2LL, g%= mod;
    cout<<(mod+v-g+1)%mod;
}

Compilation message

rack.cpp: In function 'int main()':
rack.cpp:16:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
rack.cpp:44:5: note: in expansion of macro '_for'
   44 |     _for(i, 0, n) {
      |     ^~~~
rack.cpp:16:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
rack.cpp:48:5: note: in expansion of macro '_for'
   48 |     _for(i, 0, n-pow) stek.push('L');
      |     ^~~~
rack.cpp:18:34: warning: unnecessary parentheses in declaration of 'h' [-Wparentheses]
   18 | #define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
      |                                  ^
rack.cpp:49:5: note: in expansion of macro '_forneq'
   49 |     _forneq(h, pow, 1){
      |     ^~~~~~~
rack.cpp:16:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
rack.cpp:62:12: note: in expansion of macro '_for'
   62 |     g = 1; _for(i, 0, n) g*= 2LL, g%= mod;
      |            ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
60.0 / 60.0

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