QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95626#5107. Mosaic Browsing_skb_WA 716ms54020kbC++174.3kb2023-04-10 22:47:392023-04-10 22:47:41

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-10 22:47:41]
  • 评测
  • 测评结果:WA
  • 用时:716ms
  • 内存:54020kb
  • [2023-04-10 22:47:39]
  • 提交

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 = long double;
using cd = complex<ld>;
const ld PI = acos(-1.0);


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<int> multiply(vector<int> const& a, vector<int> 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<int> res(n);
    for(int i = 0; i < n; i++) res[i] = round(fa[i].real());
    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;
    }

    vector<int> 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++) {
            motif_line[start + k] = motif[i][j];
        }
    }

    vector<int> mosaic_line(n2 * m2);
    for(int i = 0, k = 0; i < n2; i++) {
        for(int j = 0; j < m2; j++) {
            mosaic_line[k++] = mosaic[i][j];
        }
    }

    vector<int> motif_line_sq;
    vector<int> motif_line_cb;
    for(int i : motif_line) {
        motif_line_sq.push_back(i * i);
        motif_line_cb.push_back(i * i * i);
    }
    reverse(motif_line.begin(), motif_line.end());
    reverse(motif_line_sq.begin(), motif_line_sq.end());
    reverse(motif_line_cb.begin(), motif_line_cb.end());


    vector<int> mosaic_line_sq;
    vector<int> mosaic_line_cb;
    for(int i : mosaic_line) {
        mosaic_line_sq.push_back(i * i);
        mosaic_line_cb.push_back(i * i * i);
    }

    auto res1 = multiply(mosaic_line_cb, motif_line);
    auto res2 = multiply(mosaic_line_sq, motif_line_sq);
    auto res3 = multiply(mosaic_line, motif_line_cb);

    vector<i64> res4(res1.size());

    for(int i = 0; i < (int)res1.size(); i++) {
        res4[i] = res1[i] - 2 * res2[i] + res3[i];
    }

    vector<pair<int, int>> ans;
    for(int i = 0; i <= n2-n1; i++) {
        for(int j = 0; j <= m2-m1; j++) {
            if(res4[i * m2 + j + (n1 - 1) * m2 + m1 - 1] == 0) {
                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);
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 716ms
memory: 54020kb

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:

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

result:

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