TIOJ 爛測資補修計畫

# TIOJ 爛測資補修計畫鑑於 TIOJ 上許多題目測資太爛（有些甚至無法驗證解的正確性），請各位在寫到測資爛的題目時來這裡回報，某個人會盡可能改善他們。目前的計畫是一題一題修，盡可能在 TIOJ 低峰時 Rejudge。 ## 測資報修格式爛測資分為兩種： 1. 壞掉的測資如輸入 $m$ 條邊實際上卻不足 $m$ 條、題目限制輸入 $\le 10 ^ 5$ 卻超出 `long long` 等較嚴重的問題，會**導致正確的程式碼無法通過**的問題。例如：1709。這類題目經回報會先打上 `broken` 的標籤。 2. 太弱的測資如卡不掉假解、輸入量太小等較不嚴重的問題。例如：1807。如果要報修，請提供「題號、原因、Submission 編號、此 Submission 問題詳細說明」，如： - 1807 原因：測資範圍明顯有問題，且無法驗證解的正確性 Submission 編號：208419 Submission 問題：只驗證輸入邊數是否大於完全圖卻通過所有測資。其中，有問題的 Submission 可能是正解卻被排除（測資生爛），或是假解卻沒有被卡掉。請在「Submission 問題」裡註明這筆假解的錯誤處、或是你是怎麼驗出測資錯的。請注意，**確認自己的解沒有意外 bug**再丟上來，這不是 debug 板。被回報為「太弱的測資」的題目不一定會修。 ## 要如何（在看不到測資的情況下）確認問題？請善用 `<cassert>` 裡的 `assert()`，有時可以驗出測資根本生不夠輸入等問題。 ## 我有其他問題 qwq 請私訊 `FHVirus` 或其他認識的 Admin。聯絡方式： - froghackervirus@gmail.com - Discord: FHVirus --- ## 「已經修正／補強的題目」 - 1877 2022/08/01 已修正：題敘修正為長度 $\leq N/2$，測資修正與加強 - 1391 & 1392 2022/08/01 已修正：題敘修正為 $1\leq T\leq 100$ - 1406 2023/09/15 已修正：增強測資，感謝 YiaHong 提供 hack - 1668 2023/10/09 已加強：感謝 dreamoon - 2115 2024/03/06 已修正：更正測試資料，感謝 baluteshih 和 abc864197532 鼎力相助。 --- ## 「壞掉的測資」回報區 - 1709 原因：測資點 #8 #9 #12 輸入邊數不足。 Submission 編號：258223 Submission 問題：經 Assert 驗得上述問題。 - 1249 原因：測資點 #5 #6 #8 #9 有重複測資，與題意「沒有兩個人帳號一樣」矛盾 Submission 編號：259515 Submission 問題：經 Assert 驗得上述問題 ((原本用`set`寫，後來改成`multiset`就過了 - 1879 原因：經管理員查看第 8 號測資邊數不足 - 1305 原因：測資與輸入範圍不符 Submission 編號：296344 Submission 問題：在測資 #5 #7 assert 出 insert 次數超過 $10^4$ 次 - 1405 原因：測資不合題意 Submission 編號：310724 Submission 問題：在測資 #18 assert 出輸入的排列不是 self-inverse，違反光的可逆性。註 1：可和 AC 的 310725 對照。註 2：這題用 `ios::sync_with_stdio(false);` 會拿到 WA，建議修正或加註警語。 - 1726 原因：測資和輸入範圍不符 Submission 編號：321963 Submission 問題：在測資 #5 #6 #7 assert 出不符合 $1\leq C_i \leq N$ - 1228 原因：時限變太小 Submission 問題：每筆測資時限 1000 ms，但可以從其他 submission 中知道在時限還沒變小以前可 AC 的做法執行時間會超過 1000 ms，現在上傳會 TLE - 1730 原因：首先，題目說： > 第二行則是輸出所有可能之中，第K大的長長蚯。 > 如果無解，則不要有第二行的存在。但其實是如果有至少一種可能但數量不到 K 的話，要輸出最小的長長蚯然後 https://tioj.ck.tp.edu.tw/submissions/372938 這筆應該要 WA，因為少處理一個可能很容易忘的 edge case，感覺有不小的機率是官解忘了https://tioj.ck.tp.edu.tw/submissions/372936 應該要 AC --- ## 「太弱的測資」回報區 - 1807 原因：測資範圍明顯有問題，且無法驗證解的正確性 Submission 編號：208419 Submission 問題：只驗證輸入邊數是否大於完全圖卻通過所有測資。 - 1236 原因：使用不完整的最大流模板依然可以過 Submission 編號：256219 Submission 問題：`add` 裡面反向邊的 index 錯誤，應 +1 - 1253 原因：除了第一筆，其他都只有一筆測資 Submission 編號：258269 Submission 問題：我沒給ans++都能過第一筆之外的 - 1590 原因：測資實際上遠小於題目限制 Submission 編號：247255 Submission 問題：原題的限制下開值域大小的陣列應該會MLE，但只要把陣列開小一點就能過了   - 1399 原因：無法卡掉複雜度不正確的解 Submission 編號：253845 Submission 問題：題目要求應為 $O(nT)$，但 $O(n^2 \log T)$ 也會過，還比 $O(nT)$ 快許多。 - 1178 原因：無法卡掉不正確的解 Submission 編號：262500 Submission 問題：題目說「所謂凸包上的頂點，指的是轉折處(邊上的點不算)。」可是如果把邊上的點也算進去還是可以過。 - 1798 測資實際上遠小於題目限制 Submission 編號：271426 Submission 問題：陣列開5e5也能過 - 2205 測資太爛 - 1410 原因：題目值域實際上只有 $\le 10^5$ - 1811 原因：暴力找轉移點會過 Submission 編號：290166 - 1902 原因：$O(N^2+Q)$ 會過 Submission 編號：238873 - 1049 原因：沒有卡好邊界 Submission 191290 303047 都會過 - 1412 原因：無法卡掉假解 Submission 編號：308055 && 308074 Submission 問題：判斷函式中應回傳sum >= k * m，但回傳sum >= k也會AC - 2226 原因：subtask沒有卡掉漏判edge case的解 Submission 編號：343271 Submission 問題：沒判斷k=0的情況可以拿57分 - 1939 原因：有負數沒卡掉 Submission 編號：372579 Submission 問題：這樣會輸出負數還是ac了