Submission #347946

#	Time	Username	Problem	Language	Result	Execution time	Memory
347946		lovro_nidogon1	Matching (CEOI11_mat)	C++14	0 / 100	159 ms	13548 KiB

mat

#include<bits/stdc++.h>
#define breturn return
#define ll long long
using namespace std;
const ll b = 31337;
const ll mod = 1e9 + 7;
ll n, m,bn,  arr[1000001], a, pb[20000001], che[1000001], chash, rhash, tour[40000001], laz[40000001], bre, act[40000001], cnt;
vector<pair<ll, ll> > perm;
vector<ll> odg;
map<ll, ll> maph;

ll mul(ll x, ll y) {
	breturn (x * y)%mod;
}

ll ad(ll x, ll y) {
	if(x + y >= mod) breturn x + y - mod;
	else if(x + y < 0) breturn x + y + mod; 
}

ll quer(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) {
	if(l > bx or r < ax) breturn 0;
	if(l >= ax and r <= bx) breturn tour[x];
	ll mid = (l + r)/2;
	breturn ad(quer(ax, bx, x * 2, l, mid), quer(ax, bx, x * 2 + 1, mid + 1, r));
}

ll smol(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) {
	if(l > bx or r < ax) breturn 0;
	if(l >= ax and r <= bx) breturn act[x];
	ll mid = (l + r)/2;
	breturn smol(ax, bx, x * 2, l, mid) + smol(ax, bx, x * 2 + 1, mid + 1, r);
} 

ll bp(ll p, ll x) {
	if(x == 0) breturn 1;
	if(x%2) breturn mul(bp(p, x - 1), p);
	ll xx = bp(p, x/2);
	breturn mul(xx, xx);
	
} 


int main() {
	cin >> n >> m;
	bn = (1 << ((int)log2(m - 1) + 1));
	pb[0] = 1;
	for(int i = 0; i < n; i++) {
		cin >> a;
		arr[a - 1] = i + 1;
	}
	for(int i = 0; i < bn; i++)	if(i) pb[i] = mul(pb[i - 1], b);
//	cout << ad(mul(pb[4], 0), ad(mul(pb[3], 1), ad(mul(pb[2], 0), ad(mul(pb[1], 1), mul(pb[0], 1))))) << '\n';
	for(int i = 0; i < n; i++) {
		chash = mul(chash, b);
		chash = ad(chash, arr[i]);
//		cout << arr[i] << ":";
//		cout << mul(arr[i], pb[n - 1 - i]) << " ";
	}
//	cout << '\n';
//	cout << chash << '\n';
	for(int i = 0; i < m; i++) {
		cin >> arr[i];
		perm.push_back({arr[i], i});
	}
	sort(perm.begin(), perm.end());
	for(int i = 0; i < perm.size(); i++) maph[perm[i].first] = i;
	perm.clear();
	for(int i = 0; i < n; i++) {
		perm.push_back({arr[i], i});
	}
	sort(perm.begin(), perm.end());
	for(int i = 0; i < n; i++) {
		che[perm[i].second] = i + 1;
	}
	for(int i = 0; i < n; i++) {
		rhash = mul(rhash, b);
		rhash = ad(rhash, che[i]);
		tour[maph[arr[i]] + bn] = pb[n - i - 1];
		act[maph[arr[i]] + bn] = 1;
	}
	for(int i = bn - 1; i > 0; i--) tour[i] = ad(tour[i * 2], tour[i * 2 +1]), act[i] = act[i * 2] + act[i * 2 + 1];
//	cout << '\n';
//	cout << rhash << '\n';
	if(rhash == chash) odg.push_back(1);
	for(int i = n; i < m; i++) {		

//		for(int i = 1; i < 2 * bn; i++) cout << tour[i] << ":";
//		cout << '\n';
		ll x = maph[arr[i - n]];
//		cout << "Oduzimam hashu " << smol(0, x) << " pomnožen bazom na " << n - 1 << '\n';   
		rhash = ad(rhash, -mul(smol(0, x), pb[n - 1]));
//		cout << "Oduzimam hashu " << quer(x + 1, bn - 1) << " pomnožen bazom na " << cnt << '\n';
		rhash = ad(rhash, -mul(quer(x + 1, bn - 1), pb[cnt]));
		x += bn;
		act[x] = 0;
		tour[x] = 0;
		x /= 2;
		while(x) act[x] = act[x * 2] + act[x * 2 + 1], tour[x] = ad(tour[x * 2], tour[x * 2 + 1]), x /= 2;
		x = maph[arr[i]];		
//		cout << "Dodajem hashu " << quer(x + 1, bn) << " pomnožen bazom na " << cnt << '\n';
 		rhash = ad(rhash, mul(quer(x + 1, bn - 1), pb[cnt]));	
		cnt ++;	
//		cout<<  "Množim cijeli hash bazom\n";
		rhash = mul(rhash, b);		
//		for(int i = 1; i < 2 * bn; i++) cout << act[i] << ".";
//		cout << '\n';
//		cout << "Dodajem hashu " << smol(0, x) + 1 << " " << x << '\n';
		rhash = ad(rhash, smol(0, x) + 1);
		x += bn;
		act[x] = 1;
	//	cout << "BTW, ovo kaj si dodao je potencirano baza na " << -cnt << '\n';
	//	cout << mul(pb[cnt], bp(b, mod - 1 - cnt)) << " " << bp(b, cnt) << '\n'; 
		tour[x] = bp(pb[cnt], mod - 2);
		x /= 2;
		while(x) act[x] = act[x * 2] + act[x * 2 + 1], tour[x] = ad(tour[x * 2], tour[x * 2 + 1]), x /= 2;
		//rhash = ad(rhash, tour[1]);
		
//		cout << rhash << " <-> " << chash << '\n';	
		if(rhash == chash) odg.push_back(i - n + 2);
//		cout << '\n';						
	}
//	for(int i = 1; i < 2 * bn; i++) cout << tour[i] << " ";
//	cout << '\n';
	cout << odg.size() << '\n';
	for(int i = 0; i < odg.size(); i++) cout << odg[i] << " ";
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < perm.size(); i++) maph[perm[i].first] = i;
      |                 ~~^~~~~~~~~~~~~
mat.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |  for(int i = 0; i < odg.size(); i++) cout << odg[i] << " ";
      |                 ~~^~~~~~~~~~~~
mat.cpp: In function 'long long int ad(long long int, long long int)':
mat.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10