Submission #1061025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061025		kunzaZa183	Monster Game (JOI21_monster)	C++17	88 / 100	81 ms	4692 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

namespace {

bool example_variable;

} // namespace

const int maxn = 1000;
vector<vector<int>> vvi(maxn,vector<int>(maxn,-1));

bool Qry(int a,int b)
{
  if(vvi[a][b] == -1)
  {
    vvi[a][b] = Query(a,b);
    vvi[b][a] = 1 - vvi[a][b];
  }
  return vvi[a][b];
}

vector<int> Solve(int N) {
  vector<int> vi(N);
  vi.resize(N);
  iota(vi.begin(), vi.end(), 0);

  function<vector<int>(int, int)> merge = [&](int l, int r) {
    if (l == r) {
      return vector<int>(1, vi[l]);
    }
    vector<int> vi;

    int mid = (l + r) / 2;
    vector<int> vi2 = merge(l, mid), vi3 = merge(mid + 1, r);

    int in1 = 0, in2 = 0;
    while (in1 < vi2.size() && in2 < vi3.size()) {
      if (Qry(vi2[in1], vi3[in2])) {
        vi.push_back(vi3[in2]);
        in2++;
      } else {
        vi.push_back(vi2[in1]);
        in1++;
      }
    }

    while (in1 < vi2.size()) {
      vi.push_back(vi2[in1]);
      in1++;
    }

    while (in2 < vi3.size()) {
      vi.push_back(vi3[in2]);
      in2++;
    }

    return vi;
  };

  vector<int> ovi = merge(0, N - 1);

  // for (auto a : ovi)
  //   cout << a << " ";
  // cout << "\n";

  vector<int> vpii;

  for (int i = 0; i < N; i++) {
    int winct = 0;
    for (int j = 0; j < N; j++) {
      if (i != j) {
        if (Qry(ovi[i], ovi[j])) {
          winct++;
          if (winct == 2) {
            break;
          }
        }
      }
    }
    if (winct < 2) {
      vpii.push_back(i);
    }
  }

  assert(vpii.size() == 2);

  int curr;
  if (Qry(ovi[vpii[0]], ovi[vpii[1]])) {
    curr = vpii[0];
  } else {
    curr = vpii[1];
  }
  // cout << ovi[curr] << "\n";

  vector<int> orans(N, -1);

  int curval = 0, curl;
  while (1) {
    for (int i = curr; i >= 0; i--) {
      if (orans[i] != -1)
        break;
      orans[i] = curval++;
      curl = i;
    }

    for (int i = curr + 1; 1; i++) {
      if (i == N)
        goto A;
      if (Qry(ovi[curl], ovi[i])) {
        curr = i;
        break;
      }
    }
  }
A:;

  vector<int> ans(N);
  for (int i = 0; i < N; i++)
    ans[ovi[i]] = orans[i];

  return ans;
}

Compilation message (stderr)

monster.cpp: In lambda function:
monster.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while (in1 < vi2.size() && in2 < vi3.size()) {
      |            ~~~~^~~~~~~~~~~~
monster.cpp:40:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while (in1 < vi2.size() && in2 < vi3.size()) {
      |                                ~~~~^~~~~~~~~~~~
monster.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while (in1 < vi2.size()) {
      |            ~~~~^~~~~~~~~~~~
monster.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while (in2 < vi3.size()) {
      |            ~~~~^~~~~~~~~~~~
monster.cpp: At global scope:
monster.cpp:8:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
    8 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:112:23: warning: 'curl' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |       if (Qry(ovi[curl], ovi[i])) {
      |                       ^

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