Submission #1290859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290859		Jawad_Akbar_JJ	도서관 (JOI18_library)	C++20	100 / 100	68 ms	608 KiB

library

#include <iostream>
#include <deque>
#include <vector>
#include "library.h"

using namespace std;

vector<int> make_vec(int n, deque<deque<int>> & deq, int id, int ex){
	vector<int> ans(n, 0);
	for (int i=0;i<=id;i++){
		for (int j=0;j<deq[i].size();j++)
			ans[deq[i][j]-1] = 1;
	}
	ans[ex - 1] = 1;
	return ans;
}

vector<int> make_vec(int n, int a, int b, int c){
	vector<int> ans(n, 0);
	ans[a-1] = ans[b-1] = ans[c-1] = 1;
	return ans;
}

void Solve(int n){
	deque<deque<int> > deq = {{1}};
	vector<int> v(n, 0);
	v[0] = 1;

	for (int i=2;i<=n;i++){
		v[i-1] = 1;
		int sz = Query(v);

		if (sz == deq.size() + 1){
			deq.push_back({i});
		}
		else if (sz == deq.size()){
			int l = -1, r = deq.size() - 1;
			while (l + 1 < r){
				int mid = (l + r) / 2;
				if (Query(make_vec(n, deq, mid, i)) == mid + 1)
					r = mid;
				else
					l = mid;
			}
			if (Query(make_vec(n, i, i, deq[r][0])) == 1)
				deq[r].push_front(i);
			else
				deq[r].push_back(i);
		}
		else{
			int l1 = -1, r1 = deq.size() - 1, l2 = l1, r2 = r1;
			while (l1 + 1 < r1){
				int mid = (l1 + r1) / 2;
				if (Query(make_vec(n, deq, mid, i)) <= mid + 1)
					r1 = mid;
				else
					l1 = mid;
			}

			while (l2 + 1 < r2){
				int mid = (l2 + r2) / 2;
				if (Query(make_vec(n, deq, mid, i)) <= mid)
					r2 = mid;
				else
					l2 = mid;
			}

			deque<int> d1 = deq[r1], d2 = deq[r2], nw;
			deq.erase(deq.begin() + r2);
			deq.erase(deq.begin() + r1);

			if (Query(make_vec(n, i, d1[0], d2[0])) == 1){
				for (int j=d1.size()-1;j>=0;j--)
					nw.push_back(d1[j]);
				nw.push_back(i);
				for (int j=0;j<d2.size();j++)
					nw.push_back(d2[j]);
			}
			else if (Query(make_vec(n, i, d1[0], d2.back())) == 1){
				for (int j=d1.size()-1;j>=0;j--)
					nw.push_back(d1[j]);
				nw.push_back(i);
				for (int j=d2.size()-1;j>=0;j--)
					nw.push_back(d2[j]);
			}
			else if (Query(make_vec(n, i, d1.back(), d2[0])) == 1){
				for (int j=0;j<d1.size();j++)
					nw.push_back(d1[j]);
				nw.push_back(i);
				for (int j=0;j<d2.size();j++)
					nw.push_back(d2[j]);
			}
			else{
				for (int j=0;j<d1.size();j++)
					nw.push_back(d1[j]);
				nw.push_back(i);
				for (int j=d2.size()-1;j>=0;j--)
					nw.push_back(d2[j]);
			}
			deq.push_back(nw);
		}
	}
	
	vector<int> ans;
	for (int i=0;i<n;i++)
		ans.push_back(deq[0][i]);
	Answer(ans);
}

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