QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#591319 | #5534. Match | wanggk | 100 ✓ | 534ms | 6764kb | C++14 | 1.2kb | 2024-09-26 15:21:36 | 2024-09-26 15:21:42 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,il,ir) for(register int i=(il);i<=(ir);++i)
#define Forr(i,ir,il) for(register int i=(ir);i>=(il);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>
inline void read(T& x){
bool f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=1; ch=getchar(); }
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f) x=-x;
}
template<typename T,typename... Args>
void read(T& first,Args&... args){ read(first),read(args...); }
const int maxn=1e5+10;
namespace stO_Orz{
int n,tp;
string s;
char st[maxn];
char res[maxn];
ll base[maxn],a[maxn],hsh;
void div(int l,int r)
{
if(l>r) return;
for(int i=r;i>l;--i)
if(s[l-1]==s[i-1]&&a[l]==a[i-1])
{
res[l-1]='(',res[i-1]=')',div(l+1,i-1),div(i+1,r);
break;
}
}
signed my_main()
{
cin>>s;
n=s.size();
base[0]=1ll;
For(i,1,n-1) base[i]=base[i-1]*131ll;
for(int i=0;i<n;++i){
if(tp&&st[tp]==s[i]) hsh-=base[--tp]*s[i];
else hsh+=base[tp++]*s[i],st[tp]=s[i];
a[i+1]=hsh;
}
if(tp){ printf("-1\n"); return 0; }
div(1,n);
cout<<res<<endl;
return 0;
}
}
signed main(){ return stO_Orz::my_main(); }
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3504kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3572kb
input:
cbbbbccbbccbbbbbbc
output:
(((((((()))())))))
result:
ok single line: '(((((((()))())))))'
Test #3:
score: 10
Accepted
time: 0ms
memory: 3700kb
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: 3636kb
input:
fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...
output:
((((((())))(()))(((()(((()((((()(()))))((((((()((((())(())((((((((())))(()))()))((((((()((()(((()))))(())))((((((())))(((((((()())(((((())())(()()((()(((((((((()))()))(()())))()())())(()(()))))(()))))()))(((())(())))())())())))))())(()())))(())()))))))((())())))))))))(()))))())((())()))(())))((())((...
result:
ok single line: '((((((())))(()))(((()(((()((((...))(())(()))(())())))))))((())))'
Test #5:
score: 27
Accepted
time: 0ms
memory: 3736kb
input:
vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...
output:
()(()(((()())(((())))((((())(((()(((((()(())(((())()())(()((((()))(()()((((()(((((()((()))())((())(()(()))(())(((()())()())(()(())((()))((())()(()(()())(()()))(())((()())(()((()(())))())((())()(((()(()())())(()))((()(())(((((()))((((())((())()(((()(((((((())(((())(())()())()()))((()(()(())))((()(())...
result:
ok single line: '()(()(((()())(((())))((((())((...()(()(()))))(())()))(()()()))))'
Test #6:
score: 27
Accepted
time: 0ms
memory: 3628kb
input:
uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #7:
score: 27
Accepted
time: 1ms
memory: 3616kb
input:
qeeqqqeeqqqquqeeeequuquuuqqqeqqqeeqquqqeeeuuueqqeeqqqqqeeeeeeeeeuqeqquuueeuqeqeqqueeuuuueeeeuuuqqquueuqeeeqeeeqeeqeqqequeeueqquuquqququqqqqueuqueuuuueuueeuueueeququeeeqeeqeeqqeuqeuequququuuuuueuuueeeuueeeqeuqquueuueeuquuqqqeqeuqqeqqquuueuuuuueeuuqeeeeeeeueuuuququeqqqqeeuqeuuquuueueeuuuqeqeeuqqqquuuq...
output:
((((((()()))((((()(((((()(()((((()))((((()((((((()(()))((((())))((((((()()))(((((((((())()))())(()()(((((((((((((((()))(()((((())(()))((()))))((((((((((())))(()((((((((())))())(((((((((((((())((()(((()(((((((((((((())(()(((((((()(((((((((((((()()(((((((((((()((((((((((((((()((((((()())(((()((())(()(...
result:
ok single line: '((((((()()))((((()(((((()(()((...))))((())))())))((())))))()))))'
Subtask #3:
score: 63
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #8:
score: 63
Accepted
time: 0ms
memory: 3960kb
input:
jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((())((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #9:
score: 63
Accepted
time: 20ms
memory: 5492kb
input:
zpujdttdnwtkfdfyddtbocyaeniizwubzgeybkccezxjldgtskmjfdywqlrihhckmbmvewoludvvmamdgkeholteaqujgssidpivwljbsnqgxltiviiwsvtekxiftlfkkudkwmbqczskkjsnilevhvdmuelnufvftyphloppctvwksjffecxblezsryszkxrjthxowwrittvjinyfkklllkydvzciiuaayomqjulladasktsyrvffdeennbwelfnhqoisiommrolzfvzkddskonisxlasgckqioouyqtsqfq...
output:
((((((((((((((((()((((((((((((((((((((()((((((((((((((((((((((((((((((((((()(((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((((((((((((((((((()(((((((((((((((((((((((((((((((((()(((((((((((((((((()(()((((((((((((((((((()(((()(((((((((((((()((((((((()(((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((()((((((((((((...)))))))))))))))))))))))))))))))'
Test #10:
score: 63
Accepted
time: 11ms
memory: 5608kb
input:
azekdamqaoetekbsselhazotlwwjnpxxceapyxsvgxutdtnnzzvovngkkrwvjrlddncosheotmepxghaeiakddfjzugxqunauvcbyipxtzkrjsdrjbcaozefshjwyrbdviigqvrpkkeamsvnkoyafpululfzaakbwgjkhfpnwihzeuwmydiazwjujussexlzbriochtfyvwbgpduxnkwvpycobczuuzmytnlllrvtyhzzwawtzkamqucyauxrlgthhayaidysemasybwnkjjiqoscacwsqprwjdfshttqriq...
output:
((((((((((((((((((((((((((((((()((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((()((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((...
result:
ok single line: '((((((((((((((((((((((((((((((...))))))))()))))))))))))())))))))'
Test #11:
score: 63
Accepted
time: 115ms
memory: 5904kb
input:
mldshhxgdtnevvjvvvmdxxppbbrxxtpwboorjjrgpmmmnvthhjjtvbrpxpsxxsjjxtjjtpbevhhvvduprhjshccwoggsllsdcbbuubbutlojstebhrpnwsoxnopprssbuljwmxvgpprwlxnossuggmovhsggcbddprrhsthwnsleevshtnlodsjelhntswuultovcbbclndjjhnvvwewvodnmpslwnseupvccvshuusxvunnmoeeggoobbttsojjnjpvxdewnnndnlmeebprppsrppjcessehrrjnuutgpco...
output:
((((((((((((()((()((()()()(((((((()(()(((((((((()()))(((((((((()((())((((()()((((((((()((()(())((((()))(((((((((((((((((((()((((((((((((()(((((((((()(((((()((()(((((((((((()(((((((((((((((((()(((((())(((()((((((((((((((((((((((())((()((((()((()()()()((((()(((((((((()((((((((((((((((((())(((((()(((((...
result:
ok single line: '((((((((((((()((()((()()()((((...))))))))))))))()))))))()))))())'
Test #12:
score: 63
Accepted
time: 0ms
memory: 6656kb
input:
baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #13:
score: 63
Accepted
time: 4ms
memory: 6628kb
input:
baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #14:
score: 63
Accepted
time: 31ms
memory: 6764kb
input:
fbbfffbfbbgbgbfffggfbbfgfbggbbbgfgffgfgfbbfbbfbbgfbggfbbffbbfbbbffbfbfbbgbffgfgfgbbggbbfgfbfbgfgggbggbgbgfbfgbfgbggggggbffgggbffffbbbgfgffgbbgbbbgfffffbgbbgfffbbgbgbbbbgbfbfbbbbbbbfbbfgfbbffbfffgfgbgfggbffffbbgfgfbffbfbbbgffgbbgbggggbgbggggbffggbggbbgfgbfgbgfgbbfbgbbfgbgffgffggfffgfgfbggbgfbgfffbbbg...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))()'
Test #15:
score: 63
Accepted
time: 3ms
memory: 5848kb
input:
aaaaaababbbaababaababbbabaabbabbaabaabaaaaaabaababbbaaaaaabaaaaaababbbbaaabbaaabaaabaabbabbabbbbababababaaabbabbabaabaaaaabbbbabbbaabbbbbbaabbaabaaaabbaabaaabababbaabaaaaabaaaaaaaaaabbbaabbaaaabbbabbabbaaabbbbabbbababbaaaaaabaabbabaaababaababbbababaaabaaaabbabaaaaabbababaabaabaabaaaaababbaabaabaabaa...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #16:
score: 63
Accepted
time: 233ms
memory: 6292kb
input:
sccsyqrchhcltthddqhtyymrttrmqmdssyftssyyhlhsltqtcctrqqcltyhlcylqfsfqqccqhdstcrshclthdcttmqtqcttdhfyhymqdtmmqmmlyylccyrrlqhhrcsyydtdrrydsqllqcccftlqqqqlqchsccfqrrrscctchhryyfqccccyrhqrmmrmlddssfylfrlslssdtttqlsslqqldfyrtsclccdsfqcmmcyhhdmlltssryshcmmflsdydscmyfmmqyymfyqrclqqcyrfhrtlchccmryyhhtssdfdmm...
output:
(())((((()((()(()(((()((()))(((()(((()((((((((((()((()(((((((((((((((())((((((((((((((()(((((()(((((((((((((()((((()(()((()((((((((()((((())(((((((())(((((()(((()(()((()(()(((())(((((())((()()((((((((()((()((()(())((((((((()(((((())(()((()(()(((((((((((((((((((((()(((((((()((((((((((()((()()(()(((((...
result:
ok single line: '(())((((()((()(()(((()((()))((...)))))()))))()))))))))))))))))))'
Test #17:
score: 63
Accepted
time: 68ms
memory: 5724kb
input:
ovavvsmodolxnnvvvvnyyjggbddkvuuvlntjgvrrfqfjkgfqkbyiiiyxdshumxnmnksxxylkitzgooswtwidwwnfyvqbbdlvnsucpqxrrewwtkkffkpwuzrbiivqqssiaafkzzjhhpajcnuampgcovspbnlmszqigrfbbfqwnmvhryfoylvvbjhvepcppdixowicuurbjhvrmttifflliodtmmmtiitmmluaadrbnnfnjxtutbuqzivznlccuccnliolidijxnytuolnbgeuxdkwjpzwmpbvjzzschuddezz...
output:
(((()((((((((((()))()(()(()((())((((((()((((((((((((()((((((((((((((((((((((()((((((()(((((()((((((((((()(()(((()(((((((()(()(((()(((((((((((((((((((((((((((((((((())((((((((((((()(((((((()(((((((()(((((((()(()())(((((((())()((()(((()(((((((((((((((((((()((((((((((((((((((((((((((((((((((()((((()(((...
result:
ok single line: '(((()((((((((((()))()(()(()(((...)())))))))()())))))))))))()))))'
Test #18:
score: 63
Accepted
time: 534ms
memory: 6600kb
input:
slrusyssppylssldouuosrrrssslslpppplllrpossopyuuusluuooouuppllloyddlpdyldssyypploduusluuuurddryoyuldysdullsrrspyrrposddpyyodrssrrrllllulslolloullrlusslyoyyosuuddpysyprryodudpdpsoyydpylyoopsoosrssdppdlruurlpyspodyylyysyulyylssduyydlrrlrpyydpsooduoollddyuuysosslpplddoyssdpspoylrryllpyrrrsrsullurupyudos...
output:
((((((()())(())((())((()(()((((())(()(((()((((()(((((()()()(()((((((((((((()()(((()(((())(())((((((((((()(()(((()(((()(()(((()())((()(((((())(()((((((((())(()(((((((()((((((((((()(((((()((())(()(()(((()))(((((((((()((((())()((()((()(((()(((()((((()()(()(((()(())())(((((((((((((()(((()(((((((((((((((...
result:
ok single line: '((((((()())(())((())((()(()(((...))))))))))))()()))(()()))))))))'
Test #19:
score: 63
Accepted
time: 0ms
memory: 3752kb
input:
ccccsullullmmlcllmmculullzzulccuumllllzuuzmsrrzlsuulllrrlscclzzlcuzcccuuczuzzmmuuuumuumuuuzsrrrrssszuczmlcclmmcrccrcmzssssrrrllluulmmrszrrmmrrmlluuccmllmmssrruumsuummsuzzllccusmmmmsmssuzzlmmllluzuuzcccssuurrclrruuulmmlulzluummlclmmzzzscssmmcrrluuccsslssscclsslzuucrmuuccmmuumzzuumuussllmzuuzzrrrrruzc...
output:
((((((())((())(()())(((()()))((((((())(())((()((((((((()(((((()))(((()())((()(((()))())()))((())()))))(((())()((()))))(())(()(()())()))(((((()(()()())()))()))((((()((((()()()))()))))())()(()()))(())(()()()())(()(()(())))))()())(((((((((()())()(()()())())()(())((((((((()((())()())))()())(()()((())(((...
result:
ok single line: '((((((())((())(()())(((()()))(...()())))((()))))))(()))()())))))'
Test #20:
score: 63
Accepted
time: 3ms
memory: 3876kb
input:
qhhhssvggvwwgggsqwghhgssvqvgghqgsqqsswwsqvhgvwvvvgwgvssvgvvshhsssswwswgvqhqqhqhhhwwsvsssswwqqqwwqshghwhqqqvwwgsssswsswswwssvvssgqgqqvvvvgwwsqghhqshhhhqvsssvvgwhhwsqssssqgghqwssqggggssgwvqqqggggwwqgssswqswwwqvvghvshqwwqhsqqssvhssgvvqqqwqqsqwsgqggggqvwgqwqhsgvssvgvqqvghhsvqsqghhqwwwwsqgsssgvqhsswwssws...
output:
((()(((()(()(()((((())(((((((((((((((()((((((((((((((()))()(()(())()))))(((((((()()(((((((((()())(((((((()(()((((((())(()()()))(((()(()))()(((()(((())(((()((((())(((()))()(((()(((()())((((((())())((()((((()(((((((((()))(()))))())))()))()))))))(()))))))))))))())((()))()))))))())(())))))))))))((())))(...
result:
ok single line: '((()(((()(()(()((((())((((((((...(()((())()()))))))))()()(()()))'
Test #21:
score: 63
Accepted
time: 1ms
memory: 3820kb
input:
foczoiaaiikbddbtbeiaeblketbaaftzkdtikmmeatqktzjmbbddmfibbafkioobbzdbbldoqlcccctaqqlcctmqlbrdbdbrrijjejeeffkkooatizdoflorrdftkaffakdmdqdierzddcommbtticbkeebjbbjfafoejtembddfmberztklkbcqmeekrmefjjkbjokkkkkcrrbzajezzeabairbzkddfdettrkaajaztrzmcqieqbbcbbdrmmefrafbltmmmmjkttffbmfrblqcrllzltiqqierlkdocoqd...
output:
((((((()()((())((((((((((((()((((((((()(((((((((()())((()((((((()((()((((((())((()(()((((((((((()(()((()((()()(((((((((()(((((()))(((((((((()(((((()((((((((())((((((((((((((((((((((((((()(((((()(((((((()((((((((())((((((((()(((()((((((((((((((((()(()((()(((((((((())((()((((((((((((((((((((((((((((((...
result:
ok single line: '((((((()()((())((((((((((((()(...)))()(())))))))))))))))))))))))'