oj.uz

답안 #119099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119099 2019-06-20T10:26:26 Z spacewalker 도서관 (JOI18_library) C++14
100 / 100
 480 ms 528 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

vector<int> known;

int getNext(int s, vector<int> &pnext) {
	vector<int> pnlist;
	int N = pnext.size();
	for (int i = 0; i < N; ++i) {
		if (pnext[i] == 1) pnlist.push_back(i);
	}
	if (pnlist.size() == 1) return pnlist[0];
//	printf("pnlist from %d:\n", s);
//	for (int x : pnlist) printf("%d ", x);
//	printf("\n");
	vector<int> pnfirst(N), pnsec(N);
	for (int i = 0; i < pnlist.size(); ++i) {
		if (i < pnlist.size() / 2) pnfirst[pnlist[i]] = 1;
		else pnsec[pnlist[i]] = 1;
	}
	int withoutStart = Query(pnfirst);
	pnfirst[s] = 1;
	if (withoutStart != Query(pnfirst)) {
		// the next is not in pnfirst
		return getNext(s, pnsec);
	} else {
		pnfirst[s] = 0;
		return getNext(s, pnfirst);
	}
}

void Solve(int N)
{
	if (N == 1) {
		Answer({1});
		return;
	}
	int start = -1;
	vector<int> toQuery(N, 1);
	for (int i = 0; i < N; ++i) {
		toQuery[i] = 0;
		if (Query(toQuery) == 1) {
			start = i;
			break;
		}
		toQuery[i] = 1;
	}
	vector<int> ans{start};
//	printf("start %d\n", start);
	for (int i = 1; i < N; ++i) {
		vector<int> probableNext(N, 1);
		for (int x : ans) probableNext[x] = 0;
		ans.push_back(getNext(ans.back(), probableNext));
	}
	vector<int> retVal;
	for (int x : ans) retVal.push_back(x + 1);
	Answer(retVal);
}

Compilation message

library.cpp: In function 'int getNext(int, std::vector<int>&)':
library.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pnlist.size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
library.cpp:20:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < pnlist.size() / 2) pnfirst[pnlist[i]] = 1;
       ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 324 KB # of queries: 2375
2 Correct 35 ms 256 KB # of queries: 2409
3 Correct 45 ms 384 KB # of queries: 2648
4 Correct 25 ms 328 KB # of queries: 2595
5 Correct 32 ms 324 KB # of queries: 2508
6 Correct 41 ms 256 KB # of queries: 2551
7 Correct 47 ms 384 KB # of queries: 2544
8 Correct 33 ms 304 KB # of queries: 2420
9 Correct 25 ms 320 KB # of queries: 2546
10 Correct 17 ms 256 KB # of queries: 1474
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 1 ms 256 KB # of queries: 1
13 Correct 3 ms 384 KB # of queries: 4
14 Correct 2 ms 384 KB # of queries: 7
15 Correct 2 ms 256 KB # of queries: 77
16 Correct 5 ms 384 KB # of queries: 183

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 324 KB # of queries: 2375
2 Correct 35 ms 256 KB # of queries: 2409
3 Correct 45 ms 384 KB # of queries: 2648
4 Correct 25 ms 328 KB # of queries: 2595
5 Correct 32 ms 324 KB # of queries: 2508
6 Correct 41 ms 256 KB # of queries: 2551
7 Correct 47 ms 384 KB # of queries: 2544
8 Correct 33 ms 304 KB # of queries: 2420
9 Correct 25 ms 320 KB # of queries: 2546
10 Correct 17 ms 256 KB # of queries: 1474
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 1 ms 256 KB # of queries: 1
13 Correct 3 ms 384 KB # of queries: 4
14 Correct 2 ms 384 KB # of queries: 7
15 Correct 2 ms 256 KB # of queries: 77
16 Correct 5 ms 384 KB # of queries: 183
17 Correct 457 ms 424 KB # of queries: 17982
18 Correct 383 ms 376 KB # of queries: 17293
19 Correct 467 ms 448 KB # of queries: 17467
20 Correct 413 ms 528 KB # of queries: 16325
21 Correct 322 ms 384 KB # of queries: 15324
22 Correct 480 ms 444 KB # of queries: 17669
23 Correct 347 ms 444 KB # of queries: 17224
24 Correct 168 ms 256 KB # of queries: 7915
25 Correct 466 ms 384 KB # of queries: 17136
26 Correct 360 ms 408 KB # of queries: 15963
27 Correct 127 ms 384 KB # of queries: 8040
28 Correct 407 ms 492 KB # of queries: 15957
29 Correct 346 ms 404 KB # of queries: 15939
30 Correct 309 ms 332 KB # of queries: 15957