QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77984#5166. 回文匹配Forza_Ferrari0 30ms3452kbC++141.1kb2023-02-16 11:39:212023-02-16 11:39:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-16 11:39:22]
  • 评测
  • 测评结果:0
  • 用时:30ms
  • 内存:3452kb
  • [2023-02-16 11:39:21]
  • 提交

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%