QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#472806 | #5107. Mosaic Browsing | karuna | WA | 1853ms | 202900kb | C++20 | 4.7kb | 2024-07-11 19:27:40 | 2024-07-11 19:27:40 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
typedef long double ld;
#define double ld
typedef std::complex<double> cpx;
const int INF = (int)1e9 + 7;
using namespace std;
template <typename T>
vector<T> operator+ (const vector<T> &x, const vector<T> &y)
{
int n = x.size();
vector<T> ret(n);
for(int i = 0; i < n; ++i) ret[i] = x[i] + y[i];
return ret;
}
template <typename T>
vector<T> operator- (const vector<T> &x, const vector<T> &y)
{
int n = x.size();
vector<T> ret(n);
for(int i = 0; i < n; ++i) ret[i] = x[i] - y[i];
return ret;
}
template <typename T1, typename T2>
vector<T1> operator* (const vector<T1> &x, T2 y)
{
int n = x.size();
vector<T1> ret(n);
for(int i = 0; i < n; ++i) ret[i] = x[i] * y;
return ret;
}
vector<cpx> conj(vector<cpx> V)
{
for(auto &i : V) i = conj(i);
return V;
}
const double pi = acos(-1);
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));
}
}
template <typename T>
void dft(vector<T> &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)
{
T a = F[i + j];
T b = F[i + j + d] * (inv ? conj(w[M / d * j]) : w[M / d * j]);
F[i + j] = a + b;
F[i + j + d] = a - b;
}
}
}
if(inv) for(int i = 0; i < n; ++i) F[i] = F[i] * (double(1) / n);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int a, b; cin >> a >> b;
int A[a][b];
for(auto &i : A) for(auto &j : i) cin >> j;
int c, d; cin >> c >> d;
int B[c][d];
for(auto &i : B) for(auto &j : i) cin >> j;
int n = 1, m = 1;
while(n < a + c) n <<= 1;
while(m < b + d) m <<= 1;
init(15);
vector<vector<cpx>> X(n, vector<cpx>(m));
vector<vector<cpx>> Y(n, vector<cpx>(m));
vector<vector<cpx>> Z(n, vector<cpx>(m));
vector<vector<cpx>> WX(n, vector<cpx>(m));
vector<vector<cpx>> WY(n, vector<cpx>(m));
vector<vector<cpx>> WZ(n, vector<cpx>(m));
for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) X[i][j].real(A[a - i - 1][b - j - 1] * A[a - i - 1][b - j - 1] * A[a - i - 1][b - j - 1]);
for(int i = 0; i < c; ++i) for(int j = 0; j < d; ++j) X[i][j].imag(B[i][j]);
for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) Y[i][j].real(A[a - i - 1][b - j - 1] * A[a - i - 1][b - j - 1]);
for(int i = 0; i < c; ++i) for(int j = 0; j < d; ++j) Y[i][j].imag(B[i][j] * B[i][j]);
for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) Z[i][j].real(A[a - i - 1][b - j - 1]);
for(int i = 0; i < c; ++i) for(int j = 0; j < d; ++j) Z[i][j].imag(B[i][j] * B[i][j] * B[i][j]);
dft(X, false); for(auto &i : X) dft(i, false);
dft(Y, false); for(auto &i : Y) dft(i, false);
dft(Z, false); for(auto &i : Z) dft(i, false);
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
{
int _i = (n - i) % n;
int _j = (m - j) % m;
cpx p = (X[i][j] + conj(X[_i][_j])) * cpx(0.5, 0);
cpx q = (X[i][j] - conj(X[_i][_j])) * cpx(0, -0.5);
WX[i][j] = p * q;
}
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
{
int _i = (n - i) % n;
int _j = (m - j) % m;
cpx p = (Y[i][j] + conj(Y[_i][_j])) * cpx(0.5, 0);
cpx q = (Y[i][j] - conj(Y[_i][_j])) * cpx(0, -0.5);
WY[i][j] = cpx(-2.0, 0) * p * q;
}
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
{
int _i = (n - i) % n;
int _j = (m - j) % m;
cpx p = (Z[i][j] + conj(Z[_i][_j])) * cpx(0.5, 0);
cpx q = (Z[i][j] - conj(Z[_i][_j])) * cpx(0, -0.5);
WZ[i][j] = p * q;
}
dft(WX, true); for(auto &i : WX) dft(i, true);
dft(WY, true); for(auto &i : WY) dft(i, true);
dft(WZ, true); for(auto &i : WZ) dft(i, true);
vector<pii> ans;
for(int i = 0; i < c - a + 1; ++i) for(int j = 0; j < d - b + 1; ++j)
{
if((ll)round(WX[i + a - 1][j + b - 1].real())
+ (ll)round(WY[i + a - 1][j + b - 1].real())
+ (ll)round(WZ[i + a - 1][j + b - 1].real()) <= 10) ans.push_back({i, j});
}
// for(int i = 0; i < n; ++i)
// {
// for(int j = 0; j < m; ++j)
// {
// cout << (ll)round(W[i][j].real()) << ' ';
// }
// cout << endl;
// }
cout << ans.size() << '\n';
for(auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1853ms
memory: 202648kb
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: 1823ms
memory: 202748kb
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: 1835ms
memory: 202900kb
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: 3ms
memory: 4344kb
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: -100
Wrong Answer
time: 5ms
memory: 4400kb
input:
1 1 2 2 4 1 1 2 2 1 3 2 3
output:
8 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4
result:
wrong answer 1st lines differ - expected: '3', found: '8'