QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355509 | #2293. Boredom Buster | ckiseki# | WA | 307ms | 10300kb | C++20 | 4.3kb | 2024-03-16 18:50:17 | 2024-03-16 18:50:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
pair<int, int> ask(int p1, int p2) {
printf("? %d %d\n", p1, p2);
fflush(stdout);
int x, y;
scanf("%d%d", &x, &y);
return {x, y};
}
map<int, int> ans;
map<pair<int, int>, pair<int, int>> known;
map<int, tuple<int, int, int>> has;
void SolvePair(int, int, int, int);
bool SolveSingle(int p1, int p2, int v, int oth) {
auto it = has.find(v);
if (it == has.end())
return false;
debug("single", p1, p2, v, oth);
auto [p3, p4, w] = it->second;
known.erase(minmax(v, w));
has.erase(v), has.erase(w);
auto [v1, v2] = ask(p1, p3);
debug(p1, p3, v1, v2);
if (v1 == v2) {
ans[p1] = ans[p3] = v1;
ans[p2] = oth;
ans[p4] = w;
return true;
}
if (v1 == v) {
if (v2 == oth) {
ans[p2] = v;
ans[p4] = w;
} else {
assert(v2 == w);
ans[p2] = oth;
ans[p4] = v;
}
} else if (v2 == v) {
if (v1 == oth) {
ans[p2] = v;
ans[p4] = w;
} else {
assert(v1 == w);
ans[p2] = oth;
ans[p4] = v;
}
} else {
assert((v1 == oth and v2 == w) or (v1 == w and v2 == oth));
debug(v, v);
ans[p2] = v;
ans[p4] = v;
}
SolvePair(p1, p3, v1, v2);
return true;
}
bool SolveKnown(int p1, int p2, int v1, int v2) {
debug("SolveKnown", p1, p2, v1, v2);
auto it = known.find(minmax(v1, v2));
if (it == known.end())
return false;
auto [p3, p4] = it->second;
known.erase(it);
has.erase(v1), has.erase(v2);
debug(p3, p4);
while (true) {
auto [w1, w2] = ask(p1, p3);
if (w1 == w2) {
ans[p1] = ans[p3] = w1;
ans[p2] = ans[p4] = v1 ^ v2 ^ w1;
break;
}
auto [w3, w4] = ask(p1, p2);
if (w3 == w4) {
ans[p1] = ans[p2] = w3;
ans[p3] = ans[p4] = v1 ^ v2 ^ w3;
break;
}
}
return true;
}
void SolvePair(int p1, int p2, int v1, int v2) {
debug("Pair", p1, p2, v1, v2);
if (v1 == v2) {
ans[p1] = v1;
ans[p2] = v2;
return;
}
if (SolveKnown(p1, p2, v1, v2))
return;
if (SolveSingle(p1, p2, v1, v2))
return;
if (SolveSingle(p1, p2, v2, v1))
return;
known[minmax(v1, v2)] = {p1, p2};
has[v1] = {p1, p2, v2};
has[v2] = {p1, p2, v1};
}
void Solve2(int p1, int p2, int v1, int v2, int p3, int p4, int v3, int v4) {
debug("Solve2", p1, p2, v1, v2, p3, p4, v3, v4);
auto [w1, w2] = ask(p1, p3);
known[minmax(w1, w2)] = {p1, p3};
if (w1 != v1 and w1 != v2)
swap(w1, w2);
assert(w2 == v3 or w2 == v4);
ans[p2] = v1 ^ v2 ^ w1;
ans[p4] = v3 ^ v4 ^ w2;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i += 2) {
auto [x, y] = ask(i, i + 1);
SolvePair(i, i + 1, x, y);
#ifdef CKISEKI
{
vector<int> wtf;
for (int j = 1; j <= n; ++j)
wtf.push_back(ans[j]);
orange(all(wtf));
}
#endif
}
while (known.size() > 1) {
auto [vs1, ps1] = *known.begin();
known.erase(known.begin());
auto [vs2, ps2] = *known.begin();
known.erase(known.begin());
Solve2(ps1.first, ps1.second, vs1.first, vs1.second, ps2.first, ps2.second, vs2.first, vs2.second);
#ifdef CKISEKI
{
vector<int> wtf;
for (int j = 1; j <= n; ++j)
wtf.push_back(ans[j]);
orange(all(wtf));
}
#endif
}
if (known.size() == 1) {
auto vs = known.begin()->first;
debug(vs.first, vs.second);
int p1 = -1, p2 = -1;
for (int i = 1; i <= n; ++i) {
if (ans[i] == vs.first)
p1 = i;
if (ans[i] == vs.second)
p2 = i;
}
assert(p1 != -1 and p2 != -1);
assert(SolveKnown(p1, p2, vs.first, vs.second));
}
printf("!");
for (int i = 1; i <= n; ++i)
printf(" %d", ans[i]);
putchar('\n');
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 307ms
memory: 10300kb
input:
100000 14243 13962 6948 22252 19244 19543 38903 11287 38236 8431 8855 44004 32239 28696 4163 13408 34466 26456 34636 16506 17476 19659 41596 45165 44174 8145 32853 13855 13860 32650 39829 40439 26857 16321 28351 11239 14823 35976 18843 47987 13886 18541 1370 15381 16164 41277 10418 10077 1431 40902 ...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
wrong answer Wrong answer: Too many guesses: 92330 (which is 330 over).