QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95574 | #5470. Hasty Santa Claus | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 3.5kb | 2023-04-10 16:04:09 | 2023-04-10 16:04:11 |
Judging History
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