oj.uz

Submission #205638

# Submission time Handle Problem Language Result Execution time Memory
205638 2020-02-29T11:07:25 Z PeppaPig Library (JOI18_library) C++14
0 / 100
 589 ms 504 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];
  	return Query(v);
}

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 'void solve()':
library.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size() < n) {
        ~~~~~~~~~~~^~~
library.cpp:28:8: warning: unused variable 'valid' [-Wunused-variable]
   bool valid = false;
        ^~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ans.size() < n) {
     ~~~~~~~~~~~^~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 248 KB # of queries: 3133
2 Correct 54 ms 248 KB # of queries: 3115
3 Correct 70 ms 248 KB # of queries: 3286
4 Correct 63 ms 376 KB # of queries: 3286
5 Incorrect 53 ms 324 KB Wrong Answer [8]
6 Correct 77 ms 376 KB # of queries: 3286
7 Correct 64 ms 248 KB # of queries: 3285
8 Correct 60 ms 248 KB # of queries: 3152
9 Correct 61 ms 248 KB # of queries: 3267
10 Correct 43 ms 300 KB # of queries: 1936
11 Correct 6 ms 376 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 376 KB # of queries: 15
15 Correct 7 ms 248 KB # of queries: 124
16 Correct 10 ms 376 KB # of queries: 284

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 248 KB # of queries: 3133
2 Correct 54 ms 248 KB # of queries: 3115
3 Correct 70 ms 248 KB # of queries: 3286
4 Correct 63 ms 376 KB # of queries: 3286
5 Incorrect 53 ms 324 KB Wrong Answer [8]
6 Correct 77 ms 376 KB # of queries: 3286
7 Correct 64 ms 248 KB # of queries: 3285
8 Correct 60 ms 248 KB # of queries: 3152
9 Correct 61 ms 248 KB # of queries: 3267
10 Correct 43 ms 300 KB # of queries: 1936
11 Correct 6 ms 376 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 376 KB # of queries: 15
15 Correct 7 ms 248 KB # of queries: 124
16 Correct 10 ms 376 KB # of queries: 284
17 Incorrect 589 ms 344 KB Wrong Answer [3]
18 Incorrect 560 ms 248 KB Wrong Answer [3]
19 Incorrect 547 ms 376 KB Wrong Answer [3]
20 Correct 537 ms 376 KB # of queries: 19615
21 Correct 464 ms 460 KB # of queries: 18488
22 Incorrect 561 ms 248 KB Wrong Answer [3]
23 Incorrect 535 ms 420 KB Wrong Answer [3]
24 Correct 195 ms 376 KB # of queries: 9748
25 Incorrect 519 ms 504 KB Wrong Answer [3]
26 Correct 486 ms 376 KB # of queries: 19179
27 Correct 189 ms 380 KB # of queries: 9704
28 Incorrect 513 ms 376 KB Wrong Answer [3]
29 Incorrect 514 ms 248 KB Wrong Answer [3]
30 Incorrect 522 ms 248 KB Wrong Answer [3]