취미로 코딩하기

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

이번에 볼 문제는 백준 20942번 문제인 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회이다.
문제는 아래 링크를 확인하자.

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

각 참가자의 나이를 이진수로 표현하면 1의자리, 2의자리, 4의자리, 8의자리, 16의자리의 다섯개의 비트로 표현이 가능하다. 각 나이의 비트가 0인지 1인지를 TF로 생각하고, 문제에서 주어진 조건들을 적절히 명제로 바꿔 주어진 문제를 2-SAT 문제로 모델링할 수 있다.

먼저 각 나이는 8 이상 19 이하이므로, 16의 자리 비트가 0이라면 8의 자리 비트가 1이어야하고, 1이라면 8의 자리와 4의 자리 비트가 0이 되어야 한다. 위의 조건만 만족한다면 다섯 개의 비트가 나타내는 수는 항상 8 이상 19 이하가 된다.

두 정수를 and 또는 or연산을 했을 때 나오는 수에 대한 명제 또한 비트별로 떼어 5개의 명제로 구분할 수 있다.

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

#define NODE 500001
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N, gap; // 2-SAT 정점개수(TF분할 말고), T와F노드 사이 값의 차이
vector<int> G[NODE];
int dfi[NODE]; int dfidx = 1;
int sci[NODE]; int scidx = 1;
vector<int> stk;
int twosatdfs(int current) {
	stk.emplace_back(current);
	int ret = dfi[current] = dfidx++;
	for (auto node : G[current]) {
		if (sci[node]) continue;
		if (dfi[node]) ret = min(ret, dfi[node]);
		else ret = min(ret, twosatdfs(node));
	}

	if (ret == dfi[current]) {
		while (stk.back() != current) {
			sci[stk.back()] = scidx;
			stk.pop_back();
		}
		sci[stk.back()] = scidx++;
		stk.pop_back();
	}

	return ret;
}

bool ans[NODE];
bool TWOSAT() {
	for (int i = 1; i <= N; i++) {
		if (sci[i]) continue;
		twosatdfs(i);
	}
	for (int i = 1 + gap; i <= N + gap; i++) {
		if (sci[i]) continue;
		twosatdfs(i);
	}
	
	for (int i = 1; i <= N; i++) {
		if (sci[i] < sci[i + gap]) ans[i] = 1;
		else if (sci[i] > sci[i + gap]) ans[i] = 0;
		else return 0;
	}
	return 1;
}

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

	cin >> N; N *= 5;
	gap = 250000;
	for (int i = 1; i < N; i += 5) {
		G[i + 4].emplace_back(gap + i + 3);
		G[i + 3].emplace_back(gap + i + 4);
		G[i + 4].emplace_back(gap + i + 2);
		G[i + 2].emplace_back(gap + i + 4);
		G[gap + i + 4].emplace_back(i + 3);
		G[gap + i + 3].emplace_back(i + 4);

		int x; cin >> x;
		if (x == 0) continue;
		if (x & 1) G[gap + i].emplace_back(i);
		else G[i].emplace_back(gap + i);
		if (x & 2) G[gap + i + 1].emplace_back(i + 1);
		else G[i + 1].emplace_back(gap + i + 1);
		if (x & 4) G[gap + i + 2].emplace_back(i + 2);
		else G[i + 2].emplace_back(gap + i + 2);
		if (x & 8) G[gap + i + 3].emplace_back(i + 3);
		else G[i + 3].emplace_back(gap + i + 3);
		if (x & 16) G[gap + i + 4].emplace_back(i + 4);
		else G[i + 4].emplace_back(gap + i + 4);
	}

	int M; cin >> M;
	while (M--) {
		char c; int x, y, z; cin >> c >> x >> y >> z;
		int xi = (x - 1) * 5 + 1, yi = (y - 1) * 5 + 1;
		if (c == '&') {
			if (z & 1) {
				G[gap + xi].emplace_back(xi);
				G[gap + yi].emplace_back(yi);
			}
			else {
				G[xi].emplace_back(yi + gap);
				G[yi].emplace_back(xi + gap);
			}
			if (z & 2) {
				G[gap + xi + 1].emplace_back(xi + 1);
				G[gap + yi + 1].emplace_back(yi + 1);
			}
			else {
				G[xi + 1].emplace_back(yi + gap + 1);
				G[yi + 1].emplace_back(xi + gap + 1);
			}
			if (z & 4) {
				G[gap + xi + 2].emplace_back(xi + 2);
				G[gap + yi + 2].emplace_back(yi + 2);
			}
			else {
				G[xi + 2].emplace_back(yi + gap + 2);
				G[yi + 2].emplace_back(xi + gap + 2);
			}
			if (z & 8) {
				G[gap + xi + 3].emplace_back(xi + 3);
				G[gap + yi + 3].emplace_back(yi + 3);
			}
			else {
				G[xi + 3].emplace_back(yi + gap + 3);
				G[yi + 3].emplace_back(xi + gap + 3);
			}
			if (z & 16) {
				G[gap + xi + 4].emplace_back(xi + 4);
				G[gap + yi + 4].emplace_back(yi + 4);
			}
			else {
				G[xi + 4].emplace_back(yi + gap + 4);
				G[yi + 4].emplace_back(xi + gap + 4);
			}
		}
		else {
			if (z & 1) {
				G[gap + xi].emplace_back(yi);
				G[gap + yi].emplace_back(xi);
			}
			else {
				G[xi].emplace_back(gap + xi);
				G[yi].emplace_back(gap + yi);
			}
			if (z & 2) {
				G[gap + xi + 1].emplace_back(yi + 1);
				G[gap + yi + 1].emplace_back(xi + 1);
			}
			else {
				G[xi + 1].emplace_back(gap + xi + 1);
				G[yi + 1].emplace_back(gap + yi + 1);
			}
			if (z & 4) {
				G[gap + xi + 2].emplace_back(yi + 2);
				G[gap + yi + 2].emplace_back(xi + 2);
			}
			else {
				G[xi + 2].emplace_back(gap + xi + 2);
				G[yi + 2].emplace_back(gap + yi + 2);
			}
			if (z & 8) {
				G[gap + xi + 3].emplace_back(yi + 3);
				G[gap + yi + 3].emplace_back(xi + 3);
			}
			else {
				G[xi + 3].emplace_back(gap + xi + 3);
				G[yi + 3].emplace_back(gap + yi + 3);
			}
			if (z & 16) {
				G[gap + xi + 4].emplace_back(yi + 4);
				G[gap + yi + 4].emplace_back(xi + 4);
			}
			else {
				G[xi + 4].emplace_back(gap + xi + 4);
				G[yi + 4].emplace_back(gap + yi + 4);
			}
		}
	}

	if (TWOSAT()) {
		cout << 1 << '\n';
		for (int i = 1; i < N; i += 5) {
			cout << ans[i] + 2 * ans[i + 1] + 4 * ans[i + 2] + 8 * ans[i + 3] + 16 * ans[i + 4] << ' ';
		}
	}
	else cout << 0;
}