oj.uz

Submission #1097839

# Submission time Handle Problem Language Result Execution time Memory
1097839 2024-10-08T10:06:14 Z Requiem Circle selection (APIO18_circle_selection) C++17
42 / 100
 1135 ms 128888 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 = 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.insert(event(circle[i].x, i, 2));
            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));

                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;
                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;

    }
}
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:366: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]
  366 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp: At global scope:
circle_selection.cpp:416:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  416 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:420:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  420 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:421:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  421 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40028 KB Output is correct
2 Correct 18 ms 40052 KB Output is correct
3 Correct 17 ms 40028 KB Output is correct
4 Correct 16 ms 40028 KB Output is correct
5 Correct 15 ms 40024 KB Output is correct
6 Correct 18 ms 40096 KB Output is correct
7 Correct 17 ms 39880 KB Output is correct
8 Correct 22 ms 40024 KB Output is correct
9 Correct 18 ms 40028 KB Output is correct
10 Correct 18 ms 40024 KB Output is correct
11 Correct 17 ms 40076 KB Output is correct
12 Correct 18 ms 40028 KB Output is correct
13 Correct 18 ms 40028 KB Output is correct
14 Correct 18 ms 40024 KB Output is correct
15 Correct 18 ms 39940 KB Output is correct
16 Correct 20 ms 40024 KB Output is correct
17 Correct 17 ms 40024 KB Output is correct
18 Correct 18 ms 40028 KB Output is correct
19 Correct 73 ms 40120 KB Output is correct
20 Correct 81 ms 40024 KB Output is correct
21 Correct 76 ms 40128 KB Output is correct
22 Correct 94 ms 40028 KB Output is correct
23 Correct 99 ms 40028 KB Output is correct
24 Correct 93 ms 40120 KB Output is correct
25 Correct 96 ms 40128 KB Output is correct
26 Correct 93 ms 40028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 128252 KB Output is correct
2 Correct 1088 ms 122028 KB Output is correct
3 Correct 1135 ms 126380 KB Output is correct
4 Correct 1084 ms 128888 KB Output is correct
5 Correct 968 ms 114364 KB Output is correct
6 Correct 853 ms 114340 KB Output is correct
7 Correct 921 ms 114352 KB Output is correct
8 Correct 898 ms 114256 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40028 KB Output is correct
2 Correct 109 ms 52560 KB Output is correct
3 Correct 332 ms 80448 KB Output is correct
4 Correct 347 ms 80612 KB Output is correct
5 Incorrect 398 ms 80456 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 83644 KB Output is correct
2 Correct 499 ms 83740 KB Output is correct
3 Correct 586 ms 83416 KB Output is correct
4 Correct 495 ms 91136 KB Output is correct
5 Correct 490 ms 91324 KB Output is correct
6 Correct 598 ms 91576 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40028 KB Output is correct
2 Correct 18 ms 40052 KB Output is correct
3 Correct 17 ms 40028 KB Output is correct
4 Correct 16 ms 40028 KB Output is correct
5 Correct 15 ms 40024 KB Output is correct
6 Correct 18 ms 40096 KB Output is correct
7 Correct 17 ms 39880 KB Output is correct
8 Correct 22 ms 40024 KB Output is correct
9 Correct 18 ms 40028 KB Output is correct
10 Correct 18 ms 40024 KB Output is correct
11 Correct 17 ms 40076 KB Output is correct
12 Correct 18 ms 40028 KB Output is correct
13 Correct 18 ms 40028 KB Output is correct
14 Correct 18 ms 40024 KB Output is correct
15 Correct 18 ms 39940 KB Output is correct
16 Correct 20 ms 40024 KB Output is correct
17 Correct 17 ms 40024 KB Output is correct
18 Correct 18 ms 40028 KB Output is correct
19 Correct 73 ms 40120 KB Output is correct
20 Correct 81 ms 40024 KB Output is correct
21 Correct 76 ms 40128 KB Output is correct
22 Correct 94 ms 40028 KB Output is correct
23 Correct 99 ms 40028 KB Output is correct
24 Correct 93 ms 40120 KB Output is correct
25 Correct 96 ms 40128 KB Output is correct
26 Correct 93 ms 40028 KB Output is correct
27 Incorrect 30 ms 41232 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40028 KB Output is correct
2 Correct 18 ms 40052 KB Output is correct
3 Correct 17 ms 40028 KB Output is correct
4 Correct 16 ms 40028 KB Output is correct
5 Correct 15 ms 40024 KB Output is correct
6 Correct 18 ms 40096 KB Output is correct
7 Correct 17 ms 39880 KB Output is correct
8 Correct 22 ms 40024 KB Output is correct
9 Correct 18 ms 40028 KB Output is correct
10 Correct 18 ms 40024 KB Output is correct
11 Correct 17 ms 40076 KB Output is correct
12 Correct 18 ms 40028 KB Output is correct
13 Correct 18 ms 40028 KB Output is correct
14 Correct 18 ms 40024 KB Output is correct
15 Correct 18 ms 39940 KB Output is correct
16 Correct 20 ms 40024 KB Output is correct
17 Correct 17 ms 40024 KB Output is correct
18 Correct 18 ms 40028 KB Output is correct
19 Correct 73 ms 40120 KB Output is correct
20 Correct 81 ms 40024 KB Output is correct
21 Correct 76 ms 40128 KB Output is correct
22 Correct 94 ms 40028 KB Output is correct
23 Correct 99 ms 40028 KB Output is correct
24 Correct 93 ms 40120 KB Output is correct
25 Correct 96 ms 40128 KB Output is correct
26 Correct 93 ms 40028 KB Output is correct
27 Correct 1093 ms 128252 KB Output is correct
28 Correct 1088 ms 122028 KB Output is correct
29 Correct 1135 ms 126380 KB Output is correct
30 Correct 1084 ms 128888 KB Output is correct
31 Correct 968 ms 114364 KB Output is correct
32 Correct 853 ms 114340 KB Output is correct
33 Correct 921 ms 114352 KB Output is correct
34 Correct 898 ms 114256 KB Output is correct
35 Correct 17 ms 40028 KB Output is correct
36 Correct 109 ms 52560 KB Output is correct
37 Correct 332 ms 80448 KB Output is correct
38 Correct 347 ms 80612 KB Output is correct
39 Incorrect 398 ms 80456 KB Output isn't correct
40 Halted 0 ms 0 KB -