답안 #329213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329213 2020-11-19T22:01:55 Z NachoLibre 도서관 (JOI18_library) C++14
100 / 100
367 ms 640 KB
#include <bits/stdc++.h>
using namespace std;
#include "library.h"

const int N = 1003;
int e[N][2];
vector<int> qv;

int ask(vector<int> v) {
	for(int i = 0; i < qv.size(); ++i) qv[i] = 0;
	for(int i = 0; i <  v.size(); ++i) qv[v[i] - 1] = 1;
	return Query(qv);
}

bool neig(vector<int> v, int x) {
	int a = ask(v);
	v.push_back(x);
	int b = ask(v);
	return(a >= b);
}

void dvd(vector<int> &v, int x) {
	int n = v.size();
	vector<int> l;
	for(int i = 0; i < n / 2; ++i) {
		l.push_back(v[i]);
	}
	if(neig(l, x)) v = l;
	else {
		l.clear();
		for(int i = n / 2; i < n; ++i) {
			l.push_back(v[i]);
		}
		v = l;
	}
}

void Solve(int n) {
	if(n == 1) {
		Answer({1});
		return;
	}
	for(int i = 0; i < n; ++i) qv.push_back(0);
	vector<int> v;
	for(int i = 2; i <= n; ++i) {
		v.push_back(i);
	}
	int dg = 1;
	while(v.size()) {
		vector<int> u = v;
		while(u.size() > 1) {
			dvd(u, dg);
		}
		if(neig(u, dg)) {
			e[dg][0] = u[0];
			e[u[0]][1] = dg;
			dg = u[0];
			v.erase(find(v.begin(), v.end(), u[0]));
		} else {
			break;
		}
	}
	dg = 1;
	while(v.size()) {
		vector<int> u = v;
		while(u.size() > 1) {
			dvd(u, dg);
		}
		e[dg][1] = u[0];
		e[u[0]][0] = dg;
		dg = u[0];
		v.erase(find(v.begin(), v.end(), u[0]));
	}
	dg = 1;
	while(e[dg][0]) dg = e[dg][0];
	while(dg) {
		v.push_back(dg);
		dg = e[dg][1];
	}
	Answer(v);
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}*/

Compilation message

library.cpp: In function 'int ask(std::vector<int>)':
library.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = 0; i < qv.size(); ++i) qv[i] = 0;
      |                 ~~^~~~~~~~~~~
library.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i <  v.size(); ++i) qv[v[i] - 1] = 1;
      |                 ~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 364 KB # of queries: 2600
2 Correct 29 ms 384 KB # of queries: 2506
3 Correct 39 ms 640 KB # of queries: 2712
4 Correct 41 ms 512 KB # of queries: 2628
5 Correct 40 ms 364 KB # of queries: 2774
6 Correct 47 ms 364 KB # of queries: 2634
7 Correct 53 ms 364 KB # of queries: 2768
8 Correct 39 ms 364 KB # of queries: 2678
9 Correct 40 ms 364 KB # of queries: 2582
10 Correct 28 ms 364 KB # of queries: 1602
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 12
15 Correct 2 ms 364 KB # of queries: 104
16 Correct 4 ms 364 KB # of queries: 228
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 364 KB # of queries: 2600
2 Correct 29 ms 384 KB # of queries: 2506
3 Correct 39 ms 640 KB # of queries: 2712
4 Correct 41 ms 512 KB # of queries: 2628
5 Correct 40 ms 364 KB # of queries: 2774
6 Correct 47 ms 364 KB # of queries: 2634
7 Correct 53 ms 364 KB # of queries: 2768
8 Correct 39 ms 364 KB # of queries: 2678
9 Correct 40 ms 364 KB # of queries: 2582
10 Correct 28 ms 364 KB # of queries: 1602
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 12
15 Correct 2 ms 364 KB # of queries: 104
16 Correct 4 ms 364 KB # of queries: 228
17 Correct 289 ms 620 KB # of queries: 17798
18 Correct 298 ms 364 KB # of queries: 18134
19 Correct 367 ms 364 KB # of queries: 19068
20 Correct 330 ms 628 KB # of queries: 17814
21 Correct 298 ms 364 KB # of queries: 15288
22 Correct 331 ms 492 KB # of queries: 17228
23 Correct 333 ms 420 KB # of queries: 19014
24 Correct 122 ms 492 KB # of queries: 8836
25 Correct 332 ms 364 KB # of queries: 18612
26 Correct 285 ms 620 KB # of queries: 15866
27 Correct 120 ms 392 KB # of queries: 8508
28 Correct 306 ms 364 KB # of queries: 17954
29 Correct 345 ms 364 KB # of queries: 17934
30 Correct 329 ms 552 KB # of queries: 17954