QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385680#5102. Dungeon CrawlerSolitaryDream#WA 0ms6952kbC++173.4kb2024-04-10 23:07:212024-04-10 23:07:22

Judging History

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

  • [2024-04-10 23:07:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:6952kb
  • [2024-04-10 23:07:21]
  • 提交

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

详细

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'