Submission #704162

#	Time	Username	Problem	Language	Result	Execution time	Memory
704162		SamNguyen	Unscrambling a Messy Bug (IOI16_messy)	C++14	51 / 100	2 ms	468 KiB

messy

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

namespace subtask_1 {
	const int N = 8, W = 256, R = 256;
	vector<int> perm;

	string get_str(int l, int r) {
		int m = (l + r) >> 1;
		string str(N, '0');
		fill(str.begin() + l, str.begin() + m + 1, '1');
		return str;
	}

	template <class F>
	void traverse_tree(F f, int l = 0, int r = N - 1) {
		if (l == r)
			return;
		
		bool ok = f(l, r);
		if (not ok)
			return;

		int m = (l + r) >> 1;
		traverse_tree(f, l, m);
		traverse_tree(f, m + 1, r);
	}

	void add_elements() {
		traverse_tree([&](int l, int r) {
			add_element(get_str(l, r));
			return true;
		});
	}

	void check_elements() {
		vector<int> inds;

		traverse_tree([&](int l, int r) {
			string str = get_str(l, r);
			int m = (l + r) >> 1;

			for (int i = l; i <= m; i++)
			for (int j = m + 1; j <= r; j++) {
				swap(str[i], str[j]);
				if (check_element(str)) {
					inds = {i, j};
					return false;
				}
				swap(str[i], str[j]);
			}

			return true;
		});

		perm.resize(N);
		iota(perm.begin(), perm.end(), 0);

		if (not inds.empty()) 
			swap(perm[inds.front()], perm[inds.back()]);

		return;
	}

	vector<int> restore_permutation() {
		add_elements();
		compile_set();
		check_elements();

		return perm;
	}
};

namespace subtask_2 {
	int N, W, R;
	vector<int> perm, inds;

	void add_elements() {
		inds.resize(N);
		iota(inds.begin(), inds.end(), 0);
		shuffle(inds.begin(), inds.end(), mt19937(0));

		string tmp(N, '0');
		for (int i : inds) {
			tmp[i] = '1';
			add_element(tmp);
		}
	}

	void check_elements() {
		perm.resize(N);

		string tmp(N, '0');
		for (int i : inds) {
			for (int x : inds) if (tmp[x] == '0') {
				tmp[x] ^= 1;
				if (check_element(tmp)) {
					perm[x] = i;
					//cout << "perm[" << x << "] = " << i << endl;
					break;
				}
				tmp[x] ^= 1;
			}
		}
	}

	vector<int> restore_permutation(int n, int w, int r) {
		N = n, W = w, R = r;
		
		add_elements();
		compile_set();
		check_elements();

		return perm;
	}
};

namespace subtask_full {
	int N, W, R;
	vector<int> perm;

	void add_elements(int l, int r) {
		if (l >= r)
			return;

		int m = (l + r) >> 1;
		
		string tmp(N, '1');
		for (int i = l; i <= r; i++)
			tmp[i] = '0';

		for (int i = l; i <= m; i++) {
			tmp[i] = '1';
			add_element(tmp);
			tmp[i] = '0';
		}

		add_elements(l, m);
		add_elements(m + 1, r);
	}

	inline void add_elements() { add_elements(0, N - 1); }

	void check_elements(int l, int r, vector<int> vals) {
		if (l >= r) {
			perm[vals[0]] = r;
			return;
		}

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

		string tmp(N, '1');
		for (int i : vals)
			tmp[i] = '0';

		vector<int> left_vals, right_vals;

		for (int v : vals) {
			tmp[v] = '1';
			if (check_element(tmp))
				left_vals.push_back(v);
			else
				right_vals.push_back(v);

			tmp[v] = '0';
		}

		check_elements(l, m, left_vals);
		check_elements(m + 1, r, right_vals);
	}

	inline void check_elements() { 
		vector<int> vals(N);
		iota(vals.begin(), vals.end(), 0);
		perm.resize(N);
		check_elements(0, N - 1, vals); 
	}

	vector<int> restore_permutation(int n, int w, int r) {
		N = n, W = w, R = r;

		add_elements();
		compile_set();
		check_elements();

		return perm;
	}
};

vector<int> restore_permutation(int n, int w, int r) {
	if (n <= 32)
		subtask_2::restore_permutation(n, w, r);

	return subtask_full::restore_permutation(n, w, r);
}

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