oj.uz

답안 #420203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420203 2021-06-08T07:35:34 Z rama_pang Monster Game (JOI21_monster) C++17
100 / 100
 128 ms 1500 KB 
#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;
}

Compilation message

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 200 KB Output is correct
14 Correct 1 ms 200 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 21 ms 412 KB Output is correct
17 Correct 18 ms 356 KB Output is correct
18 Correct 14 ms 388 KB Output is correct
19 Correct 16 ms 348 KB Output is correct
20 Correct 21 ms 376 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 10 ms 328 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 256 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 10 ms 472 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 200 KB Output is correct
14 Correct 1 ms 200 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 21 ms 412 KB Output is correct
17 Correct 18 ms 356 KB Output is correct
18 Correct 14 ms 388 KB Output is correct
19 Correct 16 ms 348 KB Output is correct
20 Correct 21 ms 376 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 10 ms 328 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 256 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 10 ms 472 KB Output is correct
33 Correct 102 ms 1320 KB Output is correct
34 Correct 85 ms 1384 KB Output is correct
35 Correct 106 ms 1392 KB Output is correct
36 Correct 128 ms 1472 KB Output is correct
37 Correct 94 ms 1384 KB Output is correct
38 Correct 120 ms 1324 KB Output is correct
39 Correct 99 ms 1364 KB Output is correct
40 Correct 88 ms 1412 KB Output is correct
41 Correct 115 ms 1440 KB Output is correct
42 Correct 119 ms 1448 KB Output is correct
43 Correct 43 ms 948 KB Output is correct
44 Correct 117 ms 980 KB Output is correct

Subtask #3
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 1376 KB Output is correct
2 Correct 121 ms 1440 KB Output is correct
3 Correct 94 ms 1412 KB Output is correct
4 Correct 122 ms 1456 KB Output is correct
5 Correct 126 ms 1340 KB Output is correct
6 Correct 111 ms 1224 KB Output is correct
7 Correct 67 ms 1240 KB Output is correct
8 Correct 123 ms 1388 KB Output is correct
9 Correct 110 ms 1364 KB Output is correct
10 Correct 125 ms 1500 KB Output is correct
11 Correct 80 ms 1352 KB Output is correct
12 Correct 117 ms 1404 KB Output is correct
13 Correct 109 ms 1264 KB Output is correct
14 Correct 109 ms 1140 KB Output is correct
15 Correct 66 ms 864 KB Output is correct
16 Correct 64 ms 860 KB Output is correct
17 Correct 63 ms 936 KB Output is correct
18 Correct 114 ms 1340 KB Output is correct