TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

41.7% (5/12)

Description

有$n$個蘿莉參加了一場賣萌大賽。這個賣萌大賽的賽制採積分回合賽制,並包含了$m$個回合。規則如下:

每一個回合都會指定兩個蘿莉上台,看看誰比較會賣萌。每一回合都會進行「顏值比拼」和「撒嬌比賽」兩種:在「顏值比併」中,贏家會被加1分積分、輸家會被扣1分積分;然而,做為一個蘿莉,會撒嬌比較重要,因此在「撒嬌比賽」中,輸贏家獲得或失去的分數都雙倍計算。
身為比賽裁判的你,在看著蘿莉們賣萌而流口水之際,也不想要讓任何蘿莉因為分數太高而驕傲地轉變成御姐屬性,更不想要任何蘿莉因為分數太低而傷心欲絕。所以你想要盡可能地將所有蘿莉的分數控制在-1到1之間。當然,裁判,也就是你,有權力決定每一個回合的勝負。

雖然這看起來不一定可行,不過聰明的你發現每個蘿莉所參加的回合權重和都是奇數。你可以寫一個程式安排比賽的勝負嗎?

Input Format

第一行有兩個正整數n, m,分別代表蘿莉的個數和賣萌大賽的回合數。這n個蘿莉從0編號到n-1。
接下來的m行,每行有三個整數ai, bi, ki,依序參加第i回合比賽的蘿莉ai和bi,以及本回合的的回合種類ki:1代表「顏值比併」、2代表「撒嬌大賽」。
對於所有測資,$2\leq n\leq 10^ 6; \frac{n}{2}\leq m\leq 10^ 6;$
$0\leq a_i < b_i \leq n-1; 1\leq k_i\leq 2$。

子任務(測資) 額外限制 分數
1 (0~4) $m\leq 20$ 11
2 (5~10) $n\leq 4$ 7
3(11~14) 沒有撒嬌比賽 14
4(15~19) 每個蘿莉參加的回合數至多為2 28
5 (20~24) 40

Output Format

請輸出1行包含m個0或1的字串。如果第i個字元是0,代表第i回合的贏家是ai;反之,如果第i個字元是1,代表第i回合的贏家是bi

你可以假設本題一定有解。
當然,解不一定是唯一的,你只要輸出一組滿足條件的解就可以了。

Sample Input

4 8
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
0 1 2
2 3 2

Sample Output

01001011

Hints

對於範例輸出所示的安排方法,0的積分為-1、1的積分為1、2的積分為-1、3的積分為1。
當然,不只有這一種安排方法。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校隊選拔:複試pF
題目取自USATST2011p2:
https://www.artofproblemsolving.com/community/c6h420424p2374799

Subtasks

No. Testdata Range Score
1 0~4 11
2 5~10 7
3 11~14 14
4 15~19 28
5 20~24 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 1
2 1000 131072 262144 1
3 1000 131072 262144 1
4 1000 131072 262144 1
5 1000 131072 262144 2
6 1000 131072 262144 2
7 1000 131072 262144 2
8 1000 131072 262144 2
9 1000 131072 262144 2
10 1000 131072 262144 2
11 1500 131072 262144 3
12 1500 131072 262144 3
13 1500 131072 262144 3
14 1500 131072 262144 3
15 1500 131072 262144 4
16 1500 131072 262144 4
17 1500 131072 262144 4
18 1500 131072 262144 4
19 1500 131072 262144 4
20 1500 131072 262144 5
21 1500 131072 262144 5
22 1500 131072 262144 5
23 1500 131072 262144 5
24 1500 131072 262144 5