oj.uz

답안 #234776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234776 2020-05-25T14:09:41 Z Nodir_Bobiev 도서관 (JOI18_library) C++14
100 / 100
 452 ms 504 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

vector < int > firstGroup, secondGroup, thirdGroup, zeroes;
vector < int > leftNeighbor, rightNeighbor, whichGroup;

void Do(int l, int r, vector<int>&vc, int val = 1){
	while( l <= r ) zeroes[vc[l++]] = val;
}
vector < int > FindNeighbors( int l, int r, int x, vector < int> & vc ){
	if( l > r ) return {};
	if( l == r ) return {vc[l]};
	vector < int > res;
	int m = (l+r)>>1;
	Do(l, m, vc, 1); zeroes[x] = 1;
	if( Query(zeroes) <= m-l+1 ){
		Do(l, m, vc, 0); zeroes[x] = 0;
		vector < int > vv = FindNeighbors(l, m, x, vc);
		for( auto c: vv ) res.push_back( c );
	}else{
		Do(l, m, vc, 0); zeroes[x] = 0;
	}
	Do(m+1, r, vc, 1); zeroes[x] = 1;
	if( Query(zeroes) <= r-m ){
		Do(m+1, r, vc, 0); zeroes[x] = 0;
		vector < int > vv = FindNeighbors(m+1, r, x, vc);
		for( auto c: vv ) res.push_back( c );
	}else{
		Do(m+1, r, vc, 0); zeroes[x] = 0;
	}
	return res;
}
vector < int > RestoreBookshelf(int x){
	vector < int > res;
	if( leftNeighbor[x] != -1 ){
		if( leftNeighbor[leftNeighbor[x]] == x )leftNeighbor[leftNeighbor[x]] = -1;
		if( rightNeighbor[leftNeighbor[x]] == x ) rightNeighbor[leftNeighbor[x]] = -1;
		res = RestoreBookshelf(leftNeighbor[x]);
	}
	else if( rightNeighbor[x] != -1 ){
		if( leftNeighbor[rightNeighbor[x]] == x )leftNeighbor[rightNeighbor[x]] = -1;
		if( rightNeighbor[rightNeighbor[x]] == x ) rightNeighbor[rightNeighbor[x]] = -1;
		res = RestoreBookshelf(rightNeighbor[x]);
	}
	res.push_back(x+1);
	return res;
}
void Solve(int N)
{	
	for( int i = 0; i < N; i ++ ){ 
		zeroes.push_back( 0 );
		whichGroup.push_back(0);
		leftNeighbor.push_back(-1);
		rightNeighbor.push_back(-1);
	}
	vector < int > firstQueryVector(N, 0), secondQueryVector(N,0), thirQueryVector(N,0);
	for( int i = 0; i < N; i ++ ){
		firstQueryVector[i] = 1;
		size_t size = Query(firstQueryVector);
		if( size == firstGroup.size()+1 ){
			firstGroup.push_back( i );
			whichGroup[i] = 1;
		}else{
			firstQueryVector[i] = 0;
			secondQueryVector[i] = 1;
			size = Query(secondQueryVector);
			if( size == secondGroup.size()+1 ){
				secondGroup.push_back(i);
				whichGroup[i] = 2;
			}else{
				secondQueryVector[i] = 0;
				thirQueryVector[i] = 1;
				thirdGroup.push_back(i);
				whichGroup[i] = 3;
			}
		}
	}
	for( auto x: firstGroup ){
		vector < int > neighbors = FindNeighbors(0, secondGroup.size()-1, x, secondGroup);
		//printf("f to s %d ", x);
		for( auto neigh: neighbors){
			//printf("%d ", neigh);
			if( leftNeighbor[x] == -1 )
				leftNeighbor[x] = neigh;
			else rightNeighbor[x] = neigh;

			if( leftNeighbor[neigh] == -1 )
				leftNeighbor[neigh] = x;
			else rightNeighbor[neigh] = x;
		}
		//printf("\n");
	}
	for( auto x: firstGroup ){
		vector < int > neighbors = FindNeighbors(0, thirdGroup.size()-1, x, thirdGroup);
		//printf("f to th %d ", x);
		for( auto neigh: neighbors){
			//printf("%d ", neigh);
			if( leftNeighbor[x] == -1 )
				leftNeighbor[x] = neigh;
			else rightNeighbor[x] = neigh;

			if( leftNeighbor[neigh] == -1 )
				leftNeighbor[neigh] = x;
			else rightNeighbor[neigh] = x;
		}
		//printf("\n");
	}
	for( auto x: secondGroup ){
		vector < int > neighbors = FindNeighbors(0, thirdGroup.size()-1, x, thirdGroup);
		//printf("s to th %d ", x);
		for( auto neigh:neighbors){
			//printf("%d ", neigh);
			if( leftNeighbor[x] == -1 )
				leftNeighbor[x] = neigh;
			else rightNeighbor[x] = neigh;

			if( leftNeighbor[neigh] == -1 )
				leftNeighbor[neigh] = x;
			else rightNeighbor[neigh] = x;
		}
		//printf("\n");
	}
	vector < int > bookshelf;
	for( int i = 0; i < N; i ++ ){
		if( leftNeighbor[i] == -1 || rightNeighbor[i] == -1 ){
			bookshelf = RestoreBookshelf(i);
			break;
		}
	}
	/*
	for( int i = 0; i < N; i ++ ){
		printf("%d %d %d\n", i, leftNeighbor[i], rightNeighbor[i]	 );
	}
	for( auto c: firstGroup ){
		printf("%d ", c);	
	}printf("\n");
	for( auto c: secondGroup ){
		printf("%d ", c);
	}printf("\n");
	for( auto c: bookshelf){
		printf("%d ", c);
	}
	printf("\n");
	*/
	Answer(bookshelf);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 376 KB # of queries: 2641
2 Correct 44 ms 376 KB # of queries: 2644
3 Correct 45 ms 372 KB # of queries: 2716
4 Correct 44 ms 376 KB # of queries: 2676
5 Correct 47 ms 384 KB # of queries: 2748
6 Correct 50 ms 376 KB # of queries: 2729
7 Correct 41 ms 384 KB # of queries: 2748
8 Correct 42 ms 376 KB # of queries: 2572
9 Correct 44 ms 384 KB # of queries: 2752
10 Correct 27 ms 384 KB # of queries: 1585
11 Correct 5 ms 384 KB # of queries: 1
12 Correct 5 ms 384 KB # of queries: 3
13 Correct 5 ms 256 KB # of queries: 7
14 Correct 5 ms 384 KB # of queries: 10
15 Correct 6 ms 384 KB # of queries: 95
16 Correct 7 ms 256 KB # of queries: 220

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 376 KB # of queries: 2641
2 Correct 44 ms 376 KB # of queries: 2644
3 Correct 45 ms 372 KB # of queries: 2716
4 Correct 44 ms 376 KB # of queries: 2676
5 Correct 47 ms 384 KB # of queries: 2748
6 Correct 50 ms 376 KB # of queries: 2729
7 Correct 41 ms 384 KB # of queries: 2748
8 Correct 42 ms 376 KB # of queries: 2572
9 Correct 44 ms 384 KB # of queries: 2752
10 Correct 27 ms 384 KB # of queries: 1585
11 Correct 5 ms 384 KB # of queries: 1
12 Correct 5 ms 384 KB # of queries: 3
13 Correct 5 ms 256 KB # of queries: 7
14 Correct 5 ms 384 KB # of queries: 10
15 Correct 6 ms 384 KB # of queries: 95
16 Correct 7 ms 256 KB # of queries: 220
17 Correct 425 ms 504 KB # of queries: 18168
18 Correct 420 ms 440 KB # of queries: 17895
19 Correct 452 ms 504 KB # of queries: 18119
20 Correct 409 ms 384 KB # of queries: 16909
21 Correct 391 ms 504 KB # of queries: 15953
22 Correct 448 ms 504 KB # of queries: 18244
23 Correct 437 ms 504 KB # of queries: 18060
24 Correct 166 ms 384 KB # of queries: 8411
25 Correct 415 ms 504 KB # of queries: 17748
26 Correct 399 ms 400 KB # of queries: 16536
27 Correct 157 ms 504 KB # of queries: 8247
28 Correct 282 ms 384 KB # of queries: 11458
29 Correct 281 ms 504 KB # of queries: 11450
30 Correct 274 ms 384 KB # of queries: 11458