Submission #1349367

#TimeUsernameProblemLanguageResultExecution timeMemory
1349367jump도서관 (JOI18_library)C++20
0 / 100
1 ms344 KiB
#include <cstdio>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int globaln;
vector<int> adj[1010];
vector<int> split(const vector<int>& ori,int l,int r,int idx){
	vector<int> res=ori;
	for(int i=0;i<l;i++)res[i]=0;
	for(int i=r+1;i<globaln;i++)res[i]=0;
	res[idx]=1;
	return res;
}
int dnc(int idx,int l,int r,const vector<int>& process){
	int mid = (l+r)/2;
	vector<int> test = split(process,l,mid,idx);
	int sum1 = 0;int v1v=-1;
	for(int i=l;i<=mid;i++){
		if(test[i]==1)sum1+=1;
		if(test[i]==1&&i!=idx)v1v=i;
	}
	if(idx>mid||idx<l)sum1+=1;
	vector<int> test2 = split(process,mid+1,r,idx);
	int sum2 = 0;int v2v=-1;
	for(int i=mid+1;i<=r;i++){
		if(test2[i]==1)sum2+=1;
		if(test2[i]==1&&i!=idx)v2v=i;
	}
	if(idx>r||idx<mid+1)sum2+=1;
	if(sum1>1&&Query(test)<sum1){
		if(sum1>2)
		dnc(idx,l,mid,process);
		else{
			adj[idx].push_back(v1v);
			adj[v1v].push_back(idx);
		}
	}
	if(sum2>1&&Query(test2)<sum2){
		if(sum2>2)
		dnc(idx,mid+1,r,process);
		else{
			adj[idx].push_back(v2v);
			adj[v2v].push_back(idx);
		}
	}
	return 0;
}
int findEdge(int curr,int parr){
	int t=0;
	for(auto to:adj[curr]){
		if(to==parr)continue;
		t+=1;
		return findEdge(to,curr);
	}
	if(t==0)return curr;
	return curr;
}
void dfs(int curr,int parr,vector<int> ans){
	ans.push_back(curr);
	for(auto to:adj[curr]){
		dfs(to,curr,ans);
	}
}
void Solve(int N)
{
	globaln=N;
	vector<int> sub;
	vector<int> qV(N,0);
	vector<int> find;
	qV[0]=1;
	int last = 1;
	for(int i=0;i<N-1;i++){
		qV[i]=1;
		int res = Query(qV);
		if(res==last){
			qV[i]=0;
			find.push_back(i);
		}
		else{
			sub.push_back(i);
		}
	}
	for(auto idx:find){
		dnc(idx,0,N-1,qV);
	}
	std::vector<int> ans;
	dfs(findEdge(1,1),-1,ans);
	std::cout << ans.size() << ' ';
	for(auto i:ans){
		std::cout << i << ' ';
	}
	Answer(ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...