Submission #135565

#	Time	Username	Problem	Language	Result	Execution time	Memory
135565		MAMBA	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	632 KiB

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 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30