Submission #667331

#	Time	Username	Problem	Language	Result	Execution time	Memory
667331		coding_snorlax	Rectangles (IOI19_rect)	C++14	13 / 100	1088 ms	591836 KiB

rect

#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
int n,m;
int List[2505][2505];
int vis[2505][2505]={0};
vector<pair<int,int>> tmp;
int flag=1;
int Move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y){
    if( x==0 || y==0 || x==n || y==m){
        flag=0;
        return;
    }
    vis[x][y]=1;
    tmp.push_back(make_pair(x,y));
    for(int i=0;i<4;i++){
        if(!vis[x+Move[i][0]][y+Move[i][1]] && List[x+Move[i][0]][y+Move[i][1]]==0) dfs(x+Move[i][0],y+Move[i][1]);
    }
}
long long int count_rectangles(vector<vector<int>> a){
    n=a.size();
    m=a[0].size();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            List[i][j]=a[i][j];
        }
    }
    long long int answer=0;
    for(int i=1;i<n-1;i++){
        for(int j=1;j<m-1;j++){
            if(!vis[i][j] && a[i][j]==0){
                flag=1;
                tmp.clear();
                dfs(i,j);
                sort(tmp.begin(),tmp.end());
                int flag2=1;
                /*
                cout<<"---\n";
                for(int i=0;i<(int)tmp.size();i++){
                    cout<<tmp[i].first<<" "<<tmp[i].second<<endl;
                }
                cout<<endl;
                cout<<flag<<" "<<flag2<<" \n";
                cout<<"---\n";
                */
                if(((tmp[(int)tmp.size()-1].first-tmp[0].first+1)*(tmp[(int)tmp.size()-1].second-tmp[0].second+1))==(int)tmp.size() && flag){
                    for(int i=0;i<(int)tmp.size();i++){
                        if((tmp[i].second>tmp[(int)tmp.size()-1].second) || (tmp[i].second<tmp[0].second)) flag2=0;
                    }
                    if(flag2) answer++;
                }
            }
        }
    }
    return answer;
}

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