Submission #1161806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161806		Nurislam	Library (JOI18_library)	C++17	0 / 100	106 ms	432 KiB

library

#include "library.h"
#include <bits/stdc++.h>
//#include <cstdio>

//#include "grader.cpp"

using namespace std;

void Solve(int n) {
	
	vector<vector<int>> lq, q;
	
	for(int i = 0; i < n; i ++ ){
		lq.push_back({i});
	}
	
	auto ask = [&]( int &r, vector<int> &a) -> int{
		vector<int> res(n, 0);
		for(int i : a)res[i] = 1;
		for(int i = 0; i <= r; i ++ )
			for(auto x : q[i])res[x] = 1;
			
		return Query(res);
	};
	
	auto pushit = [&] ( int &m, vector<int> i ) -> void {
		/**/assert(i.size() > 0);
		/**/assert(m < q.size());
		/**/assert(q[m].size() > 0);
		vector<int> res(n, 0);
		for(int x = 0; x < 2; x ++ ){
			/**/assert(i[0] < n);
			
			res[i[0]] = 1;
				res[q[m][0]] = 1;
				/**/ assert(q[m][0] < n);
				if(Query(res) == 1){
					reverse(q[m].begin(), q[m].end());
					for(auto x : i) q[m].push_back(x);
					return;
				};
				res[q[m][0]] = 0;
				
				res[q[m].back()] = 1;
				/**/ assert(q[m].back() < n);
				if(Query(res) == 1){
					for(auto x : i) q[m].push_back(x);
					return;
				};
				res[q[m].back()] = 0;
			res[i[0]] = 0;
			
			reverse(i.begin(), i.end());
		}
			
	};
	
	while(lq.size() != 1){
		
		vector<int> al(n, 0);
		for(auto &res : lq){
			for(int &i : res)al[i] = 1;
			
			if(q.empty() || Query(al) > (int)q.size()){
				q.push_back(res);
				continue;
			}
			
			int l = 0, r = q.size()-1;
			while(l < r) {
				int m = (l + r ) >> 1;
				
				if(ask( m, res ) <= m-l+1) r = m;
				else l = m + 1;
			};
			pushit( l, res );
		};
		lq = q;
		q.clear();
	}
	vector<int> ans;
	for(int i : lq[0])ans.push_back(i+1);
	Answer(ans);
}

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