QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407235#2293. Boredom Busterthesupermarketisgoingtome#RE 0ms0kbC++202.7kb2024-05-08 11:44:082024-05-08 11:44:09

Judging History

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

  • [2024-05-08 11:44:09]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-08 11:44:08]
  • 提交

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 {
      assert(pos2[x] == -1);
      pos2[x] = i;
    }
  };
  
  auto Solve3 = [&](int i, int j, int k, int x, int y) {
    // solves the indices i, j, k, knowing {i, j, k} = {x, y}
    while (true) {
      auto [a, b] = Ask(i, j);
      if (a == b) {
        pos1[a] = i;
        pos2[a] = j;
        int c1 = x ^ y ^ a;
        Set(k, c1);
        return a;
      }
      swap(j, k);
    }
  };
  
  int x = -1;
  int y = -1;
  int a, b;
  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(pos1[a], pos1[b], x, 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);
    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);
    }
    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
...

result: