QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673585 | #9478. Shift Puzzle | hos_lyric | WA | 0ms | 3956kb | C++14 | 3.1kb | 2024-10-25 00:36:22 | 2024-10-25 00:36:24 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
/*
row(x)^b, col(y)^a, row(x)^-b, col(y)^-a (2N ops)
(x, y) -> (x-a, y) -> (x, y-b) -> (x, y)
*/
int N;
char S[110][110];
char T[110][110];
int mod(int z) {
return ((z %= N) < 0) ? (z + N) : z;
}
vector<pair<int, int>> ops;
void row(int x, int b) {
ops.insert(ops.end(), mod(b), make_pair(1, x));
}
void col(int y, int a) {
ops.insert(ops.end(), mod(a), make_pair(2, y));
}
void oper(int x, int y, int a, int b, bool inv) {
assert(mod(a));
assert(mod(b));
if (inv) {
col(y, a); row(x, b); col(y, -a); row(x, -b);
} else {
row(x, b); col(y, a); row(x, -b); col(y, -a);
}
}
int main() {
for (; ~scanf("%d", &N); ) {
for (int x = 0; x < N; ++x) scanf("%s", S[x]);
for (int x = 0; x < N; ++x) scanf("%s", T[x]);
vector<pair<int, int>> ps, qs;
for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
if (S[x][y] == '#' && T[x][y] == '.') ps.emplace_back(x, y);
if (S[x][y] == '.' && T[x][y] == '#') qs.emplace_back(x, y);
}
if (ps.size() == qs.size()) {
ops.clear();
for (int i = 0; i < (int)ps.size(); ++i) {
const int x0 = ps[i].first, y0 = ps[i].second;
const int x1 = qs[i].first, y1 = qs[i].second;
assert(S[x0][y0] == '#');
assert(S[x1][y1] == '.');
if (x0 == x1) {
const int x = mod(x0 + 1);
oper(x0, y0, x0 - x, y0 - y1, (S[x][y0] == '.'));
} else if (y0 == y1) {
const int y = mod(y0 + 1);
oper(x0, y0, x0 - x1, y0 - y, (S[x0][y] == '#'));
} else {
oper(x1, y0, x1 - x0, y0 - y1, (S[x0][y1] == '#'));
}
swap(S[x0][y0], S[x1][y1]);
}
puts("Yes");
printf("%d\n", (int)ops.size());
for (const auto &op : ops) {
printf("%d %d\n", op.first, op.second + 1);
}
} else {
puts("No");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
input:
3 .#. #.# .#. #.# ... #.#
output:
Yes 24 2 2 2 2 1 1 2 2 1 1 1 1 2 1 2 1 1 1 2 1 1 1 1 1 1 3 1 3 2 3 1 3 2 3 2 3 2 2 2 2 1 3 1 3 2 2 1 3
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
3 .#. #.# .#. .#. #.# .#.
output:
Yes 0
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
13 ............. ....#####.... ......#...... ......#...... ......#...... ......#...... ............. ....#...#.... ....#...#.... ....#...#.... ....#...#.... .....###..... ............. ....####..... ....#...#.... ....####..... ....#........ ....#........ ............. .....###..... ....#...#.... ......
output:
No
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
3 #.# #.# ### #.# .#. ###
output:
No
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 .#.. .#.. .... ...# .... ..#. #... ....
output:
No
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 .... .... .... .#.. ..## ##.# #### ..##
output:
No
result:
ok AC
Test #7:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 .. .. .. ..
output:
Yes 0
result:
ok AC
Test #8:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
3 .## ##. .#. ##. ..# .##
output:
Yes 18 2 3 2 3 1 1 1 1 2 3 1 1 2 1 2 1 1 2 2 1 1 2 1 2 2 2 1 3 1 3 2 2 2 2 1 3
result:
ok AC
Test #9:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
3 ... #.. ..# ... #.. #..
output:
Yes 6 2 3 2 3 1 3 1 3 2 3 1 3
result:
ok AC
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3812kb
input:
3 ..# .## ### #.# .## #.#
output:
Yes 6 2 2 1 1 2 2 2 2 1 1 1 1
result:
wrong answer WA S is not T