Submission #600325

#	Time	Username	Problem	Language	Result	Execution time	Memory
600325		Plurm	Monster Game (JOI21_monster)	C++17	10 / 100	209 ms	848 KiB

monster

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

namespace {

int qrs[256][256];

}  // namespace

vector<int> Solve(int N) {
  vector<int> T(N, -1);
  for(int i = 0; i < N; i++){
    for(int j = i+1; j < N; j++){
      qrs[i][j] = Query(i, j);
      qrs[j][i] = !qrs[i][j];
    }
  }
  set<int> rem;
  vector<int> cdd;
  for(int i = 0; i < N; i++){
    int sw = 0;
    for(int j = 0; j < N; j++){
      if(i == j) continue;
      if(qrs[i][j]){
        sw++;
      }
    }
    if(sw == N-2){
      cdd.push_back(i);
    }
  }
  if(cdd.size() == 2){
    if(!qrs[cdd.front()][cdd.back()]){
      T[cdd.front()] = N-1;
    }else{
      T[cdd.back()] = N-1;
    }
  }else{
    printf("Something is wrong at start\n");
  }
  for(int it = 0; it < N-1; it++){
    cdd.clear();
    for(int i = 0; i < N; i++){
      if(rem.count(i)) continue;
      int sw = 0;
      for(int j = 0; j < N; j++){
        if(rem.count(j)) continue;
        if(i == j) continue;
        if(qrs[i][j]){
          sw++;
        }
      }
      if(sw == 1){
        cdd.push_back(i);
      }
    }
    if(cdd.size() == 3){
      for(int i = 0; i < 3; i++){
        if(T[cdd[i]] == N-1){
          cdd.erase(cdd.begin()+i);
          break;
        }
      }
    }
    if(cdd.size() == 2){
      if(qrs[cdd.front()][cdd.back()]){
        T[cdd.front()] = it;
        rem.insert(cdd.front());
      }else{
        T[cdd.back()] = it;
        rem.insert(cdd.back());
      }
    }else if(cdd.size() == 1){
      T[cdd.back()] = it;
    }else{
      printf("Something is wrong at %d: %d %d %d\n", it, cdd[0], cdd[1], cdd[2]);
    }
  }
  return T;
}

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