QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95568 | #5470. Hasty Santa Claus | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 3.2kb | 2023-04-10 15:31:28 | 2023-04-10 15:31:31 |
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> transpose(const vector<string>& s) {
vector<string> res(SZ(s[0]));
FOR(i, 0, SZ(s)) {
FOR(j, 0, SZ(s[i])) {
res[j] += 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;
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, 2) {
for (string str : src) {
cerr << str << endl;
}
cerr << endl;
ULL fhSrc;
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(i);
jsSrc.insert(j);
//if ((h + pwP[row] * pwQ[col]) * pwP[N - *isSrc.begin()] * pwQ[N - *jsSrc.begin()] == fhDst)
if (h * pwP[N - *isSrc.begin()] * pwQ[N - *jsSrc.begin()] + pwP[N - *isSrc.begin() + row] * pwQ[N - *jsSrc.begin() + col] == fhDst) {
int x0 = i + 1, y0 = j + 1, x1 = row + 1, y1 = col + 1;
if (t) {
swap(x0, y0);
swap(x1, y1);
}
cout << x0 << " " << y0 << "\n";
cout << x1 << " " << y1 << "\n";
return 0;
}
isSrc.erase(isSrc.find(row));
jsSrc.erase(jsSrc.find(col));
}
}
}
isSrc.insert(i);
jsSrc.insert(j);
}
src = transpose(src);
}
assert(false);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
5 1 23 25 23 27 24 25 25 25 25 26