Submission #1182369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182369		Nonoze	Unscrambling a Messy Bug (IOI16_messy)	C++20	70 / 100	3 ms	584 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
using namespace std;


int calc(string shouldbe) {
	for (int i=0; i<sz(shouldbe); i++) {
		shouldbe[i]=(shouldbe[i]=='1' ? '0' : '1');
	}
	int lst=0;
	for (int i=0; i<sz(shouldbe); i++) if (shouldbe[i]=='1') {
		shouldbe[i]='0';
		if (check_element(shouldbe)) return i;
		shouldbe[i]='1';
	}
	assert(0);
	return -1;
}

// 2 1 3 0 -> 3 1 0 2

vector<int> restore_permutation(int n, int w, int r) {
	vector<int> p(n, -1);
	vector<vector<int>> ans, ans2;
	string shouldbe(n, '0'), s(n, '0'), s2(n, '1');
	for (int val=1, idx=1; val<n; val*=2, idx++) {
		s2[n-idx]='0', s[n-idx]='1'; add_element(s2);
		for (int i=0; i<n; i++) {
			if ((i/val)%2 == 0) {
				s[i]='1';
				add_element(s);
				s[i]='0';
			}
		}
	}
	compile_set();
	for (int val=1; val<n; val*=2) {
		s[n-sz(ans)-1]='1';
		p[n-sz(ans)-1]=calc(shouldbe);
		shouldbe[p[n-sz(ans)-1]]='1';
		ans.push_back({}), ans2.push_back({});
		for (int i=0; i<n; i++) if (shouldbe[i]=='0') {
			shouldbe[i]='1';
			if (check_element(shouldbe)) ans.back().push_back(i);
			else ans2.back().push_back(i);
			shouldbe[i]='0';
		} else ans2.back().push_back(i);
	}
	for (int i=0; i<n-sz(ans); i++) {
		set<int> possible;
		for (int j=0; j<n; j++) possible.insert(j);
		for (int LOG=0; LOG<sz(ans); LOG++) {
			set<int> npossible;
			if ((i&(1<<LOG)) == 0) {
				for (auto &u: ans[LOG]) {
					if (possible.count(u)) {
						npossible.insert(u);
					}
				}
			} else {
				for (auto &u: ans2[LOG]) {
					if (possible.count(u)) {
						npossible.insert(u);
					}
				}
			}
			possible=npossible;
		}
		p[i]=*possible.begin();
	}
	vector<int> np(n); for (int i=0; i<n; i++) np[p[i]]=i;
	return np;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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