Submission #288550

#	Time	Username	Problem	Language	Result	Execution time	Memory
288550		user202729	Ancient Books (IOI17_books)	C++17	100 / 100	732 ms	90560 KiB

books

// moreflags=grader.cpp
// 11
// late
// ...
//

#include "books.h"
#include<algorithm>
#include<numeric>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<climits>


long long minimum_walk(std::vector<int> p, int s) {
	assert(s>=0); assert(s<(int)p.size());

	int64_t result{};
	for(int index=0; index<(int)p.size(); ++index){
		if(index<p[index]){
			result+=p[index]-index;
		}
	}

	struct Dsu{
		std::vector<int> data;
		void reset(int number){data.assign(number, -1);}
		int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
		bool join(int first, int sec){
			first=root(first); sec=root(sec);
			if(first==sec) return false;
			data[first]=sec;
			return true;
		}
	};
	Dsu dsu; dsu.reset((int)p.size());

	/*
	for(int first=0; first<(int)p.size(); ++first) if(p[first]!=first)
		for(int sec=0; sec<first; ++sec) if(p[sec]!=sec){
			auto const [p1, p2]=std::minmax({
				std::minmax({first, p[first]}),
					std::minmax({sec, p[sec]})
			});
			auto const [a, b]=p1; auto const [c, d]=p2;
			if(c<=b and b<=d){// partially intersect
				dsu.join(first, sec);
			}
		}
		*/

	struct Event{int id, pos;
		bool operator<(Event other) const{return pos<other.pos;}
	};
	std::vector<Event> events; events.reserve(p.size()*2);
	for(int index=0; index<(int)p.size(); ++index) if(index!=p[index]){
		auto const [a, b]=std::minmax({index, p[index]});
		dsu.join(a, b);
		events.push_back({index, a*2});
		events.push_back({index, b*2+1}); // sort open before close in pos
	}
	std::sort(begin(events), end(events));

	std::vector<int> depth(p.size(), -1); // in stack (-2: already popped)
	struct Item{
		int firstConnect; // stack[firstConnect]..=current item should be connected (or INT_MAX)
		int id;
	};
	std::vector<Item> stack;
	for(auto [id, _pos]: events){
		if(depth[id]<0){
			assert(depth[id]==-1);
			depth[id]=(int)stack.size();
			stack.push_back({INT_MAX, id});
		}else{
			auto const curDepth=depth[id];
			assert(stack[curDepth].id==id);
			if(stack[curDepth].firstConnect<curDepth){
				stack[curDepth-1].firstConnect=std::min(stack[curDepth-1].firstConnect,
						stack[curDepth].firstConnect);
				if(stack[curDepth-1].id>=0)
					dsu.join(stack[curDepth-1].id, id);
			}

			stack[curDepth].id=-1;
			bool const removeBack=curDepth==(int)stack.size()-1;
			depth[id]=-2;

			if(not removeBack){
				dsu.join(id, stack.back().id);
			}

			int minFirstConnect=curDepth;
			while(not stack.empty() and stack.back().id<0){
				assert(removeBack);
				assert(stack.back().id==-1);
				minFirstConnect=std::min(minFirstConnect, stack.back().firstConnect);
				stack.pop_back();
			}
			if(minFirstConnect<(int)stack.size()){
				stack.back().firstConnect=std::min(stack.back().firstConnect,
						minFirstConnect);
				dsu.join(id, stack.back().id);
			}
		}
	}

	assert(([&]{
	for(int first=0; first<(int)p.size(); ++first) if(p[first]!=first)
		for(int sec=0; sec<first; ++sec) if(p[sec]!=sec){
			auto const [p1, p2]=std::minmax({
				std::minmax({first, p[first]}),
					std::minmax({sec, p[sec]})
			});
			auto const [a, b]=p1; auto const [c, d]=p2;
			if(c<=b and b<=d){// partially intersect
				assert(dsu.root(first)==dsu.root(sec));
				//dsu.join(first, sec);
			}
		}
		return true;
	}()));

	std::vector<std::vector<int>> components(p.size());
	for(int index=0; index<(int)p.size(); ++index)
		if(p[index]!=index)
			components[dsu.root(index)].push_back(index);
	components.erase(std::remove_if(begin(components), end(components), [&](auto const& it){
		return it.empty();}), components.end());

	std::vector<int> left(p.size(), INT_MAX), right(p.size(), -1);
	for(auto const& it: components)
		for(auto item: it)
			left[item]=it[0], right[item]=it.back();

	int left_=std::min(s, left[s]), right_=std::max(s, right[s]);
	while(true){
		int left1=left_, cost1=0;
		while(left1>=0 and right[left1]<=right_){
			if(left[left1]<=left1)
				left1=left[left1];
			assert(left[left1]>=left1);
			++cost1;
			--left1;
		}

		int right2=right_, cost2=0;
		while(right2<(int)p.size() and left[right2]>=left_){
			if(right[right2]>=right2)
				right2=right[right2];
			assert(right[right2]<=right2);
			++cost2;
			++right2;
		}

		assert((left1>=0)==(right2<(int)p.size()));
		if(left1<0){
			break;
		}

		if(cost1<cost2){
			result+=cost1;
		}else{
			result+=cost2;
		}

		assert(left[left1]==left[right2]);
		assert(right[left1]==right[right2]);
		left_=left[left1]; right_=right[right2];

		assert(left[left_]>=left_);
		assert(right[right_]<=right_);
	}

	while(true){
		assert(left[left_]>=left_);
		int left1=left_;
		while(left1>=0 and left[left1]>=left1) --left1;
		if(left1<0) break;
		assert(right[left1]<left_);
		result+=left_-left1; left_=left[left1];
	}

	while(true){
		assert(right[right_]<=right_);
		int right2=right_;
		while(right2<(int)p.size() and right[right2]<=right2) ++right2;
		if(right2==(int)p.size()) break;
		assert(left[right2]>right_);
		result+=right2-right_; right_=right[right2];
	}

	return result*2;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30