Submission #1053590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053590		juicy	Monster Game (JOI21_monster)	C++17	100 / 100	56 ms	848 KiB

monster

#include "monster.h"

#include <bits/stdc++.h>

using namespace std;

std::vector<int> Solve(int N) {
  auto in = [&](int x) {
    return 0 <= x && x < N;
  };
  function<vector<int>(vector<int>)> mrg = [&](vector<int> A) {
    if (A.size() == 1) {
      return A;
    }
    int md = A.size() / 2;
    auto lt = mrg(vector(A.begin(), A.begin() + md)), rt = mrg(vector(A.begin() + md, A.end()));
    vector<int> res;
    for (int i = 0, j = 0; i < lt.size() || j < rt.size(); ) { 
      if (i < lt.size() && (j == rt.size() || Query(rt[j], lt[i]))) {
        res.push_back(lt[i++]);
      } else {
        res.push_back(rt[j++]);
      }
    }
    return res;
  };
  vector<int> ord(N); iota(ord.begin(), ord.end(), 0);
  ord = mrg(ord);
  int k = min(N, 10);
  vector<int> cnt(k);
  for (int i = 0; i < k; ++i) {
    for (int j = i + 1; j < k; ++j) {
      if (Query(ord[i], ord[j])) {
        ++cnt[i];
      } else {
        ++cnt[j];
      }
    }
  }
  int a = min_element(cnt.begin(), cnt.end()) - cnt.begin();
  int b = min_element(cnt.begin() + a + 1, cnt.end()) - cnt.begin();
  int c = Query(ord[a], ord[b]) ? a : b;
  rotate(ord.begin(), ord.begin() + c, ord.begin() + c + 1);
  for (int i = 1, p = 0; i < N; ++i) {
    int j = i;
    while (!Query(ord[p], ord[j])) {
      ++j;
    }
    reverse(ord.begin() + i, ord.begin() + j + 1);
    p = i = j;
  }
  vector<int> res(N);
  for (int i = 0; i < N; ++i) {
    res[ord[i]] = i;
  }
  return res;
}

Compilation message (stderr)

monster.cpp: In lambda function:
monster.cpp:18:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0, j = 0; i < lt.size() || j < rt.size(); ) {
      |                            ~~^~~~~~~~~~~
monster.cpp:18:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0, j = 0; i < lt.size() || j < rt.size(); ) {
      |                                             ~~^~~~~~~~~~~
monster.cpp:19:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |       if (i < lt.size() && (j == rt.size() || Query(rt[j], lt[i]))) {
      |           ~~^~~~~~~~~~~
monster.cpp:19:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |       if (i < lt.size() && (j == rt.size() || Query(rt[j], lt[i]))) {
      |                             ~~^~~~~~~~~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:8:8: warning: variable 'in' set but not used [-Wunused-but-set-variable]
    8 |   auto in = [&](int x) {
      |        ^~

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