BOJ 11510 - TOPOVI (constructive, greedy)
https://www.acmicpc.net/problem/11510 시공간복잡도 파악이 힘들어서 풀이방법 자체가 떠오르지 않았다. 최대 1e9*1e9 정사각형 모양의 한 변의 길이가 n인 그리드위에 룩(rook)을 배치할 것이다. 모든 룩은 1e9 이하의 power를 부여받는다. power가 x인 룩이 (r,c)에 배치된다면, r번 row의 모든 칸의 값에 x를 XOR한 값을 저장한다. c번 column도 마찬가지다. (따라서 칸(r,c)는 두 번 xor되므로 칸(r,c)에 저장된 값은 변하지않는다.) 초기에 최대 1e5개의 룩 k개를 배치한다. (r,c,x) 이후에 최대 1e5번 (r1,c1)에 위치한 룩을 모두 (r2,c2)에 이동시킨다. (r1,c1,r2,c2 ,, 꼭 (r1,c1)에 룩이 있다는 ..
2020. 3. 11.
