Submission #344078

#	Time	Username	Problem	Language	Result	Execution time	Memory
344078		Kerim	Library (JOI18_library)	C++17	0 / 100	236 ms	262148 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
#define pb(x) push_back(x)
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define N 1003
using namespace std;
int val[N],n;
vector<int>adj[N],res;
void add(int x,int y){
	//printf("%d %d\n",x,y);
	adj[x].pb(y);
	adj[y].pb(x);	
}
void dfs(int nd,int pr){
	res.pb(nd);
	tr(it,adj[nd])
		if(*it!=pr)
			dfs(*it,nd);	
}
int ask(int x,int i,int effect){
	vector<int>M;
	int cur=0;
	for(int j=0;j<n;j++){
		if(j>=x and j<=i)
			cur+=val[j],M.pb(1);
		else
			M.pb(0);
	}		
	//printf("ask %d %d %d %d %d\n",x,i,effect,(Query(M)+cur<=i-x-effect),cur);
	return (Query(M)+cur<=i-x-effect);
}
void Solve(int nn){n=nn;
	if(n==1){
		res.pb(1);
		Answer(res);
		return;	
	}
	for(int i=1;i<n;i++){
		int st=0,en=i-1,a=-1,b=-1;
		while(st<en){
			int mid=(st+en+1)>>1;
			if(ask(mid,i,0))
				st=mid;
			else
				en=mid-1;
		}
		if(ask(st,i,0)){
			add(st+1,i+1);a=st;
			en=st-1;st=0;
			if(st<=en){
				//printf("%d %d %d\n",st,en,i);
				while(st+1<en){
					int mid=(st+en+1)>>1;
					if(ask(mid,i,1))
						st=mid;
					else
						en=mid-1;
				}
				if(ask(st,i,1))
					add(st+1,i+1),b=st;
			}
		}
		if(~a)val[a]++;
		if(~b)val[b]++;
	}
	for(int i=1;i<=n;i++)
		if(adj[i].size()==1){
			dfs(i,-1);
			break;
		}
	Answer(res);
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81