답안 #906736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906736 2024-01-14T23:17:24 Z NK_ 도서관 (JOI18_library) C++17
100 / 100
204 ms 540 KB
// 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
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 344 KB # of queries: 2586
2 Correct 19 ms 344 KB # of queries: 2591
3 Correct 20 ms 344 KB # of queries: 2726
4 Correct 20 ms 344 KB # of queries: 2724
5 Correct 21 ms 344 KB # of queries: 2708
6 Correct 24 ms 344 KB # of queries: 2714
7 Correct 23 ms 344 KB # of queries: 2716
8 Correct 19 ms 344 KB # of queries: 2611
9 Correct 21 ms 344 KB # of queries: 2709
10 Correct 15 ms 344 KB # of queries: 1601
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 1
13 Correct 1 ms 540 KB # of queries: 5
14 Correct 1 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 90
16 Correct 2 ms 344 KB # of queries: 213
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 344 KB # of queries: 2586
2 Correct 19 ms 344 KB # of queries: 2591
3 Correct 20 ms 344 KB # of queries: 2726
4 Correct 20 ms 344 KB # of queries: 2724
5 Correct 21 ms 344 KB # of queries: 2708
6 Correct 24 ms 344 KB # of queries: 2714
7 Correct 23 ms 344 KB # of queries: 2716
8 Correct 19 ms 344 KB # of queries: 2611
9 Correct 21 ms 344 KB # of queries: 2709
10 Correct 15 ms 344 KB # of queries: 1601
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 1
13 Correct 1 ms 540 KB # of queries: 5
14 Correct 1 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 90
16 Correct 2 ms 344 KB # of queries: 213
17 Correct 194 ms 452 KB # of queries: 18170
18 Correct 192 ms 456 KB # of queries: 17979
19 Correct 204 ms 452 KB # of queries: 18148
20 Correct 181 ms 452 KB # of queries: 16946
21 Correct 182 ms 448 KB # of queries: 15931
22 Correct 201 ms 452 KB # of queries: 18212
23 Correct 190 ms 456 KB # of queries: 18147
24 Correct 73 ms 436 KB # of queries: 8369
25 Correct 182 ms 448 KB # of queries: 17739
26 Correct 158 ms 456 KB # of queries: 16531
27 Correct 70 ms 444 KB # of queries: 8287
28 Correct 183 ms 452 KB # of queries: 16955
29 Correct 197 ms 452 KB # of queries: 16936
30 Correct 165 ms 448 KB # of queries: 16955