Submission #49352

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

messy

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

const int MX=130;

typedef vector<int> vi;

int n;

void tog(int x, char *s){
	s[x]='1'-s[x]+'0';
}

void put(char *s){
	add_element(s);
//	cout<<"PUT: "<<s<<'\n';
}

bool check(char *s){
	bool now=check_element(s);
//	cout<<"CHECK: "<<s<<": "<<now<<'\n';
	return now;
}

void init(int s, int e){
	if(s==e) return;
	char X[MX]; X[n]=0;
	int m=(s+e)/2;
	for(int i=0; i<n; i++)
		X[i]=(s<=i && i<=e) ? '0' : '1';
	for(int i=s; i<=m; i++){
		tog(i, X);
		put(X);
		tog(i, X);
	}
	init(s,m);
	init(m+1,e);
}

vi ans;

void solve(int s, int e){
	if(s==e) return;
	char X[MX]; X[n]=0;

	for(int i=0; i<n; i++)
		X[ans[i]]=(s<=i && i<=e) ? '0' : '1';

	bool infront[MX];
	for(int i=s; i<=e; i++){
		int x=ans[i];
		tog(x, X);
		infront[x]=check(X);
		tog(x, X);
	}

	int pos=s;
	for(int i=s; i<=e; i++){
		if(infront[ans[i]]){
			int t=ans[i];
			ans[i]=ans[pos];
			ans[pos]=t;
			pos++;
		}
	}

	solve(s, (s+e)/2);
	solve((s+e)/2+1, e);
}

vi restore_permutation(int nn, int w, int r) {
	n=nn;
	init(0, n-1);
    compile_set();

	for(int i=0; i<n; i++)
		ans.push_back(i);
    solve(0, n-1);

    vi ret(n);
    for(int i=0; i<n; i++)
    	ret[ans[i]]=i;

    return ret;
}

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