Submission #653739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
653739	2022-10-27T20:59:53 Z	600Mihnea	Matching (CEOI11_mat)	C++17	100 / 100	363 ms	48148 KB

#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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	596 KB	Output is correct
2	Correct	3 ms	596 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	588 KB	Output is correct
2	Correct	3 ms	596 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3524 KB	Output is correct
2	Correct	19 ms	2528 KB	Output is correct
3	Correct	31 ms	4688 KB	Output is correct
4	Correct	31 ms	4608 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	4428 KB	Output is correct
2	Correct	23 ms	3188 KB	Output is correct
3	Correct	29 ms	3916 KB	Output is correct
4	Correct	33 ms	4572 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	4428 KB	Output is correct
2	Correct	23 ms	3916 KB	Output is correct
3	Correct	25 ms	3656 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	21288 KB	Output is correct
2	Correct	363 ms	48148 KB	Output is correct
3	Correct	92 ms	11760 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	22872 KB	Output is correct
2	Correct	101 ms	10888 KB	Output is correct
3	Correct	355 ms	43412 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	14488 KB	Output is correct
2	Correct	172 ms	21876 KB	Output is correct
3	Correct	117 ms	16080 KB	Output is correct
4	Correct	207 ms	46080 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	16428 KB	Output is correct
2	Correct	124 ms	16356 KB	Output is correct
3	Correct	59 ms	9164 KB	Output is correct
4	Correct	210 ms	43788 KB	Output is correct

Submission #653739

Compilation message