QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385680 | #5102. Dungeon Crawler | SolitaryDream# | WA | 0ms | 6952kb | C++17 | 3.4kb | 2024-04-10 23:07:21 | 2024-04-10 23:07:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define double long double
using cpx=complex<double>;
#define int long long
const double pi=acos(-1);
const int N=5e3+1e2+7,P=998244353;
int qpow(int a,int b)
{
int ret=1;
while(b)
{
if(b&1)
ret=ret*a%P;
b>>=1;
a=a*a%P;
}
return ret;
}
int na,ma,nb,mb;
mt19937 rng(58);
int col[111],rev[N];
int w[N];
int a[N][N],b[N][N];
int tmp[N];
void dft(int *a,int len)
{
for(int i=1;i<len;i++)
if(i>rev[i])
swap(a[i],a[rev[i]]);
for(int d=1;d<len;d<<=1)
for(int m=d<<1,i=0;i<len;i+=m)
for(int j=0;j<d;j++)
{
int tmp=a[i+j+d]*w[len/m*j]%P;
a[i+j+d]=(a[i+j]-tmp)%P;
a[i+j]=(a[i+j]+tmp)%P;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=1;i<=100;i++)
{
int w;
int ok;
do {
w=rng()%P;
ok=1;
for(int j=0;j<i;j++)
if(w==col[j])
ok=0;
}while(ok==0);
col[i]=w;
}
int len=128;
for(int i=1;i<len;i++)
rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
w[0]=1;
for(int i=1;i<len;i++)
w[i]=qpow(3,(P-1)/i);
cin>>na>>ma;
int ha=0;
for(int i=0;i<na;i++)
for(int j=0;j<ma;j++)
{
int x;
cin>>x;
a[na-1-i][ma-1-j]=col[x];
ha+=col[x]*col[x];
ha%=P;
}
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
tmp[j]=a[i][j];
dft(tmp,len);
for(int j=0;j<len;j++)
a[i][j]=tmp[j];
}
for(int j=0;j<len;j++)
{
for(int i=0;i<len;i++)
tmp[i]=a[i][j];
dft(tmp,len);
for(int i=0;i<len;i++)
a[i][j]=tmp[i];
}
cin>>nb>>mb;
for(int i=1;i<=nb;i++)
for(int j=1;j<=mb;j++)
{
int x;
cin>>x;
b[i-1][j-1]=col[x];
}
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
tmp[j]=b[i][j];
dft(tmp,len);
for(int j=0;j<len;j++)
b[i][j]=tmp[j];
}
for(int j=0;j<len;j++)
{
for(int i=0;i<len;i++)
tmp[i]=b[i][j];
dft(tmp,len);
for(int i=0;i<len;i++)
b[i][j]=tmp[i];
}
for(int i=0;i<len;i++)
for(int j=0;j<len;j++)
a[i][j]=a[i][j]*b[i][j]%P;
int inv=qpow(len,P-2);
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
tmp[j]=a[i][j];
reverse(tmp,tmp+len);
dft(tmp,len);
for(int j=0;j<len;j++)
a[i][j]=tmp[j]*inv%P;
}
for(int j=0;j<len;j++)
{
for(int i=0;i<len;i++)
tmp[i]=a[i][j];
reverse(tmp,tmp+len);
dft(tmp,len);
for(int i=0;i<len;i++)
a[i][j]=tmp[i]*inv%P;
}
vector<pair<int,int> >ans;
for(int i=0;i<len;i++)
for(int j=0;j<len;j++)
{
int w=a[i][j];
w=(w%P+P)%P;
if(w==ha)
ans.push_back({i-na+1,j-nb+1});
}
cout<<ans.size()<<"\n";
for(auto [x,y]:ans)
cout<<x+1<<" "<<y+1<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 6952kb
input:
22 5 1 2 7 2 3 5 3 4 8 3 6 6 3 7 3 2 5 6 5 8 2 8 9 11 2 10 16 1 11 12 11 12 4 11 13 9 1 14 25 14 15 4 15 16 5 15 17 6 15 18 1 15 19 8 14 20 7 20 21 9 20 22 17 1 19 9 1 9 19 1 8 9 1 9 8 2 22 11
output:
0
result:
wrong answer 1st lines differ - expected: '316', found: '0'