oj.uz

Submission #865782

# Submission time Handle Problem Language Result Execution time Memory
865782 2023-10-24T16:02:05 Z boris_mihov Roads (CEOI20_roads) C++17
15 / 100
 42 ms 14532 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Failed 36 ms 12976 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 8 ms 4564 KB Output is correct
5 Correct 18 ms 8644 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 15 ms 8656 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2548 KB Output is correct
8 Failed 1 ms 2652 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 8 ms 4564 KB Output is correct
5 Correct 16 ms 8656 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 8 ms 4464 KB Output is correct
10 Correct 42 ms 14532 KB Output is correct
11 Failed 1 ms 2392 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
12 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2684 KB Output is correct
5 Correct 8 ms 4560 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Failed 1 ms 2648 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
9 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Failed 37 ms 12748 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -