Submission #680361

#	Time	Username	Problem	Language	Result	Execution time	Memory
680361		rainboy	Library (JOI18_library)	C++17	100 / 100	233 ms	4304 KiB

library

#include "library.h"
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 1000;

int ii[N][N], kk[N], ii_[2][N], kk_[2], n;

int query(int hl, int hr, int i) {
	vi aa(n, 0);
	aa[i] = 1;
	int k = 0;
	for (int h = hl; h < hr; h++) {
		if (kk[h] == 0)
			continue;
		k++;
		for (int g = 0; g < kk[h]; g++)
			aa[ii[h][g]] = 1;
	}
	return Query(aa) != k + 1;
}

void Solve(int n_) {
	n = n_;
	for (int i = 0; i < n; i++) {
		vi aa(n, 0);
		kk_[0] = kk_[1] = 0;
		int t = 0;
		while (query(0, n, i)) {
			int lower = 0, upper = n;
			while (upper - lower > 1) {
				int h = (lower + upper) / 2;
				if (query(0, h, i))
					upper = h;
				else
					lower = h;
			}
			int h = lower;
			memcpy(ii_[t], ii[h], kk[h] * sizeof *ii[h]), kk_[t] = kk[h], kk[h] = 0;
			vi aa(n, 0);
			aa[i] = 1, aa[ii[h][0]] = 1;
			int x = Query(aa);
			if (x == 2) {
				int tmp;
				for (int h1 = 0, h2 = kk_[t] - 1; h1 < h2; h1++, h2--)
					tmp = ii_[t][h1], ii_[t][h1] = ii_[t][h2], ii_[t][h2] = tmp;
			}
			t++;
		}
		kk[i] = 0;
		for (int h = kk_[0] - 1; h >= 0; h--)
			ii[i][kk[i]++] = ii_[0][h];
		ii[i][kk[i]++] = i;
		for (int h = 0; h < kk_[1]; h++)
			ii[i][kk[i]++] = ii_[1][h];
	}
	for (int i = 0; i < n; i++)
		ii[n - 1][i]++;
	Answer(vector(ii[n - 1], ii[n - 1] + n));
}

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