To solve the first subtask, we can generate all possible true/false combinations and check if any satisfy all of the given restrictions.

Time complexity: ~\mathcal{O}(N \cdot 2^N)~

To solve the second subtask, all questions are in the form !p. Therefore, we can form a graph where the nodes are the question numbers. If question ~x~ is !y, an edge exists between questions ~x~ and ~y~. Now, all we need to check is if this graph is bipartite. We can accomplish this by colouring the graph with DFS.

Well-versed programmers may recognize the graph as a pseudoforest.

Time complexity: ~\mathcal{O}(N)~

For 100% of the points, note that this problem is simply a system of ~N~ equations and ~N~ boolean variables, where false is 0 and true is 1. Suppose question ~i~ is in the form j==k, then the equation would be ~i+j+k \equiv 1 \pmod{2}~. Similarly, if question ~i~ is in the form !j, the equation would be ~i+j \equiv 1 \pmod{2}~. Thus, we can use Gaussian elimination (modulo 2) to create a suitable form for finding answers.

Notice that during Gaussian elimination, a perfect solution remains perfect, while all other rejected solutions continue to fail on at least one equation (therefore, the set of solutions do not change). After Gaussian elimination, the next step is to interpret the results very carefully. You should consider all cases where the interpretation may skip over all perfect solutions.

Well-versed programmers may recognize this problem as XOR-satisfiability.

Corollary 1: The number of solutions is either 0, 1, or some other power of 2.

Corollary 2: You can obtain the lexicographically least/greatest solution (if a solution exists).

Time complexity: ~\mathcal{O}(N^3)~