제출 #373688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373688		LucaDantas	Unscrambling a Messy Bug (IOI16_messy)	C++17	38 / 100	3 ms	384 KiB

messy

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

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

string convert(long long v, int b) {
	string s;
	for(int i = 0; i < b; i++)
		s.push_back('0');
	for(int i = 0; i < b; i++)
		if(on(v, i)) s[i] = '1';
	return s;
}

int mark[200];

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();

		long long val = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(mark[j]) continue;
				s = convert(val+(1ll << j), n);
				// cout << s << " " << val + (1ll << j) << endl;
				if(check_element(s)) {
					p[i] = j;
					mark[j] = 1;
					val += 1ll << j;
					break;
				}
			}
			// break;
		}
	// }
	vector<int> ans(n);
	for(int i = 0; i < n; i++)
		ans[p[i]] = i;
	return ans;
}

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