oj.uz

답안 #348200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348200 2021-01-14T10:59:54 Z algorithm16 Matching (CEOI11_mat) C++14
100 / 100
 1312 ms 58072 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int arr[1000005],ind[1000005],arr2[1000005],p1[1000005],t[2100005],p2[2100005],cnt2[2100005],cnt=1,off=1,p=31337;
vector <int> v,v2,sol;
void update(int x,int v,int 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;
	int 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

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

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1184 KB Output is correct
2 Correct 8 ms 1132 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1260 KB Output is correct
2 Correct 9 ms 1388 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 6888 KB Output is correct
2 Correct 71 ms 6632 KB Output is correct
3 Correct 135 ms 7528 KB Output is correct
4 Correct 135 ms 7528 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 7676 KB Output is correct
2 Correct 127 ms 6888 KB Output is correct
3 Correct 85 ms 7128 KB Output is correct
4 Correct 87 ms 9068 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 7784 KB Output is correct
2 Correct 77 ms 7400 KB Output is correct
3 Correct 101 ms 7108 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 37852 KB Output is correct
2 Correct 1312 ms 46988 KB Output is correct
3 Correct 552 ms 30320 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 524 ms 38492 KB Output is correct
2 Correct 816 ms 35548 KB Output is correct
3 Correct 1273 ms 56324 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 36828 KB Output is correct
2 Correct 440 ms 48280 KB Output is correct
3 Correct 714 ms 35932 KB Output is correct
4 Correct 544 ms 58072 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 481 ms 37668 KB Output is correct
2 Correct 741 ms 36888 KB Output is correct
3 Correct 217 ms 22116 KB Output is correct
4 Correct 659 ms 57424 KB Output is correct