QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673585#9478. Shift Puzzlehos_lyricWA 0ms3956kbC++143.1kb2024-10-25 00:36:222024-10-25 00:36:24

Judging History

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

  • [2024-10-25 00:36:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3956kb
  • [2024-10-25 00:36:22]
  • 提交

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