QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173491 | #5473. Move One Coin | Forever_Young# | WA | 2ms | 3800kb | C++14 | 2.9kb | 2023-09-09 23:49:27 | 2023-09-09 23:49:27 |
Judging History
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