oj.uz

답안 #125374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125374 2019-07-05T07:10:06 Z 구재현(#3066) Park (JOI17_park) C++14
27 / 100
 690 ms 1112 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 <= 2000) dfs(r, ls, d + 1);
	else dfs(ls);
	if(d <= 2000) 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
0 / 10.0

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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 636 KB Output is correct
2 Correct 147 ms 700 KB Output is correct
3 Correct 124 ms 632 KB Output is correct
4 Correct 71 ms 768 KB Output is correct
5 Correct 96 ms 652 KB Output is correct
6 Correct 112 ms 504 KB Output is correct
7 Correct 82 ms 504 KB Output is correct
8 Correct 91 ms 632 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 632 KB Output is correct
2 Incorrect 442 ms 1112 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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