QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110759 | #6303. Inversion | ethening | WA | 241ms | 5700kb | C++17 | 992b | 2023-06-03 21:21:35 | 2023-06-03 21:21:37 |
Judging History
answer
#include "bits/stdc++.h"
#include <array>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int main() {
int n;
cin >> n;
vector<int> v;
v.push_back(1);
auto ask = [](int x, int y) -> int {
if (x == y) return 0;
static map<pii, int> M;
auto iter = M.find({x, y});
if (iter == M.end()) {
cout << "? " << x << " " << y << endl;
int ans;
cin >> ans;
return M[{x, y}] = ans;
}
else {
return iter->second;
}
};
auto smaller = [&](int x, int y) {
return (ask(x + 1, y) == ask(x, y));
};
for (int i = 2; i <= n; i++) {
int l = 0;
int r = i - 1;
while (l < r) {
int mid = (l + r) / 2;
if (smaller(v[mid], i)) {
l = mid + 1;
}
else {
r = mid;
}
}
v.insert(begin(v) + l, i);
}
vector<int> ans(n + 1);
for (int i = 0; i < n; i++) {
ans[v[i]] = i + 1;
}
cout << "! ";
for (int i = 1; i <= n; i++) {
cout << ans[i] << " \n"[i == n];
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3396kb
input:
3 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 241ms
memory: 5700kb
input:
1993 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0...
output:
? 1 2 ? 2 3 ? 3 4 ? 2 4 ? 4 5 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 2 6 ? 5 6 ? 4 6 ? 4 7 ? 3 7 ? 2 7 ? 1 7 ? 6 7 ? 5 7 ? 3 8 ? 2 8 ? 6 8 ? 5 8 ? 7 8 ? 3 9 ? 2 9 ? 5 9 ? 4 9 ? 3 10 ? 2 10 ? 6 10 ? 5 10 ? 1 10 ? 3 11 ? 2 11 ? 5 11 ? 4 11 ? 10 11 ? 9 11 ? 3 12 ? 2 12 ? 4 12 ? 7 12 ? 6 12 ? 10 13 ? 9 13 ? 5 13 ? 4...
result:
wrong answer Wa.