| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1097563 | Requiem | Circle selection (APIO18_circle_selection) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 3e5 + 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(){
sort(circle + 1, circle + 1 + n, [&](const Circle &a, const Circle &b){
return a.r < b.r;
});
memset(deleted, 0, sizeof(deleted));
FOR(i, 1, n){
int delId = 0, maxR = 0;
FORD(j, n, 1){
if (deleted[j]) continue;
if (maximize(maxR, circle[j].r)) delId = j;
else if (maxR == circle[j].r) delId = j;
}
FORD(j, n, 1){
if (!deleted[j] and circle[delId] * circle[j]) {
deleted[j] = true;
answer[circle[j].id] = circle[delId].id;
}
}
}
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 <= 3e5;
}
struct cmp1{
bool operator () (const Circle &a, const Circle &b){
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){
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){
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]);
}
while (sortR.size() > 0){
Circle ToErase = *sortR.rbegin();
int L = ToErase.x;
int R = ToErase.y;
set<Circle, cmp1> eraseList;
// cerr << ToErase.id << ' ' << endl;
auto s1 = sortX.lower_bound(Circle(L, -inf, -inf, -inf));
while(s1 != sortX.end() and (*s1).x <= R){
eraseList.insert(*s1);
// cerr << "X: " << (*s1).x << ' ' << (*s1).id << endl;
s1 = next(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.insert(*s2);
s2 = next(s2);
}
for(auto p: eraseList){
answer[p.id] = ToErase.id;
// cout << p.id << ' ';
if (sortX.find(p) != sortX.end()) sortX.erase(sortX.find(p));
if (sortY.find(p) != sortY.end()) sortY.erase(sortY.find(p));
if (sortR.find(p) != sortR.end()) sortR.erase(sortR.find(p));
}
// cout << endl;
}
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();
}
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.
**/