oj.uz

답안 #654382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654382 2022-10-31T08:27:19 Z TranGiaHuy1508 도서관 (JOI18_library) C++17
0 / 100
 43 ms 288 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++){
		// 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 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 288 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 288 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -