247 . 放石頭

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
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]≤c，代表說 a 到 b 的石頭數量不多於 c
  2. [a,b]≥c，代表說 a 到 b 的石頭數量不少於 c

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

Input Format

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

接下來有 q 行，每行有三個整數 ai,bi,ci。ai,bi,ci 的正負號號都一樣。如果都是正數，那這行代表的條件就是 [ai,bi]≤ci。反之，這行代表的條件是 [−ai,−bi]≥−ci。

  • 1≤n,q≤5000
  • −n≤ai,bi≤n
  • ai,bi≠0
  • |ai|≤|bi|
  • −106≤ci≤106

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