Submission #221849

#	Time	Username	Problem	Language	Result	Execution time	Memory
221849		patrikpavic2	Library (JOI18_library)	C++17	100 / 100	466 ms	504 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"

#define PB push_back

using namespace std;

typedef vector < int > vi;

int n;

bool provjeri(vi skp, int x){
	vi glp(n);
	for(int y : skp)
		glp[y] = 1;
	int ans1 = Query(glp);
	glp[x] = 1;
	int ans2 = Query(glp);
	return ans1 == ans2;
}

int pocetak(){
	vi glp(n);
	for(int i = 0;i < n;i++)
		glp[i] = 1;
	for(int i = 0;i < n;i++){
		glp[i] = 0;
		if(Query(glp) == 1)
			return i;
		glp[i] = 1;
	}
}

int nadi(vi skp,int x){
	int ret = -1;
	for(int i = 10;i >= 0;i--){
		if((ret + (1 << i)) >= (int)skp.size())
			continue;
		vi tmp;
		for(int j = 0;j <= (ret + (1 << i));j++)
			tmp.PB(skp[j]);
		if(!provjeri(tmp, x))
			ret += (1 << i);
	}
	return skp[ret + 1];
}

void Solve(int nn){
	if(nn == 1){
		Answer({1}); return;
	}
	n = nn;
	int st = pocetak();
	vi tren, ret;
	ret.PB(st); 
	for(int i = 0;i < n;i++)
		if(st != i) tren.PB(i);
	for(int i = 1;i < n;i++){
		ret.PB(nadi(tren, ret.back()));
		for(int j = 0;j < n - i;j++){
			if(tren[j] == ret.back()){
				tren.erase(tren.begin() + j);
				break;
			}
		}
	}
	for(int &x : ret) x++;
	Answer(ret);
}

Compilation message (stderr)

library.cpp: In function 'int pocetak()':
library.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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