취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24539번 문제인 암호 해독이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24539

만약 주어지는 모든 구간의 오른쪽 끝이 서로 다르다면 구간들을 오른쪽 끝 오름차순으로 순회하면서 구간 xor이 조건을 만족하도록 값을 하나씩 할당하는 것으로 문제를 해결할 수 있을 것이다. 오른쪽 끝이 같은 경우를 효율적으로 제거해 문제를 해결하자.

구체적으로, 오른쪽 끝이 같은 여러 구간이 있을 경우, 그 중 (길이가 다른) 두 구간은 짧은 구간과 (긴 구간 - 짧은 구간)의 xor 정보로 대체하는 것으로 모든 구간의 오른쪽 끝이 같은 경우를 없애자. 물론 길이가 같은 두 구간의 경우 서로 값이 같아야 함을 확인해야 한다.

단, 위 과정을 아무 생각 없이 구현하면 구간 쪼개기를 $O(N^2$)번 하게 되어 문제가 생긴다. 오른쪽 끝 내림차순으로 보면서, 같은 오른쪽 끝을 가진 구간들을 왼쪽 끝 순으로 정렬해 인접한 두 구간에 대해서만 계산해 구간 쪼개기를 진행하면 총 $O(N)$회만 쪼개게 되어 문제를 안정적으로 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<pair<int, int>> vec[200001];
int A[200001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int x, y, k; cin >> x >> y >> k;
		vec[y].emplace_back(make_pair(x, k));
	}

	for (int R = N; R > 0; R--) {
		auto &v = vec[R];
		if (v.empty()) continue;
		int vsize = v.size();
		sort(v.begin(), v.end());
		for (int i = 0; i + 1 < vsize; i++) {
			if (v[i].first == v[i + 1].first) {
				if (v[i].second == v[i + 1].second) continue;
				cout << -1;
				return 0;
			}
			vec[v[i + 1].first - 1].emplace_back(make_pair(v[i].first, v[i].second ^ v[i + 1].second));
		}
	}

	for (int i = 1; i <= N; i++) {
		if (!vec[i].empty()) A[i] = A[vec[i].back().first - 1] ^ A[i - 1] ^ vec[i].back().second;
		cout << A[i] << ' ';
		A[i] ^= A[i - 1];
	}
}

랜덤 마라톤 · 코스 12 G번