Submission #1005606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005606		anango	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	1449 ms	596 KiB

necklace

#include <bits/stdc++.h>
#define int long long

using namespace std;
mt19937 rng;
int INF = 1LL<<60;
int p = 2071723;
int MOD = 1000000033;
std::chrono::steady_clock::time_point begin2 = std::chrono::steady_clock::now();

string a;
string b;
int n,m;

vector<int> hashes;

void compute_hash(string s) {
    int n1 = s.size();
    hashes.clear();
    hashes=vector<int>(n1+1,0);
    int ha = 0;
    for (int i=0; i<n1; i++) {
        ha += s[i]-'a';
        ha *= p;
        ha %= MOD;
        hashes[i+1] = ha;
    }
    
}

int exp(int p, int n) {
    int ans=1;
    int r = p;
    for (int i=0; i<30; i++) {
        if (n&(1<<i)) {
            ans*=r;
            ans%=MOD;
        }
        r*=r;
        r%=MOD;
    }
    return ans;
}

int gethash(int l, int r) {
    int h1 = hashes[l];
    int h2 = hashes[r+1];
    h1 *= exp(p,r-l+1);
    h1%=MOD;
    int dif = h2-h1;
    dif%=MOD;
    dif+=MOD;
    dif%=MOD;
    return dif;
}

bool check(int a, int b, int length) {
    return gethash(a,a+length-1)==gethash(b,b+length-1);
}
bool verify(int i, int j, int length) {
    //checks if i...i+length-1 in a = j...j+length-1 in b
    return gethash(i,length-1)==gethash(n+j, length-1);
}
int cutoff;
vector<pair<int,int>> solve() {
    compute_hash(a+b);
    int ans = 0;
    pair<int,int> xpos;
    pair<int,int> ypos;
    vector<vector<int>> binddict(26);
    for (int i=0; i<m; i++) {
        binddict[b[i]-'a'].push_back(i);
    }

    for (int trial=0; ; trial++) {
        if (!(trial%(20000/(ans+1)))) {
            std::chrono::steady_clock::time_point end2 = std::chrono::steady_clock::now();
            int x = std::chrono::duration_cast<std::chrono::microseconds>(end2 - begin2).count();
            if (x>cutoff) {
                //cout <<x <<" " << cutoff <<" " << trial << " " << ans << endl;
                return {{ans,ans},xpos,ypos};
            }
        }
        int i,j;
        i=rng()%n; 
        j=rng()%m; 
        if (binddict[a[i]-'a'].size()==0) {
            continue;
        }
        j=binddict[a[i]-'a'][rng()%(binddict[a[i]-'a'].size())];
        //cout << "testing " << i <<" " << j << endl;
        if (a[i]!=b[j]) {
            continue;
        }
        int l,r;
        l=0;
        r=0;
        while (l+i>=0 && l+j>=0 && a[i+l]==b[j+l]) {
            //cout << "doing " << i <<" " << l <<" " << a[i+l] <<" " << b[j+l] << endl;
            l--;
        }
        l++;
        while (r+i<=n-1 && r+j<=m-1 && a[i+r]==b[j+r]) {
            r++;
        }
        r--;
        int length = r-l+1;
        int subans = length;
        if (subans>ans) {
            ans=subans;
            xpos={i+l,i+l+length};
            ypos={j+l,j+l+length};
        }
        if (subans<=ans/2) {
            continue;
        }
        for (int blubber=1; blubber<=length; blubber++) { //add it on both sides
            int la = i+r+1;
            int ra = i+r+blubber;
            int lb = j+l-blubber;
            int rb = j+l-1;
            if (!(0<=la && la<=n-1) || !(0<=lb && rb<=m-1)) {
                break;
            }
            if (gethash(la,ra)==gethash(n+lb,n+rb)) {
                int subans = blubber+length;
                if (subans>ans) {
                    //cout << a <<" " << b <<" " << ans <<" " << i <<" " << j <<" " << blubber <<" " << subans << endl;
                    //cout << la <<" " << ra <<" " << lb <<" " << rb << endl;
                    ans=subans;
                    xpos = {i+l,ra};
                    ypos = {lb,j+r};
                }
            }
        }

    }
    return {{ans,ans},xpos,ypos};

    
}

signed main() {
    //freopen("input.txt","r", stdin);
    //freopen("output.txt","w",stdout);
    const std::clock_t c_start = std::clock();
    auto t_start = std::chrono::high_resolution_clock::now();
    cin >> a;
    cin >> b;
    n=a.size();
    m=b.size();
    vector<pair<int,int>> ans2;
    vector<int> ans(3);
    int TL = 1450000;
    cutoff=TL/4;
    ans2=solve();
    ans[0] = ans2[0].first;
    ans[1] = ans2[1].first; 
    ans[2] = ans2[2].first;
    reverse(b.begin(), b.end());
    cutoff=2*TL/4;
    ans2 = solve();
    if (ans2[0].first>ans[0]) {
        ans[0] = ans2[0].first;
        ans[1] = ans2[1].first;
        ans[2] = m-ans2[2].second-1;
    }
    reverse(a.begin(), a.end());
    cutoff=3*TL/4;
    ans2 = solve();
    if (ans2[0].first>ans[0]) {
        ans[0] = ans2[0].first;
        ans[1] = n-ans2[1].second-1;
        ans[2] = m-ans2[2].second-1;
    }
    reverse(b.begin(), b.end());
    cutoff=4*TL/4;
    ans2 = solve();
    if (ans2[0].first>ans[0]) {
        ans[0] = ans2[0].first;
        ans[1] = n-ans2[1].second-1;
        ans[2] = ans2[2].first;
    }
    cout << ans[0] << endl;
    cout << ans[1] <<" " << ans[2] << endl;


    //want to store for each x and j, the smallest t such that match[x][t]+t = j
    

}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:146:24: warning: unused variable 'c_start' [-Wunused-variable]
  146 |     const std::clock_t c_start = std::clock();
      |                        ^~~~~~~
necklace.cpp:147:10: warning: variable 't_start' set but not used [-Wunused-but-set-variable]
  147 |     auto t_start = std::chrono::high_resolution_clock::now();
      |          ^~~~~~~

• Subtask 1: 15 / 15