QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373147 | #5107. Mosaic Browsing | RobeZH# | RE | 412ms | 89076kb | C++23 | 3.9kb | 2024-04-01 03:52:33 | 2024-04-01 03:52:34 |
Judging History
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