Submission #1306998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306998		Double_Slash	Library (JOI18_library)	C++20	100 / 100	89 ms	468 KiB

library

#include "library.h"
#include <bits/stdc++.h>

using namespace std;
using pint = pair<int, int>;
#define all(x) x.begin(), x.end()

vector<pint> e;
vector<int> seen, adj[1000], ans;

void dfs(int i, int p = -1) {
	ans.emplace_back(i + 1);
	for (int j: adj[i]) {
		if (j != p) dfs(j, i);
	}
}

void dnc(int l, int r) {
	if (l == r) return;
	int m = (l + r) >> 1;
	dnc(l, m), dnc(m + 1, r);
	auto qu = [&] (int i, int l, int r) {
		fill(all(seen), 0);
		seen[i] = 1;
		for (int i = l; i <= r; ++i) seen[i] = 1;
		int q = r - l + 2 - Query(seen);
		for (auto &[a, b]: e) q -= seen[a] and seen[b];
		return q;
	};
	for (int i = m; ++i <= r;) {
		for (int li = l;;) {
			if (not qu(i, li, m)) break;
			int mi = m;
			for (int k = 10; k--;) {
				if (mi - (1 << k) < li) continue;
				qu(i, li, mi - (1 << k)) and (mi -= 1 << k);
			}
			e.emplace_back(i, mi);
			adj[i].emplace_back(mi);
			adj[mi].emplace_back(i);
			li = mi + 1;
		}
	}
}

void Solve(int N) {
	seen.resize(N);
	dnc(0, N - 1);
	for (int i = N; i--;) {
		if (adj[i].size() >= 2) continue;
		dfs(i);
		Answer(ans);
		break;
	}
}

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