이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define baza 10000
#define MOD1 1000000007
#define MOD2 1000000013
using namespace std;
struct wow
{
long long first,second,nr;
}arb[4000005];
long long p1[1000005],p2[1000005],ceau[1000005];
void update (int st,int dr,int nod,int poz,int val)
{
if (st==dr)
{
arb[nod].first=arb[nod].second=val;
if (val==0)
{
arb[nod].nr=0;
}
else
{
arb[nod].nr=1;
}
return ;
}
int mij=(st+dr)/2;
if (poz<=mij)
{
update(st,mij,2*nod,poz,val);
}
else
{
update(mij+1,dr,2*nod+1,poz,val);
}
arb[nod].first=((arb[2*nod].first*p1[arb[2*nod+1].nr])%MOD1+arb[2*nod+1].first)%MOD1;
arb[nod].second=((arb[2*nod].second*p2[arb[2*nod+1].nr])%MOD2+arb[2*nod+1].second)%MOD2;
arb[nod].nr=arb[2*nod].nr+arb[2*nod+1].nr;
}
long long n,m,check1,check2,sum1,sum2,i,val1,val2,x;
pair <int,int> v[1000005];vector <int> sol;
int main()
{
#ifdef HOME
ifstream cin ("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>m>>n;
for (i=1;i<=m;i++)
{
cin>>x;
check1=(check1*baza+x)%MOD1;
check2=(check2*baza+x)%MOD2;
}
p1[0]=1;p2[0]=1;
for (i=1;i<=n;i++)
{
p1[i]=(p1[i-1]*baza)%MOD1;
p2[i]=(p2[i-1]*baza)%MOD2;
}
for (i=0;i<m;i++)
{
sum1=(sum1+p1[i])%MOD1;
sum2=(sum2+p2[i])%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++)
{
ceau[v[i].second]=i;
}
for (i=1;i<m;i++)
{
update(1,n,1,ceau[i],i);
}
for (i=m;i<=n;i++)
{
update(1,n,1,ceau[i],i);
val1=(arb[1].first-(sum1*(i-m))%MOD1+MOD1)%MOD1;
val2=(arb[1].second-(sum2*(i-m))%MOD2+MOD2)%MOD2;
if (val1==check1&&val2==check2)
{
sol.push_back(i-m+1);
}
update(1,n,1,ceau[i-m+1],0);
}
cout<<sol.size()<<'\n';
for (i=0;i<sol.size();i++)
{
cout<<sol[i]<<" ";
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
mat.cpp: In function 'int main()':
mat.cpp:93:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (i=0;i<sol.size();i++)
| ~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |