Submission #1097765

#TimeUsernameProblemLanguageResultExecution timeMemory
1097765RequiemCircle selection (APIO18_circle_selection)C++17
19 / 100
1236 ms113232 KiB
#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(){ 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]); } set<Circle, cmp1> 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.insert(*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.insert(*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; } } 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. **/

Compilation message (stderr)

circle_selection.cpp:211:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  211 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...