| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 895678 | Alcabel | Monster Game (JOI21_monster) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cstdlib>
#include "monster.h"
namespace {
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;
constexpr int Q_MAX = 25'000;
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);
}
} // namespace
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);
}
#include <bits/stdc++.h>
using namespace std;
void sort(int l, int r, vector<int>& order) {
if (l + 1 >= r) {
return;
}
int m = l + (r - l) / 2;
sort(l, m, order);
sort(m, r, order);
vector<int> tmp(r - l);
int ptrL = l, ptrR = m, ptr = 0;
while (ptrL < m && ptrR < r) {
if (Query(order[ptrR], order[ptrL])) {
tmp[ptr++] = order[ptrL++];
} else {
tmp[ptr++] = order[ptrR++];
}
}
while (ptrL < m) {
tmp[ptr++] = order[ptrL++];
}
while (ptrR < r) {
tmp[ptr++] = order[ptrR++];
}
for (int i = 0; i < r - l; ++i) {
order[l + i] = tmp[i];
}
}
vector<int> Solve(int n) {
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(0, n, order);
int cntWin = 0, firstWin = n, firstLoss = n;
for (int i = 1; i < n; ++i) {
if (Query(order[0], order[i])) {
++cntWin;
firstWin = min(i, firstWin);
} else {
firstLoss = min(i, firstLoss);
}
}
int border = -1;
if (cntWin > 1 && cntWin < n - 2) {
// order[cntWin] = 0;
border = cntWin + 1;
} else if (cntWin == 1) {
// order[0] = 1 or 0
if (firstWin == 1) {
border = 1;
} else {
if (firstWin >= 3) {
if (Query(order[firstWin], order[1])) {
border = 2;
} else {
border = 1;
}
} else {
bool moreWon = false;
vector<int> rask(n - 3);
iota(rask.begin(), rask.end(), 3);
for (const int& i : rask) {
if (Query(order[2], order[i])) {
moreWon = true;
break;
}
}
if (moreWon) {
border = 2;
} else {
border = 1;
}
}
}
} else {
// order[0] = n - 1 or n - 2
if (Query(order[n - 3], order[n - 1])) {
border = n;
} else {
border = n - 1;
}
}
reverse(order.begin(), order.begin() + border);
while (border < n - 1) {
int newBorder = border;
while (!Query(order[border - 1], order[newBorder])) {
++newBorder;
}
reverse(order.begin() + border, order.begin() + newBorder + 1);
border = newBorder + 1;
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[order[i]] = i;
}
return ans;
}
int 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);
}
}
std::vector<int> T = Solve(N);
if ((int)T.size() != N) WrongAnswer(1);
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 0;
}