QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591194#5534. MatchBreakPlus100 ✓26ms47112kbC++142.2kb2024-09-26 14:43:432024-09-26 14:43:45

Judging History

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

  • [2024-09-26 14:43:45]
  • 评测
  • 测评结果:100
  • 用时:26ms
  • 内存:47112kb
  • [2024-09-26 14:43:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
void init(){ }
char s[100005]; ll n;
ll f[26][100005],nxt[100005],suc[100005];
ll g[26][100005],prv[100005];
ll stk[100005];

char ans[100005];
bool check(ll l,ll r){
	if(l==r+1) return 1;
	// cout<<"checking "<<l<<"->"<<r<<endl;
	ll now=r;
	while(1){
		now=prv[now];
		if(now==l) return 1;
		else if(now<l) return 0;
		now--;
	}
	return 0;
}
void procedure(){
	scanf("%s", s+1); n=strlen(s+1);
	memset(f,0x3f,sizeof(f)); memset(nxt,0x3f,sizeof(nxt));
	f[s[n]-'a'][n]=n;
	for(ll i=n-1;i>=1;i--){
		nxt[i]=f[s[i]-'a'][i+1];
		if(nxt[i]==n) suc[i]=1;
		if(nxt[i]<n) suc[i] |= suc[nxt[i]+1];
		f[s[i]-'a'][i]=i;
		if(nxt[i]<n){
			for(ll j=0;j<=25;j++)
				f[j][i]=min(f[j][i], f[j][nxt[i]+1]);
		}
	}
	if(!suc[1]) {
		puts("-1");
		return;
	}
	g[s[1]-'a'][1]=1;
	for(ll i=2;i<=n;i++){
		prv[i]=g[s[i]-'a'][i-1];
		g[s[i]-'a'][i]=i;
		if(prv[i]>1){
			for(ll j=0;j<=25;j++)
				g[j][i]=max(g[j][i], g[j][prv[i]-1]);
		}
	}

	// for(ll i=1;i<=n;i++){
	// 	printf("%lld: %lld %lld %lld\n", i, prv[i], g[0][i], g[1][i]);
	// }
	ans[n+1]='\0';
	vector<ll>vc = {n+1};
	for(ll i=1;i<=n;i++){
		ll now=g[s[i]-'a'][vc.back()-1];
		// cout<<"here now = "<<now<<endl;
		if(now <= i || !check(i+1, now-1)){
			// cout<<"erasing "<<endl;
			vc.pop_back();
			ans[i]=')';
		}else vc.pb(now), ans[i]='(';// cout<<"adding"<<endl;
	}
	printf("%s\n", ans+1);
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=1;
	init();
	while(T--) procedure();
	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: 27528kb

input:

abbaaa

output:

(()())

result:

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

Test #2:

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

input:

cbbbbccbbccbbbbbbc

output:

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

result:

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

Test #3:

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

input:

ddbcbdacccbddaba

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 27
Accepted

Dependency #1:

100%
Accepted

Test #4:

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

input:

fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...

output:

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

result:

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

Test #5:

score: 27
Accepted
time: 0ms
memory: 30856kb

input:

vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...

output:

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

result:

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

Test #6:

score: 27
Accepted
time: 0ms
memory: 31452kb

input:

uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...

output:

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

result:

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

Test #7:

score: 27
Accepted
time: 3ms
memory: 29788kb

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: 3ms
memory: 28912kb

input:

jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...

output:

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

result:

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

Test #9:

score: 63
Accepted
time: 4ms
memory: 38660kb

input:

zpujdttdnwtkfdfyddtbocyaeniizwubzgeybkccezxjldgtskmjfdywqlrihhckmbmvewoludvvmamdgkeholteaqujgssidpivwljbsnqgxltiviiwsvtekxiftlfkkudkwmbqczskkjsnilevhvdmuelnufvftyphloppctvwksjffecxblezsryszkxrjthxowwrittvjinyfkklllkydvzciiuaayomqjulladasktsyrvffdeennbwelfnhqoisiommrolzfvzkddskonisxlasgckqioouyqtsqfq...

output:

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

result:

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

Test #10:

score: 63
Accepted
time: 7ms
memory: 39668kb

input:

azekdamqaoetekbsselhazotlwwjnpxxceapyxsvgxutdtnnzzvovngkkrwvjrlddncosheotmepxghaeiakddfjzugxqunauvcbyipxtzkrjsdrjbcaozefshjwyrbdviigqvrpkkeamsvnkoyafpululfzaakbwgjkhfpnwihzeuwmydiazwjujussexlzbriochtfyvwbgpduxnkwvpycobczuuzmytnlllrvtyhzzwawtzkamqucyauxrlgthhayaidysemasybwnkjjiqoscacwsqprwjdfshttqriq...

output:

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

result:

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

Test #11:

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

input:

mldshhxgdtnevvjvvvmdxxppbbrxxtpwboorjjrgpmmmnvthhjjtvbrpxpsxxsjjxtjjtpbevhhvvduprhjshccwoggsllsdcbbuubbutlojstebhrpnwsoxnopprssbuljwmxvgpprwlxnossuggmovhsggcbddprrhsthwnsleevshtnlodsjelhntswuultovcbbclndjjhnvvwewvodnmpslwnseupvccvshuusxvunnmoeeggoobbttsojjnjpvxdewnnndnlmeebprppsrppjcessehrrjnuutgpco...

output:

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

result:

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

Test #12:

score: 63
Accepted
time: 22ms
memory: 43692kb

input:

baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...

output:

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

result:

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

Test #13:

score: 63
Accepted
time: 26ms
memory: 43692kb

input:

baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...

output:

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

result:

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

Test #14:

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

input:

fbbfffbfbbgbgbfffggfbbfgfbggbbbgfgffgfgfbbfbbfbbgfbggfbbffbbfbbbffbfbfbbgbffgfgfgbbggbbfgfbfbgfgggbggbgbgfbfgbfgbggggggbffgggbffffbbbgfgffgbbgbbbgfffffbgbbgfffbbgbgbbbbgbfbfbbbbbbbfbbfgfbbffbfffgfgbgfggbffffbbgfgfbffbfbbbgffgbbgbggggbgbggggbffggbggbbgfgbfgbgfgbbfbgbbfgbgffgffggfffgfgfbggbgfbgfffbbbg...

output:

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

result:

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

Test #15:

score: 63
Accepted
time: 7ms
memory: 45272kb

input:

aaaaaababbbaababaababbbabaabbabbaabaabaaaaaabaababbbaaaaaabaaaaaababbbbaaabbaaabaaabaabbabbabbbbababababaaabbabbabaabaaaaabbbbabbbaabbbbbbaabbaabaaaabbaabaaabababbaabaaaaabaaaaaaaaaabbbaabbaaaabbbabbabbaaabbbbabbbababbaaaaaabaabbabaaababaababbbababaaabaaaabbabaaaaabbababaabaabaabaaaaababbaabaabaabaa...

output:

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

result:

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

Test #16:

score: 63
Accepted
time: 3ms
memory: 46760kb

input:

sccsyqrchhcltthddqhtyymrttrmqmdssyftssyyhlhsltqtcctrqqcltyhlcylqfsfqqccqhdstcrshclthdcttmqtqcttdhfyhymqdtmmqmmlyylccyrrlqhhrcsyydtdrrydsqllqcccftlqqqqlqchsccfqrrrscctchhryyfqccccyrhqrmmrmlddssfylfrlslssdtttqlsslqqldfyrtsclccdsfqcmmcyhhdmlltssryshcmmflsdydscmyfmmqyymfyqrclqqcyrfhrtlchccmryyhhtssdfdmm...

output:

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

result:

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

Test #17:

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

input:

ovavvsmodolxnnvvvvnyyjggbddkvuuvlntjgvrrfqfjkgfqkbyiiiyxdshumxnmnksxxylkitzgooswtwidwwnfyvqbbdlvnsucpqxrrewwtkkffkpwuzrbiivqqssiaafkzzjhhpajcnuampgcovspbnlmszqigrfbbfqwnmvhryfoylvvbjhvepcppdixowicuurbjhvrmttifflliodtmmmtiitmmluaadrbnnfnjxtutbuqzivznlccuccnliolidijxnytuolnbgeuxdkwjpzwmpbvjzzschuddezz...

output:

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

result:

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

Test #18:

score: 63
Accepted
time: 4ms
memory: 47112kb

input:

slrusyssppylssldouuosrrrssslslpppplllrpossopyuuusluuooouuppllloyddlpdyldssyypploduusluuuurddryoyuldysdullsrrspyrrposddpyyodrssrrrllllulslolloullrlusslyoyyosuuddpysyprryodudpdpsoyydpylyoopsoosrssdppdlruurlpyspodyylyysyulyylssduyydlrrlrpyydpsooduoollddyuuysosslpplddoyssdpspoylrryllpyrrrsrsullurupyudos...

output:

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

result:

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

Test #19:

score: 63
Accepted
time: 4ms
memory: 32044kb

input:

ccccsullullmmlcllmmculullzzulccuumllllzuuzmsrrzlsuulllrrlscclzzlcuzcccuuczuzzmmuuuumuumuuuzsrrrrssszuczmlcclmmcrccrcmzssssrrrllluulmmrszrrmmrrmlluuccmllmmssrruumsuummsuzzllccusmmmmsmssuzzlmmllluzuuzcccssuurrclrruuulmmlulzluummlclmmzzzscssmmcrrluuccsslssscclsslzuucrmuuccmmuumzzuumuussllmzuuzzrrrrruzc...

output:

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

result:

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

Test #20:

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

input:

qhhhssvggvwwgggsqwghhgssvqvgghqgsqqsswwsqvhgvwvvvgwgvssvgvvshhsssswwswgvqhqqhqhhhwwsvsssswwqqqwwqshghwhqqqvwwgsssswsswswwssvvssgqgqqvvvvgwwsqghhqshhhhqvsssvvgwhhwsqssssqgghqwssqggggssgwvqqqggggwwqgssswqswwwqvvghvshqwwqhsqqssvhssgvvqqqwqqsqwsgqggggqvwgqwqhsgvssvgvqqvghhsvqsqghhqwwwwsqgsssgvqhsswwssws...

output:

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

result:

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

Test #21:

score: 63
Accepted
time: 3ms
memory: 29060kb

input:

foczoiaaiikbddbtbeiaeblketbaaftzkdtikmmeatqktzjmbbddmfibbafkioobbzdbbldoqlcccctaqqlcctmqlbrdbdbrrijjejeeffkkooatizdoflorrdftkaffakdmdqdierzddcommbtticbkeebjbbjfafoejtembddfmberztklkbcqmeekrmefjjkbjokkkkkcrrbzajezzeabairbzkddfdettrkaajaztrzmcqieqbbcbbdrmmefrafbltmmmmjkttffbmfrblqcrllzltiqqierlkdocoqd...

output:

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

result:

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