# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
739490 | jelly1010 | Matching (CEOI11_mat) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define maxi(a, b) a = max(a, b)
#define mize(a, b) a = min(a, b)
#define getbit(a, i) ((a) >> (i) & 1)
#define FOR(i, a, b) for(int i=a, _n=b; i<=_n; ++i)
#define FORD(i, a, b) for(int i=a, _n=b; i>=_n; --i)
#define REP(i, _n) for(int i=0; i<_n; ++i)
#define sz(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
#define ii pair<int, int>
using namespace std;
typedef long long hash_type;
const int DIM = 2e5+5;
const hash_type MOD1 = 1e9+7;
const hash_type MOD2 = 1e9+7;
const base=1e4;
struct segment_tree{
int hash1,hash2;
int cnt;
} aint[DIM*4];
pair <int,int> v[DIM];
int nrm[DIM];
int p1[DIM],p2[DIM];
vector <int> sol;
int n,m,i,j,x;
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
aint[nod].hash1 = aint[nod].hash2 = val;
if (val)
aint[nod].cnt = 1;
else aint[nod].cnt = 0;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[nod].hash1 = (1LL * aint[fiu_st].hash1 * p1[ aint[fiu_dr].cnt ] % MOD1 + aint[fiu_dr].hash1) % MOD1;
aint[nod].hash2 = (1LL * aint[fiu_st].hash2 * p2[ aint[fiu_dr].cnt ] % MOD2 + aint[fiu_dr].hash2) % MOD2;
aint[nod].cnt = aint[fiu_st].cnt + aint[fiu_dr].cnt;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>m>>n;
int hash1 = 0, hash2 = 0;
for (i=1;i<=m;i++){
cin>>x;
hash1 = (1LL * hash1 * B % MOD1 + x) % MOD1;
hash2 = (1LL * hash2 * B % MOD2 + x) % MOD2;
}
p1[0] = p2[0] = 1;
for (i=1;i<=n;i++){
p1[i] = 1LL * p1[i-1] * B % MOD1;
p2[i] = 1LL * p2[i-1] * B % MOD2;
}
for (i=1;i<=n;i++){
cin>>v[i].first;
v[i].second = i;
}
sort (v+1,v+n+1);
for (i=1;i<=n;i++)
nrm[v[i].second] = i;
for (i=1;i<m;i++)
update (1,1,n,nrm[i],i);
int sum1 = 0, sum2 = 0;
for (i=0;i<m;i++){
sum1 = (sum1 + p1[i]) % MOD1;
sum2 = (sum2 + p2[i]) % MOD2;
}
for (i=m;i<=n;i++){
/// adaug elem asta
update (1,1,n,nrm[i],i);
int val1 = (aint[1].hash1 - 1LL * sum1 * (i-m) % MOD1 + MOD1) % MOD1;
int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2;
if (val1 == hash1)
sol.push_back(i-m+1);
/// sterg i-m+1
update (1,1,n,nrm[i-m+1],0);
}
cout<<sol.size()<<"\n";
for (auto it : sol)
cout<<it<<" ";
return 0;
}
//Jelly1010