QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152656#6618. Encoded Strings IILFCodeWA 1ms7628kbC++141.6kb2023-08-28 16:13:582023-08-28 16:13:58

Judging History

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

  • [2023-08-28 16:13:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7628kb
  • [2023-08-28 16:13:58]
  • 提交

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'