QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225922#5108. Prehistoric Programsb05704085TL 0ms0kbC++201.3kb2023-10-25 11:49:252023-10-25 11:49:25

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 11:49:25]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-25 11:49:25]
  • 提交

answer

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>

using namespace std;

bool isProperlyNested(const vector<int> &permutation, const vector<string> &tablets)
{
    stack<char> s;

    for (int num : permutation)
    {
        const string &tablet = tablets[num - 1];
        for (char c : tablet)
        {
            if (c == '(')
            {
                s.push(c);
            }
            else if (c == ')')
            {
                if (s.empty() || s.top() != '(')
                {
                    return false;
                }
                s.pop();
            }
        }
    }

    return s.empty();
}

int main()
{
    int n;
    cin >> n;

    vector<string> tablets(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> tablets[i];
    }

    vector<int> originalPermutation(n);
    for (int i = 0; i < n; ++i)
    {
        originalPermutation[i] = i + 1;
    }

    do
    {
        if (isProperlyNested(originalPermutation, tablets))
        {
            for (int num : originalPermutation)
            {
                cout << num << endl;
            }
            return 0;
        }
    } while (next_permutation(originalPermutation.begin(), originalPermutation.end()));

    cout << "impossible" << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:


result: