Submission #346643

#	Time	Username	Problem	Language	Result	Execution time	Memory
346643		jamielim	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	640 KiB

messy

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

string str;

void add(int s,int e){
	if(s+1==e){
		str[s]='1';
		add_element(str);
		str[s]='0';
		return;
	}
	int m=(s+e)/2;
	for(int i=s;i<=m;i++){
		str[i]='1';
		add_element(str);
		str[i]='0';
	}
	for(int i=s;i<=m;i++)str[i]='1';
	add(m+1,e);
	for(int i=s;i<=m;i++)str[i]='0';
	for(int i=m+1;i<=e;i++)str[i]='1';
	add(s,m);
}

vector<int> ans;

void check(int s,int e,vector<int> cur){
	if(s+1==e){
		str[cur[0]]='1';
		if(check_element(str)){
			str[cur[0]]='0';
			ans[cur[0]]=s;
			ans[cur[1]]=e;
		}else{
			str[cur[0]]='0';
			ans[cur[0]]=e;
			ans[cur[1]]=s;
		}
		return;
	}
	int m=(s+e)/2;
	vector<int> left,right;
	for(int i=0;i<(int)cur.size();i++){
		str[cur[i]]='1';
		if(check_element(str)){
			left.pb(cur[i]);
		}else{
			right.pb(cur[i]);
		}
		str[cur[i]]='0';
	}
	for(int i=0;i<(int)left.size();i++)str[left[i]]='1';
	check(m+1,e,right);
	for(int i=0;i<(int)left.size();i++)str[left[i]]='0';
	for(int i=0;i<(int)right.size();i++)str[right[i]]='1';
	check(s,m,left);
}

vector<int> restore_permutation(int n, int w, int r) {
    for(int i=0;i<n;i++)str.pb('0');
    add(0,n-1);
    compile_set();
    ans.resize(n);
    for(int i=0;i<n;i++)str[i]='0';
    vector<int> temp;
    for(int i=0;i<n;i++)temp.pb(i);
    check(0,n-1,temp);
    return ans;
}

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