Submission #1018305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018305		tmarcinkevicius	Soccer Stadium (IOI23_soccer)	C++17	29.50 / 100	265 ms	47696 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define f first
#define s second

bool CheckIfStadium(int N, vector<vector<int>> F)
{
    pii minRow, maxRow;
    bool possible = true;
    int state = 0;
    int fullCount = 0;
    vector<pii> rows;
    pii prev;

    for (int i = 0; i < N; i++)
    {
        int start = N;
        int end = 0;
        int openCount = 0;
        for (int j = 0; j < N; j++)
        {
            if (F[i][j] == 0)
            {
                fullCount++;
                if (openCount == 0)
                {
                    openCount++;
                }
                else if (openCount == 2)
                {
                    openCount++;
                    break;
                }
                start = min(start, j);
                end = max(end, j);
            }
            else
            {
                if (openCount == 1)
                {
                    openCount++;
                }
            }
        }

        // cout << "i = " << i << ", {" << start << ", " << end << "}, cnt = " << openCount << '\n';

        if (openCount >= 3)
        {
            possible = false;
        }

        for (pii p : rows)
        {
            if (!((start <= p.f && end >= p.s) || (start >= p.f && end <= p.s)))
            {
                possible = false;
                break;
            }
        }

        if (!possible)
            break;

        rows.push_back({start, end});

        if (i == 0)
        {
            minRow = {start, end};
            maxRow = {start, end};

            prev = {start, end};
            continue;
        }

        // cout << "min: {" << minRow.f << ", " << minRow.s << "}, max: {" << maxRow.f << ", " << maxRow.s << "}\n";

        if (state == 0 && start <= maxRow.f && end >= maxRow.s)
        {
            maxRow = {start, end};

            prev = {start, end};
            continue;
        }
        else if (start >= prev.f && end <= prev.s && ((start >= minRow.f && end <= minRow.s) || (start <= minRow.f && end >= minRow.s)))
        {
            state = 1;
            minRow = {max(minRow.f, start), min(minRow.s, end)};

            prev = {start, end};
            continue;
        }

        possible = false;
        break;
    }

    return possible;
}

int biggest_stadium(int N, vector<vector<int>> F)
{

    bool isStadium = CheckIfStadium(N, F);
    int treeCount = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            treeCount += F[i][j];
        }
    }

    if (isStadium)
    {
        return N * N - treeCount;
    }
    else
    {
        if (treeCount == 1)
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (!F[i][j])
                        continue;

                    int ans = N * N;
                    ans -= min(i + 1, N - i) * min(j + 1, N - j);
                    return ans;
                }
            }
        }

        return 0;
    }
}

int biggest_stadium2(int N, vector<vector<int>> F)
{
    vector<vector<int>> prefixLine(N), prefixCol(N);

    for (int i = 0; i < N; i++)
    {
        prefixLine[i] = vector<int>(N, 0);

        prefixLine[i][0] = F[i][0];

        for (int j = 1; j < N; j++)
        {
            prefixLine[i][j] = prefixLine[i][j - 1] + F[i][j];
        }
    }

    for (int i = 0; i < N; i++)
    {
        prefixCol[i] = vector<int>(N, 0);

        prefixCol[i][0] = F[0][i];

        for (int j = 1; j < N; j++)
        {
            prefixCol[i][j] = prefixCol[i][j - 1] + F[j][i];
        }
    }

    set<pii> freeCells;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (F[i][j] == 0)
            {
                freeCells.insert({i, j});
            }
        }
    }

    bool possible = true;
    for (pii p1 : freeCells)
    {
        for (pii p2 : freeCells)
        {
            if (p1 == p2)
                continue;

            if (p1.f == p2.f)
            {
                int sum = prefixLine[p1.f][max(p1.s, p2.s)];

                if (min(p1.s, p2.s) > 0)
                {
                    sum -= prefixLine[p1.f][min(p1.s, p2.s) - 1];
                }
                if (sum != 0)
                {
                    // cout << "{" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
                    possible = false;
                    break;
                }
            }
            else if (p1.s == p2.s)
            {
                int sum = prefixCol[p1.s][max(p1.f, p2.f)];

                if (min(p1.f, p2.f) > 0)
                {
                    sum -= prefixCol[p1.s][min(p1.f, p2.f) - 1];
                }
                if (sum != 0)
                {
                    // cout << "{" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
                    possible = false;
                    break;
                }
            }
            else
            {
                // cout << "check {" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
                int sum1 = prefixLine[p1.f][max(p1.s, p2.s)] + prefixCol[p2.s][max(p1.f, p2.f)];
                int sum2 = prefixLine[p2.f][max(p1.s, p2.s)] + prefixCol[p1.s][max(p1.f, p2.f)];

                if (min(p1.s, p2.s) > 0)
                {
                    sum1 -= prefixLine[p1.f][min(p1.s, p2.s) - 1];
                    sum2 -= prefixLine[p2.f][min(p1.s, p2.s) - 1];
                }
                if (min(p1.f, p2.f) > 0)
                {
                    sum1 -= prefixCol[p2.s][min(p1.f, p2.f) - 1];
                    sum2 -= prefixCol[p1.s][min(p1.f, p2.f) - 1];
                }

                // cout << "sums: " << sum1 << " " << sum2 << '\n';
                // cout << "s1: " << prefixLine[p1.f][max(p1.s, p2.s)] - prefixLine[p1.f][min(p1.s, p2.s)] << '\n';

                if (sum1 != 0 && sum2 != 0)
                {
                    // cout << "{" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
                    possible = false;
                    break;
                }
            }
        }

        if (!possible)
            break;
    }

    if (possible)
    {
        return freeCells.size();
    }
    else
    {
        return 0;
    }
}

// int main()
// {
//     int count = 0;
//     for (int num = 0; num < (1 << 25); num++)
//     {
//         if (num % 100 == 0)
//         {
//             cout << "----" << num << '\n';
//         }
//         vector<vector<int>> vec(5);
//         bitset<25> bSet(num);

//         for (int i = 0; i < 5; i++)
//         {
//             vec[i] = vector<int>(5);
//             for (int j = 0; j < 5; j++)
//             {
//                 vec[i][j] = bSet[5 * i + j];
//             }
//         }

//         int res = biggest_stadium(5, vec);
//         int res2 = biggest_stadium2(5, vec);

//         if (res != res2)
//         {
//             cout << "\nfound: " << count << '\n';
//             count++;
//             for (int i = 0; i < 5; i++)
//             {
//                 for (int j = 0; j < 5; j++)
//                 {
//                     cout << vec[i][j];
//                 }
//                 cout << '\n';
//             }

//             cout << "different: " << res << " " << res2 << '\n';
//             return 0;
//         }
//     }
// }

• 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