Submission #894065

#	Time	Username	Problem	Language	Result	Execution time	Memory
894065		MilosMilutinovic	Monster Game (JOI21_monster)	C++17	91 / 100	60 ms	1364 KiB

monster

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

using namespace std;

namespace {

bool example_variable;

}  // namespace

vector<int> Solve(int n) {
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  vector<int> tmp(n);
  function<void(int, int)> MergeSort = [&](int l, int r) {
    if (l == r) {
      return;
    }
    int mid = l + r >> 1;
    MergeSort(l, mid);
    MergeSort(mid + 1, r);
    for (int i = l; i <= r; i++) {
      tmp[i] = order[i];
    }
    int pl = l, pr = mid + 1;
    int ptr = l;
    while (pl <= mid || pr <= r) {
      if (pl > mid) {
        order[ptr++] = tmp[pr++];
      } else if (pr > r) {
        order[ptr++] = tmp[pl++];
      } else {
        order[ptr++] = (Query(tmp[pl], tmp[pr]) ? tmp[pl++] : tmp[pr++]);
      }
    }
  };
  MergeSort(0, n - 1);
  int pos = -1;
  vector<int> bad;
  for (int i = 1; i < n; i++) {
    if (!Query(order[0], order[i])) {
      bad.push_back(i);
    }
  }
  if ((int) bad.size() > 1) {
    pos = bad.rbegin()[1];
  } else {
    bool ok = true;
    for (int i = 2; i < n; i++) {
      if (!Query(order[1], order[i])) {
        ok = false;
        break;
      }
    }
    if (ok) {
      pos = 1;
    } else {
      pos = 0;
    }
  }
  vector<int> res;
  function<void(int, int)> Solve = [&](int l, int r) {
    for (int i = r; i >= l; i--) {
      res.push_back(order[i]);
    }
    if (r == n - 1) {
      return;
    }
    for (int i = r + 1; i < n; i++) {
      if (!Query(order[l], order[i])) {
        Solve(r + 1, i);
        break;
      }
    }
  };
  Solve(0, pos);
  reverse(res.begin(), res.end());
  vector<int> ret(n);
  for (int i = 0; i < n; i++) {
    ret[res[i]] = i;
  }
  return ret;
}

Compilation message (stderr)

monster.cpp: In lambda function:
monster.cpp:20:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int mid = l + r >> 1;
      |               ~~^~~
monster.cpp: At global scope:
monster.cpp:8:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
    8 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

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