QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #458878 | #7901. Basic Substring Structure | WrongAnswer_90 | TL | 0ms | 33240kb | C++14 | 7.3kb | 2024-06-29 20:18:24 | 2024-06-29 20:18:24 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define mp make_pair
//#define LOCALJUDGE
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,INF=4557430888798830399;
static const double eps=1e-8,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
using namespace std;
//#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
struct tup{int x,y,z;tup(int X=0,int Y=0,int Z=0){x=X,y=Y,z=Z;}};
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[25];int top=0;
do{st[top++]=x%10+'0',x/=10;}while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' ')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
s=0;char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-')&&(ch=getchar());
while((ch>='0')&&(ch<='9'))s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=(tf?-s:s);
}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
int T,m,n,ans[200010],c1[200010],c2[200010],b[400010],s[400010],x[400010],y[400010],F[18][200010],rk[200010],sa[200010];
vector<pii> ve[200010];
inline int LCP(int x,int y)
{
if(x>n||y>n)return 0;
if(x==y)return n-x+1;
if((x=rk[x])>(y=rk[y]))swap(x,y);
int k=__lg(y-x++);
return min(F[k][x],F[k][y-(1<<k)+1]);
}
void modify(int x,int y,int st){if(x>y)return;c2[x+1]++,c2[y+1]--,c1[x]+=st,c1[y+1]-=st+y-x;}
bool cmp(pii a,pii b){return a.fi<b.fi;}
inline void mian()
{
read(T);
for(int _=1;_<=T;++_)
{
if(_==3000)return;
read(n),m=n,s[n+1]=0;
assert(n<=100);
for(int i=1;i<=n;++i)read(s[i]);
for(int i=1;i<=m;++i)b[i]=0;
for(int i=1;i<=n;++i)++b[x[i]=s[i]];
for(int i=2;i<=m;++i)b[i]+=b[i-1];
for(int i=1;i<=n;++i)sa[b[s[i]]--]=i;
for(int k=1,num=0;k<=n;k<<=1,num=0)
{
for(int i=n;i>n-k;--i)y[++num]=i;
for(int i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;++i)b[i]=0;
for(int i=1;i<=n;++i)++b[x[i]];
for(int i=2;i<=m;++i)b[i]+=b[i-1];
for(int i=n;i>=1;--i)sa[b[x[y[i]]]--]=y[i];
swap(x,y),x[sa[1]]=1;
for(int i=2;i<=n;++i)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=x[sa[i-1]];
else x[sa[i]]=x[sa[i-1]]+1;
}
if((m=x[sa[n]])==n)break;
}
for(int i=1;i<=n;++i)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;++i,k?--k:0)
{
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
F[0][rk[i]]=k;
}
for(int i=1;i<18;++i)
{
for(int j=1;j+(1<<i)-1<=n;++j)
F[i][j]=min(F[i-1][j],F[i-1][j+(1<<(i-1))]);
}
for(int i=0;i<=n;++i)ve[i].clear(),ans[i]=c1[i]=c2[i]=0;
c1[0]=n;
for(int i=2;i<=n;++i)
{
int x=LCP(1,i);
// cerr<<i<<" "<<x<<endl;
// memset(c1,0,sizeof(c1));
// memset(c2,0,sizeof(c2));
// memset(ans,0,sizeof(ans));
// for(int j=1;j<=n;++j)ve[j].clear();
if(x+1<i)
{
modify(1,x,0);
if(i+x<=n)ve[x+1].eb(mp(s[i+x],1+LCP(x+2,i+x+1)));
c1[x+1]+=x,c1[i]-=x;
modify(i,i+x-1,0);
int nw=x+1+LCP(x+2,i+x+1);
if(s[x+1]!=s[i+i+x-1])Mmin(nw,i+x-1);
else if(nw==i+x-1)nw+=1+LCP(i+x+1,i+i+x);
ve[i+x].eb(mp(s[x+1],nw));
c1[i+x+1]+=x;
}
else
{
modify(1,i-1,0);
modify(i,i+x-1,0);
int nw=x+1+LCP(x+2,i+x+1);
if(s[x+1]!=s[i+i+x-1])Mmin(nw,i+x-1);
else if(nw==i+x-1)nw+=1+LCP(i+x+1,i+i+x);
ve[i+x].eb(mp(s[x+1],max(0ll,nw-x)));
c1[i+x]+=x;
}
// for(int j=1;j<=n;++j)c2[j]+=c2[j-1];
// for(int k=1;k<=n;++k)
// {
// c1[k]+=c1[k-1]+c2[k],ans[k]=c1[k];
// sort(ve[k].begin(),ve[k].end());
//// for(int j=0,sum=0;j<(int)ve[k].size();++j)
//// {
//// sum+=ve[k][j].se;
//// if(j==(int)ve[k].size()-1||ve[k][j].fi!=ve[k][j+1].fi)
//// Mmax(ans[k],c1[k]+sum),sum=0;
//// }
// write(ans[k]);
// }
// puts("");
// for(int k=1;k<=n;++k)
// {
// for(auto p:ve[k])write('(',k,',',p.fi,',',p.se,')');
// }
// puts("");
}
// exit(0);
for(int i=1;i<=n;++i)c2[i]+=c2[i-1];
ll fin=0;
for(int i=1;i<=n;++i)
{
c1[i]+=c1[i-1]+c2[i],ans[i]=c1[i];
sort(ve[i].begin(),ve[i].end());
for(int j=0,sum=0;j<(int)ve[i].size();++j)
{
sum+=ve[i][j].se;
if(j==(int)ve[i].size()-1||ve[i][j].fi!=ve[i][j+1].fi)
Mmax(ans[i],c1[i]+sum),sum=0;
}
fin+=ans[i]^i;
}
write(fin,'\n');
}
}
}
bool ED;
signed main()
{
#ifdef LOCALJUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
double st=clock();
WrongAnswer_90::mian();
double ed=clock();
#ifndef LOCALJUDGE
cerr<<endl;
#endif
cerr<<"Time: "<<ed-st<<" ms\n";
#ifdef LOCALJUDGE
cerr<<" ";
#endif
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 33240kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
15 217
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
10000 8 2 1 2 1 1 1 2 2 9 2 2 1 2 1 2 1 2 1 15 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 2 1 1 10 2 1 1 1 2 2 1 1 2 2 3 2 1 2 11 1 2 2 1 1 2 1 2 2 1 1 14 2 1 1 1 1 2 1 1 1 2 2 1 2 1 12 2 2 2 1 2 2 2 1 1 2 1 2 4 2 1 1 2 8 1 2 2 2 1 2 1 1 8 1 1 2 1 2 1 1 1 6 2 1 1 1 2 2 14 2 2 1 1 1 1 2 2 2 1 2 2 1 1 10 1 2 2 1 1...
output:
94 128 347 3 211 9 265 363 278 15 95 114 58 348 225 3 335 364 377 316 3 19 122 66 15 83 36 258 11 63 28 90 85 103 252 191 21 48 303 63 102 20 24 68 316 362 266 309 355 281 326 281 231 312 3 330 54 328 3 69 32 147 322 39 338 90 242 3 165 346 245 20 155 3 404 393 392 81 269 360 20 54 21 279 3 17 351 3...