QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152656 | #6618. Encoded Strings II | LFCode | WA | 1ms | 7628kb | C++14 | 1.6kb | 2023-08-28 16:13:58 | 2023-08-28 16:13:58 |
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)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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7628kb
input:
4 aacc
output:
GG bbaa
result:
wrong answer 1st lines differ - expected: 'bbaa', found: 'GG'