Submission #234776

#	Time	Username	Problem	Language	Result	Execution time	Memory
234776		Nodir_Bobiev	Library (JOI18_library)	C++14	100 / 100	452 ms	504 KiB

library

#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 / 19
• Subtask 2: 81 / 81