oj.uz

Submission #959231

# Submission time Handle Problem Language Result Execution time Memory
959231 2024-04-07T17:52:09 Z MinaRagy06 Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 14936 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "shortcut.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
 
const int N = 1'000'005;
const ll inf = 1e18;
ll prf[N], vals[N];
ll s[N], d[N];
array<ll, 3> vals2[N];
int n, c, order[N], l[N], a[N];
bool check(ll t) {
	ll l1 = -inf, r1 = inf, l2 = -inf, r2 = inf;
	int ptr = n;
	ll mxs[2] = {-inf, -inf}, mnd[2] = {inf, inf};
	for (int idx = 0; idx < n; idx++) {
		int i = order[idx];
		while (ptr > 0 && vals2[ptr][0] > t + prf[i] - a[i]) {
			mxs[1] = max(mxs[1], vals2[ptr][1]);
			if (mxs[0] < mxs[1]) swap(mxs[0], mxs[1]);
			mnd[1] = min(mnd[1], vals2[ptr][2]);
			if (mnd[0] > mnd[1]) swap(mnd[0], mnd[1]);
			ptr--;
		}
		ll sj = mxs[0], dj = mnd[0];
		if (prf[i] + a[i] > t + prf[i] - a[i]) {
			if (mxs[0] == s[i]) sj = mxs[1];
			if (mnd[0] == d[i]) dj = mnd[1];
		}
		l1 = max(l1, s[i] + sj - t + c);
		r1 = min(r1, d[i] + dj + t - c);
		l2 = max(l2, - d[i] + sj - t + c);
		r2 = min(r2, - s[i] + dj + t - c);
		if (l1 > r1 || l2 > r2) return false;
	}
	ptr = n;
	ll mn = 1e18;
	int lst = 0;
	for (int x = 1; x <= n; x++) {
		if (prf[x] > (l1 - l2) / 2) {
			break;
		}
		lst = x;
		while (ptr > 0 && l1 - vals[x] <= vals[ptr]) {
			mn = min(mn, vals[ptr]);
			ptr--;
		}
		if (mn <= min(r1 - vals[x], r2 + vals[x])) {
			return true;
		}
	}
	ptr = n, mn = 1e18;
	for (int x = n; x > lst; x--) {
		while (ptr > 0 && l2 + vals[x] <= vals[ptr]) {
			mn = min(mn, vals[ptr]);
			ptr--;
		}
		if (mn <= min(r1 - vals[x], r2 + vals[x])) {
			return true;
		}
	}
	return false;
}
ll find_shortcut(int _n, vector<int> _l, vector<int> _a, int _c) {
	n = _n, c = _c;
	for (int i = 1; i < n; i++) {
		l[i] = _l[i - 1];
		a[i] = _a[i - 1];
	}
	a[n] = _a[n - 1];
	l[n] = 0;
	prf[1] = 1;
	for (int i = 2; i <= n; i++) {
		prf[i] = prf[i - 1] + l[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		vals[i] = prf[i];
	}
	sort(vals + 1, vals + n + 1);
	for (int i = 1; i <= n; i++) {
		s[i] = prf[i] + a[i];
		d[i] = prf[i] - a[i];
	}
	for (int i = 1; i <= n; i++) {
		order[i - 1] = i;
	}
	sort(order, order + n, [&] (int x, int y) {return prf[x] + a[x] < prf[y] + a[y];});
	for (int i = 1; i <= n; i++) {
		vals2[i] = {prf[order[i - 1]] + a[order[i - 1]], s[order[i - 1]], d[order[i - 1]]};
	}
	sort(order, order + n, [&] (int x, int y) {return prf[x] - a[x] > prf[y] - a[y];});
	ll st = 0, en = 2e15;
	while (en - st > 6) {
		ll md1 = st + (en - st + 1) / 3, md2 = en - (en - st + 1) / 3;
		if (check(md1)) {
			en = md1;
		} else if (check(md2)) {
			st = md1 + 1;
          	en = md2;
		} else {
          	st = md2 + 1;
		}
	}
	for (int i = st; i <= en; i++) if (check(i)) return i;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB n = 4, 80 is a correct answer
2 Correct 3 ms 14680 KB n = 9, 110 is a correct answer
3 Correct 2 ms 14936 KB n = 4, 21 is a correct answer
4 Correct 2 ms 14680 KB n = 3, 4 is a correct answer
5 Correct 2 ms 14684 KB n = 2, 62 is a correct answer
6 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
7 Correct 2 ms 14684 KB n = 3, 29 is a correct answer
8 Correct 2 ms 14684 KB n = 2, 3 is a correct answer
9 Correct 3 ms 14684 KB n = 2, 3 is a correct answer
10 Correct 5 ms 14684 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2047 ms 14680 KB Time limit exceeded
12 Halted 0 ms 0 KB -