Submission #528852

#	Time	Username	Problem	Language	Result	Execution time	Memory
528852		c28dnv9q3	Monster Game (JOI21_monster)	C++17	10 / 100	224 ms	344 KiB

monster

#include "monster.h"
#include <iostream>

std::vector<int> quick(std::vector<int> a, bool help) {
	std::vector<int> left = std::vector<int>(), right = std::vector<int>();
	if (help) {
		goto A;
	}
	if (a.size() < 2) {
		return a;
	}
	else if (a.size() == 2) {
		std::vector<int> b = std::vector<int>();
		if (Query(a[0], a[1])) {
			b.push_back(a[0]);
			b.push_back(a[1]);
		}
		else {
			b.push_back(a[1]);
			b.push_back(a[0]);
		}
		return b;
	}
	else if (a.size() <= 8) {
	A: std::vector<int> counter = std::vector<int>(a.size());
		for (int i = 0; i < a.size() - 1; i++) {
			for (int j = i + 1; j < a.size(); j++) {
				if (Query(a[i], a[j])) {
					counter[i]++;
				}
				else {
					counter[j]++;
				}
			}
		}
		std::vector<int> end = std::vector<int>(a.size());
		bool did1 = false, didN = false;
		for (int i = 0; i < a.size(); i++) {
			if (counter[i] == 1 && !did1) {
				end[0] = a[i];
				did1 = true;
			}
			else if (counter[i] == a.size() - 2 && !didN) {
				end[a.size() - 1] = a[i];
				didN = true;
			}
			end[counter[i]] = a[i];
		}
		if (Query(end[1], end[0])) {
			int z = end[0];
			end[0] = end[1];
			end[1] = z;
		}
		if (Query(end[a.size() - 1], end[a.size() - 2])) {
			int z = end[a.size() - 2];
			end[a.size() - 2] = end[a.size() - 1];
			end[a.size() - 1] = z;
		}
		return end;
	}


	int pivot = a[a.size() / 2];
	for (int i = 0; i < a.size(); i++) {
		if (!(i == (a.size() / 2))) {
			if (Query(pivot, a[i])) {
				left.push_back(a[i]);
			}
			else {
				right.push_back(a[i]);
			}
		}
	}
	if (left.size() <= 3 || right.size() <= 3) {
		return quick(a, true);
	}
	int min = 0;
	for (int i = 1; i < right.size(); i++) {
		if (Query(right[min], right[i])) {
			min = i;
		}
	}
	int max = 0;
	for (int i = 1; i < left.size(); i++) {
		if (Query(left[i], left[max])) {
			max = i;
		}
	}
	right.push_back(left[max]);
	left.push_back(right[min]);
	left.erase(left.begin() + max);
	right.erase(right.begin() + min);

	std::vector<int> end = quick(left, false);
	end.push_back(pivot);
	right = quick(right, false);
	for (int i = 0; i < right.size(); i++) {
		end.push_back(right[i]);
	}
	return end;
}

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

	std::vector<int> T2 = std::vector<int>(N);
	for (int i = 0; i < N; i++) {
		T2[T[i]] = i;
	}
	/*for (int i = 0; i < N; i++) {
		std::cout << T2[i] << " ";
	}*/
	return T2;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> quick(std::vector<int>, bool)':
monster.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int i = 0; i < a.size() - 1; i++) {
      |                   ~~^~~~~~~~~~~~~~
monster.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for (int j = i + 1; j < a.size(); j++) {
      |                        ~~^~~~~~~~~~
monster.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = 0; i < a.size(); i++) {
      |                   ~~^~~~~~~~~~
monster.cpp:43:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    else if (counter[i] == a.size() - 2 && !didN) {
monster.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
monster.cpp:65:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if (!(i == (a.size() / 2))) {
      |         ~~^~~~~~~~~~~~~~~~~
monster.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 1; i < right.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
monster.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 1; i < left.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
monster.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0; i < right.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

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