시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.6 초 | 1024 MB | 75 | 19 | 15 | 27.273% |
Your task is to determine one possible binary array A of length N that abides by M given constraints of the form:
The first line of input contains two integers N and M (1 ≤ N ≤ 5 000, 1 ≤ M ≤ 10 000) - the length of array A and the number of constraints.
The next M lines describe the constraints. Each line contains four integers li, ri, ki, valuei, describing the i-th constraint.
The first line of the output contains N integers - one possible binary array A. If there are several that abide by all M constraints you may output any of them. If there is no such array you must instead output the single integer -1.
번호 | 배점 | 제한 |
---|---|---|
1 | 7 | 1 ≤ N ≤ 18, 1 ≤ M ≤ 200 |
2 | 13 | 1 ≤ N ≤ 5 000, 1 ≤ M ≤ 10 000, for all constraints k = 1 holds |
3 | 25 | 1 ≤ N ≤ 5 000, 1 ≤ M ≤ 10 000, for all constraints k = 1 or k = (r - l + 1) holds |
4 | 55 | 1 ≤ N ≤ 5 000, 1 ≤ M ≤ 10 000 |
4 5 0 1 2 1 0 2 2 0 2 2 1 0 0 1 1 0 1 2 1 0
0 1 0 0
There are several binary arrays that abide by all the constraints. One of them is 0 1 0 0 because: