Submission #1246412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246412		trideser	Art Collections (BOI22_art)	C++20	50 / 100	375 ms	604 KiB

art

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

using namespace std;

vector<int> def;
int defcount;
bool compare(int a, int b) {
	def[a - 1] = b;
	def[b - 1] = a;
	int ans = publish(def); 
	if(ans == defcount)
		exit(1);
	def[a - 1] = a;
	def[b - 1] = b;
	return ans < defcount;
}

vector<int> merge(vector<int>& l, vector<int>& r) {
	vector<int> ret;
	int ll = 0;
	int rr = 0;
	while(ll != l.size() && rr != r.size()) {
		if(compare(l[ll], r[rr])) {
			ret.push_back(r[rr]);
			rr++;
		}
		else{
			ret.push_back(l[ll]);
			ll++;
		}
	}
	while(ll < l.size()) {
		ret.push_back(l[ll]);
		ll++;
	}
	while(rr < r.size()) {
		ret.push_back(r[rr]);
		rr++;
	}
	return ret;
}

void solve(int N) {
	def = vector<int>(N);
	vector<vector<int>> parts;
	for(int i = 0; i < N; i++) {
		def[i] = i + 1;
		parts.push_back(vector<int>());
		parts.back().push_back(i + 1);
	}
	defcount = publish(def);
	while(parts.size() > 1) {
		vector<vector<int>> newparts;
		for(int i = 0; i < parts.size() - 1; i += 2) {
			newparts.push_back(merge(parts[i], parts[i + 1]));
		}
		if(parts.size() % 2 == 1)
			newparts.push_back(parts.back());
		parts = newparts;
	}
	answer(parts.back());
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30