oj.uz

Submission #71568

# Submission time Handle Problem Language Result Execution time Memory
71568 2018-08-25T07:21:30 Z gnoor Shortcut (IOI16_shortcut) C++17
0 / 100
 3 ms 492 KB 
#include "shortcut.h"

#include <vector>
#include <algorithm>

using namespace std;

struct rect {
	long long lft,top,rgt,bot;

	rect():lft(-1e18),top(1e18),rgt(1e18),bot(-1e18) {}
	rect(long long _lft,long long _top,long long _rgt,long long _bot):lft(_lft),top(_top),rgt(_rgt),bot(_bot) {}
};

rect comb(const rect &a, const rect &b) {
	return rect(max(a.lft,b.lft),min(a.top,b.top),min(a.rgt,b.rgt),max(a.bot,b.bot));
}

struct inter {
	long long a,b,c;

	rect eval(long long k) const {
		long long z=k-c;
		return rect(a-b-z,a+b+z,a-b+z,a+b-z);
	}
};


vector<long long> qs;
vector<inter> inters;

bool work(long long k,long long cost) {
	rect cur;
	for (auto &i:inters) {
		if (i.c-cost+i.b-i.a<=k) continue;
		cur=comb(cur,i.eval(k));
	}
	if (cur.lft>cur.rgt||cur.bot>cur.top) return false;
	int n=(int)qs.size();
	long long x,y;
	for (int i=0;i<n;i++) {
		for (int j=i+1;j<n;j++) {
			x=qs[i]-qs[j];
			y=qs[i]+qs[j];
			if (cur.lft<=x&&x<=cur.rgt&&cur.bot<=y&&y<=cur.top) return true;
		}
	}
	return false;
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
	qs.resize(n,0);
	for (int i=1;i<n;i++) {
		qs[i]=l[i];
		qs[i]+=qs[i-1];
	}
	inters.reserve(n*(n-1)/2);
	for (int i=0;i<n;i++) {
		for (int j=i+1;j<n;j++) {
			inters.push_back(inter{qs[i],qs[j],d[i]+d[j]+c});
		}
	}
	long long lo=0;
	long long hi=1e15;
	long long mid;
	while (lo<hi) {
		mid=(lo+hi)>>1;
		if (work(mid,c)) {
			hi=mid;
		} else {
			lo=mid+1;
		}
	}
	return lo;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 3 ms 492 KB n = 9, 110 is a correct answer
3 Correct 2 ms 492 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 492 KB n = 3, incorrect answer: jury 4 vs contestant 3