oj.uz

Submission #33929

# Submission time Handle Problem Language Result Execution time Memory
33929 2017-11-05T08:48:14 Z imeimi2000 Shortcut (IOI16_shortcut) C++14
0 / 100
 0 ms 1932 KB 
#include "shortcut.h"
#include <algorithm>

using namespace std;
typedef long long llong;

int n, c;
vector<llong> dist;
vector<int> etc;
vector<pair<llong, int>> ad, sb;

bool check(llong m) {
	llong fs = 0ll, se = 0ll;
	int mxi = -1, sei = -1, p;
	llong lad = -1e18, gad = 1e18, lsb = -1e18, gsb = 1e18;
	for (int i = 0, j = 0; i < n; ++i) {
		while (j < m && sb[j].first + m < ad[i].first) {
			p = sb[j].second;
			llong mx = dist[p] + etc[p];
			if (fs < mx) {
				sei = mxi;
				mxi = p;
				se = fs;
				fs = mx;
			}
			else if (se < mx) sei = p, se = mx;
			++j;
		}
		p = (ad[i].second == mxi ? sei : mxi);
		if (p == -1) continue;
		llong adi = (ad[i].second == mxi ? se : fs);
		llong sbi = (ad[i].second == sb[0].second ? sb[1].first : sb[0].first);
		p = ad[i].second;
		llong adj = ad[i].first;
		llong sbj = dist[p] - etc[p];
		lsb = max(lsb, adi - sbj - m + c);
		gsb = min(gsb, sbi - adj + m - c);
		lad = max(lad, adi + adj - m + c);
		gad = min(gad, sbi + sbj + m - c);
	}
	llong gpos = -1e18, lpos = 1e18;
	for (int i = 0; i < n; ++i) {
		if (lpos <= dist[i] && dist[i] <= gpos) return true;
		gpos = max(gpos, min(dist[i] - lsb, gad - dist[i]));
		lpos = min(lpos, max(dist[i] - gsb, lad - dist[i]));
	}
	return false;
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C) {
	n = N; c = C;
	dist.resize(n);
	llong sum = 0ll;
	for (int i = 1; i < n; ++i) {
		sum += l[i - 1];
		dist[i] = sum;
	}
	etc = d;
	llong ld = 0ll, e = 0ll;
	int fs = 0, se = 0;
	for (int i = 0; i < n; ++i) {
		ad.push_back({ dist[i] + etc[i], i });
		sb.push_back({ dist[i] - etc[i], i });

		e = max(e, ld + etc[i]);

		if (fs < etc[i]) {
			se = fs;
			fs = etc[i];
		}
		else if (se < etc[i]) {
			se = etc[i];
		}

		if (i < n - 1)
			ld = max(ld, (llong)etc[i]) + l[i];
	}
	sort(ad.begin(), ad.end());
	sort(sb.begin(), sb.end());

	llong s = fs + se;
	while (s < e) {
		llong m = (s + e) / 2;
		if (check(m)) e = m;
		else s = m + 1ll;
	}
	return s;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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