QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217560#5108. Prehistoric ProgramsdrldrlsWA 13ms3600kbC++171.5kb2023-10-16 23:41:442023-10-16 23:41:44

Judging History

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

  • [2023-10-16 23:41:44]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3600kb
  • [2023-10-16 23:41:44]
  • 提交

answer

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

int main(){
    // To get input n
    int count{0};
    cin >> count;

    queue<vector<int>> q; // a queue to save strings that haven't been used
    vector<int> result(0); // save permutation results 

    int parentheses{0}; // save the current score: numbers of '(' - numbers of ')' 

    // iterate *count* times to receive inputs
    for(int i = 0; i < count; i++){
        string s;
        int score{0};
        cin >> s;
        score = 2 * std::count(s.begin(), s.end(), '(') - s.length();

        if(parentheses + score >= 0 && (parentheses || s[0] != ')')){
            parentheses += score;
            result.emplace_back(i + 1);
        }else{
            vector<int> v{i + 1, score, s[0]};
            q.emplace(v);
        }

        while(parentheses >= 0 && !q.empty()){
            if(parentheses + q.front()[1] > 0){
                parentheses += q.front()[1];
                result.emplace_back(q.front()[0]);
                q.pop();
            }else{
                break;
            }
        }
    }

    while(parentheses >= 0 && !q.empty() && (parentheses || q.front()[2] != ')')){
        if(parentheses + q.front()[1] >= 0){
            parentheses += q.front()[1];
            result.emplace_back(q.front()[0]);
            q.pop();
        }else{
            break;
        }
    }
    
    if(parentheses == 0 && !result.empty() && q.empty()){
        for(auto x: result) cout << x << " ";
    }else{
        cout << "impossible";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 3600kb

input:

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

output:

1 2 3 5 6 7 4 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 46 47 48 49 50 51 52 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 45 53 74 75 101 102 ...

result:

ok good plan

Test #2:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

1 3 4 5 9 10 12 13 2 6 7 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 8 11 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok good plan

Test #3:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

2
()
()

output:

1 2 

result:

ok good plan

Test #4:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

2
((
))

output:

1 2 

result:

ok good plan

Test #5:

score: 0
Accepted
time: 1ms
memory: 3420kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

3
()
(
)

output:

1 2 3 

result:

ok good plan

Test #7:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

3
)(
(
)

output:

2 1 3 

result:

ok good plan

Test #8:

score: 0
Accepted
time: 0ms
memory: 3424kb

input:

5
))(
(()
)(
(
)

output:

2 3 4 1 5 

result:

ok good plan

Test #9:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

3
((
))())
(

output:

1 3 2 

result:

ok good plan

Test #10:

score: 0
Accepted
time: 1ms
memory: 3364kb

input:

6
)
()
()()()
((
)
)

output:

impossible

result:

ok impossible

Test #11:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

500
(
)
)
(
)(
(
(
)
))(
(
(
(
(
)
)
(
(
)
(
(
)
(
()(()
(
)())
(
(
)
(
)()((
(
)
(
)
)
(
(
(
)
(
(
)
)
)(
(
(
)
)
(
)
(
(
(
)
(
(
())))
(
(
(
)
(
)
)
(
(
)
)
(
(
(
(
(
()
(
(
(
(
(
((
)
(
(
)
(
(
(
)
())
(
(
(
)
(
(
(
)
)
(
)
)
(
)
(
(
(
(
)
(
)
)
)
)
(
)
)))()(
(
)
)
(
)
)(
)
(
)
)
))
(
(
(
(
(
(
...

output:

1 2 4 5 6 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok good plan

Test #12:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

50
)
)
((((()())())))(())(())
()(((()))
(((()))(()
()(((
))
)
)()))(()(()())(((((()
(
)
)
)((
)()((
())()))
(())))()
(((
))))(()
()(())(()))())()
)
)
(
(
(
(
((())()())())))(((())
()(
(()(())()((()
()(((()())))())()(
)
)((()
(
)
((
)
()(
(
(
)
)))((())
)
()))()(((()(()
((
((()))(())(()())(()())())()...

output:

3 4 5 1 2 6 7 8 9 10 11 12 13 14 15 16 17 18 22 23 24 19 25 20 26 27 28 21 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 46 45 47 48 49 50 

result:

ok good plan

Test #13:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

50
)
(
)()(
())(
()()(((((())(
)(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...

output:

2 3 4 5 1 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 17 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 

result:

ok good plan

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3528kb

input:

150
))(()))(())(())))()))())()()()(())(((())))()))))()
)))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...

output:

impossible

result:

wrong answer you didn't find a solution but jury did