Submission #1017622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017622		caterpillow	Matching (CEOI11_mat)	C++17	100 / 100	233 ms	59988 KiB

mat

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

let fb[i] be how much you should shift your pattern to the right if you mismatch at index i
    i cant be 0

let s be the prefix that we currently know matches
if there does not exist a suffix of this prefix which matches the prefix of s, then we can slide our pattern
    to the end of s, since we know that it definitely wont match inside this prefix

however, if there does exist a suffix that matches the prefix, we can slide our pattern
such that our prefix is now aligned with this matching suffix
    and then start matching from there

-------------------------------------------------------------------------------------------

let the pattern be p
let s be the prefix of the pattern of length i
fb[i] = the length of the longest suffix in s such that this suffix matches the prefix of s
define fb[0] = -1

if we can compute this array, then
    if we know that we have a prefix of length i that matches the string (so char at index i is the first mismatch)
    we can delete the first i - fb[i] characters of the string, and we will know that 
    characters up to fb[i] - 1 will match the pattern of this new string and index fb[i] may or may not be a mismatch

for example, the string abcdabc would have fb = [-1, 0, 0, 0, 0, 1, 2, 3]

-------------------------------------------------------------------------------------------

to compute this array, we would like to know many characters each suffix of the pattern p match with itself
for example, abcdabc would be [7, 0, 0, 0, 3, 0, 0]
let this array be called dp
then, calculating fb[i] in increasing i, 
    let j be the leftmost index among the indices strictly less than i such that j + dp[j] >= i
    fb[i] = i - j

we need to exclude dp[0], since we only care about proper suffixes

-------------------------------------------------------------------------------------------

to calculate dp, idk 

*/

// automatically pad on either side
struct DSU {
    vt<int> e, rep;
    void init(int n) {
        e.resize(n + 2, -1);
        rep.resize(n + 2); iota(all(rep), 0);
    }
    int _find(int x) { // just remember to add 1 before calling
        return e[x] < 0 ? x : e[x] = _find(e[x]);
    }
    void _unite(int x, int y) {
        x = _find(x), y = _find(y);
        if (e[x] < e[y]) swap(x, y), swap(rep[x], rep[y]);
        e[y] += e[x];
        e[x] = y;
    }

    void unite(int x, int y) {
        _unite(x + 1, y + 1);
    }
    int find(int x) {
        return rep[_find(x + 1)] - 1;
    }
};

int m, n;
vt<int> pat;
vt<pi> comp;
vt<int> h;

// check match at index j of the pattern starting at index i in str
bool match(int i, int j, vt<int>& str) { 
    pi prv = comp[j - i];
    bool good = true;
    if (prv.f != -1) good &= str[prv.f + i] < str[j];
    if (prv.s != -1) good &= str[j] < str[prv.s + i];
    return good;
}

vt<int> dp;
void compute_dp() {
    dp.resize(m, inf);
    dp[0] = 0;
    int j = 1; // the first mismatched character starting from index i
    FOR (i, 1, m) {
        while (j < m && match(i, j, pat)) j++;
        dp[i] = j - i;
        int k = 1;
        while (i + k < m && i + k + dp[k] < j) { // case 1: we know the mismatch happens in our good prefix
            dp[i + k] = dp[k];
            k++;
        }
        i += k - 1;
    }
}   

vt<int> fb;
void compute_fallback() {
    fb.resize(m + 1, -1);
    queue<int> q;
    FOR (i, 1, m + 1) {
        q.push(i - 1);
        while (size(q) && q.front() + dp[q.front()] < i) q.pop();
        if (!size(q)) fb[i] = 0; 
        else fb[i] = i - q.front();
    }
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> m >> n;
    pat.resize(m);
    F0R (i, m) {
        int v; cin >> v;
        pat[v - 1] = i;
    }
    comp.resize(m, {-1, -1});

    // need to optimise memory bruh
    DSU next_lower, next_higher;
    next_lower.init(m);
    next_higher.init(m);
    vt<int> rpat(m); F0R (i, m) rpat[pat[i]] = i;
    ROF (i, 0, m) {
        int lo = next_lower.find(pat[i] - 1);
        int hi = next_higher.find(pat[i] + 1);
        if (lo != -1) comp[i].f = rpat[lo];
        if (hi != m) comp[i].s = rpat[hi];
        next_lower.unite(pat[i], pat[i] - 1);
        next_higher.unite(pat[i], pat[i] + 1);
    }
     
    h.resize(n);
    F0R (i, n) cin >> h[i];

    compute_dp();
    compute_fallback();

    vt<int> out;

    int i = 0;
    int off = 0;
    while (i + off < n) {
        while (i + off < n && i < m && match(off, off + i, h)) i++;
        if (i == m) out.pb(off);
        off += i - fb[i];
        i = fb[i];
    }

    cout << size(out) << endl;
    for (int e : out) cout << e + 1 << " ";
    cout << endl;
}

Compilation message (stderr)

mat.cpp:158:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  158 | main() {
      | ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10