oj.uz

Submission #122652

# Submission time Handle Problem Language Result Execution time Memory
122652 2019-06-29T02:18:38 Z anayk Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 632 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 8
2 Correct 2 ms 376 KB n = 8
3 Correct 2 ms 376 KB n = 8
4 Correct 2 ms 380 KB n = 8
5 Correct 2 ms 376 KB n = 8
6 Correct 2 ms 256 KB n = 8
7 Correct 2 ms 256 KB n = 8
8 Correct 2 ms 376 KB n = 8
9 Correct 2 ms 376 KB n = 8
10 Correct 2 ms 376 KB n = 8
11 Correct 2 ms 376 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 376 KB n = 8
14 Correct 2 ms 376 KB n = 8
15 Correct 2 ms 504 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB n = 32
2 Correct 2 ms 376 KB n = 32
3 Correct 2 ms 348 KB n = 32
4 Correct 2 ms 424 KB n = 32
5 Correct 2 ms 376 KB n = 32
6 Correct 2 ms 376 KB n = 32
7 Correct 2 ms 376 KB n = 32
8 Correct 2 ms 376 KB n = 32
9 Correct 2 ms 380 KB n = 32
10 Correct 2 ms 276 KB n = 32
11 Correct 2 ms 376 KB n = 32
12 Correct 2 ms 376 KB n = 32
13 Correct 2 ms 376 KB n = 32
14 Correct 2 ms 376 KB n = 32
15 Correct 2 ms 504 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 32
2 Correct 2 ms 376 KB n = 32
3 Correct 2 ms 376 KB n = 32
4 Correct 2 ms 376 KB n = 32
5 Correct 2 ms 376 KB n = 32
6 Correct 2 ms 376 KB n = 32
7 Correct 2 ms 376 KB n = 32
8 Correct 2 ms 376 KB n = 32
9 Correct 2 ms 376 KB n = 32
10 Correct 2 ms 376 KB n = 32
11 Correct 2 ms 376 KB n = 32
12 Correct 2 ms 376 KB n = 32
13 Correct 2 ms 376 KB n = 32
14 Correct 2 ms 380 KB n = 32
15 Correct 2 ms 376 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB n = 128
2 Correct 4 ms 504 KB n = 128
3 Correct 4 ms 504 KB n = 128
4 Correct 4 ms 476 KB n = 128
5 Correct 4 ms 504 KB n = 128
6 Correct 3 ms 504 KB n = 128
7 Correct 3 ms 504 KB n = 128
8 Correct 3 ms 504 KB n = 128
9 Correct 3 ms 504 KB n = 128
10 Correct 3 ms 504 KB n = 128
11 Correct 3 ms 504 KB n = 128
12 Correct 3 ms 504 KB n = 128
13 Correct 3 ms 504 KB n = 128
14 Correct 3 ms 504 KB n = 128
15 Correct 4 ms 504 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB n = 128
2 Correct 3 ms 504 KB n = 128
3 Correct 3 ms 504 KB n = 128
4 Correct 3 ms 504 KB n = 128
5 Correct 3 ms 508 KB n = 128
6 Correct 3 ms 504 KB n = 128
7 Correct 3 ms 504 KB n = 128
8 Correct 3 ms 508 KB n = 128
9 Correct 3 ms 508 KB n = 128
10 Correct 3 ms 504 KB n = 128
11 Correct 4 ms 504 KB n = 128
12 Correct 4 ms 504 KB n = 128
13 Correct 4 ms 504 KB n = 128
14 Correct 3 ms 504 KB n = 128
15 Correct 3 ms 504 KB n = 128