Submission #135565

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135565	2019-07-24T08:23:34 Z	MAMBA	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	632 KB

messy

#include <bits/stdc++.h>
#include "messy.h"

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back

typedef vector<int> vi;

bitset<512> bs;

vi restore_permutation(int n, int w, int r) {

	bs.reset();

	for (int bt = 0; (1 << bt) != n; bt++) {
		string s;
		rep(i , 0 , n) s.pb(bs[i] ? '1' : '0');
		bs.reset();
		rep(i , 0 , n) 
			if ((i >> bt) & 1) {
				bs[i] = true;
				s[i] ^= 1;
				add_element(s);
				s[i] ^= 1;
			}
	}

	compile_set();

	string s;
	vi res(n);
	rep(i , 0 , n) s.pb('0');
	for (int bt = 0; (1 << bt) != n; bt++) {
		bs.reset();
		rep(i , 0 , n) {
			s[i] ^= 1;
			if (check_element(s)) {
				bs[i] = true;
				res[i] += (1 << bt);
			}
			s[i] ^= 1;
		}
		rep(i , 0 , n) {
			s[i] = '0';
			if (bs[i]) 
				s[i] = '1';
		}
	}

	return res;

}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	n = 8
2	Correct	2 ms	376 KB	n = 8
3	Correct	2 ms	376 KB	n = 8
4	Correct	2 ms	364 KB	n = 8
5	Correct	2 ms	252 KB	n = 8
6	Correct	2 ms	376 KB	n = 8
7	Correct	2 ms	256 KB	n = 8
8	Correct	2 ms	256 KB	n = 8
9	Correct	2 ms	376 KB	n = 8
10	Correct	2 ms	380 KB	n = 8
11	Correct	2 ms	376 KB	n = 8
12	Correct	2 ms	376 KB	n = 8
13	Correct	2 ms	256 KB	n = 8
14	Correct	2 ms	256 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	2 ms	376 KB	n = 32
2	Correct	2 ms	248 KB	n = 32
3	Correct	2 ms	380 KB	n = 32
4	Correct	2 ms	376 KB	n = 32
5	Correct	3 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	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	348 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	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	3 ms	504 KB	n = 128
2	Correct	3 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	3 ms	504 KB	n = 128
7	Correct	4 ms	504 KB	n = 128
8	Correct	3 ms	504 KB	n = 128
9	Correct	4 ms	504 KB	n = 128
10	Correct	3 ms	504 KB	n = 128
11	Correct	4 ms	504 KB	n = 128
12	Correct	3 ms	520 KB	n = 128
13	Correct	4 ms	632 KB	n = 128
14	Correct	4 ms	504 KB	n = 128
15	Correct	3 ms	504 KB	n = 128

Subtask #5

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	n = 128
2	Correct	3 ms	504 KB	n = 128
3	Correct	3 ms	484 KB	n = 128
4	Correct	3 ms	504 KB	n = 128
5	Correct	3 ms	504 KB	n = 128
6	Correct	3 ms	504 KB	n = 128
7	Correct	4 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	548 KB	n = 128
13	Correct	3 ms	504 KB	n = 128
14	Correct	4 ms	504 KB	n = 128
15	Correct	4 ms	504 KB	n = 128