QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#457386 | #8816. Solar Panel Grid Optimization | hos_lyric | WA | 1ms | 4120kb | C++14 | 3.8kb | 2024-06-29 11:23:12 | 2024-06-29 11:23:13 |
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, 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]