QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #522470 | #9132. Painting Fences | berarchegas# | WA | 4ms | 7960kb | C++20 | 6.9kb | 2024-08-16 23:47:02 | 2024-08-16 23:47:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 2e6 + 5;
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 lg[MAXN];
int calc(int a, int b, int c, int d) {
int tx = c - a + 1;
int qtdx = 1 + (n - c) / tx + !!((n - c) % tx) + (a - 1) / tx + !!((a - 1) % tx);
int ty = d - b + 1;
int qtdy = 1 + (m - d) / ty + !!((m - d) % ty) + (b - 1) / ty + !!((b - 1) % ty);
return lg[qtdx] + lg[qtdy];
}
// 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() {
int a = 1, cnt = 0;
while (a < MAXN) {
for (int i = a; i >= 2; i--) {
if (lg[i]) break;
lg[i] = cnt;
}
a *= 2;
cnt++;
}
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: 7892kb
input:
4 4 1001 0100 0110 0110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7724kb
input:
3 3 000 111 111
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7960kb
input:
4 3 011 011 001 110
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 3ms
memory: 7676kb
input:
4 4 0011 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
4 4 0000 0010 0100 1000
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
2 5 00010 00111
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 3ms
memory: 7888kb
input:
5 5 11111 11111 11111 01111 11111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 7732kb
input:
5 5 00101 00000 00001 00000 00100
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 3ms
memory: 7728kb
input:
5 5 00000 00000 00001 10000 00000
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 7672kb
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: 7668kb
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: 3ms
memory: 7892kb
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: 7960kb
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: 4ms
memory: 7704kb
input:
30 31 0000000000000000000000000000000 0000000000000000000000000000000 1111111111111110000000000000011 1111111111111110000000000000011 1111111111111110000000000000011 1111111111111111111111111111111 1111111111111111111111111111111 1111111111111111111111111111100 1111111111111111111111111111100 111111...
output:
3
result:
ok 1 number(s): "3"
Test #15:
score: -100
Wrong Answer
time: 3ms
memory: 7728kb
input:
30 31 0000000000000000000000000000000 0000000000000000000000000000000 0000000001000000000000000000000 0000000000000000000000100000000 0000000000000000000100000000000 0000000000000000001000000000000 0000000000000010000000000000000 0000000000000000000000000000000 0000000000000000000000000100110 000000...
output:
9
result:
wrong answer 1st numbers differ - expected: '10', found: '9'