oj.uz

답안 #288541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288541 2020-09-01T15:40:02 Z user202729 고대 책들 (IOI17_books) C++17
12 / 100
 1 ms 384 KB 
// moreflags=grader.cpp
// 11
// late
// that stack...

#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]});
		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);
		}
	}


	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.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338574'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338574'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3344'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338574'
20 Halted 0 ms 0 KB -