oj.uz

Submission #528770

# Submission time Handle Problem Language Result Execution time Memory
528770 2022-02-21T11:27:33 Z c28dnv9q3 Monster Game (JOI21_monster) C++17
0 / 100
 204 ms 284 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Incorrect 0 ms 200 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Incorrect 0 ms 200 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 284 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -