#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;
// }
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
