10076 2024. 03. 26 12:37:22 Error42 Hadjárat cpp17 Elfogadva 100/100 119ms 8004 KiB
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct city {
    int id, x, y, from;
};

struct hull {
    map<int, city> h;

    hull(city const& n) {
        h[n.x] = n;
    }

    bool inside(city const& n) const {
        auto it = h.lower_bound(n.x);

        if (it == h.begin())
            return false;

        --it;

        return n.y > it->second.y;
    }

    city inside_of(city const& n) const {
        auto it = h.lower_bound(n.x);

        --it;

        return it->second;
    }

    bool outside(city const& n) const {
        auto it = h.upper_bound(n.x);

        if (it == h.begin())
            return true;

        --it;

        if (it->second.x == n.x)
            return false;

        return n.y < it->second.y;
    }

    void insert(city const& n) {
        if (!outside(n))
            return;

        h[n.x] = n;

        auto it = h.find(n.x);

        while (it != h.begin()) {
            auto before = it;
            --before;

            assert(before->second.y != it->second.y);

            if (before->second.y < it->second.y)
                h.erase(before);
            else
                break;
        }

        while (true) {
            auto after = it;
            ++after;

            if (after == h.end())
                break;

            if (after->second.y >= it->second.y)
                h.erase(after);
            else
                break;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<city> cities(n);
    for (int i = 0; i < n; i++) {
        cities[i].id = i;
        cin >> cities[i].x >> cities[i].y;
        cities[i].from = -2;
    }

    vector<hull> lis;

    for (int i = 0; i < n; i++) {
        int const insert = lower_bound(lis.begin(), lis.end(), cities[i], [&](hull const& h, city const& c) {
            return h.inside(c);
        }) - lis.begin();

        if (insert == 0)
            cities[i].from = -1;
        else
            cities[i].from = lis[insert - 1].inside_of(cities[i]).id;

        if (insert == lis.size())
            lis.push_back({ cities[i] });
        else
            lis[insert].insert(cities[i]);
    }

    cout << lis.size() << "\n";

    vector<int> sol;

    int cur = lis.back().h.begin()->second.id;

    while (cur != -1) {
        sol.push_back(cur);
        cur = cities[cur].from;
    }

    reverse(sol.begin(), sol.end());

    for (int const& x : sol)
        cout << x + 1 << " ";
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1956 KiB
2 Elfogadva 0/0 54ms 4032 KiB
3 Elfogadva 4/4 3ms 2588 KiB
4 Elfogadva 4/4 3ms 2556 KiB
5 Elfogadva 4/4 3ms 2692 KiB
6 Elfogadva 4/4 3ms 2772 KiB
7 Elfogadva 4/4 3ms 2952 KiB
8 Elfogadva 4/4 3ms 3048 KiB
9 Elfogadva 4/4 3ms 3140 KiB
10 Elfogadva 4/4 3ms 3148 KiB
11 Elfogadva 4/4 7ms 3496 KiB
12 Elfogadva 4/4 10ms 3760 KiB
13 Elfogadva 6/6 10ms 3844 KiB
14 Elfogadva 6/6 20ms 4456 KiB
15 Elfogadva 6/6 32ms 5060 KiB
16 Elfogadva 6/6 54ms 5916 KiB
17 Elfogadva 6/6 68ms 6432 KiB
18 Elfogadva 6/6 79ms 6564 KiB
19 Elfogadva 6/6 93ms 7168 KiB
20 Elfogadva 6/6 119ms 7840 KiB
21 Elfogadva 6/6 119ms 7876 KiB
22 Elfogadva 6/6 119ms 8004 KiB