Submission #643690

#	Time	Username	Problem	Language	Result	Execution time	Memory
643690		czhang2718	Permutation (APIO22_perm)	C++17	71.22 / 100	82 ms	1008 KiB

perm

#include "bits/stdc++.h"
using namespace std;

// #include "perm.h"

std::vector<int> construct_permutation(long long S)
{
    pair<int, vector<int>> mn={1e9, {}};
    for(int k=(S%2)+1; k<=120; k+=2){
        long long s=S-1+k;
        vector<int> v;
        assert(s%2==0);
        if(__builtin_popcountll(s)>k || s/2<k) continue; 
        multiset<int> bi;
        for(int i=1; i<60; i++){
            if(s&(1LL<<i)) bi.insert(i);
        }
        while(bi.size()<k){
            auto it=bi.upper_bound(1);
            assert(it!=bi.end());
            // cout << "split " << (*it) << "\n";
            bi.insert((*it)-1);
            bi.insert((*it)-1);
            bi.erase(it);
        }
        int x=0;
        for(int i:bi){
            // cout << "i " << i << "\n";
            for(int j=x+i-1; j>=x; j--) v.push_back(j);
            x+=i;
        }
        reverse(v.begin(), v.end());
        mn=min(mn, {v.size(), v});
    }
    return mn.second;
}


// int main(){
//     cin.tie(0)->sync_with_stdio(0);

//     int k; cin >> k;
//     for(int x:construct_permutation(k)) cout << x << " ";
// }
// // kindness is weakness

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:18:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |         while(bi.size()<k){
      |               ~~~~~~~~~^~

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