제출 #420203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420203		rama_pang	Monster Game (JOI21_monster)	C++17	100 / 100	128 ms	1500 KiB

monster

#include "monster.h"

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

vector<int> Solve(int N) {
  int query_count = 0;
  map<pair<int, int>, int> memo;
  const auto Compare = [&](int a, int b) {
    if (memo.count({a, b})) return memo[{a, b}];
    query_count++;
    int foo = Query(a, b);
    memo[{a, b}] = foo;
    memo[{b, a}] = 1 - foo;
    return foo;
  };

  const auto MergeSort = [&](const auto &self, int l, int r) -> vector<int> {
    // S result will look like: [6 7 8][3 4 5][1 2]
    // Groups of consecutive elements i, i+1, ..., sorted decreasingly
    // There are no adjacent groups with both size 1
    // There are at least 2 groups

    if (l == r) return {l};
    int md = (l + r) / 2;
    vector<int> lft = self(self, l, md);
    vector<int> rgt = self(self, md + 1, r);

    vector<int> res;
    reverse(begin(lft), end(lft));
    reverse(begin(rgt), end(rgt));

    while (!lft.empty() && !rgt.empty()) {
      if (Compare(lft.back(), rgt.back())) {
        res.emplace_back(lft.back());
        lft.pop_back();
      } else {
        res.emplace_back(rgt.back());
        rgt.pop_back();
      }
    }
    while (!lft.empty()) {
      res.emplace_back(lft.back());
      lft.pop_back();
    }
    while (!rgt.empty()) {
      res.emplace_back(rgt.back());
      rgt.pop_back();
    }

    return res;
  };

  vector<int> almostSorted = MergeSort(MergeSort, 0, N - 1);

  // If we can find maximum element in almostSorted[], we can recover the sorted[] easily
  // Just, from maximum element, sweep to front. Delete all involved.
  // Then, from first elements, we sweep until we hit a false query. This must be
  // the second maximum elements, so we can recurse.
  //
  // How to find maximum element?
  // For first element, go sweep until we hit WRONG 2 times. Then, first element must not
  // be maximum. Continue from the first time we hit WRONG.
  //
  // Then, if we only hit WRONG once, it is either max or second max. The one which is WRONG
  // must be current-1. Check whether the one which is wrong is max or second max (WRONG occurs
  // once). If it is, then by the structure of almostSorted[],  then current must be max.
  //
  // If current is second max, we must find max. But due to the structure of almostSorted[],
  // the next element after current must be max.
  //
  // So we need 2N queries to identify max, and an additional N queries to get sort[].
  // This gets 92-94 points.
  //
  // Note that, using the merge sort takes at most 8977 queries (\sum_{i = 1}^{1000} ceil(log2(i))).
  // Alternatively: N log N - N.
  // Now we have 1023 queries left to identify sorted[].
  //
  // Of those 1023 queries, we need 1000 to construct sorted[]. Through casebashing,
  // we need around N + constant queries to find max and recover sorted[]. Thus the total
  // number of queries <= 10000.
  //
  // Total queries: N log N.

  const auto FindMaxSpecial = [&](int start) -> int {
    // find max in almostSorted[start...]
    // assuming almostSorted[start, start + 2] is in a group
    for (int i = start + 1; i + 2 < N; i++) {
      if (Compare(almostSorted[i], almostSorted[i + 2])) {
        // looks like: 4 5 0 (Compare 4 <-> 0)
        // Compare(x, x - 1) will never occur
        return i + 1;
      }
    }
    // everything in 1 group
    return N - 1;
  };

  vector<int> sorted;
  vector<int> done(N);

  int mxId = -1;
  int last = 0;

  if (Compare(almostSorted[0], almostSorted[2])) {
    // - 3 4 1 2 ..
    // - 3 0 1 2 ..
    if (Compare(almostSorted[1], almostSorted[3])) {
      mxId = 1;
    } else {
      mxId = 0;
    }
  } else {
    // - 3 4 5 6 ...
    // - 3 4 5 2 ...
    // - 3 4 5 0 ...
    // - 3 1 2 0 ...
    // - 3 4 2 0 ...
    if (Compare(almostSorted[0], almostSorted[3])) {
      // - 3 4 5 0 ...
      // - 3 1 2 0 ...
      // - 3 4 2 0 ...
      if (Compare(almostSorted[1], almostSorted[3])) {
        // - 3 4 5 0 1
        // - 3 4 5 1 2 ...
        // - 3 4 2 0 1 ...
        // - 4 5 3 0 1 ...
        // - 4 2 3 0 1 ...
        assert(N >= 5);
        if (!Compare(almostSorted[1], almostSorted[4])) {
          // - 5 3 4 1 2 ...
          mxId = 4;
          last = 3;
          done[0] = done[1] = done[2] = 1;
          sorted.emplace_back(almostSorted[0]);
          sorted.emplace_back(almostSorted[2]);
          sorted.emplace_back(almostSorted[1]);
        } else if (Compare(almostSorted[2], almostSorted[4])) {
          // - 3 4 5 0 1 ...
          // - 3 4 5 1 2 ...
          // - 4 5 3 0 1 ...
          // - 5 3 4 0 1 ...
          if (Compare(almostSorted[0], almostSorted[4])) {
            // - 3 4 5 0 1 2 ...
            // - 4 5 3 0 1 2 ...
            // - 5 3 4 0 1 2 ...
            assert(N >= 6);
            last = 3;
            mxId = FindMaxSpecial(3);
            if (!Compare(almostSorted[0], almostSorted[mxId])) {
              // - 3 4 5 0 1 2 ...
              done[0] = done[1] = done[2] = 1;
              sorted.emplace_back(almostSorted[2]);
              sorted.emplace_back(almostSorted[1]);
              sorted.emplace_back(almostSorted[0]);
            } else if (!Compare(almostSorted[1], almostSorted[mxId])) {
              // - 5 3 4 0 1 2 ...
              done[0] = done[1] = done[2] = 1;
              sorted.emplace_back(almostSorted[0]);
              sorted.emplace_back(almostSorted[2]);
              sorted.emplace_back(almostSorted[1]);
            } else if (!Compare(almostSorted[2], almostSorted[mxId])) {
              // - 4 5 3 0 1 2 ...
              done[0] = done[1] = done[2] = 1;
              sorted.emplace_back(almostSorted[1]);
              sorted.emplace_back(almostSorted[0]);
              sorted.emplace_back(almostSorted[2]);
            }
          } else {
            // - 3 4 5 1 2 ...
            mxId = 2;
          }
        } else {
          // - 3 4 2 0 1 ...
          mxId = 1;
        }
      } else {
        // - 3 1 2 0 ...
        mxId = 0;
      }
    } else {
      // - 3 4 5 6 ...
      // - 3 4 5 2 ...
      mxId = FindMaxSpecial(0);
    }
  }

  for (int i = mxId; i >= 0; i--) if (!done[i]) {
    done[i] = 1;
    sorted.emplace_back(almostSorted[i]);
  }
  for (int i = mxId + 1; i < N; i++) {
    if (!Compare(almostSorted[last], almostSorted[i])) {
      last = i;
      while (!done[last]) {
        done[last] = 1;
        sorted.emplace_back(almostSorted[last]);
        last--;
      }
      last++;
    }
  }

  assert(sorted.size() == N);
  vector<int> ans(N);
  for (int i = 0; i < N; i++) {
    ans[sorted[i]] = i;
  }
  for (int i = 0; i < N; i++) {
    ans[i] = N - 1 - ans[i];
  }
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from monster.cpp:3:
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:204:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  204 |   assert(sorted.size() == N);
      |          ~~~~~~~~~~~~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75