QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217073#5534. MatchCamillus#10 0ms3816kbC++201.5kb2023-10-16 14:19:492024-07-04 02:20:13

Judging History

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

  • [2024-07-04 02:20:13]
  • 评测
  • 测评结果:10
  • 用时:0ms
  • 内存:3816kb
  • [2023-10-16 14:19:49]
  • 提交

answer

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

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    string s;
    cin >> s;
    int n = (int)s.size();
    string t = s;

    vector<int> q;
    vector<int> V = { 0 };
    vector<int> before(n);
    vector<int> after(n);

    map<int, set<int>> Q[26];

    int v = 0;
    for (int i = 0; i < n; i++) {
        before[i] = q.size();
        if (!q.empty() && s[q.back()] == s[i]) {
            t[i] = ')';
            q.pop_back();
            V.pop_back();
        } else {
            t[i] = '(';
            q.push_back(i);
            V.push_back(++v);
        }
        after[i] = q.size();
        Q[s[i] - 'a'][after[i]].insert(i);
    }

    if (!q.empty()) {
        cout << -1 << '\n';
    } else {
        auto rec = [&](auto &&rec, int l, int r) -> void {
            if (l > r) {
                return;
            }
            if (s[l] == s[r]) {
                t[l] = '(';
                t[r] = ')';
                rec(rec, l + 1, r - 1);
            } else {
                const auto &B = Q[s[l] - 'a'][before[l]];
                auto it = B.upper_bound(r);

                int best = *prev(it);

                rec(rec, l, best);
                rec(rec, best + 1, r);
            }
        };
        rec(rec, 0, n - 1);
        cout << t << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 3816kb

input:

abbaaa

output:

(()())

result:

ok single line: '(()())'

Test #2:

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

input:

cbbbbccbbccbbbbbbc

output:

(((((((()))())))))

result:

ok single line: '(((((((()))())))))'

Test #3:

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

input:

ddbcbdacccbddaba

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #4:

score: 0
Time Limit Exceeded

input:

fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%