QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152657 | #6618. Encoded Strings II | LFCode | WA | 16ms | 24236kb | C++14 | 1.6kb | 2023-08-28 16:14:12 | 2023-08-28 16:14:12 |
Judging History
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++){
if(mx[i]==0&&i>0)puts("GG");
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]||(tot==lc[nxt]&&pre[mn[ss]][j]<f[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: 7720kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7888kb
input:
4 acac
output:
bba
result:
ok single line: 'bba'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7732kb
input:
1 t
output:
a
result:
ok single line: 'a'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7732kb
input:
12 bcabcabcbcbb
output:
ccbbaa
result:
ok single line: 'ccbbaa'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7820kb
input:
1000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7876kb
input:
1000 ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...
output:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
result:
ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7808kb
input:
1000 edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7868kb
input:
1000 hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...
output:
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddccbbbaaa
result:
ok single line: 'dddddddddddddddddddddddddddddd...dddddddddddddddddddddddccbbbaaa'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7872kb
input:
1000 cceooojojcecesjojsssesjojccoecceoojecsscojsosoccojscjcjssococjscssosecooeejoosojeecjceoeeojcocosjcecocoesjceejjecssjejccjsjosjsjcjesjojcojocjjeooeccojjosjcjjcjoecseecsjccojcoessecejcocosecsojeoceejeccejeoosssscecjcssooojoseeccosocoeejjecsjeoecejsoojessoescecjjsscecoccjsjsscccssjoeejsscoesecssco...
output:
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeddccbaaa
result:
ok single line: 'eeeeeeeeeeeeeeeeeeeeeeeeeeeeee...eeeeeeeeeeeeeeeeeeeeeeeddccbaaa'
Test #10:
score: 0
Accepted
time: 2ms
memory: 7808kb
input:
1000 mmmfqfmpqrccmqfcrprpfppcpcffqcrcrcqmmmqmrfmrpqffppcmqpqqrfqqcffpmqqfmcmpmcfcqcffqmrmqrmmqmffpqqpfqrcppmmpmrqffmfcfffqmrprfcpfqffrrrmcqmpfmpfmprmcrrqqrmcrcmpcffmpfcprmcpmcfmpcfprrqrpcqccpcmmqcqqfmrcrrqrqcmcpqcrcqcrrpmpmfccqcffrrfmpfqqmqcpmfpmqpcmqpmfqpffmqpcrmcmqrqfqqcrfffcfqprcprrmfppfpqqmmrcmc...
output:
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeeeeddcbaa
result:
ok single line: 'ffffffffffffffffffffffffffffff...fffffffffffffffffffffeeeeddcbaa'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
1000 hljikoiljhkhhikjihlhokhjnjlijjhkhinohnioklilhonihliiiohllkniiokjiihkokkkhnijkkkijnnjljoihiljlnjhllnjlhojnjojnnjhllilnnoloiijioiohkononkijhniihjiinononokjjokljjkinonhkojknohijhlilhjjlhkhjoonojlknjnljniklohinhinnnkhnkljjknkjhhlhlkllihhihnlkjklhokkihlhlikjhkjokhkniooljkojjiiljjjnojkiojnkniljnkoljn...
output:
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggfeedccccbaa
result:
ok single line: 'gggggggggggggggggggggggggggggg...ggggggggggggggggggggfeedccccbaa'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7908kb
input:
1000 cbpfmafbflfblamcccmcbbfqqfpbaaqfpccqqbqfcabmlbbmfqcpfqmcpqcfffacqbpbllappmbmcfpqqfqlcbcaclbbfqmqfqlammbcqblbccqcpabapcbbfcmpfcmmcpccbcbcfblfclmflpfaqppqbfppfpacmfqqafcmlmbqcbbfqaqffpafcbcqfpqmpcabfmcqcqpblfccmffplcbbaamcallbblmbcmammaablfmbfqqlcqacpqfaqpfcbamamcqcmqqffqfcbcffmabcfplabbmfqcampqc...
output:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhgggfedcba
result:
ok single line: 'hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...hhhhhhhhhhhhhhhhhhhhhhgggfedcba'
Test #13:
score: 0
Accepted
time: 0ms
memory: 7844kb
input:
1000 oikrbsjdjjsrcdbroobidjojkdjikbirccicdiicbskkciijkssjirjokcjosbbkcdkbrdroirsooiibsjokircbkjbrbkoobkrddcbossoskosbiksodsjkkocoricjkdscdickjdisiddbsdiikdisdcjdkddscdjjrkkddjbbbdidkidddijbibdisbicjokodrcbjkkcrokiciijssjjbscrssccckdjdirbbcocjkobrijssijjcjrcskdobrjcscbocoobdocobrorosiidoscrijjorsrirk...
output:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiihgfeedcba
result:
ok single line: 'iiiiiiiiiiiiiiiiiiiiiiiiiiiiii...iiiiiiiiiiiiiiiiiiiiiihgfeedcba'
Test #14:
score: 0
Accepted
time: 2ms
memory: 8048kb
input:
1000 cmctnhnrhchdnnaitttiirathamrkhtahnmrttkrhdimhatrttatrtmkiminahadihkdkrdthrkrhiandtmhtrdtiinicrmmirinnarkanadnhaatkkakarirnahrtcndarniihkdnddkhitkmdrtarhinirccaitdccnncnmnanhmtrdthkrmakdkktnimictdanrcmrhtcakmcmnahcrahkhtmadmhkrriinakkrhhddmnaknacchtacaktdnmaihnhcmtcchrdmihritatkactmmhattcrkknnkr...
output:
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjiiihhhhgggfeeedccbaa
result:
ok single line: 'jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...jjjjjjjjjjjiiihhhhgggfeeedccbaa'
Test #15:
score: 0
Accepted
time: 2ms
memory: 10132kb
input:
1000 bcqeheddhchrddimchmikdfsmimikchdmmbreskiqfbikcdfhhmfbmqrmsibihciqqqsefmebmrbmcedhmdkmiqbdhsmkcqkifmiddhfieqersmksfiidqesisffhhrsbkiddbkbksrchchccifqkciidibqssihmmfrmfbeffhhqdbhmmdsisqkhqmhsmhckbccfreihdreiqqfcdsfffdbhsicbqfirhhchemfihedrbbkekhsfcccfmmieqfrrimsfddbqmkemciqfqrfbsresbhsiceffebfkfd...
output:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllkkkkkkjjihgggfedcba
result:
ok single line: 'llllllllllllllllllllllllllllll...llllllllllllkkkkkkjjihgggfedcba'
Test #16:
score: 0
Accepted
time: 1ms
memory: 8096kb
input:
1000 pdipkeekpamgdiiafeigfaaoktngfpmkggmkdmaicekcoggpattofngagapfaifodftdmkfoctpdkkomkttgpotdggeeonkdieocdcdnffiittompaopieonamnpiigienpenieaigfiieaeiiftmpkaaegopdeamatngamagapfnppkgciptpnmpcmiagfdoaiemftddddenikaiidmmdopfapgnmefdidgdkegofmeofnetktinipopkfdpkikcodtkapngefetkaffgppkkieikmfadottcceipk...
output:
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmlllkjjjjiiihggfedcba
result:
ok single line: 'mmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...mmmmmmmmmmmlllkjjjjiiihggfedcba'
Test #17:
score: 0
Accepted
time: 1ms
memory: 8052kb
input:
1000 redfdnprmcbbhfdlmepnolpfotdhlrrlbedeccnrdblprfbdptohmbldthoorcrnceelhochsrppfbotmlchhsftlemfhbcnpdltofescnhmdhombpcddpscfhnmrnordbehnpdlrbbbfcdsoohpbhtcpsrhffobpehhdtmfcmmsbnpcedtmpfcpfporehfbfbotcpbeobnlednofedbpldcrosfcfnplnhbdlohfedrpsosmrpedenpfrrnsbehslloeldemsoeenfrsssppldtnfelrlboepptlpo...
output:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnmmllkkjjihhhhgfeeeeddcba
result:
ok single line: 'nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...nnnnnnnmmllkkjjihhhhgfeeeeddcba'
Test #18:
score: 0
Accepted
time: 2ms
memory: 8240kb
input:
1000 hegsdmeapjipglsnfmianparlaersaragrlepapooflllgnsiggjdjdpraslojdfdaaesfpllhnihselidejrgrfmmaldfnrejophlanehrdsjrrsidomemhmeafrgrrajrrfrjjgpfmgsprifnolfglhmnfapljamsldgrfsomopfedsegdadmojparrssjpfsfaporljfhsfhhgrnilmhdlppoldhaomrjprnfirlmnnhfseofjenrohflfndfiimmsirjopeeipafhphogsafrngjjiprnifeila...
output:
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooonnmllkjjiihhggfedcbbbba
result:
ok single line: 'oooooooooooooooooooooooooooooo...oooooooonnmllkjjiihhggfedcbbbba'
Test #19:
score: 0
Accepted
time: 0ms
memory: 8188kb
input:
1000 dgenmltemgsnbimnhicfomcbbliddfhllohldnthotglfeoobtohilblglibclhdlmmfgseslgseiimkhhbflfekildtgllfdkjolnilbtscnfjklfidbknhlljkokodbtmoccbiigicgnfdfbhktcomilkbijisdhmjcmgbkomojjfmdnjltbmnnsbslbtflkkbsofehhnndmjtifsisggeocdbtolimtnlhcoekedjsnhoobbjnhihbbtkomnjomiskfobilkjkbocdmhnffglfogtosndsitecdf...
output:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppoooonnnmmllkkjjihhgfedcbbbaa
result:
ok single line: 'pppppppppppppppppppppppppppppp...pppoooonnnmmllkkjjihhgfedcbbbaa'
Test #20:
score: 0
Accepted
time: 1ms
memory: 14468kb
input:
1000 chkkcqdcggjsjadhtrjqgntecdhgrsqsbkqqqsodfkfcblqntsjrjnfcteghkafgjqtaaabdddakcbnabaqtoqdkogfgqaebrsdcdqkadkeqoleknokgfhshkqdhhsjddatblonnlnkllordrbgjjsjdedhlgsdsodcbcbojaehanhqetgnasocghtcrdbqdclegfscnqcelofffckefedohhadlhhnadnffbkreeletoknrrhrffrogrcgghaeglcefhbaaefggaabohttrstfgfqgcnnbeqjdklqr...
output:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqpppooonnmmlkjiihgffedcba
result:
ok single line: 'qqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...qqqqqqqpppooonnmmlkjiihgffedcba'
Test #21:
score: 0
Accepted
time: 1ms
memory: 8896kb
input:
1000 mmimrctldielpadeocgmaifcafkhjccnaktgmsejehgcoialclsopnrokmamnahangmhfmgcrmlatislecsgiaaarkpssscshtcrncptsoijirnogggititpohtgcaegdaaeoegmioridoggttsorppehjhiondejafeanspotcngepscflcseeikasopdmdthgnasdnfedkookrnkjcsinkejkiskasoecnlnkigrdfktopfcoehlsednknimtshljrdlnnainrfskmddegerildgcnkmfoapefalm...
output:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrqqqqqqponnmmlkjihgfedcba
result:
ok single line: 'rrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...rrrrrrrqqqqqqponnmmlkjihgfedcba'
Test #22:
score: 0
Accepted
time: 7ms
memory: 14088kb
input:
1000 qdjplrlfkgqbnncnglcfdijiifboesenqmfjilnqrppabmntsgdefcjrkotiejacrdmqqoegtspofdejngqmddjatlfakscdcfdfjfrqkfllmoteldgnirkmpmbjfpkkiblsnjsqjijposifejtoliolrfionfiirqrdojcfqipraenpfeqfqcegkfctssmrrbdjkkrbctqiqejsfsqcgdnoaelcfaslegtrcefleqqjbtgjpbjrdqtmajcfgotetrkeeoqptnsbkgoaedsqorniralmeklcigocfal...
output:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssrrqqqqqqppoonnmlllkkjihgfedcba
result:
ok single line: 'ssssssssssssssssssssssssssssss...srrqqqqqqppoonnmlllkkjihgfedcba'
Test #23:
score: -100
Wrong Answer
time: 16ms
memory: 24236kb
input:
1000 opaqmbjhoctlnmefoocaqnqtecgbnirdjjhqkhiftktbslrpbacpjbrbreapkptlrcpjqpfobtiiqqtjpsrpitbljanmfdfbhldlplsniffflegrtckqjdarlhleffsalnjgmfrpasfgatgfffraheohidlolipksnskjjfaihidesjnlasitccjbbhpheglpdertnqqlgsfafikpneglbokpfaejipaeolmdrinnafpntfichatljgiqlaqhfmsmggdohcncpihiinqbssjnaleiripnbgllhcnnha...
output:
GG nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnmmlkkkjiihgfffedcbaa
result:
wrong answer 1st lines differ - expected: 'tttttttttttttttttttttttttttttt...tttsrrqpppoonmmllkkjihgfeeedcba', found: 'GG'