oj.uz

Submission #604043

# Submission time Handle Problem Language Result Execution time Memory
604043 2022-07-24T16:09:06 Z elgamalsalman Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 520 KB 
#include <bits/stdc++.h>

// #include "grader.cpp"
#include "messy.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

int N;
int used_buffers[130];
vi perm;
map<ii, string> range_bases;

void construct_perm(int l, int r) {
	// cerr << "// construct_perm(" << l << ", " << r << ")\n";
	int interval_size = r - l;
	int m = (l + r) / 2;
	if (interval_size == 1) return;

	string base = range_bases[ii(l, r)];
	string new_base = range_bases[ii(l, r)];
	for (int i = 0; i < N; i++) {
		new_base[perm[i]] = base[i];
	}
	base = new_base;
	// cerr << "// base : " << base << '\n';

	
	set<int> left_locations, right_locations;
	for (int i = l; i < r; i++) {
		right_locations.insert(perm[i]);
	}

	for (int i = l; i < r; i++) {
		string input = "";
		copy(base.begin(), base.end(), back_inserter(input));
		// cerr << "// perm[" << i << "] : " << perm[i] << '\n';
		// assert((perm[i] == '0') && "perm[i] is occupied!");
		input[perm[i]] = '1';

		if (check_element(input)) {
			// cerr << "// " << input << " is present!\n";
			left_locations.insert(perm[i]);
			right_locations.erase(perm[i]);
		}
	}

	// cerr << "// left_locations :";
	// for (int ele : left_locations) cerr << ' ' << ele;
	// cerr << '\n';

	// cerr << "// right_locations :";
	// for (int ele : right_locations) cerr << ' ' << ele;
	// cerr << '\n';

	for (int i = l; i < r; i++) {
		if (i < m) {
			perm[i] = *left_locations.begin();
			left_locations.erase(perm[i]);
		} else {
			perm[i] = *right_locations.begin();
			right_locations.erase(perm[i]);
		}
	}

	// cerr << "// perm :";
	// for (int ele : perm) cerr << ' ' << ele;
	// cerr << '\n';

	construct_perm(l, m);
	construct_perm(m, r);
}

vi restore_permutation(int _n, int w, int r) {
	N = _n;
	for (int window_size = N; window_size >= 2; window_size /= 2) {
		// cerr << "// window_size : " << window_size << '\n';
		int sub_window_size = window_size / 2;
		for (int i = 0; i < N; i += window_size) {
			string base = "";

			for (int j = 0; j < N; j++) {
				bool bit = 0;
				if (i) { 
					if (j < sub_window_size) bit = 1;
				}
				if (j >= i + window_size) bit = 1;
				base += (bit ? "1" : "0");
			}

			range_bases[ii(i, i + window_size)] = base;

			for (int k = i; k < i + sub_window_size; k++) {
				string input = "";
				copy(base.begin(), base.end(), back_inserter(input));
				input[k] = '1';

				// cerr << "// input : " << input << '\n';
				add_element(input);
			}
		}
	}

	compile_set();

	perm.resize(N);
	for (int i = 0; i < N; i++) {
		perm[i] = i;
	}

	construct_perm(0, N);

	vi new_perm(N, 0);
	for (int i = 0; i < N; i++) {
		new_perm[perm[i]] = i;
	}
	perm = new_perm;

	return perm;
}

// 0000000000000000
// ????????00000000 : 0
// ????000011111111 : 8
// 11110000????0000 : 4
// ??00111111111111 : 12
// 1100??0011111111 : 10
// 11000000??001111 : 6
// 110000000000??00 : 2
// ?011111111111111 : 14
// 1011111111111111 : 14

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 8
2 Correct 1 ms 212 KB n = 8
3 Correct 1 ms 300 KB n = 8
4 Correct 0 ms 304 KB n = 8
5 Correct 1 ms 212 KB n = 8
6 Correct 1 ms 300 KB n = 8
7 Correct 1 ms 296 KB n = 8
8 Correct 1 ms 212 KB n = 8
9 Correct 1 ms 212 KB n = 8
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 300 KB n = 8
15 Correct 1 ms 300 KB n = 8

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB n = 128
2 Correct 3 ms 468 KB n = 128
3 Correct 3 ms 468 KB n = 128
4 Correct 3 ms 468 KB n = 128
5 Correct 3 ms 468 KB n = 128
6 Correct 3 ms 432 KB n = 128
7 Correct 3 ms 520 KB n = 128
8 Correct 3 ms 424 KB n = 128
9 Correct 3 ms 428 KB n = 128
10 Correct 3 ms 468 KB n = 128
11 Correct 3 ms 468 KB n = 128
12 Correct 3 ms 468 KB n = 128
13 Correct 3 ms 428 KB n = 128
14 Correct 3 ms 468 KB n = 128
15 Correct 3 ms 468 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 516 KB n = 128
2 Correct 3 ms 468 KB n = 128
3 Correct 3 ms 468 KB n = 128
4 Correct 3 ms 424 KB n = 128
5 Correct 3 ms 420 KB n = 128
6 Correct 3 ms 468 KB n = 128
7 Correct 3 ms 468 KB n = 128
8 Correct 3 ms 468 KB n = 128
9 Correct 3 ms 468 KB n = 128
10 Correct 4 ms 468 KB n = 128
11 Correct 4 ms 468 KB n = 128
12 Correct 3 ms 428 KB n = 128
13 Correct 4 ms 468 KB n = 128
14 Correct 3 ms 468 KB n = 128
15 Correct 3 ms 432 KB n = 128