oj.uz

Submission #125356

# Submission time Handle Problem Language Result Execution time Memory
125356 2019-07-05T06:47:40 Z 임유진(#3061) Park (JOI17_park) C++14
57 / 100
 337 ms 652 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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 504 KB Output is correct
2 Correct 310 ms 376 KB Output is correct
3 Correct 337 ms 376 KB Output is correct
4 Correct 291 ms 504 KB Output is correct
5 Correct 323 ms 480 KB Output is correct
6 Correct 295 ms 488 KB Output is correct
7 Correct 297 ms 504 KB Output is correct
8 Correct 304 ms 504 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 376 KB Output is correct
2 Correct 305 ms 632 KB Output is correct
3 Correct 302 ms 488 KB Output is correct
4 Correct 273 ms 604 KB Output is correct
5 Correct 278 ms 504 KB Output is correct
6 Correct 232 ms 632 KB Output is correct
7 Correct 241 ms 652 KB Output is correct
8 Correct 285 ms 504 KB Output is correct
9 Correct 280 ms 504 KB Output is correct
10 Correct 260 ms 500 KB Output is correct
11 Correct 265 ms 632 KB Output is correct
12 Correct 294 ms 508 KB Output is correct
13 Correct 244 ms 504 KB Output is correct
14 Correct 268 ms 504 KB Output is correct
15 Correct 258 ms 604 KB Output is correct
16 Correct 309 ms 504 KB Output is correct
17 Correct 207 ms 504 KB Output is correct
18 Correct 264 ms 376 KB Output is correct
19 Correct 241 ms 504 KB Output is correct
20 Correct 310 ms 504 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 372 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -