oj.uz

Submission #428542

# Submission time Handle Problem Language Result Execution time Memory
428542 2021-06-15T12:43:53 Z oolimry Park (JOI17_park) C++17
67 / 100
 1512 ms 33520 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

vector<int> done;
static int place[1400];
static int indone[1400];
int n;
int query(int S, int E, vector<int> stuff, bool assumedone=true){
	if(S > E) swap(S,E);
	for(int i = 0;i < n;i++) place[i] = 0;
	
	for(int x : stuff) place[x] = 1;
	if(assumedone) for(int x : done) place[x] = 1;
	
	place[S] = 1, place[E] = 1;
	//show2(S,E);
	//for(int i = 0;i < n;i++) cerr << place[i]; cerr << endl;
	return Ask(S, E, place);
}

void findmiddle(int S, int E, vector<int> &v){
	vector<int> possible;
	for(int i = 0;i < n;i++){
		if(i == S or i == E or indone[i]) continue;
		possible.push_back(i);
	}
	random_shuffle(all(possible));
	//for(int x : possible) cerr << x <<  " "; cerr << endl;
	
	if(query(S, E, {})){
		v.push_back(E);
		return;
	}
	
	int low = 0, high = sz(possible)-1;
	
	while(low < high){
		int mid = (low+high)/2;
		vector<int> toask;
		for(int i = 0;i < sz(possible);i++){
			if(low <= i and i <= mid) continue;
			toask.push_back(possible[i]);
		}
		if(query(S, E, toask)) low = mid+1;
		else high = mid;
		//for(int x : toask) cerr << x << " "; cerr << endl;
	}
	
	//show3(S, E, possible[low]);
	findmiddle(S, possible[low], v);
	findmiddle(possible[low],E,v);
}

void answer(int A, int B){
	if(A > B) swap(A,B);
	//show2(A,B);
	Answer(A,B);
}

void Detect(int T, int _n){
	int seed = time(0);
	srand(1623760428);
	//show(seed);
	n = _n;
	vector<int> possible;
	for(int i = 1;i < n;i++) possible.push_back(i);
	done.push_back(0);
	indone[0] = 1;
	while(true){
		vector<int> undone;
		for(int i = 0;i < n;i++) if(not indone[i]) undone.push_back(i);
		if(sz(undone) == 0) break;
		
		vector<int> erm;
		findmiddle(0, undone[rand()%sz(undone)], erm);
		//for(int x : erm) cerr << x << " "; cerr << endl;
		
		int low = -1, high = sz(done)-1;
		int u = erm[0];
		while(low != high-1){
			int mid = (low+high)/2;
			vector<int> stuff;
			for(int i = 0;i <= mid;i++) stuff.push_back(done[i]);
			
			if(query(0, u, stuff, false)) high = mid;
			else low = mid;
		} 
		
		//show2(u, done[high]);
		answer(u, done[high]);
		for(int i = 1;i < sz(erm);i++) answer(erm[i-1], erm[i]);
				
		///push back into order
		for(int x : erm){
			done.push_back(x);
			indone[x] = 1;
		}
	}
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:70:6: warning: unused variable 'seed' [-Wunused-variable]
   70 |  int seed = time(0);
      |      ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 620 KB Output is correct
2 Correct 226 ms 588 KB Output is correct
3 Correct 220 ms 756 KB Output is correct
4 Correct 282 ms 636 KB Output is correct
5 Correct 260 ms 652 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 460 KB Output is correct
2 Correct 318 ms 472 KB Output is correct
3 Correct 341 ms 368 KB Output is correct
4 Correct 298 ms 460 KB Output is correct
5 Correct 336 ms 580 KB Output is correct
6 Correct 322 ms 464 KB Output is correct
7 Correct 312 ms 576 KB Output is correct
8 Correct 321 ms 460 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 432 KB Output is correct
2 Correct 358 ms 460 KB Output is correct
3 Correct 364 ms 532 KB Output is correct
4 Correct 362 ms 520 KB Output is correct
5 Correct 364 ms 684 KB Output is correct
6 Correct 289 ms 620 KB Output is correct
7 Correct 321 ms 668 KB Output is correct
8 Correct 355 ms 532 KB Output is correct
9 Correct 351 ms 560 KB Output is correct
10 Correct 342 ms 620 KB Output is correct
11 Correct 343 ms 608 KB Output is correct
12 Correct 334 ms 592 KB Output is correct
13 Correct 319 ms 556 KB Output is correct
14 Correct 355 ms 696 KB Output is correct
15 Correct 325 ms 556 KB Output is correct
16 Correct 321 ms 588 KB Output is correct
17 Correct 271 ms 692 KB Output is correct
18 Correct 363 ms 648 KB Output is correct
19 Correct 306 ms 580 KB Output is correct
20 Correct 361 ms 640 KB Output is correct

Subtask #5
0 / 23.0

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