시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 607 | 232 | 186 | 42.081% |
악명높은 의사 House는 환자를 치료할 때 죽을 환자는 버리고 살 환자는 살린다. 중상을 입어 거의 죽을 고비에 다다른 환자만이 그에게 맡겨지는데, 이러한 환자에게서는 여러 가지 증세가 동시에 관측되곤 한다.
House에게는 이러한 증세들 중 두 가지가 동시에 관측될 때면 환자가 죽게 된다는 규칙을 정리해 둔 표가 있다. 이를테면, 뇌출혈과 복막염이 동시에 관측되면 그 환자는 죽게 된다는 규칙이나, 뇌출혈이 일어나지 않는 상태와 불면증이 동시에 관측되면 그 환자는 죽게 된다는 규칙 등이 기록되어 있다.
그런데 최근 House의 손에 맡겨진 환자가 너무 많이 죽어나가는 바람에, House의 규칙이 너무 가혹해서 살아남을 수 있는 환자가 없는 건 아닌지 검사해야 할 필요가 생겼다.
House의 규칙이 주어지면, 이러한 규칙에 의거해서 과연 살아남을 수 있는 환자가 존재하는지, 아니면 이 규칙에 따르면 모든 환자가 죽을 수밖에 없는지를 알아내는 프로그램을 작성하시오.
입력은 여러 개의 테스트 데이터들로 구성되어 있다. 각 데이터의 첫 줄에는 House의 규칙의 개수 N, 증세의 종류 M이 빈 칸을 사이에 두고 주어진다. 다음 줄부터 N개의 줄에 걸쳐 House의 규칙에 대한 정보가 주어진다. 규칙은 두 개의 수로 표현되는데, 각 수는 상태를 나타낸다. 상태의 절댓값은 증세의 번호를 나타내며, 1 이상 M 이하이다. 상태가 양수이면 해당되는 증세가 관측되는 상태를 의미하고, 음수이면 관측되지 않는 상태를 의미한다. 두 개의 상태가 동시에 만족되면 환자는 죽는다. (N ≤ 200,000, M ≤ 20,000)
예를 들어 House의 규칙이 2 -3이라면, 증세 2가 일어나고 동시에 증세 3이 일어나지 않은 경우 환자가 죽게 된다는 뜻이다.
데이터의 끝은 0 0으로 주어진다. 즉 N과 M이 0으로 주어지면 입력을 종료하면 된다.
첫째 줄부터 각 테스트 데이터마다 한 줄에 규칙에서 살아남을 수 있는 사람이 있으면 1을, 살아남는 게 불가능한 경우 0을 출력한다.
3 3 1 -2 2 3 -3 -1 4 2 1 2 1 -2 -1 2 -1 -2 0 0
1 0