/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 344.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 2ms 532.0 KiB
#4 Accepted 2ms 560.0 KiB
#5 Accepted 2ms 532.0 KiB
#6 Accepted 5ms 532.0 KiB
#7 Accepted 5ms 532.0 KiB
#8 Accepted 5ms 532.0 KiB
#9 Accepted 6ms 564.0 KiB
#10 Accepted 5ms 532.0 KiB
#11 Accepted 4ms 532.0 KiB
#12 Accepted 2ms 532.0 KiB
#13 Time Exceeded ≥4098ms ≥54.801 MiB
#14 Time Exceeded ≥4099ms ≥78.262 MiB

Code

#include <bits/stdc++.h>
using namespace std;
 
// Global variables for DFS recursion
int N, L, D;
vector<int> arr;
 
// DFS with memoization using bitmask.
unordered_map<int, bool> dp;
 
// Helper function to generate combinations of indices (for blocks with L > 2).
// This function will try to choose (r) indices from vector 'candidates' (starting from index pos)
// and then combine with base index 'base'. The current mask of chosen indices (besides base) is 'curMask'
// and the current maximum value in the block is 'curMax'.
bool chooseCombination(const vector<int>& candidates, int pos, int r, int base, int curMask, int curMax, int mask) {
    // If we have chosen enough indices, then check if block's max is exactly arr[base] + D.
    if(r == 0) {
        if(curMax == arr[base] + D) {
            int newMask = mask | (1 << base);
            // Mark all chosen indices as used.
            newMask |= curMask;
            // Try to partition the remaining indices.
            // We call the main DFS recursion.
            // (The DFS function is defined below.)
            extern bool dfs(int);
            if(dfs(newMask)) return true;
        }
        return false;
    }
    // If not enough candidates remain, return false.
    if(pos >= (int)candidates.size()) return false;
    
    // Option 1: choose candidate at pos if it does not exceed arr[base]+D.
    int idx = candidates[pos];
    // Prune: if this candidate's value is greater than the allowed maximum, skip.
    if(arr[idx] > arr[base] + D)
        return false;
    
    // Choose candidate at pos.
    if(chooseCombination(candidates, pos + 1, r - 1, base, curMask | (1 << idx), max(curMax, arr[idx]), mask))
        return true;
    
    // Option 2: skip candidate at pos.
    if(chooseCombination(candidates, pos + 1, r, base, curMask, curMax, mask))
        return true;
    
    return false;
}
 
// DFS function that tries to partition the sorted array into groups of size L with difference D.
// 'mask' is a bitmask indicating which indices have been used (1 means used).
bool dfs(int mask) {
    if(mask == (1 << N) - 1) return true; // All indices used.
    if(dp.count(mask)) return dp[mask];
    
    // Find the smallest unused index; this will be the minimum element of the next block.
    int base = 0;
    while(mask & (1 << base)) base++;
    
    // Build list of unused indices (only indices > base).
    vector<int> candidates;
    for (int i = base + 1; i < N; i++) {
        if(!(mask & (1 << i)))
            candidates.push_back(i);
    }
    
    bool possible = false;
    if(L == 2) {
        // For blocks of size 2, we just need to find one candidate j such that arr[j]-arr[base] == D.
        for (int j : candidates) {
            if(arr[j] - arr[base] == D) {
                int newMask = mask | (1 << base) | (1 << j);
                if(dfs(newMask)) {
                    possible = true;
                    break;
                }
            }
        }
    } else {
        // For blocks of size L > 2, we need to choose L-1 indices from candidates.
        // At least one of the chosen indices must be such that its value equals arr[base]+D (so that the max is achieved).
        possible = chooseCombination(candidates, 0, L - 1, base, 0, arr[base], mask);
    }
    
    dp[mask] = possible;
    return possible;
}
 
// The main function that returns the maximum number of blocks the array can be partitioned into.
int maxBlocks(vector<int>& inputArr) {
    N = inputArr.size();
    arr = inputArr;
    sort(arr.begin(), arr.end());
    
    // Precompute candidate differences D from any pair (and include 0)
    set<int> diffs;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            diffs.insert(arr[j] - arr[i]);
        }
    }
    diffs.insert(0); // In case of blocks with all equal elements.
    
    int best = 1; // at worst, the entire array is one block.
    // Try possible k from maximum possible (N/2) down to 2.
    for (int k = N/2; k >= 2; k--) {
        if(N % k != 0) continue; // must divide equally
        L = N / k;
        // For each candidate difference, try to partition.
        for (int d : diffs) {
            D = d;
            dp.clear();
            if(dfs(0)) {
                return k;
            }
        }
    }
    return best;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> arrInput(n);
        for (int i = 0; i < n; i++){
            cin >> arrInput[i];
        }
        cout << maxBlocks(arrInput) << "\n";
    }
    
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1162 Roy and Maximum Partition
Language
C++17 (G++ 13.2.0)
Submit At
2025-03-28 08:09:54
Judged At
2025-03-28 08:09:54
Judged By
Score
50
Total Time
≥4099ms
Peak Memory
≥78.262 MiB