Submission #832908

#	Time	Username	Problem	Language	Result	Execution time	Memory
832908		Marco_Escandon	Rectangles (IOI19_rect)	C++17	31 / 100	4119 ms	360780 KiB

rect

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define cad a
ll su,iz,de, in;
ll contt;
vector<vector<ll>> v;
ll dfs(ll a, ll b)
{
    if(a==-1||b==-1||a==v.size()||b==v[0].size())
        return false;
    if(v[a][b]==1)
        return true;
    contt++;
    su=min(a,su);
    in=max(a,in);
    iz=min(b,iz);
    de=max(b,de);
    v[a][b]=1;
    ll pl= true;
    if(dfs(a+1,b)==false) pl= false;
    if(dfs(a,b+1)==false) pl= false;
    if(dfs(a-1,b)==false) pl= false;
    if(dfs(a,b-1)==false) pl= false;
    return pl;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    ll n=cad.size(),m=cad[0].size();
    if((n<=30&&m<=30)||n<=3)
    {
        ll cont=0;
        for(int i=1; i<n-1; i++)
        {
            for(int j=1; j<m-1; j++)
            {
                for(int k=i; k<n-1; k++)
                {
                    for(int l=j; l<m-1; l++)
                    {
                        ll pl=0;
                        for(int o=i; o<=k; o++)
                        {
                            for(int p=j; p<=l; p++)
                            {
                                if(cad[i-1][p]<=cad[o][p]||cad[k+1][p]<=cad[o][p]||cad[o][j-1]<=cad[o][p]||cad[o][l+1]<=cad[o][p])
                                {
                                    pl=1;
                                }
                            }
                        }
                        if(pl==0)
                            cont++;
                    }
                }
            }
        }
        return cont;
    }
    ll cont=0;
    v.resize(a.size());
    for(int i=0; i<a.size(); i++)
    {
        v[i].resize(a[i].size());
        for(int j=0; j<a[0].size(); j++)
        {
            v[i][j]=a[i][j];
        }
    }
    for(int i=1; i<a.size()-1; i++)
    {
        for(int j=1; j<a[0].size()-1; j++)
        {
            if(v[i][j]==0)
            {
                su= 1000000;
                in= 0;
                iz=1000000;
                de= 0;
                contt=0;
                if(dfs(i,j)==false) continue;
                //cout<<(in-su+1)*(de-iz+1)<<" ";
                if(contt==(in-su+1)*(de-iz+1))
                {
                    cont++;
                    //cout<<i<<" "<< j<<"\n";
                }

            }
        }
    }
    return cont;
}

Compilation message (stderr)

rect.cpp: In function 'll dfs(ll, ll)':
rect.cpp:10:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(a==-1||b==-1||a==v.size()||b==v[0].size())
      |                      ~^~~~~~~~~~
rect.cpp:10:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(a==-1||b==-1||a==v.size()||b==v[0].size())
      |                                   ~^~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0; i<a.size(); i++)
      |                  ~^~~~~~~~~
rect.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0; j<a[0].size(); j++)
      |                      ~^~~~~~~~~~~~
rect.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=1; i<a.size()-1; i++)
      |                  ~^~~~~~~~~~~
rect.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j=1; j<a[0].size()-1; j++)
      |                      ~^~~~~~~~~~~~~~

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