oj.uz

답안 #1097859

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097859 2024-10-08T12:20:35 Z Requiem 원 고르기 (APIO18_circle_selection) C++17
57 / 100
 1091 ms 135640 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.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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -