QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#467774 | #5107. Mosaic Browsing | karuna | WA | 5831ms | 104132kb | C++20 | 3.5kb | 2024-07-08 17:25:44 | 2024-07-08 17:25:45 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
namespace fft {
typedef complex<ld> cpx;
const ld pi = acos(-1);
const int D = 1000;
int M, B;
vector<int> rev;
vector<cpx> w;
void init(int _B) {
B = _B;
M = 1 << B;
w.resize(M);
rev.resize(M);
for (int i = 0; i < M; i++) {
w[i] = {cos(pi * i / M), sin(pi * i / M)};
rev[i] = (rev[i / 2] >> 1) | ((i & 1) << (B - 1));
}
}
void dft(vector<cpx> &F, bool inv) {
int n = F.size();
int b = __lg(n);
for (int i = 0; i < n; i++) {
int p = rev[i] >> (B - b);
if (i < p) swap(F[i], F[p]);
}
for (int d = 1; d < n; d *= 2) {
for (int i = 0; i < n; i += 2 * d) {
for (int j = 0; j < d; j++) {
cpx r = w[M / d * j];
if (inv) r = conj(r);
cpx a = F[i + j];
cpx b = F[i + j + d] * r;
F[i + j] = a + b;
F[i + j + d] = a - b;
}
}
}
if (inv) for (int i = 0; i < n; i++) F[i] /= n;
}
void dft_2d(vector<vector<cpx>> &F, bool rev) {
int n = F.size();
int m = F[0].size();
for (int i = 0; i < n; i++) dft(F[i], rev);
for (int i = 0; i < m; i++) {
vector<cpx> G(n);
for (int j = 0; j < n; j++) G[j] = F[j][i];
dft(G, rev);
for (int j = 0; j < n; j++) F[j][i] = G[j];
}
}
vector<vector<ll>> multiply(vector<vector<ll>> F, vector<vector<ll>> G) {
int n = 1, m = 1;
while (n < F.size() + G.size()) n *= 2;
while (m < F[0].size() + G[0].size()) m *= 2;
vector<vector<cpx>> P(n), Q(n);
for (int i = 0; i < n; i++) {
P[i].resize(m);
Q[i].resize(m);
}
for (int i = 0; i < F.size(); i++) for (int j = 0; j < F[0].size(); j++) {
P[i][j] = {(ld)F[i][j], (ld)0};
}
for (int i = 0; i < G.size(); i++) for (int j = 0; j < G[0].size(); j++) {
Q[i][j] = {(ld)G[i][j], (ld)0};
}
dft_2d(P, false);
dft_2d(Q, false);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) P[i][j] *= Q[i][j];
dft_2d(P, true);
vector<vector<ll>> R(n);
for (int i = 0; i < n; i++) {
R[i].resize(m);
for (int j = 0; j < m; j++) R[i][j] = (ll)round(P[i][j].real());
}
return R;
}
}
vector<vector<ll>> F[3], G[3], R[3];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
int n1, m1;
cin >> n1 >> m1;
vector<vector<ll>> C(n1, vector<ll>(m1));
for (int i = 0; i < n1; i++) for (int j = 0; j < m1; j++) cin >> C[n1 - 1 - i][m1 - 1 - j];
int n2, m2;
cin >> n2 >> m2;
vector<vector<ll>> A(n2, vector<ll>(m2));
for (int i = 0; i < n2; i++) for (int j = 0; j < m2; j++) cin >> A[i][j];
F[2] = C;
for (int t = 2; t > 0; t--) {
F[t - 1] = F[t];
for (int i = 0; i < n1; i++) for (int j = 0; j < m1; j++) F[t - 1][i][j] *= C[i][j];
}
G[0] = vector<vector<ll>>(n2, vector<ll>(m2, 1));
for (int t = 0; t < 2; t++) {
G[t + 1] = G[t];
for (int i = 0; i < n2; i++) for (int j = 0; j < m2; j++) G[t + 1][i][j] *= A[i][j];
}
fft::init(11);
vector<vector<ll>> R[3];
for (int t = 0; t < 3; t++) R[t] = fft::multiply(F[t], G[t]);
vector<pii> ans;
for (int x = n1; x <= n2; x++) for (int y = m1; y <= m2; y++) {
if (R[0][x][y] - 2 * R[1][x][y] + R[2][x][y] == 0) {
ans.push_back({x - n1 + 1, y - m1 + 1});
}
}
cout << ans.size() << '\n';
for (auto [x, y] : ans) {
cout << x << ' ' << y << '\n';
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 5831ms
memory: 104132kb
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:
1604 1 100 1 200 1 300 1 400 2 100 2 200 2 300 2 400 3 100 3 200 3 300 3 400 4 100 4 200 4 300 4 400 5 100 5 200 5 300 5 400 6 100 6 200 6 300 6 400 7 100 7 200 7 300 7 400 8 100 8 200 8 300 8 400 9 100 9 200 9 300 9 400 10 100 10 200 10 300 10 400 11 100 11 200 11 300 11 400 12 100 12 200 12 300 12...
result:
wrong answer 1st lines differ - expected: '2005', found: '1604'