小 H 的老師小 K 每次派測驗卷時總是會按分數從高到低派。若有多位同學的分數相同，他可以隨機調換這些同學的試卷的順序。
這一次測驗卷的滿分為 s，最低可能的分數是 0 分。小 K 還說出了這次測驗的得分情況，小 H 使用一個正整數 m 記下：
• 若 m=1，則這次測驗可能有多位同學的分數相同，也可能沒有。
• 若 m=2，則這次測驗所有同學的分數互不相同。
小 H 希望知道全班 n 位同學 (學號分別為 1,2,3,…,n) 的分數，但有些同學可能不情願告訴他。小 H 問了所有同學，只有部分同學願意告訴他分數。
他把這些同學的分數表示為一個長度為 n 的整數序列 a，其中，a[i]=-1 表示學號為 i 的同學不願透露自己的分數，否則 a[i] 表示他的分數。
小 H 記下了小 K 派卷的順序，第 i 份測驗卷派給了學號為 p[i] 的同學。
小 H 可以推測其他同學的分數的範圍。他已經把答案算了出來，但他還想考考你的計算能力。因此他要求你算出兩個整數序列 l,r。其中，對於所有滿足 1≤i≤n 的整數 i，l[i],r[i] 表示學號為 i 的同學的分數的範圍，即該同學的分數不可能比 l[i] 小且不可能比 r[i] 大。
由於這兩個序列太大，他不想和你對答案時太麻煩，因此他希望你計算以下兩個數值，以方便和他對答案：
• L=(1×l[1])⊕(2×l[2])⊕(3×l[3])⊕…⊕(n×l[n]) mod 232
• R=(1×r[1])⊕(2×r[2])⊕(3×r[3])⊕…⊕(n×r[n]) mod 232
其中，mod 是取餘運算，a mod b 即為 a 除以 b 所得的餘數。而 ⊕ 表示二進制按位異或運算。在 C++ 中，可以使用 ^ 運算符對兩個整數變量進行此運算。
你需要在標準輸入 (stdin) 讀入數據。
本題有多組測試數據。
輸入的第一行包含一個正整數 T，表示測試數據組數。
對於每組測試數據：
• 第一行包含三個正整數 n,m,s，以空格分隔。
• 第二行包含 n 個整數 p[1],p[2],p[3],…,p[n]，以空格分隔。
• 第三行包含 n 個整數 a[1],a[2],a[3],…,a[n]，以空格分隔。
你需要在標準輸出 (stdout) 輸出答案。
對於每組測試數據：
• 輸出一行，包含兩個整數 L,R，以空格分隔。
2 5 1 100 2 3 1 5 4 -1 100 85 -1 60 5 2 100 2 3 1 5 4 -1 100 85 -1 60
295 446 294 419
公開 測資點#0 (4%): 2.0s , <1K
公開 測資點#1 (4%): 2.0s , <1M
公開 測資點#2 (4%): 2.0s , <1M
公開 測資點#3 (4%): 2.0s , <1M
公開 測資點#4 (4%): 2.0s , <1M
公開 測資點#5 (4%): 2.0s , <1M
公開 測資點#6 (4%): 2.0s , <1M
公開 測資點#7 (4%): 2.0s , <10M
公開 測資點#8 (4%): 2.0s , <10M
公開 測資點#9 (4%): 2.0s , <10M
公開 測資點#10 (4%): 2.0s , <10M
公開 測資點#11 (4%): 2.0s , <10M
公開 測資點#12 (4%): 2.0s , <10M
公開 測資點#13 (4%): 2.0s , <10M
公開 測資點#14 (4%): 2.0s , <10M
公開 測資點#15 (4%): 2.0s , <10M
公開 測資點#16 (4%): 2.0s , <10M
公開 測資點#17 (4%): 2.0s , <10M
公開 測資點#18 (4%): 2.0s , <10M
公開 測資點#19 (4%): 2.0s , <10M
公開 測資點#20 (4%): 2.0s , <10M
公開 測資點#21 (4%): 2.0s , <10M
公開 測資點#22 (4%): 2.0s , <10M
公開 測資點#23 (4%): 2.0s , <10M
公開 測資點#24 (4%): 2.0s , <10M
【樣例1 解釋】
對於第一組數據：
• 學號為 1 的同學的分數會在學號為 5,3 的同學的分數之間，即 60 分和 85 分之間 (包括 60 和 85)。因此 l[1]=60,r[1]=85。
• 學號為 4 的同學的分數不大於學號為 5 的同學的分數 (即 60)，而沒有同學比他的分數低，因此最低可能的分數為 0。於是他的分數會在 0 分和 60 分之間 (包括 0 和 60)。因此 l[4]=0,r[4]=60。
• 學號為 2,3,5 的同學的分數都是固定的，因此 l[2]=r[2]=a[2]=100，l[3]=r[3]=a[3]=85，l[5]=r[5]=a[5]=60。
• 經過計算可得 L=295,R=446。
對於第二組數據：
• 學號為 1 的同學的分數會在學號為 5,3 的同學的分數之間。由於所有同學的分數互不相同，因此他的分數在 61 分和 84 分之間 (包括 61 和 84)。因此 l[1]=61,r[1]=84。
• 學號為 4 的同學的分數嚴格小於學號為 5 的同學的分數 (即 60)，而沒有同學比他的分數低，因此最低可能的分數為 0。於是他的分數會在 0 分和 59 分之間 (包括 0 和 59)。因此 l[4]=0,r[4]=59。
• 學號為 2,3,5 的同學的分數都是固定的，因此 l[2]=r[2]=a[2]=100，l[3]=r[3]=a[3]=85，l[5]=r[5]=a[5]=60。
• 經過計算可得 L=294,R=419。
【數據範圍】
對於所有測試數據，保證：
• T≤5
• n≤106
• m≤2
• s≤109
• p 為序列 (1,2,3,…,n) 的一個排列。
• 對於所有滿足 1≤i≤n 的整數 i，-1≤a[i]≤s。
• 至少存在一組分數滿足對應輸入的條件。
特殊性質 A：對於所有滿足 1≤i≤n 的整數 i，a[i]≠-1。
特殊性質 B：對於所有滿足 1≤i≤n 的整數 i，a[i]=-1。
特殊性質 C：對於所有滿足 1≤i≤n 的整數 i，p[i]=i。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||