oj.uz

답안 #29078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29078 2017-07-18T08:05:30 Z 서규호(#1171) Park (JOI17_park) C++14
47 / 100
 299 ms 2252 KB 
#include "park.h"
#include <bits/stdc++.h>
#include <unistd.h>

#define pb push_back

using namespace std;

static int N;
static int place[1400];

static void divide(int s,int e,vector<int> tmp){
	if(tmp.size() == 0){
		Answer(min(s,e),max(s,e));
		return;
	}else if(tmp.size() == 1){
		Answer(min(s,tmp[0]),max(s,tmp[0]));
		Answer(min(tmp[0],e),max(tmp[0],e));
		return;
	}

	int value;
	vector<int> tmp1,tmp2;
	value = rand()%tmp.size(); value = tmp[value];
	for(int i=0; i<tmp.size(); i++){
		if(tmp[i] == value) continue;
		for(int j=0; j<N; j++) place[j] = 1;
		place[tmp[i]] = 0;
		if(Ask(min(s,value),max(s,value),place)){
			tmp2.pb(tmp[i]);
		}else tmp1.pb(tmp[i]);
	}
	divide(s,value,tmp1);
	divide(value,e,tmp2);
}

static void dfs(int x,vector<int> tmp){
	if(tmp.size() == 0) return;
	vector<int> child;
	for(auto &i : tmp){
		for(int j=0; j<N; j++) place[j] = 0;
		place[x] = place[i] = 1;
		if(Ask(min(x,i),max(x,i),place)){
			child.pb(i);
		}
	}
	if(child.size() > (6 + (x == 0))) while(true);
	if(child.size() == 0) while(true);
	vector<int> t[7];
	for(auto &i : tmp){
		bool flag = false;
		for(auto &j : child) if(i == j) flag = true;
		if(flag) continue;
		int s,e;
		s = 0; e = child.size()-1;
		while(s != e){
			int m = (s+e)/2;
			for(int j=0; j<N; j++) place[j] = 1;
			for(int j=m+1; j<=e; j++) place[child[j]] = 0;
			place[i] = 1;
			if(Ask(min(child[m],i),max(child[m],i),place)){
				e = m;
			}else s = m+1;
		}
		t[s].pb(i);
	}
	for(int i=0; i<child.size(); i++){
		dfs(child[i],t[i]);
		t[i].clear();
		Answer(min(x,child[i]),max(x,child[i]));
	}
}

void Detect(int T, int n) {
	srand(time(NULL));
	N = n;
	if(T == 1){
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				place[i] = place[j] = true;
				if(Ask(i,j,place)) Answer(i,j);
				place[i] = place[j] = false;
			}
		}
	}else if(T == 2){
		vector<int> tmp;
		for(int i=1; i<N-1; i++) tmp.pb(i);
		divide(0,N-1,tmp);
	}else if(T == 3){
		vector<int> tmp;
		for(int i=1; i<N; i++) tmp.pb(i);
		dfs(0,tmp);
	}
}

Compilation message

park.cpp: In function 'void divide(int, int, std::vector<int>)':
park.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<tmp.size(); i++){
                ^
park.cpp: In function 'void dfs(int, std::vector<int>)':
park.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<child.size(); i++){
                ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2120 KB Output is correct
2 Correct 6 ms 2120 KB Output is correct
3 Correct 6 ms 2120 KB Output is correct
4 Correct 6 ms 2120 KB Output is correct
5 Correct 6 ms 2120 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 2252 KB Output is correct
2 Correct 143 ms 2252 KB Output is correct
3 Correct 126 ms 2252 KB Output is correct
4 Correct 199 ms 2252 KB Output is correct
5 Correct 186 ms 2120 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 2120 KB Output is correct
2 Correct 299 ms 2120 KB Output is correct
3 Correct 289 ms 2120 KB Output is correct
4 Correct 183 ms 2120 KB Output is correct
5 Correct 229 ms 2120 KB Output is correct
6 Correct 219 ms 2120 KB Output is correct
7 Correct 219 ms 2120 KB Output is correct
8 Correct 299 ms 2120 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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