oj.uz

답안 #125376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125376 2019-07-05T07:11:09 Z 구재현(#3066) Park (JOI17_park) C++14
10 / 100
 790 ms 992 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

bool ask(int s, int e, vector<int> v){
	if(s > e) swap(s, e);
	int Place[1400] = {};
	v.push_back(s); v.push_back(e);
	for(auto &i : v) Place[i] = 1;
	return Ask(s, e, Place);
}

void dfs(vector<int> v){
	if(v.size() == 1) return;
	random_shuffle(v.begin(), v.end());
	int r = v[0];
	vector<int> adj;
	int j = -1;
	for(auto &i : v){
		if(i == r) continue;
		if(ask(i, r, {})){		
			j = i;
			break;
		}
	}
	vector<int> noj = v;
	noj.erase(find(noj.begin(), noj.end(), j));
	vector<int> ls, rs;
	for(auto &i : v){
		if(i == r || i == j) continue;
		if(ask(r, i, noj) == 1) ls.push_back(i);
		else rs.push_back(i);
	}
	Answer(min(r, j), max(r, j));
	ls.push_back(r);
	rs.push_back(j);
	dfs(ls);
	dfs(rs);
}

void dfs(int r, vector<int> v, int d){
	if(v.size() == 1) return;
	vector<int> adj;
	int j = -1;
	for(auto &i : v){
		if(i == r) continue;
		if(ask(i, r, {})){
			j = i;
			break;
		}
	}
	vector<int> noj = v;
	noj.erase(find(noj.begin(), noj.end(), j));
	vector<int> ls, rs;
	for(auto &i : v){
		if(i == r || i == j) continue;
		if(ask(r, i, noj) == 1) ls.push_back(i);
		else rs.push_back(i);
	}
	Answer(min(r, j), max(r, j));
	ls.push_back(r);
	rs.push_back(j);
	if(d < 0) dfs(r, ls, d + 1);
	else dfs(ls);
	if(d < 0) dfs(j, rs, d + 1);
	else dfs(rs);
}

void Detect(int T, int N) {
	srand(69696969);
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	dfs(0, v, 0);
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 616 KB Output is correct
2 Correct 87 ms 612 KB Output is correct
3 Correct 79 ms 632 KB Output is correct
4 Correct 97 ms 632 KB Output is correct
5 Correct 108 ms 632 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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