oj.uz

Submission #1037961

# Submission time Handle Problem Language Result Execution time Memory
1037961 2024-07-29T11:19:26 Z erray Soccer Stadium (IOI23_soccer) C++17
6 / 100
 195 ms 31784 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/egoi2024/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
  int tree_count = 0, one_tree_i, one_tree_j;
  for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
    if (F[i][j]) {
      tree_count++;
      one_tree_i = i, one_tree_j = j;
    }
  }
  if (tree_count <= 1) {
    if (tree_count == 0) return N * N;
    int i = one_tree_i;
    int j = one_tree_j;
    return N * N - min(i + 1, N - i) * min(j + 1, N - j);
  }
  if (N > 500) {
    bool bad = false;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (F[i][j]) {
          if (i > 0 && i < N - 1 && !F[i + 1][j] && !F[i - 1][j]) {
            bad = true;
          }
          if (j > 0 && j < N - 1 && !F[i][j + 1] && !F[i][j - 1]) {
            bad = true;
          }
        }
      }
    }
    vector<int> T(N, -1), B(N, -1), L(N, -1), R(N, -1);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (F[i][j]) continue;
        if (T[j] == -1) T[j] = N - 1 - i;
        if (L[i] == -1) L[i] = N - 1 - j;
        B[j] = i;
        R[i] = j;
      }
    }
    auto Check = [&](vector<int> v) {
      int components = 0;
      for (int i = 0; i < N; ++i) {
        if (v[i] != -1 && (i == 0 || v[i - 1] == -1)) {
          components++;
        }
      }
      if (components > 1) return false;
      for (int i = 1; i < N - 1; ++i) {
        if (v[i] != -1 && v[i - 1] != -1 && v[i + 1] != -1 && v[i] < min(v[i + 1], v[i - 1])) {
          return false;
        }
      }
      return true;
    };
    if (!Check(T) || !Check(B) || !Check(L) || !Check(R) || bad) {
      return 0;
    } else {
      return N * N - tree_count;
    }
  }
    
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^
soccer.cpp:24:46: warning: 'one_tree_j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     return N * N - min(i + 1, N - i) * min(j + 1, N - j);
      |                                            ~~^~~
soccer.cpp:24:26: warning: 'one_tree_i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     return N * N - min(i + 1, N - i) * min(j + 1, N - j);
      |                        ~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 12 ms 2396 KB ok
9 Correct 195 ms 31784 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 1 ms 344 KB partial
4 Partially correct 1 ms 348 KB partial
5 Incorrect 1 ms 348 KB wrong
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 1 ms 344 KB partial
5 Partially correct 1 ms 348 KB partial
6 Incorrect 1 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Partially correct 1 ms 344 KB partial
7 Partially correct 1 ms 348 KB partial
8 Incorrect 1 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Partially correct 1 ms 344 KB partial
7 Partially correct 1 ms 348 KB partial
8 Incorrect 1 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 12 ms 2396 KB ok
10 Correct 195 ms 31784 KB ok
11 Partially correct 1 ms 344 KB partial
12 Partially correct 1 ms 348 KB partial
13 Incorrect 1 ms 348 KB wrong
14 Halted 0 ms 0 KB -