Submission #1164143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164143		WH8	Library (JOI18_library)	C++20	100 / 100	127 ms	472 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n;
vector<int> ans;
vector<vector<int>> al(1005);

void dfs(int x, int p){
	ans.push_back(x+1);
	for(auto it:al[x]){
		if(it==p)continue;
		dfs(it,x);
	}
}

int qry(int l, int r){
	vector<int> m(n,0);
	for(int i=l; i<=r;i++){
		m[i]=1;
	}
	return Query(m);
}

void Solve(int N)
{
	n=N;
	int res[n]; res[0]=1;
	for(int i=1;i<N;i++){
		res[i]=qry(0, i);
		//~ printf("iteration i = %d\n", i);
		if(res[i]==res[i-1]-1){
			int hi=i-1, lo=0, m, ans=-1;
			while(hi>=lo){
				m=(hi+lo)/2;
				if(qry(m, i-1)>=qry(m,i)){
					ans=m;
					lo=m+1;
				}
				else hi=m-1;
			}
			assert(ans!=-1);
			//~ printf("ans1=%d\n",ans);
			al[ans].pb(i);
			al[i].pb(ans);
			
			hi=i-1, lo=0, ans=-1;
			while(hi>=lo){
				m=(hi+lo)/2;
				if(qry(m, i-1)>=qry(m,i)+1){
					ans=m;
					lo=m+1;
				}
				else hi=m-1;
			}
			assert(ans!=-1);
			//~ printf("ans2=%d\n",ans);
			//~ printf("pushing back ans2=%d to i=%d\n",ans,i);
			al[ans].pb(i);
			al[i].pb(ans);
		}
		else if(res[i]==res[i-1]){
			int hi=i-1, lo=0, m, ans=-1;
			while(hi>=lo){
				m=(hi+lo)/2;
				if(qry(m, i-1)>=qry(m,i)){
					ans=m;
					lo=m+1;
				}
				else hi=m-1;
			}
			assert(ans!=-1);
			al[ans].pb(i);
			al[i].pb(ans);
		}
	}
	int st=0;
	for(int i=0;i<n;i++) if(al[i].size()==1)st=i;
	dfs(st,-1);
	//~ for(int i=0;i<n;i++){
		//~ for(auto it:al[i])cout<<it<< " ";
		//~ cout<<endl;
	//~ }
	//~ for(auto it:ans){
		//~ cout<<it<<" ";
	//~ }
	cout<<endl;
	Answer(ans);
}

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