Submission #718361

#	Time	Username	Problem	Language	Result	Execution time	Memory
718361		lam	Permutation (APIO22_perm)	C++17	10 / 100	1 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> construct_permutation(long long k)
{
    vector <int> res;
    ll len = log2(k);
    vector <int> a;
    for (int i=1; i<=len; i++) a.push_back(i-1);
    k-=(1LL<<len);
    while (k>0)
    {
        ll it = 0;
        while ((1LL<<(it+1))<= k)
        {
            it++;
        }
        k-= (1LL<<it);
        a.push_back(it);
    }
    int n=a.size();
    vector <int> d(n+1,0);
    for (int i=0; i<n; i++) d[a[i]] ++;
    for (int i=1; i<=n; i++) d[i]+=d[i-1];
    res.resize(n);
    for (int i=0; i<n; i++) res[i] = --d[a[i]];
//    for (int i:a) cerr<<i<<' '; cerr<<endl;
//    for (int i:res) cerr<<i<<' '; cerr<<endl;
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 90