QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97368#6303. InversionksunhokimWA 279ms65372kbC++202.2kb2023-04-16 17:57:032023-04-16 17:57:06

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:57:06]
  • 评测
  • 测评结果:WA
  • 用时:279ms
  • 内存:65372kb
  • [2023-04-16 17:57:03]
  • 提交

answer

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

int cnt = 0;
int cache[2001][2001];
int cache2[2001][2001];

// #define HIDDEN

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

int query(int l, int r) {
  if (l == r)
    return 0;
  if (cache[l][r] != -1)
    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 (cache2[i][j] != -1)
    return cache2[i][j];
  if (i == j) {
    return false;
  }
  if (i == j-1) {
    return cache2[i][j] = query(i,j);
  }
  return cache2[i][j] = (query(i, j) - query(i, j-1) - query(i+1, j) + query(i+1, j-1) + 8)%2;
}

int main() {
  memset(cache, -1, sizeof(cache));
  memset(cache2, -1, sizeof(cache2));

  int n;
  cin >> n;

  // unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  // hidden.assign(n,0);
  // iota(begin(hidden), end(hidden),0);
  // shuffle(begin(hidden), end(hidden), std::default_random_engine(seed));

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

  vector<vector<ll>> inv(n, vector<ll>(n));

  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=i;j>=ok+1;j--){
      A[j] = A[j-1];
    }
    A[ok] = tmp;

    int cnt = 0;
    for (int j=i-1;j>=0;j--) {
      if (A[j] < tmp) 
        cnt ++;
      inv[A[j]][i] = inv[A[j]][i-1] + cnt;
      if (A[j] < tmp) {
        cache[A[j]][tmp] = inv[j][i] % 2;
      } else {
        cache[tmp][A[j]] = (inv[j][i] % 2)^1;
      }
    }
  }
  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: 0ms
memory: 34556kb

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: 279ms
memory: 65372kb

input:

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

output:

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

result:

wrong answer Wa.