Submission #286040

#	Time	Username	Problem	Language	Result	Execution time	Memory
286040		DanerZein	Rectangles (IOI19_rect)	C++14	50 / 100	1924 ms	362788 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000000
typedef vector<int> vi;
vector<vi> b;
int vis[2510][2510];
int Y[4]={-1,0,1,0};
int X[4]={0,-1,0,1};
int c1,r1,c2,r2;
bool sw1=0;
int flod(int y,int x){
  //cout<<y<<" "<<x<<endl;
  c1=min(c1,x);
  r1=min(r1,y);
  c2=max(c2,x);
  r2=max(r2,y);
  vis[y][x]=1;
  int ans=1;
  for(int i=0;i<4;i++){
    if(y+Y[i]<b.size()-1 and y+Y[i]>=1 and x+X[i]<b[0].size()-1 and x+X[i]>=1){
      if(b[y+Y[i]][x+X[i]]==0 and !vis[y+Y[i]][x+X[i]])
      ans+=flod(y+Y[i],x+X[i]);
    }
    else{
      if(b[y+Y[i]][x+X[i]]==0){
	sw1=1;
      }
    }
  }
  return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
  //cout<<"llamado\n";
  long long c=0;
   if((a.size()<=200 and b.size()<=200) or (a.size()<=3 and b.size()<=2500)){
  //if(c==1){
     //cout<<"if\n";
    for(int i=1;i<a.size()-1;i++){
      for(int j=1;j<a[i].size()-1;j++){
	for(int k=i;k<a.size()-1;k++){
	  for(int l=j;l<a[k].size()-1;l++){
	    bool sw=0;
	    for(int y=i;y<=k;y++){
	      for(int x=j;x<=l;x++){
		if(a[y][x]>=a[y][j-1] or a[y][x]>=a[y][l+1] or a[y][x]>=a[k+1][x] or a[y][x]>=a[i-1][x]){
		  sw=1;
		  break;
		}
	      }
	      if(sw==1) break;
	    }
	    if(sw==0){
	    c++;
	    }
	  }
	}
      }
    }
  }
  else{
    memset(vis,0,sizeof vis);
    b=a;
    // cout<<"else\n";
    for(int i=1;i<a.size()-1;i++){
      for(int j=1;j<a[i].size()-1;j++){
	if(a[i][j]==0 and !vis[i][j]){
	  c1=r1=MAX;
	  c2=r2=-MAX;
	   sw1=0;
	  int ar=flod(i,j);
	  //cout<<i<<" "<<j<<" "<<sw1<<endl;
	  if((abs(c1-c2)+1)*(abs(r1-r2)+1)==ar and sw1==0) c++;
	}
      }
    }
  }
  return c;
}

Compilation message (stderr)

rect.cpp: In function 'int flod(int, int)':
rect.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(y+Y[i]<b.size()-1 and y+Y[i]>=1 and x+X[i]<b[0].size()-1 and x+X[i]>=1){
      |        ~~~~~~^~~~~~~~~~~
rect.cpp:21:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(y+Y[i]<b.size()-1 and y+Y[i]>=1 and x+X[i]<b[0].size()-1 and x+X[i]>=1){
      |                                            ~~~~~~^~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       for(int j=1;j<a[i].size()-1;j++){
      |                   ~^~~~~~~~~~~~~~
rect.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int k=i;k<a.size()-1;k++){
      |              ~^~~~~~~~~~~
rect.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int l=j;l<a[k].size()-1;l++){
      |                ~^~~~~~~~~~~~~~
rect.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |       for(int j=1;j<a[i].size()-1;j++){
      |                   ~^~~~~~~~~~~~~~

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