#include<bits/stdc++.h>
#include "perm.h"
#define pb push_back
using namespace std;
vector<int> construct_permutation(long long k){
vector<long double> tmp;
int itr = 0;
bool used = false;
long double ngungu = 1.5;
int pos = 1e9, neg = -1;
vector<int> xx;
while(k){
xx.pb(k % 4);
k /= 4;
}
reverse(xx.begin(), xx.end());
for(int m : xx){
if(!itr){
if(m == 2)
tmp = {0};
else if(m == 3){
tmp = {1, 0};
// used = true;
}
}
else{
if(!m){
tmp.pb(pos);
tmp.pb(pos + 1);
pos += 2;
}
else if(m == 1){
tmp.pb(pos);
tmp.pb(pos + 1);
tmp.pb(neg);
pos += 2;
--neg;
// used = true;
}
else if(m == 2){
tmp.pb(pos);
tmp.pb(neg);
tmp.pb(pos + 1);
pos += 2;
--neg;
// used = true;
}
else{
if(!used){
// used = true;
tmp.pb(pos);
tmp.pb(neg);
tmp.pb(pos + 1);
tmp.pb(neg - 1);
pos += 2;
neg -= 2;
}
// else{
// tmp.pb(pos);
// tmp.pb(pos + 1);
// tmp.pb(ngungu);
// pos += 2;
// ngungu += 5.0;
// }
}
}
++itr;
}
vector<int> ans;
vector<long double> t1 = tmp;
sort(t1.begin(), t1.end());
for(auto &i : tmp)
ans.pb(i = lower_bound(t1.begin(), t1.end(), i) - t1.begin());
// for(int i : ans)
// cout << i << " ";
// cout << "\n";
return ans;
}
//static bool check_permutation(vector<int> v)
//{
// sort(v.begin(),v.end());
// for(int i=0;i<v.size();i++)
// if(v[i]!=i) return 0;
// return 1;
//}
//
//long long count_increasing(const vector<int>& v) {
// vector<long long> dp(v.size() + 1, 0);
// dp[0] = 1;
// for (int x : v)
// {
// for (int i = 0; i <= x; i++)
// {
// dp[x+1] += dp[i];
// dp[x+1] = min(dp[x+1],1000000000000000001);
// }
// }
// long long result = 0;
// for (int i = 0; i <= (int)v.size(); i++){
// result += dp[i];
// result = min(result,1000000000000000001);
// }
// return result;
//}
//
//
//int main(){
// long long k;
// cin >> k;
// vector<int> v = construct_permutation(k);
// if(!check_permutation(v)){
// cout << k << " Not a permutation.";
// return 0;
// }
// if(count_increasing(v) != k){
// cout << "Differ.\n";
// cout << k << " " << count_increasing(v) << "\n";
// return 0;
// }
//}
Compilation message
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:10:17: warning: unused variable 'ngungu' [-Wunused-variable]
10 | long double ngungu = 1.5;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Partially correct |
2 ms |
348 KB |
Partially correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Partially correct |
2 ms |
348 KB |
Partially correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 11 |
Partially correct |
2 ms |
348 KB |
Partially correct |
| 12 |
Partially correct |
2 ms |
348 KB |
Partially correct |
| 13 |
Partially correct |
2 ms |
460 KB |
Partially correct |
