Submission #44261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44261	2018-03-31T04:34:44 Z	HachikujiMayoi	Library (JOI18_library)	C++14	100 / 100	616 ms	844 KB

library

#include "library.h"
#include "bits/stdc++.h"

using namespace std;

const int maxN = 1000;

int chosen[maxN + 10];
int lft;
vector <int> M;
vector <int> order;

int query(int f, int n){
	fill(M.begin(), M.end(), 0);
	for(auto id : order) M[id - 1] = 1;
	for(int i = 0; i < M.size() && n; ++i){
		if(!M[i]) M[i] = 1, n -= 1;	
	}
	for(auto id : order) M[id - 1] = f;
	return Query(M);
}

int QUERY(int id, int start){
	fill(M.begin(), M.end(), 0);
	for(int i = start; i < order.size(); ++i){
		M[order[i] - 1] = 1;
	}
	M[id - 1] = 1;
	return Query(M) == 1;
}

bool OK(int n){
	return query(1, n) <= query(0, n);
}

vector <int> place(int id){
	vector <int> A = {id};
	vector <int> B = order;
	vector <int> ans;
	if(int(order.size()) > 1 && QUERY(id, 1)) swap(A, B);
	ans.insert(ans.end(), A.begin(), A.end());
	ans.insert(ans.end(), B.begin(), B.end());
	return ans;
}

vector <int> get(){
	int lo = 1, hi = lft, ans = lft;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(OK(mid)) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	fill(M.begin(), M.end(), 0);
	for(auto id : order) M[id - 1] = 1;
	for(int i = 0; i < M.size(); ++i){
		if(M[i]) continue;
		--ans;
		if(ans == 0) return place(i + 1);
	}
	assert(0);
}

void Solve(int N){
	M.resize(N);
	order.push_back(1);
	lft = N - 1;
	for(int i = 2; i <= N; ++i){
		order = get();
		--lft;
	}
	Answer(order);
}

Compilation message

library.cpp: In function 'int query(int, int)':
library.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < M.size() && n; ++i){
                 ~~^~~~~~~~~~
library.cpp: In function 'int QUERY(int, int)':
library.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = start; i < order.size(); ++i){
                     ~~^~~~~~~~~~~~~~
library.cpp: In function 'std::vector<int> get()':
library.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < M.size(); ++i){
                 ~~^~~~~~~~~~

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	296 KB	Output is correct
2	Correct	44 ms	364 KB	Output is correct
3	Correct	44 ms	492 KB	Output is correct
4	Correct	45 ms	540 KB	Output is correct
5	Correct	51 ms	588 KB	Output is correct
6	Correct	48 ms	588 KB	Output is correct
7	Correct	43 ms	588 KB	Output is correct
8	Correct	31 ms	588 KB	Output is correct
9	Correct	44 ms	588 KB	Output is correct
10	Correct	24 ms	588 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	2 ms	588 KB	Output is correct
13	Correct	2 ms	588 KB	Output is correct
14	Correct	2 ms	588 KB	Output is correct
15	Correct	3 ms	588 KB	Output is correct
16	Correct	5 ms	588 KB	Output is correct

Subtask #2

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	296 KB	Output is correct
2	Correct	44 ms	364 KB	Output is correct
3	Correct	44 ms	492 KB	Output is correct
4	Correct	45 ms	540 KB	Output is correct
5	Correct	51 ms	588 KB	Output is correct
6	Correct	48 ms	588 KB	Output is correct
7	Correct	43 ms	588 KB	Output is correct
8	Correct	31 ms	588 KB	Output is correct
9	Correct	44 ms	588 KB	Output is correct
10	Correct	24 ms	588 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	2 ms	588 KB	Output is correct
13	Correct	2 ms	588 KB	Output is correct
14	Correct	2 ms	588 KB	Output is correct
15	Correct	3 ms	588 KB	Output is correct
16	Correct	5 ms	588 KB	Output is correct
17	Correct	572 ms	592 KB	Output is correct
18	Correct	542 ms	828 KB	Output is correct
19	Correct	554 ms	828 KB	Output is correct
20	Correct	465 ms	844 KB	Output is correct
21	Correct	420 ms	844 KB	Output is correct
22	Correct	531 ms	844 KB	Output is correct
23	Correct	522 ms	844 KB	Output is correct
24	Correct	179 ms	844 KB	Output is correct
25	Correct	499 ms	844 KB	Output is correct
26	Correct	458 ms	844 KB	Output is correct
27	Correct	166 ms	844 KB	Output is correct
28	Correct	574 ms	844 KB	Output is correct
29	Correct	616 ms	844 KB	Output is correct
30	Correct	531 ms	844 KB	Output is correct