oj.uz

Submission #284533

# Submission time Handle Problem Language Result Execution time Memory
284533 2020-08-27T15:04:11 Z user202729 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 256 KB 
// moreflags=grader.cpp
// 16
// what's wrong with me...
// the latest version is not proven rigorously.
#include "shortcut.h"
#include<vector>
#include<numeric>
#include<algorithm>
#include<cstdint>
#include<climits>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

struct T: std::array<int64_t, 2>{
};
// the code is starting to look messy.

struct Tree{ // BIT.
	std::vector<T> value;
	Tree(int number): value(number, {{INT64_MAX, INT64_MAX}}){}
	static T f(T first, T sec){
		std::transform(begin(first), end(first), sec.begin(), first.begin(),
				[&](int64_t first, int64_t sec){return std::min(first, sec);});
		return first;
	}
	T minSuffix(int pos) const{
		assert(pos>=0); // if pos is too large then INT64_MAX is returned
		T result; result.fill(INT64_MAX);
		while(pos<(int)value.size()){
			result=f(result, value[pos]);
			pos|=pos+1;
		}
		return result;
	}
	void setMinimum(int pos, T value_){
		do{
			value[pos]=f(value[pos], value_);
			pos&=pos+1; --pos;
		}while(pos>=0);
	}
};

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	std::vector<int64_t> pos; pos.reserve(n);
	pos.push_back(0);
	/*
	pos.insert(pos.end(), begin(l), end(l));
	std::partial_sum(++begin(pos), end(pos), ++pos.begin(), 0);
	*/
	std::inclusive_scan(begin(l), end(l), std::back_inserter(pos), std::plus<>(), (int64_t)0);

	int64_t result{};
	for(auto it: l) result+=it;
	result+=2**std::max_element(begin(d), end(d));
	l.clear();

	auto const check=[&](int64_t const result){
		auto const process=[&](std::array<int64_t, 4> initial)
			->std::array<int64_t, 4>{
			auto const c1=[&](int a){return d[a]-pos[a];};
			auto const c2=[&](int b){return +d[b]+pos[b];};

			enum class Type{query, set};
			struct Event{
				int64_t x; int y; Type type;
				//std::array<int64_t, 2> value;
			};
			std::vector<Event> events; events.reserve(n*2-1);

			for(int a=0; a<n; ++a){
				//auto const [x, y]=(std::array<int64_t, 2>)f1(a);
				//assert(x==x_); assert(y==y_);
				events.push_back({result-c1(a), a+1, Type::query});
			}
			for(int b=1; b<n; ++b){
				//auto const [x, y]=(std::array<int64_t, 2>)f2(b);
				events.push_back({c2(b), b, Type::set});
			}
			assert((int)events.size()==n*2-1);

			std::array<int64_t, 2> tree_{INT64_MAX, INT64_MAX};

			std::sort(begin(events), end(events),[&](Event first, Event sec){
				return first.x!=sec.x ? first.x>sec.x: first.type<sec.type;
			});
			for(auto const [_x, y, type]: events){
				if(type==Type::query){
					std::array<int64_t, 2> value{{-c2(y-1), -c1(y-1)}};
					for(int i=0; i<4; ++i)
						if(tree_[i>>1]!=INT64_MAX)
							initial[i]=std::min(initial[i], tree_[i>>1]+value[i&1]);
				}else{
					assert(type==Type::set);
					assert(_x==c2(y));
					tree_={{
						std::min(tree_[0], -c2(y)),
							std::min(tree_[1], -c1(y))
					}};
				}
			}

			return initial;
		};

		std::array<int64_t, 4> bounds=process(
				{{0, 0, INT64_MAX, INT64_MAX}}
				);
		std::swap(bounds[2], bounds[3]);
		std::swap(bounds[1], bounds[2]);

		if(bounds[1]==INT64_MAX) return true; // no bound. (result >=old diameter)
		for(auto& it: bounds) it+=result-c;
		bounds[0]=-bounds[0]; bounds[2]=-bounds[2]; // -minimum -> minimum
		if(bounds[0]>bounds[1] or bounds[2]>bounds[3]) return false;
		for(auto p: pos){
			auto const l=std::max(bounds[0]-p, bounds[2]+p), r=std::min(bounds[1]-p, bounds[3]+p);
			if(l<=r){
				auto const iterator=std::lower_bound(begin(pos), end(pos), l);
				if(iterator!=pos.end() and *iterator<=r)
					return true; // found a point
			}
		}
		return false;
	};

	for(int64_t step=(int64_t)1<<(63^__builtin_clzll(result)); step; step>>=1)
		if(result-step>0 and check(result-step))
			result-=step;
	return result;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 4, 80 is a correct answer
2 Correct 0 ms 256 KB n = 9, 110 is a correct answer
3 Correct 0 ms 256 KB n = 4, 21 is a correct answer
4 Correct 0 ms 256 KB n = 3, 4 is a correct answer
5 Correct 1 ms 256 KB n = 2, 62 is a correct answer
6 Correct 0 ms 256 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 256 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -