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>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;
pair<int, int> gore[3000][3000], dole[3000][3000], levo[3000][3000], deso[3000][3000];
int n;
vector<pair<int, int>> granica;
int stadsize(int x, int y) {
if(gore[x][y]==mp(x, y)) return 0;
int maxgore=gore[x][y].yy;
int mindole=dole[x][y].yy;
int rez=0;
for(int i=0; true; i++) {
if(x+i>n||gore[x+i][y]==mp(x+i, y)) break;
maxgore=max(maxgore, gore[x+i][y].yy);
mindole=min(mindole, dole[x+i][y].yy);
granica.pb(mp(gore[x+i][y].xx, gore[x+i][y].yy+1));
granica.pb(mp(dole[x+i][y].xx, dole[x+i][y].yy-1));
rez+=-maxgore+mindole-1;
}
maxgore=gore[x][y].yy;
mindole=dole[x][y].yy;
for(int i=-1; true; i--) {
if(x+i<1||gore[x+i][y]==mp(x+i, y)) break;
maxgore=max(maxgore, gore[x+i][y].yy);
mindole=min(mindole, dole[x+i][y].yy);
granica.pb(mp(gore[x+i][y].xx, gore[x+i][y].yy+1));
granica.pb(mp(dole[x+i][y].xx, dole[x+i][y].yy-1));
rez+=-maxgore+mindole-1;
}
return rez;
}
int cx, cy, lx, dx, gy, dy, mxg, myl, mxd, myd, X, Y;
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
{
for(int i=1; i<=N; i++) {
if(F[i-1][0]) gore[i][1]=mp(i, 1);
else gore[i][1]=mp(i, 0);
}
for(int i=2; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(F[j-1][i-1]) gore[j][i]=mp(j, i);
else gore[j][i]=gore[j][i-1];
}
}
for(int i=1; i<=N; i++) {
if(F[i-1][N-1]) dole[i][N]=mp(i, N);
else dole[i][N]=mp(i, N+1);
}
for(int i=N-1; i>0; i--) {
for(int j=1; j<=N; j++) {
if(F[j-1][i-1]) dole[j][i]=mp(j, i);
else dole[j][i]=dole[j][i+1];
}
}
for(int i=1; i<=N; i++) {
if(F[0][i-1]) levo[1][i]=mp(1, i);
else levo[1][i]=mp(0, i);
}
for(int i=2; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(F[i-1][j-1]) levo[i][j]=mp(i, j);
else levo[i][j]=levo[i-1][j];
}
}
for(int i=1; i<=N; i++) {
if(F[N-1][i-1]) deso[N][i]=mp(N, i);
else deso[N][i]=mp(N+1, i);
}
for(int i=N-1; i>0; i--) {
for(int j=1; j<=N; j++) {
if(F[i-1][j-1]) deso[i][j]=mp(i, j);
else deso[i][j]=deso[i+1][j];
}
}
}
n=N;
lx=N-1;
dx=0;
gy=N-1;
dy=0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(!F[i][j]) {
lx=min(lx, i);
dx=max(dx, i);
gy=min(gy, j);
dy=min(dy, j);
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(!F[i][j]) {
if(i==lx) {
myl=max(myl, j);
}
if(i==dx) {
myd=max(myd, j);
}
if(j==gy) {
mxg=max(mxg, i);
}
if(j==dy) {
mxd=max(mxd, i);
}
}
}
}
X=min(mxg, mxd);
Y=min(myl, myd);
bool b1=false ,b2=false, b3=false ,b4=false;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(!F[i][j]) {
if(i==lx) {
if(j<=Y) b1=true;
}
if(i==dx) {
if(j<=Y) b2=true;
}
if(j==gy) {
if(i<=X) b3=true;
}
if(j==dy) {
if(i<=X) b4=true;
}
}
}
}
if(!(b1&&b2&&b3&&b4)) return 0;
int prazna=0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) if(!F[i][j]) prazna++;
}
if(prazna!=stadsize(X+1, Y+1)) return 0;
for(int i=0; i<granica.size(); i++) {
for(int j=i+1; j<granica.size(); j++) {
if(F[granica[i].xx-1][granica[j].yy-1]&&F[granica[j].xx-1][granica[i].yy-1]) return 0;
}
}
return prazna;
}
Compilation message (stderr)
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:146:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i=0; i<granica.size(); i++) {
| ~^~~~~~~~~~~~~~~
soccer.cpp:147:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int j=i+1; j<granica.size(); 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... |