oj.uz

Submission #722358

# Submission time Handle Problem Language Result Execution time Memory
722358 2023-04-11T20:33:37 Z FatihSolak Library (JOI18_library) C++17
0 / 100
 49 ms 436 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
void Solve(int N){
	vector<int> M(N);
	auto ask = [&](vector<int> &v){
		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);
	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);
		}
		if(!ok(v,tp))continue;
		while(v.size() > 1){
			vector<int> a;
			while(a.size() < v.size()){
				a.push_back(v.back());
				v.pop_back();
			}
			if(ok(v,tp)){
				continue;
			}
			v = a;
		}
		if(!ok(v,tp))continue;
		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;
		}
	}
	assert(res.size() == N);
	for(auto &u:res)
		u++;
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:61:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     if(res.size() == N)
      |        ~~~~~~~~~~~^~~~
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:73:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  assert(res.size() == N);
      |         ~~~~~~~~~~~^~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 304 KB # of queries: 3142
2 Correct 45 ms 320 KB # of queries: 3120
3 Correct 42 ms 428 KB # of queries: 3288
4 Correct 46 ms 320 KB # of queries: 3298
5 Correct 43 ms 316 KB # of queries: 3300
6 Correct 48 ms 312 KB # of queries: 3304
7 Correct 34 ms 324 KB # of queries: 3278
8 Correct 43 ms 312 KB # of queries: 3166
9 Correct 34 ms 436 KB # of queries: 3278
10 Correct 21 ms 208 KB # of queries: 1950
11 Runtime error 1 ms 336 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 304 KB # of queries: 3142
2 Correct 45 ms 320 KB # of queries: 3120
3 Correct 42 ms 428 KB # of queries: 3288
4 Correct 46 ms 320 KB # of queries: 3298
5 Correct 43 ms 316 KB # of queries: 3300
6 Correct 48 ms 312 KB # of queries: 3304
7 Correct 34 ms 324 KB # of queries: 3278
8 Correct 43 ms 312 KB # of queries: 3166
9 Correct 34 ms 436 KB # of queries: 3278
10 Correct 21 ms 208 KB # of queries: 1950
11 Runtime error 1 ms 336 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -