oj.uz

Submission #242024

# Submission time Handle Problem Language Result Execution time Memory
242024 2020-06-26T14:41:56 Z lyc Shortcut (IOI16_shortcut) C++14
0 / 100
 6 ms 436 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using ll=long long;

const int mxN = 1e6+5;
const ll mxX = 1e17;

int N, C, D[mxN];
ll X[mxN];
int id1[mxN], id2[mxN];

bool check(ll k) {
    int i = 1;
    ll b[] = { -mxX, mxX, -mxX, mxX };  // min/max y+z, min/max y-z
    ll v[] = { -mxX, -mxX, mxX, mxX };  // max X[I]+D[i], min X[I]-D[I]
    int s[] = { -1, -1, -1, -1 };       // ids for v
    FOR(j,1,N){
        int I = id1[i], J = id2[j];
        while (i <= N && (X[J]+D[J])-(X[I]-D[I]) > k) {
            if (X[I]+D[I] > v[0]) v[0] = X[I]+D[I], s[0] = I;
            if (v[0] > v[1]) swap(v[0],v[1]), swap(s[0],s[1]);
            if (X[I]-D[I] < v[2]) v[2] = X[I]-D[I], s[2] = I;
            if (v[2] < v[3]) swap(v[2],v[3]), swap(s[2],s[3]);
            b[0] = max(b[0], -k+C+(X[J]+D[J])+(J==s[1]?v[0]:v[1]));
            b[1] = min(b[1],  k-C+(X[J]-D[J])+(J==s[3]?v[2]:v[3]));
            b[2] = max(b[2], -k+C-(X[J]-D[J])+(J==s[1]?v[0]:v[1]));
            b[3] = min(b[3],  k-C-(X[J]+D[J])+(J==s[3]?v[2]:v[3]));
            I = id1[++i];
        }
    }
    int l = 1, r = 0; // move only O(N) times
    FOR(i,1,N){
        while (l > 1 && X[l-1] >= max(b[0]-X[i],b[2]+X[i])) --l;
        while (r < N && X[r+1] <= min(b[1]-X[i],b[3]+X[i])) ++r;
        while (l <= N && X[l] < max(b[0]-X[i],b[2]+X[i])) ++l;
        while (r >= 1 && X[r] > min(b[1]-X[i],b[3]+X[i])) --r;
        if (l <= r) return 1; // found a shortcut
    }
    return 0;
}

ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    N = n, C = c;
    X[1] = 0;
    FOR(i,2,N) X[i] = X[i-1] + l[i-2];
    int mx = 0, smx = 0;
    FOR(i,1,N){
        D[i] = d[i-1];
        if (D[i] > smx) smx = D[i];
        if (smx > mx) swap(smx,mx);
    }

    FOR(i,1,N) id1[i] = id2[i] = i;
    sort(id1+1,id1+1+N,[](int a, int b){
            ll p = X[a]-D[a], q = X[b]-D[b];
            return (p == q ? a < b : p < q);
            });
    sort(id2+1,id2+1+N,[](int a, int b){
            ll p = X[a]+D[a], q = X[b]+D[b];
            return (p == q ? a < b : p < q);
            });
    ll lo = mx+smx-1, hi = mxX;
    while (hi-lo > 1){ 
        ll mid = (lo+hi)/2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    return hi;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 6 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 5 ms 384 KB n = 3, 29 is a correct answer
8 Correct 5 ms 384 KB n = 2, 3 is a correct answer
9 Correct 5 ms 384 KB n = 2, 3 is a correct answer
10 Correct 5 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 5 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 5 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 436 KB n = 10, 1000000343 is a correct answer
18 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 2971
19 Halted 0 ms 0 KB -