Submission #1165810

#TimeUsernameProblemLanguageResultExecution timeMemory
1165810sitablechairNecklace (Subtask 4) (BOI19_necklace4)C++20
3 / 15
417 ms520 KiB
#include <bits/stdc++.h> #define ll long long #define ldb long double #define endl '\n' #define For(i,l,r) for(int i=l;i<=r;i++) #define ForD(i,r,l) for(int i=r;i>=l;i--) #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() #define sz(x) (signed)x.size() #define unq(x) x.resize(unique(all(x))-x.begin()) #define F "TASK" #define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout); #ifdef NCGM #include"debug.h" #else #define debug(...) "fr"; #endif using namespace std; const int N=3003; string s,s1,s2,s3; int pf[N*2],pf1[N*2]; pair<int,pair<int,int>> solve() { int ans=0,x1=-1,y1=-1; int n=sz(s)-1,m=sz(s1)-1; For(i,1,m-1) { s2=s3=" "; ForD(j,i,1) s2+=s1[j]; ForD(j,n,1) s2+=s[j]; For(j,i+1,m) s3+=s1[j]; For(j,1,n) s3+=s[j]; int p=sz(s2)-1,q=sz(s3)-1; fill(pf,pf+1+p,0); fill(pf1,pf1+1+q,0); For(j,2,p) { int k=pf[j-1]; while(true) { if (s2[k+1]==s2[j]) { pf[j]=k+1; break; } if (k==0) break; k=pf[k]; } } For(j,2,p) { int k=pf1[j-1]; while(true) { if (s3[k+1]==s3[j]) { pf1[j]=k+1; break; } if (k==0) break; k=pf1[k]; } } For(j,2,n) { int x=pf[n-j+i+1]; if (x>n-j+1) x=n-j+1; if (x>i) x=i; int y=pf1[m-i+j-1]; if (y>m-i) y=m-i; if (y>j-1) y=j-1; if (x+y>ans) { // if (x+y==3) debug(i,x,y); ans=x+y; y1=i-x+1; x1=j-y; } } } if (m==1) { For(j,1,n) if (s[j]==s1[1]) return {1,{j,1}}; } if (n==1) { For(j,1,m) if (s1[j]==s[1]) return {1,{1,j}}; } // debug(ans,x1,y1); return {ans,{x1,y1}}; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> s >> s1; s=" "+s; s1=" "+s1; auto xx=solve(); reverse(all(s)); s.pop_back(); s=" "+s; auto xxx=solve(); int tmp=sz(s)-1; xxx.ss.ff=tmp-xxx.ss.ff+1; if (xxx.ff>xx.ff) cout << xxx.ff << endl << xxx.ss.ff-xxx.ff << " " << xxx.ss.ss-1 << endl; else cout << xx.ff << endl << xx.ss.ff-1 << " " << xx.ss.ss-1 << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...