Submission #44261

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

library

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

using namespace std;

const int maxN = 1000;

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

int query(int f, int n){
	fill(M.begin(), M.end(), 0);
	for(auto id : order) M[id - 1] = 1;
	for(int i = 0; i < M.size() && n; ++i){
		if(!M[i]) M[i] = 1, n -= 1;	
	}
	for(auto id : order) M[id - 1] = f;
	return Query(M);
}

int QUERY(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;
}

bool OK(int n){
	return query(1, n) <= query(0, n);
}

vector <int> place(int id){
	vector <int> A = {id};
	vector <int> B = order;
	vector <int> ans;
	if(int(order.size()) > 1 && QUERY(id, 1)) swap(A, B);
	ans.insert(ans.end(), A.begin(), A.end());
	ans.insert(ans.end(), B.begin(), B.end());
	return ans;
}

vector <int> get(){
	int lo = 1, hi = lft, ans = lft;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(OK(mid)) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	fill(M.begin(), M.end(), 0);
	for(auto id : order) M[id - 1] = 1;
	for(int i = 0; i < M.size(); ++i){
		if(M[i]) continue;
		--ans;
		if(ans == 0) return place(i + 1);
	}
	assert(0);
}

void Solve(int N){
	M.resize(N);
	order.push_back(1);
	lft = N - 1;
	for(int i = 2; i <= N; ++i){
		order = get();
		--lft;
	}
	Answer(order);
}

Compilation message (stderr)

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

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