QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173491#5473. Move One CoinForever_Young#WA 2ms3800kbC++142.9kb2023-09-09 23:49:272023-09-09 23:49:27

Judging History

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

  • [2023-09-09 23:49:27]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3800kb
  • [2023-09-09 23:49:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
const int N = 555;
const int T = 500;
typedef long long LL;
const LL mod = 998244353;
constexpr LL fastpo(LL x, LL n, LL mod) {
	LL res = 1;
	while(n) {
		if(n % 2 == 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		n /= 2;
	}
	return res;
}
const LL RG = 3;
const LL CG = fastpo(RG, T, mod);
char st[N];
LL hsh(const pair<int, int> & t) {
	return fastpo(RG, t.fi, mod) * fastpo(CG, t.se, mod) % mod;
}
struct Board {
	int n, m;
	vector<pair<int, int> > vec;
	void scan() {
		scanf("%d%d", &n, &m);
		vec.clear();
		for(int i = 0; i < n; i++) {
			scanf("%s", st);
			for(int j = 0; j < m; j++) {
				if(st[j] == 'o') {
					vec.pb({i, j});
				}
			}
		}
	}
	void rotate() {
		for(auto & t : vec) {
			swap(t.fi, t.se);
			t.fi = T - t.fi - 1;
		}
	}
	vector<pair<LL, pair<int, int> > > res;
	void calc() {
		vector<int> cx(T), cy(T);
		LL tot = 0;
		for(auto t:  vec) {
			cx[t.fi]++;
			cy[t.se]++;
			tot = (tot + hsh(t)) % mod;
			//printf("hsh %d %d %d\n", t.fi, t.se, hsh(t));
		}
		for(auto t : vec) {
			cx[t.fi]--;
			cy[t.se]--;
			int mnx = -1, mny = -1;
			for(int i = 0; i < T; i++) {
				if(cx[i] > 0) {
					mnx = i;
					break;
				}
			}
			for(int i = 0; i < T; i++) {
				if(cy[i] > 0) {
					mny = i;
					break;
				}
			}
			if(mnx == -1) {
				res.pb({0, t});
				break;
			}
			tot = (tot - hsh(t) + mod) % mod;
			LL tf = tot;
			tf = tf * fastpo(RG, (mod - 2ll) * mnx, mod) % mod;
			tf = tf * fastpo(CG, (mod - 2ll) * mny, mod) % mod;
			//printf("%d %d = %d\n", t.fi, t.se, tf);
			res.pb({tf, t});

			tot = (tot + hsh(t)) % mod;
			cx[t.fi]++;
			cy[t.se]++;
		}
		sort(all(res));
	}
	int mnx, mny;
	vector<pair<int, int> > aligned_vec;
	void remove(const pair<int, int> & p) {
		vector<int> cx(T), cy(T);
		for(auto t:  vec) {
			if(t != p) {
				cx[t.fi]++;
				cy[t.se]++;
			}
		}
		mnx = -1, mny = -1;
		for(int i = 0; i < T; i++) {
			if(cx[i] > 0) {
				mnx = i;
				break;
			}
		}
		for(int i = 0; i < T; i++) {
			if(cy[i] > 0) {
				mny = i;
				break;
			}
		}
		aligned_vec.clear();
		for(auto t : vec) {
			if(t != p) {
				aligned_vec.pb({t.fi - mnx, t.se - mny});
			}
		}
		sort(all(aligned_vec));
	}
} a, b;
bool check(Board & a, const pair<int, int> & ap, Board & b, const pair<int, int> & bp) {
	a.remove(ap);
	b.remove(bp);
	return a.aligned_vec == b.aligned_vec;
}
int main() {
	a.scan();
	b.scan();
	a.calc();
	for(int d = 0; d < 4; d++) {

		b.calc();
		for(auto t : b.res) {
			auto itr = lower_bound(all(a.res), make_pair(t.fi, make_pair(-1, -1)));
			if(itr->fi == t.fi) {
				if(check(a, itr->se, b, t.se)) {
					printf("%d %d %d %d\n", itr->se.fi, itr->se.se, t.se.fi - b.mnx + a.mnx, t.se.se - b.mny + a.mny);
					exit(0);
				}
			}
		}
		b.rotate();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3800kb

input:

2 3
xox
ooo
4 2
ox
ox
ox
ox

output:

0 1 1 -1

result:

wrong answer Pattern did not match after movement