#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else
#define debug(...)
#endif
template<typename T>
ostream& operator << (ostream& out, vector<T> vals) {
for(auto& i : vals) {
out << i << " ";
}
return out;
}
// i hypothesize that we can greedily append to a permutation the greatest number that will not make the increasing sequences > k and that this will terminate with at most 90 numbers
// we can get 2 ^ k - 1 with 1, 2, 3, 4, ... k
// n - (2 ^ k - 1) will not have a bit higher than k set
// 2 ^ k - 1 is what the numbers are
// so after we get close we can use the 2 ^ k - 1 and we do this at most k times?
// v*2 + 1, greatest will become (answer - 1) / 2
// v*2 - greatest
// + 1
// + 1 + smallest = 1 + 1 = 2
// + 1 + smallest + second smallest = 1 + 1 + 1 or 2 = 3 or 4
void mul2(vector<int>& vals) {
vals[0] += 1;
vals.push_back(sz(vals));
}
void add1(vector<int>& vals) {
for(int& i : vals) {
i++;
}
vals.push_back(1);
}
void add3(vector<int>& vals) {
for(int& i : vals) {
i += (i > 2);
}
vals.push_back(3);
}
vector<int> construct_permutation(ll k) {
if(k == 1) {
return vector<int>(0);
}
k -= 1;
vector<int> bits;
for(int i = 0, cnt = 0; i < 62; i++) {
if((k >> i) & 1) {
bits.resize(sz(bits) + cnt, 0);
bits.push_back(1);
cnt = 0;
} else {
cnt++;
}
}
debug(bits);
debug(sz(bits));
assert(k > 0);
bool fadd1 = 0;
bits.pop_back();
vector<int> ret(1, 1);
while(sz(bits) > 1) {
int a = bits.back();
bits.pop_back();
int b = bits.back();
bits.pop_back();
if(a == 0 && b == 0) {
mul2(ret);
mul2(ret);
}
if(a == 0 && b == 1) {
mul2(ret);
mul2(ret);
add1(ret);
fadd1 = 1;
}
if(a == 1 && b == 0) {
mul2(ret);
add1(ret);
mul2(ret);
fadd1 = 1;
}
if(a == 1 && b == 1 && !fadd1) {
mul2(ret);
add1(ret);
mul2(ret);
add1(ret);
fadd1 = 1;
} else if(a == 1 && b == 1 && fadd1) {
mul2(ret);
mul2(ret);
add3(ret);
}
}
if(sz(bits) == 1 && bits[0] == 0) {
mul2(ret);
}
if(sz(bits) == 1 && bits[0] == 1) {
ret.push_back(sz(ret) + 1);
}
for(int& i : ret) {
i -= 1;
}
debug(ret);
return ret;
}
#ifdef LOCmain
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll k;
cin >> k;
vector<int> val = construct_permutation(k);
debug(val);
vector<ll> dp(sz(val) + 1, 0);
for(int& crn : val) {
for(int i = 0; i < crn; i++) {
dp[crn] += dp[i];
}
dp[crn] += 1;
}
debug(dp);
ll incs = 0;
for(ll& i : dp) {
incs += i;
}
debug(incs);
assert(sz(val) <= 90);
assert(incs == k);
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
2 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
304 KB |
Output is correct |
| 12 |
Correct |
2 ms |
340 KB |
Output is correct |
| 13 |
Correct |
2 ms |
300 KB |
Output is correct |
