Submission #772299

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
772299	2023-07-03T23:23:53 Z	NK_	Matching (CEOI11_mat)	C++17	100 / 100	617 ms	45108 KB

	// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back

// using ll = long long;
template<class T> using V = vector<T>;


const int MOD1 = int(1e9)+7;
// const int MOD2 = 998244353;
const int base = int(1e6) + 1007;

const int nax = (1 << 20);

int POW1[nax], A[nax], B[nax];
// int POW2[nax];

struct T {
	int H1,/* H2,*/ len;
	bool operator==(const T &a) {
		return a.H1 == H1/* && a.H2 == H2*/;
	};	
};

T c;
T comb(const T &a, const T &b) { 
	c = a; c.len += b.len;
	c.H1 = ((a.H1 * 1LL * POW1[b.len]) + b.H1) % MOD1;
	// c.H2 = ((a.H2 * 1LL * POW2[b.len]) + b.H2) % MOD2;
	return c;
}

// SEGTREE
T seg[2*nax];
void pull(const int &x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }
void upd(int p, const T &v) { seg[p += nax] = v; for(p /= 2; p; p /= 2) pull(p); }
T get() { return seg[1]; }

int main() {
	cin.tie(0)->sync_with_stdio(0);
		

	for(int t = 0; t < 2*nax; t++) seg[t] = T{0, 0};

	int N, M; cin >> N >> M;

	for(int i = 0; i < N; i++) { cin >> A[i]; --A[i]; }
	for(int i = 0; i < M; i++) { cin >> B[i]; POW1[i] = B[i]; }

	sort(POW1, POW1 + M);
	for(int i = 0; i < M; i++) {
		B[i] = lower_bound(POW1, POW1 + M, B[i]) - POW1;
	}

	// PRE-COMPUTE
	POW1[0] = 1;
	// POW2[0] = 1;
	for(int t = 1; t < nax; t++) {
		POW1[t] = (POW1[t - 1] * 1LL * base) % MOD1;
		// POW2[t] = (POW2[t - 1] * 1LL * base) % MOD2;
	}


	T H = T{0, 0}, R = T{0, 0}, REM = T{0, 0}; 
	for(int i = 0; i < N; i++) {
		H = comb(H, T{A[i] + 1, 1});
		R = comb(R, T{1, 1});
	}

	V<int> ans;
	for(int i = 0; i < N; i++) upd(B[i], T{i + 1, 1});

	auto check = [&](int i) {
		T res = get(); 

		if ((res.H1 -= REM.H1) < 0) res.H1 += MOD1;
		// if ((res.H2 -= REM.H2) < 0) res.H2 += MOD2;

		if (res == H) ans.push_back(i);
	};

	check(0);

	for(int i = N; i < M; i++) {
		if ((REM.H1 += R.H1) >= MOD1) REM.H1 -= MOD1;
		// if ((REM.H2 += R.H2) >= MOD2) REM.H2 -= MOD2;

		upd(B[i], T{i + 1, 1});
		upd(B[i - N], T{0, 0});

		check(i - N + 1);
	}

	cout << sz(ans) << nl;
	for(auto& x : ans) cout << x+1 << " ";
	cout << nl;

    return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	20812 KB	Output is correct
2	Correct	14 ms	20732 KB	Output is correct
3	Correct	13 ms	20780 KB	Output is correct
4	Correct	13 ms	20820 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	20820 KB	Output is correct
2	Correct	13 ms	20820 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	20876 KB	Output is correct
2	Correct	20 ms	20876 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	20948 KB	Output is correct
2	Correct	22 ms	20944 KB	Output is correct
3	Correct	15 ms	20812 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	21616 KB	Output is correct
2	Correct	93 ms	21612 KB	Output is correct
3	Correct	117 ms	21752 KB	Output is correct
4	Correct	125 ms	21748 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	22220 KB	Output is correct
2	Correct	121 ms	21524 KB	Output is correct
3	Correct	100 ms	21984 KB	Output is correct
4	Correct	100 ms	23748 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	22196 KB	Output is correct
2	Correct	92 ms	21780 KB	Output is correct
3	Correct	110 ms	21704 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	513 ms	36224 KB	Output is correct
2	Correct	580 ms	45108 KB	Output is correct
3	Correct	422 ms	31544 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	461 ms	35808 KB	Output is correct
2	Correct	617 ms	31556 KB	Output is correct
3	Correct	553 ms	41488 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	504 ms	33832 KB	Output is correct
2	Correct	454 ms	42352 KB	Output is correct
3	Correct	547 ms	34768 KB	Output is correct
4	Correct	380 ms	42980 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	459 ms	34448 KB	Output is correct
2	Correct	549 ms	35168 KB	Output is correct
3	Correct	218 ms	27368 KB	Output is correct
4	Correct	447 ms	43208 KB	Output is correct

Submission #772299

Compilation message