Submission #67778

#	Time	Username	Problem	Language	Result	Execution time	Memory
67778		gnoor	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	540 KiB

messy

#include <vector>
#include <string>

#include "messy.h"

using namespace std;

string tmp;

void add(int l,int r) {
	int m=(l+r)>>1;
	for (int i=l;i<m;i++) {
		tmp[i]='1';
		add_element(tmp);
		tmp[i]='0';
	}
	if (l+2==r) return;
	for (int i=m;i<r;i++) tmp[i]='1';
	add(l,m);
	for (int i=l;i<m;i++) tmp[i]='1';
	for (int i=m;i<r;i++) tmp[i]='0';
	add(m,r);
	for (int i=l;i<r;i++) tmp[i]='0';
}

vector<int> ans;

void solve(int l,int r,const vector<int> &candid,const vector<int> &pre) {
	if (l+1==r) {
		ans[candid.front()]=l;
		return;
	}
	for (auto i:pre) {
		tmp[i]='1';
	}
	vector<int> ll;
	vector<int> rr;
	for (auto i:candid) {
		tmp[i]='1';
		if (check_element(tmp)) {
			ll.push_back(i);
		} else {
			rr.push_back(i);
		}
		tmp[i]='0';
	}
	int m=(l+r)>>1;
	solve(l,m,ll,rr);
	solve(m,r,rr,ll);
	for (auto i:pre) {
		tmp[i]='0';
	}
}

std::vector<int> restore_permutation(int n, int w, int r) {
	for (int i=0;i<n;i++) {
		tmp.push_back('0');
	}
	add(0,n);
	compile_set();
	ans.resize(n);
	for (int i=0;i<n;i++) {
		tmp[i]='0';
	}
	vector<int> init(n);
	for (int i=0;i<n;i++) {
		init[i]=i;
	}
	solve(0,n,init,vector<int>());
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30