Submission #726506

#	Time	Username	Problem	Language	Result	Execution time	Memory
726506		abcvuitunggio	Permutation (APIO22_perm)	C++17	0 / 100	1093 ms	209788 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--;
    }
    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[4];
    ve[0]=construct(k,2);
    ve[1]=construct(k,3);
    ve[2]=construct(k,5);
    ve[3]=construct(k,7);
    vector <int> res;
    int mn=10000;
    for (int i=0;i<4;i++)
        if (mn>ve[i].size()){
            mn=ve[i].size();
            res=ve[i];
        }
    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:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (mn>ve[i].size()){
      |             ~~^~~~~~~~~~~~~

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