Submission #855012

#	Time	Username	Problem	Language	Result	Execution time	Memory
855012		MilosMilutinovic	Matching (CEOI11_mat)	C++14	100 / 100	669 ms	40636 KiB

mat

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int B=77777;
const int md=1e9+7;

int ckmul(int a,int b){return (ll)a*b%md;}
int ckadd(int a,int b){return a+b>=md?a+b-md:a+b;}
int cksub(int a,int b){return a>=b?a-b:a-b+md;}
int qpow(int a,int b){int r=1;while(b){if(b&1)r=ckmul(r,a);a=ckmul(a,a);b>>=1;}return r;}
int ckdiv(int a,int b){return ckmul(a,qpow(b,md-2));}

int n,m,p[1000005],a[1000005],pw[1000005],pp[1000005];

void compress(){
	vector<int> xs;
	for(int i=1;i<=m;i++) xs.pb(a[i]);
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for(int i=1;i<=m;i++) a[i]=(int)(lower_bound(xs.begin(),xs.end(),a[i])-xs.begin())+1;
}

namespace cnt{
	int fenw[1000005];
	void clr(){for(int i=0;i<1000005;i++)fenw[i]=0;}
	void upd(int p,int v){for(;p<1000005;p+=p&-p)fenw[p]+=v;}
	int get(int p){int r=0;for(;p>0;p-=p&-p)r+=fenw[p];return r;}
	int get(int l,int r){if(l>r)return 0;return get(r)-get(l-1);}
};

namespace sum{
	int fenw[1000005];
	void clr(){for(int i=0;i<1000005;i++)fenw[i]=0;}
	void upd(int p,int v){for(;p<1000005;p+=p&-p)fenw[p]=ckadd(fenw[p],v);}
	int get(int p){int r=0;for(;p>0;p-=p&-p)r=ckadd(r,fenw[p]);return r;}
	int get(int l,int r){if(l>r)return 0;return cksub(get(r),get(l-1));}
}

int main(){
	n=readint(); m=readint();
	for(int i=1;i<=n;i++) p[i]=readint();
	for(int i=1;i<=m;i++) a[i]=readint();
	for(int i=1;i<=n;i++) pp[p[i]]=i;
	for(int i=1;i<=n;i++) p[i]=pp[i];
	compress();
	pw[0]=1;
	for(int i=1;i<=m;i++) pw[i]=ckmul(pw[i-1],B),assert(pw[i]==qpow(B,i));
	ll hsh=0;
	for(int i=1;i<=n;i++){
		hsh=ckadd(hsh,sum::get(p[i],n));
		cnt::upd(p[i],1);
		sum::upd(p[i],pw[i]);
	}
	cnt::clr(); sum::clr();
	ll cur=0;
	for(int i=1;i<=n;i++){
		cur=ckadd(cur,sum::get(a[i],m));
		cnt::upd(a[i],1);
		sum::upd(a[i],pw[i]);
	} 
	vector<int> res;
	if(hsh==cur) res.pb(1);
	for(int i=n+1;i<=m;i++){
		cur=cksub(cur,ckmul(pw[i-n],cnt::get(1,a[i-n]-1)));
		cnt::upd(a[i-n],-1);
		sum::upd(a[i-n],cksub(0,pw[i-n]));
		cur=ckadd(cur,sum::get(a[i],m));
		cnt::upd(a[i],1);
		sum::upd(a[i],pw[i]);
		if(ckdiv(cur,pw[i-n])==hsh) res.pb(i-n+1);
	}
	printf("%d\n",res.size());
	for(int i=0;i<res.size();i++) printf("%d ",res[i]);
	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:88:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   88 |  printf("%d\n",res.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld
mat.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i=0;i<res.size();i++) printf("%d ",res[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: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10