oj.uz

Submission #200668

# Submission time Handle Problem Language Result Execution time Memory
200668 2020-02-08T01:43:20 Z CaroLinda Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 7 ms 632 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB n = 8
2 Correct 5 ms 256 KB n = 8
3 Correct 5 ms 256 KB n = 8
4 Correct 5 ms 376 KB n = 8
5 Correct 5 ms 256 KB n = 8
6 Correct 6 ms 376 KB n = 8
7 Correct 5 ms 376 KB n = 8
8 Correct 5 ms 256 KB n = 8
9 Correct 5 ms 376 KB n = 8
10 Correct 5 ms 256 KB n = 8
11 Correct 5 ms 256 KB n = 8
12 Correct 5 ms 376 KB n = 8
13 Correct 5 ms 376 KB n = 8
14 Correct 5 ms 380 KB n = 8
15 Correct 5 ms 376 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB n = 32
2 Correct 5 ms 376 KB n = 32
3 Correct 5 ms 360 KB n = 32
4 Correct 5 ms 376 KB n = 32
5 Correct 5 ms 376 KB n = 32
6 Correct 5 ms 376 KB n = 32
7 Correct 5 ms 376 KB n = 32
8 Correct 5 ms 376 KB n = 32
9 Correct 5 ms 376 KB n = 32
10 Correct 5 ms 380 KB n = 32
11 Correct 5 ms 376 KB n = 32
12 Correct 5 ms 376 KB n = 32
13 Correct 5 ms 376 KB n = 32
14 Correct 5 ms 376 KB n = 32
15 Correct 5 ms 380 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB n = 32
2 Correct 5 ms 376 KB n = 32
3 Correct 5 ms 376 KB n = 32
4 Correct 6 ms 376 KB n = 32
5 Correct 5 ms 376 KB n = 32
6 Correct 5 ms 376 KB n = 32
7 Correct 5 ms 380 KB n = 32
8 Correct 5 ms 376 KB n = 32
9 Correct 5 ms 376 KB n = 32
10 Correct 5 ms 376 KB n = 32
11 Correct 5 ms 376 KB n = 32
12 Correct 5 ms 376 KB n = 32
13 Correct 5 ms 376 KB n = 32
14 Correct 5 ms 376 KB n = 32
15 Correct 5 ms 376 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB n = 128
2 Correct 7 ms 504 KB n = 128
3 Correct 7 ms 504 KB n = 128
4 Correct 7 ms 504 KB n = 128
5 Correct 6 ms 504 KB n = 128
6 Correct 6 ms 504 KB n = 128
7 Correct 7 ms 504 KB n = 128
8 Correct 6 ms 504 KB n = 128
9 Correct 7 ms 504 KB n = 128
10 Correct 7 ms 504 KB n = 128
11 Correct 6 ms 504 KB n = 128
12 Correct 6 ms 504 KB n = 128
13 Correct 6 ms 504 KB n = 128
14 Correct 7 ms 504 KB n = 128
15 Correct 7 ms 504 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB n = 128
2 Correct 6 ms 504 KB n = 128
3 Correct 7 ms 504 KB n = 128
4 Correct 6 ms 504 KB n = 128
5 Correct 7 ms 508 KB n = 128
6 Correct 7 ms 504 KB n = 128
7 Correct 6 ms 504 KB n = 128
8 Correct 7 ms 632 KB n = 128
9 Correct 6 ms 504 KB n = 128
10 Correct 7 ms 504 KB n = 128
11 Correct 6 ms 504 KB n = 128
12 Correct 7 ms 504 KB n = 128
13 Correct 6 ms 504 KB n = 128
14 Correct 7 ms 504 KB n = 128
15 Correct 7 ms 504 KB n = 128