oj.uz

Submission #1097563

# Submission time Handle Problem Language Result Execution time Memory
1097563 2024-10-07T14:59:11 Z Requiem Circle selection (APIO18_circle_selection) C++17
Compilation error
 0 ms 0 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "circlesec"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Cho n đường tròn, đường tròn thứ i: có tâm (xi, yi) và bán kính ri.

Ta có 1 thuật toán:
- Tìm đường tròn có bán kính lớn nhất.
- Xóa đường tròn đó và những đường tròn giao với nó.
- Lặp lại bước 1 và 2 cho đến khi không còn đường tròn nào.

Ta gọi đường tròn i bị loại bởi đường tròn j nếu như khi đường tròn j bị loại ở bước 1 thì đường tròn i sẽ bị loại ở bước 2.

subtask 1: n <= 5000. O(N^2)
subtask 2: n <= 3e5. yi = 0, bài toán đưa về khoảng. Giả sử cho n đoạn [li, ri], ta sẽ xóa đoạn lớn nhất xong tìm những thằng
giao với đoạn đó và loại nó ra.

Subtask này đơn giản ta sweep qua các đoạn, với mỗi đoạn.
Ta lưu 3 cái set. Mỗi set sẽ sort theo 1 thông số li, ri, và radius.

Ta có nhận xét là những đoạn có l nằm trong [l, r] sẽ bị xóa xổ ở cả 3. Khi này, độ phức tạp chỉ là O(N log N) khi mỗi phần
tử chỉ được xóa 1 lần.

subtask 3: n <= 3e5, mỗi đường tròn chỉ giao với 1 đường tròn khác.
2 đường tròn giao nhau khi d(O1, O2) <= R1 + R2.

subtask 4: n <= 3e5, mỗi đường tròn có cùng bán kính.

**/

const int MAXN = 3e5 + 9;
struct Circle{
    int x, y, r, id;
    Circle(int _x = 0, int _y = 0, int _r = 0, int _id = 0): x(_x), y(_y), r(_r), id(_id) {}

    bool operator * (const Circle &other){
        return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y) <= (r + other.r) * (r + other.r);
    }

} circle[MAXN];

int n;

bool deleted[MAXN];
int answer[MAXN];

namespace subtask1{
    bool check(){
        return n <= 5000;
    }

    void solve(){
        sort(circle + 1, circle + 1 + n, [&](const Circle &a, const Circle &b){
             return a.r < b.r;
        });
        memset(deleted, 0, sizeof(deleted));

        FOR(i, 1, n){
            int delId = 0, maxR = 0;

            FORD(j, n, 1){
                if (deleted[j]) continue;

                if (maximize(maxR, circle[j].r)) delId = j;
                else if (maxR == circle[j].r) delId = j;
            }

            FORD(j, n, 1){
                if (!deleted[j] and circle[delId] * circle[j]) {
                    deleted[j] = true;
                    answer[circle[j].id] = circle[delId].id;
                }
            }
        }

        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
        cout << endl;

    }
}

namespace subtask2{
    bool check(){
        FOR(i,1 , n){
            if (circle[i].y != 0) return false;
        }
        return n <= 3e5;
    }

    struct cmp1{
        bool operator () (const Circle &a, const Circle &b){
            if (a.x == b.x) {
                if (a.y == b.y) {
                    if (a.r == b.r) return a.id < b.id;
                    return a.r < b.r;
                }
                return a.y < b.y;
            }
            return a.x < b.x;
        }
    };

    struct cmp2{
        bool operator () (const Circle &a, const Circle &b){
            if (a.y == b.y) {
                if (a.x == b.x) {
                    if (a.r == b.r) return a.id < b.id;
                    return a.r < b.r;
                }
                return a.x < b.x;
            }
            return a.y < b.y;
        }
    };

    struct cmp3{
        bool operator () (const Circle &a, const Circle &b){
            if (a.r == b.r) {
                if (a.id == b.id) {
                    if (a.y == b.y) return a.x < b.x;
                    return a.y < b.y;
                }
                return a.id > b.id;
            }
            return a.r < b.r;
        }
    };

    set<Circle, cmp1> sortX;
    set<Circle, cmp2> sortY;
    set<Circle, cmp3> sortR;

    void solve(){
        FOR(i, 1, n){
            int x = circle[i].x;
            circle[i].x = x - circle[i].r;
            circle[i].y = x + circle[i].r;
//            cout << circle[i].x << ' ' << circle[i].y << ' ' << circle[i].r << endl;
            sortX.insert(circle[i]);
            sortY.insert(circle[i]);
            sortR.insert(circle[i]);
        }

        while (sortR.size() > 0){
            Circle ToErase = *sortR.rbegin();
            int L = ToErase.x;
            int R = ToErase.y;
            set<Circle, cmp1> eraseList;
//            cerr << ToErase.id << ' ' << endl;

            auto s1 = sortX.lower_bound(Circle(L, -inf, -inf, -inf));
            while(s1 != sortX.end() and (*s1).x <= R){
                eraseList.insert(*s1);
//                cerr << "X: " << (*s1).x << ' ' << (*s1).id << endl;
                s1 = next(s1);
            }

            auto s2 = sortY.lower_bound(Circle(-inf, L, -inf, -inf));
            while(s2 != sortY.end() and (*s2).y <= R){
//                cerr << "Y: " << (*s2).y << ' ' << (*s2).id << endl;

                eraseList.insert(*s2);
                s2 = next(s2);
            }
            for(auto p: eraseList){
                answer[p.id] = ToErase.id;
//                cout << p.id << ' ';
                if (sortX.find(p) != sortX.end()) sortX.erase(sortX.find(p));
                if (sortY.find(p) != sortY.end()) sortY.erase(sortY.find(p));
                if (sortR.find(p) != sortR.end()) sortR.erase(sortR.find(p));
            }
//            cout << endl;
        }

        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
        cout << endl;
    }
}
void input(){
    cin >> n;
    FOR(i, 1, n){
        cin >> circle[i].x >> circle[i].y >> circle[i].r;
        circle[i].id = i;
    }

    if (subtask1::check()) return subtask1::solve();
    if (subtask2::check()) return subtask2::solve();
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }

    input();

}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

circle_selection.cpp:210:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  210 | main()
      | ^~~~
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from circle_selection.cpp:1:
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp1; _Alloc = std::allocator<Circle>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<Circle>*]':
/usr/include/c++/10/bits/stl_tree.h:2101:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp1; _Alloc = std::allocator<Circle>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = Circle]'
/usr/include/c++/10/bits/stl_tree.h:2154:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const Circle&; _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp1; _Alloc = std::allocator<Circle>]'
/usr/include/c++/10/bits/stl_set.h:512:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = Circle; _Compare = subtask2::cmp1; _Alloc = std::allocator<Circle>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<Circle, Circle, std::_Identity<Circle>, subtask2::cmp1, std::allocator<Circle> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = Circle]'
circle_selection.cpp:158:35:   required from here
/usr/include/c++/10/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp2; _Alloc = std::allocator<Circle>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<Circle>*]':
/usr/include/c++/10/bits/stl_tree.h:2101:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp2; _Alloc = std::allocator<Circle>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = Circle]'
/usr/include/c++/10/bits/stl_tree.h:2154:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const Circle&; _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp2; _Alloc = std::allocator<Circle>]'
/usr/include/c++/10/bits/stl_set.h:512:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = Circle; _Compare = subtask2::cmp2; _Alloc = std::allocator<Circle>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<Circle, Circle, std::_Identity<Circle>, subtask2::cmp2, std::allocator<Circle> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = Circle]'
circle_selection.cpp:159:35:   required from here
/usr/include/c++/10/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp3; _Alloc = std::allocator<Circle>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<Circle>*]':
/usr/include/c++/10/bits/stl_tree.h:2101:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp3; _Alloc = std::allocator<Circle>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = Circle]'
/usr/include/c++/10/bits/stl_tree.h:2154:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const Circle&; _Key = Circle; _Val = Circle; _KeyOfValue = std::_Identity<Circle>; _Compare = subtask2::cmp3; _Alloc = std::allocator<Circle>]'
/usr/include/c++/10/bits/stl_set.h:512:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = Circle; _Compare = subtask2::cmp3; _Alloc = std::allocator<Circle>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<Circle, Circle, std::_Identity<Circle>, subtask2::cmp3, std::allocator<Circle> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = Circle]'
circle_selection.cpp:160:35:   required from here
/usr/include/c++/10/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:214:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~