oj.uz

Submission #394123

# Submission time Handle Problem Language Result Execution time Memory
394123 2021-04-25T16:32:46 Z Mounir Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 484 KB 
#include <bits/stdc++.h>
#include "messy.h"
#define pb push_back
using namespace std;

int nBits;

void ajouterElements(int gauche, int droite){
	if (gauche == droite)
		return;

	int milieu = (gauche + droite)/2;
	for (int a0 = gauche; a0 <= milieu; ++a0){
		string chaine = "";
		for (int _ = 0; _ < nBits; ++_)
			chaine += '0';
		for (int ind = gauche; ind <= droite; ++ind)
			chaine[ind] = '1';
		chaine[a0] = '0';

		//cout << "ADD " << chaine << endl;

		add_element(chaine);
	}

	ajouterElements(gauche, milieu);
	ajouterElements(milieu + 1, droite);
}

vector<int> permutation;

void retrouver(int gauche, int droite, vector<int> iChiffres){
	if (gauche == droite){
		permutation[iChiffres[0]] = gauche;
		return;
	}

	vector<int> aGauche, aDroite;
	for (int ind : iChiffres){
		string chaine = "";
		for (int _ = 0; _ < nBits; ++_)
			chaine += '0';
		for (int iChiffre : iChiffres)
			chaine[iChiffre] = '1';
		chaine[ind] = '0';

	//	cout << "ASK " << chaine << " " << check_element(chaine) << endl;

		if (check_element(chaine))
			aGauche.pb(ind);
		else
			aDroite.pb(ind);
	}
/*
	cout << "SEQ " << gauche << " " << droite << endl;
	for (int e : aGauche)
		cout << e << " ";
	cout << endl;
	for (int e : aDroite)
		cout << e << " ";
	cout << endl << endl;*/

	int milieu = (gauche + droite)/2;
	retrouver(gauche, milieu, aGauche);
	retrouver(milieu + 1, droite, aDroite);
}

vector<int> restore_permutation(int n, int w, int r) {
	nBits = n;
	permutation.resize(nBits);
	for (int ind = 0; ind < nBits; ++ind)
		permutation[ind] = ind;
	ajouterElements(0, nBits - 1);
	compile_set();
	retrouver(0, nBits - 1, permutation);
	/*for (int e : permutation)
		cout << e << " ";
	cout << endl;*/
	return permutation;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB n = 128
2 Correct 4 ms 460 KB n = 128
3 Correct 4 ms 460 KB n = 128
4 Correct 3 ms 460 KB n = 128
5 Correct 3 ms 460 KB n = 128
6 Correct 3 ms 424 KB n = 128
7 Correct 3 ms 424 KB n = 128
8 Correct 3 ms 460 KB n = 128
9 Correct 4 ms 484 KB n = 128
10 Correct 3 ms 408 KB n = 128
11 Correct 3 ms 412 KB n = 128
12 Correct 3 ms 460 KB n = 128
13 Correct 3 ms 372 KB n = 128
14 Correct 3 ms 460 KB n = 128
15 Correct 4 ms 464 KB n = 128