#include "bits/stdc++.h"
using namespace std;
int query(vector<int> q);
int get(vector<int> q) {
for (auto& x : q) {
x++;
}
int res = query(q);
if (res == (int) q.size()) {
exit(0);
}
return res;
}
mt19937 gen(22);
void solve(int n) {
if (n == 1) {
get({1});
return;
}
vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
while (get(p) > 0) {
std::shuffle(p.begin(), p.end(), gen);
}
vector<int> used(n);
int cur = 0;
while (cur < n) {
vector<int> need;
for (int i = 0; i < n; i++) {
if (!used[i]) {
need.push_back(i);
}
}
const int m = (int) need.size();
vector<vector<pair<int, int>>> qu;
if (m % 2 == 0) {
// 0 1 2 3 4 5
for (int i = 0; i + 1 < m; i++) {
qu.push_back({{i, m - 1}});
for (int j = 0; j + 1 < m; j++) {
if (j == i) {
continue;
}
int j2 = 2 * i - j;
j2 %= (m - 1);
j2 += m - 1;
j2 %= m - 1;
if (j < j2) {
qu.back().push_back({j, j2});
}
}
}
} else {
// 0 1 2 3 4 5 6
for (int i = 0; i < m; i++) {
qu.push_back({});
for (int j = 0; j < m; j++) {
if (j == i) {
continue;
}
int j2 = 2 * i - j;
j2 %= m;
j2 += m;
j2 %= m;
if (j < j2) {
qu.back().push_back({j, j2});
}
}
}
}
for (auto& arr : qu) {
auto q = p;
for (auto [x, y] : arr) {
swap(q[x], q[y]);
}
int res = get(q);
if (res > cur) {
int l = -1, r = (int) arr.size() - 1, value = res;
while (l + 1 < r) {
int m = (l + r) / 2;
q = p;
for (int i = 0; i <= m; i++) {
swap(q[arr[i].first], q[arr[i].second]);
}
int res2 = get(q);
if (res2 > cur) {
r = m;
value = res2;
} else {
l = m;
}
}
auto [x, y] = arr[r];
if (value - cur == 2) {
swap(p[x], p[y]);
used[x] = used[y] = 1;
} else {
swap(p[x], p[y]);
cur = value;
int j = 0;
while (j < n && (!used[j] || j == x || j == y)) {
j++;
}
if (j < n) {
q = p;
swap(q[x], q[j]);
value = get(q);
if (cur - value == 2) {
used[x] = 1;
} else {
used[y] = 1;
}
} else {
j = 0;
while (j == x || j == y) j++;
q = p;
swap(q[x], q[j]);
value = get(q);
if (cur - value == 1) {
used[x] = 1;
} else {
used[y] = 1;
}
}
}
break;
}
}
cur = std::accumulate(used.begin(), used.end(), 0);
}
get(p);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
440 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
440 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
440 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
