QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89935 | #1283. Paper-cutting | wangzhe_0477 | WA | 25ms | 73912kb | C++23 | 5.5kb | 2023-03-21 20:15:45 | 2023-03-21 20:15:46 |
Judging History
answer
/*
Source:
39th Petrozavodsk Programming Camp
Day 4: Xi Lin Contest 6, Tuesday, August 25, 2020
Problem:
Paper-cutting
*/
#include <bits/stdc++.h>
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
constexpr ULL E(LD x, int y) {
while (y--) x *= 10;
return x;
}
constexpr ULL SIZE(LD x, int y) {return E(x, y) + 5;}
const int inf32 = E(1, 9) + 5;
const LL inf64 = E(1, 18) + 5;
using ULL = unsigned long long;
namespace IO {
const int MAX_SIZE = 1 << 20;
class Reader {
private:
FILE *file;
char buff[MAX_SIZE], *p1, *p2;
int getchar() {
if (p1 == p2) p2 = (p1 = buff) + fread(buff, 1, MAX_SIZE, file);
return p1 == p2 ? EOF : *p1++;
}
public:
Reader(FILE *_file) {
file = _file;
p1 = p2 = buff;
}
Reader(const char* file_dir) {
file = std::fopen(file_dir, "r");
p1 = p2 = buff;
}
void Read() {}
template<typename... Args>
void Read(int &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(long long &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(__int128 &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(double &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (ch == '.') {
double e = 1;
for (ch = getchar(); isdigit(ch); ch = getchar())
x += (ch ^ 48) * (e *= .1);
}
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(char &ch, Args &...other) {
ch = getchar();
while (!isgraph(ch)) ch = getchar();
Read(other...);
}
template<typename... Args>
void Read(std::string &s, Args &...other) {
char ch;
s = "";
ch = getchar();
for (; !isgraph(ch);) ch = getchar();
for (; isgraph(ch); ch = getchar()) s += ch;
Read(other...);
}
template<typename... Args>
void Read(char* s, Args &...other) {
char ch;
ch = getchar();
while (!isgraph(ch)) ch = getchar();
for (; isgraph(ch); ch = getchar()) *s++ = ch;
*s = 0;
Read(other...);
}
};
}
IO::Reader reader(stdin);
int n, m, c[SIZE(1, 6)];
std::string s[SIZE(1, 6)];
std::vector<bool> vis[SIZE(1, 6)];
ULL h1[SIZE(1, 6)], h2[SIZE(1, 6)];
void Manacher(ULL s[SIZE(1, 6)], int len, int &l, int &r) {
int _r = 0, _mid = 0;
s[len + 1] = 0;
for (int i = 1; i <= len; i++) {
c[i] = i > _r ? 0 : c[2 * _mid - i];
while (i - c[i] > 0 && s[i - c[i]] == s[i + c[i] + 1]) c[i]++;
if (i + c[i] > _r) {
_r = i + c[i];
_mid = i;
}
}
l = 1;
for (int i = 2; i < len; i++)
if (i - c[i] < l)
l = i + 1;
r = len;
for (int i = len - 1; i >= l; i--)
if (i + c[i] >= r)
r = i;
}
int l1, r1, l2, r2;
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
void Dfs(int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < l1 || tx > r1) continue;
if (ty < l2 || ty > r2) continue;
if (s[tx - 1][ty - 1] != '0') continue;
if (vis[tx][ty]) continue;
Dfs(tx, ty);
}
}
int main() {
int data_count;
scanf("%d", &data_count);
for (int data = 1; data <= data_count; data++) {
reader.Read(n, m);
for (int i = 0; i < n; i++) reader.Read(s[i]);
for (int i = 0; i <= std::max(n, m) + 1; i++) h1[i] = h2[i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
h1[i] = h1[i] * 2 + (s[i - 1][j - 1] == '0');
h2[j] = h2[j] * 2 + (s[i - 1][j - 1] == '0');
}
Manacher(h1, n, l1, r1);
Manacher(h2, m, l2, r2);
printf("%d %d %d %d\n", l1, r1, l2, r2);
int ans = 0;
for (int i = 1; i <= n; i++) vis[i].resize(m + 5, 0);
for (int i = l1; i <= r1; i++)
for (int j = l2; j <= r2; j++)
if (s[i - 1][j - 1] == '0' && !vis[i][j])
Dfs(i, j), ans++;
printf("%d\n", ans);
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 25ms
memory: 73912kb
input:
3 2 5 11001 11001 5 7 1001100 0110011 0101101 0010010 1000000 3 2 11 11 11
output:
1 1 4 5 1 1 5 1 4 4 3 3 1 1 0
result:
wrong answer 2nd words differ - expected: '4', found: '1'