Submission #906736

#	Time	Username	Problem	Language	Result	Execution time	Memory
906736		NK_	Library (JOI18_library)	C++17	100 / 100	204 ms	540 KiB

library

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

#define nl '\n'
#define pb push_back
#define pf push_front
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

void Solve(int N) {	
	deque<int> d = {0};
	vi vis(N);

	while(sz(d) < N) {
		vi Q(N, 1); for(auto& x : d) Q[x] = 0;
		int F = (vis[d.front()] ? d.back() : d.front());
		vis[F] = (sz(d) > 1);

		// cout << "D: ";
		// for(auto& x : d) cout << x << " ";
		// cout << endl;

		// cout << "FOCUS: " << F << endl;

		while(1) {
			int on = accumulate(begin(Q), end(Q), 0);
			if (on == 1) {
				Q[F] = 1; if (Query(Q) != 1) break;
				Q[F] = 0;

				int adj = find(begin(Q), end(Q), 1) - begin(Q);
				// cout << "ADJ: " << adj << endl;
				if (d.front() == F) d.pf(adj);
				else d.pb(adj);
				break;
			}

			int amt = on / 2;

			vi L(N), R(N);
			for(int i = 0, cur = 0; i < N; i++) if (Q[i]) {
				if (cur < amt) L[i] = 1;
				else R[i] = 1;
				cur++;
			}

			int resL = Query(L);
			L[F] = 1; int resF = Query(L); L[F] = 0;

			if (resL >= resF) Q = L;
			else Q = R;
		}
	}

	vi ans(begin(d), end(d)); for(auto& x : ans) x++;

	// for(auto& x : ans) cout << x << " ";
	// cout << nl;

	Answer(ans);
}

// g++ -std=c++17 -O2 -o grader grader.cpp A.cpp

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