oj.uz

Submission #805845

# Submission time Handle Problem Language Result Execution time Memory
805845 2023-08-04T01:02:08 Z resting Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 296 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll inf = 1e18;
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];

    vector<int> distl(n, 0), distr(n, 0);
    int cur = 0;
    for (int i = 0; i < n; i++) {
        distl[i] = cur + d[i];
        if (i) distl[i] = max(distl[i], distl[i - 1]);
        cur = max(cur, d[i]);
        if (i + 1 < n)
            cur += l[i];
    }
    cur = 0;
    for (int i = n - 1; i >= 0; i--) {
        distr[i] = cur + d[i];
        if (i != n - 1) distr[i] = max(distr[i], distr[i + 1]);
        cur = max(cur, d[i]);
        if (i)
            cur += l[i - 1];
    }

    int mxmn = 0;
    for (int i = 0; i < n; i++) {
        mxmn = max(mxmn, min(distl[i], distr[i]));
    }

    vector<pair<int, int>> partl, partr; //partition left, right
    int mid = 0;
    for (int i = 0; i < n; i++) {
        if (distl[i] == mxmn) {
            partl.push_back({ d[i], i });
            mid = p[i];
            break;
        }

        if (distr[i] == mxmn) {
            partr.push_back({ d[i], i });
            mid = p[i];
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        if (p[i] < mid) partl.push_back({ mid - p[i] + d[i], i });
        if (p[i] > mid) partr.push_back({ p[i] - mid + d[i], i });
    }

    sort(partl.begin(), partl.end());
    sort(partr.begin(), partr.end());



    ll left = mxmn - 1, right = 3e9 + 5;
    while (right - left > 1) {
        ll mid = (left + right) / 2;
        ll x1 = -inf, x2 = inf, y1 = -inf, y2 = inf;


        ll rangl = -1e9, rangr = 1e9;
        int cur = partr.size() - 1;
        for (int i = 0; i < partl.size(); i++) {
            while (cur >= 0 && partr[cur].first + partl[i].first > mid) {
                rangl = max(rangl, (ll)p[partr[cur].second] - (mid - c - d[partr[cur].second]));
                rangr = min(rangr, (ll)p[partr[cur].second] + (mid - c - d[partr[cur].second]));
                cur--;
            }

            // {p[i], rangl}, {p[i], rangr}
            //rangr > rangl
            //(x, y) -> (x + y, x - y)
            rangl += d[i]; rangr -= d[i];
            x1 = max(x1, p[i] + rangl);
            x2 = min(x2, p[i] + rangr);
            y1 = max(y1, p[i] - rangr);
            y2 = min(y2, p[i] - rangl);
            rangl -= d[i]; rangr += d[i];
        }
        if (x1 <= x2 && y1 <= y2) right = mid;
        else left = mid;
    }
    return right;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < partl.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 296 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 296 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 1 ms 212 KB n = 2, 3 is a correct answer
9 Correct 1 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 1000000000
11 Halted 0 ms 0 KB -