제출 #252911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252911		user202729	원 고르기 (APIO18_circle_selection)	C++17	100 / 100	2366 ms	111768 KiB

circle_selection

// 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);
   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13