QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771600 | #6618. Encoded Strings II | ucup-team3161# | WA | 2ms | 7956kb | C++17 | 1.5kb | 2024-11-22 14:30:16 | 2024-11-22 14:30:17 |
Judging History
answer
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define Dow(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N = 1010, M = 1<<20|10;
int n,las[N][26],pre[N][26],all,r[M];
char s[N];
struct node{
int cnt,a[21],las;
}f[M];
inline int get(int c,int l,int r){
return pre[r][c]-pre[l-1][c];
}
inline bool cmp(node *x,node *y){
For(i,1,x->cnt){
if (x->a[i] > y->a[i]) return 1;
if (x->a[i] < y->a[i]) return 0;
}
return x->las < y->las;
}
int main(){
scanf("%d%s",&n,s+1);
For(i,1,n){
For(j,0,19) las[i][j]=las[i-1][j];
las[i][s[i]-'a']=i;
all|=(1<<(s[i]-'a'));
}
For(i,1,n){
For(j,0,19) pre[i][j]=pre[i-1][j];
pre[i][s[i]-'a']++;
}
FOR(i,0,1<<20) if ((i&all)==i){
r[i]=n+1;
For(j,0,19) if (i>>j&1) r[i]=min(r[i],las[n][j]);
}
Dow(i,(1<<20)-1,1) if ((i&all)==i){
if (i!=all&&!f[i].cnt) continue;
node tmp=f[i];
++tmp.cnt;
For(j,0,19) if (i>>j&1){
int k=i^(1<<j);
tmp.a[tmp.cnt]=get(j,tmp.las+1,r[k]-1);
tmp.las=las[r[k]-1][j];
if (tmp.a[tmp.cnt]<=0) continue;
if (!f[k].cnt) f[k]=tmp;
else if (cmp(&tmp,&f[k])) f[k]=tmp;
}
}
For(i,1,f[0].cnt){
For(j,1,f[0].a[i]) printf("%c",f[0].cnt-i+'a');
}
}
/*
6
aabbcc
4
abab
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5808kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5896kb
input:
4 acac
output:
bba
result:
ok single line: 'bba'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7956kb
input:
1 t
output:
a
result:
ok single line: 'a'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 5884kb
input:
12 bcabcabcbcbb
output:
ccbba
result:
wrong answer 1st lines differ - expected: 'ccbbaa', found: 'ccbba'