oj.uz

답안 #125355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125355 2019-07-05T06:46:23 Z 임유진(#3061) Park (JOI17_park) C++14
0 / 100
 422 ms 592 KB 
#include "park.h"
#include<algorithm>
#include<vector>

using namespace std;

static int zero[1400], one[1400];
static int N;
static bool chk[1400];
static int dep[1400];

void answer(int a, int b) {
	Answer(min(a, b), max(a, b));
}

int ask(int a, int b, int place[]) {
	return Ask(min(a, b), max(a, b), place);
}

int f(int x, int y) {
	//printf("f(x = %d, y = %d)\n", x, y);
	zero[x] = zero[y] = 1;
	int t = ask(x, y, zero);
	zero[x] = zero[y] = 0;
	if(t == 1) return -1;

	vector<int> v;
	for(int i = 1; i < N; i++) if(i != x && i != y) v.push_back(i);
	sort(v.begin(), v.end(), [&](const int a, const int b) { return dep[a] < dep[b]; } );

	int s = 0, e = v.size() - 1;
	while(s < e) {
		int m = (s + e) / 2;
		//printf("cnt = %d, s = %d, e = %d, m = %d\n", cnt, s, e, m);
		for(int i = s; i <= m; i++) one[v[i]] = 0;
		t = ask(x, y, one);
		for(int i = s; i <= m; i++) one[v[i]] = 1;
		if(t == 0) e = m;
		else s = m + 1;
	}
	return v[s];
}

void solve(int x, int y) {
	//printf("solve(x = %d, y = %d)\n", x, y);
	if(chk[y]) return;
	int z = f(x, y);
	//printf("z = %d\n", z);
	if(z == -1) {
		answer(x, y);
		chk[y] = true;
		dep[y] = dep[x] + 1;
	}
	else {
		solve(x, z);
		solve(z, y);
	}
}

void Detect(int T, int N) {
	if(T != 3 && T != 4) return;
	::N = N;
	for(int i = 0; i < N; i++) one[i] = 1;
	for(int i = 1; i < N; i++) dep[i] = N;
	for(int i = 1; i < N; i++) solve(0, i);
}

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 3 ms 592 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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