Submission #824973

#	Time	Username	Problem	Language	Result	Execution time	Memory
824973		phoenix	Library (JOI18_library)	C++17	100 / 100	296 ms	656 KiB

library

#include<iostream>
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

const int N = 10000;
vector<int> g[N];
vector<int> ord;
void dfs(int s, int p) {
	ord.push_back(s);
	for(int to : g[s]) 
		if(to != p) 
			dfs(to, s);
}
void Solve(int n) {
	vector<pair<int, int>> edges;
	for(int iter = 1; iter < n; iter++) {
		int a, b;
		int lb = 0, rb = n + 1;
		while(rb - lb > 1) {
			int mid = (lb + rb) / 2;
			vector<int> q(n);
			for(int i = 1; i <= mid; i++) 
				q[i - 1] = 1; 
			int cmp = mid;
			for(auto [l, r] : edges) {
				cmp -= (1 <= l && r <= mid);
			}
			if(Query(q) < cmp) rb = mid;
			else lb = mid;
		}
		b = rb;
		lb = 0, rb = b;
		while(rb - lb > 1) {
			int mid = (lb + rb) / 2;
			vector<int> q(n);
			for(int i = mid; i <= b; i++) 
				q[i - 1] = 1;
			int cmp = b - mid + 1;
			for(auto [l, r] : edges) 
				cmp -= (mid <= l && r <= b);
			if(Query(q) < cmp) lb = mid;
			else rb = mid;
		}
		a = lb;
		edges.push_back({a, b});
	}
	for(auto [u, v] : edges) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int t = 0;
	for(int i = 1; i <= n; i++)
		if((int)g[i].size() <= 1) t = i;
	dfs(t, t);
	Answer(ord);

}

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