Submission #420203

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
420203	2021-06-08T07:35:34 Z	rama_pang	Monster Game (JOI21_monster)	C++17	100 / 100	128 ms	1500 KB

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

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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

Submission #420203

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 15.0 / 15.0

Subtask #3 75.0 / 75.0

Subtask #1
10.0 / 10.0

Subtask #2
15.0 / 15.0

Subtask #3
75.0 / 75.0