oj.uz

Submission #654389

# Submission time Handle Problem Language Result Execution time Memory
654389 2022-10-31T08:32:52 Z TranGiaHuy1508 Library (JOI18_library) C++17
0 / 100
 503 ms 372 KB 
#include <bits/stdc++.h>
using namespace std;

#include "library.h"

int _N;

int Query(int l, int r, vector<int> include, vector<int> exclude){
	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){
	_N = N;
	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]);

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

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

				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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 503 ms 372 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 503 ms 372 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -