oj.uz

답안 #124153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124153 2019-07-02T15:08:14 Z pedy4000 Matching (CEOI11_mat) C++14
83 / 100
 381 ms 40220 KB 
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

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 && 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() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> Crr[i];
		Crr[i]--;

		Arr[Crr[i]] = i;
	}

	processRel();

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

	KMP();
	findMatching();

	cout << ans.size() << "\n";
	for (int l: ans)
		cout << l << (ans.back() == l? "\n": " ");
	return 0;
}

// S --> 5:45

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 760 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3292 KB Output is correct
2 Correct 26 ms 2472 KB Output is correct
3 Correct 41 ms 4320 KB Output is correct
4 Correct 41 ms 4284 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4228 KB Output is correct
2 Correct 32 ms 3252 KB Output is correct
3 Correct 35 ms 3940 KB Output is correct
4 Correct 42 ms 4692 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4216 KB Output is correct
2 Correct 31 ms 3576 KB Output is correct
3 Correct 33 ms 3576 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 19580 KB Output is correct
2 Correct 381 ms 40220 KB Output is correct
3 Correct 119 ms 11668 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 20404 KB Output is correct
2 Incorrect 126 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 14324 KB Output is correct
2 Correct 217 ms 22020 KB Output is correct
3 Correct 163 ms 15672 KB Output is correct
4 Correct 275 ms 38284 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 15676 KB Output is correct
2 Correct 157 ms 15940 KB Output is correct
3 Correct 75 ms 8412 KB Output is correct
4 Correct 275 ms 36860 KB Output is correct