Submission #528781

#	Time	Username	Problem	Language	Result	Execution time	Memory
528781		c28dnv9q3	Monster Game (JOI21_monster)	C++17	10 / 100	206 ms	284 KiB

monster

#include "monster.h"

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Monster {
	int index, wins;

	bool operator<(const Monster &m) const {
		return wins < m.wins;
	}
};

std::vector<int> T;
std::vector<Monster> monsters;

/*int findPivot(int from, int to) {
	int pivot = T[to - 1];
	for (int i = from; i < to - 1; ++i) {
		if (Query(i, pivot)) {	// i wins
			//swap(T[i], T[]);
		}
	}
}

void findSequence(int from, int to) {
	if (from == to + 1) {
		return;
	}

	int pivot = findPivot(from, to);

	findSequence(from, pivot);
	findSequence(pivot + 1, to);
}*/

std::vector<int> Solve(int N) {
	T = std::vector<int>(N);
	monsters = std::vector<Monster>(N);

	// findSequence(0, N);

	for (int i = 0; i < N; ++i) {
		monsters[i] = {i, 0};
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < i; ++j) {
			if (i == j) {
				continue;
			}

			if (Query(i, j)) {	// i wins
				++monsters[i].wins;
			} else {
				++monsters[j].wins;
			}
		}
	}

	sort(monsters.begin(), monsters.end());

	if (!Query(monsters[0].index, monsters[1].index)) {
		swap(monsters[0], monsters[1]);
	}
	if (Query(monsters[N - 1].index, monsters[N - 2].index)) {
		swap(monsters[N - 2], monsters[N - 1]);
	}

	for (int i = 0; i < N; ++i) {
		T[monsters[i].index] = i;
	}

	return T;
}

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