oj.uz

답안 #205634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205634 2020-02-29T11:06:13 Z PeppaPig 도서관 (JOI18_library) C++14
0 / 100
 601 ms 1464 KB 
#include "library.h"
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 1e3+5;
const int M = 98765431;

long mpow[N];
map<long, int> mp;

int ask(vector<int> &v) {
	long hsh = 0;
	for(int i = 0; i < v.size(); i++) if(v[i]) hsh += mpow[i];	
	if(!mp.count(hsh)) return mp[hsh] = Query(v);
	else return mp[hsh];
}

int n;
vector<int> vec, ans = {1};

void solve() {
	while(ans.size() < n) {
		int l = 0, r = n-1;
		bool valid = false;
		while(l < r) {
			int mid = (l + r) >> 1;

			vector<int> now = vec;
			for(int i = l; i <= mid; i++) now[i] = 1;

			int q1 = accumulate(now.begin(), now.end(), 0) ? ask(now) : 0;
			now[ans.back()-1] = 0;
			int q2 = accumulate(now.begin(), now.end(), 0) ? ask(now) : 0;

			if(ans.size() == 1) {
				if(q1 <= q2) r = mid;
				else l = mid + 1;
			} else {
				if(q1 < q2) r = mid;
				else l = mid + 1;
			}
		}

		for(int x : ans) if(x == r + 1) return;
		vector<int> now = vec; now[r] = 1;
		if(ask(now) == 1) ans.emplace_back(r + 1), vec[r] = 1;
		else return;
	}
}

void Solve(int _n) {
	n = _n;
	mpow[0] = 1;
	for(int i = 1; i < N; i++) mpow[i] = mpow[i-1] * M;

	vec = vector<int>(n);	
	vec[0] = 1;
	solve();
	if(ans.size() < n) {
		reverse(ans.begin(), ans.end());
		solve();
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'int ask(std::vector<int>&)':
library.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) if(v[i]) hsh += mpow[i]; 
                 ~~^~~~~~~~~~
library.cpp: In function 'void solve()':
library.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size() < n) {
        ~~~~~~~~~~~^~~
library.cpp:27:8: warning: unused variable 'valid' [-Wunused-variable]
   bool valid = false;
        ^~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ans.size() < n) {
     ~~~~~~~~~~~^~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 536 KB # of queries: 2193
2 Correct 43 ms 504 KB # of queries: 2188
3 Correct 51 ms 468 KB # of queries: 2324
4 Correct 46 ms 376 KB # of queries: 2263
5 Incorrect 64 ms 376 KB Wrong Answer [8]
6 Correct 42 ms 376 KB # of queries: 2299
7 Correct 48 ms 520 KB # of queries: 2270
8 Correct 47 ms 424 KB # of queries: 2154
9 Correct 63 ms 632 KB # of queries: 2310
10 Correct 43 ms 504 KB # of queries: 1309
11 Correct 5 ms 248 KB # of queries: 0
12 Correct 5 ms 248 KB # of queries: 2
13 Incorrect 5 ms 376 KB Wrong Answer [8]
14 Correct 5 ms 248 KB # of queries: 7
15 Correct 5 ms 248 KB # of queries: 62
16 Correct 7 ms 324 KB # of queries: 168

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 536 KB # of queries: 2193
2 Correct 43 ms 504 KB # of queries: 2188
3 Correct 51 ms 468 KB # of queries: 2324
4 Correct 46 ms 376 KB # of queries: 2263
5 Incorrect 64 ms 376 KB Wrong Answer [8]
6 Correct 42 ms 376 KB # of queries: 2299
7 Correct 48 ms 520 KB # of queries: 2270
8 Correct 47 ms 424 KB # of queries: 2154
9 Correct 63 ms 632 KB # of queries: 2310
10 Correct 43 ms 504 KB # of queries: 1309
11 Correct 5 ms 248 KB # of queries: 0
12 Correct 5 ms 248 KB # of queries: 2
13 Incorrect 5 ms 376 KB Wrong Answer [8]
14 Correct 5 ms 248 KB # of queries: 7
15 Correct 5 ms 248 KB # of queries: 62
16 Correct 7 ms 324 KB # of queries: 168
17 Correct 485 ms 1420 KB # of queries: 15897
18 Correct 478 ms 1464 KB # of queries: 15756
19 Correct 487 ms 1464 KB # of queries: 15893
20 Correct 459 ms 1196 KB # of queries: 14881
21 Correct 436 ms 1144 KB # of queries: 13963
22 Correct 601 ms 1340 KB # of queries: 15939
23 Correct 522 ms 1288 KB # of queries: 15949
24 Correct 233 ms 748 KB # of queries: 7092
25 Correct 548 ms 1272 KB # of queries: 15574
26 Correct 485 ms 1232 KB # of queries: 14515
27 Correct 164 ms 760 KB # of queries: 7172
28 Correct 214 ms 684 KB # of queries: 6034
29 Correct 196 ms 836 KB # of queries: 6030
30 Correct 216 ms 608 KB # of queries: 6034