QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504943 | #9111. Zayin and String | PhantomThreshold# | WA | 95ms | 46444kb | C++20 | 2.7kb | 2024-08-04 17:36:51 | 2024-08-04 17:36:51 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1010;
const int maxp = 4010;
const int mod = 998244353;
const double eps = 1e-9;
int pw(int x,int k)
{
int re=1;
for(;k;k>>=1,x=(ll)x*x%mod) if(k&1)
re=(ll)re*x%mod;
return re;
}
int inv(int x){ return pw(x,mod-2); }
struct Trie
{
int rt,tot;
int son[maxp][26],sum[maxp],fail[maxp];
int newnode()
{
++tot;
memset(son[tot],0,sizeof son[tot]);
sum[tot]=fail[tot]=0;
return tot;
}
void init()
{
rt=tot=0;
rt=newnode();
}
void insert(string ss,const int val)
{
int x=rt;
for(auto c:ss)
{
int w=c-'a';
if(!son[x][w]) son[x][w]=newnode();
x=son[x][w];
}
sum[x]+=val;
}
void build()
{
queue<int>q;
q.push(rt); fail[rt]=0;
while(!q.empty())
{
const int x=q.front(); q.pop();
int fl=fail[x];
sum[x]+=sum[fl];
for(int w=0;w<26;w++)
{
int &y=son[x][w];
if(y)
{
if(x!=rt) fail[y]=son[fl][w];
else fail[y]=x;
q.push(y);
}
else
{
if(x!=rt) y=son[fl][w];
else y=rt;
}
}
}
}
}tr;
int n,m;
string S;
int tf[maxn][maxp],tn;
double f[maxn][maxp];
int pf[maxn][maxp];
inline void upd(const int i,const int j,const double F,const int pj)
{
if(tf[i][j]!=tn)
{
tf[i][j]=tn, f[i][j]=F;
pf[i][j]=pj;
}
else if(f[i][j]<F) f[i][j]=F, pf[i][j]=pj;
}
int check(const double mid)
{
f[0][tr.rt]=0;
tf[0][tr.rt]=tn;
for(int i=0;i<=n;i++)
{
for(int j=1;j<=tr.tot;j++) if(tf[i][j]==tn)
{
if(i && f[i][j]>eps) return 1;
if(i<n)
{
upd(i+1,j,f[i][j],-j);
int w=S[i+1]-'a';
int nj= tr.son[j][w];
upd(i+1,nj,f[i][j]-mid+tr.sum[nj],j);
}
}
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int Tcase; cin>>Tcase;
while(Tcase--)
{
cin>>n>>m;
cin>>S; S=' '+S;
tr.init();
double l=0,r=0;
for(int i=1;i<=m;i++)
{
string ss; cin>>ss;
int c; cin>>c;
tr.insert(ss,c);
r+=c;
}
tr.build();
tn=0;
for(int ti=1;ti<=50;ti++)
{
double mid=(l+r)/2;
++tn;
if(check(mid)) l=mid;
else r=mid;
}
++tn; check(l);
int edi=0,edj;
for(int i=1;i<=n && edi==0;i++) for(int j=1;j<=tr.tot;j++) if(tf[i][j]==tn)
{
if(f[i][j]>eps)
{
edi=i,edj=j;
break;
}
}
ll ansp=0,ansq=0;
while(edi)
{
ansp+=(pf[edi][edj]>0)*tr.sum[edj];
ansq+=(pf[edi][edj]>0);
edj=abs( pf[edi][edj] );
edi--;
}
// cerr<<fixed<<setprecision(12)<<l<<' '<<r<<'\n';
// cerr<<ansp<<'/'<<ansq<<'\n';
cout<<ansp%mod*inv(ansq)%mod<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 95ms
memory: 46444kb
input:
80 4 7 ggeg g 92946 d 65678 gg 50828 wrj 93954 gge 53780 a 94179 geg 40837 5 6 hiiii ii 67984 foh 69185 hi 88153 pj 39431 i 32219 wfmve 96834 8 12 wvxxvwww xw 1522 rzl 16262 wx 77596 v 69622 vw 82225 nykkmkv 19236 xv 83470 o 16781 w 2405 m 98319 ww 13889 qggbvty 16331 8 14 jjjiiijh i 96670 z 74397 i...
output:
332874949 83207 76546 48335 16709 499162503 61572 67112 64022 499218573 0 69374 74929 52557 499139737 748710601 32566 0 23951 36250 0 52838 14442 0 0 89874 110460 14995 0 0 97813 144466 48174 0 96540 0 499164910 22778 70934 0 94481 499144203 0 0 40809 0 0 0 36781 499203655 20687 499143274 98206 4991...
result:
wrong answer 2nd lines differ - expected: '599030808', found: '83207'