Submission #653739

#	Time	Username	Problem	Language	Result	Execution time	Memory
653739		600Mihnea	Matching (CEOI11_mat)	C++17	100 / 100	363 ms	48148 KiB

mat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#ifdef ONPC
mt19937 rng(228);
#else
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

signed main() {
#ifndef ONPC
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	int n, m;
	cin >> n >> m;
	vector<int> a(n), pos(n), b(m);
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		x--;
		a[x] = i;
		pos[i] = x;
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	if (0) {
		cout << "a = ";
		for (int i = 0; i < n; i++) {
			cout << a[i] << " ";
		}
		cout << "\n";
	}
	vector<int> small(n, -1), big(n, -1);
	vector<int> urm(n, -1), ant(n, -1);
	for (int i = 0; i < n - 1; i++) {
		urm[i] = i + 1;
		ant[i + 1] = i;	
	}
	for (int i = n - 1; i >= 0; i--) {
		int x = a[i];
		if (ant[x] != -1) {
			small[i] = i - pos[ant[x]];
		}
		if (urm[x] != -1) {
			big[i] = i - pos[urm[x]];
		}
		int a = ant[x], b = urm[x];
		if (b != -1) ant[b] = a;
		if (a != -1) urm[a] = b;	
	}
	int cnt = 0;
	function<int(vector<int>&, int, int)> isok = [&] (vector<int> &v, int pos, int j) {
		//cout << " = " << pos << " " << j << ", " << small[j] << " " << big[j] << "\n";
		//cnt++;
		if (cnt == 2) {
			//exit(0);
		}
//		cout << " : " << pos << " out of " << (int) v.size() << "\n";
		assert(0 <= j && j < n);
		assert(0 <= pos && pos < (int) v.size());
		
		if (small[j] != -1) {
			assert(pos - small[j] >= 0);
		}
		if (big[j] != -1) {
			assert(pos - big[j] >= 0);
		}
		if (small[j] != -1 && v[pos] < v[pos - small[j]]) {
			return 0;
		}
		if (big[j] != -1 && v[pos] > v[pos - big[j]]) {
			return 0;
		}
		return 1;
	};
	vector<int> ps(n, 0);
	int j = 0;
	for (int i = 1; i < n; i++) {
		while (j && !isok(a, i, j)) {
			j = ps[j - 1];
		}
		if (isok(a, i, j)) {
			j++;
		}
		ps[i] = j;
	}
	//exit(0);
	vector<int> sol;
	j = 0;
	for (int i = 0; i < m; i++) {
		while (j && !isok(b, i, j)) {
			j = ps[j - 1];
		}
		if (isok(b, i, j)) {
			j++;
		}
		if (j == n) {
			sol.push_back(i - n + 2);
			j = ps[j - 1];
		}
	}
	cout << (int) sol.size() << "\n";
	for (auto &i : sol) {
		cout << i << " ";
	}
	cout << "\n";
	return 0;
}
/*
input = 
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9

output = 
2
2 6
*/
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

• 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