oj.uz

Submission #241980

# Submission time Handle Problem Language Result Execution time Memory
241980 2020-06-26T13:11:45 Z lyc Shortcut (IOI16_shortcut) C++14
0 / 100
 5 ms 384 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) {
    array<ll,4> res = {-mxX,mxX,-mxX,mxX}, cur;
    FOR(J,1,N){
        ll mxs = -mxX, mne = mxX;
        FOR(I,1,J-1){
            if (D[I]+D[J]+(X[J]-X[I]) <= k) continue;
            mxs = max(mxs,X[I]-(k-C-D[I]));
            mne = min(mne,X[I]+(k-C-D[I]));
        }
        if (mxs > mne) return 0;
        ll a = mxs+D[J], b = mne-D[J];
        //TRACE(J _ a _ b);
        cur = {X[J]+a,X[J]+b,X[J]-b,X[J]-a};
        res[0] = max(res[0],cur[0]);
        res[1] = min(res[1],cur[1]);
        res[2] = max(res[2],cur[2]);
        res[3] = min(res[3],cur[3]);
        //TRACE(cur[0] _ cur[1] _ cur[2] _ cur[3]);
        //TRACE(res[0] _ res[1] _ res[2] _ res[3]);
        if (res[0] > res[1] || res[2] > res[3]) return 0;
    }
    return 1;
}

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];
        int tmp = D[i];
        if (tmp > mx) swap(tmp,mx);
        if (tmp > smx) swap(tmp,smx);
    }

    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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 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 4 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 5 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 4 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 Incorrect 5 ms 384 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -