oj.uz

답안 #705060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705060 2023-03-03T10:09:07 Z Cyanmond Monster Game (JOI21_monster) C++17
75 / 100
 109 ms 1092 KB 
#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 < 20; ++i) {
        int c = 0;
        for (int j = 0; j < 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 1092 KB Output is correct
2 Correct 73 ms 844 KB Output is correct
3 Correct 70 ms 816 KB Output is correct
4 Correct 69 ms 816 KB Output is correct
5 Correct 109 ms 832 KB Output is correct
6 Correct 58 ms 704 KB Output is correct
7 Correct 60 ms 716 KB Output is correct
8 Correct 90 ms 848 KB Output is correct
9 Correct 88 ms 796 KB Output is correct
10 Correct 66 ms 956 KB Output is correct
11 Correct 88 ms 872 KB Output is correct
12 Correct 98 ms 804 KB Output is correct
13 Correct 42 ms 672 KB Output is correct
14 Correct 80 ms 828 KB Output is correct
15 Correct 39 ms 608 KB Output is correct
16 Correct 52 ms 620 KB Output is correct
17 Correct 87 ms 860 KB Output is correct
18 Correct 56 ms 616 KB Output is correct