oj.uz

답안 #704780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704780 2023-03-03T02:23:32 Z uylulu Park (JOI17_park) C++14
0 / 100
 9 ms 596 KB 
#include "park.h"
#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 2000;
 
static int adj[1400];
bool vis[N + 1];

int n;
 
vector<pair<int,int>> res;
 
int help(int a,int b) {
	if(a > b) swap(a,b);
 
	return Ask(a,b,adj);
}
 
int ask(int a,int b) {
	adj[a] = true;
	adj[b] = true;

	int x = help(a,b);

	adj[a] = false;
	adj[b] = false;
	return x;
}

void ans(int a,int b) {
	if(a > b) swap(a,b);
	Answer(a,b);
}

void init() {
	for(int i =0;i < n;i++) {
		adj[i] = false;
	}
}

void dfs(int s,vector<int> curr) {
	if(vis[s]) return;

	init();
	vector<int> nw;
	for(auto u : curr) {
		if(u != s) {
			nw.push_back(u);
		}
	}

	// if(s == 0) {
	// 	cout<<s<<endl;
	// 	for(auto u : nw) {
	// 		cout<<u<<" ";
	// 	}
	// 	cout<<endl;
	// }
	
	vis[s] = true;

	if(nw.size() == 0) return;

	if(ask(nw[0],s)) {

		for(auto u : nw) {

			init();

			// if(s == 1) {
			// 	cout<<s<<" "<<u<<" "<<ask(u,s)<<endl;
			// 	for(int i = 0;i < n;i++) {
			// 		cout<<i<<" "<<adj[i]<<endl;
			// 	}
			// } 

			if(ask(u,s)) {
				res.push_back({u,s});
				dfs(u,nw);
			}
		}
	} else {
		vector<int> tmp = nw,after;

		while(true) {
			int l = 0,r = tmp.size(),val = -1;

			while(l < r) {
				int mid = (l + r)/2;
				init();

				for(int i = 0;i <= mid;i++) {
					adj[tmp[i]] = true;
				}
				adj[s] = true;

				if(help(tmp[0],s)) {
					r = mid;
					val = tmp[mid];
				} else {
					l = mid + 1;
				}

			}

			if(val == -1) {
				break;
			}

			res.push_back({s,val});

			dfs(val,nw);

			after.clear();

			for(auto u : tmp) {
				if(u == val) continue;
				after.push_back(u);
			}
			tmp = after;
		}
	}
}
 
void Detect(int T, int N) {
	n = N;

	vector<int> curr;

	for(int i = 0;i < n;i++) {
		curr.push_back(i);
	}
	dfs(n - 1,curr);

	for(auto u : res) {
		// cout<<u.first<<" "<<u.second<<endl;

		ans(u.first,u.second);
	}
	
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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