oj.uz

Submission #915254

# Submission time Handle Problem Language Result Execution time Memory
915254 2024-01-23T15:01:40 Z vjudge1 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 600 KB 
#include "shortcut.h"

#include <bits/stdc++.h>
using namespace std;

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
        vector<int64_t> a(n), b(n);  // a = x + d, b = x - d
        vector<int64_t> x(n);
        for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
        for (int i = 0; i < n; i++) a[i] = x[i] + d[i], b[i] = x[i] - d[i];

        // abs(x[i] - x[p]) + abs(x[j] - x[q]) + d[i] + d[j] + c <= target
        // x[i] - x[p] + x[j] - x[q] + d[i] + d[j] + c <= target
        // x[p] - x[i] + x[j] - x[q] + d[i] + d[j] + c <= target
        // x[i] - x[p] + x[q] - x[j] + d[i] + d[j] + c <= target
        // x[p] - x[i] + x[q] - x[j] + d[i] + d[j] + c <= target

        // x[p] + x[q] >= x[i] + x[j] + d[i] + d[j] + c - target
        // x[p] + x[q] <= x[i] + x[j] - d[i] - d[j] - c + target
        // x[q] - x[p] <= x[j] - x[i] - d[i] - d[j] - c + target
        // x[q] - x[p] >= x[j] - x[i] + d[i] + d[j] + c - target

        // k := c - target
        // x[p] + x[q] >= (x[i] + d[i]) + (x[j] + d[j]) + k
        // x[p] + x[q] <= (x[i] - d[i]) + (x[j] - d[j]) - k
        // x[q] - x[p] >= (x[j] + d[j]) - (x[i] + d[i]) + k
        // x[q] - x[p] <= (x[j] - d[j]) - (x[i] - d[i]) - k

        // x[p] + x[q] >= a[i] + a[j] + k
        // x[p] + x[q] <= b[i] + b[j] - k
        // x[q] - x[p] >= a[j] - a[i] + k
        // x[q] - x[p] <= b[j] - b[i] - k

        auto check = [&](int64_t target) {
                const int64_t k = c - target;
                int64_t low_sum = 0, high_sum = x.back() * 2;
                int64_t low_diff = 0, high_diff = x.back();
                for (int i = 0; i < n; i++) {
                        for (int j = i + 1; j < n; j++) {
                                if (x[j] - x[i] + d[i] + d[j] > target) {
                                        low_sum = max(low_sum, a[i] + a[j] + k);
                                        high_sum = min(high_sum, b[i] + b[j] - k);
                                        low_diff = max(low_diff, a[j] - a[i] + k);
                                        high_diff = min(high_diff, b[j] - b[i] - k);
                                }
                        }
                }
                if (low_sum > high_sum) return 0;
                if (low_diff > high_diff) return 0;
                // low_sum <= x[p] + x[q] <= high_sum
                // low_diff <= x[q] - x[p] <= high_diff
                for (int p = 0; p < n; p++) {
                        for (int q = p + 1; q < n; q++) {
                                if (low_sum <= x[p] + x[q] && x[p] + x[q] <= high_sum &&
                                    low_diff <= x[q] - x[p] && x[q] - x[p] <= high_diff) {
                                        return 1;
                                }
                        }
                }
                return 0;
        };

        int64_t low = 0, high = 1ll << 60;
        while (low < high) {
                int64_t mid = low + high >> 1;
                if (check(mid)) {
                        high = mid;
                } else {
                        low = mid + 1;
                }
        }
        return high;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:65:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |                 int64_t mid = low + high >> 1;
      |                               ~~~~^~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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