Submission #124160

#	Time	Username	Problem	Language	Result	Execution time	Memory
124160		pedy4000	Matching (CEOI11_mat)	C++14	100 / 100	126 ms	24876 KiB

mat

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

inline char nc() {
    static char buf[1000000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
    int x=0; char ch=nc();
    while(ch<'0'||ch>'9') ch=nc();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=nc();
    return x;
}


const int MAX_N = 1e6 + 6;
int n, m;
int Arr[MAX_N];
int Brr[MAX_N];
int Crr[MAX_N];
int F[MAX_N];
int sm[MAX_N];
int bg[MAX_N];
vector <int> ans;

bool can (int *list, int l, int r) {
	int ind = r - l;

	if (list[r] < list[l + sm[ind]])
		return false;

	if (list[l + bg[ind]] < list[r])
		return false;

	return true;
}

void KMP() {
	F[1] = 0;
	F[2] = 1;
	int ind = 1;
	for (int i = 3; i <= n; i++) {
		while (ind && !can(Arr, i - ind - 1 , i - 1))
			ind = F[ind];

		ind++;
		F[i] = ind;
	}
}

void processRel() {
	sm[Crr[0]] = Crr[0];
	for (int i = 1; i < n; i++) {
		sm[Crr[i]] = Crr[i];
		int ind = Crr[i - 1];

		while (sm[ind] != ind && Crr[i] < ind)
			ind = sm[ind];

		if (ind <= Crr[i])
			sm[Crr[i]] = ind;
	}

	bg[Crr[n - 1]] = Crr[n - 1];
	for (int i = n - 2; ~i; i--) {
		bg[Crr[i]] = Crr[i];
		int ind = Crr[i + 1];

		while (bg[ind] != ind && Crr[i] < ind)
			ind = bg[ind];

		if (ind <= Crr[i])
			bg[Crr[i]] = ind;
	}
}

void findMatching() {
	int L = 0, R = 0;
	while (L < m) {
		while (R + 1 < L + n && R + 1 < m && can(Brr, L, R + 1))
			R++;
		
		if (R - L == n - 1)
			ans.push_back(L + 1);

		if (L == R)
			L++, R++;
		else
			L += R - L + 1 - F[R - L + 1];
	}
}

int main() {
	n = rd();
	m = rd();
	for (int i = 0; i < n; i++) {
		Crr[i] = rd();
		Crr[i]--;

		Arr[Crr[i]] = i;
	}

	processRel();

	for (int i = 0; i < m; i++)
		Brr[i] = rd();

	KMP();
	findMatching();

	printf("%lu\n", ans.size());
	for (int l: ans)
		printf("%d ", l);
	return 0;
}

// S --> 5:45

• 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