Submission #536810

#	Time	Username	Problem	Language	Result	Execution time	Memory
536810		pavement	Library (JOI18_library)	C++17	100 / 100	197 ms	472 KiB

library

#include "library.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, link[1005], sz[1005];
vector<int> M, vec, adj[1005];
vector<ii> rel;

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

void fillM(int l, int r) {
	for (int i = 0; i < N; i++) M[i] = 0;
	for (int i = l; i <= r; i++) M[i] = 1;
}

void dfs(int n, int e = -1) {
	vec.pb(n + 1);
	for (auto u : adj[n]) if (u != e) dfs(u, n);
}

int comp(int l, int r) {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (auto [a, b] : rel)
		if (l <= a && a <= r && l <= b && b <= r) unite(a, b);
	for (int i = l; i <= r; i++)
		if (i == link[i]) ret++;
	return ret;
}

void Solve(int N) {
	if (N == 1) {
		vec.pb(1);
		Answer(vec);
		return;
	}
	::N = N;
	M.resize(N);
	for (int i = 0, prv = 0; i < N; i++) {
		fillM(0, i);
		int tmp = Query(M);
		if (tmp == prv) {
			int lo = 0, hi = i - 1, ans = -1;
			while (lo <= hi) {
				int mid = (lo + hi) >> 1;
				fillM(mid, i);
				if (comp(mid, i - 1) == Query(M)) ans = mid, lo = mid + 1;
				else hi = mid - 1;
			}
			assert(ans != -1);
			rel.eb(ans, i);
		} else if (tmp == prv - 1) {
			int lo = 0, hi = i - 1, ans = -1;
			while (lo <= hi) {
				int mid = (lo + hi) >> 1;
				fillM(mid, i);
				if (comp(mid, i - 1) >= Query(M)) ans = mid, lo = mid + 1;
				else hi = mid - 1;
			}
			assert(ans != -1);
			rel.eb(ans, i);
			lo = 0, hi = i - 1, ans = -1;
			while (lo <= hi) {
				int mid = (lo + hi) >> 1;
				fillM(mid, i);
				if (comp(mid, i) != Query(M)) ans = mid, lo = mid + 1;
				else hi = mid - 1;
			}
			assert(ans != -1);
			rel.eb(ans, i);
		}
		prv = tmp;
	}
	for (auto [x, y] : rel) {
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for (int i = 0; i < N; i++)
		if (adj[i].size() == 1) {
			dfs(i);
			break;
		}
	Answer(vec);
}

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