TopCoder

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

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

42.9% (3/7)

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

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