hun3555   2년 전

게시판에 있는 반례들 다 넣어봤는데 문제가 없는거 같은데 20퍼에서 계속 틀리네요


들어오는 논리식을 && 단위로 구분한 다음

==인 식들에 대해서는 union-find로 합쳐줬고

!=인 식들은 나중에 처리하려고 저장했습니다

==인 식을 다 처리한 후에는 같은 단항식들을 전부 모은 다음

해당 단항식들 중 길이가 가장 짧은 것, 그리고 만일 있다면 해당 단항식들의 값을 찾아서 == 관계를 전부 찾아주었고

(이 과정 중 정수가 두번 나오면 항상 거짓인 논리식이니 1==0을 출력하고 종료)

이후 !=인 식들을 해당 길이가 가장 짧은 단항식으로 바꿔서 처리했습니다

만일 !=로 연결된 두 값이 서로 같거나 ==로 연결된 두 값이 서로 다르면 1==0을 출력하였고

!=인 식들을 처리할 때도 해당 식이 처리되었는지 여부를 acted라는 set에 이들을 구분할 값을 집어넣어서 처리했습니다

만일 모든 식을 처리하고 나서 처리한 식 목록이 비었을 경우 1==1을 출력하였습니다

코드가 난잡하지만 게시판에서 확인한 반례들은 다 넣어보았고 제대로 출력되는거 같은데

뭐가 문제일까요

ediya   2년 전

반례드립니다.

 INPUT : ab==cde&&abc==de&&a!=bcde&&abcd!=e

WA : ab==cde&&abc==de&&a!=bcde

ANS : abc==de&&cde==ab&&e!=abcd&&bcde!=a

!= 처리할때 key방식을 다시 짜면 통과 할 것 같습니당

저도 이문제 푸느라 되게 고생 많이했는데 도움이 됐으면 좋겠네요!

hun3555   2년 전

감사합니다

!= 처리할때 문제가 있는걸 알고 뒤늦게 key 방식을 추가하다가 잘못 짰네요

고쳐봐야겠네요

댓글을 작성하려면 로그인해야 합니다.