Submission #1222053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222053		rythm_of_knight	Library (JOI18_library)	C++17	100 / 100	64 ms	532 KiB

library

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

void Solve(int n) {
	vector <int> st(n);
	vector <deque <int>> cur;
	int now = 0;
	for (int i = 0; i < n; i++) {
		st[i] = 1;
		int bec = Query(st);
		if (bec > now) {
			cur.push_back({i});
			now = bec;
		} else if (bec == now) {
			int l = -1, r = cur.size();
			while (l + 1 < r) {
				int m = l + r >> 1;
				vector <int> tmp(n);
				for (int j = 0; j <= m; j++)
					for (int k : cur[j])
						tmp[k] = 1;
				tmp[i] = 1;
				if (Query(tmp) == m + 1)
					r = m;
				else
					l = m;
			}
			vector <int> tmp(n);
			tmp[i] = tmp[cur[r].front()] = 1;
			if (Query(tmp) == 1) {
				cur[r].push_front(i);
			} else {
				cur[r].push_back(i);
			}
		} else {
			int l = -1, r = cur.size();
			while (l + 1 < r) {
				int m = l + r >> 1;
				vector <int> tmp(n);
				for (int j = 0; j <= m; j++)
					for (int k : cur[j])
						tmp[k] = 1;
				tmp[i] = 1;
				if (Query(tmp) <= m + 1)
					r = m;
				else
					l = m;
			}
			int lef = r;
			l = lef, r = cur.size();
			while (l + 1 < r) {
				int m = l + r >> 1;
				vector <int> tmp(n);
				for (int j = 0; j <= m; j++)
					for (int k : cur[j])
						tmp[k] = 1;
				tmp[i] = 1;
				if (Query(tmp) <= m)
					r = m;
				else
					l = m;
			}
			int rig = r;
			deque <int> nw;
			vector <int> tmp(n);
			tmp[i] = tmp[cur[lef].front()] = 1;
			if (Query(tmp) == 1) {
				while (!cur[lef].empty()) {
					nw.push_back(cur[lef].back());
					cur[lef].pop_back();
				}
				swap(cur[lef], nw);
			}
			cur[lef].push_back(i);
			tmp = vector <int> (n, 0);
			tmp[i] = tmp[cur[rig].back()] = 1;
			if (Query(tmp) == 1) {
				while (!cur[rig].empty()) {
					cur[lef].push_back(cur[rig].back());
					cur[rig].pop_back();
				}
			} else {
				while (!cur[rig].empty()) {
					cur[lef].push_back(cur[rig].front());
					cur[rig].pop_front();
				}
			}
			cur.erase(cur.begin() + rig);
			now = bec;
		}
	}
	vector <int> res;
	while (!cur[0].empty()) {
		res.push_back(cur[0].back() + 1);
		cur[0].pop_back();
	}
	Answer(res);
}

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