QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355634#5107. Mosaic BrowsingInfinityNS#WA 1109ms223112kbC++145.2kb2024-03-17 00:31:122024-03-17 00:31:13

Judging History

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

  • [2024-03-17 00:31:13]
  • 评测
  • 测评结果:WA
  • 用时:1109ms
  • 内存:223112kb
  • [2024-03-17 00:31:12]
  • 提交

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 cd=complex<long double>;

namespace polynomial{


    const ld PI=acos(-1);
    const int maxn=(1<<22);
    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,ld 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])/n;

            fft(fa,1);

            polyn ret;
            ret.resize(n);
            for(int i=0;i<n;i++){
                ret[i]=round(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: 100
Accepted
time: 1103ms
memory: 217708kb

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:

2005
1 1
1 101
1 201
1 301
1 401
2 1
2 101
2 201
2 301
2 401
3 1
3 101
3 201
3 301
3 401
4 1
4 101
4 201
4 301
4 401
5 1
5 101
5 201
5 301
5 401
6 1
6 101
6 201
6 301
6 401
7 1
7 101
7 201
7 301
7 401
8 1
8 101
8 201
8 301
8 401
9 1
9 101
9 201
9 301
9 401
10 1
10 101
10 201
10 301
10 401
11 1
11 10...

result:

ok 2006 lines

Test #2:

score: 0
Accepted
time: 1109ms
memory: 218288kb

input:

250 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:

1255
1 1
1 101
1 201
1 301
1 401
2 1
2 101
2 201
2 301
2 401
3 1
3 101
3 201
3 301
3 401
4 1
4 101
4 201
4 301
4 401
5 1
5 101
5 201
5 301
5 401
6 1
6 101
6 201
6 301
6 401
7 1
7 101
7 201
7 301
7 401
8 1
8 101
8 201
8 301
8 401
9 1
9 101
9 201
9 301
9 401
10 1
10 101
10 201
10 301
10 401
11 1
11 10...

result:

ok 1256 lines

Test #3:

score: 0
Accepted
time: 1088ms
memory: 223112kb

input:

500 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:

5
1 1
1 101
1 201
1 301
1 401

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 200ms
memory: 139268kb

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 188ms
memory: 138980kb

input:

1 1
2
2 4
1 1 2 2
1 3 2 3

output:

3
1 3
1 4
2 3

result:

ok 4 lines

Test #6:

score: 0
Accepted
time: 191ms
memory: 138948kb

input:

1 1
1
4 1
1
4
2
6

output:

1
1 1

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 180ms
memory: 138956kb

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #8:

score: 0
Accepted
time: 194ms
memory: 138988kb

input:

2 2
1 3
0 0
1 3
1 2 3

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 1ms
memory: 7860kb

input:

1 4
4 4 4 1
1 1
2

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 192ms
memory: 138992kb

input:

1 1
0
6 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

output:

24
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4

result:

ok 25 lines

Test #11:

score: 0
Accepted
time: 188ms
memory: 138952kb

input:

1 1
2
1 5
3 2 3 3 2

output:

2
1 2
1 5

result:

ok 3 lines

Test #12:

score: 0
Accepted
time: 200ms
memory: 138924kb

input:

1 1
3
2 8
7 2 6 3 7 2 5 3
1 5 3 4 1 3 3 6

output:

5
1 4
1 8
2 3
2 6
2 7

result:

ok 6 lines

Test #13:

score: 0
Accepted
time: 0ms
memory: 7784kb

input:

2 3
1 1 0
1 1 0
1 7
1 1 1 1 1 1 1

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 174ms
memory: 139268kb

input:

2 2
0 1
2 2
9 3
2 3 2
1 1 1
1 3 2
1 1 1
1 2 2
3 3 3
1 1 3
1 3 3
1 3 1

output:

1
4 2

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 192ms
memory: 139264kb

input:

1 1
2
4 3
5 6 5
3 2 4
1 2 4
7 3 5

output:

2
2 2
3 2

result:

ok 3 lines

Test #16:

score: 0
Accepted
time: 0ms
memory: 7832kb

input:

5 4
1 0 1 1
0 0 1 0
1 0 0 1
1 0 0 0
0 0 1 1
3 1
1
1
1

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 1ms
memory: 7912kb

input:

4 2
3 0
0 0
1 2
3 2
1 4
1 1 1 2

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 1ms
memory: 7876kb

input:

8 8
0 2 3 6 5 3 5 2
6 5 6 5 3 2 0 5
2 1 5 3 0 0 4 2
2 0 7 2 3 5 3 7
5 1 4 6 0 5 6 7
3 0 1 0 5 4 5 7
3 4 6 1 5 3 3 1
3 6 7 3 6 1 5 5
4 4
7 7 3 7
2 4 5 3
6 3 1 1
3 7 2 1

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 192ms
memory: 138972kb

input:

1 1
61
4 1
52
48
40
46

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 225ms
memory: 140824kb

input:

1 1
1
95 86
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

8170
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

result:

ok 8171 lines

Test #21:

score: 0
Accepted
time: 161ms
memory: 139132kb

input:

1 1
2
6 96
3 2 1 2 1 1 3 2 1 2 2 3 1 3 3 3 3 2 2 1 1 2 2 3 2 1 1 2 2 1 1 3 1 3 1 3 2 3 3 1 3 2 3 3 3 3 3 1 1 1 2 2 3 2 3 3 3 1 3 3 2 1 1 1 1 2 2 2 1 2 2 3 2 1 3 2 1 3 3 3 3 2 3 1 1 3 2 2 2 2 1 2 2 2 1 1
1 2 3 2 2 3 2 2 3 1 2 2 3 3 2 3 2 1 1 1 3 1 3 3 3 2 3 2 3 3 3 3 1 1 3 2 2 1 3 1 1 3 1 1 3 2 1 3 3...

output:

191
1 2
1 4
1 8
1 10
1 11
1 18
1 19
1 22
1 23
1 25
1 28
1 29
1 37
1 42
1 51
1 52
1 54
1 61
1 66
1 67
1 68
1 70
1 71
1 73
1 76
1 82
1 87
1 88
1 89
1 90
1 92
1 93
1 94
2 2
2 4
2 5
2 7
2 8
2 11
2 12
2 15
2 17
2 26
2 28
2 36
2 37
2 46
2 54
2 60
2 61
2 62
2 64
2 66
2 70
2 75
2 76
2 80
2 81
2 84
2 86
2 87...

result:

ok 192 lines

Test #22:

score: 0
Accepted
time: 206ms
memory: 139224kb

input:

1 1
6
80 23
5 3 7 7 4 5 3 3 7 6 3 3 6 1 4 6 5 7 2 6 2 5 6
2 1 4 5 1 6 6 2 1 1 5 1 1 3 5 6 5 7 4 7 4 4 2
7 1 5 1 2 1 1 4 3 3 4 3 2 1 6 1 1 6 7 5 4 7 1
7 4 6 3 7 7 2 5 1 7 5 3 4 3 6 2 2 2 3 3 1 2 5
7 7 4 5 7 7 5 1 2 2 6 6 4 6 1 2 4 1 5 6 1 7 4
3 1 3 2 5 3 1 7 2 6 4 2 2 6 5 4 2 1 5 1 3 6 7
1 3 6 7 4 4 ...

output:

277
1 10
1 13
1 16
1 20
1 23
2 6
2 7
2 16
3 15
3 18
4 3
4 15
5 11
5 12
5 14
5 20
6 10
6 14
6 22
7 3
7 8
7 12
7 14
7 16
8 13
8 23
9 1
9 3
9 14
9 21
10 3
10 12
10 14
10 15
10 21
11 1
11 5
11 9
11 13
11 20
12 9
12 18
13 7
13 8
13 12
13 18
13 19
13 21
14 16
14 19
15 5
15 14
17 2
17 12
17 19
17 23
18 4
1...

result:

ok 278 lines

Test #23:

score: 0
Accepted
time: 1ms
memory: 7824kb

input:

1 3
94 82 89
4 2
32 23
91 15
19 42
54 45

output:

0

result:

ok single line: '0'

Test #24:

score: -100
Wrong Answer
time: 210ms
memory: 140704kb

input:

1 4
0 0 1 0
65 88
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

5720
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

result:

wrong answer 1st lines differ - expected: '5525', found: '5720'