oj.uz

Submission #406578

# Submission time Handle Problem Language Result Execution time Memory
406578 2021-05-17T18:55:39 Z Ronin13 Rack (eJOI19_rack) C++14
100 / 100
 1 ms 204 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define INF 1e9+1;
using namespace std;
vector<ll>path;
void rec(ll x,ll lev){
    if(lev==0){path.pb(x);return;}
    if(x<=(1LL<<(lev-1)))rec(x,lev-1);
    else
    rec(x-(1LL<<(lev-1)),lev-1);
    path.pb(x);
}

ll mod=1e9+7;
ll logpow(ll a,ll pow){
    if(pow==0)return 1;
    ll k=logpow(a,pow/2);
    k*=k;k%=mod;
    if(pow&1)k*=(a%mod);
    return k%mod;
}

void solve(){
    ll n,k;cin>>n>>k;
    ll lev=log2(k);
    if((1LL<<lev)!=k)lev++;
    rec(k,lev);

    ll curhook=path[0];
    ll cur=n-1;
    for(int i=0;i<path.size()-1;i++){
        if(path[i]!=path[i+1]){
            curhook+=logpow(2,cur);
            curhook%=mod;
        }
        cur--;
    }
    cout<<curhook;
}
int main(){
    int t;t=1;
    while(t--){
        solve();
    }
}

Compilation message

rack.cpp: In function 'void solve()':
rack.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<path.size()-1;i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 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 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct