QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584605 | #6618. Encoded Strings II | Soestx | WA | 71ms | 14384kb | C++14 | 1.6kb | 2024-09-23 15:44:16 | 2024-09-23 15:44:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
//typedef long long ll;
//typedef unsigned long long ull;
const int N = 2e6 + 10, M = 1e6,mod=998244353;
int n, m, k;
int num[N];
int res;
int la[30];
int dp[N],sum[1010][30],pre[1010][30];
int book[30];
int cnt;
void dfs(int ct,int l,int w)
{
if(ct==cnt+1) return;
int su=0;
int tmp=(1<<20)-1;
tmp^=w;
for(int i=0;i<20;i++)
{
int bk=((tmp>>i)&1);
if(!bk||!la[i]) continue;
int tp=(tmp^(1<<i));
int r=dp[tp]-1;
if(r>1e7) continue;
su=max(su,sum[r][i]-sum[l-1][i]);
}
if(su<num[ct]) return;
num[ct]=su;
for(int i=ct+1;i<=cnt;i++) num[i]=0;
for(int i=0;i<20;i++)
{
int bk=((tmp>>i)&1);
if(!bk||!la[i]) continue;
int tp=(tmp^(1<<i));
int r=dp[tp]-1;
if(su==sum[r][i]-sum[l-1][i])
{
dfs(ct+1,pre[r][i]+1,(w|(1<<i)));
}
}
}
void solve()
{
cin>>n;
string s;
cin>>s;
s='x'+s;
for(int i=1;i<=n;i++)
{
int t=s[i]-'a';
if(!la[t]) cnt++;
la[t]=i;
memcpy(sum[i],sum[i-1],sizeof sum[i]);
memcpy(pre[i],pre[i-1],sizeof pre[i-1]);
sum[i][t]++;
pre[i][t]=i;
}
dp[0]=n+1;
for(int i=1;i<(1<<20);i++)
{
dp[i]=1e8;
for(int j=0;j<20;j++)
{
if(((i>>j)&1)&&la[j]) dp[i]=min(dp[i],la[j]);
}
if(dp[i]==1e8) dp[i]=n+1;
//cout<<dp[i]<<" "<<i<<endl;
}
dfs(1,1,0);
string tmp="";
for(int i=1;i<=cnt;i++)
{
char c='a'+cnt-i;
while(num[i]--) tmp+=c;
}
cout<<tmp<<endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
//cin>>T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 64ms
memory: 12576kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 63ms
memory: 12136kb
input:
4 acac
output:
bba
result:
ok single line: 'bba'
Test #3:
score: 0
Accepted
time: 65ms
memory: 12048kb
input:
1 t
output:
a
result:
ok single line: 'a'
Test #4:
score: 0
Accepted
time: 64ms
memory: 13324kb
input:
12 bcabcabcbcbb
output:
ccbbaa
result:
ok single line: 'ccbbaa'
Test #5:
score: 0
Accepted
time: 68ms
memory: 13576kb
input:
1000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
Test #6:
score: 0
Accepted
time: 71ms
memory: 14040kb
input:
1000 ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...
output:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
result:
ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'
Test #7:
score: 0
Accepted
time: 64ms
memory: 12560kb
input:
1000 edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'
Test #8:
score: 0
Accepted
time: 66ms
memory: 13356kb
input:
1000 hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...
output:
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddccbbbaaa
result:
ok single line: 'dddddddddddddddddddddddddddddd...dddddddddddddddddddddddccbbbaaa'
Test #9:
score: 0
Accepted
time: 70ms
memory: 12436kb
input:
1000 cceooojojcecesjojsssesjojccoecceoojecsscojsosoccojscjcjssococjscssosecooeejoosojeecjceoeeojcocosjcecocoesjceejjecssjejccjsjosjsjcjesjojcojocjjeooeccojjosjcjjcjoecseecsjccojcoessecejcocosecsojeoceejeccejeoosssscecjcssooojoseeccosocoeejjecsjeoecejsoojessoescecjjsscecoccjsjsscccssjoeejsscoesecssco...
output:
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeddccbaaa
result:
ok single line: 'eeeeeeeeeeeeeeeeeeeeeeeeeeeeee...eeeeeeeeeeeeeeeeeeeeeeeddccbaaa'
Test #10:
score: 0
Accepted
time: 67ms
memory: 14384kb
input:
1000 mmmfqfmpqrccmqfcrprpfppcpcffqcrcrcqmmmqmrfmrpqffppcmqpqqrfqqcffpmqqfmcmpmcfcqcffqmrmqrmmqmffpqqpfqrcppmmpmrqffmfcfffqmrprfcpfqffrrrmcqmpfmpfmprmcrrqqrmcrcmpcffmpfcprmcpmcfmpcfprrqrpcqccpcmmqcqqfmrcrrqrqcmcpqcrcqcrrpmpmfccqcffrrfmpfqqmqcpmfpmqpcmqpmfqpffmqpcrmcmqrqfqqcrfffcfqprcprrmfppfpqqmmrcmc...
output:
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeeeeddcbaa
result:
ok single line: 'ffffffffffffffffffffffffffffff...fffffffffffffffffffffeeeeddcbaa'
Test #11:
score: 0
Accepted
time: 68ms
memory: 13976kb
input:
1000 hljikoiljhkhhikjihlhokhjnjlijjhkhinohnioklilhonihliiiohllkniiokjiihkokkkhnijkkkijnnjljoihiljlnjhllnjlhojnjojnnjhllilnnoloiijioiohkononkijhniihjiinononokjjokljjkinonhkojknohijhlilhjjlhkhjoonojlknjnljniklohinhinnnkhnkljjknkjhhlhlkllihhihnlkjklhokkihlhlikjhkjokhkniooljkojjiiljjjnojkiojnkniljnkoljn...
output:
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggfeedccccbaa
result:
ok single line: 'gggggggggggggggggggggggggggggg...ggggggggggggggggggggfeedccccbaa'
Test #12:
score: 0
Accepted
time: 66ms
memory: 12856kb
input:
1000 cbpfmafbflfblamcccmcbbfqqfpbaaqfpccqqbqfcabmlbbmfqcpfqmcpqcfffacqbpbllappmbmcfpqqfqlcbcaclbbfqmqfqlammbcqblbccqcpabapcbbfcmpfcmmcpccbcbcfblfclmflpfaqppqbfppfpacmfqqafcmlmbqcbbfqaqffpafcbcqfpqmpcabfmcqcqpblfccmffplcbbaamcallbblmbcmammaablfmbfqqlcqacpqfaqpfcbamamcqcmqqffqfcbcffmabcfplabbmfqcampqc...
output:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhgggfedcba
result:
ok single line: 'hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...hhhhhhhhhhhhhhhhhhhhhhgggfedcba'
Test #13:
score: 0
Accepted
time: 66ms
memory: 13336kb
input:
1000 oikrbsjdjjsrcdbroobidjojkdjikbirccicdiicbskkciijkssjirjokcjosbbkcdkbrdroirsooiibsjokircbkjbrbkoobkrddcbossoskosbiksodsjkkocoricjkdscdickjdisiddbsdiikdisdcjdkddscdjjrkkddjbbbdidkidddijbibdisbicjokodrcbjkkcrokiciijssjjbscrssccckdjdirbbcocjkobrijssijjcjrcskdobrjcscbocoobdocobrorosiidoscrijjorsrirk...
output:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiihgfeedcba
result:
ok single line: 'iiiiiiiiiiiiiiiiiiiiiiiiiiiiii...iiiiiiiiiiiiiiiiiiiiiihgfeedcba'
Test #14:
score: -100
Wrong Answer
time: 64ms
memory: 12660kb
input:
1000 cmctnhnrhchdnnaitttiirathamrkhtahnmrttkrhdimhatrttatrtmkiminahadihkdkrdthrkrhiandtmhtrdtiinicrmmirinnarkanadnhaatkkakarirnahrtcndarniihkdnddkhitkmdrtarhinirccaitdccnncnmnanhmtrdthkrmakdkktnimictdanrcmrhtcakmcmnahcrahkhtmadmhkrriinakkrhhddmnaknacchtacaktdnmaihnhcmtcchrdmihritatkactmmhattcrkknnkr...
output:
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjiiihhhhgggfeeedccba
result:
wrong answer 1st lines differ - expected: 'jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...jjjjjjjjjjjiiihhhhgggfeeedccbaa', found: 'jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...jjjjjjjjjjjjiiihhhhgggfeeedccba'