Submission #722376

# Submission time Handle Problem Language Result Execution time Memory
722376 2023-04-11T21:01:23 Z FatihSolak Library (JOI18_library) C++17
100 / 100
322 ms 632 KB
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
void Solve(int N){
	if(N == 1){
		Answer({1});
		return;
	}
	vector<int> M(N);
	int tot = 0;
	auto ask = [&](vector<int> &v){
		tot++;
		fill(M.begin(),M.end(),0);
		for(auto u:v){
			M[u] = 1;
		}
		return Query(M);
	};
	auto ok = [&](vector<int> v,int x)->bool{
		if(v.empty())
			return false;
		int tmp = ask(v);
		v.push_back(x);
		return ask(v) <= tmp;
	};
	vector<int> adj[N];
	vector<bool> used(N,0);
	queue<int> q;
	used[0] = 1;
	q.push(0);
	q.push(0);
	while(q.size()){
		int tp = q.front();
		q.pop();
		vector<int> v;
		for(int i = 0;i<N;i++){
			if(!used[i])
				v.push_back(i);
		}
		while(v.size() > 1){
			vector<int> a;
			while(a.size() < v.size()){
				if(v.empty()){
					Answer({});
					exit(0);
				}
				a.push_back(v.back());
				v.pop_back();
			}
			if(!ok(v,tp)){
				v = a;
			}
		}
		if(!ok(v,tp))continue;
		if(v.empty()){
			Answer({});
			exit(0);
		}
		q.push(v[0]);
		used[v[0]] = 1;
		adj[tp].push_back(v[0]);
		adj[v[0]].push_back(tp);
	}
	vector<int> res;
	for(int i = 0;i<N;i++){
		if(adj[i].size() == 1){
			int now = i;
			while(1){
				int tmp = -1;
				if(res.size())
					tmp = res.back();
				res.push_back(now);
				if(res.size() == N)
					break;
				for(auto u:adj[now]){
					if(u != tmp){
						now = u;
						break;
					}
				}	
			}
			break;
		}
	}
	for(auto &u:res)
		u++;
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:73:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     if(res.size() == N)
      |        ~~~~~~~~~~~^~~~
# Verdict Execution time Memory Grader output
1 Correct 38 ms 336 KB # of queries: 2768
2 Correct 42 ms 304 KB # of queries: 2754
3 Correct 41 ms 300 KB # of queries: 2898
4 Correct 39 ms 308 KB # of queries: 2914
5 Correct 57 ms 308 KB # of queries: 2916
6 Correct 37 ms 312 KB # of queries: 2920
7 Correct 44 ms 312 KB # of queries: 2892
8 Correct 44 ms 308 KB # of queries: 2796
9 Correct 45 ms 308 KB # of queries: 2896
10 Correct 18 ms 304 KB # of queries: 1694
11 Correct 1 ms 256 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 2
13 Correct 1 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 16
15 Correct 2 ms 208 KB # of queries: 110
16 Correct 4 ms 208 KB # of queries: 238
# Verdict Execution time Memory Grader output
1 Correct 38 ms 336 KB # of queries: 2768
2 Correct 42 ms 304 KB # of queries: 2754
3 Correct 41 ms 300 KB # of queries: 2898
4 Correct 39 ms 308 KB # of queries: 2914
5 Correct 57 ms 308 KB # of queries: 2916
6 Correct 37 ms 312 KB # of queries: 2920
7 Correct 44 ms 312 KB # of queries: 2892
8 Correct 44 ms 308 KB # of queries: 2796
9 Correct 45 ms 308 KB # of queries: 2896
10 Correct 18 ms 304 KB # of queries: 1694
11 Correct 1 ms 256 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 2
13 Correct 1 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 16
15 Correct 2 ms 208 KB # of queries: 110
16 Correct 4 ms 208 KB # of queries: 238
17 Correct 256 ms 452 KB # of queries: 19214
18 Correct 262 ms 492 KB # of queries: 18958
19 Correct 280 ms 480 KB # of queries: 19204
20 Correct 276 ms 472 KB # of queries: 17896
21 Correct 278 ms 464 KB # of queries: 16818
22 Correct 322 ms 376 KB # of queries: 19134
23 Correct 283 ms 468 KB # of queries: 19142
24 Correct 105 ms 336 KB # of queries: 8832
25 Correct 284 ms 612 KB # of queries: 18718
26 Correct 263 ms 472 KB # of queries: 17460
27 Correct 122 ms 300 KB # of queries: 8796
28 Correct 298 ms 364 KB # of queries: 17976
29 Correct 208 ms 632 KB # of queries: 17956
30 Correct 262 ms 364 KB # of queries: 17976