/ SeriousOJ /

Record Detail

Compile Error

foo.cc: In function 'bool dfs(int)':
foo.cc:60:27: error: expected initializer at end of input
   60 |     vector<int> candidates
      |                           ^
foo.cc:60:27: error: expected '}' at end of input
foo.cc:50:20: note: to match this '{'
   50 | bool dfs(int mask) {
      |                    ^

Code

#include <bits/stdc++.h>
using namespace std;
 
int N, L, D;
vector<int> arr;
unordered_map<int, bool> dp; // memo for global DFS (key = used indices mask)
 
// Global DFS: try to partition the sorted array (of size N) into groups of size L with common difference D.
// mask: bitmask of indices already used.
bool dfs(int mask);
 
// Helper: given a fixed "base" (the smallest unused index in the current DFS call)
// and a candidate list (indices > base and unused), recursively choose L-1 indices 
// to form a block with min = arr[base] and max = arr[base] + D.
// pos: current index in candidate vector to consider
// r: how many indices still need to be chosen
// found: whether we have already chosen an element equal to arr[base] + D
// currentSet: bitmask (with respect to global indices) of the candidates chosen so far.
bool chooseCombination(const vector<int> &candidates, int pos, int r, bool found, int currentSet, int base, int curMask) {
    // If we have chosen enough indices, check that the block has the required max and try DFS on the new mask.
    if(r == 0) {
        if(!found) return false; // must have at least one candidate equal to arr[base] + D
        int newMask = curMask | (1 << base) | currentSet;
        if(dfs(newMask))
            return true;
        return false;
    }
    // Prune: if there are not enough remaining candidates
    if(pos >= (int)candidates.size())
        return false;
    // Also, if we haven't found an element equal to arr[base]+D, check if any candidate in the remaining list can supply that.
    bool canFindMax = found;
    for (int i = pos; i < (int)candidates.size(); i++) {
        if(arr[candidates[i]] == arr[base] + D) { canFindMax = true; break; }
    }
    if(!canFindMax) return false;
    
    // Option 1: pick the candidate at pos.
    int idx = candidates[pos];
    bool newFound = found || (arr[idx] == arr[base] + D);
    if(chooseCombination(candidates, pos + 1, r - 1, newFound, currentSet | (1 << idx), base, curMask))
        return true;
    // Option 2: skip the candidate at pos.
    if(chooseCombination(candidates, pos + 1, r, found, currentSet, base, curMask))
        return true;
    
    return false;
}
 
bool dfs(int mask) {
    if(mask == (1 << N) - 1) return true; // all indices used
    if(dp.count(mask))
        return dp[mask];
    
    // Choose the smallest unused index as the base for the next block.
    int base = 0;
    while(mask & (1 << base)) base++;
    
    // Gather candidate indices (all unused indices > base).
    vector<int> candidates

Information

Submit By
Type
Submission
Problem
P1162 Roy and Maximum Partition
Language
C++17 (G++ 13.2.0)
Submit At
2025-03-28 10:26:32
Judged At
2025-03-28 10:26:32
Judged By
Score
0
Total Time
0ms
Peak Memory
0 Bytes