| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1282530 | am_aadvik | Monster Game (JOI21_monster) | C++20 | 0 ms | 0 KiB |
//#define SUBMIT 1
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>
#include <algorithm>
#include<map>
using namespace std;
#ifdef SUBMIT
#include "monster.h"
#else
#include <cstdio>
#include <cstdlib>
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);
}
}
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);
}
vector<int> Solve(int n);
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);
}
}
for (int t = 0; t < 20; ++t) {
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;
}
#endif
//main code
#include <random>
bool q(int a, int b) { return Query(a, b); }
vector<int> rem(vector<int>& a, int m) {
vector<int> v;
for (auto x : a)
if (x != m)
v.push_back(x);
return v;
}
vector<int> qsort(vector<int> a) {
if (a.size() <= 1) return a;
if (a.size() == 2) {
auto x = q(a[0], a[1]);
if (x) return a;
else return { a[1], a[0] };
}
int n = a.size();
random_device rd;
mt19937 gd(rd());
uniform_int_distribution<> dd(0, n - 1);
int mx = a[0], mn = a[0], p = 0;
map<int, int> mxp, mnp;
int mxo = 0, mno = 0, bmx = mx, bmn = mn;
vector<int> l, r, sa;
for (int t = 0; t < 100; ++t) {
mx = a[0], mn = a[0];
for (int i = 1; i < n; ++i)
mx = (q(a[i], mx) ? a[i] : mx),
mn = (q(a[i], mn) ? mn : a[i]);
int vmx = mx, vmn = mn;
mx = a[0], mn = a[0];
for (int i = 1; i < n; ++i) {
if (a[i] != vmx)
mx = (q(a[i], mx) ? a[i] : mx);
if (a[i] != vmn)
mn = (q(a[i], mn) ? mn : a[i]);
}
shuffle(a.begin(), a.end(), gd);
++mxp[mx], ++mnp[mn];
if (mxp[mx] > mxo) mxo = mxp[mx], bmx = mx;
if (mnp[mn] > mno) mno = mnp[mn], bmn = mn;
}
mx = bmx, mn = bmn;
while ((a[p] == mx) || (a[p] == mn)) p = dd(gd);
for (int i = 0; i < n; ++i)
if (i != p) {
auto v = q(a[p], a[i]);
if (v) l.push_back(a[i]);
else r.push_back(a[i]);
}
int wl = (l.empty() ? -1 : l[0]), lr = (r.empty() ? -1 : r[0]);
for (int i = 1; i < l.size(); ++i)
wl = (q(l[i], l[i - 1]) ? l[i] : l[i - 1]);
for (int i = 1; i < r.size(); ++i)
lr = (q(r[i], r[i - 1]) ? r[i - 1] : r[i]);
l = rem(l, wl), r = rem(r, lr);
l = qsort(l), r = qsort(r);
for (auto x : l) sa.push_back(x);
if (lr != -1) sa.push_back(lr);
sa.push_back(a[p]);
if (wl != -1) sa.push_back(wl);
for (auto x : r) sa.push_back(x);
return sa;
}
vector<int> Solve(int n) {
vector<int> a;
for (int i = 0; i < n; ++i) a.push_back(i);
random_device rd;
mt19937 g(rd());
auto res = qsort(a);
for (int i = 0; i < n; ++i)
a[res[i]] = i;
a[0] += 0;
return a;
}