Submission #1222170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222170		hoa208	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	313 ms	648 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const ll mod = 1e9 + 7;
const ll INF = 1e17;
const ll N = 6e3 + 10;
ll p1[N], p2[N];
void get(string s, ll *p) {

    FOR(i, 1, s.size() - 1)
    {
        p[i] = 0;
        ll k = p[i-1];
        while(k > 0 && s[i] != s[k])
            k = p[k - 1];
        p[i] = k + (s[k] == s[i] ? 1 : 0);
    }
}
pair<ll, pa> slove(string s, string t, bool flag) {
    ll n = s.size(), m = t.size();
    ll ans = 0;
    ll id_l = 0, id_r = 0;
    FOR(i, 0, n - 1) {

        string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
		reverse(s1.begin(), s1.end());
		string t1 = t, t2 = t;
		reverse(t2.begin(), t2.end());
		get(s1 + "#" + t1, p1), get(s2 + "#" + t2, p2);
        FOR(j, 1, m) {
        ll val = p1[i + j] + p2[n + m - i - j];
            if(ans <= val) {
                ans = val;
                id_l = i - p1[i + j];
                id_r = flag ? m - j - p2[n + m - i - j] : j - p1[i + j];
            }
        }
    }
    return {ans, {id_l, id_r}};
}
int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen("hbmt.inp", "r")) {
            freopen("hbmt.inp", "r", stdin);
            freopen("hbmt.out", "w", stdout);
        }
    string s, t;
    cin >> s >> t;
    pair<ll, pa> ans1 = slove(s, t, 0);
    reverse(t.begin(), t.end());
    pair<ll, pa> ans2 = slove(s, t, 1);
    if(ans1.fi > ans2.fi) {
        cout << ans1.fi << '\n';
        cout << ans1.se.fi << ' ' << ans1.se.se << '\n';
    }
    else {
         cout << ans2.fi << '\n';
        cout << ans2.se.fi << ' ' << ans2.se.se << '\n';
    }
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:52:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             freopen("hbmt.inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:53:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |             freopen("hbmt.out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15