oj.uz

답안 #1005563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005563 2024-06-22T15:40:49 Z anango Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 805 ms 592 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;
mt19937 rng;
int INF = 1LL<<60;
int p = 2071723;
int MOD = 1000000033;

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);
}

vector<pair<int,int>> solve() {
    compute_hash(a+b);
    int ans = 0;
    pair<int,int> xpos;
    pair<int,int> ypos;
    for (int trial=0; trial*ans<7000000; trial++) {
        int i,j;
        i=rng()%n;  
        j=rng()%m;
        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);
    cin >> a;
    cin >> b;
    n=a.size();
    m=b.size();
    vector<pair<int,int>> ans2;
    vector<int> ans(3);
    ans2=solve();
    ans[0] = ans2[0].first;
    ans[1] = ans2[1].first;
    ans[2] = ans2[2].first;
    reverse(b.begin(), b.end());
    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());
    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());
    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
    

}

Subtask #1
5.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 592 KB Output is correct
2 Partially correct 160 ms 348 KB Output is partially correct
3 Correct 480 ms 348 KB Output is correct
4 Correct 259 ms 348 KB Output is correct
5 Partially correct 39 ms 344 KB Output is partially correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 592 KB Output is correct
2 Partially correct 160 ms 348 KB Output is partially correct
3 Correct 480 ms 348 KB Output is correct
4 Correct 259 ms 348 KB Output is correct
5 Partially correct 39 ms 344 KB Output is partially correct
6 Partially correct 334 ms 348 KB Output is partially correct
7 Correct 163 ms 344 KB Output is correct
8 Partially correct 284 ms 420 KB Output is partially correct
9 Correct 200 ms 344 KB Output is correct
10 Correct 8 ms 348 KB Output is correct
11 Correct 9 ms 348 KB Output is correct
12 Correct 649 ms 592 KB Output is correct

Subtask #3
8.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 592 KB Output is correct
2 Partially correct 160 ms 348 KB Output is partially correct
3 Correct 480 ms 348 KB Output is correct
4 Correct 259 ms 348 KB Output is correct
5 Partially correct 39 ms 344 KB Output is partially correct
6 Partially correct 334 ms 348 KB Output is partially correct
7 Correct 163 ms 344 KB Output is correct
8 Partially correct 284 ms 420 KB Output is partially correct
9 Correct 200 ms 344 KB Output is correct
10 Correct 8 ms 348 KB Output is correct
11 Correct 9 ms 348 KB Output is correct
12 Correct 649 ms 592 KB Output is correct
13 Partially correct 350 ms 344 KB Output is partially correct
14 Partially correct 173 ms 348 KB Output is partially correct
15 Partially correct 400 ms 348 KB Output is partially correct
16 Partially correct 181 ms 504 KB Output is partially correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 12 ms 344 KB Output is correct
19 Partially correct 151 ms 496 KB Output is partially correct
20 Partially correct 799 ms 344 KB Output is partially correct
21 Partially correct 805 ms 520 KB Output is partially correct