| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 546333 | s_jaskaran_s | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 327 ms | 548 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define endl '\n'
void zedd(string &s,string &t,int z[]){
t+='#';
z[0]=0;
int x=0,y=0;
for(int i=1;i<t.size();i++){
z[i]=max(0,min(z[i-x],y-i+1));
while(i+z[i]<t.size()&&t[z[i]]==t[z[i]+i]){
z[i]++;
x=i;
y=i+z[i]-1;
}
}
for(int i=0;i<s.size();i++){
z[i+t.size()]=max(0,min(z[i+t.size()-x],y-(i+(int)t.size())+1));
while(i+z[i+t.size()]<s.size()&&t[z[i+t.size()]]==s[z[i+t.size()]+i]){
z[i+t.size()]++;
x=i+t.size();
y=i+t.size()+z[i+t.size()]-1;
}
}
for(int i=0;i<s.size();i++){
z[i]=z[i+t.size()];
}
t.pop_back();
}
void kmp(string &s,string &t,int x[]){
if(t.size()==0){
for(int i=0;i<s.size();i++){
x[i]=0;
}
return;
}
int j=0;
s=t+'#'+s;
x[0]=0;
for(int i=1;i<s.size();i++){
while(j>0&&s[i]!=s[j]){
j=x[j-1];
}
if(s[i]==s[j]){
j++;
}
x[i]=j;
}
j=0;
for(int i=0;i<s.size()-t.size()-1;i++){
x[i]=x[i+t.size()+1];
}
s=s.substr(t.size()+1,s.size()-t.size()-1);
}
int solve_noflip(string &s, string &t, int *loc) {
int n = s.size(); // vertical
int m = t.size(); // horizontal
int res = 0;
vector< short > forw_back_len(m + 1);
vector< short > cur_v_len(n + m + 1); // offset -n
vector< short > cur_v_y(n + m + 1);
for (int i = 0; i <= n; ++i) cur_v_y[n - i] = i;
vector< short > cur_h_len(m + 1);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) forw_back_len[j] = max(0, forw_back_len[j] - 1);
for (int j = 0; j <= m; ++j) {
int idx = n - i + j;
while (cur_v_y[idx] - cur_v_len[idx] == i) {
int y = cur_v_y[idx];
// x-j == y-i
int x = y - i + j;
forw_back_len[x] = max(forw_back_len[x], cur_v_len[idx]);
if (y == n || x == m) {
cur_v_y[idx] = -1;
} else {
++cur_v_y[idx];
if (s[y] == t[x]) {
++cur_v_len[idx];
} else {
cur_v_len[idx] = 0;
}
}
}
}
vector< short > back_forw_len(m + 1);
for (int j = 0; j <= m; ++j) {
int nj = j - cur_h_len[j];
back_forw_len[nj] = max(back_forw_len[nj], cur_h_len[j]);
}
for (int j = 1; j <= m; ++j) {
back_forw_len[j] = max((int)back_forw_len[j], back_forw_len[j - 1] - 1);
}
for (int j = 0; j <= m; ++j) {
if (forw_back_len[j] + back_forw_len[j] > res) {
res = forw_back_len[j] + back_forw_len[j];
loc[0] = i - back_forw_len[j];
loc[1] = j - forw_back_len[j];
}
}
if (i < n) {
for (int j = m - 1; j >= 0; --j) {
if (s[i] == t[j]) {
cur_h_len[j + 1] = cur_h_len[j] + 1;
} else {
cur_h_len[j + 1] = 0;
}
}
cur_h_len[0] = 0;
}
}
return res;
}
int solve(string &s, string &t, int *loc,int res) {
int loc_noflip[2];
int loc_flip[2];
int res_flip = solve_noflip(s, t, loc_flip);
if (res_flip > res) {
res = res_flip;
loc[0] = loc_flip[0];
loc[1] = (int)t.size() - loc_flip[1] - res;
} else {
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s,p,t;
cin>>s>>p;
for(int j=p.size()-1;j>=0;j--){
t+=p[j];
}
int loc[2];
int z[s.size()+p.size()+1];
int y[s.size()+p.size()+1],x[s.size()+p.size()+1];
int ans=0;
int e,f;
for(int i=0;i<s.size();i++){
string r=s.substr(i,s.size()-i);
zedd(p,r,z);
r.clear();
for(int j=i-1;j>=0;j--){
r+=s[j];
}
kmp(t,r,y);
for(int j=0;j<p.size();j++){
x[j]=y[p.size()-j-1];
}
x[p.size()]=0;
for(int j=0;j<p.size();j++){
if(z[j]+x[j+z[j]]>ans){
ans=z[j]+x[j+z[j]];
e=i-x[j+z[j]];
f=j;
}
}
}
loc[0]=e;
loc[1]=f;
cout<<solve(s,t,loc,ans)<<endl;
cout<<loc[0]<<" "<<loc[1];
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||