Submission #110067

#	Time	Username	Problem	Language	Result	Execution time	Memory
110067		hugo_pm	Library (JOI18_library)	C++17	100 / 100	285 ms	608 KiB

library

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

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

int nbLivres;
const int borne = 1005;
int nbIv[borne];
vector<int> adj[borne];

int req(int mm, int raj=-1)
{
	vector<int> rq(nbLivres, 0);
	form2(i, 1, mm+1) rq[i-1] = 1;
	if (raj > mm) rq[raj-1] = 1; 
	return Query(rq);
}

vector<int> ans;

void dfs(int nod, int par)
{
	ans.push_back(nod);
	for (int vo : adj[nod]) if (vo != par) {
		dfs(vo, nod);
	}
}

void Solve(int locN)
{
	nbLivres = locN;

	if (nbLivres == 1) {
		Answer({1});
		return;
	}
	form2(dv, 1, nbLivres+1) {
		nbIv[dv] = req(dv);
		if (dv == 1) continue;
		int prev = nbIv[dv-1], cur = nbIv[dv];

		if (cur <= prev) {
			int l = 1, r = dv-1;
			while (l < r) {
				int mid = (l+r) / 2;
				int nouveau = req(mid, dv);
				if (nouveau > nbIv[mid]) l = mid+1;
				else r = mid;
			}
			adj[dv].push_back(l);
			adj[l].push_back(dv);
		}

		if (cur < prev) { // A fusionné deux iv
			int l = 1, r = dv-1;
			while (l < r) {
				int mid = (l+r) / 2;
				int nouveau = req(mid, dv);
				if (nouveau >= nbIv[mid]) l = mid+1;
				else r = mid;
			}
			adj[dv].push_back(l);
			adj[l].push_back(dv);
		}
	}

	form2(dv, 1, nbLivres+1) if (adj[dv].size() == 1U) {
		dfs(dv, -1);
		break;
	}

	Answer(ans);
}

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