Submission #1079389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079389		Mike_Vu	Matching (CEOI11_mat)	C++14	100 / 100	170 ms	51796 KiB

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 pb push_back
#define fi first
#define se second

bool maximize(ll &x, ll y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(ll &x, ll y){
    if (x > y) {x = y; return true;}
    return false;
}

const int maxn = 1e6+5;
int n, m, a[maxn], s[maxn];

int kmp[maxn], match[maxn];
int ind1[maxn], ind2[maxn], point1[maxn], point2[maxn], corind[maxn]; //for every prefix

bool check(int i, int temp, int val[]) {
    if (temp > n) return 0;
    return ((ind1[temp]==0 || val[i]>val[i-temp+ind1[temp]])&&
            (ind2[temp]==0 || val[i]<val[i-temp+ind2[temp]]));
}

void setupkmp() {
    memset(ind1, 0, sizeof(ind1));
    memset(ind2, 0, sizeof(ind2));
    point1[0] = point2[0] = corind[0] = 0;
    for (int i = 1; i <= n; i++) {
        point1[i] = i-1;
        point2[i] = i+1;
        if (i == n) point2[i] = 0;
    }
    for (int i = n; i; i--) {
        ind1[i] = corind[point1[s[i]]];
        ind2[i] = corind[point2[s[i]]];
        point1[point2[s[i]]] = point1[s[i]];
        point2[point1[s[i]]] = point2[s[i]];
    }
    int temp = kmp[1] = 0;
    for (int i = 2; i <= n; i++) {
        while (temp > 0 && !check(i, temp+1, s)) temp = kmp[temp];
        kmp[i] = check(i, temp+1, s) ? ++temp : 0;
    }
}

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "matching"
//    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++) {
        cin >> corind[i];
        s[corind[i]] = i;
    }
    for (int i= 1; i <= m; i++) {
        cin >> a[i];
    }
    setupkmp();
    kmpsolve();
}
/*
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9

5 10
2 1 5 4 3
31 3 5 4 49 47 35 6 37 39

5 10
2 1 5 4 3
5 1 3 2 10 9 6 4 7 8

1 2 1 2 3 4 5 2 3 1
1 2 1 2 3 4 5 5 3 1
*/

• 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