시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 3 | 2 | 2 | 66.667% |
Currently, there are $n$ galactic governments in the $k$-dimensional cubic universe. The universe is a cube with two opposite vertices $(0, \ldots, 0)$ and $(C, \ldots, C)$ and sides parallel to coordinate axes. Formally, the set of points in the universe is $$U = \{(x_1, \ldots, x_k) \in \mathbb{R}^k \colon 0 \le x_i \le C\}\text{.}$$
Each galactic government claims that its territory is a parallelepiped with sides parallel to coordinate axes. The $i$-th government claims a parallelepiped with two opposite vertices $(a_{i,1}, \ldots, a_{i,k})$ and $(b_{i,1}, \ldots, b_{i,k})$ such that $a_{i,j} < b_{i,j}$ for all $j$. Formally, the $i$-th government claims the set of points $$G_i = \{(x_1, \ldots, x_k) \in U \colon a_{i,j} \le x_j \le b_{i,j}\}\text{.}$$
Note that some pieces of territory can be claimed by multiple governments.
Rick tries to find a point which is not claimed by any of the galactic governments. He has noticed that $a_{i,j}$ is an integer for all $i$ from $1$ to $n$ and all $j$ from $1$ to $k$. Rick knows that it implies that an unclaimed point exists if and only if there exists an unclaimed point $\left(\alpha_1 + \frac{1}{2}, \alpha_2 + \frac{1}{2}, \ldots, \alpha_k + \frac{1}{2}\right)$ where $\alpha_i$ are all integers. Rick likes integers, so he asks you to find $\alpha_1, \ldots, \alpha_k$ such that $\left(\alpha_1 + \frac{1}{2}, \alpha_2 + \frac{1}{2}, \ldots, \alpha_k + \frac{1}{2}\right)$ is a point in the universe and it does not belong in any of the $G_1, \ldots, G_n$. If there are multiple such points, Rick wants to find the lexicographically smallest one.
Point $\left(\beta_1 + \frac{1}{2}, \ldots, \beta_k + \frac{1}{2}\right)$ is lexicographically smaller than $\left(\gamma_1 + \frac{1}{2}, \ldots, \gamma_k + \frac{1}{2}\right)$ if there exists such $j$ ($1 \le j \le k$) such that for all $i < j$ we have $\beta_i = \gamma_i$, and $\beta_j < \gamma_j$.
The first line contains three integers $n$, $k$, and $C$ ($1 \le n \le 18$, $1 \le k \le 10$, $1 \le C \le 1000$). The $i$-th of the next $n$ lines contains $2 k$ integers: $a_{i,1}, \ldots, a_{i,k}, \; b_{i,1}, \ldots, b_{i,k}$ ($0 \le a_{i,j} < b_{i,j} \le C$ for every $j$ from $1$ to $k$).
Print "NO
" if all points in the universe are claimed by galactic governments. Otherwise, print "YES
" on the first line, and on the second line, print $k$ integers $\alpha_1, \ldots, \alpha_k$ such that $\left(\alpha_1 + \frac{1}{2}, \alpha_2 + \frac{1}{2}, \ldots, \alpha_k + \frac{1}{2}\right)$ is a point in the universe and it does not belong in any of the $G_1, \ldots, G_n$. If there are multiple solutions, print the lexicographically smallest one.
2 2 3 0 0 2 2 1 1 3 3
YES 0 2
1 3 5 0 0 0 5 5 5
NO