Submission #1220981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220981		ssafarov	Library (JOI18_library)	C++20	19 / 100	136 ms	448 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

vector<int> nw(vector<int> v, int x){
	vector<int> nv;
	for(auto g :v){
		if(g == x) continue;
		nv.push_back(g);
	}
	return nv;
}

void Solve(int n)
{
	deque<int> dq;
	dq.push_back(1);
	if(n == 1){
		vector<int> ans;
		ans.push_back(1);
		Answer(ans);
		return;
	}
	vector<int> v;
	for(int i = 2; i <= n; ++i) v.push_back(i);
	int l = -1;
	int r = n - 1;
	while(r - l > 1){
		int mid = (l + r) / 2;
		vector<int> nv(n);
		vector<int> nv2(n);
		for(auto g : dq){
			nv[g - 1] = 1;
			if(g != 1) nv2[g - 1] = 1;
		}
		for(int i = 0; i <= mid; ++i){
			nv[v[i] - 1] = 1;
			nv2[v[i] - 1] = 1;
		}
		int cnt = Query(nv);
		int nc = Query(nv2);
		if(nc == (cnt - 1)){
			l = mid;
		}else r = mid;
	}
	dq.push_back(v[r]);
	v = nw(v, v[r]);
	int ct = 0;
	for(int i = 3; i <= n; ++i){
		int l = -1;
		int r = n - i + 1;
		while(r - l > 1){
			int mid = (l + r) / 2;
			vector<int> sv(n);
			vector<int> nv1(n);
			vector<int> nv2(n);
			for(auto g : dq){
				sv[g - 1] = 1;
				if(g != dq.front())nv1[g - 1] = 1;
				if(g != dq.back()) nv2[g - 1] = 1;
			}
			for(int i = 0; i <= mid; ++i){
				sv[v[i] - 1] = 1;
				nv1[v[i] - 1] = 1;
				nv2[v[i] - 1] = 1;
			}
			int rct = Query(sv);
			int cnt = Query(nv1);
			int nc = Query(nv2);
			if(cnt == (rct + 1)){
				ct = 1;
				r = mid;
			}else if(nc == (rct + 1)){
				ct = 2;
				r = mid;
			}else{
				l = mid;
			}
		}
		if(ct == 1){
			dq.push_front(v[r]);
		}else{
			dq.push_back(v[r]);
		}
		v = nw(v, v[r]);
	}
	vector<int> ans;
	for(auto g : dq){
		ans.push_back(g);
	}
	Answer(ans);
}

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