QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95630#5107. Mosaic Browsing_skb_WA 131ms92104kbC++175.5kb2023-04-10 23:28:122023-04-10 23:28:14

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 23:28:14]
  • 评测
  • 测评结果:WA
  • 用时:131ms
  • 内存:92104kb
  • [2023-04-10 23:28:12]
  • 提交

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 ll = long long;
using ld = long double;

#define eps 1e-12
#define op operator

struct base {
    typedef double T;
    T re, im;
    base() :re(0), im(0) {}
    base(T re) :re(re), im(0) {}
    base(T re, T im) :re(re), im(im) {}
    base op + (const base& o) const {
        return base(re + o.re, im + o.im);
    }
    base op - (const base& o) const {
        return base(re - o.re, im - o.im);
    }
    base op * (const base& o) const {
        return base(re * o.re - im * o.im, re * o.im + im * o.re);
    }
    base op * (ld k) const {return base(re * k, im * k) ;}
    base conj() const { return base(re, -im);}
};
const ll N = 21;
const ll MAXN = (1<<N);
base w[MAXN];
base f1[MAXN];
ll rev[MAXN];
void build_rev(ll k) {
    static ll rk = -1;
    if( k == rk )return ;
    rk = k;
    for(ll i=1; i<=(1<<k); i++) {
        ll j = rev[i-1], t = k-1;
        while( t >= 0 && ((j>>t)&1) ) {j ^= 1 << t;--t;}
        if( t >= 0 ) { j ^= 1 << t; --t;}
        rev[i] = j;
    }
}
void fft(base *a, ll k) {
    build_rev(k);
    ll n = 1 << k;
    for(ll i=0; i<n; i++) if( rev[i] > i ) swap(a[i], a[rev[i]]);
    for(ll l = 2, llo = 1; l <= n; l += l, llo += llo) {
        if( w[llo].re == 0 && w[llo].im == 0 ) {
            ld angle = M_PI / llo;
            base ww( cosl(angle), sinl(angle) );
            if( llo > 1 ) for(ll j = 0; j < llo; ++j) {
                    if( j & 1 ) w[llo + j] = w[(llo+j)/2] * ww;
                    else w[llo + j] = w[(llo+j)/2];
                }
            else w[llo] = base(1, 0);
        }
        for(ll i = 0; i < n; i += l) {
            for(ll j=0; j<llo; j++) {
                base v = a[i + j], u = a[i + j + llo] * w[llo + j];
                a[i + j] = v + u;
                a[i + j + llo] = v - u;
            }
        }
    }
}
vector<ll> Multiply(vector<ll>& a, vector<ll>& b) {
    vector<ll> res;
    ll k = 1;
    while( (1<<k) < (a.size() + b.size()) ) ++k;
    ll n = (1<<k);
    for(ll i=0; i<n; i++) f1[i] = base(0,0);
    for(ll i=0; i<a.size(); i++) f1[i] = f1[i] + base(a[i], 0);
    for(ll i=0; i<b.size(); i++) f1[i] = f1[i] + base(0, b[i]);
    fft(f1, k);
    for(ll i=0; i<1+n/2; i++) {
        base p = f1[i] + f1[(n-i)%n].conj();
        base _q = f1[(n-i)%n] - f1[i].conj();
        base q(_q.im, _q.re);
        f1[i] = (p * q) * 0.25;
        if( i > 0 ) f1[(n - i)] = f1[i].conj();
    }
    for(ll i=0; i<n; i++) f1[i] = f1[i].conj();
    fft(f1, k);
    res.resize(a.size() + b.size());
    for(ll i=0; i<res.size(); i++) {
        if(fabs(f1[i].re) < eps) res[i]=0;
        else res[i] = f1[i].re / fabs(f1[i].re) * ll (abs(f1[i].re / n) + 0.5);
    }
    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<i64> 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<i64> 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<i64> motif_line_sq;
    vector<i64> motif_line_cb;
    for(int i : motif_line) {
        motif_line_sq.push_back(i * i);
        motif_line_cb.push_back(i * i * i);
    }

    vector<i64> mosaic_line_sq;
    vector<i64> 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);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 131ms
memory: 92104kb

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:

574
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 101...

result:

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