發表新討論
#17342: 雖然過了，但是想知道和 a174 的差異


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.35.55]
最後登入時間 ：
2024-11-27 00:16:52
a175. 撒旦玩不玩骰子？ | From: [140.113.208.164] | 發表日期 : 2019-04-05 16:19

如題，除了比起 a174 的操作多出10倍以外並沒有感覺到差異？

兩題我都是用 C++的 set 實作 HashTable 

 
#17346: Re:雖然過了，但是想知道和 a174 的差異


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

學校 : 臺北市私立延平高級中學
編號 : 83268
來源 : [203.72.178.1]
最後登入時間 ：
2023-10-30 13:02:50
a175. 撒旦玩不玩骰子？ | From: [114.42.219.193] | 發表日期 : 2019-04-05 16:36

如題，除了比起 a174 的操作多出10倍以外並沒有感覺到差異？

兩題我都是用 C++的 set 實作 HashTable 

這題有點年代了,也許Zerojudge經過幾次更新後速度變快,原本的時限就卡不到人了


只有一部份題目速度變快，大部分已經無法0ms了，那些紀錄都是在更新前創下的。


 
#17352: Re:雖然過了，但是想知道和 a174 的差異


inversion (「我們所認識的可符香是個像天使的好女孩」之葉林 *Cries...)

學校 : 國立清華大學
編號 : 43537
來源 : [49.159.6.107]
最後登入時間 ：
2022-05-28 19:29:12
a175. 撒旦玩不玩骰子？ | From: [49.158.83.43] | 發表日期 : 2019-04-05 17:23

如題，除了比起 a174 的操作多出10倍以外並沒有感覺到差異？

兩題我都是用 C++的 set 實作 HashTable 

這題有點年代了,也許Zerojudge經過幾次更新後速度變快,原本的時限就卡不到人了


只有一部份題目速度變快，大部分已經無法0ms了，那些紀錄都是在更新前創下的。


本人的感覺是前置時間(overhead)變長，但是整體實際上變快了。


 
#17353: Re:雖然過了，但是想知道和 a174 的差異


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

學校 : 臺北市私立延平高級中學
編號 : 83268
來源 : [203.72.178.1]
最後登入時間 ：
2023-10-30 13:02:50
a175. 撒旦玩不玩骰子？ | From: [114.42.219.193] | 發表日期 : 2019-04-05 18:03

如題，除了比起 a174 的操作多出10倍以外並沒有感覺到差異？

兩題我都是用 C++的 set 實作 HashTable 

這題有點年代了,也許Zerojudge經過幾次更新後速度變快,原本的時限就卡不到人了


只有一部份題目速度變快，大部分已經無法0ms了，那些紀錄都是在更新前創下的。


本人的感覺是前置時間(overhead)變長，但是整體實際上變快了。


所以是因為前置時間變長，才導致原本很快的程式變慢，但本身就無法很快的程式變快?


 
#17354: Re:雖然過了，但是想知道和 a174 的差異


inversion (「我們所認識的可符香是個像天使的好女孩」之葉林 *Cries...)

學校 : 國立清華大學
編號 : 43537
來源 : [49.159.6.107]
最後登入時間 ：
2022-05-28 19:29:12
a175. 撒旦玩不玩骰子？ | From: [49.158.83.43] | 發表日期 : 2019-04-05 19:13

如題，除了比起 a174 的操作多出10倍以外並沒有感覺到差異？

兩題我都是用 C++的 set 實作 HashTable 

這題有點年代了,也許Zerojudge經過幾次更新後速度變快,原本的時限就卡不到人了


只有一部份題目速度變快，大部分已經無法0ms了，那些紀錄都是在更新前創下的。


本人的感覺是前置時間(overhead)變長，但是整體實際上變快了。


所以是因為前置時間變長，才導致原本很快的程式變慢，但本身就無法很快的程式變快?


應該是如此。但實際的伺服器情況就要問管理員了。

 
#17359: Re:雖然過了，但是想知道和 a174 的差異


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.35.55]
最後登入時間 ：
2024-11-27 00:16:52
a175. 撒旦玩不玩骰子？ | From: [140.113.208.164] | 發表日期 : 2019-04-05 22:11

後來，我去找了 Morris128 大大對於這題提供的作法是用 LinkList 實作

所以查詢某個數字是否存在HashTable時會是O(N)，

如果是用 set 或是 map 實作的話查詢成本會降低成 O(logN)

所以照搬 a174 的 LinkList 作法會 TLE。

 

 
 
#17360: Re:雖然過了，但是想知道和 a174 的差異


freedom501999@gmail.com (帥氣魔方生)

學校 : 不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 ：
2019-05-30 22:56:25
a175. 撒旦玩不玩骰子？ | From: [27.52.129.54] | 發表日期 : 2019-04-06 09:40
 

C 可沒有 Map 或 HashTable 可以用

必須自己實作 LinkedList + tree 或 HashTable 才能過

不然單純用 LinkedList ，只會吃 TLE

( 自己作平衡樹很累的.... )

 
ZeroJudge Forum