oj.uz

답안 #428623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428623 2021-06-15T13:16:08 Z jamezzz Park (JOI17_park) C++17
20 / 100
 92 ms 592 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define pb emplace_back
#define sz(x) (int)x.size()
mt19937 rng(time(0));

static int place[1400];
int rem[1405];

void dnc(int l,int r,vector<int> &v){
	/*
	pf("dnc: %d %d\n",l,r);
	for(int x:v)pf("%d ",x);
	pf("\n");
	//*/
	if(sz(v)==2){
		int _l=v[0],_r=v[1];
		if(_l>_r)swap(_l,_r);
		Answer(_l,_r);
		return;
	}
	int m=v[rng()%(sz(v)-2)+1];
	vector<int> nl,nr;
	nl.pb(l);
	nr.pb(m);
	memset(place,0,sizeof place);
	for(int i=0;i<sz(v);++i)place[v[i]]=1;
	for(int i=0;i<sz(v);++i){
		if(v[i]==l||v[i]==m||v[i]==r)continue;
		place[v[i]]=0;
		int _l=l,_m=m;
		if(_l>_m)swap(_l,_m);
		if(Ask(_l,_m,place)){
			nr.pb(v[i]);
			place[v[i]]=1;
		}
		else{
			nl.pb(v[i]);
			place[v[i]]=1;
		}
	}
	nl.pb(m);
	nr.pb(r);
	dnc(l,m,nl);
	dnc(m,r,nr);
}

void Detect(int T,int N){
	if(T==1){
		for(int i=0;i<N;++i)rem[i]=7;
		for(int i=0;i<N;++i){
			if(rem[i]==0)continue;
			for(int j=i+1;j<N;++j){
				if(rem[j]==0)continue;
				memset(place,0,sizeof place);
				place[i]=place[j]=1;
				if(Ask(i,j,place)){
					Answer(i,j);
					--rem[i];--rem[j];
				}
			}
		}
		return;
	}
	if(T==2){
		vector<int> v;
		for(int i=0;i<N;++i)v.pb(i);
		dnc(0,N-1,v);
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 14 ms 336 KB Output is correct
3 Correct 11 ms 336 KB Output is correct
4 Correct 15 ms 332 KB Output is correct
5 Correct 11 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 488 KB Output is correct
2 Correct 43 ms 484 KB Output is correct
3 Correct 48 ms 488 KB Output is correct
4 Correct 66 ms 472 KB Output is correct
5 Correct 92 ms 592 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -