QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583212#5108. Prehistoric ProgramsdeepthoughtWA 13ms7108kbC++231.6kb2024-09-22 18:58:552024-09-22 18:58:56

Judging History

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

  • [2024-09-22 18:58:56]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:7108kb
  • [2024-09-22 18:58:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
pair<int, int> look(const string& s) {
    int fin = 0;
    int minima = 0;
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == '(') fin++;
        else fin--;
        // if(s.length() == 150) cout << i << " " << fin << endl;
        minima = min(fin, minima);
    }
    return {fin, minima};
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <string> a(n + 1);
    vector <pair <int, int>> v1;
    vector <pair <int, int>> v2;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        auto ax = look(a[i]);
        int minima = ax.second;
        int fin = ax.first;
        if(fin >= 0) {
            v1.push_back({-minima, i});
        }
        else {
            reverse(a[i].begin(), a[i].end());
            // for (char& c : a[i]) c = (c == '(') ? ')' : '(';
            ax = look(a[i]);
            // cout << a[i] << endl;
            minima = ax.second;
            fin = ax.first;
            v2.push_back({-minima, i});
        }
    }
    vector <int> ans;
    string s = "";
    
    sort(v1.begin(), v1.end());
    for(auto x: v1) {
        int idx = x.second;
        s += a[idx];
        ans.push_back(idx);
    }


    sort(v2.begin(), v2.end());
    for(auto x: v2) {
        int idx = x.second;
        s += a[idx];
        // cout << idx << " " << a[idx] << endl;
        ans.push_back(idx);
    }

    auto bx = look(s);
    
    if(bx.second >= 0 && bx.first == 0) {
        for(auto x: ans)
            cout << x << '\n';
    }
    else cout << "impossible" << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 13ms
memory: 7108kb

input:

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

output:

impossible

result:

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