oj.uz

Submission #963689

# Submission time Handle Problem Language Result Execution time Memory
963689 2024-04-15T13:30:28 Z yellowtoad Library (JOI18_library) C++17
100 / 100
 198 ms 696 KB 
#include <cstdio>
#include <vector>
#include <iostream>
#include "library.h"
using namespace std;

void Solve(int n)
{
	int x, y;
	vector<int> b(n,1), res, tmp, tmmp;
	if (n == 1) {
		Answer({1});
		return;
	}
	for (int i = 1; i <= n; i++) {
		b[i-1] = 0;
		if (Query(b) == 1) {
			res.push_back(i);
			for (int j = 1; j <= n; j++) if (j != i) tmp.push_back(j);
			break;
		}
		b[i-1] = 1;
	}
	for (int i = 2; i <= n; i++) {
		int l = 0, r = tmp.size()-1;
		while (l != r) {
			int mid = (l+r)/2;
			for (int j = 0; j < n; j++) b[j] = 0;
			for (int j = 0; j < res.size(); j++) b[res[j]-1] = 1;
			for (int j = 0; j <= mid; j++) b[tmp[j]-1] = 1;
			x = Query(b);
			b[res.back()-1] = 0;
			y = Query(b);
			if (i == 2) {
				if (x == y) r = mid;
				else l = mid+1;
			} else {
				if (y > x) r = mid;
				else l = mid+1;
			}
		}
		res.push_back(tmp[l]);
		tmmp.clear();
		for (int j = 0; j < tmp.size(); j++) if (j != l) tmmp.push_back(tmp[j]);
		tmp = tmmp;
	}
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    for (int j = 0; j < res.size(); j++) b[res[j]-1] = 1;
      |                    ~~^~~~~~~~~~~~
library.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j = 0; j < tmp.size(); j++) if (j != l) tmmp.push_back(tmp[j]);
      |                   ~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 436 KB # of queries: 2387
2 Correct 20 ms 436 KB # of queries: 2433
3 Correct 23 ms 432 KB # of queries: 2638
4 Correct 18 ms 440 KB # of queries: 2593
5 Correct 17 ms 440 KB # of queries: 2504
6 Correct 17 ms 432 KB # of queries: 2553
7 Correct 17 ms 436 KB # of queries: 2568
8 Correct 21 ms 432 KB # of queries: 2402
9 Correct 15 ms 432 KB # of queries: 2512
10 Correct 11 ms 436 KB # of queries: 1478
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 1 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 73
16 Correct 1 ms 344 KB # of queries: 187

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 436 KB # of queries: 2387
2 Correct 20 ms 436 KB # of queries: 2433
3 Correct 23 ms 432 KB # of queries: 2638
4 Correct 18 ms 440 KB # of queries: 2593
5 Correct 17 ms 440 KB # of queries: 2504
6 Correct 17 ms 432 KB # of queries: 2553
7 Correct 17 ms 436 KB # of queries: 2568
8 Correct 21 ms 432 KB # of queries: 2402
9 Correct 15 ms 432 KB # of queries: 2512
10 Correct 11 ms 436 KB # of queries: 1478
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 1 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 73
16 Correct 1 ms 344 KB # of queries: 187
17 Correct 188 ms 684 KB # of queries: 18008
18 Correct 178 ms 440 KB # of queries: 17231
19 Correct 190 ms 440 KB # of queries: 17451
20 Correct 141 ms 696 KB # of queries: 16277
21 Correct 149 ms 444 KB # of queries: 15362
22 Correct 191 ms 436 KB # of queries: 17617
23 Correct 156 ms 436 KB # of queries: 17170
24 Correct 81 ms 440 KB # of queries: 7885
25 Correct 164 ms 440 KB # of queries: 17118
26 Correct 159 ms 440 KB # of queries: 15989
27 Correct 75 ms 440 KB # of queries: 7994
28 Correct 177 ms 440 KB # of queries: 17935
29 Correct 198 ms 696 KB # of queries: 17915
30 Correct 170 ms 440 KB # of queries: 17935