Submission #914582

#	Time	Username	Problem	Language	Result	Execution time	Memory
914582		sunwukong123	Library (JOI18_library)	C++14	100 / 100	303 ms	1500 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 

vector<int>adj[1005];
void Solve(int n)
{
	if(n==1){
		vector<int>Ans;Ans.push_back(1);
		return Answer(Ans);
	}
	if(n==2){

		vector<int>Ans;Ans.push_back(1);Ans.push_back(2);
		return Answer(Ans);
	}
	vector<int>books(n,1);
	vector<int> roots;
	set<int> ele;
	for(int i=1;i<=n;i++){
		books[i-1]=0;
		if(Query(books)==1)roots.push_back(i);
		else{
			ele.insert(i);
		}
		books[i-1]=1;
	}
	ele.insert(roots.back());
	roots.pop_back();
	for(int i=2;i<=n;i++){
		int x=roots.back();
		vector<int> cand;
		for(auto x:ele)cand.push_back(x);
		int lo=-1,hi=cand.size();
		while(lo<hi-1){
			int mi=(lo+hi)/2;
			vector<int> qq(n,0);
			for(int e=0;e<=mi;e++){
				qq[cand[e]-1]=1;
			}
			int r1=Query(qq);
			qq[x-1]=1;
			int r2=Query(qq);
			if(r1==r2){ //have the next root
				hi=mi;
			} else {
				lo=mi;
			}
		}
		assert(hi!=cand.size());
		ele.erase(cand[hi]);
		roots.push_back(cand[hi]);
	}
	Answer(roots);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from library.cpp:1:
library.cpp: In function 'void Solve(int)':
library.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   assert(hi!=cand.size());
      |          ~~^~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81