Submission #373683

#	Time	Username	Problem	Language	Result	Execution time	Memory
373683		LucaDantas	Unscrambling a Messy Bug (IOI16_messy)	C++17	20 / 100	1 ms	364 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;

bool on(int mask, int i) { return (mask&(1 << i)) > 0; }

vector<int> restore_permutation(int n, int w, int r) {
	vector<int> p(n);
	string s;
	for(int i = 0; i < n; i++)
		s.push_back('0');
	if(n == 8) {
		// caso brute de read
		for(int i = 0; i < n; i++)
			s[i] = '1', add_element(s);
		compile_set();
		vector<int> masks(n), mark(n);
		for(int mask = 0; mask < (1 << n); mask++) {
			for(int i = 0; i < n; i++)
				s[i] = on(mask, i)?'1':'0';
			int c = __builtin_popcount(mask);
			if(check_element(s)) masks[c-1] = mask;
		}
		for(int i = 0; i < n; i++) {
			// printf("%d\n", masks[i]);
			// bitset<8> b(masks[i]);
			// cout << b << endl;
			for(int j = 0; j < n; j++)
				if(on(masks[i], j) && !mark[j])
					mark[j] = 1, p[i] = j;
		}
	}
	if(n == 32 && r == 1024) {
		// vai na fe pq eu n to a fim de fazer um caso desse tamanho
		for(int i = 0; i < n; i++)
			s[i] = '1', add_element(s);
		compile_set();

		vector<int> masks(n), mark(n);
		long long val = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(mark[j]) continue;
				bitset<32> b(val+(1 << j));
				s = b.to_string();
				reverse(s.begin(), s.end());
				if(check_element(s)) {
					p[i] = j;
					mark[j] = 1;
					val += 1 << j;
				}
			}
		}
	}
	vector<int> ans(n);
	for(int i = 0; i < n; i++)
		ans[p[i]] = i;
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 18
• Subtask 3: 0 / 11
• Subtask 4: 0 / 21
• Subtask 5: 0 / 30