동아리 부스 배치
플래티넘 I의견: 0
축제에서 \(N\)개의 동아리가 각자 부스를 운영한다. 각 동아리는 부스를 실내(0) 또는 실외(1) 중 한 곳에 배치해야 한다.
주최 측에는 \(M\)개의 요구사항이 있다. 각 요구사항은 두 개의 조건 중 적어도 하나가 만족되어야 한다는 형태이다. 하나의 조건은 "동아리 \(i\)를 실내에 둔다" 또는 "동아리 \(i\)를 실외에 둔다" 중 하나이다.
모든 요구사항을 동시에 만족하는 배치가 존재하는지 판별하고, 존재한다면 그러한 배치 하나를 출력하여라.
\(1 \le N \le 100{,}000\)
\(1 \le M \le 200{,}000\)
\(1 \le |a|, |b| \le N\)
첫 줄에 동아리 수 \(N\)과 요구사항 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어진다. 정수 \(x\)가 양수이면 "동아리 \(|x|\)를 실외(1)에 둔다"는 조건을, 음수이면 "동아리 \(|x|\)를 실내(0)에 둔다"는 조건을 의미한다. 각 요구사항은 두 조건 \(a\), \(b\) 중 적어도 하나가 만족되어야 한다.
모든 요구사항을 만족하는 배치가 존재하면 첫 줄에 \(1\)을, 둘째 줄에 동아리 \(1\)부터 \(N\)까지의 배치(\(0\) 또는 \(1\))를 공백으로 구분해 출력한다. 존재하지 않으면 첫 줄에 \(0\)만 출력한다. 여러 답이 가능하면 아무 것이나 출력한다.
3 3
1 2
-1 2
-2 3
1
0 1 1요구사항: (1을 실외) 또는 (2를 실외); (1을 실내) 또는 (2를 실외); (2를 실내) 또는 (3을 실외). 첫 두 요구사항에서 2는 실외여야 하고(둘 다 2 실외를 공통으로 가능케 함), 세 번째에서 2가 실외이므로 3은 실외여야 한다. 동아리1은 자유. 한 가지 답이 출력된다.
1 2
1 1
-1 -1
0첫 요구사항은 동아리1을 실외에, 둘째 요구사항은 동아리1을 실내에 두라고 강제한다. 둘을 동시에 만족할 수 없으므로 배치가 불가능하다. 0을 출력한다.
플래티넘 Vriseoj 작성
출처 Original
평가 및 의견
동아리 부스 배치
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
동아리 부스 배치