oj.uz

답안 #205624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205624 2020-02-29T10:28:04 Z PeppaPig 도서관 (JOI18_library) C++14
0 / 100
 563 ms 1452 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;
			}
		}

		vector<int> now = vec;
		now[r] = 1;
		if(ask(vec) == ask(now)) 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 Incorrect 54 ms 376 KB Wrong Answer [6]
2 Correct 44 ms 376 KB # of queries: 2189
3 Correct 40 ms 560 KB # of queries: 2325
4 Correct 47 ms 376 KB # of queries: 2264
5 Incorrect 44 ms 376 KB Wrong Answer [8]
6 Correct 54 ms 504 KB # of queries: 2300
7 Incorrect 50 ms 472 KB Wrong Answer [6]
8 Incorrect 56 ms 376 KB Wrong Answer [6]
9 Correct 55 ms 376 KB # of queries: 2311
10 Incorrect 31 ms 400 KB Wrong Answer [6]
11 Correct 5 ms 248 KB # of queries: 0
12 Correct 5 ms 376 KB # of queries: 2
13 Incorrect 6 ms 376 KB Wrong Answer [8]
14 Correct 5 ms 376 KB # of queries: 7
15 Correct 6 ms 376 KB # of queries: 63
16 Incorrect 9 ms 248 KB Wrong Answer [6]

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 376 KB Wrong Answer [6]
2 Correct 44 ms 376 KB # of queries: 2189
3 Correct 40 ms 560 KB # of queries: 2325
4 Correct 47 ms 376 KB # of queries: 2264
5 Incorrect 44 ms 376 KB Wrong Answer [8]
6 Correct 54 ms 504 KB # of queries: 2300
7 Incorrect 50 ms 472 KB Wrong Answer [6]
8 Incorrect 56 ms 376 KB Wrong Answer [6]
9 Correct 55 ms 376 KB # of queries: 2311
10 Incorrect 31 ms 400 KB Wrong Answer [6]
11 Correct 5 ms 248 KB # of queries: 0
12 Correct 5 ms 376 KB # of queries: 2
13 Incorrect 6 ms 376 KB Wrong Answer [8]
14 Correct 5 ms 376 KB # of queries: 7
15 Correct 6 ms 376 KB # of queries: 63
16 Incorrect 9 ms 248 KB Wrong Answer [6]
17 Correct 502 ms 1404 KB # of queries: 15898
18 Correct 485 ms 1372 KB # of queries: 15757
19 Incorrect 497 ms 1412 KB Wrong Answer [6]
20 Incorrect 472 ms 1444 KB Wrong Answer [6]
21 Incorrect 410 ms 1332 KB Wrong Answer [6]
22 Correct 483 ms 1272 KB # of queries: 15940
23 Incorrect 530 ms 1404 KB Wrong Answer [6]
24 Incorrect 159 ms 760 KB Wrong Answer [6]
25 Incorrect 563 ms 1316 KB Wrong Answer [6]
26 Correct 441 ms 1452 KB # of queries: 14516
27 Incorrect 169 ms 764 KB Wrong Answer [6]
28 Correct 240 ms 760 KB # of queries: 6034
29 Correct 214 ms 664 KB # of queries: 6030
30 Correct 199 ms 888 KB # of queries: 6034