QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#217072	#5534. Match	Camillus^#	37	1269ms	297472kb	C++20	1.5kb	2023-10-16 14:07:32	2024-07-04 02:20:12

Judging History

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

[2024-07-04 02:20:12]
评测

测评结果：37
用时：1269ms
内存：297472kb

查看

[2023-10-16 14:07:32]
提交

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;
    for (int i = 0; i < n; i++) {
        if (!q.empty() && s[q.back()] == s[i]) {
            t[i] = ')';
            q.pop_back();
        } else {
            t[i] = '(';
            q.push_back(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 {
                vector<int> q;
                int best = l;
                for (int i = l; i <= r; i++) {
                    if (!q.empty() && s[q.back()] == s[i]) {
                        q.pop_back();
                    } else {
                        q.push_back(i);
                    }
                    if (q.empty() && s[i] == s[l]) {
                        best = i;
                    }
                }

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

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 0ms

memory: 3744kb

input:

abbaaa

output:

(()())

result:

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

Test #2:

score: 0

Accepted

time: 0ms

memory: 3744kb

input:

cbbbbccbbccbbbbbbc

output:

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

result:

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

Test #3:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

ddbcbdacccbddaba

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 27

Accepted

Dependency #1:

100%

Accepted

Test #4:

score: 27

Accepted

time: 0ms

memory: 3640kb

input:

fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...

output:

((((((())))(()))(((()(((()((((()(()))))((((((()((((())(())((((((((())))(()))()))((((((()((()(((()))))(())))((((((())))(((((((()())(((((())())(()()((()(((((((((()))()))(()())))()())())(()(()))))(()))))()))(((())(())))())())())))))())(()())))(())()))))))((())())))))))))(()))))())((())()))(())))((())((...

result:

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

Test #5:

score: 0

Accepted

time: 0ms

memory: 3764kb

input:

vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...

output:

()(()(((()())(((())))((((())(((()(((((()(())(((())()())(()((((()))(()()((((()(((((()((()))())((())(()(()))(())(((()())()())(()(())((()))((())()(()(()())(()()))(())((()())(()((()(())))())((())()(((()(()())())(()))((()(())(((((()))((((())((())()(((()(((((((())(((())(())()())()()))((()(()(())))((()(())...

result:

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

Test #6:

score: 0

Accepted

time: 0ms

memory: 3532kb

input:

uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

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

Test #7:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

qeeqqqeeqqqquqeeeequuquuuqqqeqqqeeqquqqeeeuuueqqeeqqqqqeeeeeeeeeuqeqquuueeuqeqeqqueeuuuueeeeuuuqqquueuqeeeqeeeqeeqeqqequeeueqquuquqququqqqqueuqueuuuueuueeuueueeququeeeqeeqeeqqeuqeuequququuuuuueuuueeeuueeeqeuqquueuueeuquuqqqeqeuqqeqqquuueuuuuueeuuqeeeeeeeueuuuququeqqqqeeuqeuuquuueueeuuuqeqeeuqqqquuuq...

output:

((((((()()))((((()(((((()(()((((()))((((()((((((()(()))((((())))((((((()()))(((((((((())()))())(()()(((((((((((((((()))(()((((())(()))((()))))((((((((((())))(()((((((((())))())(((((((((((((())((()(((()(((((((((((((())(()(((((((()(((((((((((((()()(((((((((((()((((((((((((((()((((((()())(((()((())(()(...

result:

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

Subtask #3:

score: 0

Time Limit Exceeded

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #8:

score: 63

Accepted

time: 2ms

memory: 5016kb

input:

jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((())((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((...

result:

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

Test #9:

score: 0

Accepted

time: 100ms

memory: 57488kb

input:

zpujdttdnwtkfdfyddtbocyaeniizwubzgeybkccezxjldgtskmjfdywqlrihhckmbmvewoludvvmamdgkeholteaqujgssidpivwljbsnqgxltiviiwsvtekxiftlfkkudkwmbqczskkjsnilevhvdmuelnufvftyphloppctvwksjffecxblezsryszkxrjthxowwrittvjinyfkklllkydvzciiuaayomqjulladasktsyrvffdeennbwelfnhqoisiommrolzfvzkddskonisxlasgckqioouyqtsqfq...

output:

((((((((((((((((()((((((((((((((((((((()((((((((((((((((((((((((((((((((((()(((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((((((((((((((((((()(((((((((((((((((((((((((((((((((()(((((((((((((((((()(()((((((((((((((((((()(((()(((((((((((((()((((((((()(((((((((((((((((((((((((...

result:

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

Test #10:

score: 0

Accepted

time: 31ms

memory: 31164kb

input:

azekdamqaoetekbsselhazotlwwjnpxxceapyxsvgxutdtnnzzvovngkkrwvjrlddncosheotmepxghaeiakddfjzugxqunauvcbyipxtzkrjsdrjbcaozefshjwyrbdviigqvrpkkeamsvnkoyafpululfzaakbwgjkhfpnwihzeuwmydiazwjujussexlzbriochtfyvwbgpduxnkwvpycobczuuzmytnlllrvtyhzzwawtzkamqucyauxrlgthhayaidysemasybwnkjjiqoscacwsqprwjdfshttqriq...

output:

((((((((((((((((((((((((((((((()((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((()((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((...

result:

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

Test #11:

score: 0

Accepted

time: 724ms

memory: 297472kb

input:

mldshhxgdtnevvjvvvmdxxppbbrxxtpwboorjjrgpmmmnvthhjjtvbrpxpsxxsjjxtjjtpbevhhvvduprhjshccwoggsllsdcbbuubbutlojstebhrpnwsoxnopprssbuljwmxvgpprwlxnossuggmovhsggcbddprrhsthwnsleevshtnlodsjelhntswuultovcbbclndjjhnvvwewvodnmpslwnseupvccvshuusxvunnmoeeggoobbttsojjnjpvxdewnnndnlmeebprppsrppjcessehrrjnuutgpco...

output:

((((((((((((()((()((()()()(((((((()(()(((((((((()()))(((((((((()((())((((()()((((((((()((()(())((((()))(((((((((((((((((((()((((((((((((()(((((((((()(((((()((()(((((((((((()(((((((((((((((((()(((((())(((()((((((((((((((((((((((())((()((((()((()()()()((((()(((((((((()((((((((((((((((((())(((((()(((((...

result:

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

Test #12:

score: 0

Accepted

time: 8ms

memory: 3740kb

input:

baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

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

Test #13:

score: 0

Accepted

time: 7ms

memory: 3836kb

input:

baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

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

Test #14:

score: 0

Accepted

time: 97ms

memory: 17600kb

input:

fbbfffbfbbgbgbfffggfbbfgfbggbbbgfgffgfgfbbfbbfbbgfbggfbbffbbfbbbffbfbfbbgbffgfgfgbbggbbfgfbfbgfgggbggbgbgfbfgbfgbggggggbffgggbffffbbbgfgffgbbgbbbgfffffbgbbgfffbbgbgbbbbgbfbfbbbbbbbfbbfgfbbffbfffgfgbgfggbffffbbgfgfbffbfbbbgffgbbgbggggbgbggggbffggbggbbgfgbfgbgfgbbfbgbbfgbgffgffggfffgfgfbggbgfbgfffbbbg...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

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

Test #15:

score: 0

Accepted

time: 58ms

memory: 4076kb

input:

aaaaaababbbaababaababbbabaabbabbaabaabaaaaaabaababbbaaaaaabaaaaaababbbbaaabbaaabaaabaabbabbabbbbababababaaabbabbabaabaaaaabbbbabbbaabbbbbbaabbaabaaaabbaabaaabababbaabaaaaabaaaaaaaaaabbbaabbaaaabbbabbabbaaabbbbabbbababbaaaaaabaabbabaaababaababbbababaaabaaaabbabaaaaabbababaabaabaabaaaaababbaabaabaabaa...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

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

Test #16:

score: 0

Accepted

time: 1269ms

memory: 285908kb

input:

sccsyqrchhcltthddqhtyymrttrmqmdssyftssyyhlhsltqtcctrqqcltyhlcylqfsfqqccqhdstcrshclthdcttmqtqcttdhfyhymqdtmmqmmlyylccyrrlqhhrcsyydtdrrydsqllqcccftlqqqqlqchsccfqrrrscctchhryyfqccccyrhqrmmrmlddssfylfrlslssdtttqlsslqqldfyrtsclccdsfqcmmcyhhdmlltssryshcmmflsdydscmyfmmqyymfyqrclqqcyrfhrtlchccmryyhhtssdfdmm...

output:

(())((((()((()(()(((()((()))(((()(((()((((((((((()((()(((((((((((((((())((((((((((((((()(((((()(((((((((((((()((((()(()((()((((((((()((((())(((((((())(((((()(((()(()((()(()(((())(((((())((()()((((((((()((()((()(())((((((((()(((((())(()((()(()(((((((((((((((((((((()(((((((()((((((((((()((()()(()(((((...

result:

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

Test #17:

score: 0

Accepted

time: 471ms

memory: 220996kb

input:

ovavvsmodolxnnvvvvnyyjggbddkvuuvlntjgvrrfqfjkgfqkbyiiiyxdshumxnmnksxxylkitzgooswtwidwwnfyvqbbdlvnsucpqxrrewwtkkffkpwuzrbiivqqssiaafkzzjhhpajcnuampgcovspbnlmszqigrfbbfqwnmvhryfoylvvbjhvepcppdixowicuurbjhvrmttifflliodtmmmtiitmmluaadrbnnfnjxtutbuqzivznlccuccnliolidijxnytuolnbgeuxdkwjpzwmpbvjzzschuddezz...

output:

(((()((((((((((()))()(()(()((())((((((()((((((((((((()((((((((((((((((((((((()((((((()(((((()((((((((((()(()(((()(((((((()(()(((()(((((((((((((((((((((((((((((((((())((((((((((((()(((((((()(((((((()(((((((()(()())(((((((())()((()(((()(((((((((((((((((((()((((((((((((((((((((((((((((((((((()((((()(((...

result:

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

Test #18:

score: -63

Time Limit Exceeded

input:

slrusyssppylssldouuosrrrssslslpppplllrpossopyuuusluuooouuppllloyddlpdyldssyypploduusluuuurddryoyuldysdullsrrspyrrposddpyyodrssrrrllllulslolloullrlusslyoyyosuuddpysyprryodudpdpsoyydpylyoopsoosrssdppdlruurlpyspodyylyysyulyylssduyydlrrlrpyydpsooduoollddyuuysosslpplddoyssdpspoylrryllpyrrrsrsullurupyudos...