#include "perm.h"
#include "bits/stdc++.h"
using namespace std;
static long long MX=1e18;
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],MX+1);
}
}
long long result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
result = min(result,MX+1);
}
return result;
}
int fastlog(long long x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
mt19937_64 rng((long long)std::chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long x, long long y) {
long long u = uniform_int_distribution<long long>(x, y)(rng); return u;
}
std::vector<int> construct_permutation(long long k)
{
if(k == 1) return {};
if(k == 2) return {0};
if(k == 3) return {1, 0};
if(k == 4) return {0, 1};
//cout << "Solve(" << k <<")\n";
long long x, c, rem;
long long sq = sqrt(k);
while(1) {
x = rnd(2, sq);
c = k / x;
rem = k % x;
if(rem < 3) break;
}
//cout << x << " " << c << " " << rem << "\n";
vector<int> cur = {};
vector<int> l = construct_permutation(c);
vector<int> r = construct_permutation(x);
for(int q: l) cur.push_back(q);
for(int q: r) cur.push_back(q + (int) l.size());
int n = cur.size();
vector<int> now;
for(int i=rem-1; i>=0; i--) now.push_back(i + n);
for(int q: cur) now.push_back(q);
cur = now;
return cur;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
212 KB |
Output is correct |
5 |
Execution timed out |
1093 ms |
212 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |