QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591355#5534. Matchliuhengxi100 ✓19ms28552kbC++142.0kb2024-09-26 15:32:212024-09-26 15:32:23

Judging History

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

  • [2024-09-26 15:32:23]
  • 评测
  • 测评结果:100
  • 用时:19ms
  • 内存:28552kb
  • [2024-09-26 15:32:21]
  • 提交

answer

// created:  2024-09-26 15:09:39
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<chrono>
#include<random>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned long long ull;
struct hash4
{
	static constexpr int MOD[4]={1036503019,937029311,897183317,920341061};
	static int bas[4];
	int a[4];
	void append(int c)
	{
		F(i,0,4)a[i]=(int)(((ull)a[i]*bas[i]+c)%MOD[i]);
	}
	friend bool operator<(const hash4 &u,const hash4 &v){return memcmp(&u,&v,sizeof(hash4))<0;}
	friend bool operator==(const hash4 &u,const hash4 &v){return !memcmp(&u,&v,sizeof(hash4));}
};
constexpr int hash4::MOD[4];
int hash4::bas[4];
constexpr int N=1e5+5,S=26;
int n,t,to[N][S],la[N][S],id[N],b[N],su[N];
hash4 sh[N],h[N];
char a[N],s[N];
int main()
{
	{
		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
		F(i,0,4)hash4::bas[i]=(int)(rnd()%500000000+100000000);
	}
	scanf("%s",a);
	while(a[n])++n;
	F(i,0,n)
	{
		if(t&&s[t-1]==a[i])--t;
		else s[t++]=a[i],(sh[t]=sh[t-1]).append(a[i]);
		h[i+1]=sh[t];
	}
	if(t)return puts("-1"),0;
	F(i,0,n+1)id[i]=i;
	sort(id,id+n+1,[](const int &u,const int &v){return h[u]<h[v];});
	F(i,1,n+1)b[id[i]]=h[id[i]]==h[id[i-1]]?b[id[i-1]]:i;
	memset(la,0xff,sizeof(int)*S*n);
	F(i,0,n)
	{
		la[b[i+1]][a[i]-'a']=i;
		memcpy(to[i+1],la[b[i+1]],sizeof(int)*S);
	}
	su[0]=n;
	F(i,0,n)
	{
		if((su[t+1]=to[su[t]][a[i]-'a'])>i)putchar('('),++t;
		else putchar(')'),--t;
		if(t<0)return 1;
	}
	puts("");
	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: 11892kb

input:

abbaaa

output:

(()())

result:

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

Test #2:

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

input:

cbbbbccbbccbbbbbbc

output:

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

result:

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

Test #3:

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

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: 7888kb

input:

fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...

output:

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

result:

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

Test #5:

score: 27
Accepted
time: 1ms
memory: 7888kb

input:

vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...

output:

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

result:

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

Test #6:

score: 27
Accepted
time: 2ms
memory: 11964kb

input:

uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...

output:

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

result:

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

Test #7:

score: 27
Accepted
time: 1ms
memory: 8044kb

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: 12280kb

input:

jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...

output:

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

result:

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

Test #9:

score: 63
Accepted
time: 9ms
memory: 21376kb

input:

zpujdttdnwtkfdfyddtbocyaeniizwubzgeybkccezxjldgtskmjfdywqlrihhckmbmvewoludvvmamdgkeholteaqujgssidpivwljbsnqgxltiviiwsvtekxiftlfkkudkwmbqczskkjsnilevhvdmuelnufvftyphloppctvwksjffecxblezsryszkxrjthxowwrittvjinyfkklllkydvzciiuaayomqjulladasktsyrvffdeennbwelfnhqoisiommrolzfvzkddskonisxlasgckqioouyqtsqfq...

output:

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

result:

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

Test #10:

score: 63
Accepted
time: 10ms
memory: 23236kb

input:

azekdamqaoetekbsselhazotlwwjnpxxceapyxsvgxutdtnnzzvovngkkrwvjrlddncosheotmepxghaeiakddfjzugxqunauvcbyipxtzkrjsdrjbcaozefshjwyrbdviigqvrpkkeamsvnkoyafpululfzaakbwgjkhfpnwihzeuwmydiazwjujussexlzbriochtfyvwbgpduxnkwvpycobczuuzmytnlllrvtyhzzwawtzkamqucyauxrlgthhayaidysemasybwnkjjiqoscacwsqprwjdfshttqriq...

output:

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

result:

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

Test #11:

score: 63
Accepted
time: 12ms
memory: 23588kb

input:

mldshhxgdtnevvjvvvmdxxppbbrxxtpwboorjjrgpmmmnvthhjjtvbrpxpsxxsjjxtjjtpbevhhvvduprhjshccwoggsllsdcbbuubbutlojstebhrpnwsoxnopprssbuljwmxvgpprwlxnossuggmovhsggcbddprrhsthwnsleevshtnlodsjelhntswuultovcbbclndjjhnvvwewvodnmpslwnseupvccvshuusxvunnmoeeggoobbttsojjnjpvxdewnnndnlmeebprppsrppjcessehrrjnuutgpco...

output:

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

result:

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

Test #12:

score: 63
Accepted
time: 14ms
memory: 25720kb

input:

baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...

output:

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

result:

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

Test #13:

score: 63
Accepted
time: 14ms
memory: 27720kb

input:

baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...

output:

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

result:

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

Test #14:

score: 63
Accepted
time: 12ms
memory: 27948kb

input:

fbbfffbfbbgbgbfffggfbbfgfbggbbbgfgffgfgfbbfbbfbbgfbggfbbffbbfbbbffbfbfbbgbffgfgfgbbggbbfgfbfbgfgggbggbgbgfbfgbfgbggggggbffgggbffffbbbgfgffgbbgbbbgfffffbgbbgfffbbgbgbbbbgbfbfbbbbbbbfbbfgfbbffbfffgfgbgfggbffffbbgfgfbffbfbbbgffgbbgbggggbgbggggbffggbggbbgfgbfgbgfgbbfbgbbfgbgffgffggfffgfgfbggbgfbgfffbbbg...

output:

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

result:

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

Test #15:

score: 63
Accepted
time: 12ms
memory: 26208kb

input:

aaaaaababbbaababaababbbabaabbabbaabaabaaaaaabaababbbaaaaaabaaaaaababbbbaaabbaaabaaabaabbabbabbbbababababaaabbabbabaabaaaaabbbbabbbaabbbbbbaabbaabaaaabbaabaaabababbaabaaaaabaaaaaaaaaabbbaabbaaaabbbabbabbaaabbbbabbbababbaaaaaabaabbabaaababaababbbababaaabaaaabbabaaaaabbababaabaabaabaaaaababbaabaabaabaa...

output:

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

result:

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

Test #16:

score: 63
Accepted
time: 18ms
memory: 26708kb

input:

sccsyqrchhcltthddqhtyymrttrmqmdssyftssyyhlhsltqtcctrqqcltyhlcylqfsfqqccqhdstcrshclthdcttmqtqcttdhfyhymqdtmmqmmlyylccyrrlqhhrcsyydtdrrydsqllqcccftlqqqqlqchsccfqrrrscctchhryyfqccccyrhqrmmrmlddssfylfrlslssdtttqlsslqqldfyrtsclccdsfqcmmcyhhdmlltssryshcmmflsdydscmyfmmqyymfyqrclqqcyrfhrtlchccmryyhhtssdfdmm...

output:

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

result:

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

Test #17:

score: 63
Accepted
time: 11ms
memory: 21576kb

input:

ovavvsmodolxnnvvvvnyyjggbddkvuuvlntjgvrrfqfjkgfqkbyiiiyxdshumxnmnksxxylkitzgooswtwidwwnfyvqbbdlvnsucpqxrrewwtkkffkpwuzrbiivqqssiaafkzzjhhpajcnuampgcovspbnlmszqigrfbbfqwnmvhryfoylvvbjhvepcppdixowicuurbjhvrmttifflliodtmmmtiitmmluaadrbnnfnjxtutbuqzivznlccuccnliolidijxnytuolnbgeuxdkwjpzwmpbvjzzschuddezz...

output:

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

result:

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

Test #18:

score: 63
Accepted
time: 19ms
memory: 28552kb

input:

slrusyssppylssldouuosrrrssslslpppplllrpossopyuuusluuooouuppllloyddlpdyldssyypploduusluuuurddryoyuldysdullsrrspyrrposddpyyodrssrrrllllulslolloullrlusslyoyyosuuddpysyprryodudpdpsoyydpylyoopsoosrssdppdlruurlpyspodyylyysyulyylssduyydlrrlrpyydpsooduoollddyuuysosslpplddoyssdpspoylrryllpyrrrsrsullurupyudos...

output:

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

result:

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

Test #19:

score: 63
Accepted
time: 0ms
memory: 12156kb

input:

ccccsullullmmlcllmmculullzzulccuumllllzuuzmsrrzlsuulllrrlscclzzlcuzcccuuczuzzmmuuuumuumuuuzsrrrrssszuczmlcclmmcrccrcmzssssrrrllluulmmrszrrmmrrmlluuccmllmmssrruumsuummsuzzllccusmmmmsmssuzzlmmllluzuuzcccssuurrclrruuulmmlulzluummlclmmzzzscssmmcrrluuccsslssscclsslzuucrmuuccmmuumzzuumuussllmzuuzzrrrrruzc...

output:

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

result:

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

Test #20:

score: 63
Accepted
time: 0ms
memory: 12092kb

input:

qhhhssvggvwwgggsqwghhgssvqvgghqgsqqsswwsqvhgvwvvvgwgvssvgvvshhsssswwswgvqhqqhqhhhwwsvsssswwqqqwwqshghwhqqqvwwgsssswsswswwssvvssgqgqqvvvvgwwsqghhqshhhhqvsssvvgwhhwsqssssqgghqwssqggggssgwvqqqggggwwqgssswqswwwqvvghvshqwwqhsqqssvhssgvvqqqwqqsqwsgqggggqvwgqwqhsgvssvgvqqvghhsvqsqghhqwwwwsqgsssgvqhsswwssws...

output:

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

result:

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

Test #21:

score: 63
Accepted
time: 0ms
memory: 12072kb

input:

foczoiaaiikbddbtbeiaeblketbaaftzkdtikmmeatqktzjmbbddmfibbafkioobbzdbbldoqlcccctaqqlcctmqlbrdbdbrrijjejeeffkkooatizdoflorrdftkaffakdmdqdierzddcommbtticbkeebjbbjfafoejtembddfmberztklkbcqmeekrmefjjkbjokkkkkcrrbzajezzeabairbzkddfdettrkaajaztrzmcqieqbbcbbdrmmefrafbltmmmmjkttffbmfrblqcrllzltiqqierlkdocoqd...

output:

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

result:

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