oj.uz

Submission #441333

# Submission time Handle Problem Language Result Execution time Memory
441333 2021-07-05T00:20:21 Z Agnimandur Library (JOI18_library) C++17
100 / 100
 369 ms 4580 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

# Verdict Execution time Memory Grader output
1 Correct 42 ms 532 KB # of queries: 2954
2 Correct 47 ms 456 KB # of queries: 2950
3 Correct 42 ms 536 KB # of queries: 3100
4 Correct 50 ms 456 KB # of queries: 3092
5 Correct 44 ms 548 KB # of queries: 3098
6 Correct 51 ms 532 KB # of queries: 3102
7 Correct 33 ms 576 KB # of queries: 3106
8 Correct 48 ms 536 KB # of queries: 2954
9 Correct 49 ms 456 KB # of queries: 3082
10 Correct 28 ms 456 KB # of queries: 1822
11 Correct 0 ms 328 KB # of queries: 0
12 Correct 0 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 4 ms 328 KB # of queries: 266

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 532 KB # of queries: 2954
2 Correct 47 ms 456 KB # of queries: 2950
3 Correct 42 ms 536 KB # of queries: 3100
4 Correct 50 ms 456 KB # of queries: 3092
5 Correct 44 ms 548 KB # of queries: 3098
6 Correct 51 ms 532 KB # of queries: 3102
7 Correct 33 ms 576 KB # of queries: 3106
8 Correct 48 ms 536 KB # of queries: 2954
9 Correct 49 ms 456 KB # of queries: 3082
10 Correct 28 ms 456 KB # of queries: 1822
11 Correct 0 ms 328 KB # of queries: 0
12 Correct 0 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 4 ms 328 KB # of queries: 266
17 Correct 323 ms 4580 KB # of queries: 19968
18 Correct 319 ms 4372 KB # of queries: 19720
19 Correct 364 ms 4408 KB # of queries: 19968
20 Correct 242 ms 4292 KB # of queries: 18692
21 Correct 270 ms 4108 KB # of queries: 17604
22 Correct 356 ms 4540 KB # of queries: 19974
23 Correct 365 ms 4532 KB # of queries: 19948
24 Correct 138 ms 2424 KB # of queries: 9244
25 Correct 340 ms 4432 KB # of queries: 19502
26 Correct 333 ms 4100 KB # of queries: 18270
27 Correct 151 ms 1384 KB # of queries: 9212
28 Correct 233 ms 4544 KB # of queries: 18482
29 Correct 369 ms 4520 KB # of queries: 18462
30 Correct 352 ms 4532 KB # of queries: 18482