Submission #704025

#	Time	Username	Problem	Language	Result	Execution time	Memory
704025		SamNguyen	Unscrambling a Messy Bug (IOI16_messy)	C++14	18 / 100	1 ms	340 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 = 320;
	vector<int> perm, inds;
 
	void add_elements() {
		inds.resize(N);
		iota(inds.begin(), inds.end(), 0);
		shuffle(inds.begin(), inds.end(), mt19937(time(NULL)));
 
		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;
					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) {
		return subtask_2::restore_permutation();
}

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