oj.uz

Submission #575790

# Submission time Handle Problem Language Result Execution time Memory
575790 2022-06-11T09:34:37 Z somo Permutation (APIO22_perm) C++17
0 / 100
 1 ms 212 KB 
#include "perm.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7 ;
const int  N= 5e5 + 10;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        //ans %= MOD;
        //x %= MOD;
    }
    return ans;
}



vector<int> construct_permutation(long long k){
    k -- ;
    ll ctr = 0;
    vector<int>ans;
    vector<pair<ll,bool>>g;
    for(ll i= 60 ; i > 0 ; i --){
        if((1LL << i)-1 <= k ){
            if(2*((1LL << i)-1) <= k){
                g.pb({i,1});
                ctr += i + 1;
                break;
            }
            else g.pb({i,0});
            ctr += i;
            k -= ((1LL << i)-1);
        }
    }
    for(auto i : g){
        ll f = ctr - i.F - i.S ;
        if(i.F + i.S == 1){
            ans.pb(ctr-1);
            ctr --;
            continue;
        }
        for(ll j = f ; j < ctr-2 ; j ++) ans.pb(j);
        if(i.S){
            ans.pb(ctr-1);
            ans.pb(ctr-2);
        }
        else{
            ans.pb(ctr-2);
            ans.pb(ctr-1);
        }
        ctr -= (i.F + i.S);
    }
    return ans;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -