oj.uz

Submission #581038

# Submission time Handle Problem Language Result Execution time Memory
581038 2022-06-22T08:41:36 Z TimDee Rack (eJOI19_rack) C++14
100 / 100
 19 ms 23892 KB 
#include <bits/stdc++.h>
using namespace std;

#define paiu return
#define moment 0;
 
#define int long long
#define ll long long
 
#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)
#define forrr(i,j,x) for (int i=j; i<x; i++)
 
#define di(a,n) deque<int> a(n,0)
#define dll(a,n) deque<ll> a(n,0)
#define vi(a,n) vector<int> a(n,0)
#define vll(a,n) vector<ll> a(n,0)
 
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
    int n=a.size();
    vi(pr,n+1);
    forn(i,n) pr[i+1]=pr[i]+a[i];
    return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
 
#define f first
#define s second
 
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
 
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
     
//const int maxn = 3e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;

vector<int> tow(1e6+5);
vector<int> dp(1e6+5);
void ini() {
    tow[0]=0;
    int sum=0;
    for (int i=1; i<=1e6; i++) {
        tow[i]=sum+1;
        sum+=tow[i];
    }

    dp[0]=0;
    for (int i=1; i<=1e6; i++) {



    }
}

int pw2(int x, vector<int>&a) {
    int ret=1;
    for (int bit=32; bit>=0; bit--) {
        if (x&(1ll<<bit)) { ret*=a[bit]; ret%=mod; }
    }
    return ret;
}

void solve() {
    
    int n; cin>>n;
    int k; cin>>k; 

    vector<int> binexp(1e6+3,2);
    binexp[0]=2;
    forn(i,1e6) binexp[i+1]=(binexp[i]*binexp[i])%mod;

    int ans=1;

    int lev=n-1;
    while (lev>=0) {
        if (k%2) {
            k=(k+1)>>1;
        } else {
            ans+=pw2(lev,binexp);
            //cout<<ans<<' ';
            ans%=mod;
            k=k>>1;
        }
        lev--;
    }

    cout<<ans;

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //init_primes();
    
    int t=1;
    //cin>>t;
    
    while(t--) solve();
    
    paiu moment
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23784 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 15 ms 23792 KB Output is correct
4 Correct 15 ms 23796 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23784 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 15 ms 23792 KB Output is correct
4 Correct 15 ms 23796 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 15 ms 23780 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 15 ms 23764 KB Output is correct
9 Correct 15 ms 23716 KB Output is correct
10 Correct 16 ms 23764 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23784 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 15 ms 23792 KB Output is correct
4 Correct 15 ms 23796 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 15 ms 23780 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 15 ms 23764 KB Output is correct
9 Correct 15 ms 23716 KB Output is correct
10 Correct 16 ms 23764 KB Output is correct
11 Correct 16 ms 23812 KB Output is correct
12 Correct 16 ms 23808 KB Output is correct
13 Correct 19 ms 23768 KB Output is correct
14 Correct 18 ms 23808 KB Output is correct
15 Correct 16 ms 23892 KB Output is correct