oj.uz

Submission #520963

# Submission time Handle Problem Language Result Execution time Memory
520963 2022-01-31T14:48:07 Z koioi.org-koosaga Park (JOI17_park) C++17
67 / 100
 333 ms 836 KB 
#include "park.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 1500;

static int Place[1400];

vector<int> gph[MAXN];
vector<int> ord;

void dfs(int x){
	ord.push_back(x);
	for(auto &y : gph[x]) dfs(y);
}

void Detect(int T, int N) {
	vector<int> v = {};
	for(int i = 1; i < N; i++){
		auto init = [&](){
			memset(Place, 0, sizeof(Place));
			for(int i = 0; i < N; i++) Place[i] = 1;
		};
		int s = 0, e = sz(v);
		while(s != e){
			int m = (s + e) / 2;
			init();
			for(int i = m; i < sz(v); i++) Place[v[i]] = 0;
			if(Ask(0, i, Place) == 1) e = m;
			else s = m + 1;
		}
		v.insert(v.begin() + s, i);
	}
	for(int i = 0; i < sz(v); i++){
		auto init = [&](){
			memset(Place, 0, sizeof(Place));
			for(int i = 0; i < N; i++) Place[i] = 1;
		};
		ord.clear();
		dfs(0);
		int s = 0, e = sz(ord) - 1;
		while(s != e){
			int m = (s + e) / 2;
			init();
			for(int i = m + 1; i < sz(ord); i++) Place[ord[i]] = 0;
			if(Ask(0, v[i], Place) == 1) e = m;
			else s = m + 1;
		}
		gph[ord[s]].push_back(v[i]);
	}
	for(int i = 0; i < N; i++){
		for(auto &j : gph[i]) Answer(min(i, j), max(i, j));
		gph[i].clear();
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 616 KB Output is correct
2 Correct 137 ms 452 KB Output is correct
3 Correct 147 ms 468 KB Output is correct
4 Correct 302 ms 672 KB Output is correct
5 Correct 300 ms 488 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 424 KB Output is correct
2 Correct 283 ms 424 KB Output is correct
3 Correct 273 ms 452 KB Output is correct
4 Correct 301 ms 436 KB Output is correct
5 Correct 273 ms 444 KB Output is correct
6 Correct 270 ms 548 KB Output is correct
7 Correct 265 ms 440 KB Output is correct
8 Correct 281 ms 452 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 392 KB Output is correct
2 Correct 266 ms 420 KB Output is correct
3 Correct 285 ms 408 KB Output is correct
4 Correct 300 ms 468 KB Output is correct
5 Correct 273 ms 412 KB Output is correct
6 Correct 317 ms 556 KB Output is correct
7 Correct 272 ms 444 KB Output is correct
8 Correct 289 ms 716 KB Output is correct
9 Correct 271 ms 440 KB Output is correct
10 Correct 286 ms 452 KB Output is correct
11 Correct 307 ms 456 KB Output is correct
12 Correct 274 ms 452 KB Output is correct
13 Correct 305 ms 564 KB Output is correct
14 Correct 298 ms 452 KB Output is correct
15 Correct 310 ms 436 KB Output is correct
16 Correct 286 ms 428 KB Output is correct
17 Correct 302 ms 720 KB Output is correct
18 Correct 305 ms 460 KB Output is correct
19 Correct 308 ms 836 KB Output is correct
20 Correct 280 ms 460 KB Output is correct

Subtask #5
0 / 23.0

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