QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#457389#8816. Solar Panel Grid Optimizationhos_lyricWA 2ms3924kbC++143.8kb2024-06-29 11:23:472024-06-29 11:23:47

Judging History

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

  • [2024-06-29 11:23:47]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3924kb
  • [2024-06-29 11:23:47]
  • 提交

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")


int N;

vector<int> to0(vector<string> a, int y0) {
// cerr<<"[to0]"<<endl;for(int x=0;x<N;++x)cerr<<"  "<<a[x]<<endl;
  vector<int> ops;
  auto left = [&](int x) -> void {
    ops.push_back(x);
    rotate(a[x].begin(), a[x].begin() + 1, a[x].end());
// cerr<<"[left] "<<x<<endl;for(int x=0;x<N;++x)cerr<<"  "<<a[x]<<endl;
  };
  auto down = [&](int y) -> void {
    ops.push_back(N + y);
    const char t = a[N - 1][y];
    for (int x = N - 1; --x >= 0; ) a[x + 1][y] = a[x][y];
    a[0][y] = t ^ '0' ^ '1';
// cerr<<"[down] "<<y<<endl;for(int x=0;x<N;++x)cerr<<"  "<<a[x]<<endl;
  };
  for (int x = N; --x >= 0; ) {
   loop:
    for (int y = 0; y < N; ++y) if (y0 != y && a[x][y] == '1') {
      for (; a[x][y0] == '1'; down(y0)) {}
      for (; a[x][y0] == '0'; left(x)) {}
      goto loop;
    }
  }
  const int y1 = y0 ? (y0 - 1) : (N - 1);
  for (int x = 0; x < N; ++x) (a[x][y0] == '1') ? left(x) : down(y1);
  for (int x = 0; x < N; ++x) down(y1);
  return ops;
}

vector<int> to0(const vector<string> &a) {
  auto ret = to0(a, 0);
  for (int y = 1; y < N; ++y) {
    auto res = to0(a, y);
    if (ret.size() > res.size()) ret = res;
  }
  return ret;
}

vector<int> solve(const vector<string> &a, const vector<string> &b) {
  auto opsA = to0(a);
  auto opsB = to0(b);
  reverse(opsB.begin(), opsB.end());
  for (const int op : opsB) {
    if (op < N) {
      opsA.push_back(N - 1 - op);
    } else {
      opsA.push_back(N + (N - 1 - (op - N)));
    }
  }
  return opsA;
}

char A[30][30], B[30][30];

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int x = 0; x < N; ++x) scanf("%s", A[x]);
    for (int x = 0; x < N; ++x) scanf("%s", B[x]);
    
    vector<string> a(N, string(N, '?'));
    vector<string> b(N, string(N, '?'));
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) a[x][y] = A[x][y];
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) b[x][y] = B[N - 1 - x][N - 1 - y];
    
    const auto ops0 = solve(a, b);
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) a[x][y] ^= '0' ^ '1';
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) b[x][y] ^= '0' ^ '1';
    const auto ops1 = solve(a, b);
cerr<<"|ops0| = "<<ops0.size()<<", |ops1| = "<<ops1.size()<<endl;
    
    const auto ans = (ops0.size() < ops1.size()) ? ops0 : ops1;
    printf("%d\n", (int)ans.size());
    for (const int op : ans) {
      if (op < N) {
        printf("row %d\n", op + 1);
      } else {
        printf("column %d\n", (op - N) + 1);
      }
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3924kb

input:

4
1011
1100
0100
1011

1001
0110
0110
1001

output:

37
row 3
column 2
row 3
column 2
column 2
row 3
row 2
column 2
row 2
column 1
row 2
row 3
row 4
column 1
column 1
column 1
column 1
column 4
column 4
column 4
column 4
row 1
row 2
row 3
row 4
row 4
row 3
column 3
row 3
row 3
row 2
column 3
column 3
row 2
row 2
row 1
column 3

result:

ok Accepted! 37 steps.

Test #2:

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

input:

3
110
111
101

111
010
111

output:

15
row 1
row 1
column 1
row 3
column 1
column 1
column 1
column 2
column 2
column 2
row 1
row 2
row 3
row 2
column 1

result:

ok Accepted! 15 steps.

Test #3:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

4
1101
1000
0011
1010

0110
0011
1010
1010

output:

39
column 2
column 2
column 2
row 4
row 4
row 3
row 3
row 3
row 2
column 2
row 2
row 1
row 1
row 2
row 3
row 4
column 1
column 1
column 1
column 1
column 3
column 3
column 3
column 3
row 1
row 2
row 3
row 4
row 4
row 4
row 3
row 3
row 2
row 1
column 2
column 2
column 2
column 2
row 1

result:

ok Accepted! 39 steps.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

5
10000
00000
00001
00000
01001

00000
00001
01010
00001
00000

output:

29
column 5
row 5
row 5
row 1
row 1
column 4
column 4
row 4
row 5
column 4
column 4
column 4
column 4
column 4
column 1
column 1
column 1
column 1
column 1
row 1
row 2
row 3
row 4
column 1
row 3
row 3
column 5
column 5
row 3

result:

ok Accepted! 29 steps.

Test #5:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

6
111111
111111
111111
111111
111111
111111

111111
111111
111111
111111
111111
111111

output:

24
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 6
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1
column 1

result:

ok Accepted! 24 steps.

Test #6:

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

input:

7
1000000
1101010
1110010
0101000
1110011
0001100
1000010

1100100
1000010
0001000
1001101
1010110
0000001
1010111

output:

109
column 6
row 7
row 7
column 6
row 6
row 6
row 6
row 6
row 6
column 6
column 6
column 6
row 6
row 5
column 6
row 5
column 6
row 5
column 6
row 5
row 4
row 4
row 4
column 6
row 4
row 4
row 3
row 3
column 6
row 3
column 6
row 3
row 2
row 2
column 6
row 2
column 6
row 2
row 2
row 1
row 1
row 1
row 2...

result:

ok Accepted! 109 steps.

Test #7:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

8
10000000
01100110
11000110
01010000
10000101
01101100
01001111
00110101

00011110
00000001
00111000
01011101
01000111
01010001
01101001
11010000

output:

153
column 6
column 6
column 6
column 6
row 8
row 8
column 6
column 6
column 6
row 8
row 8
row 8
column 6
row 8
row 7
column 6
row 7
column 6
row 7
row 7
column 6
row 7
row 7
row 7
row 6
row 6
row 6
row 6
column 6
row 6
column 6
row 6
row 6
row 5
row 5
column 6
row 5
row 4
row 4
row 4
row 4
column 6...

result:

ok Accepted! 153 steps.

Test #8:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

9
000000000
010000000
000000000
100000010
010001000
000000000
000100000
100000010
000001001

110000000
000110001
100000100
000100000
000000100
000010000
000000000
000000000
000000000

output:

94
row 9
column 8
column 8
row 9
row 9
row 9
row 9
row 9
row 9
row 8
row 8
row 7
row 7
row 7
row 7
row 7
row 5
row 5
row 5
column 8
row 5
row 5
row 5
row 5
row 4
row 4
row 2
row 2
row 2
column 7
row 2
column 7
row 4
row 5
row 6
row 7
row 8
row 9
column 7
column 7
column 7
column 7
column 7
column 7
...

result:

ok Accepted! 94 steps.

Test #9:

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

input:

10
0001011101
1101000101
1111101111
0110001110
1111011111
0011101110
1101100001
1000001111
1011011111
1111100110

1101101000
1111001011
1101011100
1000111110
0101001000
0011111101
1111011111
1100100111
1110101111
1110110101

output:

220
row 10
row 10
row 10
row 10
column 2
column 2
column 2
row 10
column 2
column 2
row 10
row 10
row 10
row 9
row 9
row 9
row 8
column 2
row 8
column 2
column 2
row 8
column 2
row 8
row 7
column 2
row 7
row 7
row 7
column 2
row 7
column 2
row 7
column 2
row 7
row 6
row 6
row 6
row 6
column 2
row 6
...

result:

ok Accepted! 220 steps.

Test #10:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

11
01101011000
00000000010
01001110100
00000000100
10010001110
11000000101
10000010000
10001010011
00100000100
10100000000
11000000100

00101110001
01100001100
10010000000
00011111000
01001000000
00100000001
11000000000
10000101001
00001000000
01010100011
11001000000

output:

228
column 9
row 11
row 11
row 11
column 9
column 9
row 11
row 10
row 10
row 10
column 9
column 9
column 9
column 9
column 9
row 10
row 10
row 9
row 9
row 9
row 9
row 9
row 8
column 9
row 8
column 9
row 8
column 9
row 8
row 8
row 8
row 8
column 9
row 8
row 8
row 7
row 7
row 7
column 9
row 7
row 7
ro...

result:

ok Accepted! 228 steps.

Test #11:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

12
000000000000
000000000100
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000

000100000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
0000000000...

output:

48
column 9
row 2
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 5
column 5
column 5
column 5
column 5
column 5
column 5
column 5
column 5
col...

result:

ok Accepted! 48 steps.

Test #12:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

13
0111111010110
0101111010110
1111110111111
0100110111110
1100111011011
1111100110110
0111011101111
0110111011111
1110111101101
0111111011101
0101000011101
1110111100110
0010100011111

1101011011111
0111111111111
0010010111101
0111011110000
1000101011111
1100101101001
0111111111110
1110110111100
11...

output:

369
column 7
row 13
column 7
column 7
row 13
row 13
row 13
row 13
row 13
row 13
column 7
row 13
column 7
row 13
row 13
column 7
row 13
row 13
column 7
row 12
row 12
column 7
column 7
column 7
row 12
column 7
row 12
row 12
row 12
column 7
row 12
row 12
row 12
row 12
row 11
column 7
row 11
row 11
row ...

result:

ok Accepted! 369 steps.

Test #13:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

14
00100000110000
10000000001000
10000000110000
00001000000000
00100000000001
00100000000001
00000000010000
00000000010000
00000001000000
00010010000000
00000000000000
00100000000000
00000000000000
10000000100000

00000000001000
10000000000100
01000000100000
00000000000000
00000110000011
00100000000...

output:

244
row 14
column 8
row 14
row 14
row 14
row 14
row 14
row 14
row 12
row 12
row 12
row 12
row 12
row 12
row 12
row 12
row 12
column 8
row 10
row 10
row 10
row 10
row 10
row 10
row 10
row 10
row 10
row 10
column 8
row 10
row 10
row 10
row 8
row 8
row 7
row 7
row 6
row 6
row 6
row 6
row 6
row 6
column...

result:

ok Accepted! 244 steps.

Test #14:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

15
011101111011111
111111111101111
111111111110111
111111111111111
111111111011011
111011111011101
010111111111111
111111101111111
111110110111111
111111110111111
111001110111111
111111111101101
011111110111011
100110101110110
101111011111111

011111111111111
111111011111111
111111101011111
00101111...

output:

336
row 15
row 15
row 15
row 15
row 15
row 15
row 15
row 15
row 15
column 8
column 8
row 15
row 15
row 15
row 15
row 15
row 14
row 14
row 14
row 14
column 8
row 14
row 14
row 14
column 8
row 14
row 14
column 8
row 14
column 8
column 8
row 14
row 14
row 14
row 13
column 8
row 13
row 13
row 13
row 13
...

result:

ok Accepted! 336 steps.

Test #15:

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

input:

16
1111110101010011
1111111111101101
0111111111111111
1101101111101000
1101011101111111
1110011101111011
0111111111110111
1111111101011101
1111111000011111
1101011111101111
1101110100111011
1111111111101110
1011111111011011
1111011010001100
1111111111101001
0110010111110110

1001101110000011
1000111...

output:

476
row 16
column 12
column 12
column 12
row 16
row 16
row 16
column 12
column 12
row 16
column 12
column 12
row 16
row 16
row 16
column 12
row 16
column 12
row 16
row 16
row 15
row 15
column 12
row 15
column 12
row 14
row 14
row 14
column 12
column 12
row 14
column 12
row 14
row 14
row 14
row 14
ro...

result:

ok Accepted! 476 steps.

Test #16:

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

input:

17
11010000101111110
11010010010011111
00010100001100110
01110011010101000
01100101110110101
01101001001010011
10101010000111111
01101000001010100
01100100001111010
11110011010110011
10110001001010100
10100111100111000
01001001011011001
01110110111011100
11010111101010101
00100001100110101
010011100...

output:

804
row 17
column 14
column 14
column 14
row 17
column 14
row 17
column 14
row 17
column 14
column 14
column 14
row 17
row 17
column 14
column 14
row 17
column 14
column 14
column 14
row 17
row 17
row 17
row 17
column 14
column 14
row 17
row 16
row 16
column 14
row 16
row 16
column 14
row 16
column ...

result:

ok Accepted! 804 steps.

Test #17:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

18
101011101111111100
101011011110111101
101101001010101011
010011011001100000
011011110110011110
010111111001100001
100101111001100001
101100111100111111
110000101101101110
111111110010100111
011011101100111011
111110101110110011
011101101010011011
010010001111011011
101111110101100111
011000001111...

output:

808
column 5
column 5
column 5
row 18
row 18
column 5
row 18
row 18
row 18
row 18
column 5
column 5
row 18
row 18
row 18
row 18
row 18
row 18
column 5
row 18
row 18
row 17
row 17
row 17
row 17
column 5
column 5
column 5
column 5
row 17
row 17
row 17
row 16
column 5
row 16
column 5
column 5
row 16
co...

result:

ok Accepted! 808 steps.

Test #18:

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

input:

19
0110101001111111000
1011110111000000011
1110111111110100101
1111110010111110111
1111110111101111110
0111001101011101101
0111111110101011100
0000010001010101010
1101011001001110011
1110101100101011001
1110100010001101001
1011000010101101001
1011010111011101010
1010010011101000101
01111001110010111...

output:

938
row 19
column 4
column 4
column 4
row 19
column 4
row 19
column 4
column 4
row 19
column 4
row 19
row 19
row 19
column 4
column 4
column 4
row 19
column 4
column 4
row 19
column 4
row 19
row 19
row 19
row 18
row 18
row 18
column 4
row 18
column 4
column 4
row 18
row 18
row 18
column 4
column 4
r...

result:

ok Accepted! 938 steps.

Test #19:

score: -100
Wrong Answer
time: 2ms
memory: 3680kb

input:

20
11101101111000111000
01101100100001001010
00001010110101000010
10011000000001101010
00100011110101011010
11100001011000011001
01010110010111000000
11100100010000100111
10000100011000111101
11101101001100111001
10000000011011011001
01000100101110000101
00101010001101000000
01010101000000000000
000...

output:

1038
row 20
row 20
row 20
column 2
column 2
column 2
row 20
column 2
row 20
row 20
row 20
column 2
row 20
row 20
row 20
column 2
column 2
row 20
row 20
row 20
row 20
column 2
row 19
column 2
column 2
row 19
column 2
column 2
column 2
column 2
row 19
row 19
row 19
column 2
row 19
column 2
row 19
colu...

result:

wrong answer Integer parameter [name=steps] equals to 1038, violates the range [0, 1000]