oj.uz

Submission #876455

# Submission time Handle Problem Language Result Execution time Memory
876455 2023-11-21T19:02:50 Z alexdd Permutation (APIO22_perm) C++17
71.3692 / 100
 474 ms 2756 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include "perm.h"
const int NRIT = 10;
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 349 ms 1708 KB Output is correct

Subtask #2
61.369230771 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 349 ms 1708 KB Output is correct
3 Partially correct 450 ms 2048 KB Partially correct
4 Partially correct 441 ms 1712 KB Partially correct
5 Partially correct 448 ms 2136 KB Partially correct
6 Partially correct 452 ms 2320 KB Partially correct
7 Partially correct 450 ms 2252 KB Partially correct
8 Partially correct 474 ms 2596 KB Partially correct
9 Correct 454 ms 1912 KB Output is correct
10 Partially correct 458 ms 2756 KB Partially correct
11 Partially correct 449 ms 2576 KB Partially correct
12 Partially correct 465 ms 2508 KB Partially correct
13 Partially correct 451 ms 2468 KB Partially correct