Submission #44077

#	Time	Username	Problem	Language	Result	Execution time	Memory
44077		HachikujiMayoi	Library (JOI18_library)	C++14	19 / 100	580 ms	844 KiB

library

#include "library.h"
#include "bits/stdc++.h"

using namespace std;

const int maxN = 1000;

int chosen[maxN + 10];
vector <int> M;

int QUERY(vector <int> &order, int id, int start){
	fill(M.begin(), M.end(), 0);
	for(int i = start; i < order.size(); ++i){
		M[order[i] - 1] = 1;
	}
	M[id - 1] = 1;
	return Query(M) == 1;
}

void Solve(int N){
	srand(time(NULL));
	M.resize(N);
	vector <int> order;
	order.push_back(1);
	chosen[1] = 1;
	while(int(order.size()) < N){
		vector <int> rnd, got, norder;
		for(int i = 1; i <= N; ++i){
			if(chosen[i] == 0){
				rnd.push_back(i);
			}
		}
		random_shuffle(rnd.begin(), rnd.end());
		for(auto id : rnd){
			if(QUERY(order, id, 0)){
				got.push_back(id);
				if(int(got.size()) > 1) break;
			}
		}
		if(int(got.size()) == 1){
			if(int(order.size()) == 1){
				norder.push_back(got[0]);
				norder.push_back(order[0]);
			}
			else{
				if(QUERY(order, got[0], 1)){
					norder.insert(norder.end(), order.begin(), order.end());
					norder.push_back(got[0]);
				}
				else{
					norder.push_back(got[0]);
					norder.insert(norder.end(), order.begin(), order.end());
				}
			}
		}
		else{
			if(int(order.size()) == 1){
				norder.push_back(got[0]);
				norder.push_back(order[0]);
				norder.push_back(got[1]);
			}
			else{
				if(QUERY(order, got[0], 1)){
					swap(got[0], got[1]);
				}
				norder.push_back(got[0]);
				norder.insert(norder.end(), order.begin(), order.end());
				norder.push_back(got[1]);
			}
		}
		order = norder;
		for(auto id : got){
			chosen[id] = 1;
		}
	}
	Answer(order);
}

Compilation message (stderr)

library.cpp: In function 'int QUERY(std::vector<int>&, int, int)':
library.cpp:13:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = start; i < order.size(); ++i){
                     ~~^~~~~~~~~~~~~~

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