QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355633 | #5107. Mosaic Browsing | InfinityNS# | TL | 0ms | 0kb | C++14 | 5.2kb | 2024-03-17 00:29:28 | 2024-03-17 00:29:30 |
answer
#include<bits/stdc++.h>
#define ff first
#define pb push_back
#define ss second
#define ld long double
#define ll long long
using namespace std;
typedef pair<int,int> pii;
using f128=__float128;
using cd=complex<f128>;
namespace polynomial{
const ld PI=acos(-1);
const int maxn=(1<<21);
cd prekw[maxn];
bool isprek=0;
void prek(){
if(isprek)return;
isprek=1;
for(int i=0;i<maxn;i++){
ld angle=(2*PI)/maxn*i;
prekw[i]=cd(cos(angle),sin(angle));
}
}
void fft(vector<cd>&a,bool invert){
int n=a.size();
prek();
int j=0;
for(int i=1;i<n;i++){
int bit=n>>1;
for(;j&bit;bit>>=1)j^=bit;
j^=bit;
if(i<j)swap(a[i],a[j]);
}
for(int len=2;len<=n;len<<=1){
int hlen=len>>1;
for(int i=0;i<n;i+=len){
int curr=0;
int d=maxn/len;
if(invert)d=maxn-d;
for(int j=0;j<hlen;j++){
cd pom1=a[i+j];
cd pom2=prekw[curr]*a[i+j+hlen];
a[i+j]=pom1+pom2;
a[i+j+hlen]=pom1-pom2;
curr+=d;
if(curr>=maxn)curr-=maxn;
}
}
}
}
cd operator /(cd a,f128 n){
return cd(a.real()/n,a.imag()/n);
}
struct polyn{
vector<ll>a;
int size(){return a.size();}
void resize(int x){a.resize(x);}
ll& operator [](int x){
if(x>=a.size())a.resize(x+1);
return a[x];
}
polyn operator +(polyn b){
polyn ret=(*this);
for(int i=0;i<b.size();i++)ret[i]+=b[i];
return ret;
}
polyn operator -(polyn b){
polyn ret=(*this);
for(int i=0;i<b.size();i++)ret[i]-=b[i];
return ret;
}
polyn operator *(polyn b){
int n=1;
while(n<size()+b.size()-1)n<<=1;
vector<cd>fa(n),fb(n);
for(int i=0;i<a.size();i++)fa[i].real(a[i]);
for(int i=0;i<b.size();i++)fb[i].real(b[i]);
fft(fa,0);
fft(fb,0);
for(int i=0;i<n;i++)fa[i]=(fa[i]*fb[i])/((f128)n);
fft(fa,1);
polyn ret;
ret.resize(n);
for(int i=0;i<n;i++){
ret[i]=round((long double)fa[i].real());
}
return ret;
}
void ispis(){
for(int i=0;i<a.size();i++){
printf("%lld ",a[i]);
}
printf("\n");
}
};
}
using namespace polynomial;
const int mpn=1010;
int a[mpn][mpn],b[mpn][mpn],c[mpn][mpn];
int r1,r2,c1,c2;
polyn matchuj(polyn a,polyn b){
//a.ispis();
//b.ispis();
reverse(b.a.begin(),b.a.end());
polyn b3;
polyn ones;
for(int i=0;i<b.size();i++){
b3[i]=b[i]*b[i]*b[i];
ones[i]=1;
}
polyn a2;
for(int i=0;i<a.size();i++){
a2[i]=a[i]*a[i];
}
polyn b2;
for(int i=0;i<b.size();i++){
b2[i]=-2*b[i]*b[i];
}
//printf("POSL\n");
//(b*a2).ispis();
//(a*b2).ispis();
//(b3*ones).ispis();
return b*a2+a*b2+b3*ones;
}
int main(){
///freopen("test.txt","r",stdin);
/*polyn a,b;
a.a.pb(1);
a.a.pb(1);
b.a.pb(2);
b.a.pb(3);
b.a.pb(5);
a=a*b;
a.ispis();*/
scanf("%d %d",&r1,&c1);
int mnr=r1;
int mnc=c1;
for(int i=0;i<r1;i++){
for(int j=0;j<c1;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
mnr=min(mnr,i);
mnc=min(mnc,j);
}
}
}
for(int i=mnr;i<r1;i++){
for(int j=mnc;j<c1;j++){
c[i-mnr][j-mnc]=a[i][j];
}
}
int mxr=0;
int mxc=0;
for(int i=0;i<r1;i++){
for(int j=0;j<c1;j++){
if(c[i][j]){
mxr=max(mxr,i);
mxc=max(mxc,j);
}
}
}
r1=mxr+1;
c1=mxc+1;
scanf("%d %d",&r2,&c2);
for(int i=0;i<r2;i++){
for(int j=0;j<c2;j++){
scanf("%d",&b[i][j]);
}
}
if(r1>r2 || c1>c2){
printf("0\n");
return 0;
}
polyn bp,cp;
for(int i=0;i<r2;i++){
for(int j=0;j<c2;j++){
bp.a.pb(b[i][j]);
cp.a.pb(c[i][j]);
//printf("%d ",c[i][j]);
}
//printf("\n");
}
polyn pom=matchuj(bp,cp);
///pom.ispis();
vector<pii>rez;
int curr=-1;
int n=r2*c2;
for(int i=0;i<r2;i++){
for(int j=0;j<c2;j++){
curr++;
//printf("%d %d | %d %d AA\n",i,j,i+r1-1,j+c1-1);
if(i+r1-1>=r2 || j+c1-1>=c2)continue;
if(pom[curr+n-1]==0)rez.pb({i,j});
}
}
sort(rez.begin(),rez.end());
printf("%d\n",rez.size());
for(int i=0;i<rez.size();i++){
printf("%d %d\n",rez[i].ff+1,rez[i].ss+1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
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 ...