QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #522447 | #9132. Painting Fences | berarchegas# | WA | 2ms | 3864kb | C++20 | 6.2kb | 2024-08-16 23:16:12 | 2024-08-16 23:16:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int query(int a, int b, int c, int d, vector<vector<int>> &v) {
return v[c][d] - v[c][b - 1] - v[a - 1][d] + v[a - 1][b - 1];
}
int n, m;
int calc(int a, int b, int c, int d) {
int w = 0, x = 0, y = 0, z = 0;
int tam = c - a + 1;
while (tam < c) {
tam *= 2;
w++;
}
tam = c;
while (tam < n) {
tam *= 2;
w++;
}
tam = c - a + 1;
while (tam < n - a + 1) {
tam *= 2;
x++;
}
tam = n - a + 1;
while (tam < n) {
tam *= 2;
x++;
}
tam = d - b + 1;
while (tam < d) {
tam *= 2;
y++;
}
tam = d;
while (tam < m) {
tam *= 2;
y++;
}
tam = d - b + 1;
while (tam < m - b + 1) {
tam *= 2;
z++;
}
tam = m - b + 1;
while (tam < m) {
tam *= 2;
z++;
}
return min(w, x) + min(y, z);
}
int main() {
cin >> n >> m;
vector<vector<int>> v(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
v[i][j] = c - '0';
v[i][j] += v[i][j - 1];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
v[j][i] += v[j - 1][i];
}
}
int ans = 200;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// cout << i << ' ' << j << '\n';
int lin = n - i + 1;
int col = m - j + 1;
vector<int> ver, hor;
while (lin > 1) {
ver.push_back(lin);
lin = (lin / 2) + lin % 2;
}
while (col > 1) {
hor.push_back(col);
col = (col / 2) + col % 2;
}
ver.push_back(1);
hor.push_back(1);
reverse(ver.begin(), ver.end());
reverse(hor.begin(), hor.end());
// for (int x : ver) cout << x << ' ';
// cout << '\n';
// for (int x : hor) cout << x << ' ';
// cout << '\n';
for (int k = 0; k < (int)ver.size(); k++) {
if (query(i, j, i + ver[k] - 1, j, v) != ver[k]) break;
for (int l = 0; l < (int)hor.size(); l++) {
if (query(i, j, i + ver[k] - 1, j + hor[l] - 1, v) != ver[k] * hor[l]) break;
ans = min(ans, calc(i, j, i + ver[k] - 1, j + hor[l] - 1));
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
// cout << i << ' ' << j << '\n';
int lin = n - i + 1;
int col = j;
vector<int> ver, hor;
while (lin > 1) {
ver.push_back(lin);
lin = (lin / 2) + lin % 2;
}
while (col > 1) {
hor.push_back(col);
col = (col / 2) + col % 2;
}
ver.push_back(1);
hor.push_back(1);
reverse(ver.begin(), ver.end());
reverse(hor.begin(), hor.end());
// for (int x : ver) cout << x << ' ';
// cout << '\n';
// for (int x : hor) cout << x << ' ';
// cout << '\n';
for (int k = 0; k < (int)ver.size(); k++) {
if (query(i, j, i + ver[k] - 1, j, v) != ver[k]) break;
for (int l = 0; l < (int)hor.size(); l++) {
if (query(i, j - hor[l] + 1, i + ver[k] - 1, j, v) != ver[k] * hor[l]) break;
ans = min(ans, calc(i, j - hor[l] + 1, i + ver[k] - 1, j));
}
}
}
}
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= m; j++) {
// cout << i << ' ' << j << '\n';
int lin = i;
int col = m - j + 1;
vector<int> ver, hor;
while (lin > 1) {
ver.push_back(lin);
lin = (lin / 2) + lin % 2;
}
while (col > 1) {
hor.push_back(col);
col = (col / 2) + col % 2;
}
ver.push_back(1);
hor.push_back(1);
reverse(ver.begin(), ver.end());
reverse(hor.begin(), hor.end());
// for (int x : ver) cout << x << ' ';
// cout << '\n';
// for (int x : hor) cout << x << ' ';
// cout << '\n';
for (int k = 0; k < (int)ver.size(); k++) {
if (query(i - ver[k] + 1, j, i, j, v) != ver[k]) break;
for (int l = 0; l < (int)hor.size(); l++) {
if (query(i - ver[k] + 1, j, i, j + hor[l] - 1, v) != ver[k] * hor[l]) break;
ans = min(ans, calc(i - ver[k] + 1, j, i, j + hor[l] - 1));
}
}
}
}
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
// cout << i << ' ' << j << '\n';
int lin = i;
int col = j;
vector<int> ver, hor;
while (lin > 1) {
ver.push_back(lin);
lin = (lin / 2) + lin % 2;
}
while (col > 1) {
hor.push_back(col);
col = (col / 2) + col % 2;
}
ver.push_back(1);
hor.push_back(1);
reverse(ver.begin(), ver.end());
reverse(hor.begin(), hor.end());
// for (int x : ver) cout << x << ' ';
// cout << '\n';
// for (int x : hor) cout << x << ' ';
// cout << '\n';
for (int k = 0; k < (int)ver.size(); k++) {
if (query(i - ver[k] + 1, j, i, j, v) != ver[k]) break;
for (int l = 0; l < (int)hor.size(); l++) {
if (query(i - ver[k] + 1, j - hor[l] + 1, i, j, v) != ver[k] * hor[l]) break;
ans = min(ans, calc(i - ver[k] + 1, j - hor[l] + 1, i, j));
}
}
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
4 4 1001 0100 0110 0110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 3 000 111 111
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 3 011 011 001 110
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
4 4 0011 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 4 0000 0010 0100 1000
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 5 00010 00111
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
5 5 11111 11111 11111 01111 11111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 5 00101 00000 00001 00000 00100
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 5 00000 00000 00001 10000 00000
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
10 10 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
10 10 0001000000 0000000000 0000000000 0000000001 0000000001 0000000001 0000000000 0000000000 0000000000 0000000001
output:
6
result:
ok 1 number(s): "6"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
10 10 1111111110 1111111110 1111111110 1111111110 1111111110 1111100110 1111100010 1111101110 1111101100 1111100000
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
10 10 0000000000 0000001000 0000000000 0000000000 0000000000 0100000000 0000000000 0000000100 0000000000 0000000000
output:
8
result:
ok 1 number(s): "8"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
30 31 0000000000000000000000000000000 0000000000000000000000000000000 1111111111111110000000000000011 1111111111111110000000000000011 1111111111111110000000000000011 1111111111111111111111111111111 1111111111111111111111111111111 1111111111111111111111111111100 1111111111111111111111111111100 111111...
output:
3
result:
ok 1 number(s): "3"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
30 31 0000000000000000000000000000000 0000000000000000000000000000000 0000000001000000000000000000000 0000000000000000000000100000000 0000000000000000000100000000000 0000000000000000001000000000000 0000000000000010000000000000000 0000000000000000000000000000000 0000000000000000000000000100110 000000...
output:
10
result:
ok 1 number(s): "10"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
30 31 0000000000000000000000000000000 0000000011111111111111000000000 0000000011111111111111000000000 1111111111111111111111000000000 1111111111111111111111000000000 1111111111111111111111000000000 1111111111111111111111000111100 1111111111111111111111000111100 1111111111111111111111000111100 111111...
output:
3
result:
ok 1 number(s): "3"
Test #17:
score: -100
Wrong Answer
time: 1ms
memory: 3524kb
input:
30 31 0000001010000000000000000000000 0000000000000000000000000000000 0000000000000000001000000000000 0000010000000000000000000000000 0000000000000000000000000000000 0000000000000000000000000000000 0000001000010000000000000000000 0000100000010010000000000000000 0000000001000001000000010000000 000000...
output:
10
result:
wrong answer 1st numbers differ - expected: '9', found: '10'