#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int a[11], answer[N];
vector<int> save[N];
int cal(vector<int> v){
int ans = 0;
for(int i = 0; i < (1LL << v.size()); i++){
vector<int> v2;
bool ok = 1;
for(int j = 0; j < v.size(); j++){
if(i & (1LL << j)) v2.pb(v[j]);
}
for(int j = 1; j < v2.size(); j++) ok &= (v2[j] > v2[j - 1]);
ans += ok;
}
return ans;
}
vector<int> construct_permutation(ll k){
for(int i = 1; i <= 6; i++) a[i] = i;
do{
int pos1, pos2;
for(int i = 1; i <= 6; i++){
if(a[i] == 1) pos1 = i;
if(a[i] == 2) pos2 = i;
}
if(pos1 < pos2) continue;
vector<int> x;
for(int i = 1; i <= 6; i++) x.pb(a[i]);
save[cal(x)] = x;
}while(next_permutation(a + 1, a + 7));
//for(auto it : save[10]) cout << it << " ";
//cout << "\n";
if(k <= 8){
vector<int> temp;
for(int i = k - 2; i >= 0; i--) temp.pb(i);
return temp;
}
vector<int> bits;
while(k){
bits.pb(k % 2);
k /= 2;
}
reverse(bits.begin(), bits.end());
assert(bits[0] == 1);
//cout << bits[0] * 8 + bits[1] * 4 + bits[2] * 2 + bits[3] << "\n";
//exit(0);
for(int i = 1; i <= 6; i++) answer[i] = save[bits[0] * 8 + bits[1] * 4 + bits[2] * 2 + bits[3]][i - 1];
int cnt = 6;
for(int i = 4; i < bits.size(); i += 2){
if(i == bits.size() - 1){
cnt++;
answer[cnt] = cnt;
if(bits[i] == 1){
for(int j = 1; j <= cnt; j++) answer[j]++;
cnt++;
answer[cnt] = 1;
}
break;
}
cnt++;
answer[cnt] = cnt;
cnt++;
answer[cnt] = cnt;
int tempo = bits[i] * 2 + bits[i + 1];
if(!tempo) continue;
vector<int> x;
for(int j = 1; j <= cnt; j++) x.pb(answer[j]);
//cout << cal(x) << "\n";
if(tempo == 1){
//cout << "OK1\n";
for(int j = 1; j <= cnt; j++) answer[j]++;
cnt++;
answer[cnt] = 1;
}
else if(tempo == 2){
//cout << "OK2\n";
for(int j = cnt; j >= 1; j--) answer[j + 1] = answer[j];
cnt++;
for(int j = 2; j <= cnt; j++) if(answer[j] == (cnt - 1)) answer[j]++;
answer[1] = cnt - 1;
}
else{
//cout << "OK3\n";
//int pos1, pos2;
for(int j = 1; j <= cnt; j++) if(answer[j] > 2) answer[j]++;
cnt++;
answer[cnt] = 3;
}
x.clear();
for(int j = 1; j <= cnt; j++) x.pb(answer[j]);
int pos1, pos2;
//cout << cal(x) << "\n";
for(int j = 1; j <= cnt; j++){
if(answer[j] == 1) pos1 = j;
if(answer[j] == 2) pos2 = j;
}
//cout << "P " << pos1 << " " << pos2 << "\n";
}
vector<int> a;
for(int i = 1; i <= cnt; i++) a.pb(answer[i] - 1);
return a;
}
//int n, a[N];
/*
void process(){
int q;
cin >> q;
while(q--){
int x;
cin >> x;
vector<int> temp = construct_permutation(x);
cout << cal(temp) << "\n";
for(auto it : temp) cout << it << " ";
cout << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}*/
Compilation message
perm.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
perm.cpp: In function 'int cal(std::vector<int>)':
perm.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int j = 0; j < v.size(); j++){
| ~~^~~~~~~~~~
perm.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j = 1; j < v2.size(); j++) ok &= (v2[j] > v2[j - 1]);
| ~~^~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 4; i < bits.size(); i += 2){
| ~~^~~~~~~~~~~~~
perm.cpp:71:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if(i == bits.size() - 1){
| ~~^~~~~~~~~~~~~~~~~~
perm.cpp:112:7: warning: variable 'pos1' set but not used [-Wunused-but-set-variable]
112 | int pos1, pos2;
| ^~~~
perm.cpp:112:13: warning: variable 'pos2' set but not used [-Wunused-but-set-variable]
112 | int pos1, pos2;
| ^~~~
perm.cpp:47:3: warning: 'pos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
47 | if(pos1 < pos2) continue;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
202 ms |
2656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
202 ms |
2656 KB |
Output is correct |
| 3 |
Correct |
219 ms |
2660 KB |
Output is correct |
| 4 |
Correct |
220 ms |
2896 KB |
Output is correct |
| 5 |
Correct |
219 ms |
2660 KB |
Output is correct |
| 6 |
Correct |
218 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
222 ms |
2792 KB |
Output is correct |
| 8 |
Correct |
255 ms |
2668 KB |
Output is correct |
| 9 |
Correct |
214 ms |
2656 KB |
Output is correct |
| 10 |
Correct |
257 ms |
2788 KB |
Output is correct |
| 11 |
Correct |
218 ms |
2684 KB |
Output is correct |
| 12 |
Correct |
222 ms |
2664 KB |
Output is correct |
| 13 |
Correct |
236 ms |
2776 KB |
Output is correct |
