Submission #405692

#	Time	Username	Problem	Language	Result	Execution time	Memory
405692		rainboy	Unscrambling a Messy Bug (IOI16_messy)	C11	100 / 100	6 ms	2196 KiB

messy

#include "messy_c.h"
#include <string.h>

#define N	128

char cc[N + 1]; int pp[N];

void write(int l, int r) {
	int m, i;

	if (r - l == 1)
		return;
	m = (l + r) / 2;
	memset(cc + l, '0', (r - l) * sizeof *cc);
	for (i = l; i < m; i++)
		cc[i] = '1', add_element(cc), cc[i] = '0';
	memset(cc + m, '1', (r - m) * sizeof *cc), write(l, m);
	memset(cc + l, '1', (m - l) * sizeof *cc), write(m, r);
}

void read(int l, int r) {
	int m, i, j;

	if (r - l == 1)
		return;
	m = (l + r) / 2;
	for (i = l; i < r; i++)
		cc[pp[i]] = '0';
	i = l, j = r;
	while (i < j) {
		int x, tmp;

		cc[pp[i]] = '1', x = check_element(cc), cc[pp[i]] = '0';
		if (x)
			i++;
		else {
			j--;
			tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
		}
	}
	for (i = m; i < r; i++)
		cc[pp[i]] = '1';
	read(l, m);
	for (i = l; i < m; i++)
		cc[pp[i]] = '1';
	read(m, r);
}

void restore_permutation(int n, int w, int r, int *ii) {
	int i;

	write(0, n);
	compile_set();
	for (i = 0; i < n; i++)
		pp[i] = i;
	read(0, n);
	for (i = 0; i < n; i++)
		ii[pp[i]] = i;
}

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