QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96615#5107. Mosaic Browsing_skb_WA 97ms29332kbC++174.0kb2023-04-14 19:49:542023-04-14 19:49:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-14 19:49:57]
  • 评测
  • 测评结果:WA
  • 用时:97ms
  • 内存:29332kb
  • [2023-04-14 19:49:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

struct debug {
#define contPrint { *this << "["; \
        int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
        *this << "]"; return *this;}
 
    ~debug(){cerr << endl;}
    template<class c> debug& operator<<(c x) {cerr << x; return *this;}
    template<class c, class d>
    debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")"; 
        return *this;}
    template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};

#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() << 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);

using ld = double;
using cd = complex<ld>;
const ld PI = acos(-1.0);
const ld eps = 1e-9;


void fft(vector<cd>& a, bool invert)
{
    int n = (int)a.size();

    for(int i = 1, j = 0; 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) {
        ld ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cosl(ang), sinl(ang));
        for(int i = 0; i < n; i += len) {
            cd w(1);
            for(int j = 0; j < len / 2; j++) {
                cd u = a[i + j], v = a[i + j + len/2] * w;
                a[i + j] = u + v;
                a[i + j + len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if(invert) {
        for(cd& x : a) {
            x /= n;
        }
    }
}

vector<i64> multiply(vector<cd> const& a, vector<cd> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while(n < (int)a.size() + b.size()) {
        n <<= 1;
    }
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for(int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);

    vector<i64> res(n);
    for(int i = 0; i < n; i++) {
        if(abs(fa[i].imag()) < eps) {
            res[i] = round(fa[i].real());
            if(abs(res[i] - fa[i].real()) > eps) {
                res[i] = -1;
            }
        } else {
            res[i] = -1;
        }
    }
    return res;
}

int main() 
{
    int n1, m1;
    scanf("%d %d", &n1, &m1);
    int motif[n1][m1];
    for(int i = 0; i < n1; i++) {
        for(int j = 0; j < m1; j++) {
            scanf("%d", &motif[i][j]);
        }
    }

    int n2, m2;
    scanf("%d %d", &n2, &m2);
    int mosaic[n2][m2];
    for(int i = 0; i < n2; i++) {
        for(int j = 0; j < m2; j++) {
            scanf("%d", &mosaic[i][j]);
        }
    }

    if(n1 > n2 || m1 > m2) {
        puts("0");
        return 0;
    }

    int nz = 0;
    vector<cd> motif_line((n1 - 1) * m2 + m1);
    for(int i = n1-1, start = 0; i >= 0; i--, start += m2) {
        for(int j = m1-1, k = 0; j >= 0; j--, k++) {
            ld ang = 2 * PI * motif[i][j] / 101;
            if(motif[i][j]) {
                motif_line[start + k] = cd(cosl(ang), sinl(ang));
                nz++;
            } else {
                motif_line[start + k] = cd(0, 0);
            }
        }
    }

    vector<cd> mosaic_line(n2 * m2);
    for(int i = 0, k = 0; i < n2; i++) {
        for(int j = 0; j < m2; j++) {
            ld ang = 2 * PI * mosaic[i][j] / 101;
            mosaic_line[k++] = cd(cosl(ang), -sinl(ang));
        }
    }
    auto res = multiply(mosaic_line, motif_line);
    vector<pair<int, int>> ans;
    for(int i = 0; i <= n2-n1; i++) {
        for(int j = 0; j <= m2-m1; j++) {
            if(res[i * m2 + j + (n1 - 1) * m2 + m1 - 1] == nz) {
                ans.push_back({i + 1, j + 1});
            }
        }
    }
    sort(ans.begin(), ans.end());

    printf("%d\n", (int)ans.size());
    for(auto it : ans) {
        printf("%d %d\n", it.first, it.second);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 97ms
memory: 29332kb

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:

0

result:

wrong answer 1st lines differ - expected: '2005', found: '0'