Submission #1161791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161791		Nurislam	Library (JOI18_library)	C++17	0 / 100	112 ms	588 KiB

library

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

//#include "grader.cpp"

using namespace std;

void Solve(int n) {
	
	vector<deque<int>> lq, q;
	
	for(int i = 0; i < n; i ++ ){
		deque<int> res;
		res.push_back(i);
		lq.push_back(res);
	}
	
	auto ask = [&]( int &r, deque<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;
		};
		int x = Query(res);
		for(int &i : res)i = 0;
		return x;
	};
	
	auto pushit = [&] ( int &m, deque<int> &i ) -> void {
		vector<int> res(n, 0);
		
			res[i.front()] = 1;
			
			// front
				res[q[m].front()] = 1;
				if(Query(res) == 1){
					while(i.size()){
						q[m].push_front(i.front());
						i.pop_front();
					}
					return;
				};
				res[q[m].front()] = 0;
			// back
				res[q[m].back()] = 1;
				if(Query(res) == 1){
					while(i.size()){
						q[m].push_back(i.front());
						i.pop_front();
					}
					return;
				};
				res[q[m].back()] = 0;
			
			res[i.front()] = 0;
			
			
			res[i.back()] = 1;
			// front
				res[q[m].front()] = 1;
				if(Query(res) == 1){
					while(i.size()){
						q[m].push_front(i.back());
						i.pop_back();
					}
					return;
				};
				res[q[m].front()] = 0;
			// back
				res[q[m].back()] = 1;
				if(Query(res) == 1){
					while(i.size()){
						q[m].push_back(i.back());
						i.pop_back();
					}
					return;
					
				};
				res[q[m].back()] = 0;
			res[i.back()] = 0;
	};
	
	while(lq.size() != 1){
		
		vector<int> al(n, 0);
		for(deque<int> &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();
		
		//break;
		//reverse(lq.begin(), lq.end());
	}
	vector<int> ans;
	for(int i : lq[0])ans.push_back(i+1);
	Answer(ans);
}

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