Submission #544783

#	Time	Username	Problem	Language	Result	Execution time	Memory
544783		rainboy	Matching (CEOI11_mat)	C11	100 / 100	440 ms	51928 KiB

mat

#include <stdio.h>

#define N	1000000

int main() {
	static int ii[N], pp[N], qq[N], pp_[N], qq_[N], aa[N * 2], zz[N * 2];
	int n, m, n_, h, i, l, r, cnt;

	scanf("%d%d", &m, &n), n_ = m + n;
	for (h = 0; h < m; h++) {
		scanf("%d", &i), i--;
		aa[i] = h, ii[h] = i;
	}
	for (i = 0; i < n; i++)
		scanf("%d", &aa[m + i]), aa[m + i] += m;
	for (i = 0; i < m; i++)
		pp[i] = i - 1, qq[i] = i + 1;
	for (i = m - 1; i >= 0; i--) {
		int a = aa[i];

		pp_[i] = pp[a] == -1 ? -1 : ii[pp[a]], qq_[i] = qq[a] == m ? m : ii[qq[a]];
		if (pp[a] != -1)
			qq[pp[a]] = qq[a];
		if (qq[a] != m)
			pp[qq[a]] = pp[a];
	}
	for (i = l = r = 1; i < n_; i++)
		if (zz[i - l] < r - i)
			zz[i] = zz[i - l];
		else {
			l = i;
			while (r < n_ && r - l < m && (pp_[r - l] == -1 || aa[l + pp_[r - l]] < aa[r]) && (qq_[r - l] == m || aa[r] < aa[l + qq_[r - l]]))
				r++;
			zz[i] = r - l;
		}
	cnt = 0;
	for (i = m; i < n_; i++)
		if (zz[i] == m)
			ii[cnt++] = i - m;
	printf("%d\n", cnt);
	for (h = 0; h < cnt; h++)
		printf("%d ", ii[h] + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

mat.c: In function 'main':
mat.c:9:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  scanf("%d%d", &m, &n), n_ = m + n;
      |  ^~~~~~~~~~~~~~~~~~~~~
mat.c:11:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~
mat.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", &aa[m + i]), aa[m + i] += m;
      |   ^~~~~~~~~~~~~~~~~~~~~~~

• 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