oj.uz

Submission #428705

# Submission time Handle Problem Language Result Execution time Memory
428705 2021-06-15T14:00:17 Z oolimry Park (JOI17_park) C++17
67 / 100
 1571 ms 33440 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){
	
	if(T == 1){
		for(int i = 0;i < n;i++){
			for(int j = i+1;j < n;j++){
				if(query(i,j,{i,j},false)) answer(i,j);
			}
		}
		return;
	}
	
	int seed = time(0);
	srand(seed);
	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;
		}
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 644 KB Output is correct
2 Correct 218 ms 612 KB Output is correct
3 Correct 226 ms 624 KB Output is correct
4 Correct 281 ms 668 KB Output is correct
5 Correct 265 ms 608 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 476 KB Output is correct
2 Correct 323 ms 596 KB Output is correct
3 Correct 334 ms 488 KB Output is correct
4 Correct 299 ms 468 KB Output is correct
5 Correct 361 ms 460 KB Output is correct
6 Correct 332 ms 480 KB Output is correct
7 Correct 316 ms 576 KB Output is correct
8 Correct 361 ms 480 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 432 KB Output is correct
2 Correct 380 ms 516 KB Output is correct
3 Correct 372 ms 496 KB Output is correct
4 Correct 382 ms 492 KB Output is correct
5 Correct 363 ms 660 KB Output is correct
6 Correct 284 ms 688 KB Output is correct
7 Correct 336 ms 628 KB Output is correct
8 Correct 364 ms 644 KB Output is correct
9 Correct 362 ms 620 KB Output is correct
10 Correct 349 ms 572 KB Output is correct
11 Correct 351 ms 588 KB Output is correct
12 Correct 361 ms 552 KB Output is correct
13 Correct 341 ms 556 KB Output is correct
14 Correct 352 ms 580 KB Output is correct
15 Correct 338 ms 544 KB Output is correct
16 Correct 337 ms 464 KB Output is correct
17 Correct 249 ms 636 KB Output is correct
18 Correct 361 ms 568 KB Output is correct
19 Correct 314 ms 580 KB Output is correct
20 Correct 362 ms 620 KB Output is correct

Subtask #5
0 / 23.0

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