QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385691 | #5107. Mosaic Browsing | SolitaryDream# | WA | 526ms | 99212kb | C++17 | 3.4kb | 2024-04-10 23:17:14 | 2024-04-10 23:17:15 |
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=2048;
for(int i=1;i<len;i++)
rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
w[0]=1;
w[1]=qpow(3,(P-1)/len);
for(int i=2;i<len;i++)
w[i]=w[i-1]*w[1]%P;
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+1,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+1,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=na-1;i<=nb-na+1;i++)
for(int j=ma-1;j<=mb-ma+1;j++)
{
int w=a[i][j];
w=(w%P+P)%P;
if(w==ha)
ans.push_back({i-na+1,j-ma+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: 526ms
memory: 99212kb
input:
100 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
1212 1 1 1 101 1 201 1 301 2 1 2 101 2 201 2 301 3 1 3 101 3 201 3 301 4 1 4 101 4 201 4 301 5 1 5 101 5 201 5 301 6 1 6 101 6 201 6 301 7 1 7 101 7 201 7 301 8 1 8 101 8 201 8 301 9 1 9 101 9 201 9 301 10 1 10 101 10 201 10 301 11 1 11 101 11 201 11 301 12 1 12 101 12 201 12 301 13 1 13 101 13 201 ...
result:
wrong answer 1st lines differ - expected: '2005', found: '1212'