Submission #528792

#	Time	Username	Problem	Language	Result	Execution time	Memory
528792		c28dnv9q3	Monster Game (JOI21_monster)	C++17	0 / 100	28 ms	416 KiB

monster

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

namespace {

}  // namespace

std::vector<int> quick(std::vector<int> a) {
	int pivot = a[a.size() / 2];
	std::vector<int> left = std::vector<int>(), right = std::vector<int>();
	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;
	}

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

		if (right.size() == 1) {
			for (int i = 0; i < left.size(); i++) {
				if (Query(left[i], right[0])) {
					left.push_back(right[0]);
					right.erase(right.begin());
					goto END;
				}
			}
		}
		else if (left.size() == 1) {
			for (int i = 0; i < right.size(); i++) {
				if (!Query(right[i], left[0])) {
					right.push_back(left[0]);
					left.erase(left.begin());
					goto END;
				}
			}
		}
	}

END: std::vector<int> end = std::vector<int>();
	std::vector<int> l;
	if (left.size() == 3) {
		for (int i = 0; i < 3; i++) {
			if (Query(left[i], pivot)) {
				l = left;
				left = std::vector<int>();
				for (int j = 0; j < 3; j++) {
					if (j != i) {
						left.push_back(l[j]);
					}
				}
				int x = l[i];
				l = quick(left);
				l.push_back(x);
			}
		}
	}
	else {
		l = quick(left);
	}
end = l;
	end.push_back(pivot);
std::vector<int> r = std::vector<int>();
if (right.size() == 3) {
	for (int i = 0; i < 3; i++) {
		if (Query(pivot, right[i])) {
			r = right;
			right = std::vector<int>();
			for (int j = 0; j < 3; j++) {
				if (j != i) {
					right.push_back(r[j]);
				}
			}
			int x = r[i];
			right = quick(right);
			r.push_back(x);
			r.push_back(right[0]);
			r.push_back(right[1]);
		}
	}
}
else {
	r = quick(right);
}
for (int i = 0; i < r.size(); i++) {
	end.push_back(r[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);

  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>)':
monster.cpp:26:20: 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(); i++) {
      |                  ~~^~~~~~~~~~
monster.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if (!(i == (a.size() / 2))) {
      |         ~~^~~~~~~~~~~~~~~~~
monster.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int i = 1; i < right.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
monster.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 1; i < left.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
monster.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 1; i < right.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
monster.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i = 1; i < left.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
monster.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for (int i = 0; i < left.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
monster.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for (int i = 0; i < right.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
monster.cpp:140:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 | for (int i = 0; i < r.size(); i++) {
      |                 ~~^~~~~~~~~~

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