제출 #428705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428705		oolimry	Park (JOI17_park)	C++17	67 / 100	1571 ms	33440 KiB

park

#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
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23