QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#77984 | #5166. 回文匹配 | Forza_Ferrari | 0 | 30ms | 3452kb | C++14 | 1.1kb | 2023-02-16 11:39:21 | 2023-02-16 11:39:22 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+9,base=1145141;
int 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]='|';
char c;
cin>>c;
while(c<'a'||c>'z')
cin>>c;
while(c>='a'&&c<='z')
{
s[++len]=c;
s[++len]='|';
cin>>c;
}
}
inline int Mod(int x)
{
return x>=mod? x-mod:x;
}
int main()
{
init();
cin>>n>>m;
for(int i=1;i<=n;++i)
{
read();
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]+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: 2ms
memory: 3392kb
input:
0 2 500000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1 1
result:
wrong answer Unexpected EOF in the participants output
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 15
Accepted
time: 30ms
memory: 3408kb
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:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 500000 tokens
Test #11:
score: -15
Wrong Answer
time: 18ms
memory: 3332kb
input:
0 250000 500000 di ne pk cw la bt cx hs ku ga rq zq jo zr at ue og sl su ju gy oo om ev df bm jh um vw ts qs we pn pe zc zb nl ld kl pl tk uh cm hn qb xi wb lu kq gf vc eq xe ni se ng kn rt zd bv vb vn ui dz kn do cg nn ct mz op od lu cb ra ib dk lh xh wh ny ws jw lh vk bl ak an rz xv sm zt mp yr an...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer 4th words differ - expected: '0', found: '1'
Subtask #3:
score: 0
Wrong Answer
Test #32:
score: 20
Accepted
time: 1ms
memory: 3452kb
input:
0 1 1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1
result:
ok "1"
Test #33:
score: -20
Wrong Answer
time: 1ms
memory: 3392kb
input:
0 2 1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1 1
result:
wrong answer Participant output contains extra tokens
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%