oj.uz

답안 #1072152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072152 2024-08-23T14:58:14 Z Mihailo 축구 경기장 (IOI23_soccer) C++17
0 / 100
 1 ms 452 KB 
#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+1][y].yy+1));
        granica.pb(mp(dole[x+i][y].xx, dole[x+1][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+1][y].yy+1));
        granica.pb(mp(dole[x+i][y].xx, dole[x+1][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

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++) {
      |                        ~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB partial

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 452 KB wrong
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 452 KB wrong
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB partial
2 Incorrect 1 ms 452 KB wrong
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB partial
2 Incorrect 1 ms 452 KB wrong
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB partial
2 Incorrect 1 ms 452 KB wrong
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB partial
2 Incorrect 1 ms 452 KB wrong
3 Halted 0 ms 0 KB -