QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#457384 | #8816. Solar Panel Grid Optimization | hos_lyric | WA | 1ms | 3940kb | C++14 | 3.5kb | 2024-06-29 11:19:02 | 2024-06-29 11:19:03 |
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")
int N;
vector<int> to0(vector<string> a) {
// 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 = 1; y < N; ++y) if (a[x][y] == '1') {
for (; a[x][0] == '1'; down(0)) {}
for (; a[x][0] == '0'; left(x)) {}
goto loop;
}
}
for (int x = 0; x < N; ++x) (a[x][0] == '1') ? left(x) : down(N - 1);
for (int x = 0; x < N; ++x) down(N - 1);
return ops;
}
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: 3656kb
input:
4 1011 1100 0100 1011 1001 0110 0110 1001
output:
41 row 4 column 1 row 3 row 3 column 1 row 3 row 2 row 2 column 1 row 2 row 1 row 1 row 2 row 3 row 4 column 4 column 4 column 4 column 4 column 1 column 1 column 1 column 1 row 1 row 2 row 3 row 4 row 4 column 4 row 4 row 3 row 3 row 3 row 2 row 2 row 2 row 1 column 4 column 4 column 4 row 1
result:
ok Accepted! 41 steps.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
3 110 111 101 111 010 111
output:
18 row 3 row 1 row 1 row 1 column 3 row 3 column 3 column 3 column 3 column 1 column 1 column 1 row 1 row 2 row 3 row 2 row 2 column 3
result:
ok Accepted! 18 steps.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
4 1101 1000 0011 1010 0110 0011 1010 1010
output:
42 column 1 row 4 row 4 column 1 column 1 row 3 row 3 column 1 row 3 row 1 column 1 row 1 row 1 row 1 row 2 column 4 row 4 column 4 column 4 column 4 column 4 column 1 column 1 column 1 column 1 row 1 row 2 row 3 row 4 row 4 row 4 column 4 row 4 row 3 row 3 column 4 row 3 row 2 row 1 column 4 column...
result:
ok Accepted! 42 steps.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 10000 00000 00001 00000 01001 00000 00001 01010 00001 00000
output:
34 row 5 column 1 row 5 row 5 row 5 row 3 row 3 row 3 row 3 column 5 row 2 row 3 column 5 row 5 column 5 column 5 column 5 column 5 column 5 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! 34 steps.
Test #5:
score: 0
Accepted
time: 1ms
memory: 3836kb
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: 1ms
memory: 3800kb
input:
7 1000000 1101010 1110010 0101000 1110011 0001100 1000010 1100100 1000010 0001000 1001101 1010110 0000001 1010111
output:
117 column 1 row 7 row 7 row 7 row 7 row 7 column 1 row 6 row 6 row 6 column 1 column 1 column 1 column 1 row 6 row 5 column 1 row 5 column 1 row 5 row 5 row 5 column 1 row 5 row 4 column 1 row 4 row 4 row 3 column 1 row 3 column 1 row 3 row 3 row 3 row 2 column 1 row 2 row 2 column 1 row 2 row 2 co...
result:
ok Accepted! 117 steps.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
8 10000000 01100110 11000110 01010000 10000101 01101100 01001111 00110101 00011110 00000001 00111000 01011101 01000111 01010001 01101001 11010000
output:
154 row 8 row 8 column 1 row 8 column 1 row 8 row 8 column 1 column 1 row 8 row 8 column 1 row 7 column 1 column 1 row 7 row 7 row 7 column 1 row 7 column 1 row 7 column 1 row 7 row 6 column 1 row 6 column 1 row 6 row 6 column 1 row 6 row 5 row 5 row 5 row 5 row 5 column 1 row 5 row 5 row 4 column 1...
result:
ok Accepted! 154 steps.
Test #8:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
9 000000000 010000000 000000000 100000010 010001000 000000000 000100000 100000010 000001001 110000000 000110001 100000100 000100000 000000100 000010000 000000000 000000000 000000000
output:
106 row 9 row 9 row 9 row 9 row 9 column 1 column 1 row 9 row 9 row 9 row 8 row 8 row 8 row 8 row 8 row 8 row 8 row 7 row 7 row 7 row 5 column 1 row 5 row 5 row 5 row 5 row 4 row 4 row 4 row 4 row 4 row 4 row 4 row 2 column 9 row 2 column 9 row 4 row 5 row 6 row 7 row 8 row 9 column 9 column 9 colum...
result:
ok Accepted! 106 steps.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
10 0001011101 1101000101 1111101111 0110001110 1111011111 0011101110 1101100001 1000001111 1011011111 1111100110 1101101000 1111001011 1101011100 1000111110 0101001000 0011111101 1111011111 1100100111 1110101111 1110110101
output:
230 row 10 row 10 row 10 row 10 row 10 column 1 row 10 column 1 row 10 row 10 row 10 row 9 column 1 column 1 row 9 row 9 row 9 column 1 row 8 column 1 row 8 column 1 column 1 row 8 column 1 row 8 column 1 row 8 row 7 row 7 column 1 row 7 row 7 row 7 column 1 row 7 column 1 row 7 column 1 row 7 row 6...
result:
ok Accepted! 230 steps.
Test #10:
score: 0
Accepted
time: 1ms
memory: 3616kb
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:
273 column 1 column 1 row 11 column 1 column 1 column 1 column 1 column 1 row 11 row 11 row 11 row 11 row 11 row 11 row 11 row 10 row 10 row 9 row 9 column 1 row 9 row 9 row 9 row 9 row 9 row 9 row 8 row 8 row 8 row 8 column 1 row 8 row 8 column 1 row 8 row 8 row 8 column 1 row 8 row 7 row 7 row 7 r...
result:
ok Accepted! 273 steps.
Test #11:
score: 0
Accepted
time: 0ms
memory: 3724kb
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:
65 row 2 row 2 row 2 row 2 row 2 row 2 row 2 row 2 row 2 column 12 row 2 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column 12 column ...
result:
ok Accepted! 65 steps.
Test #12:
score: 0
Accepted
time: 1ms
memory: 3684kb
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:
401 column 1 row 13 column 1 column 1 column 1 row 13 row 13 column 1 column 1 column 1 row 13 row 13 column 1 row 13 column 1 column 1 row 13 column 1 column 1 row 12 row 12 row 12 column 1 row 12 row 12 row 12 row 12 row 12 column 1 row 12 column 1 row 12 row 12 row 12 row 11 row 11 column 1 row 1...
result:
ok Accepted! 401 steps.
Test #13:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
14 00100000110000 10000000001000 10000000110000 00001000000000 00100000000001 00100000000001 00000000010000 00000000010000 00000001000000 00010010000000 00000000000000 00100000000000 00000000000000 10000000100000 00000000001000 10000000000100 01000000100000 00000000000000 00000110000011 00100000000...
output:
267 column 1 row 14 row 14 row 14 row 14 row 14 row 14 row 14 row 14 row 12 row 12 row 10 row 10 row 10 column 1 row 10 row 10 row 10 row 9 row 9 row 9 row 9 row 9 row 9 row 9 row 8 row 8 row 8 row 8 row 8 row 8 row 8 row 8 row 8 row 7 row 7 row 7 row 7 row 7 row 7 row 7 row 7 row 7 row 6 row 6 colu...
result:
ok Accepted! 267 steps.
Test #14:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
15 011101111011111 111111111101111 111111111110111 111111111111111 111111111011011 111011111011101 010111111111111 111111101111111 111110110111111 111111110111111 111001110111111 111111111101101 011111110111011 100110101110110 101111011111111 011111111111111 111111011111111 111111101011111 00101111...
output:
383 row 15 column 1 row 15 row 15 row 15 row 15 row 15 column 1 row 14 column 1 row 14 column 1 row 14 row 14 row 14 column 1 row 14 row 14 column 1 row 14 row 14 row 14 row 14 column 1 column 1 row 14 row 14 row 14 row 13 row 13 row 13 row 13 row 13 row 13 row 13 row 13 column 1 row 13 row 13 row 1...
result:
ok Accepted! 383 steps.
Test #15:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
16 1111110101010011 1111111111101101 0111111111111111 1101101111101000 1101011101111111 1110011101111011 0111111111110111 1111111101011101 1111111000011111 1101011111101111 1101110100111011 1111111111101110 1011111111011011 1111011010001100 1111111111101001 0110010111110110 1001101110000011 1000111...
output:
541 column 1 row 16 row 16 row 16 column 1 row 16 column 1 row 16 row 16 column 1 row 16 row 16 row 16 row 16 row 16 row 16 column 1 row 16 row 16 row 16 row 15 row 15 row 15 row 15 row 15 row 15 row 15 row 15 row 15 row 15 row 15 column 1 row 15 row 15 column 1 row 15 column 1 row 14 row 14 row 14 ...
result:
ok Accepted! 541 steps.
Test #16:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
17 11010000101111110 11010010010011111 00010100001100110 01110011010101000 01100101110110101 01101001001010011 10101010000111111 01101000001010100 01100100001111010 11110011010110011 10110001001010100 10100111100111000 01001001011011001 01110110111011100 11010111101010101 00100001100110101 010011100...
output:
814 column 1 column 1 row 17 row 17 column 1 column 1 column 1 row 17 column 1 row 17 row 17 row 17 row 17 column 1 row 17 column 1 column 1 column 1 row 17 row 17 row 17 row 17 row 17 row 17 column 1 column 1 column 1 column 1 column 1 row 17 column 1 row 17 row 16 column 1 row 16 row 16 column 1 r...
result:
ok Accepted! 814 steps.
Test #17:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
18 101011101111111100 101011011110111101 101101001010101011 010011011001100000 011011110110011110 010111111001100001 100101111001100001 101100111100111111 110000101101101110 111111110010100111 011011101100111011 111110101110110011 011101101010011011 010010001111011011 101111110101100111 011000001111...
output:
823 column 1 row 18 row 18 row 18 row 18 column 1 column 1 row 18 row 18 column 1 column 1 column 1 row 18 row 18 row 18 row 18 column 1 column 1 row 18 row 18 row 18 row 18 row 18 row 18 row 17 row 17 row 17 row 17 column 1 row 17 row 17 row 17 row 17 column 1 row 17 row 17 row 17 column 1 column 1...
result:
ok Accepted! 823 steps.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
19 0110101001111111000 1011110111000000011 1110111111110100101 1111110010111110111 1111110111101111110 0111001101011101101 0111111110101011100 0000010001010101010 1101011001001110011 1110101100101011001 1110100010001101001 1011000010101101001 1011010111011101010 1010010011101000101 01111001110010111...
output:
968 row 19 row 19 row 19 row 19 column 1 row 19 column 1 column 1 row 19 column 1 column 1 row 19 column 1 row 19 row 19 row 19 column 1 row 19 column 1 row 19 column 1 row 19 row 19 row 19 row 18 column 1 column 1 column 1 column 1 row 18 column 1 row 18 column 1 row 18 row 18 row 18 column 1 row 1...
result:
ok Accepted! 968 steps.
Test #19:
score: -100
Wrong Answer
time: 0ms
memory: 3812kb
input:
20 11101101111000111000 01101100100001001010 00001010110101000010 10011000000001101010 00100011110101011010 11100001011000011001 01010110010111000000 11100100010000100111 10000100011000111101 11101101001100111001 10000000011011011001 01000100101110000101 00101010001101000000 01010101000000000000 000...
output:
1054 row 20 row 20 row 20 row 20 column 1 row 20 column 1 row 20 row 20 row 20 column 1 column 1 row 20 row 20 row 20 column 1 row 20 row 20 row 20 row 20 row 19 column 1 row 19 column 1 row 19 column 1 column 1 column 1 column 1 column 1 row 19 row 19 row 19 column 1 column 1 row 19 column 1 column...
result:
wrong answer Integer parameter [name=steps] equals to 1054, violates the range [0, 1000]