Submission #1097859

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097859	2024-10-08T12:20:35 Z	Requiem	Circle selection (APIO18_circle_selection)	C++17	57 / 100	1091 ms	135640 KB

circle_selection

#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 = 5e5 + 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(){
        memset(deleted, 0, sizeof(deleted));

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

            FOR(j, 1, n){
                if (deleted[j]) continue;
                if (maximize(maxR, circle[j].r)) delId = j;
            }

//            cout << delId << endl;
            FOR(j, 1, n){
                if (!deleted[j] and circle[delId] * circle[j]) {
                    deleted[j] = true;
                    answer[j] = delId;
//                    cout << j << ' ';
                }
            }
//            cout << endl;
        }

        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 <= 300000;
    }

    struct cmp1{
        bool operator () (const Circle &a, const Circle &b) const{
            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) const{
            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) const{
            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]);
        }
        vector<Circle> eraseList;

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

            auto s1 = sortX.lower_bound(Circle(L, -inf, -inf, -inf));
            while(s1 != sortX.end() and (*s1).x <= R){
                eraseList.pb(*s1);
//                cerr << "X: " << (*s1).x << ' ' << (*s1).id << endl;
                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.pb(*s2);
                s2++;
            }
            for(auto p: eraseList){
                answer[p.id] = ToErase.id;
                auto it1 = sortX.find(p);
                auto it2 = sortY.find(p);
                auto it3 = sortR.find(p);
//                cout << p.id << ' ';
                if (it1 != sortX.end()) sortX.erase(it1);
                if (it2 != sortY.end()) sortY.erase(it2);
                if (it3 != sortR.end()) sortR.erase(it3);
            }
//            cout << endl;
        }

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

namespace subtask3{
    bool check(){
        return true;
    }

    struct event{
        int x, id, type;
        event(int _x = 0, int _id = 0, int _type = 0): x(_x), id(_id), type(_type) {}
        //1: them
        //2: loai bo

        bool operator < (const event &other) const{
            if (x == other.x){
                if (type == other.type){
                    return id < other.id;
                }
                return type < other.type;
            }
            return x < other.x;
        }

    };

    struct cmp{
        bool operator() (const ii &a, const ii &b) const{
            return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        }
    };
    //moi duong tron chi giao voi toi da 1 duong tron khac.
    int other[MAXN];
    vector<event> events; //chua pair(x, i) la event.
    multiset<ii> listY;
    multiset<ii, cmp> sortR;
    void solve(){
        FOR(i, 1, n){
            sortR.insert(ii(circle[i].r, i));
            events.pb(event(circle[i].x - circle[i].r, i, 1));
            events.pb(event(circle[i].x - circle[i].r, i, 3));
            events.pb(event(circle[i].x, i, 3));
            events.pb(event(circle[i].x + circle[i].r, i, 3));
            events.pb(event(circle[i].x + circle[i].r + 1, i, 2));
        }
        sort(events.begin(),events.end());

        for(auto e: events){
            if (e.type == 1) {
                int addId = e.id;
                listY.insert(ii(circle[addId].y, addId));
            }
            else if (e.type == 3){
                int addId = e.id;
                auto it = listY.lower_bound(ii(circle[addId].y, addId));
                if (it != listY.end()){
                    auto nxt = next(it);
                    if (nxt != listY.end() and circle[addId] * circle[(*nxt).se]) {
                        other[addId] = (*nxt).se;
                        other[(*nxt).se] = addId;
                    }
                }

                if (it != listY.begin()){
                    auto prv = prev(it);
                    if (circle[addId] * circle[(*prv).se]) {
                        other[addId] = (*prv).se;
                        other[(*prv).se] = addId;
                    }
                }
            }

            else{
                int delId = e.id;
//                cout << "DEL: " << delId << endl;

                listY.erase(listY.find(ii(circle[delId].y, delId)));
            }
        }

        while(!sortR.empty()){
            auto it = *sortR.rbegin();

            int id = it.se;
            answer[id] = id;
//            cout << circle[id].id << endl;

            sortR.erase(sortR.find(it));

            if (other[id] != 0) {
                answer[other[id]] = id;
                ii tmp = ii(circle[other[id]].r, circle[other[id]].id);
                if (sortR.find(tmp) != sortR.end()) sortR.erase(sortR.find(tmp) );
            }
        }
//        FOR(i, 1, n){
//            cout << other[i] << ' ';
//        }
//        cout << endl;

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

namespace subtask4{
    bool check(){
        FOR(i,1 , n){
            if (circle[i].r != circle[1].r) return false;
        }
        return true;
    }

    /**
    Idea cua sub nay la: ta se chia
    truc thanh cac o r * r.
    luc nay, ta chi can xet hinh trong co tam nam trong vung hinh vuong 5r * 5r.
    **/

    int maxR = 0;
    vector<int> listX;

    int getVal(vector<int> &listVal, int x){
        return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin();
    }


    struct cmpR{
        bool operator() (const ii &a, const ii &b) const{
            return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        }
    };

    struct cmpGrid{
        bool operator() (const ii &a, const ii &b) const{
            return (a.fi == b.fi) ? (a.se < b.se) : (a.fi < b.fi);
        }
    };
    multiset<ii, cmpR> sortR;  //chua ii(r, i)
    multiset<ii, cmpGrid> gridding[MAXN];  //chua ii(y, i)
    vector<int> toErase;
    void solve(){
        maxR = circle[1].r;
        FOR(i, 1, n){
            sortR.insert(ii(circle[i].r, circle[i].id));
        }

        FOR(i, 1, n){
            listX.pb(circle[i].x / maxR);
        }

        sort(listX.begin(), listX.end());
        listX.erase(unique(listX.begin(), listX.end()), listX.end());
//
        FOR(i, 1, n){
            int x = getVal(listX, circle[i].x / maxR);
            gridding[x].insert(ii(circle[i].y / maxR, i));
        }
        while(!sortR.empty()){
            auto it = *sortR.rbegin();
            int id = it.se;
            answer[id] = id;
//            cout << id << endl;

            int discreteX = circle[id].x / maxR;
            int discreteY = circle[id].y / maxR;
//            cout << discreteX << ' ' << discreteY << endl;

            FOR(nx, discreteX - 2, discreteX + 2){
                int valX = getVal(listX, nx);
                toErase.clear();

                if (valX != listX.size() and listX[valX] == nx){
//                    cout << valX << ' ' << listX[valX] << ' ' << gridding[valX].size() <<endl;
                    auto it = gridding[valX].lower_bound(ii(discreteY - 2, -inf));
                    for(;it != gridding[valX].end() and (*it).fi <= discreteY + 2; it++){
                        int idC = (*it).se;
                        if (circle[idC] * circle[id]) {
                            answer[idC] = id;
                            toErase.pb(idC);
                        }
                    }

//                    cout << "ERASE: ";
//                    for(int p: toErase){
//                        cout << p << ' ';
//                    }
//                    cout << endl;

                    for(auto id: toErase){
                        ii t1 = ii(circle[id].r, circle[id].id);
                        if (sortR.find(t1) != sortR.end())
                            sortR.erase(sortR.find(t1));

                        ii t2 = ii(circle[id].y / maxR, circle[id].id);
                        if (gridding[valX].find(t2) != gridding[valX].end())
                            gridding[valX].erase(gridding[valX].find(t2));
                    }
                }
            }
        }

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

    }
}

namespace subtask56{
    bool check(){
        return true;
    }

    void solve(){

    }
}
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();
    if (subtask4::check()) return subtask4::solve();

    if (subtask3::check()) return subtask3::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: In function 'void subtask4::solve()':
circle_selection.cpp:372:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  372 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp: At global scope:
circle_selection.cpp:431:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  431 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:435:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  435 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:436:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  436 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	40024 KB	Output is correct
2	Correct	15 ms	40024 KB	Output is correct
3	Correct	15 ms	40032 KB	Output is correct
4	Correct	15 ms	39876 KB	Output is correct
5	Correct	15 ms	40016 KB	Output is correct
6	Correct	15 ms	40028 KB	Output is correct
7	Correct	15 ms	40028 KB	Output is correct
8	Correct	15 ms	40028 KB	Output is correct
9	Correct	15 ms	40028 KB	Output is correct
10	Correct	18 ms	39880 KB	Output is correct
11	Correct	18 ms	40028 KB	Output is correct
12	Correct	17 ms	40028 KB	Output is correct
13	Correct	16 ms	40024 KB	Output is correct
14	Correct	17 ms	40024 KB	Output is correct
15	Correct	18 ms	40028 KB	Output is correct
16	Correct	19 ms	40024 KB	Output is correct
17	Correct	20 ms	40020 KB	Output is correct
18	Correct	17 ms	40028 KB	Output is correct
19	Correct	53 ms	40284 KB	Output is correct
20	Correct	50 ms	40264 KB	Output is correct
21	Correct	51 ms	40280 KB	Output is correct
22	Correct	73 ms	40028 KB	Output is correct
23	Correct	72 ms	40272 KB	Output is correct
24	Correct	78 ms	40276 KB	Output is correct
25	Correct	71 ms	40176 KB	Output is correct
26	Correct	72 ms	40272 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1091 ms	134804 KB	Output is correct
2	Correct	979 ms	128764 KB	Output is correct
3	Correct	1008 ms	133044 KB	Output is correct
4	Correct	1066 ms	135640 KB	Output is correct
5	Correct	907 ms	118768 KB	Output is correct
6	Correct	865 ms	118864 KB	Output is correct
7	Correct	837 ms	119064 KB	Output is correct
8	Correct	802 ms	118932 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	40028 KB	Output is correct
2	Correct	131 ms	62380 KB	Output is correct
3	Correct	431 ms	110008 KB	Output is correct
4	Correct	485 ms	110012 KB	Output is correct
5	Correct	522 ms	109876 KB	Output is correct
6	Correct	264 ms	75388 KB	Output is correct
7	Correct	129 ms	58332 KB	Output is correct
8	Correct	35 ms	43780 KB	Output is correct
9	Correct	494 ms	110008 KB	Output is correct
10	Correct	612 ms	110344 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	538 ms	91528 KB	Output is correct
2	Correct	461 ms	90808 KB	Output is correct
3	Correct	511 ms	91836 KB	Output is correct
4	Correct	468 ms	91068 KB	Output is correct
5	Correct	466 ms	91316 KB	Output is correct
6	Correct	610 ms	91584 KB	Output is correct

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	40024 KB	Output is correct
2	Correct	15 ms	40024 KB	Output is correct
3	Correct	15 ms	40032 KB	Output is correct
4	Correct	15 ms	39876 KB	Output is correct
5	Correct	15 ms	40016 KB	Output is correct
6	Correct	15 ms	40028 KB	Output is correct
7	Correct	15 ms	40028 KB	Output is correct
8	Correct	15 ms	40028 KB	Output is correct
9	Correct	15 ms	40028 KB	Output is correct
10	Correct	18 ms	39880 KB	Output is correct
11	Correct	18 ms	40028 KB	Output is correct
12	Correct	17 ms	40028 KB	Output is correct
13	Correct	16 ms	40024 KB	Output is correct
14	Correct	17 ms	40024 KB	Output is correct
15	Correct	18 ms	40028 KB	Output is correct
16	Correct	19 ms	40024 KB	Output is correct
17	Correct	20 ms	40020 KB	Output is correct
18	Correct	17 ms	40028 KB	Output is correct
19	Correct	53 ms	40284 KB	Output is correct
20	Correct	50 ms	40264 KB	Output is correct
21	Correct	51 ms	40280 KB	Output is correct
22	Correct	73 ms	40028 KB	Output is correct
23	Correct	72 ms	40272 KB	Output is correct
24	Correct	78 ms	40276 KB	Output is correct
25	Correct	71 ms	40176 KB	Output is correct
26	Correct	72 ms	40272 KB	Output is correct
27	Incorrect	32 ms	42232 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	40024 KB	Output is correct
2	Correct	15 ms	40024 KB	Output is correct
3	Correct	15 ms	40032 KB	Output is correct
4	Correct	15 ms	39876 KB	Output is correct
5	Correct	15 ms	40016 KB	Output is correct
6	Correct	15 ms	40028 KB	Output is correct
7	Correct	15 ms	40028 KB	Output is correct
8	Correct	15 ms	40028 KB	Output is correct
9	Correct	15 ms	40028 KB	Output is correct
10	Correct	18 ms	39880 KB	Output is correct
11	Correct	18 ms	40028 KB	Output is correct
12	Correct	17 ms	40028 KB	Output is correct
13	Correct	16 ms	40024 KB	Output is correct
14	Correct	17 ms	40024 KB	Output is correct
15	Correct	18 ms	40028 KB	Output is correct
16	Correct	19 ms	40024 KB	Output is correct
17	Correct	20 ms	40020 KB	Output is correct
18	Correct	17 ms	40028 KB	Output is correct
19	Correct	53 ms	40284 KB	Output is correct
20	Correct	50 ms	40264 KB	Output is correct
21	Correct	51 ms	40280 KB	Output is correct
22	Correct	73 ms	40028 KB	Output is correct
23	Correct	72 ms	40272 KB	Output is correct
24	Correct	78 ms	40276 KB	Output is correct
25	Correct	71 ms	40176 KB	Output is correct
26	Correct	72 ms	40272 KB	Output is correct
27	Correct	1091 ms	134804 KB	Output is correct
28	Correct	979 ms	128764 KB	Output is correct
29	Correct	1008 ms	133044 KB	Output is correct
30	Correct	1066 ms	135640 KB	Output is correct
31	Correct	907 ms	118768 KB	Output is correct
32	Correct	865 ms	118864 KB	Output is correct
33	Correct	837 ms	119064 KB	Output is correct
34	Correct	802 ms	118932 KB	Output is correct
35	Correct	15 ms	40028 KB	Output is correct
36	Correct	131 ms	62380 KB	Output is correct
37	Correct	431 ms	110008 KB	Output is correct
38	Correct	485 ms	110012 KB	Output is correct
39	Correct	522 ms	109876 KB	Output is correct
40	Correct	264 ms	75388 KB	Output is correct
41	Correct	129 ms	58332 KB	Output is correct
42	Correct	35 ms	43780 KB	Output is correct
43	Correct	494 ms	110008 KB	Output is correct
44	Correct	612 ms	110344 KB	Output is correct
45	Correct	538 ms	91528 KB	Output is correct
46	Correct	461 ms	90808 KB	Output is correct
47	Correct	511 ms	91836 KB	Output is correct
48	Correct	468 ms	91068 KB	Output is correct
49	Correct	466 ms	91316 KB	Output is correct
50	Correct	610 ms	91584 KB	Output is correct
51	Incorrect	32 ms	42232 KB	Output isn't correct
52	Halted	0 ms	0 KB	-