Submission #544783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544783	2022-04-02T16:44:41 Z	rainboy	Matching (CEOI11_mat)	C	100 / 100	440 ms	51928 KB

#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

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

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	300 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 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	4 ms	692 KB	Output is correct
2	Correct	4 ms	724 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	724 KB	Output is correct
2	Correct	6 ms	660 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	31 ms	4212 KB	Output is correct
2	Correct	33 ms	3232 KB	Output is correct
3	Correct	39 ms	5452 KB	Output is correct
4	Correct	40 ms	5472 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	4968 KB	Output is correct
2	Correct	39 ms	3900 KB	Output is correct
3	Correct	34 ms	4508 KB	Output is correct
4	Correct	40 ms	5144 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	4972 KB	Output is correct
2	Correct	39 ms	4624 KB	Output is correct
3	Correct	36 ms	4372 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	25012 KB	Output is correct
2	Correct	440 ms	51928 KB	Output is correct
3	Correct	121 ms	14796 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	26528 KB	Output is correct
2	Correct	143 ms	14856 KB	Output is correct
3	Correct	347 ms	47436 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	18104 KB	Output is correct
2	Correct	208 ms	25724 KB	Output is correct
3	Correct	161 ms	19944 KB	Output is correct
4	Correct	288 ms	49884 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	19712 KB	Output is correct
2	Correct	172 ms	20104 KB	Output is correct
3	Correct	88 ms	11108 KB	Output is correct
4	Correct	281 ms	47700 KB	Output is correct