# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
151685 |
2019-09-04T06:42:16 Z |
tri |
Shortcut (IOI16_shortcut) |
C++14 |
|
2 ms |
376 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
const ll INF = 1e16;
int N;
vl x;
vi d;
ll C;
vector<pl> order, process;
namespace debug {
const int DEBUG = false;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"), cout << flush; }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
bool binSearch(ll K) {
ll P = -INF;
ll Q = INF;
ll R = -INF;
ll S = INF;
ll maxP = -INF;
ll minM = INF;
int nP = 0;
for (pl cI: order) {
ll cP = x[cI.s] + d[cI.s];
ll cM = x[cI.s] - d[cI.s];
while (nP < N && cI.f - K > process[nP].f) {
int pI = process[nP].s;
// ps("added", cI.s, pI);
maxP = max(maxP, x[pI] + d[pI]);
minM = min(minM, x[pI] - d[pI]);
nP++;
}
// ps(maxP, minM);
P = max(P, cP + maxP + C - K);
Q = min(Q, cM + minM - C + K);
R = max(R, cP - minM + C - K);
S = min(S, cM - maxP - C + K);
}
// ps("PQRS", P, Q, R, S);
int bPt = 0;
for (int i = 0; i < N; i++) {
ll aBnd = min(Q - x[i], x[i] - R);
ll bBnd = max(P - x[i], x[i] - S);
while (bPt + 1 < N && x[bPt + 1] < bBnd) {
bPt++;
}
while (bPt >= 0 && x[bPt] >= bBnd) {
bPt--;
}
// ps("in", aBnd, bBnd, bPt);
if (bPt + 1 < N && x[bPt + 1] <= aBnd) {
// ps(i, bPt);
return true;
}
}
return false;
}
ll find_shortcut(int iN, vi len, vi iD, int iC) {
N = iN;
x.resize(N, 0);
d = iD;
C = iC;
x[0] = 0;
for (int i = 0; i < N - 1; i++) {
x[i + 1] = x[i] + len[i];
}
for (int i = 0; i < N; i++) {
order.pb({x[i] + d[i], i});
process.pb({x[i] - d[i], i});
}
sort(order.begin(), order.end());
sort(process.begin(), process.end());
ll lo = 0;
ll hi = INF;
// ps(x);
// ps(C);
// ps(binSearch(4));
// ps("finnnnnnnnnn");
while (lo != hi) {
ll mid = (lo + hi) / 2;
if (binSearch(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
292 KB |
n = 3, 4 is a correct answer |
5 |
Incorrect |
2 ms |
376 KB |
n = 2, incorrect answer: jury 62 vs contestant 72 |
6 |
Halted |
0 ms |
0 KB |
- |