Submission #528846

#	Time	Username	Problem	Language	Result	Execution time	Memory
528846		c28dnv9q3	Monster Game (JOI21_monster)	C++17	0 / 100	214 ms	552 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<long unsigned int> counter = std::vector<long unsigned int>(a.size());
		for (long unsigned int i = 0; i < a.size() - 1; i++) {
			for (long unsigned 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 (long unsigned 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 (long unsigned 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]);
			}
		}
	}

	int min = 0;
	for (long unsigned int i = 1; i < right.size(); i++) {
		if (Query(right[min], right[i])) {
			min = i;
		}
	}
	int max = 0;
	for (long unsigned 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);

	if (left.size() == 3 || right.size() == 3) {
		return quick(a, true);
	}
	std::vector<int> end = quick(left, false);
	end.push_back(pivot);
	right = quick(right, false);
	for (long unsigned 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;
}

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