Submission #205321

#	Time	Username	Problem	Language	Result	Execution time	Memory
205321		ruler	Matching (CEOI11_mat)	C++14	100 / 100	830 ms	38504 KiB

mat

// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////

const int N = 1e6 + 3;

int FEN[N], F[N], P[N], H[N], S[N];

void Add(int p, int x) { for (p++; p < N; p += p & -p) FEN[p] += x; }
int Get(int p) {
	int res = 0;
	for (; p > 0; p -= p & -p) res += FEN[p];
	return res;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);	
	
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int p; cin >> p; p--;
		P[p] = i;
	}
	vector<int> comp, res;
	for (int i = 0; i < m; i++) cin >> H[i], comp.push_back(H[i]);
	sort(all(comp));
	for (int i = 0; i < m; i++) H[i] = lower_bound(all(comp), H[i]) - comp.begin();
	for (int i = 0; i < n; i++) S[i] = Get(P[i]), Add(P[i], +1);
	memset(FEN, 0, sizeof FEN);
	int cur = F[1] = 0;
	for (int i = 1; i < n; i++) {
		int s = Get(P[i]); Add(P[i], +1);
		while (cur && S[cur] != s) {
			for (int j = i - cur; j < i - F[cur]; j++) Add(P[j], -1);
			cur = F[cur];
			s = Get(P[i]);
		}
		if (S[cur] == s) cur++;
		F[i + 1] = cur;
	}
	memset(FEN, 0, sizeof FEN);
	cur = 0;
	for (int i = 0; i < m; i++) {
		int s = Get(H[i]); Add(H[i], +1);
		while (cur && S[cur] != s) {
			for (int j = i - cur; j < i - F[cur]; j++) Add(H[j], -1);
			cur = F[cur];
			s = Get(H[i]);
		}
		if (S[cur] == s) cur++;
		if (cur == n) {
			res.push_back(i - cur + 1);
			for (int j = i - cur + 1; j < i - F[cur] + 1; j++) Add(H[j], -1);
			cur = F[cur];
		}
	}
	cout << sz(res) << endl;
	for (int i : res) cout << i + 1 << ends;
	cout << endl;

	return 0;
}

• 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