제출 #693308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693308		jeroenodb	도서관 (JOI18_library)	C++17	100 / 100	176 ms	628 KiB

library

#include "library.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int n;
int vquery(vi v) {
	vi res(n);
	for(auto i : v) res[i]=1;
	return Query(res);
}
void Solve(int N)
{
	
	n=N;
	vi special(n);
	{
	int num=0;
	for(int i=0;i<n;++i) {
		special[i]=1;
		num++;
		if(Query(special)!=num) {
			special[i]=0;
			num--;
		}
	}
	}
	vvi comps;
	for(int i=0;i<n;++i) if(special[i]) {
		comps.push_back({i});
	}
	auto merge = [&](vi old, vi nw) {
		if(vquery({old[0],nw[0]})!=1) {
			reverse(all(old));
		}
		reverse(all(nw));
		nw.insert(nw.end(),all(old));
		return nw;
	};

	auto addCmp = [&]( vi cmp) {
		auto check = [&](int i) {
			vi res(n);
			for(auto& v : cmp) res[v]=1;
			for(int j=0;j<=i;++j) {
				for(auto v : comps[j]) res[v]=1;
			}
			return Query(res);
		};
		if(check(comps.size()-1)>comps.size()) {
			return cmp;
		}
		int l = 0, r = comps.size()-1;
		while(l<r) {
			int mid = (l+r)/2;
			// check prefix, what then?
			// if found component, check on which side
			// merge it.
			// remove this component for now,
			// add it back.
			if(check(mid)>mid+1) {
				l = mid+1;
			} else {
				r = mid;
			}
		}
		// found place to insert
		auto old = comps[l];
		comps.erase(comps.begin()+l);
		return merge(old,cmp);
	};
	for(int i=0;i<n;++i) if(!special[i]) {
		vi cmp = {i};
		// find where it belongs
		cmp = addCmp(cmp);
		cmp = addCmp(cmp);
		comps.push_back(cmp);
	}
	assert(comps.size()==1);
	for(auto& i : comps[0]) ++i;
	Answer(comps[0]);
}

컴파일 시 표준 에러 (stderr) 메시지

library.cpp: In lambda function:
library.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if(check(comps.size()-1)>comps.size()) {
      |      ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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