Submission #1098055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098055		Requiem	Circle selection (APIO18_circle_selection)	C++17	100 / 100	922 ms	150172 KiB

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 all(a) a.begin(),a.end()
#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];

struct DSU{
    vector<int> lab;

    int small_to_large = 1;
    int path_compression = 1;

    DSU(int _sz = 0, int _small_to_large = 1, int _path_compression = 1){
        small_to_large = _small_to_large;
        path_compression = _path_compression;
        lab.resize(_sz + 1, -1);
    }

    int root(int u){
        if (path_compression)  return ((lab[u] < 0) ? u : lab[u] = root(lab[u]));
        return root(lab[u]);
    }

    void unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
//            cerr << "MERGE: " << u <<  ' ' << v << endl;
            if (lab[u] > lab[v] and small_to_large) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
        }
    }
};

struct gridding{
    vector<ii> grid;
    DSU remaining;

    void add(ii a){  //them 1 phan tu
        grid.pb(a);
    }

    void refine(){
        sort(grid.begin(), grid.end());
        remaining = DSU(grid.size() + 3, 0, 1);
    }

    int lb(ii x){
        return lower_bound(grid.begin(), grid.end(), x) - grid.begin() ;
    }

    int rb(ii x){
        int l = 0, r = grid.size() - 1, res = -1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if (grid[mid].fi < x.fi or (grid[mid].fi == x.fi and grid[mid].se > x.se)){
                res = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return res;
    }

    void toDelete(int l, int dir = 1){  //xoa 1 phan tu l.
        remaining.unite(l + dir, l);
    }
};

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;
    }
    gridding sortX;
    gridding sortY;
    gridding 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;
            sortX.add(ii(circle[i].x, i));
            sortY.add(ii(circle[i].y, i));
            sortR.add(ii(circle[i].r, i));
//            if (circle[i].r == 0) cout << i << endl;
        }
        vector<int> eraseList;
        sortX.refine();
        sortY.refine();
        sortR.add(ii(-inf, 0));
        sortR.refine();
        sort(all(sortR.grid), [&](const ii &a, const ii &b){
             return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        });
        int cur = n;
        while(cur > 0){
//        FOR(t, 0, 2){
            cur = sortR.remaining.root(cur);
            if (cur == 0) continue;
            int delId = sortR.grid[cur].se;
            int L = circle[delId].x;
            int R = circle[delId].y;

            int id1 = sortX.lb(ii(L, -inf));
            for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
                id1 = sortX.remaining.root(id1);
                if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;

                int idC = sortX.grid[id1].se;
                eraseList.pb(idC);
                sortX.toDelete(id1);

                int delId = sortY.lb(ii(circle[idC].y, circle[idC].id));
                sortY.toDelete(delId);
            }
            id1 = sortY.lb(ii(L, -inf));
            for(;id1 < sortY.grid.size() and sortY.grid[id1].fi <= R;){
                id1 = sortY.remaining.root(id1);
                if (id1 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
                int idC = sortY.grid[id1].se;

                eraseList.pb(idC);
                sortY.toDelete(id1);

                int delId = sortX.lb(ii(circle[idC].x, circle[idC].id));
                sortX.toDelete(delId);
            }

            for(auto p: eraseList){
                answer[p] = delId;
                int id = sortR.rb(ii(circle[p].r, circle[p].id));
                sortR.toDelete(id + 1, -1);
            }
            eraseList.clear();
        }
        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);
        }
    };

    multiset<ii, cmpR> sortR;  //chua ii(r, i)


    gridding grid[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);
            grid[x].add(ii(circle[i].y / maxR, i));
        }
        FOR(i, 0, MAXN - 1){
            grid[i].refine();
        }
//        FOR(i, 0, 2){
//            for(auto p: grid[i].grid){
//                cout << p.fi << ' ' << p.se << endl;
//            }
//            cout << endl;
//        }
//        cout << endl;
        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){

                    int id1 = grid[valX].lb(ii(discreteY - 2, -inf));
                    int cnt = 0;

//                    cout << "CHOSE: ";
                    for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
                        id1 = grid[valX].remaining.root(id1);
                        if (id1 >= grid[valX].grid.size()) continue;
                        int idC = grid[valX].grid[id1].se;
//                        cout << idC << ' ';
//                        cnt++;
                        if (circle[idC] * circle[id]) {
                            toErase.pb(idC);
                            answer[idC] = id;
                            grid[valX].toDelete(id1);
                        }
                        else id1++;
//                        if (cnt > n) break;
                    }
//                    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));
                    }
                }
            }
        }

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

    }
}

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

    /**
    Quy trình:
    Như subtask 4 nhưng ta sẽ chia maxR làm đôi mỗi khi curMaxR < maxR.
    Ta sẽ thêm 1 cái log vào kết quả.
    Độ phức tạp của ta có thể là O(N log N) + O(log 10^9) * O(scaling) + O(zi).
    **/

    Circle tmp[MAXN];  //sorted Circle.
    vector<gridding> grid;
    vector<int> listX;
    gridding sortR;
    int getVal(vector<int> &listVal, int x){
        return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin();
    }

    void rescaling(int maxSize){
        listX.clear();
        grid.clear();
        int cur = 0, lastX = -inf;
        FOR(i, 1, n){
            if (deleted[tmp[i].id]) continue;
            int id = tmp[i].id;
            int x1 = circle[id].x / maxSize;
            int y1 = circle[id].y / maxSize;
//            cout << circle[id].x << ' ' << circle[id].y << ' ' << circle[id].id <<endl;
            if (grid.size() == 0 or x1 != lastX) {
                if (!grid.empty()) grid.back().refine();
                grid.pb({});
            }

            grid.back().add(ii(y1, id));
            listX.pb(x1);
            lastX = x1;
            cur++;
        }
        listX.erase(unique(listX.begin(), listX.end()), listX.end());
//        cout << "SZ: " << listX.size() << ' ' << grid.size() << endl;
        if (!grid.empty()) grid.back().refine();
    }

    int maxRadius = 0;
    void solve(){
        FOR(i, 1, n){
            tmp[i] = circle[i];

            maximize(maxRadius, circle[i].r);
            sortR.add(ii(circle[i].r, circle[i].id));
        }
        sort(tmp + 1, tmp + 1 + n, [&](const Circle &a, const Circle &b){
             return (a.x == b.x) ? (a.y < b.y) : a.x < b.x;
        });

        sortR.add(ii(-inf, 0));
        sortR.refine();

        sort(all(sortR.grid), [&](const ii &a, const ii &b){
             return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        });

//
//        for(ii p: sortR.grid){
//            cout << p.fi << ' ' << p.se <<endl;
//        }
        int cur = n;
        vector<int> toErase;
        rescaling(maxRadius);
//        cout << listX.size() << ' ' << endl;
//        FOR(i, 0, (int) listX.size() - 1){
//            cout << listX[i] << endl;
//            for(ii id: grid[i].grid){
//                cout << id.fi << ' ' << id.se << endl;
//            }
//            cout << endl;
//        }

        while(cur > 0){
//        FOR(t, 0, 1){
            cur = sortR.remaining.root(cur);
            if (cur == 0) break;

            int delId = sortR.grid[cur].se;

            if (circle[delId].r < maxRadius / 2){
                rescaling(circle[delId].r);
                maxRadius = circle[delId].r;
            }



            int x = circle[delId].x / maxRadius;
            int y = circle[delId].y / maxRadius;
//            cout << x << ' ' << y << ' ' << delId  << endl;
//
            FOR(nx, x - 2, x + 2){
                int valX = getVal(listX, nx);
                if (valX < listX.size() and listX[valX] == nx){

                    int id = grid[valX].lb(ii(y - 2, -inf));
//                    cout << id << ' ' << grid[valX].grid[id].fi << endl;
                    for(;id < grid[valX].grid.size() and grid[valX].grid[id].fi <= y + 2;){
                        id = grid[valX].remaining.root(id);
//                        cout << id << endl;
                        if (id >= grid[valX].grid.size() or grid[valX].grid[id].fi > y + 2) break;
                        int idC = grid[valX].grid[id].se;
                        if (circle[idC] * circle[delId]){
//                            cout << "DELE: " <<idC << ' ' << delId << endl;
                            answer[idC] = delId;
                            deleted[idC] = true;
                            toErase.pb(idC);
                            grid[valX].toDelete(id);
                        }
                        else id++;
                    }

                    for(int idC: toErase){
                        int id = sortR.rb(ii(circle[idC].r, circle[idC].id));
                        sortR.toDelete(id + 1, -1);
                    }
//                    cout <<endl;
                    toErase.clear();
                }


            }
        }

        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 (subtask56::check()) return subtask56::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 (stderr)

circle_selection.cpp: In function 'void subtask2::solve()':
circle_selection.cpp:200:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |             for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:202:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |                 if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:212:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |             for(;id1 < sortY.grid.size() and sortY.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:214:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |                 if (id1 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void subtask4::solve()':
circle_selection.cpp:415: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]
  415 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:421:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  421 |                     for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:423:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  423 |                         if (id1 >= grid[valX].grid.size()) continue;
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:418:25: warning: unused variable 'cnt' [-Wunused-variable]
  418 |                     int cnt = 0;
      |                         ^~~
circle_selection.cpp: In function 'void subtask56::solve()':
circle_selection.cpp:554: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]
  554 |                 if (valX < listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~
circle_selection.cpp:558:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  558 |                     for(;id < grid[valX].grid.size() and grid[valX].grid[id].fi <= y + 2;){
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:561:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  561 |                         if (id >= grid[valX].grid.size() or grid[valX].grid[id].fi > y + 2) break;
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: At global scope:
circle_selection.cpp:608:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  608 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:612:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  612 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:613:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  613 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13