QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152690 | #6618. Encoded Strings II | do_while_true | WA | 2ms | 9404kb | C++14 | 3.1kb | 2023-08-28 17:20:38 | 2023-08-28 17:20:39 |
Judging History
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'