QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355509#2293. Boredom Busterckiseki#WA 307ms10300kbC++204.3kb2024-03-16 18:50:172024-03-16 18:50:24

Judging History

你现在查看的是最新测评结果

  • [2024-03-16 18:50:24]
  • 评测
  • 测评结果:WA
  • 用时:307ms
  • 内存:10300kb
  • [2024-03-16 18:50:17]
  • 提交

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).