제출 #366152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366152		Rainbowbunny	도서관 (JOI18_library)	C++17	100 / 100	394 ms	704 KiB

library

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>
#include "library.h"
using namespace std;

int dsu[1005];
vector <int> Ask;
vector <int> Component[1005];

int Root(int node)
{
	return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}

bool Adj(int N, int x, int y)
{
	for(int i = 0; i < N; i++)
	{
		Ask[i] = 0;
	}
	Ask[x] = 1;
	Ask[y] = 1;
	return Query(Ask) == 1;
}

void Solve(int N)
{
	Ask.resize(N);
	for(int i = 0; i < N; i++)
	{
		dsu[i] = i;
		Component[i].push_back(i);
	}
	for(int edges = 1; edges < N; edges++)
	{
		vector <int> Remain;
		for(int j = 0; j < N; j++)
		{
			if(Root(j) == j)
			{
				Remain.push_back(j);
			}
		}
		int l = 0, r = Remain.size() - 1;
		while(l < r)
		{
			int mid = (l + r) >> 1;
			for(int i = 0; i < N; i++)
			{
				Ask[i] = 0;
			}
			for(int i = 0; i <= mid; i++)
			{
				for(auto x : Component[Remain[i]])
				{
					Ask[x] = 1;
				}
			}
			if(Query(Ask) == mid + 1)
			{
				l = mid + 1;
			}
			else
			{
				r = mid;
			}
		}
		int u = l;
		if(edges == 6)
		{
			for(int i = 0; i < N; i++)
			{
				Ask[i] = 0;
			}
			for(int i = 0; i <= 1; i++)
			{
				for(auto x : Component[Remain[i]])
				{
					Ask[x] = 1;
				}
			}
		}
		l = 0, r = u - 1;
		while(l < r)
		{
			int mid = (l + r + 1) >> 1;
			for(int i = 0; i < N; i++)
			{
				Ask[i] = 0;
			}
			for(int i = mid; i <= u; i++)
			{
				for(auto x : Component[Remain[i]])
				{
					Ask[x] = 1;
				}
			}
			if(Query(Ask) == u - mid + 1)
			{
				r = mid - 1;
			}
			else
			{
				l = mid;
			}
		}
		int v = l;
		u = Remain[u], v = Remain[v];
		if(Adj(N, Component[u][0], Component[v][0]))
		{
			reverse(Component[v].begin(), Component[v].end());
			Component[v].insert(Component[v].end(), Component[u].begin(), Component[u].end());
		}
		else if(Adj(N, Component[u][0], Component[v].back()))
		{
			Component[v].insert(Component[v].end(), Component[u].begin(), Component[u].end());
		}
		else if(Adj(N, Component[u].back(), Component[v][0]))
		{
			Component[v].insert(Component[v].begin(), Component[u].begin(), Component[u].end());
		}
		else
		{
			reverse(Component[v].begin(), Component[v].end());
			Component[v].insert(Component[v].begin(), Component[u].begin(), Component[u].end());
		}
		Component[u].clear();
		dsu[u] = v;
	}
	for(int i = 0; i < N; i++)
	{
		if(Root(i) == i)
		{
			for(auto &x : Component[i])
			{
				x++;
			}
			Answer(Component[i]);
		}
	}
}

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