oj.uz

Submission #536810

# Submission time Handle Problem Language Result Execution time Memory
536810 2022-03-14T05:09:57 Z pavement Library (JOI18_library) C++17
100 / 100
 197 ms 472 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 340 KB # of queries: 1522
2 Correct 20 ms 328 KB # of queries: 1521
3 Correct 22 ms 336 KB # of queries: 1592
4 Correct 20 ms 336 KB # of queries: 1591
5 Correct 13 ms 336 KB # of queries: 1597
6 Correct 19 ms 336 KB # of queries: 1601
7 Correct 20 ms 336 KB # of queries: 1588
8 Correct 18 ms 332 KB # of queries: 1518
9 Correct 19 ms 336 KB # of queries: 1596
10 Correct 16 ms 336 KB # of queries: 950
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 336 KB # of queries: 3
13 Correct 0 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 10
15 Correct 1 ms 208 KB # of queries: 62
16 Correct 2 ms 208 KB # of queries: 137

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 340 KB # of queries: 1522
2 Correct 20 ms 328 KB # of queries: 1521
3 Correct 22 ms 336 KB # of queries: 1592
4 Correct 20 ms 336 KB # of queries: 1591
5 Correct 13 ms 336 KB # of queries: 1597
6 Correct 19 ms 336 KB # of queries: 1601
7 Correct 20 ms 336 KB # of queries: 1588
8 Correct 18 ms 332 KB # of queries: 1518
9 Correct 19 ms 336 KB # of queries: 1596
10 Correct 16 ms 336 KB # of queries: 950
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 336 KB # of queries: 3
13 Correct 0 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 10
15 Correct 1 ms 208 KB # of queries: 62
16 Correct 2 ms 208 KB # of queries: 137
17 Correct 197 ms 444 KB # of queries: 10297
18 Correct 185 ms 456 KB # of queries: 10167
19 Correct 190 ms 332 KB # of queries: 10255
20 Correct 167 ms 340 KB # of queries: 9627
21 Correct 154 ms 460 KB # of queries: 9031
22 Correct 193 ms 332 KB # of queries: 10293
23 Correct 191 ms 328 KB # of queries: 10280
24 Correct 60 ms 460 KB # of queries: 4795
25 Correct 185 ms 336 KB # of queries: 10060
26 Correct 171 ms 340 KB # of queries: 9397
27 Correct 50 ms 336 KB # of queries: 4782
28 Correct 160 ms 336 KB # of queries: 9977
29 Correct 147 ms 336 KB # of queries: 9966
30 Correct 159 ms 472 KB # of queries: 9977