| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1283398 | 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>
#include<set>
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);
query_count = 0;
}
return 0;
}
#endif
//main code
#include <random>
bool q(int a, int b) { return Query(a, b); }
vector<int> msort(vector<int> &a) {
if (a.size() <= 1) return a;
vector<int> l, r, sa;
int n = a.size();
for (int i = 0; i < (n / 2); ++i)
l.push_back(a[i]);
for (int i = n / 2; i < n; ++i)
r.push_back(a[i]);
l = msort(l), r = msort(r);
int pl = 0, pr = 0;
while ((pl < l.size()) || (pr < r.size())) {
if (pl == l.size()) sa.push_back(r[pr]), pr++;
else if (pr == r.size()) sa.push_back(l[pl]), pl++;
else if(q(l[pl], r[pr])) sa.push_back(r[pr]), pr++;
else sa.push_back(l[pl]), pl++;
}
return sa;
}
int find0(int n, vector<int> l) {
int m = l.size();
vector<int> win(n);
for (auto x : l)
for (int y : l)
if (x != y)
if (q(x, y)) ++win[x];
else ++win[y];
for (auto& x : win) x /= 2;
vector<int> w1, wn;
for(int i = 0; i < l.size(); ++i)
if (win[l[i]] == 1)
w1.push_back(i);
auto r1 = q(l[w1[0]], l[w1[1]]);
if (r1) return w1[0];
else return w1[1];
}
void rev(int i, int j, vector<int>& a) {
while (i < j) swap(a[i], a[j]), i++, j--;
}
vector<int> Solve(int n) {
vector<int> a(n);
for (int i = 0; i < n; a[i] = i, ++i);
a = msort(a);
vector<int> f(min(20, n));
for (int i = 0; i < min(20, n); ++i) f[i] = a[i];
int p = find0(n, f);
for (int i = p - 1; i >= 0; --i) swap(a[i + 1], a[i]);
p = 0;
while (1) {
int j = -1;
for(int i = p + 1; i < n; ++i)
if (q(a[p], a[i])) { j = i; break; }
if (j == -1) break;
rev(p + 1, j, a);
p = j;
}
vector<int> res(n);
for (int i = 0; i < n; ++i)
res[a[i]] = i;
return res;
}