Submission #444668

#	Time	Username	Problem	Language	Result	Execution time	Memory
444668		prvocislo	Matching (CEOI11_mat)	C++17	100 / 100	441 ms	47964 KiB

mat

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e6 + 5;
int s[maxn]; // povodne pole
int p[maxn]; // p[i] = relativna vyska i-teho schodiku
int nx[maxn], pv[maxn]; // polia pre linked list. Indexujeme do nich poradim. Cize na zaciatku su vsetky prvky zlinkovane v poradi 0, ..., n-1.
int dist_pv[maxn], dist_nx[maxn]; // o kolko dozadu sa nachadza prvok ktory je tesne mensi/vacsi ako ja?
int h[maxn]; // vysky budov
int f[maxn]; // failure funkcia pre KMP
bool ok(int i, int j, int *text) // mozeme posunut index j v patterne ak dalsi znak je text[i]?
{
    if ((!dist_pv[j+1] || text[i-dist_pv[j+1]] < text[i]) && (!dist_nx[j+1] || text[i-dist_nx[j+1]] > text[i])) return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        p[--s[i]] = i;
        nx[i] = i+1, pv[i] = i-1;
    }
    for (int i = n-1; i >= 0; i--)
    {
        if (pv[p[i]] != -1) // najblizsi mensi prvok v mojom prefixe
        {
            dist_pv[i] = i - s[pv[p[i]]]; // p[i] je hodnota mojho prvku, pv[p[i]] je najblizsi mensi
            nx[pv[p[i]]] = nx[p[i]];
        }
        if (nx[p[i]] != n) // najblizsi vacsi prvok v mojom prefixe
        {
            dist_nx[i] = i - s[nx[p[i]]]; // p[i] je hodnota mojho prvku, nx[p[i]] je najblizsi vacsi
            pv[nx[p[i]]] = pv[p[i]];
        }
    }
    f[0] = -1;
    for (int i = 1, j = f[0]; i < n; i++)
    {
        while (j != -1 && !ok(i, j, p)) j = f[j];
        if (ok(i, j, p)) j++;
        f[i] = j;
    }
    vector<int> ans;
    for (int i = 0, j = -1; i < m; i++)
    {
        cin >> h[i];
        while (j != -1 && !ok(i, j, h)) j = f[j];
        if (ok(i, j, h)) j++;
        if (j == n-1)
        {
            ans.push_back(i-(n-1));
            j = f[j];
        }
    }
    cout << ans.size() << "\n";
    for (int i : ans) cout << i+1 << " ";
    cout << "\n";
    return 0;
}

• 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