QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87920 | #5107. Mosaic Browsing | zoker | WA | 158ms | 40940kb | C++17 | 6.2kb | 2023-03-14 20:17:48 | 2023-03-14 20:17:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")
using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;
#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V>
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif
#define eb emplace_back
#define fi first
#define se second
const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T, class V>
ostream& operator << (ostream &s, pair<T, V> a){
s << a.fi << ' ' << a.se; return s;
}
template<class T, class V>
istream& operator >> (istream &s, pair<T, V> &a){
s >> a.fi >> a.se; return s;
}
template<class T>
ostream& operator << (ostream &s, vector<T> a){
for(int i = 0; i < (int)a.size(); i++){
if(i > 0)s << ' ' ;
s << a[i];
} return s;
}
template<class T>
istream& operator >> (istream &s, vector<T> &a){
for(T &x : a)s >> x;
return s;
}
template<class T>
void input(T a[], int l, int r, istream &s = cin){
while(l <= r)s >> a[l++];
}
template<class T>
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
while(l <= r){ s << a[l++];
if(l <= r) s << ' ';
} if(en)s << "\n";
}
const int N = 4e3+3, K = 101;
//====================================================================//
struct CD {
double x, y;
CD(double x=0, double y=0) :x(x), y(y) {}
CD operator+(const CD& o) {return {x+o.x, y+o.y};}
CD operator-(const CD& o) {return {x-o.x, y-o.y};}
CD operator*(const CD& o) {
return {x*o.x-y*o.y, x*o.y+o.x*y};}
void operator /= (double d) { x/=d; y/=d;}
double real() {return x;}
double imag() {return y;}
};
CD conj(const CD &c) {return CD(c.x, -c.y);}
typedef long long LL; ;
namespace FFT {
int N;
vector<int> perm;
vector<CD> wp[2];
void precal(int n) {
assert((n & (n-1)) == 0); N = n;
perm = vector<int> (N, 0);
for (int k=1; k<N; k<<=1) {
for (int i=0; i<k; i++) {
perm[i] <<= 1; perm[i+k] = 1 + perm[i];}
}
wp[0] = wp[1] = vector<CD>(N);
for (int i=0; i<N; i++) {
wp[0][i] = CD( cos(2*PI*i/N), sin(2*PI*i/N));
wp[1][i] = CD( cos(2*PI*i/N), -sin(2*PI*i/N));
}
}
void fft(vector<CD> &v, bool invert = false) {
if (v.size() != perm.size()) precal(v.size());
for (int i=0; i<N; i++)
if (i < perm[i]) swap(v[i], v[perm[i]]);
for (int len = 2; len <= N; len *= 2) {
for (int i=0, d = N/len; i<N; i+=len) {
for (int j=0, idx=0; j<len/2; j++, idx+=d) {
CD x = v[i+j];
CD y = wp[invert][idx]*v[i+j+len/2];
v[i+j] = x+y;
v[i+j+len/2] = x-y;
}
}
} if (invert) {
for (int i=0; i<N; i++) v[i]/=N; }
}
void pairfft(vector<CD> &a, vector<CD> &b,
bool invert = false) {
int N = a.size(); vector<CD> p(N);
for (int i=0; i<N; i++) p[i]=a[i]+b[i]*CD(0, 1);
fft(p, invert); p.push_back(p[0]);
for (int i=0; i<N; i++) { if (invert) {
a[i] = CD(p[i].real(), 0);
b[i] = CD(p[i].imag(), 0);
} else {
a[i] = (p[i]+conj(p[N-i]))*CD(0.5, 0);
b[i] = (p[i]-conj(p[N-i]))*CD(0, -0.5);
}
}
}
vector<LL> multiply(vector<LL> a, vector<LL> b) {
int n = 1; while (n < a.size()+ b.size()) n<<=1;
vector<CD> fa(a.begin(), a.end()), fb(b.begin(),
b.end()); fa.resize(n); fb.resize(n);
pairfft(fa, fb); // fft(fa); fft(fb);
for (int i=0; i<n; i++) fa[i] = fa[i] * fb[i];
fft(fa, true);
vector<LL> ans(n);
for(int i=0;i<n;i++) ans[i]=round(fa[i].real());
return ans;
}
vector<vector<CD>> multiply(vector<vector<CD>> a, vector<vector<CD>> b) {
int n = 1; while (n < a.size()+ b.size()) n<<=1;
int m = 1; while (m < a[0].size()+ b[0].size()) m<<=1;
a.resize(n);
b.resize(n);
for(auto &x : a)x.resize(m);
for(auto &x : b)x.resize(m);
for(int i = 0; i < n; i++){
fft(a[i]);
fft(b[i]);
}
for(int i = 0; i < m; i++){
vector<CD> temp(n);
for(int j = 0; j < n; j++)temp[j] = a[j][i];
fft(temp);
for(int j = 0; j < n; j++)a[j][i] = temp[j], temp[j] = b[j][i];
fft(temp);
for(int j = 0; j < n; j++)b[j][i] = temp[j];
}
for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)a[i][j] = a[i][j] * b[i][j];
for(int i = 0; i < m; i++){
vector<CD> temp(n);
for(int j = 0; j < n; j++)temp[j] = a[j][i];
fft(temp, true);
for(int j = 0; j < n; j++)a[j][i] = temp[j];
}
for(int i = 0; i < n; i++){
fft(a[i], true);
}
return a;
}
}
CD getCD(int x){
if(x == 0)return CD(0, 0);
return CD( cos(2*PI*x/K), -sin(2*PI*x/K));
}
void testcase(){
int r1, c1, r2, c2;
cin >> r1 >> c1;
int cnt = 0;
vector<vector<CD>> g1(r1, vector<CD>(c1));
for(int i = 0; i < r1; i++){
for(int j = 0; j < c1; j++){
int x;
cin >> x;
cnt += (x == 0);
g1[r1 - 1 - i][c1 - 1 - j] = getCD(x);
}
}
cin >> r2 >> c2;
vector<vector<CD>> g2(r2, vector<CD>(c2));
for(int i = 0; i < r2; i++){
for(int j = 0; j < c2; j++){
int x;
cin >> x;
g2[i][j] = getCD(K - x);
}
}
vii ans;
const ld EPS = 1e-5;
auto G = FFT::multiply(g1, g2);
for(int i = r1 - 1; i < G.size(); i++){
for(int j = c1 - 1; j < G[i].size(); j++){
int u = round(G[i][j].real());
if(abs(G[i][j].real() - u) > EPS)u = -1;
u += cnt;
if(u == r1 * c1)ans.eb(i - r1 + 2, j - c1 + 2);
}
}
cout << ans.size() << "\n";
for(auto x : ans)cout << x << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
//cin >> T;
for(int qq = 1; qq <= T; ++qq){
//cout << "Case #" << qq << ": ";
testcase();
}
return 0;
}
/*
6 1597352862016328480
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 153ms
memory: 40300kb
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: 153ms
memory: 40420kb
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: 158ms
memory: 40940kb
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: 1ms
memory: 3640kb
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: 2ms
memory: 3604kb
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: 2ms
memory: 3584kb
input:
1 1 1 4 1 1 4 2 6
output:
1 1 1
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 2ms
memory: 3544kb
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: 1ms
memory: 3604kb
input:
2 2 1 3 0 0 1 3 1 2 3
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
1 4 4 4 4 1 1 1 2
output:
0
result:
ok single line: '0'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3624kb
input:
1 1 0 6 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
64 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8
result:
wrong answer 1st lines differ - expected: '24', found: '64'