Submission #289734

#	Time	Username	Problem	Language	Result	Execution time	Memory
289734		Ozy	Rectangles (IOI19_rect)	C++17	13 / 100	571 ms	158072 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl

struct x{
    lli fila;
    lli colu;
};

lli hijos[8] = {1,-1,0,0,0,0,1,-1};
lli visitados[2502][2502];
lli arr[2500][2500];
lli fil,col,res;
queue<x> cola;

bool checa(int f, int c) {
    lli f1,f2,c1,c2,sum,x1,y1;
    x act;
    bool res1;

    res1 = true;
    f1 = f;
    f2 = f;
    c1 = c;
    c2 = c;
    sum = 0;
    cola.push({f,c});

    while (!cola.empty()) {
        act = cola.front();
        cola.pop();

        if (act.fila == 0 || act.fila == fil-1) {
            res1 = false;
            continue;
        }
        if (act.colu == 0 || act.colu == col-1) {
            res1 = false;
            continue;
        }

        if (visitados[act.fila][act.colu] == 0) {
            visitados[act.fila][act.colu] = 1;
            sum++;

            f1 = max(f1,act.fila);
            f2 = min(f2,act.fila);
            c1 = max(c1,act.colu);
            c2 = min(c2,act.colu);

            rep(i,0,3) {
                x1 = act.fila + hijos[i];
                y1 = act.colu + hijos[i+4];
                //cout << x1 << ' ' << y1<<endl;

                if (visitados[x1][y1] == 0 && arr[x1][y1] == 0) cola.push({x1,y1});
            }
        }
    }

    x1 = (f1-f2+1)*(c1-c2+1);

    if (!res1) return false;

    if (sum == x1) return true;
    else return false;

}

long long count_rectangles(std::vector<std::vector<int> > a) {

	fil = a.size();
	col = a[0].size();

	rep(i,0,fil-1) {
        rep(j,0,col-1) {
            arr[i][j] = a[i][j];
        }
	}

	res = 0;
	rep(i,1,fil-2) {
        rep(j,1,col-2) {

            if (visitados[i][j] == 0 && a[i][j] == 0) {

                if (checa(i,j)) res++;
            }

        }
	}

	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