/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 540.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 1ms 540.0 KiB
#7 Accepted 1ms 516.0 KiB
#8 Accepted 2ms 620.0 KiB
#9 Accepted 1ms 540.0 KiB
#10 Accepted 5ms 844.0 KiB
#11 Accepted 1ms 540.0 KiB
#12 Accepted 57ms 3.633 MiB
#13 Accepted 1ms 540.0 KiB
#14 Time Exceeded ≥599ms ≥34.699 MiB
#15 Accepted 1ms 540.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;

vector<string> ans;
int n;

void generate(string curr, int open1, int close1, int open2, int close2) {
    // If current length equals required length
    if(curr.length() == n) {
        if(open1 == close1 && open2 == close2) {  // All brackets are matched
            ans.push_back(curr);
        }
        return;
    }
    
    // Can add ( if we haven't used all n/2 opening brackets
    if(open1 < n/2) {
        generate(curr + '(', open1 + 1, close1, open2, close2);
    }
    
    // Can add ) if we have more ( than )
    if(close1 < open1) {
        generate(curr + ')', open1, close1 + 1, open2, close2);
    }
    
    // Can add [ if we haven't used all n/2 opening brackets
    if(open2 < n/2) {
        generate(curr + '[', open1, close1, open2 + 1, close2);
    }
    
    // Can add ] if we have more [ than ]
    if(close2 < open2) {
        generate(curr + ']', open1, close1, open2, close2 + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    if(n % 2 == 1) {  // Odd length can't form valid sequence
        cout << '\n';
        return 0;
    }
    
    generate("", 0, 0, 0, 0);
    sort(ans.begin(), ans.end());  // Sort lexicographically
    
    for(const string& s : ans) {
        cout << s << '\n';
    }
    
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1170 Regular bracket sequence
Language
C++17 (G++ 13.2.0)
Submit At
2025-02-22 19:59:56
Judged At
2025-02-22 19:59:56
Judged By
Score
95
Total Time
≥599ms
Peak Memory
≥34.699 MiB