Hola, estuve viendo el problema agujeros del OIAJ (http://juez.oia.unsam.edu.ar/#/task/agujeros/statement) y no puedo sobrepasar los 65ptos.
Mi idea es la siguiente:
- Debido a que las coordenadas de los rectángulos son muy grandes, aplico compresión de coordenadas para reducir el tablero a 2\mathrm{N}×2\mathrm{N} siendo \mathrm{N} la cantidad de rectángulos.
- Utilizo un
vector< vector<int> >para representar el plano comprimido. Todas las casillas las pongo en 0 .- Para marcar los rectángulos, marco sus esquinas tal que, la esquina superior izquierda y el extremo opuesto, le sumo uno a la casilla (+1). Mientras, en las dos restantes, le quito uno a la casilla (-1).
- Recorro el plano, en mi caso, por filas. Aplico tablas aditivas. Así entonces tengo un contador al que le sumo el valor en la casilla por la que paso. Esto podrá subir o bajar según previamente haya marcado las esquinas de un rectángulo. De ser dicho contador positivo, lleno las casillas con 1. A su vez, le sumo el valor que encuentre a la casilla de abajo, de estar dentro del límite del plano. Así llenaré todos los rectángulos según corresponda, y de terminar un rectángulo, se cancelará con la otra esquina del mismo al intentar sumar a la de abajo.
- Recorro el plano y aplico BFS para recorrer por el espacio en el cual no tengo marcado rectángulos, o sea, compuesto de ceros.
- De ser un llamado agujero como está definido en el enunciado, éste no será adyacente con ninguna casilla que se vaya del plano.
- Para obtener la superficie del agujero, hago la suma de la superficie de cada una de las casillas individuales. Para cada una lo obtengo a partir de ver, la diferencia en las coordenadas X e Y que guardé de la compresión de coordenadas antes hecha, para la casilla en cuestión y la que le sigue en el eje correspondiente. Así obtengo alto y ancho reales, pudiendo sacar la superficie como x*y siendo cada uno las diferencias dichas.
- Para ahorrar memoria y tiempo, al pasar por una casilla, la marco también con un 1 para evitar volver a pasar por ella sin necesidad de guardar la información de que pasé aparte.
- Por cada BFS, determinado que es un agujero bajo lo dicho, guardo la superficie obtenida. Luego mostraré la cantidad de superficies obtenidas seguida de tales.
De todos los casos, dos dan TLE y el resto son respuestas incorrectas (aparte de las respuestas correctas). Curiosamente, uno de los TLEs, a medida que fui mejorando ciertas cosas, apareció cuando reemplacé un vector que usaba para marcar las casillas hechas, por el plano en sí como menciono en mi idea. Dicho, con posteriores mejoras no pude hacer bajar en su tiempo de ejecución, mientras que otros TLEs si (hasta reducirlos a los dos que digo que quedan).
Esta idea la estuve trabajando con mi profe de olimpíadas (Brimix__) y me destacó que hasta el momento el problema no tiene ningún envío correcto. Por eso quería preguntar si hay algo raro con los casos de prueba o si hay algún caso o algo que me esté pasando de largo.
Dejo mi código:
Código
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0; i < int(n); i++)
#define forsn(i,s,n) for(int i = int(s); i < int(n); i++)
#define dforn(i,n) for (int i = int(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = int(n)-1; i >= int(s); i--)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
#define MAXN 2*N+2
const int tendX[] = {1,0,-1,0};
const int tendY[] = {0,1,0,-1};
struct point {
ll x,y;
};
struct rectang {
point a,b;
};
vector<ll> X,Y;
vector< pair<point,int> > P; // pto, id
vector<rectang> rectangulos;
vector< vector<int> > plano;
vector<ll> r;
int N;
int update(int e, vector<ll> E) {
return lower_bound(all(E),e) - E.begin();
}
void compress() {
for (auto &i : P) {
X.push_back(i.fst.x);
Y.push_back(i.fst.y);
}
sort(all(X));
X.erase(unique(all(X)),X.end());
sort(all(Y));
Y.erase(unique(all(Y)),Y.end());
for (auto &i : P) {
ll x = i.fst.x, y = i.fst.y;
i.fst.x = update(i.fst.x,X);
i.fst.y = update(i.fst.y,Y);
if (rectangulos[i.snd].a.x == x and rectangulos[i.snd].a.y == y)
rectangulos[i.snd].a = {i.fst.x,i.fst.y};
else
rectangulos[i.snd].b = {i.fst.x,i.fst.y};
}
}
bool esquina(int &x, int &y);
bool valid(int &x, int &y);
ll bfs (int &x, int &y) {
queue<point> Q;
ll totSup = 0;
plano[y][x] = true;
bool posib = true;
Q.push({x,y});
while (not Q.empty()) {
auto e = Q.front(); Q.pop();
totSup += abs(X[e.x]-X[e.x+1])*abs(Y[e.y]-Y[e.y+1]);
forn (i,4) {
int actX = e.x+tendX[i];
int actY = e.y+tendY[i];
if (!valid(actX,actY)) {posib = false; continue;}
if (plano[actY][actX]) continue;
//cerr << actX << ' ' << actY << ' ' << X[actX] << ' ' << Y[actY] << ' ' << X[actX+1] << ' ' << Y[actY+1] << ' ' << X[actX-1] << ' ' << Y[actY-1] << endl;
plano[actY][actX] = true;
Q.push({actX,actY});
}
}
if (posib)
return totSup;
else return -1;
}
int main() {
FAST_IO;
freopen("agujeros.in","r",stdin);
freopen("agujeros.out","w",stdout);
cin >> N;
plano.resize(MAXN,vi(MAXN,false));
forn(i,N) {
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
P.push_back({{x1,y1},rectangulos.size()});
P.push_back({{x2,y2},rectangulos.size()});
rectangulos.push_back({{x1,y1},{x2,y2}});
}
compress();
for (auto &r : rectangulos) {
/*forsn (j, r.a.y, r.b.y)
forsn(k, r.a.x, r.b.x)
plano[j][k] = true;*/
plano[r.a.y][r.a.x]++;
plano[r.a.y][r.b.x]--;
plano[r.b.y][r.a.x]--;
plano[r.b.y][r.b.x]++;
}
forn(y,MAXN) {
int cnt = 0;
forn(x,MAXN) {
int act = plano[y][x];
cnt+=act;
if (y+1 < MAXN)
plano[y+1][x]+=act;
if (act == -1)
plano[y][x] = false;
if (cnt)
plano[y][x] = true;
}
}
/*forn (i,20) {
forn (j,20) {
cout << plano[i][j];
}
cout << endl;
}*/
forn (y,MAXN)
forn (x,MAXN) {
if (plano[y][x]) continue;
ll result = bfs(x,y);
if (result != -1)
r.push_back(result);
}
cout << r.size() << '\n';
sort(all(r));
for (auto &i : r)
cout << i << '\n';
return 0;
}
bool valid(int &x, int &y) {
if (x < 0 or x >= MAXN) return false;
if (y < 0 or y >= MAXN) return false;
return true;
}
. Espero se pueda resolver para que poco a poco el juez sea mejor!