QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#745914#9432. PermutationguosounWA 1ms3836kbC++172.5kb2024-11-14 12:23:302024-11-14 12:23:30

Judging History

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

  • [2024-11-14 12:23:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3836kb
  • [2024-11-14 12:23:30]
  • 提交

answer

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

struct hope {
  int n;
  std::vector<int> p;
  hope(int n) : n(n), p(n) {
    std::iota(p.begin(), p.end(), 0);
    std::shuffle(p.begin(), p.end(), std::mt19937());
    for (int i : p) std::cerr << i << ' ';
    std::cerr << '\n';
  }
  int query(std::vector<int> a) {
    auto na = a;
    for (int i = 0; i < n; i++) na[p[i]] = a[i];
    std::cout << 0 << ' ';
    for (int i : na) std::cout << i << ' ';
    std::cout << std::endl;
    int ret;
    std::cin >> ret;
    return ret;
  }
  void answer(std::vector<int> a) {
    auto na = a;
    for (int i = 0; i < n; i++) na[p[i]] = a[i];
    std::cout << 1 << ' ';
    for (int i : a) std::cout << i << ' ';
    std::cout << std::endl;
  }
};

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int n;
  std::cin >> n;
  hope ia(n);
  if (n == 1) return ia.answer({1}), 0;
  std::vector<int> a(n);
  auto solve = [&](auto &self, int l, int r, std::vector<int> v) {
    assert((int)v.size() == r - l + 1);
    if (l == r) return a[l] = v[0], void();
    int mid = (l + r) >> 1;
    std::vector<std::vector<int>> cv;
    std::vector<int> lv, rv;
    for (int i : v) cv.push_back({i});
    while (cv.size()) {
      if (cv.size() == 1) {
        auto a = cv[0];
        cv.pop_back();
        int ev = -1;
        if (lv.size()) ev = lv[0];
        else {
          for (int i = 1; i <= n; i++)
            if (std::find(v.begin(), v.end(), i) == v.end())
              ev = i;
        }
        assert(ev != -1);
        std::vector<int> q(n, ev);
        for (int i = l; i <= mid; i++) q[i] = a[0];
        if (ia.query(q))
          lv.insert(lv.end(), a.begin(), a.end());
        else
          rv.insert(rv.end(), a.begin(), a.end());
        continue;
      }
      auto a = cv.back();
      cv.pop_back();
      auto b = cv.back();
      cv.pop_back();
      std::vector<int> q(n, a[0]);
      for (int i = mid + 1; i <= r; i++) q[i] = b[0];
      if (int t = ia.query(q); t == 1) {
        a.insert(a.end(), b.begin(), b.end());
        cv.push_back(a);
      } else if (t == 2) {
        lv.insert(lv.end(), a.begin(), a.end());
        rv.insert(rv.end(), b.begin(), b.end());
      } else {
        lv.insert(lv.end(), b.begin(), b.end());
        rv.insert(rv.end(), a.begin(), a.end());
      }
    }
    self(self, l, mid, lv);
    self(self, mid + 1, r, rv);
  };
  std::vector<int> v(n);
  std::iota(v.begin(), v.end(), 1);
  solve(solve, 0, n - 1, v);
  ia.answer(a);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3836kb

input:

5
2
0
1
1
2
0
2

output:

0 4 4 5 5 5 
0 2 2 3 3 3 
0 5 5 1 1 1 
0 1 1 1 1 2 
0 1 1 1 1 5 
0 2 2 1 2 2 
0 3 4 3 3 3 
1 1 2 5 3 4 

result:

wrong answer Wrong Anser