제출 #1282842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282842		am_aadvik	Monster Game (JOI21_monster)	C++20	10 / 100	60 ms	488 KiB

monster

#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> rem(vector<int>& a, int m) {
	vector<int> v;
	for (auto x : a)
		if (x != m)
			v.push_back(x);
	return v;
}
vector<int> solves(int n, vector<int> l) {
	int m = l.size();
	vector<int> win(n), a(n, -1);
	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 (auto x : l) {
		if (win[x] == 1) w1.push_back(x);
		if (win[x] == (m - 2)) wn.push_back(x);
		else if (win[x] > 1) a[x] = win[x];
	}
	auto r1 = q(w1[0], w1[1]);
	if (r1) a[w1[0]] = 0, a[w1[1]] = 1;
	else a[w1[0]] = 1, a[w1[1]] = 0;
	auto rn = q(wn[0], wn[1]);
	if (rn) a[wn[0]] = m - 2, a[wn[1]] = m - 1;
	else a[wn[0]] = m - 1, a[wn[1]] = m - 2;
	vector<int> sl(m);
	for (int i = 0; i < n; ++i)
		if (a[i] != -1) sl[a[i]] = i;
	return sl;
}
vector<int> qsort(int m, 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] };
	}
	if (a.size() <= 4)
		return solves(m, a);
	int n = a.size();
	set<int> s;
	vector<int> l, r, sa;
	int p = 0;
	while ((l.size() == 0) || ((l.size() == 1) || (r.size() == 1)) || ((l.size() == 4) || (r.size() == 4))) {
		p = (p + 1) % n;
		l.clear(), r.clear();
		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], wl) ? l[i] : wl);
	for (int i = 1; i < r.size(); ++i)
		lr = (q(r[i], lr) ? lr : r[i]);
	l = rem(l, wl), r = rem(r, lr);
	l = qsort(m, l), r = qsort(m, 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(n, a);
	for (int i = 0; i < n; ++i)
		a[res[i]] = i;
	res[0] += 0;
	return a;
}

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