QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355633#5107. Mosaic BrowsingInfinityNS#TL 0ms0kbC++145.2kb2024-03-17 00:29:282024-03-17 00:29:30

Judging History

你现在查看的是最新测评结果

  • [2024-03-17 00:29:30]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-03-17 00:29:28]
  • 提交

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;
}

详细

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
...

output:


result: