QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95574#5470. Hasty Santa ClausPetroTarnavskyi#RE 0ms0kbC++173.5kb2023-04-10 16:04:092023-04-10 16:04:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-10 16:04:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-04-10 16:04:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

typedef unsigned long long ULL;

const int MAX = 1 << 11;
const int N = 1 << 10;
const int P = 1'000'000'007;
const int Q = 1'000'000'009;

ULL pwP[MAX], pwQ[MAX];

vector<string> r() {
	int n, m;
	cin >> n >> m;
	vector<string> res(n);
	for (string& s : res) {
		cin >> s;
	}
	return res;
}

unordered_map<ULL, pair<int, int>> getHashes(const vector<string>& s, ULL& h, multiset<int>& is, multiset<int>& js) {
	unordered_map<ULL, pair<int, int>> res;
	FOR(i, 0, SZ(s)) {
		FOR(j, 0, SZ(s[i])) {
			if (s[i][j] == 'o') {
				is.insert(i);
				js.insert(j);
				h += pwP[i] * pwQ[j];
			}
		}
	}
	FOR(i, 0, SZ(s)) {
		FOR(j, 0, SZ(s[i])) {
			if (s[i][j] == 'o') {
				is.erase(is.find(i));
				js.erase(js.find(j));
				res[is.empty() ? 0 : (h - pwP[i] * pwQ[j]) * pwP[N - *is.begin()] * pwQ[N - *js.begin()]] = {i, j};
				is.insert(i);
				js.insert(j);
			}
		}
	}
	return res;
}

vector<string> rotate(const vector<string>& s) {
	vector<string> res(SZ(s[0]), string(SZ(s), 'x'));
	FOR(i, 0, SZ(s)) {
		FOR(j, 0, SZ(s[i])) {
			res[j][SZ(s) - 1 - i] = s[i][j];
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	pwP[0] = pwQ[0] = 1;
	FOR(i, 1, MAX) {
		pwP[i] = pwP[i - 1] * P;
		pwQ[i] = pwQ[i - 1] * Q;
	}
	vector<string> src = r(), dst = r();
	ULL fhDst = 0;
	multiset<int> isDst, jsDst;
	unordered_map<ULL, pair<int, int>> hDst = getHashes(dst, fhDst, isDst, jsDst);
	cerr << (pwP[0] + pwP[1] + pwP[2]) * pwP[N] * pwQ[N] << endl;
	for (auto [h, ij] : hDst) {
		auto [i, j] = ij;
		cerr << h << " " << i << " " << j << endl;
	}
	cerr << endl;
	FOR(t, 0, 4) {
		for (string str : src) {
			cerr << str << endl;
		}
		cerr << endl;
		ULL fhSrc = 0;
		multiset<int> isSrc, jsSrc;
		unordered_map<ULL, pair<int, int>> hSrc = getHashes(src, fhSrc, isSrc, jsSrc);
		for (auto [h, ij] : hSrc) {
			auto [i, j] = ij;
			cerr << h << " " << i << " " << j << endl;
			isSrc.erase(isSrc.find(i));
			jsSrc.erase(jsSrc.find(j));
			if (hDst.count(h)) {
				FOR(row, -N, N) {
					FOR(col, -N, N)	{
						if (row == i && col == j) {
							continue;
						}
						isSrc.insert(row);
						jsSrc.insert(col);
						//if ((h + pwP[row] * pwQ[col]) * pwP[N - *isSrc.begin()] * pwQ[N - *jsSrc.begin()] == fhDst)
						ULL h1 = (fhSrc - pwP[i] * pwQ[j]) * pwP[N - *isSrc.begin()] * pwQ[N - *jsSrc.begin()] + pwP[N - *isSrc.begin() + row] * pwQ[N - *jsSrc.begin() + col];
						ULL h2 = fhDst * pwP[N - *isDst.begin()] * pwQ[N - *jsDst.begin()];
						if (h1 == h2) {
							int n = SZ(src), m = SZ(src[0]);
							int x0 = i, y0 = j, x1 = row, y1 = col;
							cout << x0 << " " << y0 << " " << x1 << " " << y1 << endl;
							FOR(l, 0, t) {
								swap(x0, y0);
								x0 = n - 1 - x0;
								swap(x1, y1);
								x1 = n - 1 - x1;
								swap(n, m);
							}
							cout << x0 << " " << y0 << " " << x1 << " " << y1 << endl;
							return 0;
						}
						isSrc.erase(isSrc.find(row));
						jsSrc.erase(jsSrc.find(col));
					}
				}
			}
			isSrc.insert(i);
			jsSrc.insert(j);
		}
		src = rotate(src);
	}
	assert(false);
	return 0;
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

5 1
23 25
23 27
24 25
25 25
25 26

output:


result: