oj.uz

Submission #110066

# Submission time Handle Problem Language Result Execution time Memory
110066 2019-05-09T06:59:00 Z hugo_pm Library (JOI18_library) C++17
0 / 100
 111 ms 488 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);
			cout << dv << " " << l << "\n";
		}

		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);
			cout << dv << " " << l << "\n";
		}
	}

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

	Answer(ans);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 356 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
2 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
3 Incorrect 10 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
4 Incorrect 6 ms 356 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
5 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
6 Incorrect 7 ms 352 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
7 Incorrect 7 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
8 Incorrect 7 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
9 Incorrect 7 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
10 Incorrect 4 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
11 Correct 2 ms 256 KB # of queries: 0
12 Incorrect 2 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
13 Incorrect 2 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
14 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
15 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
16 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 356 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
2 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
3 Incorrect 10 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
4 Incorrect 6 ms 356 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
5 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
6 Incorrect 7 ms 352 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
7 Incorrect 7 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
8 Incorrect 7 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
9 Incorrect 7 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
10 Incorrect 4 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
11 Correct 2 ms 256 KB # of queries: 0
12 Incorrect 2 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
13 Incorrect 2 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
14 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
15 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
16 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
17 Incorrect 95 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
18 Incorrect 100 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
19 Incorrect 88 ms 368 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
20 Incorrect 81 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
21 Incorrect 78 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
22 Incorrect 111 ms 488 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
23 Incorrect 89 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
24 Incorrect 42 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
25 Incorrect 91 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
26 Incorrect 79 ms 356 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
27 Incorrect 38 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
28 Incorrect 99 ms 380 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
29 Incorrect 92 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
30 Incorrect 91 ms 364 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT