Submission #703990

#	Time	Username	Problem	Language	Result	Execution time	Memory
703990		SamNguyen	Unscrambling a Messy Bug (IOI16_messy)	C++14	38 / 100	1 ms	300 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 {
	const int N = 32, W = 320, R = 1024;
	vector<int> perm;

	void add_elements() {
		string tmp(N, '0');
		for (int i = 0; i < N; i++) {
			tmp[i] = '1';
			add_element(tmp);
		}
	}

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

		string tmp(N, '0');
		for (int i = 0; i < N; i++) {
			for (int x = 0; x < N; x++) if (tmp[x] == '0') {
				tmp[x] ^= 1;
				if (i == N - 1 or check_element(tmp)) {
					perm[x] = i;
					break;
				}
				tmp[x] ^= 1;
			}
		}
	}

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

		return perm;
	}
};

namespace subtask_full {
	vector<int> perm;

	void add_elements() {
	}

	void check_elements() {
	}

	vector<int> restore_permutation(int n, int w, int r) {
		return perm;
	}
};

vector<int> restore_permutation(int n, int w, int r) {
    if (n == 8 and w == 256 and r == 256)
		return subtask_1::restore_permutation();
    if (n == 32 and w == 320 and r == 1024)
		return subtask_2::restore_permutation();

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

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