oj.uz

답안 #29028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29028 2017-07-18T06:43:22 Z 김동현(#1169) Park (JOI17_park) C++14
47 / 100
 176 ms 2160 KB 
#include "park.h"
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

static int N, a[1400];

static int ask1(int x, int y){
	fill(a, a + N, 0);
	if(x > y) swap(x, y);
	a[x] = a[y] = 1;
	return Ask(x, y, a);
}

static int ask2(int x, int y){
	fill(a, a + N, 1);
	a[x] = 0;
	return Ask(0, y, a);
}

static int ask3(int r, int x, vector<int> v, int s, int e){
	fill(a, a + N, 1);
	for(int i = 0; i < v.size(); i++) if(i < s || e < i) a[v[i]] = 0;
	return Ask(min(r, x), max(r, x), a);
}

static void ans(int x, int y){
	Answer(min(x, y), max(x, y));
}

void f3(int r, vector<int> v){
	if(v.empty()) return;
	vector<int> sr;
	vector<int> ov, sv[7];
	for(auto &i : v){
		if(ask1(r, i)){
			ans(r, i);
			sr.push_back(i);
		}
		else ov.push_back(i);
	}
	for(auto &i : ov){
		int s = 0, e = int(sr.size()) - 1;
		while(s < e){
			int m = (s + e) / 2;
			if(ask3(r, i, sr, s, m)) e = m;
			else s = m + 1;
		}
		sv[s].push_back(i);
	}
	for(int i = 0; i < sr.size(); i++) f3(sr[i], sv[i]);
}

void Detect(int T, int N) {
	::N = N;
	if(T == 1){
		for(int i = 0; i < N; i++){
			for(int j = i + 1; j < N; j++){
				if(ask1(i, j)) ans(i, j);
			}
		}
	}
	else if(T == 2){
		vector<int> v;
		v.push_back(0);
		v.push_back(1);
		fill(a, a + N, 1);
		for(int i = 2; i < N; i++){
			int s = 1, e = i - 1;
			while(s <= e){
				int m = (s + e) / 2;
				if(ask2(i, v[m])) s = m + 1;
				else e = m - 1;
			}
			v.push_back(i);
			rotate(v.begin() + s, v.end() - 1, v.end());
		}
		for(int i = 1; i < N; i++) ans(v[i - 1], v[i]);
	}
	else if(T == 3){
		vector<int> v;
		fill(a, a + N, 1);
		for(int i = 1; i < N; i++) v.push_back(i);
		f3(0, v);
	}
}

Compilation message

park.cpp: In function 'int ask3(int, int, std::vector<int>, int, int)':
park.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) if(i < s || e < i) a[v[i]] = 0;
                   ^
park.cpp: In function 'void f3(int, std::vector<int>)':
park.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sr.size(); i++) f3(sr[i], sv[i]);
                   ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 2028 KB Output is correct
2 Correct 103 ms 2028 KB Output is correct
3 Correct 103 ms 2028 KB Output is correct
4 Correct 163 ms 2028 KB Output is correct
5 Correct 169 ms 2028 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 2028 KB Output is correct
2 Correct 159 ms 2160 KB Output is correct
3 Correct 143 ms 2028 KB Output is correct
4 Correct 123 ms 2160 KB Output is correct
5 Correct 133 ms 2028 KB Output is correct
6 Correct 163 ms 2028 KB Output is correct
7 Correct 139 ms 2160 KB Output is correct
8 Correct 176 ms 2028 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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