QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87919#5107. Mosaic BrowsingzokerWA 165ms40372kbC++176.2kb2023-03-14 20:16:572023-03-14 20:17:06

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:17:06]
  • 评测
  • 测评结果:WA
  • 用时:165ms
  • 内存:40372kb
  • [2023-03-14 20:16:57]
  • 提交

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-12;
	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: 0
Wrong Answer
time: 165ms
memory: 40372kb

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:

718
1 101
1 201
2 101
2 301
3 1
3 201
4 101
4 301
5 1
5 301
6 101
7 1
7 101
7 301
8 101
9 301
12 101
12 301
13 1
14 101
14 301
16 101
16 301
17 101
17 301
18 101
19 101
19 301
20 1
21 1
21 301
22 101
22 301
23 101
23 301
24 201
25 301
26 1
26 101
28 1
29 101
30 101
30 201
31 1
31 101
31 301
32 101
3...

result:

wrong answer 1st lines differ - expected: '2005', found: '718'