Submission #1240600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240600		mychecksedad	Soccer Stadium (IOI23_soccer)	C++17	29.50 / 100	755 ms	314660 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define cerr if(0) cerr
const int N = 2005, M = 3e5;

int arr[4][2] = {
  {0, 1},
  {0, -1},
  {1, 0},
  {-1, 0}
};
bitset<N> vis[N];
vector<pii> g[N][N];
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
  int cnt = 0, px = 0, py = 0;
  queue<pii> q;
  bool any = false;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i][j] == 0){
        if(!any){
          any = true;
          q.push({i, j});
          vis[i][j] = 1;
        }
        for(int k = 0; k < 4; ++k){
          int nx = i + arr[k][0];
          int ny = j + arr[k][1];
          if(nx >= 0 && ny < n && ny >= 0 && nx < n && a[nx][ny] == 0){
            g[i][j].pb({nx, ny});
          }
        }
      }else{
        ++cnt;
        px = i, py = j;
      }
    }
  }
  if(cnt == 0){
    return n * n;
  }
  if(cnt == 1){
    return n*n - min({
      (px + 1) * (py + 1),
      (px + 1) * (n - py),
      (n - px) * (n - py),
      (n - px) * (py + 1),
    });
  }
  int sz = 0;
  while(!q.empty()){
    int x = q.front().ff;
    int y = q.front().ss;
    q.pop();
    ++sz;
    for(auto [ux, uy]: g[x][y]){
      if(!vis[ux][uy]){
        vis[ux][uy] = 1;
        q.push({ux, uy});
      }
    }
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(!vis[i][j] && !a[i][j]){
        return 0;
      }
    }
  }
  vector<pii> R;
  for(int i = 0; i < n; ++i){
    int l = n, r = -2;
    for(int j = 0; j < n; ++j){
      if(!a[i][j]) l = min(l, j);
      if(!a[i][j]){
        if(r != -2 && r < j - 1) return 0;
        r = max(r, j);
      }
    }
    if(l < n){
      R.pb({l, r});
    }
  }
  for(int i = 0; i < n; ++i){
    int l = n, r = -2;
    for(int j = 0; j < n; ++j){
      if(!a[j][i]) l = min(l, j);
      if(!a[j][i]){
        if(r != -2 && r < j - 1) return 0;
        r = max(r, j);
      }
    }
  }
  for(auto [lx, rx]: R){
    for(auto [ly, ry]: R){
      if(lx <= ly && ry <= rx) continue;
      if(ly <= lx && rx <= ry) continue;
      return 0;
    }
  }
  return sz;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 2 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 4 / 16
• Subtask 6: 7.5 / 30