Submission #205634

#	Time	Username	Problem	Language	Result	Execution time	Memory
205634		PeppaPig	Library (JOI18_library)	C++14	0 / 100	601 ms	1464 KiB

library

#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 (stderr)

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
• Subtask 2: 0 / 81