Submission #406580

#	Time	Username	Problem	Language	Result	Execution time	Memory
406580		wittydolphin	Library (JOI18_library)	C++14	19 / 100	71 ms	8604 KiB

library

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