Submission #1282531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282531		am_aadvik	Monster Game (JOI21_monster)	C++20	0 / 100	61 ms	420 KiB

monster

#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;
}

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