Submission #348195

#	Time	Username	Problem	Language	Result	Execution time	Memory
348195		algorithm16	Matching (CEOI11_mat)	C++14	63 / 100	562 ms	65540 KiB

mat

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint arr[1000005],ind[1000005],arr2[1000005],p1[1000005],t[2200005],p2[2200005],cnt2[2200005],cnt=1,off=1,p=31337;
vector <llint> v,v2,sol;
void update(int x,llint v,llint c) {
	p2[off+x]=v;
	cnt2[off+x]=c;
	//if(x==3) cout << p2[off+x] << " " << cnt2[off+x] << " " << v << " " << c << "\n";
	for(int i=(off+x)/2;i>=1;i/=2) {
		t[i]=t[i*2]+t[i*2+1];
		p2[i]=p2[i*2]+p2[i*2+1];
		cnt2[i]=cnt2[i*2]+cnt2[i*2+1];
		//if(x==3) cout << t[i] << " " << cnt2[x*2] << " " << p2[x*2+1] << "\n";
		//if(x==3) i*2 << " " << i*2+1 << "\n";
		t[i]+=cnt2[i*2]*p2[i*2+1];
		//if(x==3) cout << t[i] << "\n";
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	while(off<m) off*=2;
	llint h=0,h2=0;
	for(int i=0;i<n;i++) {
		cin >> arr[i];
		ind[arr[i]]=i;
	}
	for(int i=0;i<n;i++) {
		h*=p;
		h+=ind[i+1];
	}
	for(int i=0;i<m;i++) {
		cin >> arr2[i];
		v.push_back(arr2[i]);
	}
	p1[0]=1;
	for(int i=1;i<=m;i++) {
		p1[i]=p1[i-1]*p;
	}
	sort(v.begin(),v.end());
	for(int i=0;i<m;i++) {
		arr2[i]=lower_bound(v.begin(),v.end(),arr2[i])-v.begin()+1;
		if(i<n) v2.push_back(arr2[i]);
	}
	sort(v2.begin(),v2.end());
	for(int i=0;i<n;i++) {
		h2*=p;
		h2+=lower_bound(v2.begin(),v2.end(),arr2[i])-v2.begin()+1;
		update(arr2[i]-1,p1[m-1-i],1);
		//cout << arr2[i]-1 << " " << p1[m-1-i] << " " << t[1] << "\n";
	}
	//cout << "\n";
	/*for(int i=0;i<n;i++) {
		cout << ind[i+1] << " ";
	}
	cout << "\n";
	for(int i=0;i<m;i++) {
		cout << arr2[i] << " ";
	}
	cout << "\n";*/
	//cout << h << " " << h2 << "\n";
	//cout << (lower_bound(v2.begin(),v2.end(),arr2[0])-v2.begin()+1)*p1[n] << " " << h2 << "\n";
	//cout << t[1] << "\n";
	//cout << h << "\n";
	for(int i=0;i+n-1<m;i++) {
		if(h*p1[m-n-i]==t[1]) sol.push_back(i+1);
		update(arr2[i]-1,0,0);
		update(arr2[i+n]-1,p1[m-n-i-1],1);
		//cout << arr2[i]-1 << " " << arr2[i+n]-1 << " " << p1[m-n-i-1] << "\n";
		//cout << t[1] << "\n";
		
	}
	cout << sol.size() << "\n";
	for(int i=0;i<sol.size();i++) {
		cout << sol[i] << " ";
	}
	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i=0;i<sol.size();i++) {
      |              ~^~~~~~~~~~~

• 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