Submission #110067

# Submission time Handle Problem Language Result Execution time Memory
110067 2019-05-09T06:59:56 Z hugo_pm Library (JOI18_library) C++17
100 / 100
285 ms 608 KB
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

int nbLivres;
const int borne = 1005;
int nbIv[borne];
vector<int> adj[borne];

int req(int mm, int raj=-1)
{
	vector<int> rq(nbLivres, 0);
	form2(i, 1, mm+1) rq[i-1] = 1;
	if (raj > mm) rq[raj-1] = 1; 
	return Query(rq);
}

vector<int> ans;

void dfs(int nod, int par)
{
	ans.push_back(nod);
	for (int vo : adj[nod]) if (vo != par) {
		dfs(vo, nod);
	}
}

void Solve(int locN)
{
	nbLivres = locN;

	if (nbLivres == 1) {
		Answer({1});
		return;
	}
	form2(dv, 1, nbLivres+1) {
		nbIv[dv] = req(dv);
		if (dv == 1) continue;
		int prev = nbIv[dv-1], cur = nbIv[dv];

		if (cur <= prev) {
			int l = 1, r = dv-1;
			while (l < r) {
				int mid = (l+r) / 2;
				int nouveau = req(mid, dv);
				if (nouveau > nbIv[mid]) l = mid+1;
				else r = mid;
			}
			adj[dv].push_back(l);
			adj[l].push_back(dv);
		}

		if (cur < prev) { // A fusionné deux iv
			int l = 1, r = dv-1;
			while (l < r) {
				int mid = (l+r) / 2;
				int nouveau = req(mid, dv);
				if (nouveau >= nbIv[mid]) l = mid+1;
				else r = mid;
			}
			adj[dv].push_back(l);
			adj[l].push_back(dv);
		}
	}

	form2(dv, 1, nbLivres+1) if (adj[dv].size() == 1U) {
		dfs(dv, -1);
		break;
	}

	Answer(ans);
}
# Verdict Execution time Memory Grader output
1 Correct 22 ms 372 KB # of queries: 1523
2 Correct 25 ms 352 KB # of queries: 1506
3 Correct 23 ms 256 KB # of queries: 1587
4 Correct 26 ms 256 KB # of queries: 1584
5 Correct 25 ms 256 KB # of queries: 1577
6 Correct 25 ms 376 KB # of queries: 1582
7 Correct 16 ms 436 KB # of queries: 1599
8 Correct 32 ms 352 KB # of queries: 1517
9 Correct 24 ms 552 KB # of queries: 1598
10 Correct 11 ms 352 KB # of queries: 940
11 Correct 3 ms 256 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 2
13 Correct 2 ms 256 KB # of queries: 4
14 Correct 2 ms 256 KB # of queries: 8
15 Correct 4 ms 384 KB # of queries: 61
16 Correct 6 ms 384 KB # of queries: 131
# Verdict Execution time Memory Grader output
1 Correct 22 ms 372 KB # of queries: 1523
2 Correct 25 ms 352 KB # of queries: 1506
3 Correct 23 ms 256 KB # of queries: 1587
4 Correct 26 ms 256 KB # of queries: 1584
5 Correct 25 ms 256 KB # of queries: 1577
6 Correct 25 ms 376 KB # of queries: 1582
7 Correct 16 ms 436 KB # of queries: 1599
8 Correct 32 ms 352 KB # of queries: 1517
9 Correct 24 ms 552 KB # of queries: 1598
10 Correct 11 ms 352 KB # of queries: 940
11 Correct 3 ms 256 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 2
13 Correct 2 ms 256 KB # of queries: 4
14 Correct 2 ms 256 KB # of queries: 8
15 Correct 4 ms 384 KB # of queries: 61
16 Correct 6 ms 384 KB # of queries: 131
17 Correct 277 ms 436 KB # of queries: 10295
18 Correct 272 ms 480 KB # of queries: 10159
19 Correct 189 ms 484 KB # of queries: 10274
20 Correct 204 ms 476 KB # of queries: 9621
21 Correct 236 ms 376 KB # of queries: 9030
22 Correct 285 ms 608 KB # of queries: 10315
23 Correct 239 ms 480 KB # of queries: 10263
24 Correct 66 ms 432 KB # of queries: 4780
25 Correct 226 ms 492 KB # of queries: 10072
26 Correct 177 ms 476 KB # of queries: 9411
27 Correct 70 ms 440 KB # of queries: 4765
28 Correct 169 ms 356 KB # of queries: 8978
29 Correct 189 ms 504 KB # of queries: 8968
30 Correct 138 ms 356 KB # of queries: 8978