oj.uz

Submission #842270

# Submission time Handle Problem Language Result Execution time Memory
842270 2023-09-02T16:40:19 Z 7mody Soccer Stadium (IOI23_soccer) C++17
8 / 100
 4500 ms 864 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<int>> row;
vector<vector<int>> col;
vector<vector<int>> arr;
int n;

bool check(int x1, int y1, int x2, int y2)
{
    if (x1 == x2)
        return (row[x1][y1] - row[x1][y2] == 0);
    if (y1 == y2)
        return (col[x1][y1] - col[x2][y2] == 0);
    return ((row[x1][y1] - row[x1][y2] == 0 && col[x1][y2] - col[x2][y2] == 0) || (col[x1][y1] - col[x2][y1] == 0 && row[x2][y1] - row[x2][y2] == 0));
}

int biggest_stadium(int N, vector<vector<int>> F)
{
    arr = F;
    n = N;
    int ans = 0;
    row = F;
    col = F;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            row[i][j] += row[i][j - 1];
            col[j][i] += col[j - 1][i];
        }
    }

    // for (auto c : row)
    // {
    //     for (auto g : c)
    //         cout << g << ' ';
    //     cout << endl;
    // }
    // cout << endl;
    // for (auto c : col)
    // {
    //     for (auto g : c)
    //         cout << g << ' ';
    //     cout << endl;
    // }
    // cout << endl;

    queue<pair<int, int>> q;

    for (int i = 0; i < n; i++)
    {
        for (int  j = 0; j < n; j++)
        {
            if (arr[i][j])
                continue;
            q.push({i - 1, j});
            q.push({i, j - 1});
            q.push({i + 1, j});
            q.push({i, j + 1});
            int curr = 1;
            vector<pair<int, int>> found;
            vector<vector<bool>> vis(n, vector<bool>(n));
            vis[i][j] = true;
            found.push_back({i, j});
            while (!q.empty())
            {
                int x = q.front().first, y = q.front().second;
                q.pop();
                bool ok = true;
                if (x == -1 || x == n || y == -1 || y == n )
                    continue;
                if(arr[x][y] || vis[x][y]) continue;
                vis[x][y] = true;
                for (pair<int, int> c : found)
                {
                    if (!check(c.first, c.second, x, y))
                    {
                        ok = false;
                        break;
                    }
                }
                if (!ok)
                    continue;
                found.push_back({x, y});
                curr++;
                // cout << curr << ' ' << x << ' ' << y << endl;
                q.push({x - 1, y});
                q.push({x, y - 1});
                q.push({x + 1, y});
                q.push({x, y - 1});
            }
            ans = max(ans, curr);
        }
    }
    return ans;
}

// void solve()
// {
//     int n;
//     cin >> n;
//     vector<vector<int>> arr(n, vector<int>(n));
//     for (int i = 0; i < n; i++)
//     {
//         for (int j = 0; j < n; j++)
//         {
//             cin >> arr[i][j];
//         }
//     }
//     cout << biggest_stadium(n, arr) << endl;
// }

// int main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie();
//     cout.tie();
//     int t = 1;
//     cin >> t;
//     while (t--)
//     {
//         solve();
//     }
// }

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 600 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 3 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Execution timed out 4550 ms 864 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 600 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 1 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 1 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 1 ms 344 KB ok
16 Partially correct 1 ms 344 KB partial
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 1 ms 544 KB ok
23 Incorrect 1 ms 344 KB wrong
24 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 600 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 3 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 1 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 1 ms 344 KB ok
16 Correct 0 ms 344 KB ok
17 Correct 1 ms 344 KB ok
18 Partially correct 1 ms 344 KB partial
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 1 ms 544 KB ok
25 Incorrect 1 ms 344 KB wrong
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 600 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 3 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 1 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 1 ms 344 KB ok
16 Correct 0 ms 344 KB ok
17 Correct 1 ms 344 KB ok
18 Partially correct 1 ms 344 KB partial
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 1 ms 544 KB ok
25 Incorrect 1 ms 344 KB wrong
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 600 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 3 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Execution timed out 4550 ms 864 KB Time limit exceeded
9 Halted 0 ms 0 KB -