Submission #1305784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305784		basic	도서관 (JOI18_library)	C++20	100 / 100	69 ms	484 KiB

library

#include "library.h"
#include <bits/stdc++.h>
#define C(a, b) ed[a].push_back(b), ed[b].push_back(a);
using namespace std;
int k, l[1010], s, e, d, bf, kk;
map<int, int> t;
vector<int> ed[1010], rs;
void dfs(int x, int f) {
	rs.push_back(x);
	for (auto i : ed[x])
		if (i != f)
			dfs(i, x);
}
void Solve(int n) {
	vector<int> m(n), p;
	m[0] = 1, t[1] = 1, bf = 1;
	for (int i = 2; i <= n; i++) {
		m[i - 1] = 1, k = Query(m);
		if (k > bf)
			t[i] = i;
		else {
			vector<int> b;
			for (auto [l, r] : t)
				if (l < r)
					b.push_back(l);
			for (auto [l, r] : t)
				if (l == r)
					b.push_back(l);
			for (auto [l, r] : t)
				if (l > r)
					b.push_back(l);
			for (s = 0, e = b.size() - 1; s < e;) {
				p = m, d = s + e >> 1, kk = k;
				for (int i = s; i <= d; i++)
					p[b[i] - 1] = 0, kk -= t[b[i]] == b[i];
				if (Query(p) > kk)
					e = d;
				else
					s = d + 1;
			}
			int x = b[s], y = t[b[s]];
			t[y] = i, t[i] = y;
			if (x ^ y)
				t.erase(x);
			C(x, i);
			if (k < bf) {
				b.erase(b.begin() + s);
				if (x ^ y)
					b.erase(find(b.begin(), b.end(), y));
				for (s = 0, e = b.size() - 1; s < e;) {
					p = m, d = s + e >> 1, kk = k;
					for (int i = s; i <= d; i++)
						p[b[i] - 1] = 0, kk -= t[b[i]] == b[i];
					if (Query(p) > kk)
						e = d;
					else
						s = d + 1;
				}
				int x = b[s], y = t[b[s]], z = t[i];
				t[y] = z, t[z] = y, t.erase(i);
				if (x ^ y)
					t.erase(x);
				C(x, i);
			}
		}
		bf = k;
	}
	for (int i = 1; i <= n; i++) {
		if (ed[i].size() < 2) {
			dfs(i, 0);
			Answer(rs);
			return;
		}
	}
}

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