Submission #1158821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158821		Der_Vlapos	Monster Game (JOI21_monster)	C++20	91 / 100	29 ms	420 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define pb push_back

bool cmp(int a, int b)
{
  return Query(a, b);
}

vector<int> tryMerge(int l, int r)
{
  if (r - l == 1)
    return {l};
  int m = (l + r) >> 1;
  vector<int> v1 = tryMerge(l, m);
  vector<int> v2 = tryMerge(m, r);
  int u1 = 0, u2 = 0;
  vector<int> ans;
  while (u1 < v1.size() or u2 < v2.size())
  {
    if (u1 == v1.size())
      ans.pb(v2[u2++]);
    else if (u2 == v2.size())
      ans.pb(v1[u1++]);
    else
    {
      if (cmp(v1[u1], v2[u2]))
        ans.pb(v2[u2++]);
      else
        ans.pb(v1[u1++]);
    }
  }
  return ans;
}

std::vector<int> Solve(int N)
{
  int n = N;
  vector<int> cur = tryMerge(0, n);

  int p, pr = -1;
  for (p = n - 1; p > 0; --p)
  {
    pr = p;
    {
      p--;
      while (p - 1 >= 0 and cmp(cur[p - 1], cur[pr]))
        p--;
      // check if on q[cur[p - 1]] == q[pr] - 1

      int bor = p;
      if (p + 2 < pr)
      {
        if (!cmp(cur[p], cur[p + 2]))
          bor = p + 1;
      }
      else if (pr + 1 < n)
      {
        if (!cmp(cur[p], cur[pr + 1]))
        {
          bor = p + 1;
        }
      }
      else
      {
        // is on cur[p] == 99
        int cnt1 = 1, cnt2 = 0;
        for (int i = 0; i < pr - 1; ++i)
        {
          cnt1 += cmp(cur[pr], cur[i]);
          cnt2 += cmp(cur[pr - 1], cur[i]);
        }

        if (cnt1 != n - 2)
          bor = p;
        else
        {
          if (cnt2 != n - 2)
          {
            p = pr;
            bor = pr + 1;
          }
          else
          {
            bor = pr - 1;
          }
        }
      }
      reverse(cur.begin() + bor, cur.begin() + pr + 1);
    }
  }
  vector<int> ans(n);
  {
    int p = 0;
    for (int el : cur)
    {
      ans[el] = p++;
    }
  }
  return ans;
}

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