Submission #58172

#	Time	Username	Problem	Language	Result	Execution time	Memory
58172		khsoo01	Library (JOI18_library)	C++11	100 / 100	700 ms	956 KiB

library

#include "library.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1005;

int n;
bool chk[N];

vector<int> cp[N], qry;

void Solve(int _N)
{
	n = _N;
	for(int i=0;i<n;i++) {
		cp[i].push_back(i);
		qry.push_back(0);
	}
	for(int k=0;k<n-1;k++) {
		int S = 2, E = n-k, P, Q;
		while(S<E) {
			int M = (S+E)/2;
			for(int i=0;i<n;i++) {
				qry[i] = 0;
			}
			for(int i=0,j=0;j<M;i++) {
				if(chk[i]) continue;
				j++;
				for(auto &T : cp[i]) {
					qry[T] = true;
				}
			}
			Query(qry) != M ? E = M : S = M+1;
		}
		for(int i=0,j=0;j<S;i++) {
			if(chk[i]) continue;
			j++;
			Q = i;
		}
		E = S;
		S = 2;
		while(S<E) {
			int M = (S+E)/2;
			for(int i=0;i<n;i++) {
				qry[i] = 0;
			}
			for(int i=Q,j=0;j<M;i--) {
				if(chk[i]) continue;
				j++;
				for(auto T : cp[i]) {
					qry[T] = true;
				}
			}
			Query(qry) != M ? E = M : S = M+1;
		}
		for(int i=Q,j=0;j<S;i--) {
			if(chk[i]) continue;
			j++;
			P = i;
		}
		for(int i=0;i<n;i++) {
			qry[i] = 0;
		}
		for(auto &T : cp[P]) {
			qry[T] = 1;
		}
		qry[cp[Q][0]] = 1;
		if(Query(qry) != 1) reverse(cp[Q].begin(), cp[Q].end());
		for(int i=0;i<n;i++) {
			qry[i] = 0;
		}
		for(auto &T : cp[Q]) {
			qry[T] = 1;
		}
		qry[cp[P].back()] = 1;
		if(Query(qry) != 1) reverse(cp[P].begin(), cp[P].end());
		for(auto &T : cp[Q]) {
			cp[P].push_back(T);
		}
		cp[Q].clear();
		chk[Q] = true;
	}
	for(auto &T : cp[0]) {
		T++;
	}
	Answer(cp[0]);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:20:26: warning: 'Q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int S = 2, E = n-k, P, Q;
                          ^

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