oj.uz

Submission #528875

# Submission time Handle Problem Language Result Execution time Memory
528875 2022-02-21T16:19:31 Z c28dnv9q3 Monster Game (JOI21_monster) C++17
0 / 100
 76 ms 200 KB 
#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, result;
// std::vector<Monster> monsters;

void merge(int from, int mid, int to) {
	int left_arr[mid - from];
	int right_arr[to - mid];
	for (int i = from; i < mid; ++i) {
		left_arr[i - from] = result[i];
	}
	for (int i = mid; i < to; ++i) {
		right_arr[i - mid] = result[i];
	}

	int li = 0, ri = 0;
	int i = from;
	for (; i < to && li < (mid - from) && ri < (to - mid); ++i) {
		if (!Query(left_arr[li], right_arr[ri])) {
			// right wins
			result[i] = left_arr[li++];
		} else {
			result[i] = right_arr[ri++];
		}
	}

	while (li < mid - from) {
		result[i++] = left_arr[li++];
	}
	while (ri < to - mid) {
		result[i++] = right_arr[ri++];
	}
}

void merge_sort(int from, int to) {
	if (from == to - 1) {
		return;
	}

	int midpoint = (from + to) / 2;
	merge_sort(from, midpoint);
	merge_sort(midpoint, to);
	merge(from, midpoint, to);
}

std::vector<int> Solve(int N) {
	T = std::vector<int>(N);
	result = std::vector<int>(N);
	for (int i = 0; i < N; ++i) {
		result[i] = i;
	}

	merge_sort(0, N);

	// correction
	for (int i = 0; i < N - 1; ++i) {
		int end = i + 1;
		while (end < N) {
            if(end == N - 1) {
                ++end;
                break;
            }
			if (!Query(result[i], result[end])) {
                ++end;
                break;
			}
		}

		reverse(result.begin() + i, result.begin() + end);
		i = end;
	}

	for (int i = 0; i < N; ++i) {
		T[result[i]] = i;
	}
	for (int i = 0; i < N; ++i) {
		cout << T[i] << " ";
	}

	return T;

	/*
	monsters = std::vector<Monster>(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]);
	}
	*/
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 200 KB Wrong Answer [0]
2 Halted 0 ms 0 KB -