제출 #252911

#제출 시각아이디문제언어결과실행 시간메모리
252911user202729원 고르기 (APIO18_circle_selection)C++17
100 / 100
2366 ms111768 KiB
// scanf/printf. #ifndef LOCAL #define NDEBUG 1 #endif #include<bits/stdc++.h> #pragma GCC optimize("O3") auto const callRange=[](auto& object, int first, int last, auto function){ auto iterator=object.lower_bound(first); while(iterator!=object.end() and iterator->first<last){ function(iterator->second); ++iterator; } }; int main(){ using Index=int; // for circles struct Circle{ int x, y, r; bool intersect(Circle other) const{ assert(r>0); assert(other.r>0); return int64_t(x-other.x)*(x-other.x)+int64_t(y-other.y)*(y-other.y)<= int64_t(r+other.r)*(r+other.r); } }; int number; std::scanf("%d",&number); std::vector<Circle> circles(number); for(auto& [x, y, r]: circles){ std::scanf("%d%d%d",&x,&y,&r); x+=1000000000; y+=1000000000; assert(x>=0 and y>=0); } struct A{ Index index; int r; bool operator<(A other) const{ return r!=other.r ? r<other.r: index>other.index; } }; std::priority_queue<A> q; for(Index index=0; index<number; ++index) q.push({index, circles[index].r}); std::vector<int> result(number); assert((result.assign(number, -1), true)); struct Cell{ std::vector<Index> indices; std::array<std::array<Cell*, 3>, 3> adjacent; // the numbering scheme is obvious. Note that [1][1] is always *this. std::array<std::array<Cell*, 2>, 2> children; }; std::deque<Cell> grid; grid.resize(1); for(Index index=0; index<number; ++index) grid[0].indices.push_back(index); grid[0].adjacent[1][1]=&grid[0]; std::vector<Cell*> contain(number, &grid[0]); for(int step=30; step>1;--step){ auto oldGrid=std::move(grid); grid.clear(); // construct all cells and children link of old layer & new contain array for(auto& cell: oldGrid){ std::array<std::array<Cell, 2>, 2> children{}; for(Index index: cell.indices){ auto const [x, y, r]=circles[index]; assert(r>0); children[x>>step&1][y>>step&1].indices.push_back(index); } for(int c=0; c<2; ++c) for(int d=0; d<2; ++d) if(not children[c][d].indices.empty()){ grid.push_back(std::move(children[c][d])); auto const cur=&grid.back(); cell.children[c][d]=cur; for(Index index: cur->indices) contain[index]=cur; } } // construct adjacent link of new layer for(auto& cell: oldGrid){ std::array<std::array<Cell*, 4>, 4> data{}; for(int c=0; c<3; ++c) for(int d=0; d<3; ++d){ Cell* cur=(c==1 and d==1 ? &cell: cell.adjacent[c][d]); if(not cur) continue; for(int e=0; e<2; ++e) for(int f=0; f<2; ++f){ unsigned const g=c*2+e-1, h=d*2+f-1; if(g<4 and h<4) data[g][h]=cur->children[e][f]; } } for(int e=0; e<2; ++e) for(int f=0; f<2; ++f){ Cell* cur=cell.children[e][f]; if(not cur) continue; for(int c=0; c<3; ++c) for(int d=0; d<3; ++d){ cur->adjacent[c][d]=data[c+e][d+f]; } } } while(true){ if(q.empty()) goto break_outer; auto [index, r_]=q.top(); auto const cur=circles[index]; auto const [x, y, r]=cur; if(r==0) { q.pop(); continue; } assert(r==r_); if(r<((1<<step)>>2)) break; // goto next step -- without popping from q q.pop(); circles[index].r=0; assert(result[index]==-1); result[index]=index; auto const curCell=contain[index]; assert(std::any_of(begin(grid), end(grid), [&](auto const& it){ return &it==curCell; })); assert(curCell->adjacent[1][1]==curCell); auto const process=[&](Cell* cell){ if(not cell) return; cell->indices.erase(std::remove_if(begin(cell->indices), end(cell->indices), [&](Index index1){ if(index1==index){ return true; } auto& cur1=circles[index1]; assert(cur1.r>0); if(cur1.intersect(cur)){ assert(result[index1]==-1); result[index1]=index; cur1.r=0; return true; } else return false; }),cell->indices.end()); }; for(int c=0; c<3; ++c) for(int d=0; d<3; ++d) process(curCell->adjacent[c][d]); } } break_outer: for(Index index=0; index<number; ++index){ auto const [x, y, r]=circles[index]; assert(result[index]!=-1); assert(r==0); } for(auto it: result) std::printf("%d ",it+1); std::printf("\n"); }

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:70:24: warning: unused variable 'r' [-Wunused-variable]
     auto const [x, y, r]=circles[index];
                        ^
circle_selection.cpp:114:19: warning: unused variable 'r_' [-Wunused-variable]
    auto [index, r_]=q.top();
                   ^
circle_selection.cpp:115:54: warning: unused variable 'x' [-Wunused-variable]
    auto const cur=circles[index]; auto const [x, y, r]=cur;
                                                      ^
circle_selection.cpp:115:54: warning: unused variable 'y' [-Wunused-variable]
circle_selection.cpp:158:22: warning: unused variable 'x' [-Wunused-variable]
   auto const [x, y, r]=circles[index];
                      ^
circle_selection.cpp:158:22: warning: unused variable 'y' [-Wunused-variable]
circle_selection.cpp:158:22: warning: unused variable 'r' [-Wunused-variable]
circle_selection.cpp:27:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int number; std::scanf("%d",&number);
              ~~~~~~~~~~^~~~~~~~~~~~~~
circle_selection.cpp:30:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   std::scanf("%d%d%d",&x,&y,&r);
   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
#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...