Submission #1144861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144861		SmuggingSpun	Library (JOI18_library)	C++20	100 / 100	117 ms	424 KiB

library

#include "library.h"
#include<bits/stdc++.h>
using namespace std;
void Solve(int n){
	vector<int>ans, M(n);
	if(n == 1){
		ans.emplace_back(1);
		Answer(ans);
		return;
	}
	if(n <= 200){
		vector<pair<int, int>>near(n, make_pair(-1, -1));
		fill(M.begin(), M.end(), 0);
		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n && near[i].second == -1; j++){
				if(near[j].second == -1){
					M[i] = M[j] = 1;
					if(Query(M) == 1){
						if(near[i].first == -1){
							near[i].first = j;
						}
						else{
							near[i].second = j;
						}
						if(near[j].first == -1){
							near[j].first = i;
						}
						else{
							near[j].second = i;
						}
					}
					M[i] = M[j] = 0;
				}
			}
		}
		for(int i = 0; i < n; i++){
			if(near[i].second == -1){
				ans.emplace_back(i);
				int pre = i;
				i = near[i].first;
				while(true){
					ans.emplace_back(i);
					if(near[i].second == -1){
						break;
					}
					int temp = i;
					i = near[i].first ^ near[i].second ^ pre;
					pre = temp;
				}
				break;
			}
		}
	}
	else{
		fill(M.begin(), M.end(), 1);
		for(int i = 0; i < n; i++){
			M[i] = 0;
			if(Query(M) == 1){
				ans.emplace_back(i);
				break;				
			}
			M[i] = 1;
		}
		vector<int>p(n);
		iota(p.begin(), p.end(), 0);
		fill(M.begin(), M.end(), 0);
		for(int _ = 2; _ < n; _++){
			p.erase(find(p.begin(), p.end(), ans.back()));
			int u = ans.back(), low = 0, high = int(p.size()) - 1;
			while(low < high){
				int mid = (low + high) >> 1;
				for(int i = 0; i <= mid; i++){
					M[p[i]] = 1;
				}
				int not_have_u = Query(M);
				M[u] = 1;
				if(Query(M) == not_have_u){
					high = mid;
				}
				else{
					low = mid + 1;
				}
				for(int i = M[u] = 0; i <= mid; i++){
					M[p[i]] = 0;
				}
			}
			ans.emplace_back(p[low]);
		}	
		ans.emplace_back(p[0] ^ p[1] ^ ans.back());
	}
	for(int& x : ans){
		x++;
	}
	Answer(ans);
}

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