Submission #219106

#	Time	Username	Problem	Language	Result	Execution time	Memory
219106		DystoriaX	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	8 ms	512 KiB

messy

#include <vector>
#include <bits/stdc++.h>
#include "messy.h"

using namespace std;

vector<int> ans;
string bit;

void generate(int l, int r){
	if(r - l == 1) return;

	int m = (l + r) >> 1;

	for(int i = l; i < m; i++){
		bit[i] = '1';

		add_element(bit);

		bit[i] = '0';
	}

	for(int i = m; i < r; i++) bit[i] = '1';
	generate(l, m);

	for(int i = m; i < r; i++) bit[i] = '0';
	for(int i = l; i < m; i++) bit[i] = '1';

	generate(m, r);

	for(int i = l; i < m; i++) bit[i] = '0';
}

void query(int l, int r, vector<int> idx){
	if(r - l == 1){
		ans[idx[0]] = l;
		return;
	}

	vector<int> lf, rg;

	for(auto &k : idx){
		bit[k] = '1';

		//1 to left, 0 to right
		if(check_element(bit)) lf.emplace_back(k);
		else rg.emplace_back(k);

		bit[k] = '0';
	}

	assert(lf.size() == rg.size());

	int m = (l + r) >> 1;

	for(auto &k : rg) bit[k] = '1';

	query(l, m, lf);

	for(auto &k : rg) bit[k] = '0';
	for(auto &k : lf) bit[k] = '1';

	query(m, r, rg);

	for(auto &k : lf) bit[k] = '0';
}

vector<int> restore_permutation(int n, int w, int r) {
	ans.resize(n);
	vector<int> idx(n);

	for(int i = 0; i < n; i++) bit += '0';

	iota(idx.begin(), idx.end(), 0);

	//[0, n)
	generate(0, n);
	compile_set();
	query(0, n, idx);

    return ans;
}

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