Submission #565482

#	Time	Username	Problem	Language	Result	Execution time	Memory
565482		lohacho	Library (JOI18_library)	C++14	100 / 100	448 ms	308 KiB

library

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

void Solve(int n)
{
	if(n == 1){
		return Answer({1});
	}
	vector<int> ans(n), inans(n);
	vector<int> chk(n, 1);
	for(int i = 0; i < n; ++i){
		chk[i] = 0;
		int rv = Query(chk);
		if(rv == 1){
			ans[0] = i;
			inans[i] = 1;
			break;
		}
		chk[i] = 1;
	}
	vector<int> left;
	for(int i = 0; i < n; ++i){
		if(!inans[i]){
			left.push_back(i);
		}
	}
	int low = 0, high = (int)left.size() - 1, mid;
	while(low < high){
		mid = low + high >> 1;
		chk = vector<int>(n);
		chk[ans[0]] = 1;
		for(int i = 0; i <= mid; ++i){
			chk[left[i]] = 1;
		}
		int rv1 = Query(chk);
		chk[ans[0]] = 0;
		int rv2 = Query(chk);
		if(rv1 == rv2){
			high = mid;
		}
		else{
			low = mid + 1;
		}
	}
	ans[1] = left[low]; inans[left[low]] = 1;
	for(int i = 2; i < n; ++i){
		left.clear();
		for(int j = 0; j < n; ++j){
			if(!inans[j]){
				left.push_back(j);
			}
		}
		low = 0, high = (int)left.size() - 1, mid;
		while(low < high){
			mid = low + high >> 1;
			chk = vector<int>(n);
			for(int k = 0; k < i; ++k){
				chk[ans[k]] = 1;
			}
			for(int k = 0; k <= mid; ++k){
				chk[left[k]] = 1;
			}
			int rv1 = Query(chk);
			chk[ans[i - 1]] = 0;
			int rv2 = Query(chk);
			if(rv1 < rv2){
				high = mid;
			}
			else{
				low = mid + 1;
			}
		}
		ans[i] = left[low]; inans[left[low]] = 1;
	}
	for(int i = 0; i < n; ++i){
		++ans[i];
	}
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   mid = low + high >> 1;
      |         ~~~~^~~~~~
library.cpp:54:44: warning: right operand of comma operator has no effect [-Wunused-value]
   54 |   low = 0, high = (int)left.size() - 1, mid;
      |                                            ^
library.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |    mid = low + high >> 1;
      |          ~~~~^~~~~~

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