Thi tuyển dụng

--- tags: Propose for Bedao --- # Thi tuyển dụng ## Statement Korn là một lập trình viên ~~giỏi~~ thất nghiệp, nhưng anh lại rất tự cao. Hôm nay anh tham gia phỏng vấn tại công ty công nghệ mới nổi mang tên Biker. Tại đây, anh được yêu cầu xây dựng một dãy nhị phân được độ dài $n$ thỏa mãn $q$ tính chất. Mỗi tính chất gồm 6 số nguyên $i_1,v_1,i_2,v_2,i_3,v_3$ ($1\le i_1<i_2<i_3\le n$, $0\le v_1,v_2,v_3\le1$) với ý nghĩa: - Giá trị của bit thứ $i_1$ là $v_1$ - Giá trị của bit thứ $i_2$ là $v_2$ - Giá trị của bit thứ $i_3$ là $v_3$ Một tính chất gọi là được thỏa mãn nếu **ít nhất hai điều kiện trong ba điều kiện trên đúng**. Để được nhận vào làm, Korn cần phải vượt qua bài kiểm tra một cách xuất sắc. Tuy nhiên do ~~thât nghiệp quá lâu~~ quá giỏi, anh ta không ~~biết~~ làm mà lại đi ~~nhờ bạn làm giúp~~ thách đố bạn làm được. Yêu cầu: Bạn hãy tìm một dãy nhị phân thỏa mãn các điều kiện trên để cho Korn hét tự cao nhé. ## Input - Dòng đầu tiên chứa hai số nguyên dương $n,q$ $(1\le n,q\le 10^5)$ là độ dài dãy nhị phân và số yêu cầu. - $q$ dòng tiép, mỗi dòng chứa 6 số nguyên $i_1,v_1,i_2,v_2,i_3,v_3$ ($1\le i_1<i_2<i_3\le n$, $0\le v_1,v_2,v_3\le1$) cho biết một yêu cầu. ## Output Nếu không thể dựng được dãy nhị phân như vậy, hãy in ra `-1`. Ngược lại, in ra xâu nhị phân tìm được. ## Example | Input | Output | | --------- | ------ | | 7 5 3 0 5 0 6 11 1 2 1 3 04 0 5 1 6 15 0 6 1 7 11 0 2 0 4 0 |1000111| ## Scoring - Có 30% số điểm của bài với $n\le 20$ - Có 30% số điểm khác với $n\le 40$ - Còn lại không có điều kiện gì thêm # Solution Mỗi yêu cầu có thể được hiểu là các biểu thức logic: - $(v_1 \neq i_1) \rightarrow (v_2 = i_2) AND (v_3 = i_3)$ - $(v_2 \neq i_2) \rightarrow (v_1 = i_1) AND (v_3 = i_3)$ - $(v_3 \neq i_3) \rightarrow (v_2 = i_2) AND (v_1 = i_1)$ Khi đó, ta có thể đưa bài toán về giải phương trình đồng dư tuyến tính $n$ ẩn dạng chuẩn tắc hội, trong đó mỗi tuyển sơ cấp chỉ gồm 2 mệnh đề sơ cấp. $\Rightarrow$ Twosat