#include<bits/stdc++.h>
#include "perm.h"
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define aint(a) a.begin(), a.end()
#define mod (int)(1000000007)
ll pw(ll a, ll b){
ll res=1;
while(b){
if(b&1)
res*=a;
a*=a, b/=2;
}
return res;
}
int gr(ll n){
ll pr=64;
ll l=0, r=64;
while(l<=r){
ll md=(l+r)/2;
if(pw(2, md)>n){
pr=md, r=md-1;
}
else
l=md+1;
}
return pr-1;
}
vector<int> construct_permutation(ll k){
ll j=k;
k--;
vector<int>Base, Ans;
map<int, stack<int>>mp;
int las=0, cur=0;
Base.push_back(-1);
while(k>0){
int mx=min(gr(k), las);
k-=pw(2, mx);
if(mx==las)
Base.push_back(cur++), las++;
else
mp[Base[mx]].push(cur++);
}
for(int i=0;i<Base.size();i++){
if(i)
Ans.push_back(Base[i]);
while(!mp[Base[i]].empty()){
Ans.push_back(mp[Base[i]].top());
mp[Base[i]].pop();
}
}
return Ans;
}
Compilation message
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<Base.size();i++){
| ~^~~~~~~~~~~~
perm.cpp:33:8: warning: unused variable 'j' [-Wunused-variable]
33 | ll j=k;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Partially correct |
4 ms |
340 KB |
Partially correct |
6 |
Correct |
3 ms |
296 KB |
Output is correct |
7 |
Correct |
3 ms |
304 KB |
Output is correct |
8 |
Partially correct |
4 ms |
340 KB |
Partially correct |
9 |
Correct |
3 ms |
340 KB |
Output is correct |
10 |
Partially correct |
4 ms |
340 KB |
Partially correct |
11 |
Partially correct |
4 ms |
380 KB |
Partially correct |
12 |
Partially correct |
5 ms |
340 KB |
Partially correct |
13 |
Partially correct |
4 ms |
340 KB |
Partially correct |