Submission #122652

#	Time	Username	Problem	Language	Result	Execution time	Memory
122652		anayk	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	632 KiB

messy

#include <vector>
#include <string>

#include "messy.h"

#define MAXN 130

int N;
std::vector<int> result;

void add(int x, int y)
{
	if(x == y)
		return;

	std::string send;
	send.resize(N);

	for(int i = 0; i < N; i++)
		if(i < x || i > y)
			send[i] = '1';
		else
			send[i] = '0';

	int sz = y-x+1;

	for(int i = x; i < x + sz/2; i++)
	{
		send[i] = '1';
		add_element(send);
		send[i] = '0';
	}

	add(x, x + sz/2 - 1);
	add(x + sz/2, y);
}

void check(int x, int y, std::vector<int> &sample)
{
	if(x == y)
	{
		result[sample[0]] = x;
		return;
	}

	int sz = y-x+1;

	std::string send;
	send.resize(N);

	for(int i = 0; i < N; i++)
		send[i] = '1';

	for(int i = 0; i < sz; i++)
		send[sample[i]] = '0';

	std::vector<int> sample1, sample2;

	for(int i = 0; i < sz; i++)
	{
		send[sample[i]] = '1';
		bool ret = check_element(send);
		if(ret)
			sample1.push_back(sample[i]);
		else
			sample2.push_back(sample[i]);
		send[sample[i]] = '0';
	}

	check(x, x + sz/2 - 1, sample1);
	check(x + sz/2, y, sample2);
}

std::vector<int> restore_permutation(int n, int w, int r)
{
    // add_element("0");
    // compile_set();
    // check_element("0");
    // return std::vector<int>();

	result.resize(n);
	N = n;

    add(0, n-1);
    compile_set();

    std::vector<int> sample;
    for(int i = 0; i < N; i++)
    	sample.push_back(i);

    check(0, n-1, sample);

    return result;
}

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