oj.uz

Submission #502885

# Submission time Handle Problem Language Result Execution time Memory
502885 2022-01-06T17:29:18 Z doowey Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 204 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e6 + 10;

int n;
ll X[N];
vector<ll> W;
ll L;
vector<pii> A,B;

bool check(ll k){
    ll mx = 0;
    for(int i = 0 ; i < n; i ++ ){
        if(W[i] + mx > k) return false;
        mx = max(mx, W[i]);
    }
    ll lowplus = -(ll)1e18;
    ll highplus = (ll)1e18;
    ll lowminus = -(ll)1e18;
    ll highminus = (ll)1e18;
    for(int i = 0 ; i < n; i ++ ){
        for(int j = 0; j < n; j ++ ){
            if(X[j] + W[j] - X[i] + W[i] <= k) continue; // no one cares
            lowplus = max(lowplus, -k + X[i] + X[j] + L + W[i] + W[j]);
            highplus = min(highplus, k + X[i] + X[j] - L - W[i] - W[j]);
            lowminus = max(lowminus, -k + X[i] - X[j] + L + W[i] + W[j]);
            highminus = min(highminus, k + X[i] - X[j] - L - W[i] - W[j]);
        }
    }
    int i0 = n - 1, j0 = n - 1;
    int i1 = 0, j1 = 0;
    int tl, tr;
    for(int i = 0 ; i < n; i ++ ){
        while(i0 >= 0 && X[i] + X[i0] > highplus){
            i0 -- ;
        }
        while(j0 > 0 && X[i] + X[j0 - 1] >= lowplus){
            j0 -- ;
        }
        while(i1 < n && X[i] - X[i1] > highminus){
            i1 ++ ;
        }
        while(j1 + 1 < n && X[i] - X[j1 + 1] >= lowminus){
            j1 ++ ;
        }
        tl = i + 1;
        tr = n - 1;
        tl = max(tl, j0);
        tr = min(tr, i0);
        tl = max(tl, i1);
        tr = min(tr, j1);
        if(tl <= tr){
            return true;
        }
    }
    return false;

}

ll find_shortcut(int _n, vector<int> l, vector<int> _d, int _c){
    n = _n;
    for(int i = 1; i < n; i ++ ){
        X[i] = X[i - 1] + l[i - 1];
    }
    for(auto x : _d)
        W.push_back(x);
    L = _c;
    ll li = 0;
    ll ri = (ll)1e16;
    ll mid;
    while(li < ri){
        mid = (li + ri) / 2;
        if(check(mid)){
            ri = mid;
        }
        else{
            li = mid + 1;
        }
    }
    return li;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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