Submission #1224878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224878		trideser	Monster Game (JOI21_monster)	C++20	0 / 100	36 ms	500 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
	
	bool example_variable;
	
}	// namespace

void finish(vector<int>& vec, vector<int>& res, int start, int lowindex) {
	cerr << "FINISH " << start << " " << lowindex << "\n";
	if(start == vec.size())
		return;
	int index = start;
	while(Query(vec[lowindex], vec[index])) {
		index++;
	}
	cerr << "\t" << index << "\n";
	for(int i = start, j = index; i < index + 1; i++, j--) {
		res[i] = vec[j];
	}
	finish(vec, res, index + 1, start);
}

void resolve(vector<int>& vec, vector<int>& res, int start) {
	if(vec.size() - start <= 6) {
		int n = vec.size() - start;
		cerr << "brute" << n << "\n";
		vector<int> winc(vec.size());
		for(int i = start; i < vec.size(); i++) {
			for(int j = i + 1; j < vec.size(); j++) {
				if(Query(vec[i], vec[j]))
					winc[i]++;
				else
					winc[j]++;
			}
		}
		cerr << "WINC\n";
		for(int i = start; i < vec.size(); i++)
			cerr << winc[i] << " ";
		cerr << "\n";
		vector<int> sw;
		vector<int> sl;
		for(int i = start; i < vec.size(); i++) {
			if(winc[i] == 1) {
				sw.push_back(vec[i]);
			}
			else if(winc[i] == n - 2) {
				sl.push_back(vec[i]);
			}
			else {
				res[res.size() - winc[i] - 1] = vec[i];
			}
		}
		cerr << "swl " << sw[0] << " " << sw[1] << " "<< sl[0] << " "<< sl[1] << "\n";
		if(vec.size() - start == 4) {
			if(Query(sw[0], sl[0]) || Query(sw[0], sl[1])) {
				res[start + 2] = sw[0];
				res[start + 3] = sw[1];
			}
			else {
				res[start + 2] = sw[1];
				res[start + 3] = sw[0];
			}
			if(Query(sl[0], sw[0]) && Query(sl[0], sw[1])) {
				res[start] = sl[0];
				res[start + 1] = sl[1];
			}
			else {
				res[start] = sl[1];
				res[start + 1] = sl[0];
			}
		}
		else if(vec.size() - start >= 5) {
			if(Query(res[start + 2], sl[0])) {
					res[start] = sl[1];
					res[start + 1] = sl[0];
			}
			else {
					res[start] = sl[0];
					res[start + 1] = sl[1];
			}
			if(Query(res[res.size() - 3], sw[0])) {
					res[res.size() - 2] = sw[1];
					res[res.size() - 1] = sw[0];
			}
			else {
					res[res.size() - 2] = sw[0];
					res[res.size() - 1] = sw[1];
			}
		}
		else {
			cerr << "ERR\n";
		}
		cerr << "BRUTERES\n";
		for(int a : res)
			cerr << a << " ";
		cerr << "\n";
		return;
	}
	if(Query(vec[start], vec[start + 2])) {
		cerr << "finish\n";
		int index = start + 3;
		while(index < vec.size() && Query(vec[start], vec[index])) {
			index++;
		}
		if(index == vec.size()) {
			cerr << "OVERFLOW\n";
			cerr << "OWF RES\n";
			for(int a : res)
				cerr << a << " ";
			cerr << "\n";
			cerr << start << " " << index << "\n";
			index--;
			//res[start] = vec[start];
			//res[start + 1] = vec[start];
			for(int i = start + 2, j = index; i < vec.size(); i++, j--) {
				res[i] = vec[j];
			}
			cerr << "OWF RES\n";
			for(int a : res)
				cerr << a << " ";
			cerr << "\n";
			return;
		}
		cerr << "s " << start << " ix " << index << "\n";
		cerr << vec[start + 1] << " " << vec[index] << "\n";
		if(Query(vec[start + 1], vec[index])) {
			cerr << "MAX 2\n";
			res[start] = vec[start + 1];
			res[start + 1] = vec[start];
			for(int i = start + 2, j = index; i <= index; i++, j--) {
				res[i] = vec[j];
			}
			finish(vec, res, index + 1, start + 2);
			//resolve(vec, res, index + 1);
		}
		else {
			cerr << "MAX 1\n";
			res[start] = vec[start];
			for(int i = start + 1, j = index; i <= index; i++, j--) {
				res[i] = vec[j];
			}
			finish(vec, res, index + 1, start + 2);
			//resolve(vec, res, index + 1);
		}
		//resolve(vec, res, index + 1);
		return;
	}
	bool q1 = Query(vec[start + 3], vec[start]);
	bool q2 = Query(vec[start + 3], vec[start + 1]);
	bool q3 = Query(vec[start + 3], vec[start + 2]);
	cerr << "Q" << q1 << " " << q2 << " " << q3 << "\n";
	if((q1 && q2) || (q1 && q3) || (q2 && q3)) {
		cerr << "4 ^\n";
		int index = start + 4;
		while(Query(vec[index], vec[start + 1])) {
			index++;
		}
		index--;
		cerr << start << " " << index << "\n";
		for(int i = index, j = start; i >= start; i--, j++) {
			res[i] = vec[j];
		}
		resolve(vec, res, index + 1);
		return;
	}
	cerr << "recursion\n";
	resolve(vec, res, start + 3);
	cerr << "rec\n";
	int a = vec[start];
	int b = vec[start + 1];
	int c = vec[start + 2];
	cerr << "\t" << start << " " << res[start + 3] << " " << a << " " << b << " " << c << " "<< Query(vec[start], vec[start + 1])<< " " << Query(vec[start + 1], vec[start + 2]) << " " << Query(vec[start + 2], vec[start]) << "\n";
	for(int a : res)
		cerr << a << " ";
	cerr << "\n";
	if(!Query(a, res[start + 3])) {
		cerr << "1st\n";
		res[start] = c;
		res[start + 1] = b;
		res[start + 2] = a;
	}
	else if(!Query(b, res[start + 3])) {
		cerr << "2nd\n";
		res[start] = a;
		res[start + 1] = c;
		res[start + 2] = b;
	}
	else if(!Query(c, res[start + 3])) {
		cerr << "3rd\n";
		res[start] = b;
		res[start + 1] = a;
		res[start + 2] = c;
	}
	else{
		cerr << "err\n";
	}
}

vector<int> Solve(int N) {
	vector<vector<int>> vec(N, vector<int>());
	for(int i = 0; i < N; i++) {
		vec[i].push_back(i);
	}
	while(vec.size() != 1) {
	cerr << "VEC:\n";
	for(vector<int> v : vec) {
		for(int i : v)
			cerr << i << " ";
		cerr << "\n";
	}
	cerr << "\n";
		vector<vector<int>> newvec;
		for(int i = 0; i < vec.size(); i += 2) {
			vector<int> vec1 = vec[i];
			vector<int> vec2 = vec.size() > i + 1 ? vec[i+1] : vector<int>();
			vector<int> res;
			int a = 0;
			int b = 0;
			for(; a < vec1.size() && b < vec2.size(); ) {
				cerr << vec1[a] << " " << vec2[b] << "\n";
				if(Query(vec1[a], vec2[b])) {
					res.push_back(vec1[a]);
					a++;
				}
				else {
					res.push_back(vec2[b]);
					b++;
				}
			}
			for(int j = a; j < vec1.size(); j++) {
				res.push_back(vec1[j]);
			}
			for(int j = b; j < vec2.size(); j++) {
				res.push_back(vec2[j]);
			}
			newvec.push_back(res);
		}
		vec = newvec;
	}

	cerr << "VEC FINAL:\n";
	for(vector<int> v : vec) {
		for(int i : v)
			cerr << i << " ";
		cerr << "\n";
	}
	cerr << "\n";
	vector<int> res(N);
	cerr << "--------------------\n";
	resolve(vec[0], res, 0);
	cerr << "RES: ";
	for(int a : res)
		cerr << a << " ";
	cerr << "\n";
	vector<int> ret(N);
	for(int i = 0; i < N; i++) {
		ret[res[N - i - 1]] = i;
	}
	cerr << "RET: ";
	for(int a : ret)
		cerr << a << " ";
	return ret;
}

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