QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#63934	#5108. Prehistoric Programs	Noobie_99	WA	11ms	6064kb	C++20	1.4kb	2022-11-23 18:36:59	2022-11-23 18:37:01

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-11-23 18:37:01]
评测

测评结果：WA
用时：11ms
内存：6064kb

查看

[2022-11-23 18:36:59]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[" << __LINE__ << ' ' << #x << "]: " << (x) << endl

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    vector<tuple<int, int, string, int>> a, b;
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;
        int cur = 0, mn = 0, mx = 0;
        for (char c : s) {
            if (c == '(') cur++;
            else cur--;
            mn = min(mn, cur);
            mx = max(mx, cur);
        }
        if (cur >= 0) a.emplace_back(mn, cur, s, i);
        else b.emplace_back(-mx, -cur, s, i);
    }

    sort(a.begin(), a.end(), [&](auto& x, auto& y) {
        return get<0>(x) > get<0>(y);
    });
    sort(b.begin(), b.end(), [&](auto& x, auto& y) {
        return get<0>(x) < get<0>(y);
    });

    vector<int> ans;
    int cur = 0;
    bool flag = true;
    for (auto& [x, _, y, z] : a) {
        for (char c : y) {
            if (c == '(') cur++;
            else cur--;
            if (cur < 0) flag = false;
        }
        ans.push_back(z);
    }
    for (auto& [x, _, y, z] : b) {
        for (char c : y) {
            if (c == '(') cur++;
            else cur--;
            if (cur < 0) flag = false;
        }
        ans.push_back(z);
    }

    if (cur != 0 || !flag) cout << "impossible\n";
    else {
        for (int e : ans) cout << e+1 << '\n';
    }

}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 11ms

memory: 6064kb

input:

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

output:

result:

ok good plan

Test #2:

score: -100

Wrong Answer

time: 3ms

memory: 3488kb

input:

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

output:

impossible

result:

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