oj.uz

답안 #991864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991864 2024-06-03T09:39:04 Z KawakiMeido Necklace (Subtask 4) (BOI19_necklace4) C++17
3 / 15
 117 ms 604 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n,m;
int p1[6010],p2[6010];
string s,t;

//KMP
void KMP(string s,int *pi){
    pi[0] = 0;
    for (int i=1; i<(int) s.size(); i++){
        int j = pi[i-1];
        while (j<0 && s[i]!=s[j]){
            j = pi[j-1];
        }
        if (s[i]==s[j]) pi[i] = j+1;
        else pi[i] = 0;
    }
}

//Solve
pair<int,pii> get(string s, string t, bool rev){
    pair<int,pii> res = {0,{0,0}};
    for (int i=0; i<n; i++){
        string s1,s2,t1,t2;
        s1 = s.substr(0,i); s2 = s.substr(i);
        t1 = t; t2 = t;
        reverse(s1.begin(),s1.end());
        reverse(t2.begin(),t2.end());
        KMP(s1+"#"+t2,p1);
        KMP(s2+"#"+t1,p2);
        for (int j=1; j<=m; j++){
            res = max(res,{p1[i+m-j]+p2[n-i+j],
                            {i-p1[i+m-j],
                            (rev)? m-(j+p1[i+m-j]): j-p2[n-i+j]}});
        }
    }
    return res;
}

/*Solution*/
void solve(){
    cin >> s >> t;
    n = (int) s.size();
    m = (int) t.size();
    pair<int,pii> ans = get(s,t,0);
    reverse(t.begin(),t.end());
    ans = max(ans,get(s,t,1));
    cout << ans.fi << endl << ans.se.fi << " " << ans.se.se;
    cout << endl;
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
3.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 604 KB Output is correct
2 Partially correct 95 ms 592 KB Output is partially correct
3 Partially correct 96 ms 576 KB Output is partially correct
4 Correct 87 ms 348 KB Output is correct
5 Correct 98 ms 348 KB Output is correct
6 Correct 117 ms 360 KB Output is correct
7 Correct 94 ms 344 KB Output is correct
8 Correct 98 ms 584 KB Output is correct
9 Correct 92 ms 348 KB Output is correct