oj.uz

Submission #909886

# Submission time Handle Problem Language Result Execution time Memory
909886 2024-01-17T14:28:34 Z mickey080929 Library (JOI18_library) C++17
100 / 100
 253 ms 1232 KB 
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

int n;
vector<int> adj[1010];

int ask(vector<int> qry) {
	int k = 0;
	for (int i=0; i<n; i++) {
		k += qry[i];
	}
	int al = 0;
	for (int i=0; i<n; i++) {
		for (auto &j : adj[i]) {
			if (qry[i] && qry[j]) {
				al ++;
			}
		}
	}
	al /= 2;
	return k - Query(qry) - al;
}

void Solve(int N) {
	n = N;
	for (int i=0; i<N-1; i++) {
		int lo = 1, hi = N-1;
		while (lo < hi) {
			int mid = lo + hi >> 1;
			vector<int> qry(N, 0);
			for (int j=0; j<=mid; j++) {
				qry[j] = 1;
			}
			if (ask(qry)) hi = mid;
			else lo = mid + 1;
		}
		int r = lo;
		lo = 0; hi = r-1;
		while (lo < hi) {
			int mid = lo + hi + 1 >> 1;
			vector<int> qry(N, 0);
			for (int j=mid; j<=r; j++) {
				qry[j] = 1;
			}
			if (ask(qry)) lo = mid;
			else hi = mid - 1;
		}
		int l = lo;
		adj[l].push_back(r);
		adj[r].push_back(l);
	}
	int x;
	for (int i=0; i<n; i++) {
		if (adj[i].size() == 1) {
			x = i;
			break;
		}
	}
	vector<int> ans;
	int p = -1;
	while (true) {
		ans.push_back(x+1);
		int nxt = -1;
		for (auto &y : adj[x]) {
			if (y != p) {
				nxt = y;
			}
		}
		if (nxt == -1) break;
		p = x;
		x = nxt;
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |    int mid = lo + hi >> 1;
      |              ~~~^~~~
library.cpp:42:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |    int mid = lo + hi + 1 >> 1;
      |              ~~~~~~~~^~~
library.cpp:64:18: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |   ans.push_back(x+1);
      |                 ~^~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 704 KB # of queries: 2792
2 Correct 26 ms 456 KB # of queries: 2777
3 Correct 24 ms 456 KB # of queries: 2922
4 Correct 24 ms 460 KB # of queries: 2915
5 Correct 27 ms 696 KB # of queries: 2928
6 Correct 24 ms 712 KB # of queries: 2930
7 Correct 29 ms 460 KB # of queries: 2920
8 Correct 19 ms 452 KB # of queries: 2777
9 Correct 24 ms 720 KB # of queries: 2911
10 Correct 13 ms 464 KB # of queries: 1717
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 1 ms 344 KB # of queries: 3
14 Correct 1 ms 344 KB # of queries: 9
15 Correct 1 ms 452 KB # of queries: 99
16 Correct 2 ms 344 KB # of queries: 228

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 704 KB # of queries: 2792
2 Correct 26 ms 456 KB # of queries: 2777
3 Correct 24 ms 456 KB # of queries: 2922
4 Correct 24 ms 460 KB # of queries: 2915
5 Correct 27 ms 696 KB # of queries: 2928
6 Correct 24 ms 712 KB # of queries: 2930
7 Correct 29 ms 460 KB # of queries: 2920
8 Correct 19 ms 452 KB # of queries: 2777
9 Correct 24 ms 720 KB # of queries: 2911
10 Correct 13 ms 464 KB # of queries: 1717
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 1 ms 344 KB # of queries: 3
14 Correct 1 ms 344 KB # of queries: 9
15 Correct 1 ms 452 KB # of queries: 99
16 Correct 2 ms 344 KB # of queries: 228
17 Correct 253 ms 960 KB # of queries: 19283
18 Correct 236 ms 716 KB # of queries: 19027
19 Correct 249 ms 468 KB # of queries: 19254
20 Correct 213 ms 968 KB # of queries: 18004
21 Correct 207 ms 464 KB # of queries: 16924
22 Correct 246 ms 472 KB # of queries: 19268
23 Correct 223 ms 712 KB # of queries: 19228
24 Correct 92 ms 464 KB # of queries: 8882
25 Correct 233 ms 716 KB # of queries: 18812
26 Correct 227 ms 464 KB # of queries: 17594
27 Correct 79 ms 724 KB # of queries: 8847
28 Correct 212 ms 1232 KB # of queries: 18932
29 Correct 232 ms 716 KB # of queries: 18911
30 Correct 234 ms 476 KB # of queries: 18932