Subtask 1: ~Q = 1, 1 \leq n \leq 10~.

Ta sinh hoán vị ~p_i~ ứng với vị trí cuối cùng của người ~i~ và kiểm tra. Độ phức tạp: ~O(N!)~.

Subtask 2: ~1 \leq N, Q \leq 10~.

Nhận xét: Nếu tồn tại đáp án cho khối lượng ~m~ thì chắc chắn tồn tại đáp án cho khối lượng ~m-1~. Duyệt từng giá trị ~m_i~, và dùng cách ở Subtask 1 để kiểm tra. Độ phức tạp: ~O(N!.Q)~

Subtask 3: ~1 \leq N \leq 20, 1 \leq Q \leq 10~.

Thay vì sinh hoán vị như Subtask 2, ta sử dụng dp bitmask. Độ phức tạp: ~O(2^N.N.Q)~.

Subtask 4, 5: ~1 \leq N \leq 2000, 1 \leq Q \leq 10~.

Tham lam: Thay vì chọn cột cho người, ta phân bổ người vào các cột. Gọi ~[l_j, r_j]~ là khả năng di chuyển của người ~j~. Vậy ta sẽ phân bổ người có khả năng di chuyển thấp nhất vào cột, hay cột ~i~ sẽ chọn người ~j~ chưa được chọn thỏa:

• ~l_j \leq i \leq r_j~.
• ~r_j \min~.

Với mỗi cột ~i~, ta duyệt ~n~ người để tìm người ~j~. Độ phức tạp: ~O(N^2.Q)~.

Subtask 6: ~1 \leq N, Q \leq 10^5~.

Dùng kỹ thuật chia nhị phân đáp án, cùng với CTDL priority_queue để tìm ~\min~ nhanh. Độ phức tạp: ~O(N.log(n).log({10^{18}}))~.

Code tham khảo:

bool check(int mid) {
    FOR(i, 1, n) add[i].clear();
    FOR(i, 1, n) {
        int able = s[i] / mid;
        add[max(1ll, v[i] - able)].pb(v[i] + able);
    }
    priority_queue<int, vector<int>, greater<int>> Q;
    FOR(i, 1, n) {
        for(int x : add[i]) Q.push(x);
        while(!Q.empty() && Q.top() < i) Q.pop();
        if (Q.empty()) return false;
        Q.pop();
    }
    return true;
}