oj.uz

Submission #288257

# Submission time Handle Problem Language Result Execution time Memory
288257 2020-09-01T11:02:39 Z user202729 Ancient Books (IOI17_books) C++17
42 / 100
 158 ms 14840 KB 
// moreflags=grader.cpp
// 11
// as usual, "I should have proven the solution before implementing"
// (and "I should not keep generating random test cases"?)

#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(std::is_permutation(begin(p), end(p)));
	assert(s>=0); assert(s<(int)p.size());
	if(p.size()>1000) return -1;

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

	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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 304 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 1 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 304 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 1 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 304 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 1 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Incorrect 158 ms 14840 KB 3rd lines differ - on the 1st token, expected: '333035179244', found: '-1'
31 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 304 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 1 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Incorrect 158 ms 14840 KB 3rd lines differ - on the 1st token, expected: '333035179244', found: '-1'
31 Halted 0 ms 0 KB -