Submission #792003

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

messy

#include <bits/stdc++.h>
using namespace std;

int ans[128];
int N;
void add_element(string x);
void compile_set();
bool check_element(string x);

void solve(int l, int r, set<int> ind){
	if (r==l){
		ans[*ind.begin()] = l;
		return;
	}
	set<int> lset;
	string f = string(N, '0');
	for (auto c: ind) f[c] = '1';
	for (auto c: ind){
		f[c] = '0';
		if (check_element(f)) lset.insert(c);
		f[c] = '1';
	}
	set<int> rset;
	for (int c: ind) if (!lset.count(c)) rset.insert(c);
	solve(l, l + (r-l)/2, lset);
	solve(l+(r-l+1)/2, r, rset);

}

vector<int> restore_permutation(int n, int w, int r){
	N = n;
	int k = 0; int rr = n; while (rr!=1) rr/=2, k++;
	for (int i=0; i<k; i++){
		int b = n/(1<<i);
		for (int l = 0; l<n; l+=b){
			string f = string(l, '0') + string(b,'1') + string(n-l-b, '0');
			for (int j = l; j<l+b/2; j++){
				f[j] = '0';
				add_element(f);
				f[j] = '1';
			}
		}
	}
	compile_set();
	set<int> st; for (int i=0; i<n; i++) st.insert(i);
	solve(0, n-1, st);
	vector<int> res(n);
	for (int i=0; i<n; i++){
		res[i] = ans[i];
	}
	return res;
}

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