Submission #1021866

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

messy

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

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

int n;
int i, j;

string get(int l, int r){
	string s = string(n, '0');
	for(int i = l; i <= r; i++) s[i] = '1';
	return s;
}

void calc1(int l = 0, int r = n - 1){
	if(l == r) return;
	int mid = (l + r) >> 1;
	add_element(get(l, mid));
	calc1(l, mid); 
	calc1(mid + 1, r);
}

void calc2(int l = 0, int r = n - 1){
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(!check_element(get(l, mid))){
		for(i = l; i <= mid; i++){
			for(j = mid + 1; j <= r; j++){
				string s = get(l, mid);
				swap(s[i], s[j]);
				if(check_element(s)){
					return;
				}
			}
		}
	}
	calc2(l, mid); calc2(mid+1, r);
}

vector<int> restore_permutation(int N, int w, int r){
	n = N;
	calc1();
	compile_set();
	calc2();
	vector<int> ans;
	for(int i = 0; i < n; i++){
		ans.push_back(i);
	}
	swap(ans[i], ans[j]);
	return ans;
}

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