QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97291#6303. InversionksunhokimWA 2ms3280kbC++201.2kb2023-04-16 17:07:162023-04-16 17:07:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-16 17:07:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3280kb
  • [2023-04-16 17:07:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int cnt = 0;
map<pair<int,int>, bool> cache;

int query(int l, int r) {
  if (l == r)
    return 0;
  if (cache.count({l,r}))
    return cache[{l,r}];
  cnt ++;
  assert(cnt <= 4e4);
  cout << "? " << l + 1 << " " << r + 1 << endl;
  int res;
  cin >> res;
  return cache[{l,r}] = res;
}

bool compare(int i, int j) {
  if (i > j)
    return !compare(j,i);
  if (i == j) {
    return false;
  }
  if (i == j-1) {
    return query(i,j);
  }
  return (query(i, j) - query(i, j-1) - query(i+1, j) + query(i+1, j-1) + 8)%2;
}

int main() {
  int n;
  cin >> n;

  vector<int> A(n);
  iota(begin(A), end(A), 0);

  for (int i=1;i<n;i++) {
    int ng = -1, ok = i;
    while (ok-ng > 1) {
      int m = (ok+ng)/2;
      if (compare(A[m], A[i])) {
        ok = m;
      } else {
        ng = m;
      }
    }
    int tmp = A[i];
    for (int j=ok+1;j<=i;j++){
      A[j] = A[j-1];
    }
    A[ok] = tmp;
  }

  vector<int> ans(n);
  for (int i=0;i<n;i++) ans[A[i]] = i;
  cout << "! ";
  for (int i=0;i<n;i++){
    cout << ans[i] + 1 << " ";
  }
  cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3280kb

input:

3
0
0
1

output:

? 1 2
? 1 3
? 2 3
! 3 1 1 

result:

wrong answer Wa.