oj.uz

Submission #653740

# Submission time Handle Problem Language Result Execution time Memory
653740 2022-10-27T21:00:31 Z 600Mihnea Matching (CEOI11_mat) C++17
100 / 100
 387 ms 31820 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];
	}
	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;	
	}
	function<int(vector<int>&, int, int)> isok = [&] (vector<int> &v, int pos, int j) {
		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;
	}
	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;
}
/* 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 324 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 340 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 572 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 4 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 2352 KB Output is correct
2 Correct 20 ms 1372 KB Output is correct
3 Correct 28 ms 2668 KB Output is correct
4 Correct 30 ms 2648 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3012 KB Output is correct
2 Correct 22 ms 1408 KB Output is correct
3 Correct 24 ms 2272 KB Output is correct
4 Correct 37 ms 3500 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3076 KB Output is correct
2 Correct 21 ms 2484 KB Output is correct
3 Correct 23 ms 2124 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 11452 KB Output is correct
2 Correct 387 ms 31820 KB Output is correct
3 Correct 81 ms 4344 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 12904 KB Output is correct
2 Correct 89 ms 4436 KB Output is correct
3 Correct 374 ms 30496 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6732 KB Output is correct
2 Correct 161 ms 15440 KB Output is correct
3 Correct 108 ms 6476 KB Output is correct
4 Correct 202 ms 31776 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 8344 KB Output is correct
2 Correct 108 ms 6572 KB Output is correct
3 Correct 56 ms 5276 KB Output is correct
4 Correct 206 ms 29068 KB Output is correct