QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95629 | #5107. Mosaic Browsing | _skb_ | WA | 219ms | 40720kb | C++17 | 4.3kb | 2023-04-10 23:22:34 | 2023-04-10 23:22:38 |
Judging History
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 = 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<i64> multiply(vector<i64> const& a, vector<i64> 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<i64> 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<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];
// Wa() dbg(i) dbg(res1[i]) dbg(2*res2[i]) dbg(res3[i]);
}
vector<pair<int, int>> ans;
for(int i = 0; i <= n2-n1; i++) {
for(int j = 0; j <= m2-m1; j++) {
// Wa() dbg(i * m2 + j + (n1 - 1) * m2 + m1 - 1) dbg(res4[i * m2 + j + (n1 - 1) * m2 + m1 - 1]);
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: 219ms
memory: 40720kb
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:
1724 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:
wrong answer 1st lines differ - expected: '2005', found: '1724'