Submission #726519

#	Time	Username	Problem	Language	Result	Execution time	Memory
726519		abcvuitunggio	Permutation (APIO22_perm)	C++17	10 / 100	1080 ms	488 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==2)
        return {0};
    int ch[1001];
    memset(ch,0,sizeof(ch));
    vector <int> ve;
    vector <int> res;
    int mn=10000;
    for (int i=2;i<=1000;i++){
        int ch=1;
        for (int j=2;j*j<=i;j++)
            if (i%j==0){
                ch=0;
                break;
            }
        if (!ch)
            continue;
        ve=construct(k,i);
        if (mn>ve.size()){
            mn=ve.size();
            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;
    }
    return res;
}

Compilation message (stderr)

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

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