Submission #722376

#	Time	Username	Problem	Language	Result	Execution time	Memory
722376		FatihSolak	Library (JOI18_library)	C++17	100 / 100	322 ms	632 KiB

library

#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 (stderr)

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)
      |        ~~~~~~~~~~~^~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81