Submission #1126113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126113		Mike_Vu	Matching (CEOI11_mat)	C++17	100 / 100	291 ms	35592 KiB

mat

///problem: https://oj.uz/problem/view/CEOI11_mat
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 1e6+5;
int n, m, a[maxn], b[maxn];
int pleft[maxn], pright[maxn], ind[maxn]; //pointer left-right
int posdown[maxn], posup[maxn]; //positions of comparing numbers
int kmp[maxn], match[maxn];
vector<int> ans;

void setupval() {
    for (int i = 1; i <= n ;i++) {
        ind[a[i]] = i;
        pleft[i] = i-1;
        pright[i] = i+1;
    }
    for (int i = n; i; i--) {
        posdown[i] = pleft[a[i]] != 0 ? ind[pleft[a[i]]] : -1;
        posup[i] = pright[a[i]] != n+1 ? ind[pright[a[i]]] : -1;
        //del
        pright[pleft[a[i]]] = pright[a[i]];
        pleft[pright[a[i]]] = pleft[a[i]];
    }
//    for (int i = 1; i <= n; i++) {
//        cout << i << ' ' << posdown[i] << ' ' << posup[i] << "\n";
//    }
}

bool check(int len, int i, int val[]) {///check if i is the len element
    if (posdown[len] != -1) {
        if (val[i-(len-posdown[len])] >= val[i]) return 0;
    }
    if (posup[len] != -1) {
        if (val[i-(len-posup[len])] <= val[i]) return 0;
    }
    return 1;
}

void setupkmp() {
    int temp = kmp[1] = 0;
    for (int i = 2; i <= n; i++) {
        while (temp > 0 && !check(temp+1, i, a)) temp = kmp[temp];
        kmp[i] = check(temp+1, i, a) ? ++temp : 0;
    }
//    for (int i = 1; i <= n; i++) {
//        cout << kmp[i] << ' ';
//    }
//    cout << "\n";
}

void solvekmp() {
    int temp = match[0] = 0;
    for (int i = 1; i <= m; i++) {
        if (temp == n) temp = kmp[temp];
        while (temp > 0 && !check(temp+1, i, b)) temp = kmp[temp];
        match[i] = check(temp+1, i, b) ? ++temp : 0;
        if (match[i] == n) {
            ans.pb(i-n+1);
        }
    }
//    for (int i= 1; i <= m; i++) {
//        cout << match[i] << ' ';
//    }
//    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")){
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> m;
    for (int i= 1; i <= n; i++) {
        int x;
        cin >> x;
        a[x] = i;
    }
    for (int j = 1; j <= m; j++) {
        cin >> b[j];
    }
    setupval();
    setupkmp();
    solvekmp();
    cout << (int)ans.size() << "\n";
    for (int x : ans) {
        cout << x << ' ';
    }
}

• 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