Submission #157593

#	Time	Username	Problem	Language	Result	Execution time	Memory
157593		dennisstar	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	4 ms	520 KiB

messy

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

int s[150], e[150];
int n, cnt;

void f(int st, int re)
{
	if (re==st+1) return ;
	int md=(st+re)/2, i;
	string S;
	S="";
	for (i=0; i<n; i++) S.push_back('1');
	for (i=0; i<n; i++) {
		if (s[i]<=st&&re<=e[i]) S[i]='0';
	}
	for (i=0; i<n; i++) {
		if (s[i]<=st&&re<=e[i]) {
			S[i]='1';
			cnt++;
			if (check_element(S)) {
				s[i]=st; e[i]=md;
			}
			else {
				s[i]=md; e[i]=re;
			}
			S[i]='0';
		}
	}
	f(st,md); f(md, re);
}

vector<int> restore_permutation(int N, int w, int r) {
	n=N;
	int i, j, k;
	string S;
	for (i=1; (1<<i)<=n; i++) {
		for (j=0; j*(1<<i)<n; j++) {
			S="";
			for (k=0; k<n; k++) S.push_back('1');
			for (k=(1<<i)*j; k<(1<<i)*(j+1); k++) S[k]='0';
			for (k=(1<<i)*j; k<(1<<i)*j+(1<<(i-1)); k++) {
				S[k]='1';
				add_element(S);
				S[k]='0';
			}
		}
	}
    compile_set();
	for (i=0; i<n; i++) e[i]=n;
	f(0, n);
	vector<int> ans; ans.resize(n);
	for (i=0; i<n; i++) ans[i]=s[i];
    return ans;
}

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