oj.uz

Submission #20600

# Submission time Handle Problem Language Result Execution time Memory
20600 2017-02-12T15:42:20 Z model_code Unscrambling a Messy Bug (IOI16_messy) C++11
100 / 100
 5 ms 560 KB 
// name = messy_cpp_ok.cpp, type = cpp.g++11

#include "messy.h"
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;


	int nn;
	string address;

	void helper(int length, int w) {
		fill(address.begin(), address.end(), '1');
		for (int i = w; i < nn; i += (1 << length)) {
			address[i] = '0';
		}
		int j = w;
		for (int i = 0; i < (nn / (1 << length)); i++) {
			address[j] = '1';
			if (i % 2 == 1) {
				add_element(address);
			}
			address[j] = '0';
			j += 1 << length;
		}
	}

	void doWrites(int n_) {
		nn = n_;
		address = string(nn, '0');
		for (int i = 0; i < nn; i++) {
			fill(address.begin(), address.end(), '0');
			address[i] = '1';
			if (i % 2 == 1) {
				add_element(address);
			}
		}
		int x = 1;
		int log = 0;
		while (x < nn) {
			x *= 2;
			log++;
		}
		for (int length = 1; length < log; length++) {
			for (int i = 0; i < (1 << length); i++) {
				helper(length, i);
			}
		}
	}

	void read(const vector<int> &t, vector<int>& answer, int step, int w) {
		if (t.size() == 1) {
			answer[t[0]] = w;
			return;
		}
		vector<int> t0;
		vector<int> t1;
		fill(address.begin(), address.end(), '1');
		for (int j : t) {
			address[j] = '0';
		}
		for (int j : t) {
			address[j] = '1';
			if (!check_element(address)) {
				t0.push_back(j);
			}
			else {
				t1.push_back(j);
			}
			address[j] = '0';
		}
		read(t0, answer, step + 1, w);
		read(t1, answer, step + 1, w + (1 << step));
	}

	void doReads(int nn, vector<int>& answer) {
		vector<int> order = vector<int>(nn);
		for (int i = 0; i < nn; i++) {
			order[i] = i;
		}
		read(order, answer, 0, 0);
	}

	vector<int> restore_permutation(int nn, int w, int r) {
		doWrites(nn);
		compile_set();
		vector<int> answer(nn);
		doReads(nn, answer);
		return answer;
	}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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