QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95630 | #5107. Mosaic Browsing | _skb_ | WA | 131ms | 92104kb | C++17 | 5.5kb | 2023-04-10 23:28:12 | 2023-04-10 23:28:14 |
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 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'