제출 #1161747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161747		Nurislam	Library (JOI18_library)	C++20	0 / 100	12 ms	408 KiB

library

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

//#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 &l, int &r, deque<int> &a) -> int{
		vector<int> res(n, 0);
		for(int i : a)res[i] = 1;
		for(int i = l; i <= r; i ++ ){
			for(auto x : q[i])res[x] = 1;
		};
		//cout << l << ' ' << r << '\n';
		//for(int i : res)cout << i << ' ';
		//cout << '\n';
		//int x = 0;
		return Query(res);
	};
	
	auto pushit = [&] ( int &m, deque<int> &i ) -> void {
		//cout << "Pushit\n";
			//for(auto x : q[m])cout << x << ' ';
			//cout << '\n';
			//for(auto x : i) cout << x << ' ';
			//cout << '\n';
		
			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;
	};
	
	int cnt = 20;
	while(lq.size() > 1 && cnt -- ){
		
		//for(auto &i : lq){
			//for(auto x : i)cout << x << ' ';
			//cout << '\n';
		//}
		//cout << '\n';
		
		vector<int> al(n, 0);
		for(deque<int> &res : lq){
			for(int &i : res)al[i] = 1;
			
			if(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( l, m, res ) <= m-l+1) r = m;
				else l = m + 1;
			};
			pushit( l, res );
		};
		swap(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