제출 #1282632

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

park

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

int visited[1405];

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

	for (int i = 1; i < N; i++) {
		// if (p[i] >= N) exit(0);
		if (p[i] <0 || p[i] >= N) continue;
		Answer(min(i,p[i]),max(i,p[i]));
	}
	


}

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