Submission #386506

#	Time	Username	Problem	Language	Result	Execution time	Memory
386506		vanic	Bomb (IZhO17_bomb)	C++14	23 / 100	1106 ms	127208 KiB

bomb

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <array>
#include <bitset>
#include <cassert>
 
using namespace std;
 
const int maxn=2505;
 
bitset < maxn > a[maxn];
bitset < maxn > bio[maxn];
int dist1[maxn][maxn];
int dist2[maxn][maxn];
int pref[maxn][maxn];
int uk;
int n, m;
 
bool provjeri(int x, int y){
	for(int i=0; i<n; i++){
		bio[i].reset();
	}
	int val;
	queue < pair < int, int > > q;
	int br=0;
	for(int i=0; i<=n-x; i++){
		for(int j=0; j<=m-y; j++){
			val=pref[i+x][j+y]-pref[i][j+y]-pref[i+x][j]+pref[i][j];
			if(val==x*y){
				br++;
				q.push({i, j});
				dist1[i][j]=0;
				dist2[i][j]=0;
				bio[i][j]=1;
			}
		}
	}
	pair < int, int > p;
	int xs, ys;
//	cout << "pocetak " << x << ' ' << y << endl;
	while(!q.empty()){
		p=q.front();
		q.pop();
		xs=p.first+1;
		ys=p.second;
		if(!bio[xs][ys] && dist1[p.first][p.second]+1<x){
			br++;
			bio[xs][ys]=1;
			dist1[xs][ys]=dist1[p.first][p.second]+1;
			dist2[xs][ys]=dist2[p.first][p.second];
			
			q.push({xs, ys});
		}
		xs=p.first;
		ys=p.second+1;
		if(!bio[xs][ys] && dist2[p.first][p.second]+1<y){
			br++;
			bio[xs][ys]=1;
			dist1[xs][ys]=dist1[p.first][p.second];
			dist2[xs][ys]=dist2[p.first][p.second]+1;
			q.push({xs, ys});
		}
	}
//	cout << br << endl;
	return br==uk;
}

int binary(int hi, int val){
	int lo=1, mid;
//	cout << lo << ' ' << hi << endl;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(provjeri(val, mid)){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	return lo;
}

int ternary(int hi, int hi1){
	int lo=1, mid;
//	cout << lo << ' ' << hi << endl;
	while(lo<hi){
		mid=(lo+hi)/2;
//		cout << mid << endl;
		if(binary(hi1, mid)*mid<binary(hi1, mid+1)*(mid+1)){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo*binary(hi1, lo);
}

vector < array < int, 3 > > svi;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	string s;
	for(int i=0; i<n; i++){
		cin >> s;
		for(int j=0; j<m; j++){
			pref[i+1][j+1]=pref[i][j+1]+pref[i+1][j]-pref[i][j];
			if(s[j]=='1'){
				pref[i+1][j+1]++;
				uk++;
				a[i][j]=1;
			}
		}
	}
	int br=0;
	int mr=1e9, mc=1e9;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(a[i][j]){
				br++;
			}
			else if(br){
				mr=min(mr, br);
				br=0;
			}
		}
		if(br){
			mr=min(mr, br);
			br=0;
		}
	}
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			if(a[i][j]){
				br++;
			}
			else if(br){
				mc=min(mc, br);
				br=0;
			}
		}
		if(br){
			mc=min(mc, br);
			br=0;
		}
	}
	assert(mr!=1e9);
	for(int i=mc; i>0; i--){
		for(int j=mr; j>0; j--){
			svi.push_back({i*j, i, j});
		}
	}
	sort(svi.begin(), svi.end());
	cout << ternary(mc, mr) << '\n';
/*	for(int i=svi.size()-1; i>-1; i--){
		if(provjeri(svi[i][1], svi[i][2])){
			cout << svi[i][0] << '\n';
			return 0;
		}
	}*/
	return 0;
}

• Subtask 1: 23 / 100