QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #253638 | #801. 回文自动机 | Mobius_127 | Compile Error | / | / | C++14 | 5.4kb | 2023-11-17 10:53:00 | 2023-11-17 10:53:01 |
Judging History
This is the latest submission verdict.
- [2023-11-17 10:53:01]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2023-11-17 10:53:00]
- Submitted
answer
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#define mem(arr, x) memset(arr, x, sizeof(arr))
#define mcy(arr, b) memcpy(arr, b, sizeof(arr))
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){return x+(x<0?cp:0)-(x>=cp?cp:0);}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
int ret=1;
for(; b; b>>=1, a=1ll*a*a%cp)
if(b&1) ret=1ll*ret*a%cp;
return ret;
}
const int N=1e6+6;
namespace SAM{
const int M=N<<1;
int ch[M][26], fa[M], len[M], occ[M], lst, ndc;
inline int clr(int x){fa[x]=len[x]=occ[x]=0, mem(ch[x], 0);return x;}
inline void rmk(){clr(ndc=lst=1);}
inline int insert(char cc){
int p=lst, cur=clr(++ndc), c=cc-'a';len[cur]=len[p]+1;
for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=cur;int q=ch[p][c];
if(!q) fa[cur]=1;else if(len[q]==len[p]+1) fa[cur]=q;
else{
int nex=clr(++ndc);mcy(ch[nex], ch[q]);len[nex]=len[p]+1;fa[nex]=fa[q];
for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nex;fa[q]=fa[cur]=nex;
}return lst=cur;
}
int pos[N], f[M][25];vi G[M];
void dfs(int x){
for(int i=1; i<25; ++i) f[x][i]=f[f[x][i-1]][i-1];
for(auto v:G[x]) f[v][0]=x, dfs(v), occ[x]+=occ[v];
}
inline void ins(char *str, int m){
rmk();for(int i=1; i<=m; ++i) pos[i]=insert(str[i]), ++occ[pos[i]];
for(int i=2; i<=ndc; ++i) G[fa[i]].pb(i);dfs(1);
}
inline int find(int l, int r){
int u=pos[r];for(int i=24; i>=0; --i)
if(len[f[u][i]]>=r-l+1) u=f[u][i];
return u;
}
inline int OCC(int l, int r){return occ[find(l, r)];}
}
int n, p[N];char s[N], t[N<<1];ll ans;
inline void chk(int mid, int len){
int l=mid-len+1>>1, r=mid+len>>1;//printf("find [%d %d]*%d\n", l, r, SAM :: OCC(l, r));
ans=max(ans, 1LL*SAM :: OCC(l, r)*(r-l+1)*(r-l+1));
}
signed main(){
scanf("%s", s+1);n=strlen(s+1);SAM :: ins(s, n);
t[0]='~', t[1]='#';for(int i=1; i<=n; ++i) t[i<<1]=s[i], t[i<<1|1]='#';
for(int i=1, mid=0, R=0; i<=n+n; ++i){
if(i<R) p[i]=min(R, p[mid+mid-i]);
while(t[i-p[i]-1]==t[i+p[i]+1]) ++p[i], chk(i, p[i]);
if(R<i+p[i]) mid=i, R=i+p[i];
}
printf("%lld\n", ans);
return 0;
}
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
int ret=1;
for(; b; b>>=1, a=1ll*a*a%cp)
if(b&1) ret=1ll*ret*a%cp;
return ret;
}
const int N=4e6+6;
const int Nc=N+N;
const int Mc=N+N+N;
namespace SAM{
int ndc, lst, siz[Nc];
struct node{int fa, nxt[26], len;}sam[Nc];
int clr(int x){sam[x]=sam[0], siz[x]=0;return x;}
void init(){clr(ndc=lst=1);}
int insert(char c){
int cur=clr(++ndc), p=lst, cc=c-'a';sam[cur].len=sam[p].len+1;
for(; p&&!sam[p].nxt[cc]; p=sam[p].fa) sam[p].nxt[cc]=cur;
int q=sam[p].nxt[cc];
if(!q) sam[cur].fa=1;
else if(sam[q].len==sam[p].len+1) sam[cur].fa=q;
else{
int nex=clr(++ndc);sam[nex]=sam[q];sam[nex].len=sam[p].len+1;
for(; p&&sam[p].len==q; p=sam[p].fa) sam[p].nxt[cc]=nex;
sam[cur].fa=sam[q].fa=nex;
}
return lst=cur;
}
int pos[N];
void insert_str(int n, char *s){init();for(int i=1; i<=n; ++i) pos[i]=insert(s[i]), siz[pos[i]]=1;}
vi G[Nc];int fa[Nc][25];
void dfs(int x){
for(int i=1; i<25; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto v:G[x]) fa[v][0]=x, dfs(v), siz[x]+=siz[v];
}
void pre(){for(int i=2; i<=ndc; ++i) G[sam[i].fa].pb(i);dfs(1);}
int Ocnum(int l, int r){
int x=pos[r];
for(int i=24; i>=0; --i) if(sam[fa[x][i]].len>=r-l+1) x=fa[x][i];
return siz[x];
}
}
int n, p[Nc];char s[N], t[Nc];ll ans;
ll calc(int x, int y){
if(t[x]=='#'&&t[y]=='#') x=x+1>>1, y=y-1>>1;
else x>>=1, y>>=1;
return 1ll*(y-x+1)*(y-x+1)*SAM :: Ocnum(x, y);
}
signed main(){
scanf("%s", s+1);n=strlen(s+1);SAM :: insert_str(n, s);SAM :: pre();
t[0]='~';t[1]='#';
for(int i=1; i<=n; ++i) t[i+i]=s[i], t[i+i+1]='#';
// printf("%s\n", t+1);
for(int i=1, R=0, mid=0; i<=n+n+1; ++i){
if(i<R) p[i]=min(R-i, p[mid*2-i]);
while(t[i-p[i]-1]==t[i+p[i]+1]) ++p[i], ans=max(ans, calc(i-p[i], i+p[i]));
if(i+p[i]>R) R=i+p[i], mid=i;
}
printf("%lld\n", ans);
return 0;
}
Details
answer.code:102:11: error: redefinition of ‘const int INF’
102 | const int INF=0x3f3f3f3f;
| ^~~
answer.code:18:11: note: ‘const int INF’ previously defined here
18 | const int INF=0x3f3f3f3f;
| ^~~
answer.code:103:11: error: redefinition of ‘const int cp’
103 | const int cp=998244353;
| ^~
answer.code:19:11: note: ‘const int cp’ previously defined here
19 | const int cp=998244353;
| ^~
answer.code:104:12: error: redefinition of ‘int mod(int)’
104 | inline int mod(int x){if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
| ^~~
answer.code:20:12: note: ‘int mod(int)’ previously defined here
20 | inline int mod(int x){return x+(x<0?cp:0)-(x>=cp?cp:0);}
| ^~~
answer.code:105:13: error: redefinition of ‘void plust(int&, int)’
105 | inline void plust(int &x, int y){x=mod(x+y);return ;}
| ^~~~~
answer.code:21:13: note: ‘void plust(int&, int)’ previously defined here
21 | inline void plust(int &x, int y){x=mod(x+y);return ;}
| ^~~~~
answer.code:106:13: error: redefinition of ‘void minut(int&, int)’
106 | inline void minut(int &x, int y){x=mod(x-y);return ;}
| ^~~~~
answer.code:22:13: note: ‘void minut(int&, int)’ previously defined here
22 | inline void minut(int &x, int y){x=mod(x-y);return ;}
| ^~~~~
answer.code:107:12: error: redefinition of ‘int read()’
107 | inline int read(){
| ^~~~
answer.code:23:12: note: ‘int read()’ previously defined here
23 | inline int read(){
| ^~~~
answer.code:113:13: error: redefinition of ‘void write(int)’
113 | inline void write(int x){
| ^~~~~
answer.code:29:13: note: ‘void write(int)’ previously defined here
29 | inline void write(int x){
| ^~~~~
answer.code:118:12: error: redefinition of ‘int ksm(int, int)’
118 | inline int ksm(int a, int b=cp-2){
| ^~~
answer.code:34:12: note: ‘int ksm(int, int)’ previously defined here
34 | inline int ksm(int a, int b=cp-2){
| ^~~
answer.code:124:11: error: redefinition of ‘const int N’
124 | const int N=4e6+6;
| ^
answer.code:40:11: note: ‘const int N’ previously defined here
40 | const int N=1e6+6;
| ^
answer.code:128:13: error: redefinition of ‘int SAM::ndc’
128 | int ndc, lst, siz[Nc];
| ^~~
answer.code:43:52: note: ‘int SAM::ndc’ previously declared here
43 | int ch[M][26], fa[M], len[M], occ[M], lst, ndc;
| ^~~
answer.code:128:18: error: redefinition of ‘int SAM::lst’
128 | int ndc, lst, siz[Nc];
| ^~~
answer.code:43:47: note: ‘int SAM::lst’ previously declared here
43 | int ch[M][26], fa[M], len[M], occ[M], lst, ndc;
| ^~~
answer.code:130:13: error: redefinition of ‘int SAM::clr(int)’
130 | int clr(int x){sam[x]=sam[0], siz[x]=0;return x;}
| ^~~
answer.code:44:20: note: ‘int SAM::clr(int)’ previously defined here
44 | inline int clr(int x){fa[x]=len[x]=occ[x]=0, mem(ch[x], 0);return x;}
| ^~~
answer.code:132:13: error: redefinition of ‘int SAM::insert(char)’
132 | int insert(char c){
| ^~~~~~
answer.code:46:20: note: ‘int SAM::insert(char)’ previously defined here
46 | inline int insert(char cc){
| ^~~~~~
answer.code:145:13: error: redefinition of ‘int SAM::pos [1000006]’
145 | int pos[N];
| ^~~
answer.code:55:13: note: ‘int SAM::pos [1000006]’ previously declared here
55 | int pos[N], f[M][25];vi G[M];
| ^~~
answer.code:147:12: error: redefinition of ‘std::vector<int> SAM::G [2000012]’
147 | vi G[Nc];int fa[Nc][25];
| ^
answer.code:55:33: note: ‘std::vector<int> SAM::G [2000012]’ previously declared here
55 | int pos[N], f[M][25];vi G[M];
| ^
answer.code:147:22: error: conflicting declaration ‘int SAM::fa [2000012][25]’
147 | vi G[Nc];int fa[Nc][25];
| ^~
answer.code:43:24: note: previous declaration as ‘int SAM::fa [2000012]’
43 | int ch[M][26], fa[M], len[M], occ[M], lst, ndc;
| ^~
answer.code:148:14: error: redefinition of ‘void SAM::dfs(int)’
148 | void dfs(int x){
| ^~~
answer.code:56:14: note: ‘void SAM::dfs(int)’ previously defined here
56 | void dfs(int x){
| ^~~
answer.code: In function ‘void SAM::dfs(int)’:
answer.code:149:46: error: invalid types ‘int[int]’ for array subscript
149 | for(int i=1; i<25; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];
| ^
ans...