oj.uz

답안 #1005567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005567 2024-06-22T15:45:28 Z anango Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 1414 ms 596 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<12000000; 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 527 ms 348 KB Output is correct
2 Partially correct 277 ms 344 KB Output is partially correct
3 Correct 778 ms 348 KB Output is correct
4 Correct 437 ms 348 KB Output is correct
5 Partially correct 71 ms 344 KB Output is partially correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 527 ms 348 KB Output is correct
2 Partially correct 277 ms 344 KB Output is partially correct
3 Correct 778 ms 348 KB Output is correct
4 Correct 437 ms 348 KB Output is correct
5 Partially correct 71 ms 344 KB Output is partially correct
6 Partially correct 571 ms 420 KB Output is partially correct
7 Correct 282 ms 596 KB Output is correct
8 Partially correct 511 ms 344 KB Output is partially correct
9 Correct 317 ms 348 KB Output is correct
10 Correct 20 ms 348 KB Output is correct
11 Correct 16 ms 444 KB Output is correct
12 Correct 1135 ms 424 KB Output is correct

Subtask #3
8.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 527 ms 348 KB Output is correct
2 Partially correct 277 ms 344 KB Output is partially correct
3 Correct 778 ms 348 KB Output is correct
4 Correct 437 ms 348 KB Output is correct
5 Partially correct 71 ms 344 KB Output is partially correct
6 Partially correct 571 ms 420 KB Output is partially correct
7 Correct 282 ms 596 KB Output is correct
8 Partially correct 511 ms 344 KB Output is partially correct
9 Correct 317 ms 348 KB Output is correct
10 Correct 20 ms 348 KB Output is correct
11 Correct 16 ms 444 KB Output is correct
12 Correct 1135 ms 424 KB Output is correct
13 Partially correct 631 ms 480 KB Output is partially correct
14 Correct 349 ms 500 KB Output is correct
15 Partially correct 705 ms 344 KB Output is partially correct
16 Partially correct 280 ms 344 KB Output is partially correct
17 Correct 3 ms 348 KB Output is correct
18 Correct 23 ms 348 KB Output is correct
19 Correct 259 ms 348 KB Output is correct
20 Correct 1414 ms 488 KB Output is correct
21 Partially correct 1335 ms 348 KB Output is partially correct