Submission #475417

#	Time	Username	Problem	Language	Result	Execution time	Memory
475417		prvocislo	Library (JOI18_library)	C++17	100 / 100	455 ms	568 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

const int maxn = 1005;
vector<int> g[maxn], ans;
bool vis[maxn];
int n;
vector<pair<int, int> > e;
int count_edges(int l, int r)
{
	int cnt = 0;
	for (pair<int, int> i : e) cnt += (l <= i.first && i.second <= r);
	return cnt;
}
bool extra_edge(int l, int r)
{
	vector<int> ask(n, 0);
	for (int i = l; i <= r; i++)
		ask[i] = 1;
	int e = r - l + 1 - Query(ask);
	return e > count_edges(l, r);
}
void dfs(int u)
{
	ans.push_back(u+1);
	vis[u] = true;
	for (int v : g[u]) if (!vis[v])
		dfs(v);
}
void Solve(int N)
{
	n = N;
	for (int it = 0; it < n - 1; it++)
	{
		int li = 1, ri = n - 1;
		while (li < ri)
		{
			int mi = (li + ri) >> 1;
			if (extra_edge(0, mi)) ri = mi;
			else li = mi + 1;
		}
		int lj = 0, rj = ri - 1;
		while (lj < rj)
		{
			int mj = (lj + rj + 1) >> 1;
			if (extra_edge(mj, ri)) lj = mj;
			else rj = mj - 1;
		}
		e.push_back({ rj, ri });
		g[ri].push_back(rj);
		g[rj].push_back(ri);
	}
	for (int i = 0; i < n; i++) if (g[i].size() < 2)
	{
		dfs(i);
		break;
	}
	Answer(ans);
}

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