QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#89935#1283. Paper-cuttingwangzhe_0477WA 25ms73912kbC++235.5kb2023-03-21 20:15:452023-03-21 20:15:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-21 20:15:46]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:73912kb
  • [2023-03-21 20:15:45]
  • 提交

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'