Submission #724366

#	Time	Username	Problem	Language	Result	Execution time	Memory
724366		PixelCat	Rectangles (IOI19_rect)	C++14	13 / 100	319 ms	86184 KiB

rect

#include "rect.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 2510;

int n, m;
int g[MAXN][MAXN];

struct OWO {
    int bruh, cnt, l, r, u, d;
    bool check() {
        if(bruh) return false;
        int w = r - l + 1;
        int h = d - u + 1;
        return w * h == cnt;
    }
    void out() {
        cout << "owo: ";
        if(bruh) cout << "bruh\n";
        else {
            cout << cnt << " (";
            cout << l << "-" << r << ", ";
            cout << u << "-" << d << ")\n";
        }
    }
};
OWO merge(const OWO &a, const OWO &b) {
    return (OWO){
        a.bruh || b.bruh,
        a.cnt + b.cnt,
        min(a.l, b.l),
        max(a.r, b.r),
        min(a.u, b.u),
        max(a.d, b.d)
    };
}

// 0 for ok
// 1 for boundary
// 2 for outside
int check(int x, int y) {
    if(x < 0 || x >= n || y < 0 || y >= m) return 2;
    if(x == 0 || x == n - 1 || y == 0 || y == m - 1) return 1;
    return 0;
}

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
OWO dfs(int sx, int sy) {
    g[sx][sy] = 1;
    OWO owo = (OWO){0, 0, sx, sx, sy, sy};
    queue<pii> que;
    que.emplace(sx, sy);
    while(!que.empty()) {
        int x, y;
        tie(x, y) = que.front();
        que.pop();
        owo = merge(owo, (OWO){0, 1, x, x, y, y});
        For(it, 0, 3) {
            int nx = x + dx[it];
            int ny = y + dy[it];
            if(check(nx, ny) == 2) continue;
            if(g[nx][ny] == 0) {
                g[nx][ny] = 1;
                que.emplace(nx, ny);
            }
        }
        if(check(x, y) == 1) {
            owo.bruh = 1;
        }
    }
    return owo;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
    n = sz(a);
    m = sz(a[0]);
    For(i, 0, n - 1) For(j, 0, m - 1) {
        g[i][j] = a[i][j];
        assert(g[i][j] < 2);
    }
    int res = 0;
    For(i, 1, n - 2) For(j, 1, m - 2) if(g[i][j] == 0) {
        auto owo = dfs(i, j);
        res += owo.check();
        // owo.out();
    }
    return res;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28