Submission #528770

#	Time	Username	Problem	Language	Result	Execution time	Memory
528770		c28dnv9q3	Monster Game (JOI21_monster)	C++17	0 / 100	204 ms	284 KiB

monster

#include "monster.h"

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

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[1].index, monsters[2].index)) {
        swap(monsters[0], monsters[1]);
    }

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

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

	return T;
}

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