Submission #704031

#	Time	Username	Problem	Language	Result	Execution time	Memory
704031		SamNguyen	Unscrambling a Messy Bug (IOI16_messy)	C++14	49 / 100	1 ms	304 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 {
	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)
		return subtask_2::restore_permutation(n, w, r);

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

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