QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373147#5107. Mosaic BrowsingRobeZH#RE 412ms89076kbC++233.9kb2024-04-01 03:52:332024-04-01 03:52:34

Judging History

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

  • [2024-04-01 03:52:34]
  • 评测
  • 测评结果:RE
  • 用时:412ms
  • 内存:89076kb
  • [2024-04-01 03:52:33]
  • 提交

answer

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define subnb true
#define Lnb true
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

namespace fft {
    using dbl = long double;
    struct num {
        dbl x, y;
        num(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) {}
    };
    inline num operator+(num a, num b) {return num(a.x + b.x, a.y + b.y);}
    inline num operator-(num a, num b) {return num(a.x - b.x, a.y - b.y);}
    inline num operator*(num a, num b) {return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);}
    inline num conj(num a) {return num(a.x, -a.y);}
    inline num inv(num a) {dbl n = (a.x * a.x + a.y * a.y); return num(a.x / n, -a.y / n);}

    using vn = vector<num>;
    vi rev({0, 1});
    vn rt(2, num(1)), fa, fb;

    inline void init(int n) {
        if(n <= sz(rt)) return ;
        rev.resize(n);
        rep(i, 0, n) rev[i] = (rev[i >> 1] | ((i & 1) * n)) >> 1;
        rt.reserve(n);
        for (int k = sz(rt); k < n; k *= 2) {
            rt.resize(2 * k);
            double a = M_PI / k; num z(cos(a), sin(a));
            rep(i, k / 2, k) rt[2 * i] = rt[i], rt[2 * i + 1] = rt[i] * z;
        }
    }

    inline void fft(vector<num> &a, int n) {
        init(n);
        int s = __builtin_ctz(sz(rev) / n);
        rep(i, 0, n) if(i < rev[i] >> s) swap(a[i], a[rev[i] >> s]);
        for (int k = 1; k < n; k *= 2) {
            for (int i = 0; i < n; i += 2 * k) rep(j, 0, k) {
                num t = rt[j + k] * a[i + j + k];
                a[i + j + k] = a[i + j] - t;
                a[i + j] = a[i + j] + t;
            }
        }
    }

    vn multiply(vn a, vn b) {
        int s = sz(a) + sz(b) - 1;
        if(s <= 0) return {};
        int L = s > 1 ? 32 - __builtin_clz(s - 1) : 0, n = 1 << L;
        a.resize(n), b.resize(n);
        fft(a, n);
        fft(b, n);
        num d = inv(num(n));
        rep(i, 0, n) a[i] = a[i] * b[i] * d;
        reverse(a.begin() + 1, a.end());
        fft(a, n);
        a.resize(s);
        return a;
    }
}

using fft::num;
using poly = fft::vn;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

//    poly a(3, {1, 0}), b(3, {1, 0});
//    auto x = fft::multiply(a, b);
//
//    rep(i, 0, sz(x)) {
//        cout << x[i].x << " ";
//    }
//    cout << endl;

    int np, mp, n, m;
    cin >> np >> mp;
    vector<vi> a(np, vi(mp));
    ll csum = 0;
    rep(i, 0, np) rep(j, 0, mp) {
        cin >> a[i][j];
        csum += 1LL * a[i][j] * a[i][j] * a[i][j];
    }
    cin >> n >> m;
    vector<vi> b(n, vi(m));
    rep(i, 0, n) rep(j, 0, m) cin >> b[i][j];

    vector<ll> res(n * m, csum);
    rep(it, 0, 2) {
        poly ps(np * m, {0, 0});
        rep(i, 0, np) {
            rep(j, 0, mp) {
                if(it == 0) ps[i * m + j] = {(ld)a[i][j] * a[i][j], (ld)0};
                else ps[i * m + j] = {(ld)a[i][j], (ld)0};
            }
        }
        reverse(all(ps));
        poly pp(n * m, {0, 0});
        rep(i, 0, n) {
            rep(j, 0, m) {
                if(it == 0) pp[i * m + j] = {(ld)b[i][j], 0};
                else pp[i * m + j] = {(ld)b[i][j] * b[i][j], 0};
            }
        }
        poly cur = fft::multiply(ps, pp);
        rep(i, 0, n * m) {
            int idx = i + np * m - 1;
            if(it == 0) res[i] -= 2 * (ll)(cur[idx].x + 0.5);
            else res[i] += (ll)(cur[idx].x + 0.5);
        }
    }
    vector<pii> ps;
    rep(i, 0, n - np + 1) {
        rep(j, 0, m - mp + 1) {
            if(res[i * m + j] == 0) ps.push_back({i, j});
        }
    }
    cout << sz(ps) << '\n';
    for (auto p : ps) cout << p.first + 1 << " " << p.second + 1 << '\n';



}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 409ms
memory: 76304kb

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:

2005
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 10...

result:

ok 2006 lines

Test #2:

score: 0
Accepted
time: 404ms
memory: 81112kb

input:

250 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:

1255
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 10...

result:

ok 1256 lines

Test #3:

score: 0
Accepted
time: 412ms
memory: 89076kb

input:

500 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:

5
1 1
1 101
1 201
1 301
1 401

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

1 1
2
2 4
1 1 2 2
1 3 2 3

output:

3
1 3
1 4
2 3

result:

ok 4 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

1 1
1
4 1
1
4
2
6

output:

1
1 1

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

2 2
1 3
0 0
1 3
1 2 3

output:

0

result:

ok single line: '0'

Test #9:

score: -100
Runtime Error

input:

1 4
4 4 4 1
1 1
2

output:


result: