Submission #290169

#	Time	Username	Problem	Language	Result	Execution time	Memory
290169		amoo_safar	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	512 KiB

messy

#include <bits/stdc++.h>

#include "messy.h"

using namespace std;

typedef string str;

int n;
void Prep(int L, int R){
	if(L + 1 == R) return ;
	str s = "";
	for(int i = 0; i < n; i++) s += "0";
	for(int i = 0; i < L; i++) s[i] = '1';
	for(int i = R; i < n; i++) s[i] = '1';
	
	int mid = (L + R) >> 1;
	for(int i = L; i < mid; i++){
		s[i] = '1';
		add_element(s);
		//cerr << "# " << s << '\n';
		s[i] = '0';
	}

	Prep(L, mid);
	Prep(mid, R);
}

int P[200];

void Solve(int L, int R, vector<int> can){
	//cerr << "! " << L << " " << R << ' ' << can.size() << '\n';
	assert(R - L == (int) can.size());
	if(L + 1 == R){
		P[can[0]] = L;
		return ;
	}
	int mid = (L + R) >> 1;
	vector<int> V1, V0;

	str s = "";
	for(int i = 0; i < n; i++) s += "1";
	for(auto x : can) s[x] = '0';

	bool ask;
	for(auto x : can){
		s[x] = '1';
		ask = check_element(s);
		s[x] = '0';
		if(ask) V1.push_back(x);
		else V0.push_back(x);
	}
	Solve(L, mid, V1);
	Solve(mid, R, V0);
}

vector<int> restore_permutation(int _n, int w, int r){
	n = _n;
	//add_element("0");
	Prep(0, n);

	compile_set();
	
	vector<int> I(n);
	iota(I.begin(), I.end(), 0);
	Solve(0, n, I);
	//check_element("0");
	
	vector<int> res(n);
	for(int i = 0; i < n; i++) res[i] = P[i];
	return res;
}

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