oj.uz

Submission #575814

# Submission time Handle Problem Language Result Execution time Memory
575814 2022-06-11T09:57:51 Z somo Permutation (APIO22_perm) C++17
79.6769 / 100
 11 ms 852 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((1LL << (i-1)) + (1LL << i) -1 <= k){
                g.pb({i,1});
                ctr += i + 1 ;
                k -= ((1LL << (i-1)) + (1LL << i) -1);
                continue;
            }
            else g.pb({i,0});
            ctr += i;
            k -= ((1LL << i)-1);
        }
    }
    //23

    // 1 2 3 5 4
    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;
}
/*
int main()
{
    vector<int>ans = construct_permutation(7);
    for(auto i : ans) cout << i << ' ' ;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
69.676923078 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Partially correct 1 ms 340 KB Partially correct
5 Partially correct 3 ms 468 KB Partially correct
6 Partially correct 4 ms 468 KB Partially correct
7 Partially correct 8 ms 596 KB Partially correct
8 Partially correct 7 ms 852 KB Partially correct
9 Correct 2 ms 340 KB Output is correct
10 Partially correct 8 ms 852 KB Partially correct
11 Partially correct 11 ms 852 KB Partially correct
12 Partially correct 6 ms 804 KB Partially correct
13 Partially correct 6 ms 724 KB Partially correct