Submission #705062

#	Time	Username	Problem	Language	Result	Execution time	Memory
705062		Cyanmond	Monster Game (JOI21_monster)	C++17	100 / 100	104 ms	980 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
 
namespace monster{
int N;
std::map<std::pair<int, int>, int> memo;
 
bool ask(int a, int b) {
    bool isSw = false;
    if (a > b) {
        isSw = true;
        std::swap(a, b);
    }
    if (memo.find({a, b}) == memo.end()) {
        memo[{a, b}] = Query(a, b);
    }
    return memo[{a, b}] ^ isSw;
}
 
std::vector<int> Solve(int n_) {
    N = n_;
    std::vector<int> res(N);
    std::iota(res.begin(), res.end(), 0);
    auto mergeSort = [&](auto &&self, int l, int r) -> void {
        if (r - l == 1) {
            return;
        }
        const int m = (l + r) / 2;
        self(self, l, m);
        self(self, m, r);
        std::vector<int> lVec, rVec;
        std::copy(res.begin() + l, res.begin() + m, std::back_inserter(lVec));
        std::copy(res.begin() + m, res.begin() + r, std::back_inserter(rVec));
        std::vector<int> mergedVec;
        int i = 0, j = 0;
        while (i != m - l and j != r - m) {
            if (not ask(lVec[i], rVec[j])) {
                mergedVec.push_back(lVec[i++]);
            } else {
                mergedVec.push_back(rVec[j++]);
            }
        }
        if (i != m - l) {
            std::copy(lVec.begin() + i, lVec.end(), std::back_inserter(mergedVec));
        }
        if (j != r - m) {
            std::copy(rVec.begin() + j, rVec.end(), std::back_inserter(mergedVec));
        }
        std::copy(mergedVec.begin(), mergedVec.end(), res.begin() + l);
    };
    mergeSort(mergeSort, 0, N);
 
    std::vector<bool> isF(N);
    isF[0] = true;
    int l = -1, r = -1;
    // find the first block!
    std::vector<int> countWin;
    for (int i = 0; i < std::min(N, 20); ++i) {
        int c = 0;
        for (int j = 0; j < std::min(N, 20); ++j) {
            if (i == j) continue;
            if (ask(res[i], res[j])) {
                ++c;
            }
        }
        if (i == 0 or countWin.back() >= c) {
            countWin.push_back(c);
        } else {
            break;
        }
    }
    if (countWin.size() == 1) {
        l = 0;
        r = 1;
    } else if (countWin.size() == 2) {
        assert(countWin[0] == countWin[1] and countWin[0] == 1);
        if (not ask(res[0], res[1])) {
            l = 0;
            r = 2;
        } else {
            isF[1] = true;
            l = 1;
            r = 2;
        }
    } else {
        l = 0;
        r = (int)countWin.size();
    }
    while (r != N) {
        isF[r] = true;
        bool fin = false;
        for (int i = r; i < N; ++i) {
            if (ask(res[l], res[i])) {
                fin = true;
                l = r;
                r = i + 1;
                break;
            }
        }
        if (not fin) {
            break;
        }
    }
 
    std::vector<int> answer;
    std::stack<int> stk;
    for (int i = 0; i < N; ++i) {
        if (isF[i]) {
            while (not stk.empty()) {
                answer.push_back(stk.top());
                stk.pop();
            }
        }
        stk.push(res[i]);
    }
    while (not stk.empty()) {
        answer.push_back(stk.top());
        stk.pop();
    }
    memo.clear();
    std::vector<int> tet(N);
    for (int i = 0; i < N; ++i) {
        tet[answer[i]] = i;
    }
    return tet;
}
}
 
std::vector<int> Solve(int n_) {
    return monster::Solve(n_);
}
 
/*
 
#include <cstdio>
#include <cstdlib>
 
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;
 
constexpr int Q_MAX = 25000;
constexpr int N_MAX = 1'000;
 
int N;
int S[N_MAX];
 
int query_count = 0;
 
void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}
 
bool Query(int a, int b) {
  if (++query_count > Q_MAX) WrongAnswer(6);
  if (a < 0 || N <= a || b < 0 || N <= b) WrongAnswer(4);
  if (a == b) WrongAnswer(5);
  return (S[a] > S[b]) ^ (abs(S[a] - S[b]) == 1);
}
 
void main_() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading.\n");
    exit(1);
  }
  for (int i = 0; i < N; i++) {
    if (scanf("%d", S + i) != 1) {
      fprintf(stderr, "Error while reading.\n");
      exit(1);
    }
  }
    N = 1000;
    int cas = 1000;
    std::mt19937 mt(100);
    std::uniform_int_distribution dist(1, N);
    std::vector<int> A(N);
    std::iota(A.begin(), A.end(), 0);
    int mav = 0;
    while (cas--) {
        std::shuffle(A.begin(), A.end(), mt);
        for (int i = 0; i < N; ++i) S[i] = A[i];
        const auto T = Solve(N);
        if (T != A) {
            std::cout << "bad" << std::endl;
        }
        mav = std::max(mav, query_count);
        query_count = 0;
    }
    std::cout << mav << std::endl;
    
  std::vector<int> T = Solve(N);
  if ((int)T.size() != N) WrongAnswer(1);
  for (int i = 0; i < N; ++i) {
    std::cout << S[T[i]] << ' ';
  }
  std::cout << std::endl;
  for (int i = 0; i < N; i++) {
    if (T[i] < 0 || N <= T[i]) WrongAnswer(2);
    if (T[i] != S[i]) WrongAnswer(3);
  }
  printf("Accepted: %d\n", query_count);
  return;
}
 
int main() {
    main_();
}*/

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