oj.uz

Submission #966796

# Submission time Handle Problem Language Result Execution time Memory
966796 2024-04-20T11:34:59 Z VMaksimoski008 Soccer Stadium (IOI23_soccer) C++17
14 / 100
 4500 ms 31780 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    int cnt = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) cnt += (F[i][j] == 1);

    if(!cnt) return N * N;

    if(cnt == 1) {
        int x=0, y=0;
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                if(F[i][j] == 1) x = i, y = j;

        return N * N - min({ (x + 1) * (y + 1), (N - x) * (y + 1), (x + 1) * (N - y), (N - x) * (N - y) });
    }

    if(N <= 3) {
        int ans = 0, n = N;

        int mat[N+1][N+1];
        vector<vector<int> > ver(n+1, vector<int>(n+1));
        vector<vector<int> > hor(n+1, vector<int>(n+1));
        memset(mat, 0, sizeof(mat));
        for(int i=1; i<=N; i++)
            for(int j=1; j<=N; j++) mat[i][j] = F[i-1][j-1];

        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++) hor[i][j] = hor[i][j-1] + mat[i][j];
        for(int j=1; j<=n; j++)
            for(int i=1; i<=n; i++) ver[j][i] = ver[j][i-1] + mat[i][j];

        vector<pair<int, int> > v;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++) if(!mat[i][j]) v.push_back({ i, j });
        sort(v.begin(), v.end());

        auto queryHor = [&](int row, int i, int j) {
            return hor[row][max(i, j)] - hor[row][min(i, j)-1];
        };

        auto queryVer = [&](int col, int i, int j) {
            return ver[col][max(i, j)] - ver[col][min(i, j)-1];
        };

        int m = v.size();
        for(int s=0; s<(1<<m); s++) {
            if(__builtin_popcount(s) <= ans) continue;
            bool ok = 1;

            for(int i=0; i<m; i++) {
                if((s & (1 << i)) == 0) continue;
                for(int j=i+1; j<m; j++) {
                    if((s & (1 << j)) == 0) continue;
                    bool ok1=1, ok2=1;

                    if(v[i].first == v[j].first) {
                        int x = max(v[j].second, v[i].second), y = min(v[j].second, v[i].second);
                        int p = hor[v[i].first][x] - hor[v[i].first][y-1];
                        
                        if(p) {
                            ok1 = 0;
                            ok2 = 0;
                            ok = 0;
                            break;
                        }
                    }

                    if(v[i].second == v[j].second) {
                        int x = max(v[j].first, v[i].first), y = min(v[j].first, v[i].first);
                        int p = ver[v[i].second][x] - ver[v[i].second][y-1];

                        if(p) {
                            ok1 = 0;
                            ok2 = 0;
                            ok = 0;
                            break;
                        }
                    }

                    if(v[i].first != v[j].first && v[i].second != v[j].second) {
                        pair<int, int> a = v[i];
                        pair<int, int> b = v[j];
                        if(a.first > b.first) swap(a, b);

                        //right-UD
                        if(queryHor(a.first, a.second, b.second) || queryVer(b.second, a.first, b.first)) ok1 = 0;

                        //UP-right
                        if(queryVer(a.second, a.first, b.first) || queryHor(b.first, a.second, b.second)) ok2 = 0;
                    }

                    if(!ok1 && !ok2) {
                        ok = 0;
                        break;
                    }
                }
            }

            if(ok) ans = max(ans, __builtin_popcount(s));
        }

        return ans;
    }
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 15 ms 2204 KB ok
9 Correct 232 ms 31780 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 436 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 436 KB ok
15 Partially correct 1 ms 544 KB partial
16 Partially correct 2 ms 348 KB partial
17 Partially correct 1 ms 348 KB partial
18 Execution timed out 4552 ms 348 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 436 KB ok
17 Partially correct 1 ms 544 KB partial
18 Partially correct 2 ms 348 KB partial
19 Partially correct 1 ms 348 KB partial
20 Execution timed out 4552 ms 348 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 436 KB ok
17 Partially correct 1 ms 544 KB partial
18 Partially correct 2 ms 348 KB partial
19 Partially correct 1 ms 348 KB partial
20 Execution timed out 4552 ms 348 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 15 ms 2204 KB ok
10 Correct 232 ms 31780 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 436 KB ok
22 Partially correct 1 ms 544 KB partial
23 Partially correct 2 ms 348 KB partial
24 Partially correct 1 ms 348 KB partial
25 Execution timed out 4552 ms 348 KB Time limit exceeded
26 Halted 0 ms 0 KB -