Submission #961748

#	Time	Username	Problem	Language	Result	Execution time	Memory
961748		0npata	Monster Game (JOI21_monster)	C++17	25 / 100	119 ms	2016 KiB

monster

#include "monster.h"
#include<bits/stdc++.h>
using namespace std;



namespace {
#define vec vector
#define arr array
#define pb push_back
	void quick_sort(vec<int>& v, int l0, int r0, int ri = -1, int rn = -1) {
		if(v.size() == 0) return;

		vec<int> left(0);
		vec<int> right(0);


		bool nr = ri==-1;
		while(ri == rn || ri == -1) {
			ri = rand()%v.size();
			ri = v[ri];
		}

		for(int i = 0; i<v.size(); i++) {
			if(v[i]==ri) continue;
			if(Query(ri, v[i])) {
				left.pb(v[i]);
			}
			else {
				right.pb(v[i]);
			}
		}

		pair<int, int> nxtl;
		pair<int, int> nxtr;
		int si = -1;
		bool sn = false;

		if(left.size() < l0) {
			int ll0 = left.size();
			nxtl = {ll0, 0};

			int lr0 = l0-(left.size()+1);
			nxtr = {lr0, r0};
		}
		else if(right.size() < r0) {
			int rr0 = right.size();
			nxtr = {0, rr0};

			int rl0 = r0-(right.size()+1);
			nxtl = {l0, rl0};
		}
		else if(v.size()-l0-r0 == 2) {
			if(left.size() > l0) {
				assert(left.size() == l0+1);
				nxtl = {l0, 1};
				nxtr = {0, r0};

				si = -2;
			}
			else {
				assert(right.size() == r0+1);
				nxtl = {l0, 0};
				nxtr = {1, r0};
				si = 2;
			}
		}
		else if(left.size() == l0) {
			assert(right.size() == r0);
			nxtl = {l0, 0};
			nxtr = {0, r0};
		}
		else if(nr && left.size() == l0+1) {
			quick_sort(v, l0, r0, left.back());
			return;
		}
		else if(nr && right.size() == r0+1) {
			quick_sort(v, l0, r0, right.front());
			return;
		}
		else {
			nxtl = {l0, 1};
			nxtr = {1, r0};

			sn = true;
		}


		int lftsz = left.size()-(nxtl.first+nxtl.second);
		int rightsz = right.size()-(nxtr.first+nxtr.second);
		if(lftsz==3 || rightsz==3) {
			quick_sort(v, l0, r0, -1, ri);
			return;
		}
		quick_sort(left, nxtl.first, nxtl.second);
		quick_sort(right, nxtr.first, nxtr.second);
		if(si == -2) {
			swap(left[left.size()-1], ri);
		}
		else if(si == 2) {
			swap(right[0], ri);
		}
		if(sn) {
			swap(right[0], left[left.size()-1]);
		}

		vec<int> res = left;
		res.pb(ri);
		for(int i = 0; i<right.size(); i++)  res.pb(right[i]);

//		cerr << "RES-------------" << '\n';
//		for(int i = 0; i<res.size(); i++) cerr << res[i] << ' ';
//		cerr << '\n';
		v = res;
	}
}


std::vector<int> Solve(int n) {
  std::vector<int> v(n);


  for (int i = 0; i < n; i++) v[i] = i;

  quick_sort(v, 0, 0);

  std::vector<int> res(n);

  for(int i = 0; i<n; i++) {
	  res[v[i]] = i;
  }

  return res;
}

Compilation message (stderr)

monster.cpp: In function 'void {anonymous}::quick_sort(std::vector<int>&, int, int, int, int)':
monster.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i = 0; i<v.size(); i++) {
      |                  ~^~~~~~~~~
monster.cpp:39:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   if(left.size() < l0) {
      |      ~~~~~~~~~~~~^~~~
monster.cpp:46:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |   else if(right.size() < r0) {
      |           ~~~~~~~~~~~~~^~~~
monster.cpp:54:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |    if(left.size() > l0) {
      |       ~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from monster.cpp:2:
monster.cpp:55:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     assert(left.size() == l0+1);
      |            ~~~~~~~~~~~~^~~~~~~
monster.cpp:62:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     assert(right.size() == r0+1);
      |            ~~~~~~~~~~~~~^~~~~~~
monster.cpp:68:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   else if(left.size() == l0) {
      |           ~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from monster.cpp:2:
monster.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |    assert(right.size() == r0);
      |           ~~~~~~~~~~~~~^~~~~
monster.cpp:73:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |   else if(nr && left.size() == l0+1) {
      |                 ~~~~~~~~~~~~^~~~~~~
monster.cpp:77:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |   else if(nr && right.size() == r0+1) {
      |                 ~~~~~~~~~~~~~^~~~~~~
monster.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int i = 0; i<right.size(); i++)  res.pb(right[i]);
      |                  ~^~~~~~~~~~~~~

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