Submission #338437

#	Time	Username	Problem	Language	Result	Execution time	Memory
338437		alishahali1382	Library (JOI18_library)	C++14	100 / 100	377 ms	492 KiB

library

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

void Solve(int n){
	vector<int> M(n, 1), mark(n, 0);
	vector<int> A;
	if (n==1){
		A={1};
		Answer(A);
		return ;
	}
	for (int i=1; i<=n; i++){
		M[i-1]--;
		if (Query(M)==1){
			A.pb(i);
			mark[i-1]=1;
			break ;
		}
		M[i-1]++;
	}
//	cerr<<"A[0]="<<A[0]<<"\n";
	while (A.size()<n){
		vector<int> vec;
		for (int i=1; i<=n; i++) if (!mark[i-1]) vec.pb(i);
//		cerr<<"vec: ";for (int x:vec) cerr<<x<<" ";cerr<<"\n";
		int dwn=0, up=vec.size();
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			fill(M.begin(), M.end(), 0);
			for (int i=0; i<mid; i++) M[vec[i]-1]++;
			int val=Query(M);
			M[A.back()-1]++;
			if (Query(M)==val) up=mid;
			else dwn=mid;
		}
		A.pb(vec[dwn]);
		mark[vec[dwn]-1]++;
	}
	
	Answer(A);
}
/*
5
4 2 5 3 1

*/

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:24:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |  while (A.size()<n){
      |         ~~~~~~~~^~

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