oj.uz

Submission #998761

# Submission time Handle Problem Language Result Execution time Memory
998761 2024-06-14T16:27:36 Z Trustfulcomic Roads (CEOI20_roads) C++14
15 / 100
 95 ms 3444 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define x first
#define y second

struct Usecka{
    pii a,b;
    int idx;
};

bool stejny(Usecka a, Usecka b){
    if ((a.a.x == b.a.x && a.a.y == b.a.y && a.b.x == b.b.x && a.b.y == b.b.y) || (a.a.x == b.b.x && a.a.y == b.b.y && a.b.x == b.a.x && a.b.y == b.a.y)){
        return true;
    }
    return false;
}

bool comp(const Usecka& l, const Usecka& r){
    if ((l.a.x == r.a.x && l.a.y == r.a.y && l.b.x == r.b.x && l.b.y == r.b.y) || (l.a.x == r.b.x && l.a.y == r.b.y && l.b.x == r.a.x && l.b.y == r.a.y)){
        return false;
    }
    bool prohozeny = false;
    Usecka u;
    pii b;
    if (min(l.a.x,l.b.x) >= min(r.a.x,r.b.x) && min(l.a.x,l.b.x) <= max(r.a.x,r.b.x)){
        b = min(l.a, l.b);
        u = r;
    } else {
        b = min(r.a, r.b);
        u = l;
        prohozeny = true;
    }

    if (u.a.x == u.b.x || b.x == u.a.x){
        return prohozeny^(u.a.y>b.y);
    } else {
        long double ynko = u.a.y + ((long double)(u.b.y-u.a.y)*(b.x-u.a.x))/((long double)(u.b.x-u.a.x));
        return prohozeny^(ynko>b.y);
    }

}

int main(){
    int n; cin >> n;
    vector<Usecka> points(2*n);
    for (int i = 0; i<n; i++){
        int a,b,c,d; cin >> a >> b >> c >> d;
        points[2*i] = {{a,b},{c,d},i};
        points[2*i+1] = {{c,d},{a,b},i};
    }

    sort(points.begin(), points.end(), [](const Usecka& l, const Usecka &r){
        return (l.a.x < r.a.x) || (l.a.x == r.a.x && l.a.y < r.a.y);
    });

    vector<pii> nad(n, {INT_MAX,INT_MAX});
    vector<pii> pod(n, {INT_MAX,INT_MAX});

    pii last_deleted = {INT_MAX,INT_MAX};

    set<Usecka, decltype(&comp)> usecky(&comp);
    usecky.insert(points[0]);
    nad[points[0].idx] = points[0].a;
    pod[points[0].idx] = points[0].a;
    for (int i = 1; i<2*n; i++){
        auto it = usecky.lower_bound(points[i]);
        if (it != usecky.end() && stejny(*it, points[i])){
            if (it != usecky.begin()){
                it--;
                nad[it->idx] = points[i].a;
                it++;
            }
            it++;
            if (it != usecky.end()){
                pod[it->idx] = points[i].a;
            }
            it--;
            last_deleted = points[i].a;
            usecky.erase(it);
        } else {
            if (usecky.size() == 0){
                cout << points[i].a.x << " " << points[i].a.y << " " << last_deleted.x << " " << last_deleted.y << endl;
            } else {
                if (it != usecky.end()){
                    cout << points[i].a.x << " " << points[i].a.y << " " << pod[it->idx].x << " " << pod[it->idx].y << endl;
                } else {
                    it--;
                    cout << points[i].a.x << " " << points[i].a.y << " " << nad[it->idx].x << " " << nad[it->idx].y << endl;
                    it++;
                }
            }

            if (it != usecky.end()){
                pod[it->idx] = points[i].a;
            }
            if (it != usecky.begin()){
                it--;
                nad[it->idx] = points[i].a;
                it++;
            }
            usecky.insert(points[i]);
        }
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Failed 90 ms 3408 KB Condition failed: "iB != P2I.end()"
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 22 ms 1440 KB Output is correct
5 Correct 43 ms 2544 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 21 ms 1356 KB Output is correct
5 Correct 45 ms 2640 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Failed 1 ms 348 KB Condition failed: "iB != P2I.end()"
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 22 ms 1372 KB Output is correct
5 Correct 43 ms 2644 KB Output is correct
6 Failed 1 ms 348 KB Condition failed: "iB != P2I.end()"
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 27 ms 1488 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Failed 1 ms 348 KB Condition failed: "iB != P2I.end()"
8 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Failed 95 ms 3444 KB Condition failed: "iB != P2I.end()"
3 Halted 0 ms 0 KB -