Submission #604043

#	Time	Username	Problem	Language	Result	Execution time	Memory
604043		elgamalsalman	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	520 KiB

messy

#include <bits/stdc++.h>

// #include "grader.cpp"
#include "messy.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

int N;
int used_buffers[130];
vi perm;
map<ii, string> range_bases;

void construct_perm(int l, int r) {
	// cerr << "// construct_perm(" << l << ", " << r << ")\n";
	int interval_size = r - l;
	int m = (l + r) / 2;
	if (interval_size == 1) return;

	string base = range_bases[ii(l, r)];
	string new_base = range_bases[ii(l, r)];
	for (int i = 0; i < N; i++) {
		new_base[perm[i]] = base[i];
	}
	base = new_base;
	// cerr << "// base : " << base << '\n';

	
	set<int> left_locations, right_locations;
	for (int i = l; i < r; i++) {
		right_locations.insert(perm[i]);
	}

	for (int i = l; i < r; i++) {
		string input = "";
		copy(base.begin(), base.end(), back_inserter(input));
		// cerr << "// perm[" << i << "] : " << perm[i] << '\n';
		// assert((perm[i] == '0') && "perm[i] is occupied!");
		input[perm[i]] = '1';

		if (check_element(input)) {
			// cerr << "// " << input << " is present!\n";
			left_locations.insert(perm[i]);
			right_locations.erase(perm[i]);
		}
	}

	// cerr << "// left_locations :";
	// for (int ele : left_locations) cerr << ' ' << ele;
	// cerr << '\n';

	// cerr << "// right_locations :";
	// for (int ele : right_locations) cerr << ' ' << ele;
	// cerr << '\n';

	for (int i = l; i < r; i++) {
		if (i < m) {
			perm[i] = *left_locations.begin();
			left_locations.erase(perm[i]);
		} else {
			perm[i] = *right_locations.begin();
			right_locations.erase(perm[i]);
		}
	}

	// cerr << "// perm :";
	// for (int ele : perm) cerr << ' ' << ele;
	// cerr << '\n';

	construct_perm(l, m);
	construct_perm(m, r);
}

vi restore_permutation(int _n, int w, int r) {
	N = _n;
	for (int window_size = N; window_size >= 2; window_size /= 2) {
		// cerr << "// window_size : " << window_size << '\n';
		int sub_window_size = window_size / 2;
		for (int i = 0; i < N; i += window_size) {
			string base = "";

			for (int j = 0; j < N; j++) {
				bool bit = 0;
				if (i) { 
					if (j < sub_window_size) bit = 1;
				}
				if (j >= i + window_size) bit = 1;
				base += (bit ? "1" : "0");
			}

			range_bases[ii(i, i + window_size)] = base;

			for (int k = i; k < i + sub_window_size; k++) {
				string input = "";
				copy(base.begin(), base.end(), back_inserter(input));
				input[k] = '1';

				// cerr << "// input : " << input << '\n';
				add_element(input);
			}
		}
	}

	compile_set();

	perm.resize(N);
	for (int i = 0; i < N; i++) {
		perm[i] = i;
	}

	construct_perm(0, N);

	vi new_perm(N, 0);
	for (int i = 0; i < N; i++) {
		new_perm[perm[i]] = i;
	}
	perm = new_perm;

	return perm;
}

// 0000000000000000
// ????????00000000 : 0
// ????000011111111 : 8
// 11110000????0000 : 4
// ??00111111111111 : 12
// 1100??0011111111 : 10
// 11000000??001111 : 6
// 110000000000??00 : 2
// ?011111111111111 : 14
// 1011111111111111 : 14

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