QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152690#6618. Encoded Strings IIdo_while_trueWA 2ms9404kbC++143.1kb2023-08-28 17:20:382023-08-28 17:20:39

Judging History

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

  • [2023-08-28 17:20:39]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9404kb
  • [2023-08-28 17:20:38]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int mod=998244353;
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
int qpow(int x,int y){
	int s=1;
	while(y){
		if(y&1)s=1ll*s*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return s;
}
inline int bit(int x){return 1<<x;}
const int N=1010;
int n;
char s[N],t[N];
int a[N];
int f[(1<<20)],mn[(1<<20)];
vi vec[21];
int mx[21],sum[N][21],ans[21];
signed main(){
	#ifdef do_while_true
//		assert(freopen("data.in","r",stdin));
//		assert(freopen("data.out","w",stdout));
	#endif
	read(n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)t[i]=s[i];
	sort(t+1,t+n+1);
	int m=unique(t+1,t+n+1)-t-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(t+1,t+m+1,s[i])-t;
	for(int i=n;i>=1;i--)if(!mn[a[i]])mn[bit(a[i]-1)]=i;mn[0]=n+1;
	for(int i=n;i>=0;i--){
		memcpy(sum[i],sum[i+1],sizeof(int)*21);
		sum[i][a[i]]++;
	}
	for(int S=1;S<(1<<m);S++)if(S-(S&(-S))){
		int T=S&(-S);
		mn[S]=max(mn[T],mn[S^T]);
	}
	for(int S=0;S<(1<<m);S++)vec[__builtin_popcount(S)].pb(S);
	memset(f,-1,sizeof(f));
	f[0]=0;
	for(int o=0;o<m;o++){
		int s=0;
		for(auto S:vec[o])if(f[S]!=-1){
			for(int i=1;i<=m;i++)
				if(!(bit(i-1)&S)){
					int T=(bit(m)-1)^S^bit(i-1);
					int t=mn[T];
					if(t>f[S]){
						cmax(s,sum[f[S]][i]-sum[t][i]);
					}
				}
		}
		ans[o]=s;
		for(auto S:vec[o])if(f[S]!=-1){
			for(int i=1;i<=m;i++)
				if(!(bit(i-1)&S)){
					int T=(bit(m)-1)^S^bit(i-1);
					int t=mn[T];
					if(t>f[S]){
						if(sum[f[S]][i]-sum[t][i]==s){
							if(f[S^bit(i-1)]==-1)f[S^bit(i-1)]=t-1;
							else cmin(f[S^bit(i-1)],t-1);
						}
					}
				}
		}
	}
	for(int i=0;i<m;i++){
		for(int j=1;j<=ans[i];j++)
			putchar('a'+m-1-i);
	}
    #ifdef do_while_true
//		cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
	#endif
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9404kb

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

score: 0
Accepted
time: 2ms
memory: 8156kb

input:

4
acac

output:

bba

result:

ok single line: 'bba'

Test #3:

score: 0
Accepted
time: 1ms
memory: 8788kb

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 7840kb

input:

12
bcabcabcbcbb

output:

ccccaa

result:

wrong answer 1st lines differ - expected: 'ccbbaa', found: 'ccccaa'