259 . 彗星

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

ioicamp ioicamp-2020

Description

在遙遠的 202020 年，星際旅行已成常態，而在星球上架設觀星站是再自然不過的事情了。 有很多天文迷的日常休閒就是在某些觀星站架設好自己的望遠鏡，並拍下自己喜歡的彗星經過的景象。

然而你只是個在觀星站工作的小小工讀生，你每天的任務就是記下哪些天文迷拍完了他想要拍的彗星景象，並且開心的離開了。 你所管轄的觀星站一共有三個，而你會獲得 q 筆紀錄，分別如下：

  • 1 ti k z1 z2,⋯,zk 代表第一種紀錄：有一個人在 k 個觀星站架設了自己的望遠鏡，並在合計拍下共 ti 單位時間的彗星之後就會開心的離開。他所架設的觀星站編號分別為 z1,z2,⋯,zk。
  • 2 p t 代表第二種紀錄：彗星出現在 p 號觀星站，一共出現了 t 單位時間。
請對於每個第二種紀錄，回答哪些人因為那次彗星的出現而開心的離開了。

Input Format

輸入的第一行有一個正整數 q，接下來會有 q 行。令一個變數 ans，初始值為 0，請繼續往下看以了解如何維護這個變數 ans。

接下來的每一行，紀錄格式如題目敘述所表示，且兩兩之間以一個空格分開。

唯要注意的是，輸入為部份加密後的資料，其中 ti,zj,p,t 都經過加密，需將其對 ans xor 後才能獲得正確的輸入值。例如，在 ans=5 時輸入為 1 0 3 7 3 8 經過解密後的應該得到 1 5 3 2 6 13。

對於解密後的輸入，保證：

  • 1≤q≤300000
  • 1≤ti,t≤109
  • 1≤k,zj,p≤3

Output Format

對於每一筆第二種紀錄，請先輸出因為這次彗星的出現而開心的離開的人數，並接著增序輸出那些開心的離開的人的編號。第一個來的人編號是 1，第二個是 2，以此類推。所有整數以一個空格分開。

接著，將 ans 對所有開心的離開的人的編號取 xor，並更新 ans。例如，對於某一次第二種紀錄輸出為 6 3 5 6 9 10 14，那麼 ans=ans⊕3⊕5⊕6⊕9⊕10⊕14，其中 ⊕ 為 xor 運算子。

Sample Input 1

5
2 1 100
1 5 2 2 3
2 2 3
1 2 1 3
2 3 5

Sample Output 1

0
0
2 1 2

Sample Input 2

5
1 2 1 1
1 3 1 1
2 1 100
1 0 3 2 1 0
2 0 103

Sample Output 2

2 1 2
1 3

Hints

對於範例測資一，解密後的測資與解密前相同。

對於範例測資二，解密後的測資如下所示：

5
1 2 1 1
1 3 1 1
2 1 100
1 3 3 1 2 3
2 3 100

Problem Source

IOICamp 2020 Day4 pC

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 262144 65536 1 2
1 2500 262144 65536 1 2
2 2500 262144 65536 2
3 2500 262144 65536 2
4 2500 262144 65536 2
5 2500 262144 65536 2
6 2500 262144 65536 2
7 2500 262144 65536 2
8 2500 262144 65536 2
9 2500 262144 65536 2
10 2500 262144 65536 2
11 2500 262144 65536 2
12 2500 262144 65536 2
13 2500 262144 65536 2
14 2500 262144 65536 2
15 2500 262144 65536 2
16 2500 262144 65536 2
17 2500 262144 65536 2
18 2500 262144 65536 2
19 2500 262144 65536 2
20 2500 262144 65536 2
21 2500 262144 65536 2
22 2500 262144 65536 2
23 2500 262144 65536 2
24 2500 262144 65536 2
25 2500 262144 65536 2
26 2500 262144 65536 2
27 2500 262144 65536 2
28 2500 262144 65536 2
29 2500 262144 65536 2
30 2500 262144 65536 2
31 2500 262144 65536 2
32 2500 262144 65536 2
33 2500 262144 65536 2
34 2500 262144 65536 2
35 2500 262144 65536 2
36 2500 262144 65536 2
37 2500 262144 65536 2
38 2500 262144 65536 2
39 2500 262144 65536 2
40 2500 262144 65536 2
41 2500 262144 65536 2
42 2500 262144 65536 2
43 2500 262144 65536 2
44 2500 262144 65536 2
45 2500 262144 65536 2
46 2500 262144 65536 2
47 2500 262144 65536 2
48 2500 262144 65536 2
49 2500 262144 65536 2
50 2500 262144 65536 2
51 2500 262144 65536 2
52 2500 262144 65536 2
53 2500 262144 65536 2
54 2500 262144 65536 2
55 2500 262144 65536 2
56 2500 262144 65536 2
57 2500 262144 65536 2
58 2500 262144 65536 2
59 2500 262144 65536 2
60 2500 262144 65536 2
61 2500 262144 65536 2
62 2500 262144 65536 2
63 2500 262144 65536 2
64 2500 262144 65536 2
65 2500 262144 65536 2
66 2500 262144 65536 2
67 2500 262144 65536 2
68 2500 262144 65536 2
69 2500 262144 65536 2
70 2500 262144 65536 2
71 2500 262144 65536 2
72 2500 262144 65536 2
73 2500 262144 65536 2
74 2500 262144 65536 2
75 2500 262144 65536 2
76 2500 262144 65536 2
77 2500 262144 65536 2
78 2500 262144 65536 2
79 2500 262144 65536 2
80 2500 262144 65536 2
81 2500 262144 65536 2
82 2500 262144 65536 2
83 2500 262144 65536 2
84 2500 262144 65536 2
85 2500 262144 65536 2
86 2500 262144 65536 2
87 2500 262144 65536 2
88 2500 262144 65536 2
89 2500 262144 65536 2
90 2500 262144 65536 2
91 2500 262144 65536 2
92 2500 262144 65536 2
93 2500 262144 65536 2
94 2500 262144 65536 2
95 2500 262144 65536 2
96 2500 262144 65536 2
97 2500 262144 65536 2
98 2500 262144 65536 2
99 2500 262144 65536 2
100 2500 262144 65536 2
101 2500 262144 65536 2
102 2500 262144 65536 2
103 2500 262144 65536 2
104 2500 262144 65536 2
105 2500 262144 65536 2
106 2500 262144 65536 2
107 2500 262144 65536 2
108 2500 262144 65536 2
109 2500 262144 65536 2
110 2500 262144 65536 2
111 2500 262144 65536 2
112 2500 262144 65536 2
113 2500 262144 65536 2
114 2500 262144 65536 2
115 2500 262144 65536 2
116 2500 262144 65536 2
117 2500 262144 65536 2
118 2500 262144 65536 2
119 2500 262144 65536 2
120 2500 262144 65536 2
121 2500 262144 65536 2
122 2500 262144 65536 2
123 2500 262144 65536 2
124 2500 262144 65536 2
125 2500 262144 65536 2
126 2500 262144 65536 2
127 2500 262144 65536 2
128 2500 262144 65536 2
129 2500 262144 65536 2
130 2500 262144 65536 2
131 2500 262144 65536 2
Submit
Back to Top