Submission #200668

#	Time	Username	Problem	Language	Result	Execution time	Memory
200668		CaroLinda	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	7 ms	632 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>

const int MAXN = 130 ;

using namespace std ;

int N , W , R ;
int resp[MAXN] ;

inline void aux( string &str) { for(int i = 0 ; i < N ; i++ ) str.push_back('0') ; }

inline void call_add(int l, int r)
{


	string str ;

	aux(str); 
	for(int i = 0 ; i < l ; i++ ) str[i] = '1' ;
	for(int i = r+1 ; i < N ; i++ ) str[i] = '1' ;

	if( r - l == 1 )
	{
		str[l] = '1' ;
		add_element(str) ;
	}

	else{
		for(int i = l ; i <= (l+r)>>1 ; i++ )
		{
			str[i] = '1' ;
			add_element(str) ;
			str[i] = '0' ;
		}
	}

}

inline void calc(int l, int r, vector<int> my_set )
{

	string str ;
	aux(str) ;
	for(int i = 0 ; i < N ; i++ ) str[i] = '1' ;
	for(int i : my_set ) str[i] = '0' ;

	if( r - l == 1 )
	{
		str[ my_set[0] ] = '1' ;
		if( !check_element(str) ) swap(my_set[0] , my_set[1]) ;
		resp[l] = my_set[0] ;
		resp[r] = my_set[1] ;
		return ;
	}

	vector<int> new_set , old_set ;

	for(int i : my_set )
	{
		str[i]= '1' ;
		if( check_element(str) ) new_set.push_back(i) ;
		else old_set.push_back(i) ;
		str[i] = '0' ;
	}

	int mid = (l+r)/2 ;

	calc(l,mid , new_set ) ;
	calc( mid+1 , r , old_set ) ;

}

vector<int> restore_permutation(int n , int w, int _r) {

	N = n ; W = w ; R = _r ;
    
	queue< pair<int,int> > fila ;
	fila.push(make_pair(0,N-1) ) ;

	while(!fila.empty() )
	{

		int l = fila.front().first ;
		int r = fila.front().second ;
		int mid = (l+r)>>1 ;

		fila.pop() ;

		call_add(l,r) ;

		if( r - l <= 1 ) continue ;

		fila.push( make_pair( mid + 1 , r ) ) ;
		fila.push( make_pair( l , mid ) ) ;

	}

	compile_set() ;

	vector<int> v ;
	for(int i = 0 ; i < N ; i++ ) v.push_back(i) ;

	calc(0,N-1, v) ;

	for(int i = 0 ; i < N ; i++ ) v[i] = resp[i] ;
	for(int i = 0 ; i < N ; i++ ) resp[ v[i] ] = i ;
	for(int i = 0 ; i < N ; i++ ) v[i] = resp[i] ;

	return v ;

}

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