QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#457386#8816. Solar Panel Grid Optimizationhos_lyricWA 1ms4120kbC++143.8kb2024-06-29 11:23:122024-06-29 11:23:13

Judging History

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

  • [2024-06-29 11:23:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4120kb
  • [2024-06-29 11:23:12]
  • 提交

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 = 0; x < N; ++x) {
   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: 0ms
memory: 3836kb

input:

4
1011
1100
0100
1011

1001
0110
0110
1001

output:

45
row 2
column 2
column 2
row 2
column 2
column 2
column 2
row 3
column 2
row 3
column 2
row 3
column 1
column 1
row 3
row 4
column 1
column 1
column 1
column 1
column 2
column 2
column 2
column 2
row 1
column 2
column 2
column 2
row 1
column 1
row 1
row 1
column 1
column 1
row 2
column 1
column 1
...

result:

ok Accepted! 45 steps.

Test #2:

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

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: 0ms
memory: 3748kb

input:

4
1101
1000
0011
1010

0110
0011
1010
1010

output:

47
row 1
column 2
column 2
row 2
column 2
row 2
column 2
column 2
row 3
row 3
row 3
column 2
column 2
row 4
row 4
column 1
column 1
column 1
row 4
column 1
column 1
column 1
column 1
column 3
column 3
column 3
column 3
row 1
column 3
column 3
column 3
row 1
column 2
row 1
column 2
column 2
row 2
col...

result:

ok Accepted! 47 steps.

Test #4:

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

input:

5
10000
00000
00001
00000
01001

00000
00001
01010
00001
00000

output:

29
row 1
column 5
row 5
row 5
column 4
row 2
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: 0ms
memory: 3804kb

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

input:

7
1000000
1101010
1110010
0101000
1110011
0001100
1000010

1100100
1000010
0001000
1001101
1010110
0000001
1010111

output:

129
column 1
column 1
row 2
column 1
column 1
row 2
row 2
column 1
column 1
row 2
row 2
column 1
column 1
row 3
column 1
row 3
column 1
row 3
row 3
row 3
column 1
column 1
row 4
column 1
row 4
row 4
column 1
column 1
row 5
column 1
row 5
column 1
row 5
row 5
row 5
column 1
row 5
column 1
column 1
ro...

result:

ok Accepted! 129 steps.

Test #7:

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

input:

8
10000000
01100110
11000110
01010000
10000101
01101100
01001111
00110101

00011110
00000001
00111000
01011101
01000111
01010001
01101001
11010000

output:

171
row 1
row 1
row 1
column 6
column 6
row 2
column 6
row 2
row 2
row 2
column 6
row 2
column 6
column 6
row 3
column 6
column 6
row 3
row 3
column 6
row 3
column 6
column 6
row 4
row 4
row 4
row 4
column 6
row 4
row 4
column 6
column 6
row 5
row 5
column 6
row 5
column 6
column 6
row 6
row 6
row 6...

result:

ok Accepted! 171 steps.

Test #8:

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

input:

9
000000000
010000000
000000000
100000010
010001000
000000000
000100000
100000010
000001001

110000000
000110001
100000100
000100000
000000100
000010000
000000000
000000000
000000000

output:

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

result:

ok Accepted! 114 steps.

Test #9:

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

input:

10
0001011101
1101000101
1111101111
0110001110
1111011111
0011101110
1101100001
1000001111
1011011111
1111100110

1101101000
1111001011
1101011100
1000111110
0101001000
0011111101
1111011111
1100100111
1110101111
1110110101

output:

253
column 5
column 5
row 1
row 1
row 1
row 1
column 5
row 1
row 1
column 5
column 5
column 5
row 1
column 5
row 1
column 5
column 5
column 5
row 2
column 5
row 2
column 5
row 2
row 2
column 5
row 2
row 2
row 2
row 2
column 5
column 5
row 3
column 5
column 5
row 4
column 5
row 4
row 4
row 4
row 4
co...

result:

ok Accepted! 253 steps.

Test #10:

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

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:

266
row 1
row 1
row 1
row 1
column 9
row 1
column 9
column 9
row 1
row 1
column 9
column 9
column 9
row 1
row 1
column 9
row 1
column 9
column 9
row 2
column 9
column 9
row 3
row 3
row 3
row 3
column 9
column 9
row 3
row 3
row 3
column 9
row 3
column 9
row 3
column 9
column 9
column 9
row 5
column 9...

result:

ok Accepted! 266 steps.

Test #11:

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

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: 0ms
memory: 4120kb

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:

422
row 1
column 7
row 1
row 1
column 7
column 7
row 1
row 1
row 1
column 7
column 7
column 7
column 7
column 7
row 1
column 7
column 7
column 7
row 2
column 7
row 2
row 2
column 7
column 7
row 2
row 2
row 2
column 7
row 2
column 7
row 2
row 2
column 7
column 7
column 7
row 4
row 4
row 4
row 4
row 4...

result:

ok Accepted! 422 steps.

Test #13:

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

input:

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

00000000001000
10000000000100
01000000100000
00000000000000
00000110000011
00100000000...

output:

307
row 1
column 8
column 8
column 8
column 8
column 8
column 8
row 1
column 8
column 8
column 8
column 8
column 8
column 8
column 8
column 8
row 1
row 1
row 1
row 1
row 1
row 1
row 1
column 8
column 8
row 2
row 2
row 2
column 8
row 2
row 2
row 2
row 2
column 8
column 8
row 3
column 8
row 3
column 8...

result:

ok Accepted! 307 steps.

Test #14:

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

input:

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

011111111111111
111111011111111
111111101011111
00101111...

output:

405
row 1
column 9
column 9
column 9
row 1
row 1
row 1
row 1
row 1
row 1
column 9
column 9
row 1
row 1
row 1
row 1
column 9
column 9
row 2
row 2
column 9
column 9
row 3
row 3
row 3
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
column 9
row 5
column 9
row 5
row 5
ro...

result:

ok Accepted! 405 steps.

Test #15:

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

input:

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

1001101110000011
1000111...

output:

540
row 1
column 12
column 12
row 1
column 12
row 1
row 1
row 1
row 1
row 1
row 1
row 1
row 1
row 1
column 12
column 12
row 1
row 1
column 12
column 12
row 1
row 1
column 12
column 12
column 12
column 12
column 12
column 12
column 12
row 2
row 2
row 2
column 12
column 12
column 12
row 3
row 3
row 3
...

result:

ok Accepted! 540 steps.

Test #16:

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

input:

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

output:

865
row 1
row 1
row 1
column 14
column 14
row 1
row 1
row 1
column 14
row 1
row 1
column 14
column 14
column 14
column 14
row 1
column 14
row 1
column 14
column 14
row 1
column 14
column 14
row 1
row 1
column 14
column 14
row 2
row 2
row 2
row 2
row 2
row 2
column 14
column 14
row 2
row 2
column 14
...

result:

ok Accepted! 865 steps.

Test #17:

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

input:

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

output:

870
row 1
row 1
row 1
column 5
row 1
row 1
row 1
row 1
row 1
row 1
row 1
row 1
row 1
column 5
row 1
column 5
row 1
row 1
column 5
column 5
column 5
row 1
row 1
column 5
column 5
column 5
column 5
column 5
row 2
row 2
column 5
row 2
row 2
row 2
row 2
row 2
column 5
row 2
row 2
row 2
row 2
row 2
colum...

result:

ok Accepted! 870 steps.

Test #18:

score: -100
Wrong Answer
time: 1ms
memory: 3892kb

input:

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

output:

1015
column 4
column 4
row 1
row 1
column 4
row 1
row 1
column 4
column 4
column 4
row 1
column 4
column 4
column 4
row 1
row 1
row 1
row 1
row 1
row 1
row 1
row 1
column 4
row 1
column 4
column 4
row 1
column 4
column 4
column 4
column 4
column 4
row 1
column 4
column 4
column 4
row 2
row 2
row 2
c...

result:

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