QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87916#5107. Mosaic BrowsingzokerWA 149ms40968kbC++176.2kb2023-03-14 20:15:312023-03-14 20:15:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 20:15:32]
  • 评测
  • 测评结果:WA
  • 用时:149ms
  • 内存:40968kb
  • [2023-03-14 20:15:31]
  • 提交

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-9;
	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
*/

详细

Test #1:

score: 100
Accepted
time: 145ms
memory: 40368kb

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: 147ms
memory: 40620kb

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: 149ms
memory: 40968kb

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: 2ms
memory: 3552kb

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: 3636kb

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: 3608kb

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: 3676kb

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: 2ms
memory: 3632kb

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: 0ms
memory: 3600kb

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: 3560kb

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'