Submission #1222842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222842		RakhimovAmir	Library (JOI18_library)	C++20	100 / 100	71 ms	668 KiB

library

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

mt19937 rng(time(0));
vector<deque<int>> v;
vector<vector<int>> edg;
vector<int> res;
int last = 1;
int N;

void connect(int x, int y) {
	edg[x].push_back(y);
	edg[y].push_back(x);
}

void psh(int r, int x) {
	vector<int> ask(N, 0);
	if (v[r].size() == 1) {
		connect(v[r].back(), x);	
		v[r].push_back(x);
	} else {
		fill(ask.begin(), ask.end(), 0);
		ask[v[r].back() - 1] = 1;
		ask[x - 1] = 1;
		if (Query(ask) == 1) {
			connect(v[r].back(), x);			
			v[r].push_back(x);
		} else {
			connect(v[r].front(), x);
			v[r].push_front(x);
		}
	}
}

void uebok() {
	cout << "uebki:\n";
	for (auto i : v) {
		for (auto j : i) {
			cout << j << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}

void add(int x) {
	vector<int> ask(N);
	for (auto i : v) {
		for (auto j : i) {
			ask[j - 1] = 1;
		}
	}
	ask[x - 1] = 1;
	int g = Query(ask);
	if (g == last + 1) {
		v.push_back({x});
	} else if (g == last) {
		int l = -1, r = v.size() - 1;
		while (r - l - 1 > 0) {
			int mid = (l + r) / 2;
			fill(ask.begin(), ask.end(), 0);
			for (int i = 0; i <= mid; i++) {
				for (int j : v[i]) {
					ask[j - 1] = 1;
				}
			}
			ask[x - 1] = 1;
			int exp = mid + 1;
			// cout << exp << " " << Query(ask) << " " << mid << "\n";
			if (Query(ask) == exp)
				r = mid;
			else
				l = mid;
		}
		psh(r, x);
	} else {
		int l = -1, r = v.size() - 1;
		while (r - l - 1 > 0) {
			int mid = (l + r) / 2;
			fill(ask.begin(), ask.end(), 0);
			for (int i = 0; i <= mid; i++) {
				for (int j : v[i]) {
					ask[j - 1] = 1;
				}
			}
			ask[x - 1] = 1;
			int exp = mid;
			if (Query(ask) == exp)
				r = mid;
			else
				l = mid;
		}
		int fi = r;
		r--;
		l = -1;
		while (r - l - 1 > 0) {
			int mid = (l + r) / 2;
			fill(ask.begin(), ask.end(), 0);
			for (int i = 0; i <= mid; i++) {
				for (int j : v[i]) {
					ask[j - 1] = 1;
				}
			}
			ask[x - 1] = 1;
			int exp = mid + 1;
			if (Query(ask) == exp)
				r = mid;
			else
				l = mid;
		}
		// cout << fi << " " << r << "\n";
		psh(r, x);
		int le = v[fi].back(), ri = v[r].front();
		fill(ask.begin(), ask.end(), 0);
		ask[v[fi].back() - 1] = 1;
		ask[x - 1] = 1;
		if (Query(ask) == 1) {
			connect(v[fi].back(), x);
		} else {
			connect(v[fi].front(), x);
		}
		v.erase(v.begin() + fi);
		deque<int> nw;
		nw.push_back(x);
		int last = x, go = edg[x][0];
		while (true) {
			nw.push_back(go);
			for (auto to : edg[go]) {
				if (to == last) {
					continue;
				}
				last = go;
				go = to;
				break;
			}
			if (go == nw.back()) {
				break;
			}
		}
		// cout << last << " " << go << "\n";
		// return;
		last = x;
		go = edg[x][1];
		while (true) {
			nw.push_front(go);
			for (auto to : edg[go]) {
				if (to == last) {
					continue;
				}
				last = go;
				go = to;
				break;
			}
			if (go == nw.front()) {
				break;
			}
		}
		v[r] = nw;
	}
	// uebok();
	last = g;
}

void Solve(int N) {
	vector<int> order;
	edg.resize(N + 1);
	::N = N;
	for (int i = 2; i <= N; i++) {
		order.push_back(i);
	}
	shuffle(order.begin(), order.end(), rng);
	v.push_back({1});
	for (auto i : order) {
		add(i);
	}
	for (auto i : v[0]) {
		res.push_back(i);
	}
	Answer(res);
}

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