Submission #937202

#	Time	Username	Problem	Language	Result	Execution time	Memory
937202		ThegeekKnight16	Shortcut (IOI16_shortcut)	C++17	38 / 100	2015 ms	26352 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

bool Teste(ll 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;}
            // cerr << "\t\tfor y = " << y << ", esq = " << erradoEsq << ", dir = " << erradoDir << '\n';

            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;}
        // cerr << "\t\tfor y = " << fim << ", esq = " << erradoEsq << ", dir = " << erradoDir << '\n';

        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 resp = d[0], diam = d[0];
    for (int i = 1; i < n; i++)
    {
        resp = max(resp, diam + (ll)l[i-1] + (ll)d[i]);
        diam = max(diam + (ll)l[i-1], (ll)d[i]);
    }

    ll ini = c, fim = (ll)resp;
    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: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3