oj.uz

Submission #71635

# Submission time Handle Problem Language Result Execution time Memory
71635 2018-08-25T09:25:01 Z gnoor Shortcut (IOI16_shortcut) C++17
0 / 100
 3 ms 524 KB 
#include "shortcut.h"

#include <vector>
#include <algorithm>

using namespace std;

vector<long long> qs;
vector<int> d;

vector<int> posj; //sort by qs[j]+d[j]
vector<int> posi; //sort by qs[i]-d[i]

bool work(long long k,long long c) {
	long long lft=-1e18;
	long long rgt=1e18;
	long long top=1e18;
	long long bot=-1e18;
	
	int n=(int)qs.size();

	int _i=0;
	for (int _j=0;_j<n;_j++) {
		int j=posj[_j];
		while (_i<n&&qs[j]-qs[posi[_i]]+d[j]+d[posi[_i]]>k) {
			int i=posi[_i];
			lft=max(lft,(qs[i]+d[i])-(qs[j]-d[j])-k+c);
			rgt=min(rgt,(qs[i]-d[i])-(qs[j]+d[j])+k-c);
			top=min(top,(qs[i]-d[i])+(qs[j]-d[j])+k-c);
			bot=max(bot,(qs[i]+d[i])+(qs[j]+d[j])-k+c);
			_i++;
		}
	}

	if (lft>rgt||bot>top) return false;
	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 (lft<=x&&x<=rgt&&bot<=y&&y<=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-1];
		qs[i]+=qs[i-1];
	}
	::d=d;

	posj.resize(n,0);
	posi.resize(n,0);
	for (int i=0;i<n;i++) {
		posi[i]=i;
		posj[i]=i;
	}

	sort(posj.begin(),posj.end(),[&](const int &a, const int &b) {
			return qs[a]+d[a]<qs[b]+d[b];
			});
	sort(posi.begin(),posi.end(),[&](const int &a, const int &b) {
			return qs[a]-d[a]<qs[b]-d[b];
			});
	

	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 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 408 KB n = 4, 21 is a correct answer
4 Correct 2 ms 456 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 524 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -