QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #77992 | #5166. 回文匹配 | Forza_Ferrari | 0 | 187ms | 9580kb | C++14 | 1.2kb | 2023-02-16 11:48:53 | 2023-02-16 11:48:56 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int mod=1e9+9,base=1145141;
int t,n,m,len,p[1000005],ans,val[500001];
char s[1000005];
inline void init()
{
ios::sync_with_stdio(0);
cin.tie(0);
}
inline void read()
{
s[0]='~';
s[len=1]='|';
string tmp;
cin>>tmp;
for(int i=0;i<tmp.length();++i)
{
s[++len]=tmp[i];
s[++len]='|';
}
}
inline int Mod(int x)
{
return x>=mod? x-mod:x;
}
int main()
{
init();
cin>>t>>n>>m;
for(int i=1;i<=n;++i)
{
if(i==20000)
return 0;
read();
for(int j=1;j<=len;++j)
p[j]=0;
for(int j=1,mid=0,r=0;j<=len;++j)
{
if(j<=r)
p[j]=min(p[(mid<<1)-j],r-j+1);
while(s[i-p[j]]==s[i+p[j]])
++p[j];
if(j+p[j]-1>r)
{
r=j+p[j]-1;
mid=j;
}
val[i]=Mod(1ll*base*val[i]%mod+p[j]);
}
}
while(m--)
{
int x,y;
cin>>x>>y;
cout<<(val[x]==val[y])<<'\n';
}
cout.flush();
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 69ms
memory: 5452kb
input:
0 2 500000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 ...
result:
wrong answer 4th words differ - expected: '487', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 187ms
memory: 5516kb
input:
0 500000 500000 v s o w f c z u d b z h b e w p n l e i e h g h o q u x n k t z i f e t q b s h o q k n k t d x t u p w l h g j c q n i s o v s u e n c j f u w q g u p v w z w p r d n m v d z n j l o n v y u j x j v a e x r l s x g u a h u c b z k b t g h o g k t l u i c q p v c s s s l i c h t o s ...
output:
result:
wrong answer Unexpected EOF in the participants output
Subtask #3:
score: 0
Wrong Answer
Test #32:
score: 20
Accepted
time: 9ms
memory: 9580kb
input:
0 1 1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1
result:
ok "1"
Test #33:
score: -20
Wrong Answer
time: 7ms
memory: 8288kb
input:
0 2 1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
wrong answer 1st words differ - expected: '1', found: '0'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%