Submission #260445

#	Time	Username	Problem	Language	Result	Execution time	Memory
260445		songc	Library (JOI18_library)	C++14	100 / 100	619 ms	384 KiB

library

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

int N;
int R[1010];
vector<int> ans, Q;

void Solve(int n){
	N = n;
	if (N==1){
		ans.push_back(1);
		Answer(ans);
        return;
	}
	Q.resize(N);
	for (int i=0; i<N; i++) R[i] = i;
	for (int i=0; i<N; i++){
		for (int j=0; j<N; j++) Q[j] = (i==j)?0:1;
		if (Query(Q) == 1){
			ans.push_back(i);
			for (int j=i; j<N; j++) swap(R[j], R[j+1]);
			break;
		}
	}
	for (int i=N-2; i>0; i--){
		int l=0, h=i, k;
		while (l<=h){
			int m=l+h>>1;
			for (int j=0; j<N; j++) Q[j] = 0;
			for (int j=0; j<=m; j++) Q[R[j]] = 1;
			int x = Query(Q);
			Q[ans.back()] = 1;
			int y = Query(Q);
			if (x == y) k=m, h=m-1;
			else l=m+1;
		}
		ans.push_back(R[k]);
		for (int j=k; j<i; j++) swap(R[j], R[j+1]);
	}
	ans.push_back(R[0]);
	for (int &x : ans) x++;
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m=l+h>>1;
          ~^~
library.cpp:28:17: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int l=0, h=i, k;
                 ^

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