Submission #865782

#	Time	Username	Problem	Language	Result	Execution time	Memory
865782		boris_mihov	Roads (CEOI20_roads)	C++17	15 / 100	42 ms	14532 KiB

roads

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;

int n;
struct Point
{
    llong x, y;
    friend bool operator < (const Point &a, const Point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};

llong size(Point a, Point b, Point c)
{
    return a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.x * c.y - a.y * b.x;
}

struct Line
{
    Point from;
    Point to;
    int idx;

    friend bool operator < (const Line &a, const Line &b)
    {
        // std::cout << "compare: " << a./
        if ((size(a.from, a.to, b.from) < 0) == (size(a.from, a.to, b.to) < 0))
        {
            return size(a.from, a.to, b.from) < 0;
        }

        return size(b.from, b.to, a.from) > 0;
    }
};

Line lines[MAXN];
std::set <Line> s;

struct Event
{
    Point p;
    int idx;
    char type;

    friend bool operator < (const Event &a, const Event &b)
    {
        return a.p < b.p;
    }
};

int maxEndAbove[MAXN];
int maxEndBelow[MAXN];
std::mt19937 rng(69420);
std::vector <Event> events;
std::vector <Line> answer;

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        lines[i].idx = i;
        if (lines[i].to < lines[i].from)
        {
            std::swap(lines[i].from, lines[i].to);
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        events.push_back({lines[i].from, i, '+'});
        events.push_back({lines[i].to, i, '-'});
    }

    int last = -1;
    std::sort(events.begin(), events.end());
    for (const auto &[p, idx, type] : events)
    {
        if (type == '+')
        {
            if (s.size())
            {
                bool matched = false;
                auto it = s.lower_bound(lines[idx]);
                auto it1 = it;
                if (it != s.end())
                {  
                    if (maxEndAbove[it->idx] != 0)
                    {
                        matched = true;
                        answer.push_back({lines[maxEndAbove[it->idx]].to, lines[idx].from});
                    }
                }

                if (it != s.begin())
                {
                    it--;
                    if (!matched && maxEndBelow[it->idx] != 0)
                    {
                        matched = true;
                        answer.push_back({lines[maxEndBelow[it->idx]].to, lines[idx].from});
                    }
                } 

                if (!matched)
                {
                    if (it1 == s.end() || it1 == s.begin()) answer.push_back({lines[it->idx].from, lines[idx].from});
                    else
                    {
                        it = std::prev(it1);
                        if (lines[it->idx].from.x > lines[it1->idx].from.x) answer.push_back({lines[it->idx].from, lines[idx].from});
                        else answer.push_back({lines[it1->idx].from, lines[idx].from});
                    }
                }
            } else
            {
                if (last != -1)
                {
                    answer.push_back({lines[last].to, lines[idx].from});
                }
            }

            s.insert(lines[idx]);
        } else
        {
            auto it = s.find(lines[idx]);
            assert(it != s.end());

            if (std::next(it) != s.end())
            {
                maxEndAbove[std::next(it)->idx] = idx;
            }

            if (it != s.begin())
            {
                maxEndBelow[std::prev(it)->idx] = idx;
            }

            s.erase(it);
        }

        last = idx;
    }

    assert(answer.size() == n - 1);
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        std::cout << answer[i].from.x << ' ' << answer[i].from.y << ' ' << answer[i].to.x << ' ' << answer[i].to.y << '\n';
    }
}   

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> lines[i].from.x >> lines[i].from.y >> lines[i].to.x >> lines[i].to.y;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from roads.cpp:4:
roads.cpp: In function 'void solve()':
roads.cpp:157:26: warning: comparison of integer expressions of different signedness: 'std::vector<Line>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  157 |     assert(answer.size() == n - 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40