#include "bits/stdc++.h"
using namespace std;
//#include "debug.h"
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> ans(n), used(n);
vector<vector<pair<int, int>>> qu;
if (n % 2 == 0) {
// 0 1 2 3 4 5
for (int i = 0; i + 1 < n; i++) {
qu.push_back({{i, n - 1}});
for (int j = 0; j + 1 < n; j++) {
if (j == i) {
continue;
}
int j2 = 2 * i - j;
j2 %= (n - 1);
j2 += n - 1;
j2 %= n - 1;
if (j < j2) {
qu.back().push_back({j, j2});
}
}
}
} else {
// 0 1 2 3 4 5 6
for (int i = 0; i < n; i++) {
qu.push_back({});
for (int j = 0; j < n; j++) {
if (j == i) {
continue;
}
int j2 = 2 * i - j;
j2 %= n;
j2 += n;
j2 %= n;
if (j < j2) {
qu.back().push_back({j, j2});
}
}
}
}
// debug(need, p, cur, qu);
std::shuffle(qu.begin(), qu.end(), gen);
for (auto& arr : qu) {
vector<pair<int, int>> arr2;
for (auto [i, j] : arr) {
if (used[p[i]] && used[p[j]]) {
//
} else {
arr2.push_back({i, j});
}
}
auto dfs = [&] (auto&& self, int l, int r) {
auto q = p;
for (int i = l; i < r; i++) {
swap(q[arr[i].first], q[arr[i].second]);
}
int res = get(q);
if (!res) {
return;
}
if (l + 1 == r) {
auto [x, y] = arr[l];
if (res == 2) {
ans[x] = p[y];
ans[y] = p[x];
used[p[x]] = used[p[y]] = 1;
} else {
if (used[p[x]]) {
ans[x] = p[y];
used[p[y]] = 1;
return;
}
if (used[p[y]]) {
ans[y] = p[x];
used[p[x]] = 1;
return;
}
auto q = p;
swap(q[x], q[y]);
int j = 0;
while (j == x || j == y) j++;
swap(q[x], q[j]);
int value = get(q);
if (value != 0) {
ans[y] = p[x];
used[p[x]] = 1;
} else {
ans[x] = p[y];
used[p[y]] = 1;
}
}
return;
}
int m = (l + r) / 2;
self(self, l, m);
self(self, m, r);
};
dfs(dfs, 0, arr.size());
}
get(ans);
// vector<int> used(n);
// int cur = 0;
//// int iter = 0;
// while (cur < n) {
//// if (iter ++ > 10) break;
// 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) {
// for (auto& [x, y] : arr) {
// x = need[x];
// y = need[y];
// }
// }
//// debug(need, p, cur, qu);
// vector<pair<int, int>> update;
// 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) {
// update.push_back({x, y});
// update.push_back({y, x});
//// 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);
}
//vector<int> want = {1, 5, 3, 4, 2};
//
//int query(vector<int> q) {
// for (auto& x : q) {
// cout << x << " ";
// }
// cout << endl;
// int cnt = 0;
// for (int i = 0; i < (int) q.size(); i++) {
// cnt += q[i] == want[i];
// }
// return cnt;
//}
//
//int main() {
// solve(want.size());
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 28 |
| 2 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 11 |
| 3 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 24 |
| 4 |
Correct |
1 ms |
508 KB |
Correct! Number of queries: 28 |
| 5 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 25 |
| 6 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 33 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 28 |
| 2 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 11 |
| 3 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 24 |
| 4 |
Correct |
1 ms |
508 KB |
Correct! Number of queries: 28 |
| 5 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 25 |
| 6 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 33 |
| 7 |
Correct |
5 ms |
504 KB |
Correct! Number of queries: 500 |
| 8 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 9 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 10 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 11 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 400 |
| 12 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 13 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 14 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 15 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 16 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 28 |
| 2 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 11 |
| 3 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 24 |
| 4 |
Correct |
1 ms |
508 KB |
Correct! Number of queries: 28 |
| 5 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 25 |
| 6 |
Correct |
1 ms |
336 KB |
Correct! Number of queries: 33 |
| 7 |
Correct |
5 ms |
504 KB |
Correct! Number of queries: 500 |
| 8 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 9 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 10 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 11 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 400 |
| 12 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 13 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 14 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 15 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 16 |
Correct |
5 ms |
336 KB |
Correct! Number of queries: 500 |
| 17 |
Correct |
84 ms |
592 KB |
Correct! Number of queries: 3500 |
| 18 |
Correct |
83 ms |
592 KB |
Correct! Number of queries: 3500 |
| 19 |
Correct |
78 ms |
592 KB |
Correct! Number of queries: 3400 |
| 20 |
Correct |
76 ms |
592 KB |
Correct! Number of queries: 3600 |
| 21 |
Correct |
80 ms |
760 KB |
Correct! Number of queries: 3500 |
| 22 |
Correct |
82 ms |
592 KB |
Correct! Number of queries: 3400 |
| 23 |
Correct |
87 ms |
592 KB |
Correct! Number of queries: 3500 |
| 24 |
Correct |
85 ms |
592 KB |
Correct! Number of queries: 3600 |
| 25 |
Correct |
102 ms |
592 KB |
Correct! Number of queries: 3600 |
| 26 |
Correct |
82 ms |
592 KB |
Correct! Number of queries: 3600 |
