QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99443 | #6303. Inversion | rgnerdplayer# | WA | 294ms | 18864kb | C++20 | 2.3kb | 2023-04-22 15:41:40 | 2023-04-22 15:41:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
// [l, r]
uniform_int_distribution<int> uni(l, r);
return uni(rng);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
auto solve = [&]() {
int n;
cin >> n;
vector<int> ord{0};
vector inv(n, vector<int>(n));
for (int i = 1; i < n; i++) {
auto ask = [&](int l, int r) {
#ifdef LOCAL
vector<int> p{5, 1, 2, 4, 3};
int res = 0;
for (int x = l; x <= r; x++) {
for (int y = x + 1; y <= r; y++) {
res ^= p[x] > p[y];
}
}
return res;
#else
if (l != r && r == i) {
cout << "? " << l + 1 << ' ' << r + 1 << endl;
int res;
cin >> res;
return res;
} else {
return inv[l][r] % 2;
}
#endif
};
int low = 0, high = ord.size();
while (low < high) {
int mid = low + high >> 1;
int j = ord[mid];
if ((ask(j, i) ^ ask(j + 1, i) ^ ask(j, i - 1) ^ ask(j + 1, i - 1)) != 0) {
high = mid;
} else {
low = mid + 1;
}
}
for (int j = low; j < int(ord.size()); j++) {
inv[ord[j]][i] = 1;
}
for (int j = i - 1; j >= 0; j--) {
inv[j][i] += inv[j][i] + inv[j + 1][i];
}
ord.insert(ord.begin() + low, i);
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[ord[i]] = i;
}
cout << '!';
for (int i = 0; i < n; i++) {
cout << ' ' << ans[i] + 1;
}
cout << endl;
};
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3444kb
input:
3 0 1 0 1
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=4
Test #2:
score: -100
Wrong Answer
time: 294ms
memory: 18864kb
input:
1993 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 4 ? 3 5 ? 4 5 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 2 6 ? 3 6 ? 4 6 ? 5 6 ? 3 7 ? 4 7 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 2 8 ? 3 8 ? 5 8 ? 6 8 ? 7 8 ? 2 9 ? 3 9 ? 4 9 ? 5 9 ? 3 9 ? 4 9 ? 2 10 ? 3 10 ? 5 10 ? 6 10 ? 1 10 ? 2 10 ? 2 11 ? 3 11 ? 4 11 ? 5 11 ? 3 11 ? 4 11 ? 9 11 ? 10 11 ? 2 12 ? ...
result:
wrong answer Wa.