oj.uz

Submission #469315

# Submission time Handle Problem Language Result Execution time Memory
469315 2021-08-31T12:13:23 Z keta_tsimakuridze Library (JOI18_library) C++14
100 / 100
 572 ms 308 KB 
#include<bits/stdc++.h>
#include "library.h"
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e3 + 5, mod = 1e9 + 7; // !
int t, used[N],n;
/*
int Query(vector<int> v){
	for(int j = 0; j < n; j++) {
		cout << v[j] <<" ";
	}
	cout << endl;
	int x;
	cin >> x;
	return x;
}
void Answer(vector<int> ans){
	for(int i = 0; i < n; i++) {
		cout << ans[i]
	}	
}
*/
int ask(vector<int> v) {
return Query(v);}
 
void Solve(int n) {
	vector<int> v(n),ans(n);
	if(n == 1) {
		ans[0] = 1;
		Answer(ans);
		return;
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++){
			if(i == j) v[i] = 0;
			else v[j] = 1;
		}
		if(ask(v) == 1) {
			ans[0] = i;
			used[ans[0]] = 1;
			for(int j = 0; j < n; j ++) v[j] = 0;
			break;
		}
	}
	for(int i = 1; i < n; i++){
		#define left Left
		vector<int> left;
		for(int j = 0; j < n; j++){
			if(!used[j]) left.push_back(j);
		}
		int l = 0, r = left.size(); r--;
		while(l <= r){
			int mid = (l + r) / 2;
			for(int j = 0; j < left.size(); j++){
				if(j <= mid) v[left[j]] = 1;
				else v[left[j]] = 0;
			}
			v[ans[i - 1]] = 1;
			int c1 = ask(v);
			v[ans[i - 1]] = 0;
			int c2 = ask(v);
			if(c1 == c2) ans[i] = left[mid], r = mid - 1;
			else l = mid + 1;
		}
		used[ans[i]] = 1;
	}
	for(int i = 0; i < n; i++) ++ans[i];	
	Answer(ans);
}
/*
main(){
	cin >> n;
	solve(n);
 }
*/

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(int j = 0; j < left.size(); j++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB # of queries: 2401
2 Correct 47 ms 200 KB # of queries: 2437
3 Correct 50 ms 200 KB # of queries: 2658
4 Correct 43 ms 200 KB # of queries: 2597
5 Correct 50 ms 200 KB # of queries: 2526
6 Correct 40 ms 200 KB # of queries: 2565
7 Correct 37 ms 200 KB # of queries: 2556
8 Correct 44 ms 200 KB # of queries: 2424
9 Correct 36 ms 200 KB # of queries: 2550
10 Correct 22 ms 200 KB # of queries: 1488
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 3
13 Correct 1 ms 200 KB # of queries: 6
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 79
16 Correct 4 ms 200 KB # of queries: 195

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB # of queries: 2401
2 Correct 47 ms 200 KB # of queries: 2437
3 Correct 50 ms 200 KB # of queries: 2658
4 Correct 43 ms 200 KB # of queries: 2597
5 Correct 50 ms 200 KB # of queries: 2526
6 Correct 40 ms 200 KB # of queries: 2565
7 Correct 37 ms 200 KB # of queries: 2556
8 Correct 44 ms 200 KB # of queries: 2424
9 Correct 36 ms 200 KB # of queries: 2550
10 Correct 22 ms 200 KB # of queries: 1488
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 3
13 Correct 1 ms 200 KB # of queries: 6
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 79
16 Correct 4 ms 200 KB # of queries: 195
17 Correct 505 ms 292 KB # of queries: 18030
18 Correct 547 ms 200 KB # of queries: 17279
19 Correct 457 ms 200 KB # of queries: 17479
20 Correct 493 ms 200 KB # of queries: 16301
21 Correct 470 ms 200 KB # of queries: 15352
22 Correct 518 ms 200 KB # of queries: 17663
23 Correct 572 ms 200 KB # of queries: 17250
24 Correct 159 ms 200 KB # of queries: 7917
25 Correct 510 ms 200 KB # of queries: 17158
26 Correct 430 ms 308 KB # of queries: 16003
27 Correct 187 ms 200 KB # of queries: 8046
28 Correct 476 ms 200 KB # of queries: 15975
29 Correct 501 ms 200 KB # of queries: 15957
30 Correct 425 ms 200 KB # of queries: 15975