Submission #553432

#	Time	Username	Problem	Language	Result	Execution time	Memory
553432		AugustinasJucas	Matching (CEOI11_mat)	C++14	63 / 100	2096 ms	41060 KiB

mat

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
using namespace std;
int n, m;
vector<int> a, b;
const int mod = 1e9 + 7;
const long long maxN = 1000000 ;
const int dydis = 1e6 + 10;
vector<long long> pw;
struct treap {
	int dbInd = 0;
	vector<int> l, r, w;
	vector<int> val, myInd, sz;
	vector<int> subHash;
	int rt = -1;
	treap() {
		pw.resize(dydis);
		l.resize(dydis);
		r.resize(dydis);
		w.resize(dydis);
		val.resize(dydis);
		myInd.resize(dydis);
		subHash.resize(dydis);
		sz.resize(dydis);
		
		pw[0] = 1;
		for(int i = 1; i < dydis; i++) {
			pw[i] = 1ll * pw[i-1] * maxN % mod;
		}
	}
	int newN(int Val, int Ind){
		l[dbInd] = r[dbInd] = -1;
		w[dbInd] = rand();
		val[dbInd] = Val;
		myInd[dbInd] = Ind;
		subHash[dbInd] = Ind;
		sz[dbInd] = 1;
		return dbInd++;
	}
	int hMerge(int h1, int h2, int sz2){
		int ret = h1;
		ret = 1ll * ret * pw[sz2] % mod;
		ret = (ret + h2) % mod;
		return ret;
	}
	void upd(int v){
		int hashL = 0, hashR = 0, hashMid;
		int lsz = 0; int rsz = 0;
		if(l[v] != -1) {
			hashL = subHash[l[v]];
			lsz = sz[l[v]];
		}
		if(r[v] != -1) {
			hashR = subHash[r[v]];
			rsz = sz[r[v]];
		}
		hashMid = myInd[v];
		sz[v] = lsz + 1 + rsz;
		subHash[v] = (1ll*hashL * maxN%mod + hashMid)%mod;
		subHash[v] = hMerge(subHash[v], hashR, rsz);
	}
	pair<int, int> split(int v, int vl) {
		if(v == -1) return {-1, -1};
		if(val[v] < vl) { 	// as kaireje puseje
			auto ds = split(r[v], vl);
			r[v] = ds.first;
			upd(v);
			return {v, ds.second};
		}else { 			// as desineje puseje
			auto kr = split(l[v], vl);
			l[v] = kr.second;
			upd(v);
			return {kr.first, v};
		}
	}
	int merge(int L, int R) {
		if(R == -1) return L;
		if(L == -1) return R;
		if(w[L] > w[R]) {
			int mr = merge(r[L], R);
			r[L] = mr;
			upd(L);
			return L;
		}else {
			int mr = merge(L, l[R]);
			l[R] = mr;
			upd(R);
			return R;
		}
	}
	void print(int v = -2){
		if(v == -2) v = rt;
		if(v == -1) return ;
		print(l[v]);
		cout << "(val=" << val[v] << ", ind=" << myInd[v] << ")  ";
		print(r[v]); 
	}
	void insert(int val, int ind) {
		int nd = newN(val, ind);
		auto prm = split(rt, val); 
		prm.first = merge(prm.first, nd);
		rt = merge(prm.first, prm.second);
	//	cout << "rt tampa " << rt << endl;
	}
	void erase(int val) {
		auto prm = split(rt, val+1);
		auto ant = split(prm.first, val);
		rt = merge(ant.first, prm.second);
	}
	int getHash() {
		return subHash[rt];
	}
};
 
treap medis;
int main () {
	srand(time(0));
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	/*int sk = 5;
	int indd = 0;
	while(sk--) {
		int val, ind;
		cin >> val ;
		medis.insert(val, indd++);
		medis.print();
		cout << ", bendras hashas = " << medis.getHash();
		cout << endl;
	}
	sk = 5;
	while(sk--) {
		int val, ind;
		cin >> val;
		medis.erase(val, 0);
		medis.print();
		//cout << ", bendras hashas = " << medis.getHash();
		//cout << endl;
	}*/
	
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}
	for(auto &x : b) {
		cin >> x;
	} 	
	long long reikia = 0;
	for(auto x : a) {
		reikia = (1ll * reikia * maxN % mod + x) % mod;
	}
	//cout << "reikia = " << reikia << endl;
	for(int i = 0; i < n; i++) {
		medis.insert(b[i], i);
	}
	long long turi = 0;
	for(int i = 0; i < n; i++) {
		turi = (turi + pw[i]) % mod;
	}
	vector<int> ans;
	if(medis.getHash() == reikia) {
		ans.push_back(0);
	}
	for(int i = n; i < m; i++) {
		medis.erase(b[i-n]);
		medis.insert(b[i], i);
		int hsh = ((medis.getHash() - 1ll * (i-n+1) * turi % mod) % mod + mod) % mod;
		if(reikia == hsh) {
			ans.push_back(i-n+1);
		}
	//	cout << "nuo " << i << ", hsh = " << hsh << endl;
	}
	cout << ans.size() << "\n";
	for(auto &x : ans) {
		cout << x+1 << " ";
	}
	return 0;
}
/*
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
 
2 5
1 2
1 2 3 4 5 
*/

• 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10