Submission #983974

#	Time	Username	Problem	Language	Result	Execution time	Memory
983974		vjudge1	Permutation (APIO22_perm)	C++17	91.33 / 100	2 ms	6748 KiB

perm

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

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] , c[N] , d[N] , sum[N];
vector<int>v[N];
vector<int> construct_permutation(ll k){
    ll x = 100000 , l;
    k--;
    dp[101] = sum[101] =  0;
    for(int i = 100; i >= 1; i--){
        v[i].clear();
        dp[i] = sum[i + 1] + 1;
        sum[i] = sum[i + 1] + dp[i];
        if(dp[i] > k){
            l = i + 1 ;break;}
        v[i].pb(x);
        k -= dp[i];
        x--;
    }
    for(int i = l;  i <= 100; i++){
        while(k >= dp[i]){
            k -= dp[i];
            v[i].pb(x);
            x--;
        }
    }
    vector<int>ans;
    for(int i = l; i <= 100; i++){
        for(auto to : v[i])
            ans.pb(to - x - 1);
    }
    return ans;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:38:13: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |     for(int i = l;  i <= 100; i++){
      |             ^

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