oj.uz

Submission #1097838

# Submission time Handle Problem Language Result Execution time Memory
1097838 2024-10-08T10:05:33 Z Requiem Circle selection (APIO18_circle_selection) C++17
19 / 100
 1305 ms 135576 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 (subtask3::check()) return subtask3::solve();
    if (subtask4::check()) return subtask4::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 40032 KB Output is correct
2 Correct 23 ms 40096 KB Output is correct
3 Correct 17 ms 40028 KB Output is correct
4 Correct 19 ms 40104 KB Output is correct
5 Correct 18 ms 40028 KB Output is correct
6 Correct 18 ms 40028 KB Output is correct
7 Correct 18 ms 39932 KB Output is correct
8 Correct 17 ms 40028 KB Output is correct
9 Correct 26 ms 40028 KB Output is correct
10 Correct 19 ms 40028 KB Output is correct
11 Correct 17 ms 39960 KB Output is correct
12 Correct 19 ms 40024 KB Output is correct
13 Correct 17 ms 39984 KB Output is correct
14 Correct 18 ms 40024 KB Output is correct
15 Correct 18 ms 40064 KB Output is correct
16 Correct 20 ms 39924 KB Output is correct
17 Correct 20 ms 40028 KB Output is correct
18 Correct 20 ms 40144 KB Output is correct
19 Correct 83 ms 40288 KB Output is correct
20 Correct 81 ms 40280 KB Output is correct
21 Correct 102 ms 40236 KB Output is correct
22 Correct 121 ms 40020 KB Output is correct
23 Correct 126 ms 40268 KB Output is correct
24 Correct 111 ms 40256 KB Output is correct
25 Correct 106 ms 40024 KB Output is correct
26 Correct 99 ms 40272 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 134988 KB Output is correct
2 Correct 1305 ms 128688 KB Output is correct
3 Correct 1305 ms 133036 KB Output is correct
4 Correct 1162 ms 135576 KB Output is correct
5 Correct 1066 ms 118816 KB Output is correct
6 Correct 965 ms 118868 KB Output is correct
7 Correct 1014 ms 119140 KB Output is correct
8 Correct 907 ms 118868 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 40024 KB Output is correct
2 Correct 107 ms 55492 KB Output is correct
3 Correct 347 ms 88544 KB Output is correct
4 Correct 375 ms 88544 KB Output is correct
5 Incorrect 458 ms 88544 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 88308 KB Output is correct
2 Correct 264 ms 87588 KB Output is correct
3 Incorrect 458 ms 89072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40032 KB Output is correct
2 Correct 23 ms 40096 KB Output is correct
3 Correct 17 ms 40028 KB Output is correct
4 Correct 19 ms 40104 KB Output is correct
5 Correct 18 ms 40028 KB Output is correct
6 Correct 18 ms 40028 KB Output is correct
7 Correct 18 ms 39932 KB Output is correct
8 Correct 17 ms 40028 KB Output is correct
9 Correct 26 ms 40028 KB Output is correct
10 Correct 19 ms 40028 KB Output is correct
11 Correct 17 ms 39960 KB Output is correct
12 Correct 19 ms 40024 KB Output is correct
13 Correct 17 ms 39984 KB Output is correct
14 Correct 18 ms 40024 KB Output is correct
15 Correct 18 ms 40064 KB Output is correct
16 Correct 20 ms 39924 KB Output is correct
17 Correct 20 ms 40028 KB Output is correct
18 Correct 20 ms 40144 KB Output is correct
19 Correct 83 ms 40288 KB Output is correct
20 Correct 81 ms 40280 KB Output is correct
21 Correct 102 ms 40236 KB Output is correct
22 Correct 121 ms 40020 KB Output is correct
23 Correct 126 ms 40268 KB Output is correct
24 Correct 111 ms 40256 KB Output is correct
25 Correct 106 ms 40024 KB Output is correct
26 Correct 99 ms 40272 KB Output is correct
27 Incorrect 26 ms 41740 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 40032 KB Output is correct
2 Correct 23 ms 40096 KB Output is correct
3 Correct 17 ms 40028 KB Output is correct
4 Correct 19 ms 40104 KB Output is correct
5 Correct 18 ms 40028 KB Output is correct
6 Correct 18 ms 40028 KB Output is correct
7 Correct 18 ms 39932 KB Output is correct
8 Correct 17 ms 40028 KB Output is correct
9 Correct 26 ms 40028 KB Output is correct
10 Correct 19 ms 40028 KB Output is correct
11 Correct 17 ms 39960 KB Output is correct
12 Correct 19 ms 40024 KB Output is correct
13 Correct 17 ms 39984 KB Output is correct
14 Correct 18 ms 40024 KB Output is correct
15 Correct 18 ms 40064 KB Output is correct
16 Correct 20 ms 39924 KB Output is correct
17 Correct 20 ms 40028 KB Output is correct
18 Correct 20 ms 40144 KB Output is correct
19 Correct 83 ms 40288 KB Output is correct
20 Correct 81 ms 40280 KB Output is correct
21 Correct 102 ms 40236 KB Output is correct
22 Correct 121 ms 40020 KB Output is correct
23 Correct 126 ms 40268 KB Output is correct
24 Correct 111 ms 40256 KB Output is correct
25 Correct 106 ms 40024 KB Output is correct
26 Correct 99 ms 40272 KB Output is correct
27 Correct 1276 ms 134988 KB Output is correct
28 Correct 1305 ms 128688 KB Output is correct
29 Correct 1305 ms 133036 KB Output is correct
30 Correct 1162 ms 135576 KB Output is correct
31 Correct 1066 ms 118816 KB Output is correct
32 Correct 965 ms 118868 KB Output is correct
33 Correct 1014 ms 119140 KB Output is correct
34 Correct 907 ms 118868 KB Output is correct
35 Correct 21 ms 40024 KB Output is correct
36 Correct 107 ms 55492 KB Output is correct
37 Correct 347 ms 88544 KB Output is correct
38 Correct 375 ms 88544 KB Output is correct
39 Incorrect 458 ms 88544 KB Output isn't correct
40 Halted 0 ms 0 KB -