oj.uz

답안 #406583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406583 2021-05-17T19:02:16 Z wittydolphin 도서관 (JOI18_library) C++14
100 / 100
 613 ms 4540 KB 
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include "library.h"

using namespace std;
vector <int> asks[2048];
int range[4096][2];
int M;
void make_ask(int l, int r,int index){///search adjacent within this range
	int mid=(l+r)/2;
	range[index][0]=l;
	range[index][1]=mid;
	for(int i=0;i<M;i++){
		if(i>=l&&i<=mid){
			asks[index].push_back(1);
		}else{
			asks[index].push_back(0);
		}
	}
	if(l==mid){//ifr-l=1
		range[index*2+1][0]=l;
		range[index*2+1][1]=mid;
		range[index*2+2][0]=mid+1;
		range[index*2+2][1]=r;
		return;
	}
	make_ask(l,mid,index*2+1);
	if(r==mid+1){//ifr-l=2
		range[index*2+2][0]=mid+1;
		range[index*2+2][1]=r;
		return;
	}
	make_ask(mid+1,r,index*2+2);
}
void Solve(int N){
	M=N;
	vector <int> adjacent[N];
	make_ask(0,N,0);
	// int s=0;
	// 	while(asks[s].size()>0){
	// 		for(int k=0;k<M;k++){
	// 			cout<<asks[s][k]<<' ';
	// 		}
	// 		s++;
	// 		cout<<endl;
	// 	}
	for(int i=0;i<N;i++){
		while(adjacent[i].size()<2){
			int index=0;
			while(asks[index].size()>0){//at most 10 steps so 20 queries
				int with,without;
				if(range[index][0]==i&&range[index][1]==i){index=index*2+2;continue;}
				if(adjacent[i].size()==1){
					if(range[index][0]==adjacent[i][0]&&range[index][1]==adjacent[i][0]){index=index*2+2;continue;}//without is less than with
					if(adjacent[i][0]-i==1&&range[index][1]==adjacent[i][0]&&range[index][0]==i){index=index*2+2;continue;}
					if(adjacent[i][0]-i==-1&&range[index][0]==adjacent[i][0]&&range[index][1]==i){index=index*2+2;continue;}
					asks[index][adjacent[i][0]]=0;
				}
				asks[index][i]=0;
				// for(int k=0;k<M;k++){
				// 	cout<<asks[index][k]<<' ';
				// }
				// cout<<endl<<i<<endl;
				// cout<<i<<'	'<<range[index][0]<<' '<<range[index][1]<<endl;
				without=Query(asks[index]);
				asks[index][i]=1;
				with=Query(asks[index]);
				if(range[index][0]<=i&&range[index][1]>=i){
					asks[index][i]=1;
				}else{
					asks[index][i]=0;
				}
				if(adjacent[i].size()==1&&range[index][0]<=adjacent[i][0]&&range[index][1]>=adjacent[i][0]){
					asks[index][adjacent[i][0]]=1;
				}

				if(without>=with){
					index=index*2+1;// adjacent within first half
				}else{
					index=index*2+2;
				}
			}
			if(range[index][0]==N){
				adjacent[i].push_back(N);
			}else{
				adjacent[i].push_back(range[index][0]);
				adjacent[range[index][0]].push_back(i);
			}		
		}		
	}
	int corner;
	for(corner=0;corner<N;corner++){
		if(adjacent[corner][0]==N||adjacent[corner][1]==N){break;}
	}
	vector <int> finish(N,0);
	int prev=N;
	for(int i=0;i<N;i++){
		finish[i]=corner+1;
		// cout<<adjacent[i][0]<<' '<<adjacent[i][1]<<endl;
		if(adjacent[corner][0]==prev){
			prev=corner;
			corner=adjacent[prev][1];
		}else{
			prev=corner;
			corner=adjacent[prev][0];
		}
	}
	Answer(finish);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 528 KB # of queries: 2954
2 Correct 63 ms 456 KB # of queries: 2950
3 Correct 65 ms 536 KB # of queries: 3100
4 Correct 42 ms 532 KB # of queries: 3092
5 Correct 59 ms 532 KB # of queries: 3098
6 Correct 62 ms 548 KB # of queries: 3102
7 Correct 43 ms 532 KB # of queries: 3106
8 Correct 33 ms 544 KB # of queries: 2954
9 Correct 63 ms 536 KB # of queries: 3082
10 Correct 34 ms 456 KB # of queries: 1822
11 Correct 1 ms 328 KB # of queries: 0
12 Correct 1 ms 328 KB # of queries: 2
13 Correct 1 ms 328 KB # of queries: 8
14 Correct 1 ms 328 KB # of queries: 18
15 Correct 3 ms 328 KB # of queries: 124
16 Correct 5 ms 328 KB # of queries: 266

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 528 KB # of queries: 2954
2 Correct 63 ms 456 KB # of queries: 2950
3 Correct 65 ms 536 KB # of queries: 3100
4 Correct 42 ms 532 KB # of queries: 3092
5 Correct 59 ms 532 KB # of queries: 3098
6 Correct 62 ms 548 KB # of queries: 3102
7 Correct 43 ms 532 KB # of queries: 3106
8 Correct 33 ms 544 KB # of queries: 2954
9 Correct 63 ms 536 KB # of queries: 3082
10 Correct 34 ms 456 KB # of queries: 1822
11 Correct 1 ms 328 KB # of queries: 0
12 Correct 1 ms 328 KB # of queries: 2
13 Correct 1 ms 328 KB # of queries: 8
14 Correct 1 ms 328 KB # of queries: 18
15 Correct 3 ms 328 KB # of queries: 124
16 Correct 5 ms 328 KB # of queries: 266
17 Correct 613 ms 4420 KB # of queries: 19968
18 Correct 536 ms 4368 KB # of queries: 19720
19 Correct 487 ms 4416 KB # of queries: 19968
20 Correct 447 ms 4180 KB # of queries: 18692
21 Correct 484 ms 3968 KB # of queries: 17604
22 Correct 484 ms 4540 KB # of queries: 19974
23 Correct 451 ms 4408 KB # of queries: 19948
24 Correct 211 ms 2424 KB # of queries: 9244
25 Correct 572 ms 4484 KB # of queries: 19502
26 Correct 469 ms 4224 KB # of queries: 18270
27 Correct 224 ms 1384 KB # of queries: 9212
28 Correct 512 ms 4420 KB # of queries: 18482
29 Correct 473 ms 4408 KB # of queries: 18462
30 Correct 505 ms 4528 KB # of queries: 18482