oj.uz

Submission #855012

# Submission time Handle Problem Language Result Execution time Memory
855012 2023-09-29T19:31:52 Z MilosMilutinovic Matching (CEOI11_mat) C++14
100 / 100
 669 ms 40636 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14876 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15120 KB Output is correct
2 Correct 10 ms 15376 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15228 KB Output is correct
2 Correct 11 ms 15116 KB Output is correct
3 Correct 4 ms 15048 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 16388 KB Output is correct
2 Correct 88 ms 18284 KB Output is correct
3 Correct 109 ms 19340 KB Output is correct
4 Correct 114 ms 19184 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19028 KB Output is correct
2 Correct 119 ms 19112 KB Output is correct
3 Correct 96 ms 19360 KB Output is correct
4 Correct 99 ms 21156 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19124 KB Output is correct
2 Correct 87 ms 18720 KB Output is correct
3 Correct 105 ms 18868 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 31932 KB Output is correct
2 Correct 520 ms 40404 KB Output is correct
3 Correct 432 ms 26580 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 33508 KB Output is correct
2 Correct 669 ms 25928 KB Output is correct
3 Correct 527 ms 36812 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 28220 KB Output is correct
2 Correct 514 ms 40636 KB Output is correct
3 Correct 566 ms 29092 KB Output is correct
4 Correct 350 ms 38460 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 28616 KB Output is correct
2 Correct 568 ms 29304 KB Output is correct
3 Correct 221 ms 23304 KB Output is correct
4 Correct 441 ms 38416 KB Output is correct