Submission #1310272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310272		settop	Permutation (APIO22_perm)	C++20	91.33 / 100	4 ms	576 KiB

perm

#include<bits/stdc++.h>
//#include "perm.h"

using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int)x.size()
#define pb push_back

vector<int> construct_permutation(long long k){
    vector<int> ans={0};
    vector<ll> pref={1};
    k-=2;

    int n=1;
    while(k){
        bool ok=0;

        rfall(i,n-1,0){
            if(pref[i]+1<=k){
                ok=1;
                k-=(pref[i]+1);
                vector<int> aux;
                vector<ll> pf;
                fall(j,0,i) aux.pb(ans[j]),pf.pb(pref[j]);
                aux.pb(n); pf.pb(2*pref[i]+1);
                fall(j,i+1,n-1) aux.pb(ans[j]),pf.pb(pref[j]+pref[i]+1);

                ans=aux,pref=pf;

                n++;

                break;
            }
        }

        if(ok) continue;

        k--;

        vector<int> aux={n};
        vector<ll> pf={1};
        for(auto u:ans) aux.pb(u);
        for(auto u:pref) pf.pb(u+1);

        ans=aux,pref=pf;

        n++;
    }
    return ans;
}

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