Submission #876457

#	Time	Username	Problem	Language	Result	Execution time	Memory
876457		alexdd	Permutation (APIO22_perm)	C++17	71.35 / 100	715 ms	3316 KiB

perm

#include<iostream>
#include<vector>
#include<algorithm>
#include "perm.h"
const int NRIT = 15;
const int MAXLUN = 10;
const int MINLUN = 4;
using namespace std;
vector<pair<long long,vector<int>>> secvs;
bool cmp(pair<long long,vector<int>> x, pair<long long,vector<int>> y)
{
    if(x.first > y.first)
        return 1;
    if(x.first < y.first)
        return 0;
    if((int)x.second.size()<(int)y.second.size())
        return 1;
    return 0;
}
long long dp[MAXLUN+5];
long long calc_nrs(vector<int> v)
{
    for(int i=0;i<=(int)v.size();i++)
        dp[i]=0;
    for(int i=0;i<(int)v.size();i++)
    {
        dp[v[i]]++;
        for(int j=0;j<v[i];j++)
            dp[v[i]] += dp[j];
    }
    long long nrs=0;
    for(int i=0;i<=(int)v.size();i++)
        nrs += dp[i];
    return nrs;
}
void get_secvs()
{
    vector<int> aux;
    for(int i=1;i<60;i++)
    {
        aux.clear();
        for(int j=0;j<i;j++)
            aux.push_back(j);
        secvs.push_back({(1LL<<i)-1, aux});
    }
    for(int lun=MINLUN;lun<=MAXLUN;lun++)
    {
        aux.clear();
        for(int i=0;i<lun;i++)
            aux.push_back(i);
        for(int i=0;i<NRIT;i++)
        {
            random_shuffle(aux.begin(),aux.end());
            secvs.push_back({calc_nrs(aux),aux});
        }
    }
    sort(secvs.begin(),secvs.end(),cmp);
}
std::vector<int> construct_permutation(long long k)
{
    get_secvs();
    vector<int> sol;
    int cnt=0;
    k--;
    for(int i=0;i<secvs.size();i++)
    {
        while(k>=secvs[i].first)
        {
            for(int j=(int)secvs[i].second.size()-1;j>=0;j--)
                sol.push_back(cnt+secvs[i].second[j]);
            cnt += (int)secvs[i].second.size();
            k -= secvs[i].first;
        }
    }
    reverse(sol.begin(),sol.end());
    return sol;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<secvs.size();i++)
      |                 ~^~~~~~~~~~~~~

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