QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385666#5102. Dungeon CrawlerSolitaryDream#WA 0ms9356kbC++173.1kb2024-04-10 22:51:322024-04-10 22:51:32

Judging History

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

  • [2024-04-10 22:51:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9356kb
  • [2024-04-10 22:51:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using cpx=complex<double>;

#define int long long

const double pi=acos(-1);

const int N=5e3+1e2+7;

int na,ma,nb,mb;

mt19937 rng(58);

int col[111],rev[N];

cpx w[N];

cpx a[N][N],b[N][N];

cpx tmp[N];

void dft(cpx *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++)
            {
                cpx tmp=a[i+j+d]*w[len/m*j];
                a[i+j+d]=a[i+j]-tmp;
                a[i+j]+=tmp;
            }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=100;i++)
    {
        int w;
        int ok;
        do {
            w=rng()%1000;
            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);
    for(int i=0;i<len;i++)
        w[i]=cpx(cos(2*pi*i/len),sin(2*pi*i/len));
    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];
        }
    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][j]=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]*=b[i][j];

    
    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]/(double)len;
    }
    
    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]/(double)len;
    }
    vector<pair<int,int> >ans;
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
        {
            int w=(a[i][j].real()+0.5);
            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: 9356kb

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'