Submission #119099

#	Time	Username	Problem	Language	Result	Execution time	Memory
119099		spacewalker	Library (JOI18_library)	C++14	100 / 100	480 ms	528 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

vector<int> known;

int getNext(int s, vector<int> &pnext) {
	vector<int> pnlist;
	int N = pnext.size();
	for (int i = 0; i < N; ++i) {
		if (pnext[i] == 1) pnlist.push_back(i);
	}
	if (pnlist.size() == 1) return pnlist[0];
//	printf("pnlist from %d:\n", s);
//	for (int x : pnlist) printf("%d ", x);
//	printf("\n");
	vector<int> pnfirst(N), pnsec(N);
	for (int i = 0; i < pnlist.size(); ++i) {
		if (i < pnlist.size() / 2) pnfirst[pnlist[i]] = 1;
		else pnsec[pnlist[i]] = 1;
	}
	int withoutStart = Query(pnfirst);
	pnfirst[s] = 1;
	if (withoutStart != Query(pnfirst)) {
		// the next is not in pnfirst
		return getNext(s, pnsec);
	} else {
		pnfirst[s] = 0;
		return getNext(s, pnfirst);
	}
}

void Solve(int N)
{
	if (N == 1) {
		Answer({1});
		return;
	}
	int start = -1;
	vector<int> toQuery(N, 1);
	for (int i = 0; i < N; ++i) {
		toQuery[i] = 0;
		if (Query(toQuery) == 1) {
			start = i;
			break;
		}
		toQuery[i] = 1;
	}
	vector<int> ans{start};
//	printf("start %d\n", start);
	for (int i = 1; i < N; ++i) {
		vector<int> probableNext(N, 1);
		for (int x : ans) probableNext[x] = 0;
		ans.push_back(getNext(ans.back(), probableNext));
	}
	vector<int> retVal;
	for (int x : ans) retVal.push_back(x + 1);
	Answer(retVal);
}
	

Compilation message (stderr)

library.cpp: In function 'int getNext(int, std::vector<int>&)':
library.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pnlist.size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
library.cpp:20:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < pnlist.size() / 2) pnfirst[pnlist[i]] = 1;
       ~~^~~~~~~~~~~~~~~~~~~

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