#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() + 2, 0, 1);
}
int lb(ii x){
return lower_bound(grid.begin(), grid.end(), x) - grid.begin() ;
}
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;
}
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;
}
};
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.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 = 0;
while(cur < n){
cur = sortR.remaining.root(cur);
if (cur == n) continue;
int delId = sortR.grid[cur].se;
int L = circle[delId].x;
int R = circle[delId].y;
int id1 = sortX.lb(ii(L, -inf));
// cout << cur << ' ' << delId << ' ' << circle[delId].x << ' ' << circle[delId].r << endl;
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;
// cout << "X: " << id1 << ' ' << idC << ' ' << endl;
eraseList.pb(idC);
sortX.toDelete(id1);
int delId = sortY.lb(ii(circle[idC].y, circle[idC].id));
sortY.toDelete(delId);
}
// cout << endl;
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;
// cout << "Y: " << id1 << ' ' << idC << ' ' << endl;
eraseList.pb(idC);
sortY.toDelete(id1);
int delId = sortX.lb(ii(circle[idC].x, circle[idC].id));
sortX.toDelete(delId);
}
// cout << endl;
for(auto p: eraseList){
answer[p] = delId;
// cout << p << ' ';
sortR.toDelete(p - 1);
}
// cout << endl;
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)
**/
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 subtask2::solve()':
circle_selection.cpp:227: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]
227 | for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
| ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:229: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]
229 | if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;
| ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:242: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]
242 | for(;id1 < sortY.grid.size() and sortY.grid[id1].fi <= R;){
| ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:244: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]
244 | if (id1 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
| ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void subtask4::solve()':
circle_selection.cpp:449: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]
449 | if (valX != listX.size() and listX[valX] == nx){
| ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:455: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]
455 | for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:457: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]
457 | if (id1 >= grid[valX].grid.size()) continue;
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:452:25: warning: unused variable 'cnt' [-Wunused-variable]
452 | int cnt = 0;
| ^~~
circle_selection.cpp: At global scope:
circle_selection.cpp:518:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
518 | main()
| ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:522:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
522 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:523:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
523 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
63060 KB |
Output is correct |
| 2 |
Correct |
39 ms |
63056 KB |
Output is correct |
| 3 |
Correct |
38 ms |
62956 KB |
Output is correct |
| 4 |
Correct |
40 ms |
63056 KB |
Output is correct |
| 5 |
Incorrect |
39 ms |
63068 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3046 ms |
90732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
43 ms |
63056 KB |
Output is correct |
| 2 |
Correct |
164 ms |
85848 KB |
Output is correct |
| 3 |
Correct |
578 ms |
133568 KB |
Output is correct |
| 4 |
Correct |
485 ms |
133560 KB |
Output is correct |
| 5 |
Correct |
538 ms |
133304 KB |
Output is correct |
| 6 |
Correct |
285 ms |
99004 KB |
Output is correct |
| 7 |
Correct |
151 ms |
81876 KB |
Output is correct |
| 8 |
Correct |
67 ms |
67580 KB |
Output is correct |
| 9 |
Correct |
507 ms |
133440 KB |
Output is correct |
| 10 |
Correct |
636 ms |
133692 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
590 ms |
106260 KB |
Output is correct |
| 2 |
Correct |
560 ms |
109748 KB |
Output is correct |
| 3 |
Correct |
472 ms |
105148 KB |
Output is correct |
| 4 |
Correct |
582 ms |
109368 KB |
Output is correct |
| 5 |
Correct |
592 ms |
109956 KB |
Output is correct |
| 6 |
Correct |
450 ms |
103764 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
63060 KB |
Output is correct |
| 2 |
Correct |
39 ms |
63056 KB |
Output is correct |
| 3 |
Correct |
38 ms |
62956 KB |
Output is correct |
| 4 |
Correct |
40 ms |
63056 KB |
Output is correct |
| 5 |
Incorrect |
39 ms |
63068 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
63060 KB |
Output is correct |
| 2 |
Correct |
39 ms |
63056 KB |
Output is correct |
| 3 |
Correct |
38 ms |
62956 KB |
Output is correct |
| 4 |
Correct |
40 ms |
63056 KB |
Output is correct |
| 5 |
Incorrect |
39 ms |
63068 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
