제출 #1167487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167487		PlayVoltz	도서관 (JOI18_library)	C++20	100 / 100	80 ms	488 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

#define pb push_back

void Solve(int n){
	int prev=1;
	vector<vector<int> > graph(n+1);
	vector<int> vect(1, 1), temp;
	for (int i=2; i<=n; ++i){
		temp.assign(n, 0);
		for (auto a:vect)temp[a-1]=1;
		temp[i-1]=1;
		int res=Query(temp);
		if (res>prev)vect.pb(i);
		else if (res==prev){
			int low=-1, high=vect.size();
			while (low+1<high){
				int mid=(low+high)/2, c=1, f;
				temp.assign(n, 0);
				for (int j=mid; j<high; ++j)temp[vect[j]-1]=1;
				temp[i-1]=1;
				f=Query(temp);
				for (int j=mid; j<high-1; ++j){
					bool got=0;
					for (auto a:graph[vect[j]])if (a==vect[j+1])got=1;
					c+=!got;
				}
				if (c==f)low=mid;
				else high=mid;
			}
			graph[vect[low]].pb(i);
			graph[i].pb(vect[low]);
			vect.pb(i);
			vector<bool> done(n+1, 0);
			vector<int> ooga;
			for (auto a:vect)if (graph[a].empty())ooga.pb(a), done[a]=1;
			for (auto a:vect)if (graph[a].size()==1&&!done[a]){
				queue<int> q;
				q.push(a);
				while (q.size()){
					int node=q.front();
					q.pop();
					done[node]=1;
					ooga.pb(node);
					for (auto num:graph[node])if (!done[num])q.push(num);
				}
			}
			vect=ooga;
		}
		else{
			int low=-1, high=vect.size();
			while (low+1<high){
				int mid=(low+high)/2, c=1, f;
				temp.assign(n, 0);
				for (int j=mid; j<high; ++j)temp[vect[j]-1]=1;
				temp[i-1]=1;
				f=Query(temp);
				for (int j=mid; j<high-1; ++j){
					bool got=0;
					for (auto a:graph[vect[j]])if (a==vect[j+1])got=1;
					c+=!got;
				}
				if (c>=f)low=mid;
				else high=mid;
			}
			vector<bool> del(n+1, 0);
			queue<int> q;
			q.push(vect[low]);
			while (q.size()){
				int node=q.front();
				q.pop();
				del[node]=1;
				for (auto num:graph[node])if (!del[num])q.push(num);
			}
			vector<int> booga;
			for (auto a:vect)if (!del[a])booga.pb(a);
			graph[vect[low]].pb(i);
			graph[i].pb(vect[low]);
			low=-1, high=booga.size();
			while (low+1<high){
				int mid=(low+high)/2, c=1, f;
				temp.assign(n, 0);
				for (int j=mid; j<high; ++j)temp[booga[j]-1]=1;
				temp[i-1]=1;
				f=Query(temp);
				for (int j=mid; j<high-1; ++j){
					bool got=0;
					for (auto a:graph[booga[j]])if (a==booga[j+1])got=1;
					c+=!got;
				}
				if (c>=f)low=mid;
				else high=mid;
			}
			graph[booga[low]].pb(i);
			graph[i].pb(booga[low]);
			vect.pb(i);
			vector<bool> done(n+1, 0);
			vector<int> ooga;
			for (auto a:vect)if (graph[a].empty())ooga.pb(a), done[a]=1;
			for (auto a:vect)if (graph[a].size()==1&&!done[a]){
				queue<int> q;
				q.push(a);
				while (q.size()){
					int node=q.front();
					q.pop();
					done[node]=1;
					ooga.pb(node);
					for (auto num:graph[node])if (!done[num])q.push(num);
				}
			}
			vect=ooga;
		}
		prev=res;
	}
	Answer(vect);
}

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