247 . 放石頭

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

76.9% (20/26)

Tags

ioicamp ioicamp-2020

Description

小明喜歡放石頭在數線的整數點上，於是老師給了小明一條長度為 $n$ 的數線跟 $q$ 個條件，希望小名可以放一些石頭在數線上滿足所有條件。每個條件的格式如下：

  1. $[a, b] \le c$，代表說 $a$ 到 $b$ 的石頭數量不多於 $c$
  2. $[a, b] \ge c$，代表說 $a$ 到 $b$ 的石頭數量不少於 $c$

小明只能在 $1, 2, \dots, n$ 放石頭。小明被難倒了。你能幫助他嗎？

Input Format

第一行有兩個正整數 $n, q$ 代表數線長度和條件數量。

接下來有 $q$ 行，每行有三個整數 $a_i, b_i, c_i$。$a_i, b_i, c_i$ 的正負號號都一樣。如果都是正數，那這行代表的條件就是 $[a_i, b_i] \le c_i$。反之，這行代表的條件是 $[-a_i, -b_i] \ge -c_i$。

  • $1\le n, q \le 5000$
  • $-n \le a_i, b_i \le n$
  • $a_i, b_i \neq 0$
  • $|a_i| \le |b_i|$
  • $-10^ 6 \le c_i \le 10^ 6$

Output Format

如果無解，輸出一行 $-1$。

如果有解，輸出 $n$ 行，第 $i$ 行輸出 $0$ 或 $1$，代表說數線上第 $i$ 個點有沒有放石頭。

若有多組合法的解，輸出任意一組即可。

Sample Input 1

10 4
4 7 2
4 8 2
-2 -10 -3
-4 -5 -1

Sample Output 1

1
1
1
1
1
0
0
0
1
1

Sample Input 2

10 4
5 10 5
1 3 1
-10 -10 -1
-1 -4 -3

Sample Output 2

-1

Hints

Problem Source

IOICamp 2020 Day3 pB

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~101 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 2
1 4000 262144 65536 1 2
2 4000 262144 65536 2
3 4000 262144 65536 2
4 4000 262144 65536 2
5 4000 262144 65536 2
6 4000 262144 65536 2
7 4000 262144 65536 2
8 4000 262144 65536 2
9 4000 262144 65536 2
10 4000 262144 65536 2
11 4000 262144 65536 2
12 4000 262144 65536 2
13 4000 262144 65536 2
14 4000 262144 65536 2
15 4000 262144 65536 2
16 4000 262144 65536 2
17 4000 262144 65536 2
18 4000 262144 65536 2
19 4000 262144 65536 2
20 4000 262144 65536 2
21 4000 262144 65536 2
22 4000 262144 65536 2
23 4000 262144 65536 2
24 4000 262144 65536 2
25 4000 262144 65536 2
26 4000 262144 65536 2
27 4000 262144 65536 2
28 4000 262144 65536 2
29 4000 262144 65536 2
30 4000 262144 65536 2
31 4000 262144 65536 2
32 4000 262144 65536 2
33 4000 262144 65536 2
34 4000 262144 65536 2
35 4000 262144 65536 2
36 4000 262144 65536 2
37 4000 262144 65536 2
38 4000 262144 65536 2
39 4000 262144 65536 2
40 4000 262144 65536 2
41 4000 262144 65536 2
42 4000 262144 65536 2
43 4000 262144 65536 2
44 4000 262144 65536 2
45 4000 262144 65536 2
46 4000 262144 65536 2
47 4000 262144 65536 2
48 4000 262144 65536 2
49 4000 262144 65536 2
50 4000 262144 65536 2
51 4000 262144 65536 2
52 4000 262144 65536 2
53 4000 262144 65536 2
54 4000 262144 65536 2
55 4000 262144 65536 2
56 4000 262144 65536 2
57 4000 262144 65536 2
58 4000 262144 65536 2
59 4000 262144 65536 2
60 4000 262144 65536 2
61 4000 262144 65536 2
62 4000 262144 65536 2
63 4000 262144 65536 2
64 4000 262144 65536 2
65 4000 262144 65536 2
66 4000 262144 65536 2
67 4000 262144 65536 2
68 4000 262144 65536 2
69 4000 262144 65536 2
70 4000 262144 65536 2
71 4000 262144 65536 2
72 4000 262144 65536 2
73 4000 262144 65536 2
74 4000 262144 65536 2
75 4000 262144 65536 2
76 4000 262144 65536 2
77 4000 262144 65536 2
78 4000 262144 65536 2
79 4000 262144 65536 2
80 4000 262144 65536 2
81 4000 262144 65536 2
82 4000 262144 65536 2
83 4000 262144 65536 2
84 4000 262144 65536 2
85 4000 262144 65536 2
86 4000 262144 65536 2
87 4000 262144 65536 2
88 4000 262144 65536 2
89 4000 262144 65536 2
90 4000 262144 65536 2
91 4000 262144 65536 2
92 4000 262144 65536 2
93 4000 262144 65536 2
94 4000 262144 65536 2
95 4000 262144 65536 2
96 4000 262144 65536 2
97 4000 262144 65536 2
98 4000 262144 65536 2
99 4000 262144 65536 2
100 4000 262144 65536 2
101 4000 262144 65536 2
Submit
Back to Top