oj.uz

Submission #226602

# Submission time Handle Problem Language Result Execution time Memory
226602 2020-04-24T13:16:16 Z Theo830 Rack (eJOI19_rack) C++17
100 / 100
 20 ms 15616 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll INF = 1e9+7;
    ll MOD = 998244353;
    typedef pair<ll,ll> ii;
    #define iii pair<ii,ll>
    #define f(i,a,b) for(long long i = a;i < b;i++)
    #define rf(i,a,b) for(long long i=a;i>=b;i--)
    #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define w(t) while(t--)
    #define c(n); cin>>n;
    #define p(n) cout<<n;
    #define pl(n) cout<<n<<"\n";
    #define ps(n); cout<<n<<" ";
    #define F first
    #define S second
    #define pb(a) push_back(a)
    #define all(x) (x).begin(), (x).end()
    #define ull unsigned long long
    #define vll vector<ll>
    #define vii vector<ii>
    #define mkp make_pair
    #define ld long double
    #define arrin(a,n) f(i,0,n){cin>>a[i];}
    #define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
    #define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
    #define PI (2*acos(0))
    const long long N = 2e5+5;
    vll visit,dist,taken;
    vector<vll> adj;
    vector<vii> adj2;
    priority_queue<ii,vector<ii>, greater<ii> > pq;
    ll bit[N][2];
    ll siz;
    ll res = 0;
    ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
    ll gcd(ll a,ll b){return __gcd(a,b);}
    ll power(ll a,ll b){if(b == 0)return 1;if(b == 1)return a;ll ans = power(a,b/2) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
    ll inverse(ll x){x%=MOD;return power(x,MOD-2);}
    void BITup(ll k, ll x,ll pos){while(k <= siz){bit[k][pos]^=x;k += k & -k;}}
    ll BITq(ll k,ll pos){ll s=0;while(k>=1){s^=bit[k][pos];k -= k &-k;}return s;}
    struct node{ll lazy=0,val=0;}seg[4000000];
    struct poll{ll x,y;};
    void dfs(ll v){visit[v] = 1;for(auto x:adj[v]){if(!visit[x])dfs(x);}}
    void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
    void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
    void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
    ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
    void YESNO(ll a){if(!!a){pl("YES");}else{pl("NO");}}
    void filesin(void){freopen("a.txt","r",stdin);}
    void filesout(void){freopen("a.out","w",stdout);}
    int main(void){
        fastio;
        ll n,k;
        c(n);
        c(k);
        k--;
        ll power[n+1];
        power[0] = 1;
        ll powerwm[n+1];
        powerwm[0] = 1;
        f(i,1,n+1){
            power[i] = power[i-1] * 2;
            powerwm[i] = powerwm[i-1] * 2;
            if(powerwm[i-1]*2 > 1e18){
                powerwm[i] = 1e18 + 1;
            }
            power[i] %= INF;
        }
        ll add = 1;
        if(k > powerwm[n-1]){
            k -= powerwm[n-1];
            add = 2;
        }
        ll ans = 0;
        f(i,0,min(n,61LL)){
            if((k & (1LL<<i)) != 0){
                ans += power[n-i-1];
                ans %= INF;
            }
        }
        ans += add;
        ans %= INF;
        pl(ans);
    }

Compilation message

rack.cpp: In function 'void filesin()':
rack.cpp:51:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void filesin(void){freopen("a.txt","r",stdin);}
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~
rack.cpp: In function 'void filesout()':
rack.cpp:52:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void filesout(void){freopen("a.out","w",stdout);}
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 1152 KB Output is correct
15 Correct 20 ms 15616 KB Output is correct