QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152651#6618. Encoded Strings IILFCodeWA 2ms8200kbC++141.6kb2023-08-28 16:09:482023-08-28 16:09:48

Judging History

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

  • [2023-08-28 16:09:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8200kb
  • [2023-08-28 16:09:48]
  • 提交

answer

#include<cstdio>
#include<vector>
using namespace std;
const int N=1010,M=20;
int n,len,a[N],vis[N],mn[1<<M],f[1<<M],g[1<<M],lc[1<<M],cnt[N][M],pre[N][M],mx[M+1];
vector<int>vec[M];
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
char gc(){char ch=getchar();while(ch<'a'||ch>'t')ch=getchar();return ch;}
int lowbit(int x){return x&(-x);}
bool dfs(int np,int no){
	if(!np)return true;dfs(g[np],no+1);
	for(int i=1;i<=lc[np];i++)putchar('a'+no);
	return true;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		char ch=gc();
		if(!vis[ch])vis[ch]=++len;
		a[i]=vis[ch]-1;mn[1<<a[i]]=i;
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<len;j++){
			cnt[i][j]=cnt[i-1][j]+(a[i]==j);
			pre[i][j]=(a[i]==j)?i:pre[i-1][j];
		}
	mn[0]=n;
	for(int S=0;S<(1<<len);S++){
		vec[__builtin_popcount(S)].push_back(S);
		if(__builtin_popcount(S)>1)
			mn[S]=Min(mn[S^lowbit(S)],mn[lowbit(S)]);
	}
	for(int i=0;i<len;i++){
		for(vector<int>::iterator it=vec[i].begin();it!=vec[i].end();it++){
			if(lc[*it]!=mx[i])continue;
			for(int j=0;j<len;j++){
				if((*it>>j)&1)continue;
				int nxt=*it|(1<<j);
				int ss=((1<<len)-1)^nxt;
				if(mn[ss]<=f[*it])continue;
				int tot=cnt[mn[ss]][j]-cnt[f[*it]][j];
				if(tot>mx[i+1])mx[i+1]=tot;
				if(tot>lc[nxt]){
					lc[nxt]=tot;
					f[nxt]=pre[mn[ss]][j];
					g[nxt]=*it;
				}
			}
		}
	}
	dfs((1<<len)-1,0);
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7832kb

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

4
acac

output:

bba

result:

ok single line: 'bba'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

score: 0
Accepted
time: 1ms
memory: 7560kb

input:

12
bcabcabcbcbb

output:

ccbbaa

result:

ok single line: 'ccbbaa'

Test #5:

score: 0
Accepted
time: 2ms
memory: 7988kb

input:

1000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7828kb

input:

1000
ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

result:

ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'

Test #7:

score: 0
Accepted
time: 2ms
memory: 7828kb

input:

1000
edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...

output:

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

result:

ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'

Test #8:

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

input:

1000
hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...

output:

ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddccbbbaaa

result:

ok single line: 'dddddddddddddddddddddddddddddd...dddddddddddddddddddddddccbbbaaa'

Test #9:

score: 0
Accepted
time: 1ms
memory: 7816kb

input:

1000
cceooojojcecesjojsssesjojccoecceoojecsscojsosoccojscjcjssococjscssosecooeejoosojeecjceoeeojcocosjcecocoesjceejjecssjejccjsjosjsjcjesjojcojocjjeooeccojjosjcjjcjoecseecsjccojcoessecejcocosecsojeoceejeccejeoosssscecjcssooojoseeccosocoeejjecsjeoecejsoojessoescecjjsscecoccjsjsscccssjoeejsscoesecssco...

output:

eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeddccbaaa

result:

ok single line: 'eeeeeeeeeeeeeeeeeeeeeeeeeeeeee...eeeeeeeeeeeeeeeeeeeeeeeddccbaaa'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7860kb

input:

1000
mmmfqfmpqrccmqfcrprpfppcpcffqcrcrcqmmmqmrfmrpqffppcmqpqqrfqqcffpmqqfmcmpmcfcqcffqmrmqrmmqmffpqqpfqrcppmmpmrqffmfcfffqmrprfcpfqffrrrmcqmpfmpfmprmcrrqqrmcrcmpcffmpfcprmcpmcfmpcfprrqrpcqccpcmmqcqqfmrcrrqrqcmcpqcrcqcrrpmpmfccqcffrrfmpfqqmqcpmfpmqpcmqpmfqpffmqpcrmcmqrqfqqcrfffcfqprcprrmfppfpqqmmrcmc...

output:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeeeeddcbaa

result:

ok single line: 'ffffffffffffffffffffffffffffff...fffffffffffffffffffffeeeeddcbaa'

Test #11:

score: 0
Accepted
time: 2ms
memory: 7780kb

input:

1000
hljikoiljhkhhikjihlhokhjnjlijjhkhinohnioklilhonihliiiohllkniiokjiihkokkkhnijkkkijnnjljoihiljlnjhllnjlhojnjojnnjhllilnnoloiijioiohkononkijhniihjiinononokjjokljjkinonhkojknohijhlilhjjlhkhjoonojlknjnljniklohinhinnnkhnkljjknkjhhlhlkllihhihnlkjklhokkihlhlikjhkjokhkniooljkojjiiljjjnojkiojnkniljnkoljn...

output:

ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggfeedccccbaa

result:

ok single line: 'gggggggggggggggggggggggggggggg...ggggggggggggggggggggfeedccccbaa'

Test #12:

score: 0
Accepted
time: 1ms
memory: 7768kb

input:

1000
cbpfmafbflfblamcccmcbbfqqfpbaaqfpccqqbqfcabmlbbmfqcpfqmcpqcfffacqbpbllappmbmcfpqqfqlcbcaclbbfqmqfqlammbcqblbccqcpabapcbbfcmpfcmmcpccbcbcfblfclmflpfaqppqbfppfpacmfqqafcmlmbqcbbfqaqffpafcbcqfpqmpcabfmcqcqpblfccmffplcbbaamcallbblmbcmammaablfmbfqqlcqacpqfaqpfcbamamcqcmqqffqfcbcffmabcfplabbmfqcampqc...

output:

hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhgggfedcba

result:

ok single line: 'hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...hhhhhhhhhhhhhhhhhhhhhhgggfedcba'

Test #13:

score: 0
Accepted
time: 2ms
memory: 7800kb

input:

1000
oikrbsjdjjsrcdbroobidjojkdjikbirccicdiicbskkciijkssjirjokcjosbbkcdkbrdroirsooiibsjokircbkjbrbkoobkrddcbossoskosbiksodsjkkocoricjkdscdickjdisiddbsdiikdisdcjdkddscdjjrkkddjbbbdidkidddijbibdisbicjokodrcbjkkcrokiciijssjjbscrssccckdjdirbbcocjkobrijssijjcjrcskdobrjcscbocoobdocobrorosiidoscrijjorsrirk...

output:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiihgfeedcba

result:

ok single line: 'iiiiiiiiiiiiiiiiiiiiiiiiiiiiii...iiiiiiiiiiiiiiiiiiiiiihgfeedcba'

Test #14:

score: 0
Accepted
time: 1ms
memory: 8032kb

input:

1000
cmctnhnrhchdnnaitttiirathamrkhtahnmrttkrhdimhatrttatrtmkiminahadihkdkrdthrkrhiandtmhtrdtiinicrmmirinnarkanadnhaatkkakarirnahrtcndarniihkdnddkhitkmdrtarhinirccaitdccnncnmnanhmtrdthkrmakdkktnimictdanrcmrhtcakmcmnahcrahkhtmadmhkrriinakkrhhddmnaknacchtacaktdnmaihnhcmtcchrdmihritatkactmmhattcrkknnkr...

output:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjiiihhhhgggfeeedccbaa

result:

ok single line: 'jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...jjjjjjjjjjjiiihhhhgggfeeedccbaa'

Test #15:

score: 0
Accepted
time: 1ms
memory: 7884kb

input:

1000
bcqeheddhchrddimchmikdfsmimikchdmmbreskiqfbikcdfhhmfbmqrmsibihciqqqsefmebmrbmcedhmdkmiqbdhsmkcqkifmiddhfieqersmksfiidqesisffhhrsbkiddbkbksrchchccifqkciidibqssihmmfrmfbeffhhqdbhmmdsisqkhqmhsmhckbccfreihdreiqqfcdsfffdbhsicbqfirhhchemfihedrbbkekhsfcccfmmieqfrrimsfddbqmkemciqfqrfbsresbhsiceffebfkfd...

output:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllkkkkkkjjihgggfedcba

result:

ok single line: 'llllllllllllllllllllllllllllll...llllllllllllkkkkkkjjihgggfedcba'

Test #16:

score: 0
Accepted
time: 1ms
memory: 8148kb

input:

1000
pdipkeekpamgdiiafeigfaaoktngfpmkggmkdmaicekcoggpattofngagapfaifodftdmkfoctpdkkomkttgpotdggeeonkdieocdcdnffiittompaopieonamnpiigienpenieaigfiieaeiiftmpkaaegopdeamatngamagapfnppkgciptpnmpcmiagfdoaiemftddddenikaiidmmdopfapgnmefdidgdkegofmeofnetktinipopkfdpkikcodtkapngefetkaffgppkkieikmfadottcceipk...

output:

mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmlllkjjjjiiihggfedcba

result:

ok single line: 'mmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...mmmmmmmmmmmlllkjjjjiiihggfedcba'

Test #17:

score: 0
Accepted
time: 2ms
memory: 7916kb

input:

1000
redfdnprmcbbhfdlmepnolpfotdhlrrlbedeccnrdblprfbdptohmbldthoorcrnceelhochsrppfbotmlchhsftlemfhbcnpdltofescnhmdhombpcddpscfhnmrnordbehnpdlrbbbfcdsoohpbhtcpsrhffobpehhdtmfcmmsbnpcedtmpfcpfporehfbfbotcpbeobnlednofedbpldcrosfcfnplnhbdlohfedrpsosmrpedenpfrrnsbehslloeldemsoeenfrsssppldtnfelrlboepptlpo...

output:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnmmllkkjjihhhhgfeeeeddcba

result:

ok single line: 'nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...nnnnnnnmmllkkjjihhhhgfeeeeddcba'

Test #18:

score: -100
Wrong Answer
time: 1ms
memory: 8200kb

input:

1000
hegsdmeapjipglsnfmianparlaersaragrlepapooflllgnsiggjdjdpraslojdfdaaesfpllhnihselidejrgrfmmaldfnrejophlanehrdsjrrsidomemhmeafrgrrajrrfrjjgpfmgsprifnolfglhmnfapljamsldgrfsomopfedsegdadmojparrssjpfsfaporljfhsfhhgrnilmhdlppoldhaomrjprnfirlmnnhfseofjenrohflfndfiimmsirjopeeipafhphogsafrngjjiprnifeila...

output:

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooonnmllkjjiihhggfedcbbba

result:

wrong answer 1st lines differ - expected: 'oooooooooooooooooooooooooooooo...oooooooonnmllkjjiihhggfedcbbbba', found: 'oooooooooooooooooooooooooooooo...ooooooooonnmllkjjiihhggfedcbbba'