Submission #1225287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225287		ansori	Library (JOI18_library)	C++20	100 / 100	90 ms	648 KiB

library

#include <bits/stdc++.h>

using namespace std;

int n;

int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);
int ask(vector<int> v){
	vector<int> q(n , 0);
	for(auto to : v) q[to - 1] = 1;
	return Query(q);
}

void Solve(int N)
{
	n = N;
	vector<int> ans;
	vector<deque<int>> b;
	for(int i = 1;i <= n; ++ i){
		vector<int> q;
		for(int j = 1;j <= i; ++ j) q.push_back(j);
		int y = ask(q);
		//cout << y << ' ';
		if(y == b.size() + 1){
			b.push_back({i});
			continue ;
		}
		int l = -1;
		int r = b.size() - 1;
		while(l + 1 < r){
			int mid = (l + r) / 2;
			vector<int> f;
			for(int j = 0;j <= mid; ++ j){
				for(auto to : b[j]) f.push_back(to);
			}
			f.push_back(i);
			if(ask(f) <= mid + 1) r = mid;
			else l = mid;
		}
		int p = r;
		vector<int> qu = {b[p].back() , i};
		if(ask(qu) == 1) b[p].push_back(i);
		else b[p].push_front(i);
		if(y == b.size()) continue ;
		deque<int> qq = b[p];
		b.erase(b.begin() + p , b.begin() + p + 1);
		l = -1;
		r = b.size() - 1;
		while(l + 1 < r){
			int mid = (l + r) / 2;
			vector<int> f;
			for(int j = 0;j <= mid; ++ j){
				for(auto to : b[j]) f.push_back(to);
			}
			for(auto to : qq) f.push_back(to);
			if(ask(f) <= mid + 1) r = mid;
			else l = mid;
		}
		if(ask({b[r].back() , qq.front()}) == 1 or ask({b[r].back() , qq.back()}) == 1){
			if(ask({b[r].back() , qq.back()}) == 1) reverse(qq.begin() , qq.end());
			for(auto to : qq) b[r].push_back(to);
		}
		else{
			if(ask({b[r].front() , qq.back()}) == 1) reverse(qq.begin() , qq.end());
			for(auto to : qq) b[r].push_front(to);
		}
	}
	for(auto to : b[0]) ans.push_back(to);
	// for(auto to : ans) cout << to << ' ';
	Answer(ans);
}

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