QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #522428 | #9132. Painting Fences | berarchegas# | RE | 0ms | 3664kb | C++20 | 6.3kb | 2024-08-16 22:50:03 | 2024-08-16 22:50:04 |
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) {
// cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
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 <= n; i++) {
for (int j = 1; j <= m; j++) {
v[j][i] += v[j - 1][i];
}
}
int ans = 200;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; 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 = n; 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 <= n; 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 = n; 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: 3568kb
input:
4 4 1001 0100 0110 0110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 3 000 111 111
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
4 3 011 011 001 110
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
4 4 0011 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4 4 0000 0010 0100 1000
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: -100
Runtime Error
input:
2 5 00010 00111