QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97205#6303. InversionksunhokimWA 188ms3344kbC++201.5kb2023-04-16 16:18:412023-04-16 16:18:45

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 16:18:45]
  • 评测
  • 测评结果:WA
  • 用时:188ms
  • 内存:3344kb
  • [2023-04-16 16:18:41]
  • 提交

answer

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

int query(int l, int r) {
  if (l == r)
    return 0;
  cout << "? " << l + 1 << " " << r + 1 << endl;
  int res;
  cin >> res;
  return 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;
}

void merge(vector<int>& arr, int L, int M, int R) {
  vector<int> res;
  int left = L, right = M+1;
  while (left <= M && right <= R) {
    if (compare(arr[left], arr[right])) {
      res.push_back(arr[left]);
      left++;
    } else {
      res.push_back(arr[right]);
      right++;
    }
  }
  while (left <= M) {
    res.push_back(arr[left]);
    left++;
  }
  while (right <= R) {
    res.push_back(arr[right]);
    right++;
  }
  for (int i=L;i<=R;i++) {
    arr[i] = res[i-L];
  }
}

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

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

  auto merge_sort = [&](auto self, int L, int R) -> void {
    if (L == R) {
      return;
    }
    int M = (R+L)/2;
    self(self, L, M);
    self(self, M+1, R);
    merge(A, L, M, R);
  };
  merge_sort(merge_sort, 0, n-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: 2ms
memory: 3340kb

input:

3
0
1
0
0
1

output:

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

result:

ok OK, guesses=5

Test #2:

score: -100
Wrong Answer
time: 188ms
memory: 3344kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected