Submission #1221846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221846		slivajan	Monster Game (JOI21_monster)	C++20	25 / 100	87 ms	3532 KiB

monster

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

using un = int;
using vuc = vector<un>;
using vol = vector<bool>;

#define REP(i, a, b) for (un i = (un)a ; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

std::map<pair<un, un>, bool> cache;

std::mt19937 seed(3589037);

bool first_wins(un a, un b){
  if (cache.find({a, b}) != cache.end()) return cache[{a, b}];

  cache[{a, b}] = Query(a, b);
  cache[{b, a}] = not cache[{a, b}];
  return cache[{a, b}];
}

/*
jaky = true <=> nejvetsi

return the best + drops the best from the input
*/
un spocti_nej(vuc& vstup, bool jaky){

  un index = 0;
  REP(i, 1, vstup.size()){
    if (first_wins(vstup[index], vstup[i]) != jaky) index = i;
  }

  un ret = vstup[index];

  swap(vstup[index], vstup.back());
  vstup.pop_back();

  return ret;
}

vuc serad(vuc vstup, un dole, un nahore){
  un N = vstup.size();
  shuffle(ALL(vstup), seed);

  if (N == 1) return vstup;

  if (N == 2){
    if (not first_wins(vstup[0], vstup[1])) reverse(ALL(vstup));
    return vstup;
  }
  
  if (N == 3){
    if (dole != -1){
      un nejmensi;
      REP(i, 0, 3){
        if (first_wins(dole, vstup[i])){
          nejmensi = i;
          break;
        }
      }

      un stredni;
      un nejvetsi;

      REP(i, 0, 3){
        if (nejmensi == i) continue;
        if (not first_wins(vstup[nejmensi], vstup[i])){
          nejvetsi = i;
          stredni = 3 - nejmensi - nejvetsi;
          break;
        }
        else{
          stredni = i;
          nejvetsi = 3 - nejmensi - stredni;
          break;
        }
      }

      return {vstup[nejmensi], vstup[stredni], vstup[nejvetsi]};
    }

    if (nahore != -1){
      un nejvetsi;
      REP(i, 0, 3){
        if (first_wins(vstup[i], nahore)){
          nejvetsi = i;
          break;
        }
      }

      un stredni;
      un nejmensi;

      REP(i, 0, 3){
        if (nejvetsi == i) continue;
        if (not first_wins(vstup[i], vstup[nejvetsi])){
          nejmensi = i;
          stredni = 3 - nejmensi - nejvetsi;
          break;
        }
        else{
          stredni = i;
          nejmensi = 3 - nejvetsi - stredni;
          break;
        }
      }

      return {vstup[nejmensi], vstup[stredni], vstup[nejvetsi]};
    }
  }

  if (N == 4){
    vuc wins(4, 0);

    REP(i, 0, 4) REP(j, i+1, 4) {
      if (first_wins(vstup[i], vstup[j])) wins[i]++;
      else wins[j]++;
    }

    vuc male;
    vuc velke;

    REP(i, 0, 4){
      if (wins[i] == 1) male.push_back(vstup[i]);
      else if (wins[i] == 2) velke.push_back(vstup[i]);
    }

    vuc predek = serad(male, -1, -1);
    vuc zadek = serad(velke, -1, -1);

    return {predek[0], predek[1], zadek[0], zadek[1]};
  }

  while(true) {
    vuc prvky = vstup;

    shuffle(ALL(prvky), seed);
    un pivot = prvky.back(); prvky.pop_back();

    vuc L, R;

    FEAC(p, prvky){
      if (not first_wins(p, pivot)) L.push_back(p);
      else R.push_back(p);
    }

    if ((L.size() == 1) or (R.size() == 1)) continue;

    shuffle(ALL(L), seed);
    shuffle(ALL(R), seed);
    
    un L_max = spocti_nej(L, true);
    un R_min = spocti_nej(R, false);

    vuc L_res = serad(L, dole, R_min);
    vuc R_res = serad(R, L_max, nahore);

    vuc res;
    res.insert(res.end(), ALL(L_res));
    res.push_back(R_min);
    res.push_back(pivot);
    res.push_back(L_max);
    res.insert(res.end(), ALL(R_res));

    return res;
  }

}

std::vector<int> Solve(int N) {
  cache.clear();

  vuc vstup(N);
  iota(ALL(vstup), 0);
  shuffle(ALL(vstup), seed);

  vuc vystup = serad(vstup, -1, -1);

  vuc ret(N);
  REP(i, 0, N) ret[vystup[i]] = i;

  return ret;
}

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