10075 2024. 03. 26 12:34:32 Error42 Hadjárat cpp17 Futási hiba 24/100 50ms 15572 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;

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

            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 24/100
1 Elfogadva 0/0 3ms 1956 KiB
2 Futási hiba 0/0 17ms 4488 KiB
3 Elfogadva 4/4 3ms 2808 KiB
4 Elfogadva 4/4 3ms 3032 KiB
5 Elfogadva 4/4 3ms 3248 KiB
6 Elfogadva 4/4 3ms 3536 KiB
7 Elfogadva 4/4 3ms 3516 KiB
8 Futási hiba 0/4 3ms 3612 KiB
9 Futási hiba 0/4 3ms 3796 KiB
10 Elfogadva 4/4 3ms 3836 KiB
11 Futási hiba 0/4 6ms 4108 KiB
12 Futási hiba 0/4 7ms 4372 KiB
13 Futási hiba 0/6 4ms 4604 KiB
14 Futási hiba 0/6 7ms 5184 KiB
15 Futási hiba 0/6 9ms 5760 KiB
16 Futási hiba 0/6 16ms 7076 KiB
17 Futási hiba 0/6 23ms 8220 KiB
18 Futási hiba 0/6 37ms 9744 KiB
19 Futási hiba 0/6 35ms 11144 KiB
20 Futási hiba 0/6 50ms 13216 KiB
21 Futási hiba 0/6 37ms 14212 KiB
22 Futási hiba 0/6 39ms 15572 KiB