sprout_b.cpp

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

#define debug true
#define DBG if (debug) cout


struct Solution {
    double lg_sum;
    int l, r; // 左右界（包含）

    Solution(double lg_sum, int l, int r): lg_sum(lg_sum), l(l), r(r) {}

    bool operator < (const Solution& o) const {
        return lg_sum < o.lg_sum; // 比較用的函數，用於讓 priority queue 排序
    }
};

typedef struct Solution sol;

int main() {
    int T; // numbers of test cases
    scanf("%d", &T);

    while (T--) { // for every test cases
        int N;
        priority_queue<sol> sols; // 連續區間組成的 pq，用於排序答案
        scanf("%d", &N);

        sols.push(sol(0, 1, N)); // 預留一個 log 總和為零的，以免沒有答案
        int t, left = 0; // 暫存、目前區段的左界
        double cur_sum = 0; // 目前區段的 log 總和

        for (int i = 0; i <= N; i++) { // 這邊是 <= 不是 <
            if (i != N) scanf("%d", &t);
            else t = 0; // 因為要包含最後面的區段，所以在這邊多計算一個（出界）

            if (t && cur_sum == 0) { // 新的區段
                DBG << "New segment! Starting at " << i+1 << endl;
                cur_sum = log(t);
                left = i+1;
            } else if (t == 0 && cur_sum) { // 遇到 0 了，上一個區段結束
                DBG << "Closing segment: Log sum - " << cur_sum << "[" << left << ", " << i << "]\n";
                sols.push(sol(cur_sum, left, i)); // 把上一個區段丟到 priority queue 中
                cur_sum = 0, left = 0;
            } else if (t) {
                DBG << "Add item: " << i << "(Log: " << log(t) << ")\n";
                cur_sum += log(t);
            }
        }

        sol ans = sols.top();
        cout << ans.l << " " << ans.r << endl;
    }
    return 0;
}