QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#450285#6303. Inversionnhuang685WA 72ms19332kbC++201.7kb2024-06-22 07:33:492024-06-22 07:33:50

Judging History

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

  • [2024-06-22 07:33:50]
  • 评测
  • 测评结果:WA
  • 用时:72ms
  • 内存:19332kb
  • [2024-06-22 07:33:49]
  • 提交

answer

/**
 * @file qoj6303-1.cpp
 * @author n685
 * @brief
 * @date 2024-06-21
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

auto main() -> int {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  std::cin >> n;

  std::vector<int> ind;
  std::vector dp(n + 1, std::vector<int>(n + 1));
  auto query = [&](int l, int r) -> int {
    if (r > std::ssize(ind)) {
      std::cout << "? " << l << ' ' << r << '\n' << std::flush;
      int v;
      std::cin >> v;
      return v;
    } else {
      return dp[l][r] % 2;
    }
  };
  auto gr = [&](int l, int r) -> bool {
    if (r - l == 1) {
      return query(l, r);
    } else {
      return query(l, r) - query(l + 1, r) - query(l, r - 1) +
             query(l + 1, r - 1);
    }
  };

  for (int i = 1; i <= n; ++i) {
    int l = 0, r = i - 2;
    while (l < r) {
      int mid = (l + r) / 2;
      if (gr(ind[mid], i)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    if (l == i - 2 && !gr(ind[l], i)) {
      l = i - 1;
    }
    ind.insert(ind.begin() + l, i);
    std::vector<int> p(i + 1);
    for (int j = 0; j < i; ++j) {
      p[ind[j]] = j;
    }
    dp[i - 1][i] = (p[i - 1] > p[i]);
    for (int j = i - 2; j >= 1; --j) {
      dp[j][i] = (dp[j + 1][i] + dp[j][i - 1] - dp[j + 1][i - 1]) % 2;
      if (dp[j][i] < 0) {
        dp[j][i] += 2;
      }
    }
  }
  std::vector<int> p(n + 1);
  for (int j = 0; j < n; ++j) {
    p[ind[j]] = j;
  }
  std::cout << "! ";
  for (int i = 1; i <= n; ++i) {
    std::cout << p[i] + 1 << ' ';
  }
  std::cout << '\n' << std::flush;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 72ms
memory: 19332kb

input:

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

output:

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

result:

wrong answer Wa.