oj.uz

답안 #406580

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

using namespace std;
vector <int> asks[1024];
int range[2048][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 58 ms 456 KB # of queries: 2954
2 Correct 62 ms 456 KB # of queries: 2950
3 Correct 61 ms 516 KB # of queries: 3100
4 Correct 48 ms 512 KB # of queries: 3092
5 Correct 60 ms 528 KB # of queries: 3098
6 Correct 57 ms 516 KB # of queries: 3102
7 Correct 57 ms 456 KB # of queries: 3106
8 Correct 31 ms 516 KB # of queries: 2954
9 Correct 71 ms 512 KB # of queries: 3082
10 Correct 33 ms 436 KB # of queries: 1822
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 2
13 Correct 1 ms 200 KB # of queries: 8
14 Correct 1 ms 200 KB # of queries: 18
15 Correct 3 ms 200 KB # of queries: 124
16 Correct 3 ms 200 KB # of queries: 266

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 456 KB # of queries: 2954
2 Correct 62 ms 456 KB # of queries: 2950
3 Correct 61 ms 516 KB # of queries: 3100
4 Correct 48 ms 512 KB # of queries: 3092
5 Correct 60 ms 528 KB # of queries: 3098
6 Correct 57 ms 516 KB # of queries: 3102
7 Correct 57 ms 456 KB # of queries: 3106
8 Correct 31 ms 516 KB # of queries: 2954
9 Correct 71 ms 512 KB # of queries: 3082
10 Correct 33 ms 436 KB # of queries: 1822
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 2
13 Correct 1 ms 200 KB # of queries: 8
14 Correct 1 ms 200 KB # of queries: 18
15 Correct 3 ms 200 KB # of queries: 124
16 Correct 3 ms 200 KB # of queries: 266
17 Runtime error 12 ms 8604 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -