oj.uz

Submission #654394

# Submission time Handle Problem Language Result Execution time Memory
654394 2022-10-31T08:38:33 Z TranGiaHuy1508 Library (JOI18_library) C++17
19 / 100
 352 ms 444 KB 
#include <bits/stdc++.h>
using namespace std;

#include "library.h"

int Query(int l, int r, vector<int> include, vector<int> exclude, int N){
	vector<int> v(r - l + 1);
	for (int i = 0; i <= r - l; i++) v[i] = l+i;

	for (auto i: include) v.push_back(i);

	for (auto i: exclude){
		if (v.empty()) return 0;
		int pos = -1;
		for (int j = 0; j < (int)v.size(); j++){
			if (v[j] == i) pos = j;
		}
		if (pos >= 0) v.erase(v.begin() + pos);
	}

	vector<int> qr(N, 0);
	if (v.empty()) return 0;
	for (auto i: v) qr[i-1] = 1;

	return Query(qr);
}

void Solve(int N){
	if (N == 1){
		vector<int> ans = {1};
		Answer(ans);
		return;
	}

	vector<vector<int>> adj(N+1);
	map<pair<int, int>, int> cache;

	for (int i = 1; i <= N; i++){
		while (true){
			// cout << "i = " << i << "\n";
			int l = 1, r = N;
			while (r - l){
				int mid = (l + r) >> 1;
				// cout << l << " " << mid << " " << r << "\n";
				// query [l, mid] and [l, mid] ^ i
				int q1, q2;
				// if (!cache.count({l, mid})) cache[{l, mid}] = Query(l, mid, {}, {});
				// q1 = cache[{l, mid}];

				q1 = Query(l, mid, {}, adj[i], N);

				if (l <= i && i <= mid){
					vector<int> tmp = adj[i]; tmp.push_back(i);
					q2 = Query(l, mid, {}, tmp, N);
					if (q1 > q2) l = mid+1;
					else r = mid;
				}
				else{
					q2 = Query(l, mid, {i}, adj[i], N);
					if (q1 < q2) l = mid+1;
					else r = mid;
				}
			}
			if (Query(i, i, {l}, adj[i], N) == 1){
				// cout << i << " " << l << "\n";
				adj[i].push_back(l);
				adj[l].push_back(i);

				if (adj[i].size() > 1) break;

				int q3 = Query(1, N, {}, {i}, N);
				vector<int> tmp = adj[i]; tmp.push_back(i);
				int q4 = Query(1, N, {}, tmp, N);

				if (q3 > q4) break;
			}
			else{
				break;
			}
		}
		
	}

	int root = 0;
	for (int i = 1; i <= N; i++){
		if ((int)adj[i].size() == 1) root = i;
	}

	// cout << "root = " << root << "\n";

	vector<int> final, a(N+1, 0);
	final.push_back(root); a[root] = 1;

	int crr = root;
	while (true){
		int crr2 = 0;
		for (auto i: adj[crr]){
			if (!a[i]) crr2 = i;
		}
		if (crr2 == 0) break;
		crr = crr2;
		// cout << "add " << crr << "\n";
		a[crr] = 1;
		final.push_back(crr);
	}

	Answer(final);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 208 KB # of queries: 4320
2 Correct 48 ms 308 KB # of queries: 4206
3 Correct 65 ms 292 KB # of queries: 4464
4 Correct 49 ms 328 KB # of queries: 4361
5 Correct 57 ms 308 KB # of queries: 4414
6 Correct 60 ms 288 KB # of queries: 4385
7 Correct 46 ms 308 KB # of queries: 4379
8 Correct 45 ms 288 KB # of queries: 4209
9 Correct 54 ms 284 KB # of queries: 4432
10 Correct 32 ms 208 KB # of queries: 2747
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 5
13 Correct 1 ms 208 KB # of queries: 18
14 Correct 1 ms 208 KB # of queries: 30
15 Correct 3 ms 208 KB # of queries: 181
16 Correct 6 ms 208 KB # of queries: 378

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 208 KB # of queries: 4320
2 Correct 48 ms 308 KB # of queries: 4206
3 Correct 65 ms 292 KB # of queries: 4464
4 Correct 49 ms 328 KB # of queries: 4361
5 Correct 57 ms 308 KB # of queries: 4414
6 Correct 60 ms 288 KB # of queries: 4385
7 Correct 46 ms 308 KB # of queries: 4379
8 Correct 45 ms 288 KB # of queries: 4209
9 Correct 54 ms 284 KB # of queries: 4432
10 Correct 32 ms 208 KB # of queries: 2747
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 5
13 Correct 1 ms 208 KB # of queries: 18
14 Correct 1 ms 208 KB # of queries: 30
15 Correct 3 ms 208 KB # of queries: 181
16 Correct 6 ms 208 KB # of queries: 378
17 Runtime error 352 ms 444 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -