Submission #127663

#	Time	Username	Problem	Language	Result	Execution time	Memory
127663		Sorting	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	6 ms	632 KiB

messy

#include <bits/stdc++.h>

using namespace std;

void add_element(string x);
void compile_set();
bool check_element(string x);

void add(string &s, int l, int r){
	if(l == r){
		return;
	}

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

	for(int i = l; i <= mid; i++){
		s[i] = '1';

		add_element(s);

		s[i] = '0';
	}

	for(int i = l; i <= mid; i++){
		s[i] = '1';
	}
	add(s, mid + 1, r);

	for(int i = l; i <= mid; i++){
		s[i] = '0';
	}
	for(int i = mid + 1; i <= r; i++){
		s[i] = '1';
	}
	add(s, l, mid);

	for(int i = mid + 1; i <= r; i++){
		s[i] = '0';
	}
}

vector<int> v1, v2;

void solve(vector<int> &p, string &s, int l, int r){
	if(l == r){
		return;
	}

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

	for(int i = l; i <= r; i++){
		s[p[i]] = '1';

		if(check_element(s)){
			v1.push_back(p[i]);
		}
		else{
			v2.push_back(p[i]);
		}

		s[p[i]] = '0';
	}

	//while(v1.size() != mid - l + 1);

	for(int i = l; i <= mid; i++){
		p[i] = v1[i - l];
	}
	for(int i = mid + 1; i <= r; i++){
		p[i] = v2[i - mid - 1];
	}
	v1.clear();
	v2.clear();

	for(int i = mid + 1; i <= r; i++){
		s[p[i]] = '1';
	}
	solve(p, s, l, mid);

	for(int i = mid + 1; i <= r; i++){
		s[p[i]] = '0';
	}
	for(int i = l; i <= mid; i++){
		s[p[i]] = '1';
	}

	solve(p, s, mid + 1, r);
	for(int i = l; i <= mid; i++){
		s[p[i]] = '0';
	}
}

vector<int> restore_permutation(int n, int w, int r){
	string s;
	for(int i = 0; i < n; i++){
		s += '0';
	}

	add(s, 0, n - 1);
	compile_set();

	vector<int> p;

	for(int i = 0; i < n; i++){
		p.push_back(i);
	}

	solve(p, s, 0, n - 1);

	vector<int> ret;

	for(int i = 0; i < n; i++){
		ret.push_back(i);
	}

	for(int i = 0; i < n; i++){
		ret[p[i]] = i;
	}

	return ret;
}

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