oj.uz

Submission #937195

# Submission time Handle Problem Language Result Execution time Memory
937195 2024-03-03T15:43:36 Z ThegeekKnight16 Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 348 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

bool Teste(int diam, int n, vector<int> &l, vector<int> &d, ll c, vector<ll> &dist)
{
    // cerr << "diam: " << diam << '\n';
    vector<pair<int, int>> badPairs;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if ((ll)d[i] + (ll)d[j] + dist[j] - dist[i] > diam)
                badPairs.emplace_back(i, j);

    for (int x = 0; x < n; x++)
    {
        // cerr << "\t now testing x = " << x << '\n';
        vector<ll> maxDist(n, INF);
        for (auto [i, j] : badPairs) maxDist[j] = min(maxDist[j], diam - c - (abs(dist[x] - dist[i]) + (ll)d[i] + (ll)d[j]));

        int ini = x+1, fim = n-1;
        while (ini <= fim)
        {
            int y = (ini + fim) >> 1;
            bool erradoEsq = 0, erradoDir = 0;
            for (int j = 0; j <= y; j++) if (dist[y] - dist[j] > maxDist[j]) {erradoEsq = 1; break;}
            for (int j = y+1; j < n; j++) if (dist[j] - dist[y] > maxDist[j]) {erradoDir = 1; break;}
            // cerr << "\t\tfor y = " << y << ", we have esq = " << erradoEsq << " , dir = " << erradoDir << '\n';
            if (ini == fim)
            {
                if (erradoEsq || erradoDir) break;
                return 1;
            }
            if (erradoDir && erradoEsq) break;
            if (erradoEsq) {fim = y-1; continue;}
            if (erradoDir) {ini = y+1; continue;}
            return 1;
        }
    }

    return 0;
}

ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    vector<ll> dist(n);
    for (int i = 1; i < n; i++) dist[i] = dist[i-1] + l[i-1];

    ll ini = c, fim = INF;
    while (ini < fim)
    {
        int m = (ini +  fim) >> 1;
        if (Teste(m, n, l, d, c, dist)) fim = m;
        else ini = m+1;
    }
    return fim;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 344 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 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 Execution timed out 2053 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -