QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97298#6303. InversionksunhokimWA 150ms4420kbC++201.4kb2023-04-16 17:14:332023-04-16 17:14:34

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:14:34]
  • 评测
  • 测评结果:WA
  • 用时:150ms
  • 内存:4420kb
  • [2023-04-16 17:14:33]
  • 提交

answer

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

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

vector<int> hidden = {2,3,1};

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;
  #ifdef HIDDEN
  int rr = 0;
  for (int i=l;i<=r;i++){
    for (int j=l;j<=i;j++){
      if (hidden[j] > hidden[i]) {
        rr++;
      }
    }
  }
  res = rr%2;
  #endif
  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[i], A[m])) {
        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;
  }
  reverse(begin(A), end(A));
  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;
}

// 2 1

// 3 1 2
// 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3284kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 150ms
memory: 4420kb

input:

1993
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
1
1
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
1
0
0
1
1
1
0
1
1
0
1
1
0
1
0
0
0
0
1
1
0
1
0
0
1
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
1
0
1
1
0
0
0
0
1
0
1
1
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
0
1
0...

output:

? 1 2
? 2 3
? 2 4
? 3 4
? 3 5
? 4 5
? 3 6
? 4 6
? 5 6
? 3 7
? 4 7
? 6 7
? 5 7
? 3 8
? 4 8
? 5 8
? 6 8
? 7 8
? 3 9
? 4 9
? 6 9
? 7 9
? 8 9
? 8 10
? 9 10
? 6 10
? 7 10
? 8 11
? 9 11
? 6 11
? 7 11
? 10 11
? 9 12
? 10 12
? 3 12
? 3 11
? 4 12
? 4 11
? 8 12
? 12 13
? 3 13
? 4 13
? 5 13
? 5 12
? 4 14
? 5 1...

result:

wrong answer Wa.