This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pt complex<int>
#define pii pair<int, int>
int N, M;
const int MAX_N = 1001;
vector<pt> points;
char cont[MAX_N][MAX_N];
signed main(){
cin>>N>>M;
vector<vector<int>> col_range(M);
for(int i = 0; i<N; i++){
int a, b;
cin>>a>>b;
points.push_back({a, b});
}
pt prev= points.back();
for(int i = 0; i<N; i++){
pt edge = points[i]-prev;
if(edge.imag() == 0){
pii range = {min(points[i].real(), prev.real()), max(points[i].real(), prev.real())};
for(int j = range.first; j<range.second; j++){
col_range[j].push_back(points[i].imag());
}
}
prev= points[i];
}
for(int i = 0; i<M; i++){
sort(col_range[i].begin(), col_range[i].end());
int line_id = 0;
for(int j = 0; j<MAX_N; j++){
while(line_id<col_range[i].size() && col_range[i][line_id]<=j){
line_id++;
}
if(line_id%2 == 0){
cont[i][j] = '.';
}
else{
cont[i][j] = '#';
}
//cout<<cont[i][j]<<" ";
}
//cout<<endl;
}
for(int i = 0; i<M; i++){
for(int j = 0; j<MAX_N; j++){
if(cont[i][j]=='#' && cont[i+1][j]=='#' && cont[i][j+1]=='#' && cont[i+1][j+1]=='#'){
cont[i][j] = ',';
cont[i+1][j] = '.';
cont[i][j+1] = ',';
cont[i+1][j+1] = '.';
}
//cout<<cont[i][j]<<" ";
}
//cout<<endl;
}
int k =0;
bool no_left = false;
for(int i = 0; i<M; i++){
bool all_points = true;
for(int j = 0; j<MAX_N; j++){
all_points &= cont[i][j] == '.';
no_left |= cont[i][j] == '#';
}
if(all_points && !no_left){
k = max(k, i+1);
}
}
cout<<k<<endl;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:40:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | while(line_id<col_range[i].size() && col_range[i][line_id]<=j){
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |