Submission #726500

#	Time	Username	Problem	Language	Result	Execution time	Memory
726500		abcvuitunggio	Permutation (APIO22_perm)	C++17	10 / 100	1077 ms	1216 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> construct(long long k, int base){
    vector <int> v;
    multiset <int> s;
    for (int i=0;i<base;i++){
        v.push_back(0);
        s.insert(1);
        k--;
    }
    v.pop_back();
    while (k){
        int res=-1;
        long long sum=0;
        for (int i:s){
            if (sum+i>k)
                break;
            sum+=i;
            res++;
        }
        k-=sum;
        v.push_back(res);
        s.insert(sum);
    }
    return v;
}
std::vector<int> construct_permutation(long long k)
{
    if (k==1)
        return {};
    if (k==2)
        return {0};
    int ch[1001];
    memset(ch,0,sizeof(ch));
    vector <int> v2=construct(k,2);
    vector <int> v3=construct(k,3);
    vector <int> res;
    if (v2.size()>v3.size())
        res=v3;
    else
        res=v2;
    for (int i=res.size()-1;i>=0;i--){
        int cnt=0;
        res[i]++;
        while (res[i]){
            cnt++;
            if (!ch[cnt])
                res[i]--;
        }
        res[i]=cnt-1;
        ch[cnt]=1;
    }
    return res;
}

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