QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217538#5108. Prehistoric ProgramsdrldrlsWA 13ms3540kbC++171.5kb2023-10-16 23:03:092023-10-16 23:03:09

Judging History

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

  • [2023-10-16 23:03:09]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3540kb
  • [2023-10-16 23:03:09]
  • 提交

answer

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

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

    queue<pair<int, 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 && (!result.empty() || s[0] != ')')){
            parentheses += score;
            result.emplace_back(i + 1);
        }else{
            q.emplace(make_pair(i + 1, score));
        }

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

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

    if(parentheses == 0 && !result.empty()){
        for(auto x: result) cout << x << " ";
    }else{
        cout << "impossible";
    }
}

詳細信息

Test #1:

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

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: 3428kb

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: 3460kb

input:

2
((
))

output:

1 2 

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

2 1 

result:

wrong answer wrong plan (expected impossible)