답안 #347316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347316 2021-01-12T14:09:02 Z maomao90 도서관 (JOI18_library) C++14
100 / 100
483 ms 492 KB
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define pb push_back

void Solve(int n) {
	vector<int> q(n, 1), res(n, -1), done(n, 0);
	if (n == 1) {
		res[0] = 1;
		Answer(res);
		return;
	}
	int end = -1;
	REP (i, 0, n) {
		q[i] = 0;
		if (Query(q) == 1) {
			end = i;
			break;
		}
		q[i] = 1;
	}
	res[0] = end;
	done[end] = 1;
	REP (i, 1, n) {
		vector<int> useful;
		REP (j, 0, n) if (!done[j]) useful.pb(j);
		int lo = 0, hi = useful.size() - 1, mid;
		while (lo < hi) {
			mid = lo + hi + 1 >> 1;
			REP (j, 0, n) q[j] = 0;
			REP (j, 0, mid) q[useful[j]] = 1;
			q[res[i - 1]] = 1;
			int with = Query(q);
			q[res[i - 1]] = 0;
			int without = Query(q);
			if (with == without) {
				hi = mid - 1;
			} else {
				lo = mid;
			}
		}
		res[i] = useful[hi];
		done[useful[hi]] = 1;
	}
	REP (i, 0, n) res[i]++;
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:31:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |    mid = lo + hi + 1 >> 1;
      |          ~~~~~~~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 364 KB # of queries: 2375
2 Correct 36 ms 364 KB # of queries: 2409
3 Correct 39 ms 364 KB # of queries: 2648
4 Correct 42 ms 364 KB # of queries: 2595
5 Correct 37 ms 364 KB # of queries: 2508
6 Correct 38 ms 364 KB # of queries: 2551
7 Correct 43 ms 364 KB # of queries: 2544
8 Correct 36 ms 364 KB # of queries: 2420
9 Correct 29 ms 364 KB # of queries: 2546
10 Correct 26 ms 364 KB # of queries: 1474
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 1
13 Correct 1 ms 364 KB # of queries: 4
14 Correct 1 ms 364 KB # of queries: 7
15 Correct 2 ms 364 KB # of queries: 77
16 Correct 3 ms 364 KB # of queries: 183
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 364 KB # of queries: 2375
2 Correct 36 ms 364 KB # of queries: 2409
3 Correct 39 ms 364 KB # of queries: 2648
4 Correct 42 ms 364 KB # of queries: 2595
5 Correct 37 ms 364 KB # of queries: 2508
6 Correct 38 ms 364 KB # of queries: 2551
7 Correct 43 ms 364 KB # of queries: 2544
8 Correct 36 ms 364 KB # of queries: 2420
9 Correct 29 ms 364 KB # of queries: 2546
10 Correct 26 ms 364 KB # of queries: 1474
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 1
13 Correct 1 ms 364 KB # of queries: 4
14 Correct 1 ms 364 KB # of queries: 7
15 Correct 2 ms 364 KB # of queries: 77
16 Correct 3 ms 364 KB # of queries: 183
17 Correct 343 ms 364 KB # of queries: 17982
18 Correct 334 ms 364 KB # of queries: 17293
19 Correct 400 ms 364 KB # of queries: 17467
20 Correct 349 ms 364 KB # of queries: 16325
21 Correct 341 ms 364 KB # of queries: 15324
22 Correct 332 ms 364 KB # of queries: 17669
23 Correct 377 ms 364 KB # of queries: 17224
24 Correct 158 ms 364 KB # of queries: 7915
25 Correct 345 ms 364 KB # of queries: 17136
26 Correct 483 ms 364 KB # of queries: 15963
27 Correct 155 ms 364 KB # of queries: 8040
28 Correct 376 ms 492 KB # of queries: 15957
29 Correct 282 ms 364 KB # of queries: 15939
30 Correct 289 ms 364 KB # of queries: 15957