#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);
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
