oj.uz

답안 #1005572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005572 2024-06-22T15:46:57 Z anango Necklace (Subtask 1-3) (BOI19_necklace1) C++17
53 / 85
 1435 ms 736 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<6000000; 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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 344 KB Output is correct
2 Correct 244 ms 412 KB Output is correct
3 Correct 711 ms 348 KB Output is correct
4 Correct 425 ms 348 KB Output is correct
5 Correct 63 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 344 KB Output is correct
2 Correct 244 ms 412 KB Output is correct
3 Correct 711 ms 348 KB Output is correct
4 Correct 425 ms 348 KB Output is correct
5 Correct 63 ms 344 KB Output is correct
6 Correct 483 ms 596 KB Output is correct
7 Correct 264 ms 428 KB Output is correct
8 Correct 479 ms 432 KB Output is correct
9 Correct 263 ms 344 KB Output is correct
10 Correct 12 ms 348 KB Output is correct
11 Correct 17 ms 348 KB Output is correct
12 Correct 964 ms 680 KB Output is correct

Subtask #3
8.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 344 KB Output is correct
2 Correct 244 ms 412 KB Output is correct
3 Correct 711 ms 348 KB Output is correct
4 Correct 425 ms 348 KB Output is correct
5 Correct 63 ms 344 KB Output is correct
6 Correct 483 ms 596 KB Output is correct
7 Correct 264 ms 428 KB Output is correct
8 Correct 479 ms 432 KB Output is correct
9 Correct 263 ms 344 KB Output is correct
10 Correct 12 ms 348 KB Output is correct
11 Correct 17 ms 348 KB Output is correct
12 Correct 964 ms 680 KB Output is correct
13 Correct 549 ms 480 KB Output is correct
14 Partially correct 252 ms 344 KB Output is partially correct
15 Partially correct 665 ms 528 KB Output is partially correct
16 Correct 334 ms 348 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 18 ms 348 KB Output is correct
19 Partially correct 264 ms 496 KB Output is partially correct
20 Partially correct 1135 ms 736 KB Output is partially correct
21 Correct 1435 ms 524 KB Output is correct