oj.uz

Submission #131816

# Submission time Handle Problem Language Result Execution time Memory
131816 2019-07-17T17:06:47 Z hugo_pm Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 4 ms 640 KB 
#include <vector>
#include "messy.h"
using namespace std;

int nbBits;
vector<int> permAns;

string vide;

void preparer(int gauche, int droite)
{
	if (gauche == droite) return;
	string rq = vide;
	for (int pos = 0; pos < nbBits; ++pos) {
		rq[pos] = ((gauche <= pos && pos <= droite) ? '0' : '1');
	}

	int mid = (gauche + droite) / 2;

	for (int pos = gauche; pos <= mid; ++pos) {
		rq[pos] = '1';
		fflush(stdout);
		add_element(rq);
		rq[pos] = '0';
	}

	preparer(gauche, mid);
	preparer(mid+1, droite);
}

void catchMe(int gaucheBase, int droiteBase, vector<bool> estInclus)
{
	if (gaucheBase == droiteBase) {
		for (int pos = 0; pos < nbBits; ++pos) {
			if (estInclus[pos]) {
				permAns[pos] = gaucheBase;
			}
		}
		return;
	}

	string rq = vide;

	vector<bool> incLeft(nbBits, false);
	vector<bool> incRight(nbBits, false);

	for (int pos = 0; pos < nbBits; ++pos) {
		rq[pos] = (estInclus[pos] ? '0' : '1');
	}

	for (int pos = 0; pos < nbBits; ++pos) {
		if (estInclus[pos]) {
			rq[pos] = '1';
			bool dansSet = check_element(rq);
			rq[pos] = '0';
			if (dansSet) incLeft[pos] = true;
			else incRight[pos] = true;
		}
	}

	int mid = (gaucheBase+droiteBase) / 2;
	catchMe(gaucheBase, mid, incLeft);
	catchMe(mid+1, droiteBase, incRight);
}

std::vector<int> restore_permutation(int _n, int _w, int _r)
{
	nbBits = _n;
	vide.resize(nbBits);
	permAns.resize(nbBits);
	preparer(0, nbBits-1);
	compile_set();

	catchMe(0, nbBits-1, vector<bool>(nbBits, true));
	return permAns;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 380 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 356 KB n = 32
11 Correct 2 ms 380 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 376 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 252 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 376 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 508 KB n = 128
2 Correct 4 ms 508 KB n = 128
3 Correct 4 ms 504 KB n = 128
4 Correct 4 ms 504 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 4 ms 504 KB n = 128
9 Correct 4 ms 504 KB n = 128
10 Correct 4 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 4 ms 504 KB n = 128

Subtask #5
30.0 / 30.0

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