QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#97201	#6303. Inversion	ksunhokim	RE	0ms	3340kb	C++20	1.5kb	2023-04-16 16:16:20	2023-04-16 16:16:23

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:16:23]
评测

测评结果：RE
用时：0ms
内存：3340kb

查看

[2023-04-16 16:16:20]
提交

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];
  }
}

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;
    }
    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
//

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3340kb

input:

output:

result:

ok OK, guesses=5

Test #2:

score: -100

Runtime Error

input:

output:

? 1 2
? 3 4
? 1 2
? 5 6
? 7 8
? 1 34
? 1 33
? 2 34
? 2 33
? 1 34
? 1 33
? 2 34
? 2 33
? 1 2
? 1 34
? 1 33
? 2 34
? 2 33
? 1 34
? 1 33
? 2 34
? 2 33
? 1 34
? 1 33
? 2 34
? 2 33
? 9 10
? 11 12
? -1702776815 1