Submission #1105492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105492		vjudge1	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	454 ms	65536 KiB

necklace

// Thanks to : TVA
// Strycks, L3, PAD, TVT, NGUYEN^2, Whisper
// My friends...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define plli pair<ll, int>
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define se second
#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 FILE freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);
#define int long long

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using str = string;
using ld = long double;
using ull = unsigned long long;
using htype = unsigned long long;

template <class T> bool ckmin(T &a, const T &b) {return (a > b ? a = b, true : false); };
template <class T> bool ckmax(T &a, const T &b) {return (a < b ? a = b, true : false); };
template <class T> void compress(vector <T> &a) {sort(all(a)); a.resize(unique(all(a)) - a.begin()); };
template <class T> int getcom(vector<T> &a, T val) {return lower_bound(all(a), val) - a.begin() + 1; };

const ll mod = 998244353;                             /// MOD CHANGED

ll add(ll x, ll y){
    return (x + y) % mod;
}

ll sub(ll x, ll y){
    return ((x - y) % mod + mod) % mod;
}

ll mul(ll x, ll y){
    return (x * y) % mod;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const char MOVE[] = {'U', 'L', 'R', 'D'};

const ll INFll = 0x3f3f3f3f3f3f3f3f;
const int INFin = 0x3f3f3f3f;

const int maxn = 3e3 + 5;                           /// MAXN CHANGED

const int maxv = 1e6 + 5;                         /// MAXV CHANGED

vector <int> zfun(str s){
    int n = s.size();
    vector <int> z(n, 0);
    int l = 0, r = 0;
    For(i, 1, n - 1){
        if(l <= i && i <= r) z[i] = min(r - i + 1, z[i - l]);
        while(i + z[i] < n && s[i + z[i]] == s[z[i]]) ++z[i];
        if(i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

vector <int> kmp(str s){
    int n = s.size();
    vector <int> pi(n, 0);
    For(i, 1, n - 1){
        int k = pi[i - 1];
        while(k > 0 && s[k] != s[i]) k = pi[k - 1];
        if(s[k] == s[i]) ++k;
        pi[i] = k;
    }
    return pi;
}

vector <vector<int>> automa(str s){
    int n = s.size();
    s = s + '#';
    vector <int> pi = kmp(s);
    vector <vector<int>> nxt(n + 1, vector<int>(26, 0));
    For(x, 0, n){
        For(c, 0, 25){
            if(x > 0 && s[x] != c + 'a') nxt[x][c] = nxt[pi[x - 1]][c];
            else nxt[x][c] = x + (s[x] == c + 'a');
        }
    }
    return nxt;
}

str a, b;
int n, m;

void init(){
    cin >> a >> b;
    n = a.size();
    m = b.size() - 1;
}

str rev(str a){
    reverse(all(a));
    return a;
}

struct uwu{int mustlen, val; };

int fen[maxn][maxn];

void upd(int fen[], int x, int val){
    // assert(x >= 0);
    if(x == 0) return;
    for(; x <= n ; x += (x & -x)) ckmax(fen[x], val);
}

int get(int fen[], int x){
    int ans = 0;
    for(; x > 0 ; x -= (x & -x)) ckmax(ans, fen[x]);
    return ans;
}

void precal(str a, str b, int cnt){
    int n = a.size();
    vector <int> z = zfun(a + '#' + b);

    For(i, n + 1, z.size() - 1){
        upd(fen[m - (i - n - 1)], n - z[i], n);
    }
}

void precal1(str a, str b){
    str tmp = b;
    reverse(all(tmp));
    int cnt = 0;
    while(a.size()){
        precal(rev(a), tmp, ++cnt);
        a.pop_back();

    }
}


pair<int, pii> cal(str a, str b, int aps){
    pair<int, pii> ans = {0, {0, 0}};

    int n = a.size();
    vector <int> z = zfun(a + '#' + b);


    For(i, n + 1, z.size() - 1){
        ckmax(ans, {z[i], {i - n - 1, i - n - 2 + z[i]}});
        if(i == n + 1) continue;
        int len = get(fen[i - n - 2], z[i] + aps);
        ckmax(ans, {len - aps, {i - n - 1, i - n - 2 + z[i]}});
    }


    return ans;
}

pair<int, pii> solve(str a, str b){
    pair<int, pii> ans = {0, {0, 0}};
    precal1(a, b);
    For(aps, 0, n - 1){
        ckmax(ans, cal(a, b, aps));
        a.erase(0, 1);
    }

    memset(fen, 0, sizeof(fen));

    return ans;
}

void trace(str a, pair<int, pii> ans, bool type){
    cout << ans.fi << '\n';
    int pos = ans.se.se - ans.fi + 1;
    str tmp = "";
    For(i, ans.se.fi, ans.se.se) tmp += b[i];
    For(i, pos, ans.se.fi - 1) tmp += b[i];

    int res = (int)a.find(tmp);
    // assert(res != -1);
    if(type) res = n - res - ans.fi;
    cout << res << " " << pos;
}

void get(){
    pair<int, pii> ans = solve(a, b);
    pair<int, pii> ans2 = solve(rev(a), b);
    if(ans > ans2) trace(a, ans, 0);
    else trace(rev(a), ans2, 1);
}

signed main(){
    fast
    #define name "Anya"
    // FILE
    init();
    get();
}

Compilation message (stderr)

necklace.cpp: In function 'void precal(str, str, long long int)':
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
      |                                          ^
necklace.cpp:137:5: note: in expansion of macro 'For'
  137 |     For(i, n + 1, z.size() - 1){
      |     ^~~
necklace.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > cal(str, str, long long int)':
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
      |                                          ^
necklace.cpp:161:5: note: in expansion of macro 'For'
  161 |     For(i, n + 1, z.size() - 1){
      |     ^~~

• Subtask 1: 0 / 15