Submission #124172

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124172	2019-07-02T15:19:56 Z	pedy4000	Matching (CEOI11_mat)	C++14	100 / 100	129 ms	24924 KB

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int INPUT_MAXCHARS = 1 << 20;
char buffer[INPUT_MAXCHARS];
struct FastReader {
    char *p;

    FastReader(): p(buffer) {
        fread(buffer, 1, sizeof buffer, stdin);
    }
    int next_int() {
        int remchars = INPUT_MAXCHARS - (p-buffer);
        if (remchars < 25) {
            memcpy(buffer, p, remchars);
            size_t cnt = fread(buffer+remchars, 1, sizeof buffer - remchars, stdin);
            if (remchars + cnt < sizeof buffer) { // assume EOF
                buffer[remchars + cnt] = 0; // make the value determinate
            }
            p = buffer;
        }
        while (*p < '0') {
            p++;
        }
        int val = 0;
        while (*p >= '0') {
            val = val*10 + (*p - '0');
            ++p;
        }
        return val;
    }
};

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 && R + 1 < m && 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() {
	cin.sync_with_stdio(false);
    FastReader reader;
	n = reader.next_int();
	m = reader.next_int();
	for (int i = 0; i < n; i++) {
		Crr[i] = reader.next_int();
		Crr[i]--;

		Arr[Crr[i]] = i;
	}

	processRel();

	for (int i = 0; i < m; i++)
		Brr[i] = reader.next_int();

	KMP();
	findMatching();

	printf("%lu\n", ans.size());
	for (int l: ans)
		printf("%d ", l);
	return 0;
}

// S --> 5:45

Compilation message

mat.cpp: In constructor 'FastReader::FastReader()':
mat.cpp:13:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buffer, 1, sizeof buffer, stdin);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	632 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	2936 KB	Output is correct
2	Correct	5 ms	2296 KB	Output is correct
3	Correct	11 ms	3192 KB	Output is correct
4	Correct	12 ms	3192 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3576 KB	Output is correct
2	Correct	7 ms	2296 KB	Output is correct
3	Correct	10 ms	2904 KB	Output is correct
4	Correct	26 ms	4336 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	3576 KB	Output is correct
2	Correct	7 ms	3064 KB	Output is correct
3	Correct	8 ms	2808 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	10492 KB	Output is correct
2	Correct	115 ms	24924 KB	Output is correct
3	Correct	22 ms	4984 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	11256 KB	Output is correct
2	Correct	28 ms	5348 KB	Output is correct
3	Correct	129 ms	23940 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	7252 KB	Output is correct
2	Correct	122 ms	16304 KB	Output is correct
3	Correct	26 ms	6796 KB	Output is correct
4	Correct	59 ms	24868 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	8400 KB	Output is correct
2	Correct	27 ms	6904 KB	Output is correct
3	Correct	15 ms	5368 KB	Output is correct
4	Correct	59 ms	22904 KB	Output is correct