Submission #726534

#	Time	Username	Problem	Language	Result	Execution time	Memory
726534		abcvuitunggio	Permutation (APIO22_perm)	C++17	100 / 100	365 ms	612 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> construct(long long k, int base){
    vector <int> v;
    multiset <long long> s;
    for (int i=0;i<base;i++){
        v.push_back(0);
        s.insert(1);
        k--;
        if (!k)
            return v;
    }
    v.pop_back();
    while (k){
        int res=-1;
        long long sum=0;
        for (auto 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> ve;
    vector <int> res;
    if (k%2==0){
        res=construct_permutation(k/2);
        res.push_back(res.size());
        return res;
    }
    if (k%3==0){
        res=construct_permutation(k/3);
        res.push_back(res.size()+1);
        res.push_back(res.size()-1);
        return res;
    }
    int mn=10000;
    for (int i=2;i<=20;i++){
        ve=construct(k,i);
        if (mn>ve.size()){
            mn=ve.size();
            swap(res,ve);
        }
    }
    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;
    }
    vector <int> res2=construct_permutation(k/2);
    res2.push_back(res2.size());
    for (int &i:res2)
        i++;
    res2.push_back(0);
    return (res.size()>res2.size()?res2:res);
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (mn>ve.size()){
      |             ~~^~~~~~~~~~

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