Submission #1221723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221723		spetr	Monster Game (JOI21_monster)	C++20	0 / 100	24 ms	408 KiB

monster

#include "monster.h"

namespace {

bool example_variable;

}  

void merge_sort(std::vector<int>& v, int l, int r) {
    if (r - l <= 1) return;
    int mid = (l + r) / 2;
    merge_sort(v, l, mid);
    merge_sort(v, mid, r);

    std::vector<int> result;
    result.reserve(r - l);
    int i = l, j = mid;
    while (i < mid && j < r) {
        bool fight = Query(v[i], v[j]);
        if (fight) {
            result.push_back(v[j]);
            j++;
        } else {
            result.push_back(v[i]);

            i++;
        }
    }
    while (i < mid) {
        result.push_back(v[i]);
        i++;
    }
    while (j < r) {
     result.push_back(v[j]);
     j++;
    }

    for (int k = l; k < r; ++k) {
        v[k] = result[k - l];
    }
}

std::vector<int> Solve(int N) {
  std::vector<int> T(N);

  std::vector<int> cisla(N);
  for (int i = 0; i < N; i++){
    cisla[i] = i;
  }

  merge_sort(cisla, 0, N);

  for (int i = 0; i + 2 < N; i++){
    bool XY = Query(cisla[i], cisla[i+1]);
    bool XZ = Query(cisla[i], cisla[i+2]);

    if (XZ == false){
        if (XY == false){
            int temp = cisla[i];
            cisla[i] = cisla[i+1];
            cisla[i+1] = temp;
        }
    }
    else{
        if (XY == true){
            int temp = cisla[i];
            cisla[i] = cisla[i+1];
            cisla[i+1] = temp;
        }
    }
  }

  for (int i = 0; i < N; i++){
    T[cisla[i]] = i;
  }

  for (int i = 0; i < N; i++) T[i] = (N - 1) - T[i];

  return T;
}

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