Submission #419967

#	Time	Username	Problem	Language	Result	Execution time	Memory
419967		schse	Monster Game (JOI21_monster)	C++17	10 / 100	233 ms	460 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

std::vector<int>
Solve(int N)
{
  std::vector<int> T(N);
  vector<int> winns(N);
  vector<vector<bool>> answs(N, vector<bool>(N, false));
  for (int i = 0; i < N; i++)
    for (int e = 0; e < i; e++)
    {
      bool b = Query(i, e);
      winns[b ? i : e]++;
      answs[i][e] = b;
      answs[e][i] = !b;
    }
  vector<int> l, f;
  for (int i = 0; i < N; i++)
  {
    if (winns[i] == 1)
      f.push_back(i);
    else if (winns[i] == N - 2)
      l.push_back(i);
    else
      T[i] = winns[i];
  }
  if (answs[l[1]][l[0]])
    swap(l[0], l[1]);
  T[l[0]] = N - 2;
  T[l[1]] = N - 1;

  if (answs[f[1]][f[0]])
    swap(f[0], f[1]);
  T[f[0]] = 0;
  T[f[1]] = 1;

  return T;
}

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