Submission #205643

# Submission time Handle Problem Language Result Execution time Memory
205643 2020-02-29T11:15:54 Z PeppaPig Library (JOI18_library) C++14
100 / 100
486 ms 1476 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) {
	if(!accumulate(v.begin(), v.end(), 0)) return 0;

	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;

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

	int l = 0, r = n-1;
	while(l < r) {
		int mid = (l + r) >> 1;

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

		int q1 = ask(now);
		for(int i = 0; i < n; i++) now[i] ^= 1;
		int q2 = ask(now);

		if(q1 >= q2) r = mid;
		else l = mid + 1;
	}
	ans.emplace_back(r + 1), vec[r] = 1;
	for(int i = 1; i < n; i++) {
		int l = 0, r = n-1;
		while(l < r) {
			int mid = (l + r) >> 1;

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

			int q1 = ask(now);
			now[ans.back() - 1] = 0;
			int q2 = ask(now);

			if(i == 1) {
				if(q1 == q2) r = mid;
				else l = mid + 1;
			} else {
				if(q1 < q2) r = mid;
				else l = mid + 1;
			}
		}
		ans.emplace_back(r + 1), vec[r] = 1;
	}

	Answer(ans);
}

Compilation message

library.cpp: In function 'int ask(std::vector<int>&)':
library.cpp:18: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]; 
                 ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB # of queries: 2121
2 Correct 48 ms 504 KB # of queries: 2160
3 Correct 42 ms 504 KB # of queries: 2278
4 Correct 44 ms 504 KB # of queries: 2205
5 Correct 43 ms 376 KB # of queries: 2277
6 Correct 46 ms 376 KB # of queries: 2244
7 Correct 40 ms 428 KB # of queries: 2221
8 Correct 40 ms 528 KB # of queries: 2115
9 Correct 48 ms 376 KB # of queries: 2253
10 Correct 23 ms 376 KB # of queries: 1264
11 Correct 4 ms 248 KB # of queries: 0
12 Correct 5 ms 248 KB # of queries: 2
13 Correct 5 ms 248 KB # of queries: 5
14 Correct 5 ms 376 KB # of queries: 8
15 Correct 6 ms 376 KB # of queries: 69
16 Correct 7 ms 376 KB # of queries: 165
# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB # of queries: 2121
2 Correct 48 ms 504 KB # of queries: 2160
3 Correct 42 ms 504 KB # of queries: 2278
4 Correct 44 ms 504 KB # of queries: 2205
5 Correct 43 ms 376 KB # of queries: 2277
6 Correct 46 ms 376 KB # of queries: 2244
7 Correct 40 ms 428 KB # of queries: 2221
8 Correct 40 ms 528 KB # of queries: 2115
9 Correct 48 ms 376 KB # of queries: 2253
10 Correct 23 ms 376 KB # of queries: 1264
11 Correct 4 ms 248 KB # of queries: 0
12 Correct 5 ms 248 KB # of queries: 2
13 Correct 5 ms 248 KB # of queries: 5
14 Correct 5 ms 376 KB # of queries: 8
15 Correct 6 ms 376 KB # of queries: 69
16 Correct 7 ms 376 KB # of queries: 165
17 Correct 479 ms 1400 KB # of queries: 15721
18 Correct 471 ms 1272 KB # of queries: 15574
19 Correct 479 ms 1476 KB # of queries: 15615
20 Correct 421 ms 1256 KB # of queries: 14710
21 Correct 399 ms 1272 KB # of queries: 13823
22 Correct 483 ms 1308 KB # of queries: 15755
23 Correct 483 ms 1324 KB # of queries: 15718
24 Correct 155 ms 760 KB # of queries: 7033
25 Correct 486 ms 1276 KB # of queries: 15343
26 Correct 411 ms 1272 KB # of queries: 14341
27 Correct 159 ms 760 KB # of queries: 7116
28 Correct 202 ms 692 KB # of queries: 6043
29 Correct 194 ms 760 KB # of queries: 6039
30 Correct 200 ms 760 KB # of queries: 6043