답안 #654391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654391	2022-10-31T08:36:28 Z	TranGiaHuy1508	도서관 (JOI18_library)	C++17	컴파일 오류	0 ms	0 KB

library

#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){
	_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], 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]) == 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);
}

Compilation message

library.cpp: In function 'int Query(int, int, std::vector<int>, std::vector<int>, int)':
library.cpp:21:17: error: '_N' was not declared in this scope; did you mean 'N'?
   21 |  vector<int> qr(_N, 0);
      |                 ^~
      |                 N
library.cpp: In function 'void Solve(int)':
library.cpp:29:2: error: '_N' was not declared in this scope; did you mean 'N'?
   29 |  _N = N;
      |  ^~
      |  N
library.cpp:59:31: error: no matching function for call to 'Query(int&, int&, <brace-enclosed initializer list>, __gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type&)'
   59 |    if (Query(i, i, {l}, adj[i]) == 1){
      |                               ^
In file included from library.cpp:4:
library.h:2:5: note: candidate: 'int Query(const std::vector<int>&)'
    2 | int Query(const std::vector<int>& M);
      |     ^~~~~
library.h:2:5: note:   candidate expects 1 argument, 4 provided
library.cpp:6:5: note: candidate: 'int Query(int, int, std::vector<int>, std::vector<int>, int)'
    6 | int Query(int l, int r, vector<int> include, vector<int> exclude, int N){
      |     ^~~~~
library.cpp:6:5: note:   candidate expects 5 arguments, 4 provided