Submission #724375

#	Time	Username	Problem	Language	Result	Execution time	Memory
724375		PixelCat	Rectangles (IOI19_rect)	C++14	0 / 100	63 ms	51572 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];
bitset<MAXN> pure[MAXN];
bitset<MAXN> vis[MAXN];

struct OWO {
    int far, pure, cnt, l, r, u, d;
    bool check() {
        if(far || !pure) return false;
        int w = r - l + 1;
        int h = d - u + 1;
        return w * h == cnt;
    }
    void out() {
        cout << "owo: ";
        if(far || !pure) cout << "far\n";
        else {
            cout << cnt << " (";
            cout << l << "-" << r << ", ";
            cout << u << "-" << d << ")\n";
        }
    }
};
OWO merge(const OWO &a, const OWO &b) {
    return (OWO){
        a.far || b.far,
        a.pure || b.pure,
        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) {
    vis[sx][sy] = 1;
    OWO owo = (OWO){0, 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, pure[x][y], 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(vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                que.emplace(nx, ny);
            }
        }
        if(check(x, y) == 1) {
            owo.far = 1;
        }
    }
    return owo;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
    n = sz(a);
    m = sz(a[0]);
    assert(max(n, m) <= 200);
    vector<pair<int, pii>> v;
    For(i, 0, n - 1) For(j, 0, m - 1) {
        g[i][j] = a[i][j];
        v.eb(g[i][j], pii(i, j));
        // assert(g[i][j] < 2);
    }
    sort(all(v));
    LL ans = 0;
    while(sz(v)) {
        int val = v.back().F;
        vector<pii> pos;
        while(sz(v) && v.back().F == val) {
            pos.eb(v.back().S);
            v.pop_back();
            auto &p = pos.back();
            pure[p.F][p.S] = 1;
        }
        For(i, 0, n - 1) vis[i].reset();
        For(i, 0, n - 1) For(j, 0, m - 1) {
            if(g[i][j] > val) vis[i][j] = 1;
            // cout << vis[i][j] << " \n"[j == m - 1];
        }
        For(i, 1, n - 2) For(j, 1, m - 2) if(vis[i][j] == 0) {
            auto owo = dfs(i, j);
            ans += owo.check();
            // owo.out();
        }
        for(auto &p:pos) {
            pure[p.F][p.S] = 0;
        }
    }
    return ans;
}

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