oj.uz

Submission #937197

# Submission time Handle Problem Language Result Execution time Memory
937197 2024-03-03T15:47:26 Z ThegeekKnight16 Shortcut (IOI16_shortcut) C++17
0 / 100
 0 ms 344 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-1; 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;}

            if (erradoDir && erradoEsq) break;
            if (erradoEsq) {fim = y; continue;}
            if (erradoDir) {ini = y+1; continue;}
            return 1;
        }

        bool erradoEsq = 0, erradoDir = 0;
        for (int j = 0; j <= fim; j++) if (dist[fim] - dist[j] > maxDist[j]) {erradoEsq = 1; break;}
        for (int j = fim+1; j < n; j++) if (dist[j] - dist[fim] > maxDist[j]) {erradoDir = 1; break;}
        if (!erradoDir && !erradoEsq) 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)
    {
        ll m = (ini +  fim) >> 1LL;
        if (Teste(m, n, l, d, c, dist)) fim = m;
        else ini = m+1LL;
    }
    return fim;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 3038287258491813968
2 Halted 0 ms 0 KB -