Buenas, anduve intentando resolver el problema “Peligro de extinción”, más conocido como “Yurumi”. http://juez.oia.unsam.edu.ar/#/task/yurumi/statement
Pude conseguir 79 puntos en el problema con el código que tengo, pero hay dos subtareas que me dan incorrectas. Una es la Subtarea 8, que tira Execution Timed Out, con un tiempo de casi 3 segundos, mientras que el resto de subtareas se resuelven todas en tiempo casi instantáneo, a excepción de una que se resuelve en 1.976 segundos. La Subtarea 13 es la otra que tira incorrecta, pero la diferencia es que esta si entra en tiempo, pero la devolución que hace es “A la superficie le falta 1”.
Paso a comentar mi idea:
Para conseguir el lado del primer cuadrado, hago una binary search, y con esto consigo el cuadrado con el lado más grande que se puede obtener (para chequear que el cuadrado tenga partes que solo sean aprovechables, utilizo una tablita aditiva).
Luego busco ese cuadrado (ya que puede haber más de un cuadrado que se puede obtener con ese lado más grande) y guardo la posición superior izquierda (Fila; Columna) y el tamaño del lado.
Para conseguir el lado del segundo cuadrado, hago una nueva binary search, evaluando que nunca se tengan en cuenta cuadrados en los que alguna de sus celdas formen parte del primer cuadrado.
Al igual que para el primero, busco el segundo cuadrado y guardo la posición superior izquierda (Fila; Columna) y el tamaño del lado.
Finalmente, muestro el output, que sería restarle uno a las filas y columnas de los cuadrados, junto con los lados de cada uno, en las líneas correspondientes.
Dejo acá abajo mi código. Si alguien puede ayudarme a encontrar algún error que yo no esté viendo en mi código, estaré más que agradecido.
Código
#include <bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i = s; i < n; i++)
#define debug(x) cout << #x << " = " << x << endl
bool cuadradoVisitado(vector<vector<bool>> vis, int i, int j, int l){
forsn(a,i,i+l){
forsn(b,j,j+l){
if(vis[a][b]) return true;
}
}
return false;
}
int main() {
ifstream cin("yurumi.in");
ofstream cout("yurumi.out");
int M, N, X;
cin >> N >> M >> X;
vector<vector<int>> mapa(N+1, vector<int> (M+1, 0));
forsn(i,0,X){
int x, y;
cin >> x >> y;
mapa[x][y] = 1;
}
vector<vector<int>> S(N+1, vector<int>(M+1,0));
vector<vector<bool>> vis(N+1, vector<bool>(M+1, false));
forsn(i,1,N+1){
forsn(j,1,M+1){
S[i][j] = mapa[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
}
}
int l = 0, h = N*M;
while(h-l > 1){
int mid = l+(h-l)/2;
bool correcto = false;
forsn(i,1,N+2-mid){
forsn(j,1,M+2-mid){
int k = i + mid - 1, m = j + mid - 1;
if((S[k][m] - S[i-1][m] - S[k][j-1] + S[i-1][j-1]) == 0){
correcto = true;
i = N+2-mid;
j = M+2-mid;
}
}
}
if(correcto) l = mid;
else h = mid;
}
int x1, y1;
forsn(i,1,N+2-l){
forsn(j,1,M+2-l){
int k = i + l - 1, m = j + l - 1;
if((S[k][m] - S[i-1][m] - S[k][j-1] + S[i-1][j-1]) == 0){
x1 = i;
y1 = j;
i = N+2-l;
j = M+2-l;
}
}
}
forsn(a,x1,x1+l){
forsn(b,y1,y1+l){
vis[a][b] = true;
}
}
int lado1 = l;
l = 0;
h = N*M;
while(h-l > 1){
int mid = l+(h-l)/2;
bool correcto = false;
forsn(i,1,N+2-mid){
forsn(j,1,M+2-mid){
int k = i + mid - 1, m = j + mid - 1;
if((S[k][m] - S[i-1][m] - S[k][j-1] + S[i-1][j-1]) == 0 and !cuadradoVisitado(vis, i, j, mid)){
correcto = true;
i = N+2-mid;
j = M+2-mid;
}
}
}
if(correcto) l = mid;
else h = mid;
}
int x2, y2;
forsn(i,1,N+2-l){
forsn(j,1,M+2-l){
int k = i + l - 1, m = j + l - 1;
if((S[k][m] - S[i-1][m] - S[k][j-1] + S[i-1][j-1]) == 0 and !cuadradoVisitado(vis, i, j, l)){
x2 = i;
y2 = j;
i = N+2-l;
j = M+2-l;
}
}
}
cout << x1-1 << " " << y1-1 << " " << lado1 << endl << x2-1 << " " << y2-1 << " " << l << endl;
}
