QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#668080#9478. Shift Puzzleucup-team173WA 0ms3800kbC++202.8kb2024-10-23 11:09:042024-10-23 11:09:19

Judging History

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

  • [2024-10-23 11:09:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3800kb
  • [2024-10-23 11:09:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<string> s(n), t(n);
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> t[i];
    }
    vector<pair<int, int>> p0, p1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(s[i][j] != t[i][j]) {
                if(s[i][j] == '#') {
                    p1.push_back({i, j});
                } else {
                    p0.push_back({i, j});
                }
            }
        }
    }
    if(p0.size() != p1.size()) {
        cout << "No\n";
        return 0;
    }
    vector<pair<int, int>> ans;
    auto row = [&](int i, int t) {
        while(t--) {
            ans.push_back({1, i});
            int tmp = s[i][n - 1];
            for(int j = n - 1; j; j--) {
                s[i][j] = s[i][j - 1];
            }
            s[i][0] = tmp;
        }
    };
    auto col = [&](int j, int t) {
        while(t--) {
            ans.push_back({2, j});
            int tmp = s[n - 1][j];
            for(int i = n - 1; i; i--) {
                s[i][j] = s[i - 1][j];
            }
            s[0][j] = tmp;
        }
    };
    auto rotate = [&](int i, int j, int r, int c, int ty) {
        // ty *= r * c;
        if(ty > 0) {
            row(i, r < 0 ? -r : n - r);
            col(j, c < 0 ? -c : n - c);
            row(i, r < 0 ? n + r : r);
            col(j, c < 0 ? n + c : c);
        } else {
            col(j, c < 0 ? -c : n - c);
            row(i, r < 0 ? -r : n - r);
            col(j, c < 0 ? n + c : c);
            row(i, r < 0 ? n + r : r);
        }
    };
    for(int _ = 0; _ < p0.size(); _++) {
        auto [x1, y1] = p0[_];
        auto [x2, y2] = p1[_];
        // cerr << '\n';
        // cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
        if(x1 != x2 && y1 != y2) {
            rotate(x1, y2, y1 - y2, x2 - x1, s[x1][y1] == s[x1][y2] ? 1 : -1);
        } else if(x1 == x2) {
            x2 = (x2 + 1) % n;
            rotate(x1, y2, y1 - y2, x2 - x1, s[x1][y1] == s[x1][y2] ? 1 : -1);
        } else {
            y1 = (y1 + 1) % n;
            rotate(x1, y2, y1 - y2, x2 - x1, s[x1][y1] != s[x1][y2] ? 1 : -1);
        }
        // for(int i = 0; i < n; i++) {
        //     for(int j = 0; j < n; j++) {
        //         cerr << s[i][j];
        //     }
        //     cerr << '\n';
        // }
    }
    cout << "Yes\n";
    cout << ans.size() << '\n';
    for(auto [x, y] : ans) {
        cout << x << ' ' << y + 1 << '\n';
    }
    return 0;
}
/*
3
.#.
#.#
.#.
#.#
...
#.#


4
..#.
#..#
.#..
#.#.
.#..
....
...#
####

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

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: 3512kb

input:

3
.#.
#.#
.#.
.#.
#.#
.#.

output:

Yes
0

result:

ok AC

Test #3:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

13
.............
....#####....
......#......
......#......
......#......
......#......
.............
....#...#....
....#...#....
....#...#....
....#...#....
.....###.....
.............
....####.....
....#...#....
....####.....
....#........
....#........
.............
.....###.....
....#...#....
......

output:

No

result:

ok AC

Test #4:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

3
#.#
#.#
###
#.#
.#.
###

output:

No

result:

ok AC

Test #5:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4
.#..
.#..
....
...#
....
..#.
#...
....

output:

No

result:

ok AC

Test #6:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

4
....
....
....
.#..
..##
##.#
####
..##

output:

No

result:

ok AC

Test #7:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

2
..
..
..
..

output:

Yes
0

result:

ok AC

Test #8:

score: 0
Accepted
time: 0ms
memory: 3536kb

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: 3596kb

input:

3
...
#..
..#
...
#..
#..

output:

Yes
6
2 3
2 3
1 3
1 3
2 3
1 3

result:

ok AC

Test #10:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

3
..#
.##
###
#.#
.##
#.#

output:

Yes
6
1 1
2 2
1 1
1 1
2 2
2 2

result:

ok AC

Test #11:

score: -100
Wrong Answer
time: 0ms
memory: 3768kb

input:

4
....
#...
...#
#.#.
#...
....
.#..
.##.

output:

Yes
24
2 1
2 1
2 1
1 1
1 1
1 1
2 1
1 1
2 4
2 4
2 4
1 3
1 3
2 4
1 3
1 3
2 1
2 1
2 1
1 4
1 4
1 4
2 1
1 4

result:

wrong answer WA S is not T