QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #647810 | #8239. Mysterious Tree | yixuanoct# | TL | 1ms | 3656kb | C++20 | 4.1kb | 2024-10-17 15:47:07 | 2024-10-17 15:47:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, x, y, z;
cin >> n;
int cnt = 0, a = 0, b = 0;
for (int i = 1;i < n;i += 2) {
cout << "? " << i << ' ' << i + 1 << '\n';
cout.flush();
cin >> x;
if (x == 1) {
cnt++;
a = i;
b = i + 1;
}
}
if (n & 1) {
if (cnt == 0) {
cout << "? " << n << ' ' << 1 << '\n';
cout.flush();
cin >> x;
cout << "? " << n << ' ' << 2 << '\n';
cout.flush();
cin >> y;
cout << "? " << n << ' ' << 3 << '\n';
cout.flush();
cin >> z;
if (x == 1 && y == 1 && z == 1) {
cout << "! 2\n";
cout.flush();
}
else {
cout << "! 1\n";
cout.flush();
}
}
else if (cnt == 1) {
int a1 = (a == n - 2 ? 1 : a + 2);
int a2 = (a1 == n - 2 ? 1 : a1 + 2);
int b1 = (b == n - 1 ? 2 : b + 2);
int b2 = (b1 == n - 1 ? 2 : b1 + 2);
cout << "? " << a << ' ' << b1 << '\n';
cout.flush();
cin >> x;
cout << "? " << a1 << ' ' << b << '\n';
cout.flush();
cin >> y;
if (x == y) {
cout << "! 1\n";
cout.flush();
}
else {
if (x == 1) {
cout << "? " << a << ' ' << b2 << '\n';
cout.flush();
cin >> x;
if (x == 1) {
cout << "! 2\n";
cout.flush();
}
else {
cout << "! 1\n";
cout.flush();
}
}
else {
cout << "? " << a2 << ' ' << b << '\n';
cout.flush();
cin >> x;
if (x == 1) {
cout << "! 2\n";
cout.flush();
}
else {
cout << "! 1\n";
cout.flush();
}
}
}
}
}
else {
if (cnt == 1) {
int a1 = (a == n - 1 ? 1 : a + 2);
int a2 = (a1 == n - 1 ? 1 : a1 + 2);
int b1 = (b == n ? 2 : b + 2);
int b2 = (b1 == n ? 2 : b1 + 2);
cout << "? " << a << ' ' << b1 << '\n';
cout.flush();
cin >> x;
cout << "? " << a1 << ' ' << b << '\n';
cout.flush();
cin >> y;
if (x == y) {
cout << "! 1\n";
cout.flush();
}
else {
if (x == 1) {
cout << "? " << a << ' ' << b2 << '\n';
cout.flush();
cin >> x;
if (x == 1) {
cout << "! 2\n";
cout.flush();
}
else {
cout << "! 1\n";
cout.flush();
}
}
else {
cout << "? " << a2 << ' ' << b << '\n';
cout.flush();
cin >> x;
if (x == 1) {
cout << "! 2\n";
cout.flush();
}
else {
cout << "! 1\n";
cout.flush();
}
}
}
}
else {
cout << "! 1\n";
cout.flush();
}
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int _ = 1;
cin >> _;
while (_--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
2 4 1 1 4 0 1 1 0 1
output:
? 1 2 ? 3 4 ! 1 ? 1 2 ? 3 4 ? 3 2 ? 1 4 ? 3 4 ! 2
result:
ok Correct (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
87 13 0 0 0 0 0 1 0 1 1 15 0 0 0 0 0 0 1 1 0 1 7 0 0 0 1 1 1 15 0 0 0 1 1 0 0
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 11 2 ? 1 12 ? 3 12 ! 2 ? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 13 2 ? 1 14 ? 13 4 ! 2 ? 1 2 ? 3 4 ? 5 6 ? 7 1 ? 7 2 ? 7 3 ! 2 ? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14