Submission #288559

#	Time	Username	Problem	Language	Result	Execution time	Memory
288559		user202729	Ancient Books (IOI17_books)	C++17	100 / 100	582 ms	40148 KiB

books

// moreflags=grader.cpp
// 11
// a little faster.

#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());

	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(int pos=0; pos<(int)p.size(); ++pos) if(pos!=p[pos]){
		dsu.join(pos, p[pos]);
		for(auto id: {pos, p[pos]}){
			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);
				}
			}
		}
	}

	std::vector<std::array<int, 2>> rootBound(p.size(), {{INT_MAX, INT_MIN}});
	for(int index=0; index<(int)p.size(); ++index){
		auto const t=dsu.root(index);
		rootBound[t]={{
			std::min(rootBound[t][0], index),
				std::max(rootBound[t][1], index)
		}};
	}

	std::vector<int> left(p.size(), INT_MAX), right(p.size(), -1);
	for(int index=0; index<(int)p.size(); ++index) if(p[index]!=index){
		auto const t=dsu.root(index);
		left[index]=rootBound[t][0];
		right[index]=rootBound[t][1];
	}

	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