QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883114 | #9734. Identify Chord | guosoun | RE | 0ms | 3584kb | C++17 | 2.3kb | 2025-02-05 14:46:05 | 2025-02-05 14:46:06 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
using V = std::vector<T>;
template <class T>
void chkmin(T &x, const T &y) {
if (x > y) x = y;
}
using ll = long long;
int query(int x, int y) {
std::cout << "? " << x + 1 << ' ' << y + 1 << std::endl;
int r;
std::cin >> r;
return r;
}
void answer(int x, int y) {
std::cout << "! " << x + 1 << ' ' << y + 1 << std::endl;
int r;
std::cin >> r;
assert(r == 1);
}
std::mt19937 rnd(10);
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
int m = n * 2;
auto qo = [&](int u) {
int r = 1e9, v = (u + m / 2) % m;
chkmin(r, query(u / 2, v / 2));
if (u & 1) chkmin(r, query(u / 2 + 1, v / 2));
if (v & 1) chkmin(r, query(u / 2, v / 2 + 1));
if ((u & 1) && (v & 1)) chkmin(r, query(u / 2 + 1, v / 2 + 1));
return r * 2 + (u & 1) + (v & 1);
};
auto solve1 = [&](int u, int l) {
int s = (n - l + 1) / 2;
if (query(u, (u + s) % n) == s && query(u, (u + s + 1) % n) != s + 1) {
if (query((u + s + l / 2) % n, ((u + s + l / 2 - l) % n + n) % n) == 1)
return answer((u + s + l / 2) % n, ((u + s + l / 2 - l) % n + n) % n);
u = (u + s) % n;
}
int d = 0;
for (int i = 30; i >= 0; i--)
while (query(u, (u + d + (1 << i)) % n) == d + (1 << i))
d += (1 << i);
answer((u + d + l / 2) % n, ((u + d + l / 2 - l) % n + n) % n);
};
auto solve2 = [&](int u) {
int l = std::min(qo((u + m / 4) % m), qo((u + m / 4 + 1) % m));
l = m / 2 - l + 2;
if (query((u - l / 2 + m) % m / 2, (u + l / 2) % m / 2) != 1)
u = (u + m / 2) % m;
answer((u - l / 2 + m) % m / 2, (u + l / 2) % m / 2);
};
int d0 = qo(0), d1 = qo(1);
if (d0 == d1) {
if (d0 == m / 2) {
int p = 0;
if (qo((p + 1) % m) != m / 2) p = (p - 1 + m) % m;
if (qo((p - 1 + m) % m) != m / 2) p = (p + 1) % m;
solve2(p);
} else
solve1(0, (m / 2 - d0 + 2) / 2);
} else {
int c = (m / 2 - d0) / 2;
int p = (d0 < d1 ? c : (-c + m) + m) % m;
assert(qo(p) == m / 2);
if (qo((p + 1) % m) != m / 2) p = (p - 1 + m) % m;
if (qo((p - 1 + m) % m) != m / 2) p = (p + 1) % m;
solve2(p);
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 6 2 2 1 2 2 2 2 1 1 4 1 1 1 1 2 1 1 1 2 2 1 1 1 1 2 1 1 1
output:
? 1 4 ? 1 4 ? 2 4 ? 1 5 ? 2 5 ? 1 3 ? 1 4 ? 4 2 ! 4 2 ? 1 3 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 2 4 ? 1 3 ? 3 1 ? 4 1 ? 3 2 ? 4 2 ? 3 1 ? 1 3 ! 1 3
result:
ok ok (2 test cases)
Test #2:
score: -100
Runtime Error
input:
1000 15 5 6 6 5 6 5 1 1 19 5 4 4 3 9 9 9 8 9 9 1 2 2 1 2 1 17 5 4 4 3 8 8 8 7 8 8 1 2 2 1 2 1 15 6 7 7 7 7 7 7 7 6 7 7 6 6 7 1 1 14 5 5 4 6 5 4 6 2 2 6 2 2 6 2 2 6 2 2 6 2 2 6 2 2 6 2 2 6 2 2 6 2 2 6 2 2 2 3 2 1 15 3 2 2 1 7 7 7 6 7 7 1 2 2 1 2 1 17 8 8 8 8 8 8 8
output:
? 1 8 ? 1 9 ? 1 9 ? 2 9 ? 1 7 ? 1 8 ? 8 5 ! 8 5 ? 1 10 ? 1 11 ? 1 11 ? 2 11 ? 17 8 ? 18 8 ? 18 8 ? 18 9 ? 16 7 ? 17 7 ? 3 12 ? 3 13 ? 2 12 ? 3 12 ? 12 2 ! 3 12 ? 1 9 ? 1 10 ? 1 10 ? 2 10 ? 16 7 ? 16 8 ? 16 8 ? 17 8 ? 15 6 ? 15 7 ? 3 11 ? 3 12 ? 2 11 ? 3 11 ? 11 2 ! 3 11 ? 1 8 ? 1 9 ? 1 9 ? 2 9 ? 1 9...