Submission #575814

#	Time	Username	Problem	Language	Result	Execution time	Memory
575814		somo	Permutation (APIO22_perm)	C++17	79.68 / 100	11 ms	852 KiB

perm

#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 / 10
• Subtask 2: 69.676923078 / 90