Submission #439560

#	Time	Username	Problem	Language	Result	Execution time	Memory
439560		8e7	Monster Game (JOI21_monster)	C++17	100 / 100	103 ms	2388 KiB

monster

#include "monster.h"
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <time.h>
#include <random>
#define maxn 1005
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ";debug(b ...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
namespace {
	bool res[maxn][maxn];
	bool found[maxn][maxn];
	int num = 0, save = 0;
}  // namespace
bool que(int a, int b) {
	if (found[a][b]) return save++, res[a][b];
	bool ret = Query(a, b);
	found[a][b] = found[b][a] = 1;
	res[a][b] = ret, res[b][a] = ret ^ 1;
	num++;
	return ret;
}
bool cmp(int a, int b) {
	return que(b, a);
}
void mergesort(vector<int> &v) {
	if (v.size() <= 1) {
		return;
	}
	vector<int> lef, rig;
	for (int i = 0;i < v.size();i++) {
		if (i < (v.size() / 2)) lef.push_back(v[i]);
		else rig.push_back(v[i]);
	}
	mergesort(lef), mergesort(rig);	
	vector<int> ret (v.size(), 0);
	merge(lef.begin(), lef.end(), rig.begin(), rig.end(), ret.begin(), cmp);
	//debug(7122);
	/*
	int ind = 0;
	for (int i = 0;i < lef.size();i++) {
		while (ind < rig.size() && que(lef[i], rig[ind])) {
			ret.push_back(rig[ind]);
			ind++;
		}
		ret.push_back(lef[i]);
	}
	while (ind < rig.size()) ret.push_back(rig[ind++]);
	*/
	v = ret;
}

vector<int> Solve(int N) {
	vector<int> ret;
	vector<int> cand;
	for (int i = 0;i < N;i++) cand.push_back(i);
	mergesort(cand);
	//for (int i = 0;i < N - 1;i++) assert(que(cand[i], cand[i + 1]));
	//pary(cand.begin(), cand.end());
	//cout << num << endl;
	vector<pii> cur;
	bool done = 0;
	for (int i = N - 1;i >= 0;i--) {
		int loss = 0;	
		for (auto &j:cur) {
			if (que(cand[i], cand[j.ff])) j.ss++;
			else loss++;	
		}
		for (int j = cur.size() - 1;j >= 0;j--) {
			if (cur[j].ss > 1) {
				cur.erase(cur.begin() + j);		
			} else if (cur[j].ff > i + 4) {
				done = 1;
				break;
			}
		}
		if (done) break;
		if (loss < 2) cur.push_back({i, loss});
	}	
	//cout << num << " " << save << endl;
	assert(cur.size());
	int big;
	if (cur.size() == 1) big = cur[0].ff;
	else if (cur.size() == 2) {
		if (cur[0].ff == cur[1].ff + 1) big = cur[1].ff;
		else big = cur[0].ff;
	} else {
		big = cur[0].ff;
		for (int i = 0;i < 2;i++) {
			if (cur[i + 1].ff == cur[i].ff - 1) big = cur[i + 1].ff;
			else {
				break;
			}
		}
	}
	for (int i = big;i < N;i++) ret.push_back(cand[i]);
	int comp = N - 1;
	for (int i = big - 1;i >= 0;i--) {
		if (que(cand[i], cand[comp])) {
			for (int j = i;j < big;j++) ret.push_back(cand[j]);
			comp = big - 1, big = i;
		}
	}
	reverse(ret.begin(), ret.end());
	vector<int> a (N, 0);
	for (int i = 0;i < N;i++) a[ret[i]] = i;
	return a;
}
/*
5
3 1 4 2 0

8
7 3 4 2 1 5 6 0

10
0 2 8 3 9 4 6 7 5 1
*/

Compilation message (stderr)

monster.cpp: In function 'void mergesort(std::vector<int>&)':
monster.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0;i < v.size();i++) {
      |                 ~~^~~~~~~~~~
monster.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (i < (v.size() / 2)) lef.push_back(v[i]);
      |       ~~^~~~~~~~~~~~~~~~

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