BOJ 4211 금고 회사

문제 링크입니다.

거울을 놓을 수 있는 위치

는 정해져 있습니다. 출발점에서 가는 레이저가 새로 넣은 거울에 반사되어 도착점으로 향해야 하므로, 출발점과 도착점에서 각각 레이저를 쐈다고 했을 때 두 레이저의 교점에 거울을 놓아야 합니다.

경로 찾기

금고가 너어어무 큽니다. 하지만 거울은 상대적으로 적으니, 거울을 기준으로 생각합시다.

각 행과 열에 있는 거울을 정렬해 저장해 두면 이분 탐색을 여러 번 해서 각 위치에서 쏜 레이저의 경로를 찾아낼 수 있습니다.

교점 개수 구하기

두 레이저가 교차하기 위해서는 한 레이저는 수직, 다른 레이저는 수평으로 그 칸에 진입해야 합니다. 이로부터, 수직인 레이저를 점 업데이트로 생각하고 수평 방향 레이저를 구간 쿼리로 취급해 높이 순으로 확인하는 세그 스위핑을 하면 교점의 개수를 구할 수 있습니다.

가장 작은 좌표 찾기

스위핑을 하다가 교점이 있으면 그 교점 중 가장 왼쪽에 있는 것을 찾아내야 합니다. 업데이트를 처리하면서 만들어진 세그먼트 트리 위에서 이분 탐색을 돌리면 됩니다.

시간 절약을 위해 BIT와 $\mathcal{O}(\lg N)$ BIT Lifting을 썼는데, 안 써도 시간 제한이 꽤 커서 돌 수도 있을 것 같네요.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using pii = pair<int, int>;

int r, c, m, n, tc;
long long ans;
pii ans_coord;

set<pii> mirror_vertical_input[1010101];
set<pii> mirror_horizontal_input[1010101];
vector<int> inpath, outpath;

struct Line{
	int h, l, r;
};

vector<Line> inpath_horizontal, inpath_vertical, outpath_horizontal, outpath_vertical;
vector<Line> Queries;

int fen[1050000];

void upd(int i, int v){for(;i<=(1<<20);i+=i&-i) fen[i]+=v;}
int qry(int i){
	int ret = 0;
	for(;i;i-=i&-i) ret += fen[i];
	return ret;
}

void pathfinder(vector<int>& path, int y, int x, int dir){ //RULD
	path.push_back(x); path.push_back(y);
	while(1){
		set<pii>::iterator nxt;
		if(dir == 0){
			nxt = mirror_horizontal_input[y].upper_bound({x,2});
			if(nxt == mirror_horizontal_input[y].end()){
				path.push_back(c+1);
				return;
			}
			path.push_back(x = nxt->first);
		}
		else if(dir == 1){
			nxt = mirror_vertical_input[x].lower_bound({y,0});
			if(nxt == mirror_vertical_input[x].begin()){
				path.push_back(0);
				return;
			}
			nxt--;
			path.push_back(y = nxt->first);
		}
		else if(dir == 2){
			nxt = mirror_horizontal_input[y].lower_bound({x,0});
			if(nxt == mirror_horizontal_input[y].begin()){
				path.push_back(0);
				return;
			}
			nxt--;
			path.push_back(x = nxt->first);
		}
		else if(dir == 3){
			nxt = mirror_vertical_input[x].upper_bound({y,2});
			if(nxt == mirror_vertical_input[x].end()){
				path.push_back(r+1);
				return;
			}
			path.push_back(y = nxt->first);
		}
		if(nxt->second) dir = 3-dir;
		else dir ^= 1;
	}
}

pii solve(vector<Line>& U, vector<Line>& Q, int n, int m, bool flipped){
	memset(fen, 0, sizeof(fen));
	Queries.clear();
	int rety = n+m, retx = n+m;
	for(auto [h, l, r] : U){
		if(l > r) swap(l, r);
		Queries.push_back({l+1, -1, h});
		Queries.push_back({r, -3, h});
	}
	for(auto [h, l, r] : Q){
		if(l > r) swap(l, r);
		Queries.push_back({h, l+1, r-1});
	}
	sort(Queries.begin(), Queries.end(), [&](const Line& a, const Line& b){
		if(a.h != b.h) return a.h < b.h;
		return a.l < b.l;
	});
	for(auto [h, l, r] : Queries){
		//cout << h << ' ' << l << ' ' << r << '\n';
		if(l < 0) upd(r, l+2);
		else{
			if(l > r) continue;
			int tmp = qry(r)-qry(l-1);
			ans += tmp;
			if(tmp){
				int gizun = qry(l-1);
				int x = 0;
				for(int bit = (1<<20); bit; bit >>= 1){
					if(fen[x+bit] <= gizun){
						gizun -= fen[x+bit];
						x += bit;
					}
					else continue;
				}
				x++;
				if(flipped){
					if(rety > x || (rety == x && retx > h)){
						rety = x;
						retx = h;
					}
				}
				else{
					if(rety > h || rety == h && retx > x){
						rety = h;
						retx = x;
					}
				}
			}
		}
	}
	return {rety, retx};
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	while(cin >> r >> c >> m >> n){
		for(int i = 1; i <= r; i++) mirror_horizontal_input[i].clear();
		for(int i = 1; i <= c; i++) mirror_vertical_input[i].clear();
		inpath.clear();
		outpath.clear();
		inpath_horizontal.clear();
		inpath_vertical.clear();
		outpath_horizontal.clear();
		outpath_vertical.clear();
		ans_coord = {r+1, c+1};
		ans = 0;
		while(m--){
			int y, x; cin >> y >> x;
			mirror_vertical_input[x].insert({y, 0});
			mirror_horizontal_input[y].insert({x, 0});
		}
		while(n--){
			int y, x; cin >> y >> x;
			mirror_vertical_input[x].insert({y, 1});
			mirror_horizontal_input[y].insert({x, 1});
		}
		
		tc++; cout << "Case " << tc <<": ";
		pathfinder(inpath, 1, 0, 0);
		if(inpath.size()%2 == 1 && inpath[inpath.size()-1] == c+1 && inpath[inpath.size()-2] == r){
			cout << "0\n";
			continue;
		}
		pathfinder(outpath, r, c+1, 2);
		for(int i = 0; i < inpath.size()-2; i+=2) inpath_horizontal.push_back({inpath[i+1], inpath[i], inpath[i+2]});
		for(int i = 1; i < inpath.size()-2; i+=2) inpath_vertical.push_back({inpath[i+1], inpath[i], inpath[i+2]});
		for(int i = 0; i < outpath.size()-2; i+=2) outpath_horizontal.push_back({outpath[i+1], outpath[i], outpath[i+2]});
		for(int i = 1; i < outpath.size()-2; i+=2) outpath_vertical.push_back({outpath[i+1], outpath[i], outpath[i+2]});
		ans_coord = min(ans_coord, solve(inpath_vertical, outpath_horizontal, r, c, 0));
		ans_coord = min(ans_coord, solve(inpath_horizontal, outpath_vertical, c, r, 1));
		if(ans){
			cout << ans << ' ' << ans_coord.first << ' ' << ans_coord.second << '\n';
		}
		else cout << "impossible\n";
	}
}