Submission #1097883

#TimeUsernameProblemLanguageResultExecution timeMemory
1097883RequiemCircle selection (APIO18_circle_selection)C++17
57 / 100
1155 ms159384 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 = 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){ if (lab[u] > lab[v] and small_to_large) swap(u, v); lab[u] += lab[v]; lab[v] = u; } } }; 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.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) 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){ //xoa 1 doan [l, r] remaining.unite(l + 1, l); } }; 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 (stderr)

circle_selection.cpp: In function 'void subtask4::solve()':
circle_selection.cpp:425: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]
  425 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:431: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]
  431 |                     for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:433: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]
  433 |                         if (id1 >= grid[valX].grid.size()) continue;
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:428:25: warning: unused variable 'cnt' [-Wunused-variable]
  428 |                     int cnt = 0;
      |                         ^~~
circle_selection.cpp: At global scope:
circle_selection.cpp:494:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  494 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:498:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  498 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:499:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  499 |         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...