oj.uz

Submission #288140

# Submission time Handle Problem Language Result Execution time Memory
288140 2020-09-01T09:02:37 Z user202729 Ancient Books (IOI17_books) C++17
0 / 100
 8 ms 2040 KB 
// moreflags=grader.cpp
// 11
// ???
#include "books.h"
#include<algorithm>
#include<numeric>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>


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;
		}
	};
	struct Edge{int first, sec, value;
		bool operator<(Edge other) const{return value<other.value;}
	};
	std::vector<Edge> edges;
	for(int first=0; first<(int)p.size(); ++first) if(first==s or p[first]!=first)
		for(int sec=0; sec<first; ++sec) if(sec==s or 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;
			edges.push_back({first, sec,
				b<=c ? c-b:
					d<=b ? std::min(b-d, c-a): 0
			});
		}

	std::sort(begin(edges), end(edges));
	Dsu dsu; dsu.reset((int)p.size());
	for(auto [first, sec, value]: edges)
		if(dsu.join(first, sec)) result+=value;

	return result*2;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory 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 Incorrect 0 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory 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 Incorrect 0 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory 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 Incorrect 0 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2040 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4042'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory 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 Incorrect 0 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -