QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#834362 | #8701. Border | xyin | 23 | 0ms | 3928kb | C++17 | 1.8kb | 2024-12-27 16:03:59 | 2024-12-27 16:04:00 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pp pop_back
#define ls p<<1
#define rs p<<1|1
#define pb push_back
#define mk make_pair
#define pai pair<int,int>
using namespace std;
const int N=55;
const int maxn=4e3+5;
// const int INF=1e18;
const int base=100411;
const int mod=1e9+0411;
typedef unsigned long long ull;
int read(int x=0,bool f=1,char c=0){
while (!isdigit(c=getchar())) f=c^45;
while (isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?x:-x;
}
int n,ans[maxn],o,tag[maxn];
char s[maxn],t[maxn];
int P[maxn],ha[maxn],las;
int get(int l,int r){
return (ha[r]-ha[l-1]*P[r-l+1]%mod+mod)%mod;
}
int bin_search(int l,int r,int t){
while (l<r){
int mid=(l+r)>>1;
if (get(1,mid)!=get(t,t+mid-1)) r=mid;
else l=mid+1;
}
return l;
}
bool check(int len,int o){
int t1=get(1,len),t2=get(n-len+1,n);
if (o>=1&&o<=len) t1=(t1-s[o]*P[len-o]%mod+t[o]*P[len-o]%mod+mod)%mod;
if (o>=n-len+1&&o<=n) t2=(t2-s[o]*P[n-o]%mod+t[o]*P[n-o]%mod+mod)%mod;
return t1==t2;
}
signed main(){
scanf("%s%s",s+1,t+1);
n=strlen(s+1);P[0]=1,ha[0]=1;
for (int i=1;i<=n;i++)
P[i]=P[i-1]*base%mod,
ha[i]=(ha[i-1]*base+s[i])%mod;
for (int len=1;len<=n;len++){
if (get(1,len)==get(n-len+1,n))
{tag[len]=1;o=len;continue;}
int t=bin_search(1,len,n-len+1);
if (check(len,t)) ans[t]=max(ans[t],len);
if (check(len,n-len+t))
ans[n-len+t]=max(ans[n-len+t],len);
}
for (int i=1;i<=(n+1)/2;i++){
if (s[i]==t[i]) ans[i]=o;
ans[i]=max(ans[i],las);
ans[n-i+1]=max(ans[n-i+1],las);
if (tag[i]) las=i;
}
for (int i=1;i<=n;i++)
printf("%lld\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 0ms
memory: 3928kb
input:
cbaababaabacbaababaabacbaabacbaababaabacbaaba dabbababbabaabbafabbgbaabfebaabzababbayaabcac
output:
0 0 0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 17 17 17 17 17 17 17 17 17 17 17 6 6 6 6 6 6 6 6 6 6 6 0 0 0 3 0 1
result:
ok 45 numbers
Test #2:
score: 23
Accepted
time: 0ms
memory: 3840kb
input:
cbaababaabacbaabadbaababaabacbaabacbaaba aabwaxjbbabtalbabcasbabibbabaabbabaabiac
output:
3 0 0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 23 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 0 0 0 0 1
result:
ok 40 numbers
Test #3:
score: 23
Accepted
time: 0ms
memory: 3912kb
input:
cadaabacabacabacabaabacabacadaabacabacaba bbbbbabtbabababalalbawababababbaoababebdc
output:
2 0 4 0 0 0 0 0 0 0 0 0 0 0 0 15 15 15 15 15 15 15 15 15 15 15 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1
result:
ok 41 numbers
Test #4:
score: 23
Accepted
time: 0ms
memory: 3924kb
input:
dabacbaadcbaadabacbaadabecbaadcbaadabacbaadabacbaa ababaabbyaarbabfbvdbuaoaaaabbaaabbababaabbababqadd
output:
2 0 0 0 0 0 0 0 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 29 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 0 0 0 0 0 2 1
result:
ok 50 numbers
Test #5:
score: 23
Accepted
time: 0ms
memory: 3864kb
input:
edacbcacacbcaecbcacacbcadacbcacacbca sabaaabtbaaabaaalblbawaeabaaababoaae
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 1
result:
ok 36 numbers
Test #6:
score: 23
Accepted
time: 0ms
memory: 3808kb
input:
cbaababaabacbaabacbaabdbaabacbaabacbaaba aabbababbaoaabbxbaabbaqabbabltbpagaabcac
output:
3 0 0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 0 0 3 0 1
result:
ok 40 numbers
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 3864kb
input:
abacadcabbacabbacabcabbacabacabbacabbacabcabbacabbacadcabbacabbacabcabbacabacabbacabbacabcabbacabbacadcabbacabbacabcabbacababacadcabbacabbacabcabbacabacabbacabbacabcabbacabbacadcabbacabbacaecabbacabacabbacabbacabcabbacabbacadcabbacabbacabcabbacababacadcabbacabbacabcabbacabacabbacabbacabcabbacabbacad...
output:
0 1 2 591 591 591 591 591 591 9 10 591 591 591 14 15 591 591 591 591 591 591 22 23 24 25 26 27 591 591 591 31 32 591 591 591 36 37 591 591 591 591 591 591 44 45 591 591 591 49 50 591 591 591 591 591 591 57 58 591 591 591 62 63 591 591 591 591 591 591 70 71 72 73 73 73 591 591 591 73 73 591 73 591 73...
result:
wrong answer 1st numbers differ - expected: '27', found: '0'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%