제출 #703755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703755		SamNguyen	Unscrambling a Messy Bug (IOI16_messy)	C++14	20 / 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;
	const int MAX = 255;

	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;
	}
};

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

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