oj.uz

Submission #529115

# Submission time Handle Problem Language Result Execution time Memory
529115 2022-02-22T07:08:10 Z ftkbrian Library (JOI18_library) C++14
100 / 100
 455 ms 412 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

vector<int> now,lef;
int chk[1010];
void Solve(int N)
{
	if(N == 1) {
		now.push_back(1);
		Answer(now);
		return;
	}
	vector<int> Qur(N,0);
	for(int i = 0 ; i < N ; i++) {
		for(int q = 0 ; q < N ; q++)
			if(q == i) Qur[q] = 0;
			else Qur[q] = 1;
		if(Query(Qur) == 1) {
			now.push_back(i);
			break;
		}
	}
	for(int i = 0 ; i < N ; i++) Qur[i] = 0;
	Qur[now[0]] = 1;
	for(int i = 0 ; i < N ; i++) {
		if(i == now[0]) continue;
		Qur[i] = 1;
		if(Query(Qur) == 1) {
			now.push_back(i); break;
		}
		Qur[i] = 0;
	}
	for(auto i : now) chk[i] = 1;
	for(int i = 0 ; i < N ; i++)
		if(!chk[i]) lef.push_back(i);
	///현재 now에 들어있는 놈이 왼쪽 끝이라 하고 문제를 해결할 것
	for(int i = 2 ; i < N ; i++) {
		int lo = 0,hi = lef.size()-1,loc;
		while(lo <= hi) {
			int mi = lo+hi>>1;
			for(int q = 0 ; q < N ; q++) Qur[q] = 0;
			for(auto q : now) Qur[q] = 1;
			for(int q = lo ; q <= mi ; q++) Qur[lef[q]] = 1;
			int tar = Query(Qur);
			Qur[now.back()] = 0;
			int tar2 = Query(Qur);
			if(tar != tar2) hi = mi-1,loc = mi;
			else lo = mi+1;
		}
		now.push_back(lef[loc]);
		swap(lef[loc],lef.back());
		lef.pop_back();
	}
	for(auto& i : now) i++;
	Answer(now);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |    int mi = lo+hi>>1;
      |             ~~^~~
library.cpp:51:24: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   now.push_back(lef[loc]);
      |                        ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 200 KB # of queries: 2387
2 Correct 40 ms 296 KB # of queries: 2618
3 Correct 41 ms 200 KB # of queries: 2662
4 Correct 45 ms 200 KB # of queries: 2742
5 Correct 40 ms 200 KB # of queries: 2598
6 Correct 38 ms 200 KB # of queries: 2744
7 Correct 41 ms 200 KB # of queries: 2728
8 Correct 36 ms 296 KB # of queries: 2571
9 Correct 34 ms 292 KB # of queries: 2662
10 Correct 22 ms 200 KB # of queries: 1540
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 2
13 Correct 0 ms 288 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 1 ms 200 KB # of queries: 83
16 Correct 3 ms 200 KB # of queries: 208

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 200 KB # of queries: 2387
2 Correct 40 ms 296 KB # of queries: 2618
3 Correct 41 ms 200 KB # of queries: 2662
4 Correct 45 ms 200 KB # of queries: 2742
5 Correct 40 ms 200 KB # of queries: 2598
6 Correct 38 ms 200 KB # of queries: 2744
7 Correct 41 ms 200 KB # of queries: 2728
8 Correct 36 ms 296 KB # of queries: 2571
9 Correct 34 ms 292 KB # of queries: 2662
10 Correct 22 ms 200 KB # of queries: 1540
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 2
13 Correct 0 ms 288 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 1 ms 200 KB # of queries: 83
16 Correct 3 ms 200 KB # of queries: 208
17 Correct 380 ms 292 KB # of queries: 18493
18 Correct 420 ms 292 KB # of queries: 18169
19 Correct 455 ms 284 KB # of queries: 17622
20 Correct 432 ms 320 KB # of queries: 17158
21 Correct 361 ms 284 KB # of queries: 16204
22 Correct 426 ms 320 KB # of queries: 18231
23 Correct 422 ms 284 KB # of queries: 18192
24 Correct 161 ms 280 KB # of queries: 8221
25 Correct 419 ms 412 KB # of queries: 17720
26 Correct 383 ms 304 KB # of queries: 16239
27 Correct 139 ms 200 KB # of queries: 8514
28 Correct 423 ms 200 KB # of queries: 17558
29 Correct 422 ms 200 KB # of queries: 17522
30 Correct 449 ms 292 KB # of queries: 17558