Codeforces 484A：為何 int 陣列會 TLE，改用 long long 卻 AC？

題目背景

Codeforces 484A Bits：給定 l, r (1 ≤ l ≤ r ≤ 10^18)，找出區間內 popcount(x)（二進位 1 的個數）最大的 x，若多解取最小值。

現象描述

參賽者發現：

• 陣列宣告 int a[300] → 提交顯示 Time Limit Exceeded (TLE)。
• 改為 long long a[300] → Accepted (AC)。
• 陣列元素數值不大，理論上 int 足夠，為何會影響效能？

真相揭露：並非型別導致 TLE

結論： int vs long long 本身不會導致演算法複雜度改變。真正原因通常是：

1. 未初始化陣列導致未定義行為（UB）：
   int a[300]; 僅分配記憶體，不保證初始為 0。若後續邏輯依賴陣列初始值（如當作旗標陣列），會讀取垃圾值，導致迴圈次數暴增、進入死迴圈或產生極大輸出，進而 TLE。
   long long a[300]; 在某些編譯器/最佳化等級下剛好落在全域/靜態區而被零初始化，掩蓋了 Bug。
2. 編譯器最佳化差異：型別大小改變記憶體佈局，影響編譯器向量化、迴圈展開等最佳化決策，極少數情況下導致效能差異，但不會從 TLE 變 AC。
3. 程式碼其處有 Bug：型別修改時順手修正了其他邏輯錯誤（如迴圈邊界、型別轉換溢位）。

正確的陣列初始化寫法

// C++11 統一初始化（推薦）
int a[300] = {};           // 全部 0
long long b[300] = {};     // 全部 0

// 或使用 std::fill / memset（僅適用 POD 型別）
std::fill(std::begin(a), std::end(a), 0);
// memset(a, 0, sizeof(a)); // 僅限 byte-wise 為 0 的型別（int/long long 適用）

// 區域陣列若需預設值，務必顯式初始化
void foo() {
    int arr[300] = {}; // 正確
    // int arr[300];    // 錯誤：值不定
}

避坑指南

• 永遠初始化區域陣列：T arr[N] = {}; 或 std::array<T, N> arr{};。
• 使用 std::vector 或 std::array 取代原生陣列，享有 RAII 與預設初始化。
• 提交前以 -Wall -Wextra -pedantic -O2 -std=c++17 編譯，啟用 sanitizers（-fsanitize=address,undefined）捕捉 UB。
• 遇到「改型別就 AC」的玄學現象，優先檢查未初始化變數、未定義行為、有符號整數溢位。

本題正確解法提示

本題核心為貪心構造：從最高位向低位嘗試將 0 翻為 1，若結果 ≤ r 則保留，否則復原。時間複雜度 O(log r)，與陣列型別無關。