NOI '22 Multi-Provincial Team Selection P3 - Community

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

Tommy discovers the relics of m messages [X1,X2,,Xm] corresponding to n clowns participating in a forum thread. A message Xi can be described by three strings Xi 1,Xi 2,Xi 3. Tommy will reorder the m messages into some sequence [Y1,Y2,,Ym]. A message Yi is good if and only if either

  • im, Yi 3=`loushang' and Yi 2=Yi+1 1
  • i1, Yi 3=`louxia' and Yi 2=Yi1 1

Find any ordering of the m given messages that maximizes the number of good messages.

Let S={Xi 1:1im}. The test data guarantees that |S|=n and that for any Xi 1, there exists j such that Xj 1=Xi 1 and Xj 3{`loushang',`louxia'}.

Constraints

The input consists of T100 individual test cases.

For each test case, 1nm77777.

Over all test cases, m2.5×105.

The length of any token of input will not exceed 12 ASCII characters.

50% of points will be granted for finding the maximum number of good messages but failing to find a valid ordering.

T M M Test Prop. A Prop. B Prop. C
5 10 50 1 / / /
10 16 160 2 / / /
30 2222 15000 3, 4 Y Y Y
30 2222 15000 5, 6 Y / Y
30 2222 15000 7, 8, 9 / Y Y
30 2222 15000 10, 11 / / Y
30 2222 15000 12, 13 / / /
100 77777 2.5×105 14, 15 Y Y Y
100 77777 2.5×105 16 Y / Y
100 77777 2.5×105 17, 18, 19 / Y Y
100 77777 2.5×105 20, 21, 22 / / Y
100 77777 2.5×105 23, 24, 25 / / /

Property A: There is no i where Xi 3=`loushang' and Xi 2S.

Property B: There exists an ordering such that all i where Xi 3{`loushang',`louxia'} and Xi 2S, are good messages.

Property C: There exists no pair 1i,jm where Xi 1=Xj 2, Xi 2=Xj 1, Xi 3=`loushang', and Xj 3=`louxia'.

Input Specification

The first line contains a positive integer T, the number of test cases. For each test case:

The first line contains two positive integers n and m, the number of clowns and the number of messages, respectively.

The following n lines contain the names of the clowns.

The following m lines contain three strings Xi 1, Xi 2, and Xi 3, describing message Xi.

Output Specification

For each test case:

On the first line output an integer, corresponding to the maximum number of good messages.

On the second line output m distinct integers a1,a2,,am from 1 to m, corresponding to an ordering of the messages, i.e. Yi=Xai.

Sample Input

Copy
2
4 15
builtin_clz
builtin_ctz
jinkela
OrzTourist
builtin_clz MengXin QiuZhu
builtin_ctz builtin_clz louxia
jinkela builtin_ctz louxia
builtin_ctz builtin_clz loushang
builtin_clz BieMoZheng YaoXueShu
OrzTourist builtin_clz louxia
OrzTourist OrzTourist louxia
builtin_clz Iam Angry!
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_ctz Xue Shu
jinkela Xue Shu
OrzTourist Xue Shu
1 9
builtin_clz
builtin_clz builtin_clz loushang
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz Loushang
builtin_clz builtin_clz LOUSHANG
builtin_clz Builtin_clz loushang
builtin_clz loushang louxia
builtin_clz builtin_clz builtin_clz
builtin_clz loushang builtin_clz

Sample Output

Copy
9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3
8 1 2 7 9 3 6 4 5

Attachments


Comments

There are no comments at the moment.