QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#407239 | #2293. Boredom Buster | thesupermarketisgoingtome# | RE | 0ms | 0kb | C++20 | 2.9kb | 2024-05-08 11:54:42 | 2024-05-08 11:54:42 |
answer
/*
* author: ADMathNoob
* created: 05/07/24 23:10:54
* problem: https://qoj.ac/problem/2293
*/
/*
Comments about problem:
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif
// vector<int> order;
pair<int, int> Ask(int x, int y) {
// cout << "? " << order[x] + 1 << ' ' << order[y] + 1 << endl;
cout << "? " << x + 1 << ' ' << y + 1 << endl;
int a, b;
cin >> a >> b;
--a; --b;
return {a, b};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
n /= 2;
// order.resize(2 * n);
// iota(order.begin(), order.end(), 0);
// random_shuffle(order.begin(), order.end());
vector<int> pos1(n, -1), pos2(n, -1);
auto Set = [&](int i, int x) {
if (pos1[x] == -1) {
pos1[x] = i;
} else {
pos2[x] = i;
}
debug("set", i, x);
};
auto Solve3 = [&](int i, int j, int k, int x, int y) {
// solves the indices i, j, k, knowing {i, j, k} = {x, y}
// starting with the question i, j
while (true) {
auto [aa, bb] = Ask(i, j);
if (aa == bb) {
pos1[aa] = i;
pos2[aa] = j;
int c1 = x ^ y ^ aa;
Set(k, c1);
return aa;
}
swap(j, k);
}
};
int x = -1;
int y = -1;
int a = -1, b = -1;
int ptr = 0;
while (ptr < 2 * n) {
if (x == -1) {
if (ptr + 1 == 2 * n) {
for (int i = 0; i < n; i++) {
if (pos2[i] == -1) {
pos2[i] = 2 * n - 1;
}
}
break;
}
x = ptr;
y = ptr + 1;
tie(a, b) = Ask(x, y);
ptr += 2;
if (a == b) {
Set(x, a);
Set(y, a);
x = y = -1;
continue;
}
if (pos1[a] != -1 && pos1[b] != -1) {
int twice = Solve3(x, pos1[a], y, a, b);
int once = a ^ b ^ twice;
Set(y, once);
x = y = -1;
} else if (pos1[a] != -1) {
Solve3(pos1[a], x, y, a, b);
x = y = -1;
} else if (pos1[b] != -1) {
Solve3(pos1[b], x, y, a, b);
x = y = -1;
}
continue;
}
assert(y != -1);
auto [c, d] = Ask(x, ptr);
if (c == d) {
Set(x, c);
Set(ptr, c);
Set(y, a ^ b ^ c);
x = y = -1;
ptr += 1;
continue;
}
set<int> s = {a, b, c, d};
if (s.size() == 3) {
int xx = 0;
for (int yy : s) {
xx ^= yy;
}
xx ^= c ^ d;
Set(y, xx);
y = ptr;
a = c;
b = d;
} else {
Solve3(x, y, ptr, a, b);
x = y = -1;
}
ptr += 1;
}
vector<int> ret(2 * n);
for (int i = 0; i < n; i++) {
ret[pos1[i]] = ret[pos2[i]] = i;
// ret[order[pos1[i]]] = ret[order[pos2[i]]] = i;
}
cout << '!';
for (int i = 0; i < 2 * n; i++) {
cout << ' ' << ret[i] + 1;
}
cout << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
100000 14243 13962 13962 6948 6948 22252 19244 22252 19543 19244 19244 11287 38903 11287 8431 38903 8431 38236 8855 38236 44004 38236 38236 28696 32239 38236 38236 13408 13408 4163 34466 4163 26456 4163 16506 4163 34636 4163 19659 4163 17476 4163 17476 41596 45165 17476 8145 45165 44174 8145 32853 8...
output:
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 1 8 ? 1 9 ? 1 10 ? 1 11 ? 1 12 ? 1 13 ? 1 14 ? 1 15 ? 1 16 ? 1 17 ? 1 18 ? 1 19 ? 1 20 ? 1 21 ? 1 22 ? 1 23 ? 1 24 ? 1 25 ? 1 26 ? 1 27 ? 1 28 ? 1 29 ? 1 30 ? 1 31 ? 1 32 ? 1 33 ? 1 34 ? 1 35 ? 1 36 ? 1 37 ? 1 38 ? 1 39 ? 1 40 ? 1 41 ? 1 42 ? 1 43 ? 1 44 ? 1 45 ...