oj.uz

Submission #914582

# Submission time Handle Problem Language Result Execution time Memory
914582 2024-01-22T11:00:03 Z sunwukong123 Library (JOI18_library) C++14
100 / 100
 303 ms 1500 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 

vector<int>adj[1005];
void Solve(int n)
{
	if(n==1){
		vector<int>Ans;Ans.push_back(1);
		return Answer(Ans);
	}
	if(n==2){

		vector<int>Ans;Ans.push_back(1);Ans.push_back(2);
		return Answer(Ans);
	}
	vector<int>books(n,1);
	vector<int> roots;
	set<int> ele;
	for(int i=1;i<=n;i++){
		books[i-1]=0;
		if(Query(books)==1)roots.push_back(i);
		else{
			ele.insert(i);
		}
		books[i-1]=1;
	}
	ele.insert(roots.back());
	roots.pop_back();
	for(int i=2;i<=n;i++){
		int x=roots.back();
		vector<int> cand;
		for(auto x:ele)cand.push_back(x);
		int lo=-1,hi=cand.size();
		while(lo<hi-1){
			int mi=(lo+hi)/2;
			vector<int> qq(n,0);
			for(int e=0;e<=mi;e++){
				qq[cand[e]-1]=1;
			}
			int r1=Query(qq);
			qq[x-1]=1;
			int r2=Query(qq);
			if(r1==r2){ //have the next root
				hi=mi;
			} else {
				lo=mi;
			}
		}
		assert(hi!=cand.size());
		ele.erase(cand[hi]);
		roots.push_back(cand[hi]);
	}
	Answer(roots);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from library.cpp:1:
library.cpp: In function 'void Solve(int)':
library.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   assert(hi!=cand.size());
      |          ~~^~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 460 KB # of queries: 2576
2 Correct 22 ms 712 KB # of queries: 2559
3 Correct 19 ms 716 KB # of queries: 2716
4 Correct 24 ms 724 KB # of queries: 2706
5 Correct 24 ms 472 KB # of queries: 2720
6 Correct 23 ms 980 KB # of queries: 2712
7 Correct 22 ms 720 KB # of queries: 2694
8 Correct 29 ms 724 KB # of queries: 2589
9 Correct 26 ms 720 KB # of queries: 2697
10 Correct 14 ms 460 KB # of queries: 1583
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: 7
14 Correct 1 ms 344 KB # of queries: 12
15 Correct 1 ms 344 KB # of queries: 93
16 Correct 2 ms 460 KB # of queries: 213

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 460 KB # of queries: 2576
2 Correct 22 ms 712 KB # of queries: 2559
3 Correct 19 ms 716 KB # of queries: 2716
4 Correct 24 ms 724 KB # of queries: 2706
5 Correct 24 ms 472 KB # of queries: 2720
6 Correct 23 ms 980 KB # of queries: 2712
7 Correct 22 ms 720 KB # of queries: 2694
8 Correct 29 ms 724 KB # of queries: 2589
9 Correct 26 ms 720 KB # of queries: 2697
10 Correct 14 ms 460 KB # of queries: 1583
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: 7
14 Correct 1 ms 344 KB # of queries: 12
15 Correct 1 ms 344 KB # of queries: 93
16 Correct 2 ms 460 KB # of queries: 213
17 Correct 299 ms 980 KB # of queries: 18170
18 Correct 303 ms 1500 KB # of queries: 17961
19 Correct 290 ms 988 KB # of queries: 18174
20 Correct 278 ms 1496 KB # of queries: 16942
21 Correct 256 ms 1488 KB # of queries: 15943
22 Correct 274 ms 972 KB # of queries: 18184
23 Correct 276 ms 976 KB # of queries: 18169
24 Correct 101 ms 1236 KB # of queries: 8361
25 Correct 301 ms 996 KB # of queries: 17761
26 Correct 232 ms 1236 KB # of queries: 16551
27 Correct 98 ms 492 KB # of queries: 8301
28 Correct 251 ms 980 KB # of queries: 16974
29 Correct 261 ms 980 KB # of queries: 16955
30 Correct 270 ms 1216 KB # of queries: 16974