oj.uz

Submission #565482

# Submission time Handle Problem Language Result Execution time Memory
565482 2022-05-21T00:38:18 Z lohacho Library (JOI18_library) C++14
100 / 100
 448 ms 308 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

void Solve(int n)
{
	if(n == 1){
		return Answer({1});
	}
	vector<int> ans(n), inans(n);
	vector<int> chk(n, 1);
	for(int i = 0; i < n; ++i){
		chk[i] = 0;
		int rv = Query(chk);
		if(rv == 1){
			ans[0] = i;
			inans[i] = 1;
			break;
		}
		chk[i] = 1;
	}
	vector<int> left;
	for(int i = 0; i < n; ++i){
		if(!inans[i]){
			left.push_back(i);
		}
	}
	int low = 0, high = (int)left.size() - 1, mid;
	while(low < high){
		mid = low + high >> 1;
		chk = vector<int>(n);
		chk[ans[0]] = 1;
		for(int i = 0; i <= mid; ++i){
			chk[left[i]] = 1;
		}
		int rv1 = Query(chk);
		chk[ans[0]] = 0;
		int rv2 = Query(chk);
		if(rv1 == rv2){
			high = mid;
		}
		else{
			low = mid + 1;
		}
	}
	ans[1] = left[low]; inans[left[low]] = 1;
	for(int i = 2; i < n; ++i){
		left.clear();
		for(int j = 0; j < n; ++j){
			if(!inans[j]){
				left.push_back(j);
			}
		}
		low = 0, high = (int)left.size() - 1, mid;
		while(low < high){
			mid = low + high >> 1;
			chk = vector<int>(n);
			for(int k = 0; k < i; ++k){
				chk[ans[k]] = 1;
			}
			for(int k = 0; k <= mid; ++k){
				chk[left[k]] = 1;
			}
			int rv1 = Query(chk);
			chk[ans[i - 1]] = 0;
			int rv2 = Query(chk);
			if(rv1 < rv2){
				high = mid;
			}
			else{
				low = mid + 1;
			}
		}
		ans[i] = left[low]; inans[left[low]] = 1;
	}
	for(int i = 0; i < n; ++i){
		++ans[i];
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   mid = low + high >> 1;
      |         ~~~~^~~~~~
library.cpp:54:44: warning: right operand of comma operator has no effect [-Wunused-value]
   54 |   low = 0, high = (int)left.size() - 1, mid;
      |                                            ^
library.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |    mid = low + high >> 1;
      |          ~~~~^~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 208 KB # of queries: 2387
2 Correct 34 ms 208 KB # of queries: 2433
3 Correct 39 ms 208 KB # of queries: 2638
4 Correct 34 ms 208 KB # of queries: 2593
5 Correct 38 ms 208 KB # of queries: 2504
6 Correct 35 ms 208 KB # of queries: 2553
7 Correct 35 ms 208 KB # of queries: 2568
8 Correct 35 ms 208 KB # of queries: 2402
9 Correct 38 ms 208 KB # of queries: 2512
10 Correct 20 ms 208 KB # of queries: 1478
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 73
16 Correct 2 ms 208 KB # of queries: 187

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 208 KB # of queries: 2387
2 Correct 34 ms 208 KB # of queries: 2433
3 Correct 39 ms 208 KB # of queries: 2638
4 Correct 34 ms 208 KB # of queries: 2593
5 Correct 38 ms 208 KB # of queries: 2504
6 Correct 35 ms 208 KB # of queries: 2553
7 Correct 35 ms 208 KB # of queries: 2568
8 Correct 35 ms 208 KB # of queries: 2402
9 Correct 38 ms 208 KB # of queries: 2512
10 Correct 20 ms 208 KB # of queries: 1478
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 73
16 Correct 2 ms 208 KB # of queries: 187
17 Correct 448 ms 288 KB # of queries: 18008
18 Correct 419 ms 308 KB # of queries: 17231
19 Correct 431 ms 308 KB # of queries: 17451
20 Correct 385 ms 304 KB # of queries: 16277
21 Correct 354 ms 208 KB # of queries: 15362
22 Correct 440 ms 208 KB # of queries: 17617
23 Correct 353 ms 208 KB # of queries: 17170
24 Correct 100 ms 304 KB # of queries: 7885
25 Correct 425 ms 208 KB # of queries: 17118
26 Correct 335 ms 288 KB # of queries: 15989
27 Correct 111 ms 208 KB # of queries: 7994
28 Correct 419 ms 208 KB # of queries: 17935
29 Correct 429 ms 208 KB # of queries: 17915
30 Correct 439 ms 208 KB # of queries: 17935