제출 #1282552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282552		nikaa123	Park (JOI17_park)	C++20	0 / 100	400 ms	668 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

static int visited[1405];
vector <int> leaf;
int cnt[1405];
int p[1405];
vector <vector<int>> v(1405);

int N;

bool check(int node, int pref, vector <int> v) {
	if (node > N-1 || node <= 0) return false;
	int a[N]= {0};
	for (int i = 1; i <= pref; i++) {
		a[v[i]] = 1;
	}
	for (int i = 0; i < N; i++) {
		if (visited[i]) a[i] = 1;
	}
	a[0] = 1;
	a[node] = 1;
	return Ask(0,node,a);
}

bool check1(int node, int pref, vector <int> v) {
	if (node > N-1 || node <= 0) return false;
	int a[N] = {0};
	for (int i = 0; i < N; i++) {
		if (visited[i]) a[i] = 1;
	}
	for (int i = 1; i <= v.size()-1; i++) {
		a[v[i]] = 0;
	}
	for (int i = 1; i <= pref; i++) {
		a[v[i]] = 1;
	}
	a[0] = 1;
	a[node] = 1;
	return Ask(0,node,a);
}

void Detect(int T, int n) {
	N = n;
	int root = 0;
	visited[root] = 0;
	stack <int> s;
	for (int i = 0; i < N; i++) {
		if (visited[i]) continue;
		s.push(i);
		while (!s.empty()) {
			int node = s.top();
			vector <int> nodes;
			nodes.push_back(-1);
			for (int j = 0; j < N; j++) {
				if (!visited[j]) nodes.push_back(j);
			}
			int l = 0; int r = nodes.size()-1;
			int res = -1;
			while (l <= r) {
				int mid  = (l+r)/2;
				if (check(node,mid,nodes)) {
					res = nodes[mid];
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			if (res != -1) {
				s.push(res);
				continue;
			}
			l = 0; r = leaf.size();
			while (l <= r) {
				int mid = (l+r)/2;
				if (check1(node,mid,leaf)) {
					res = leaf[mid];
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}	
			cnt[res]++;
			if (cnt[res] > 1) {
				auto it = find(leaf.begin(),leaf.end(),res);
				leaf.erase(it);
			}
			p[node] = res;
			leaf.push_back(node);
			visited[node] = 1;
			s.pop();
		}
	}

	for (int i = 0; i < N; i++) {
		if (p[i] >= N) exit(0);
		Answer(min(i,p[i]),max(i,p[i]));
		v[i].push_back(p[i]);
		v[p[i]].push_back(i);
	}
	


}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23