답안 #1018296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1018296	2024-07-09T18:23:56 Z	tmarcinkevicius	축구 경기장 (IOI23_soccer)	C++17	25 / 100	223 ms	39760 KB

soccer

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


int biggest_stadium(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;
    }

    if (possible)
    {
        return fullCount;
    }
    else
    {
        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 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	348 KB	partial

Subtask #1
1.5 / 6.0

#	결과	실행 시간	메모리	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	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Partially correct	0 ms	348 KB	partial
7	Partially correct	1 ms	348 KB	partial
8	Partially correct	12 ms	2396 KB	partial
9	Partially correct	208 ms	31764 KB	partial

Subtask #2
2.0 / 8.0

#	결과	메모리	Grader output
1	Correct	348 KB	ok
2	Correct	348 KB	ok
3	Partially correct	348 KB	partial
4	Partially correct	348 KB	partial
5	Partially correct	348 KB	partial
6	Partially correct	348 KB	partial
7	Partially correct	348 KB	partial
8	Correct	348 KB	ok
9	Correct	348 KB	ok
10	Partially correct	344 KB	partial
11	Partially correct	348 KB	partial
12	Partially correct	348 KB	partial
13	Correct	348 KB	ok

Subtask #3
5.5 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	348 KB	partial
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Partially correct	0 ms	348 KB	partial
5	Partially correct	0 ms	348 KB	partial
6	Partially correct	0 ms	348 KB	partial
7	Partially correct	0 ms	348 KB	partial
8	Partially correct	0 ms	348 KB	partial
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Partially correct	0 ms	344 KB	partial
12	Partially correct	0 ms	348 KB	partial
13	Partially correct	0 ms	348 KB	partial
14	Correct	0 ms	348 KB	ok
15	Partially correct	0 ms	348 KB	partial
16	Partially correct	0 ms	348 KB	partial
17	Partially correct	0 ms	344 KB	partial
18	Partially correct	1 ms	348 KB	partial
19	Partially correct	0 ms	348 KB	partial
20	Correct	0 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Partially correct	0 ms	348 KB	partial
23	Partially correct	0 ms	348 KB	partial
24	Partially correct	0 ms	348 KB	partial
25	Partially correct	1 ms	348 KB	partial
26	Partially correct	0 ms	348 KB	partial

Subtask #4
4.5 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	348 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	0 ms	348 KB	ok
6	Partially correct	0 ms	348 KB	partial
7	Partially correct	0 ms	348 KB	partial
8	Partially correct	0 ms	348 KB	partial
9	Partially correct	0 ms	348 KB	partial
10	Partially correct	0 ms	348 KB	partial
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Partially correct	0 ms	344 KB	partial
14	Partially correct	0 ms	348 KB	partial
15	Partially correct	0 ms	348 KB	partial
16	Correct	0 ms	348 KB	ok
17	Partially correct	0 ms	348 KB	partial
18	Partially correct	0 ms	348 KB	partial
19	Partially correct	0 ms	344 KB	partial
20	Partially correct	1 ms	348 KB	partial
21	Partially correct	0 ms	348 KB	partial
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Partially correct	0 ms	348 KB	partial
25	Partially correct	0 ms	348 KB	partial
26	Partially correct	0 ms	348 KB	partial
27	Partially correct	1 ms	348 KB	partial
28	Partially correct	0 ms	348 KB	partial
29	Partially correct	1 ms	344 KB	partial
30	Partially correct	0 ms	348 KB	partial
31	Partially correct	0 ms	348 KB	partial
32	Partially correct	0 ms	348 KB	partial
33	Partially correct	0 ms	348 KB	partial
34	Correct	0 ms	348 KB	ok
35	Correct	0 ms	348 KB	ok
36	Partially correct	0 ms	348 KB	partial
37	Partially correct	0 ms	348 KB	partial
38	Partially correct	0 ms	348 KB	partial
39	Partially correct	0 ms	348 KB	partial
40	Partially correct	0 ms	348 KB	partial
41	Partially correct	0 ms	348 KB	partial

Subtask #5
4.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	348 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	0 ms	348 KB	ok
6	Partially correct	0 ms	348 KB	partial
7	Partially correct	0 ms	348 KB	partial
8	Partially correct	0 ms	348 KB	partial
9	Partially correct	0 ms	348 KB	partial
10	Partially correct	0 ms	348 KB	partial
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Partially correct	0 ms	344 KB	partial
14	Partially correct	0 ms	348 KB	partial
15	Partially correct	0 ms	348 KB	partial
16	Correct	0 ms	348 KB	ok
17	Partially correct	0 ms	348 KB	partial
18	Partially correct	0 ms	348 KB	partial
19	Partially correct	0 ms	344 KB	partial
20	Partially correct	1 ms	348 KB	partial
21	Partially correct	0 ms	348 KB	partial
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Partially correct	0 ms	348 KB	partial
25	Partially correct	0 ms	348 KB	partial
26	Partially correct	0 ms	348 KB	partial
27	Partially correct	1 ms	348 KB	partial
28	Partially correct	0 ms	348 KB	partial
29	Partially correct	1 ms	344 KB	partial
30	Partially correct	0 ms	348 KB	partial
31	Partially correct	0 ms	348 KB	partial
32	Partially correct	0 ms	348 KB	partial
33	Partially correct	0 ms	348 KB	partial
34	Correct	0 ms	348 KB	ok
35	Correct	0 ms	348 KB	ok
36	Partially correct	0 ms	348 KB	partial
37	Partially correct	0 ms	348 KB	partial
38	Partially correct	0 ms	348 KB	partial
39	Partially correct	0 ms	348 KB	partial
40	Partially correct	0 ms	348 KB	partial
41	Partially correct	0 ms	348 KB	partial
42	Partially correct	12 ms	2904 KB	partial
43	Partially correct	12 ms	2692 KB	partial
44	Partially correct	12 ms	2908 KB	partial
45	Partially correct	12 ms	2904 KB	partial
46	Partially correct	12 ms	2908 KB	partial
47	Partially correct	23 ms	2688 KB	partial
48	Correct	22 ms	2692 KB	ok
49	Partially correct	12 ms	2904 KB	partial
50	Partially correct	16 ms	2908 KB	partial
51	Partially correct	12 ms	2904 KB	partial
52	Partially correct	12 ms	2700 KB	partial
53	Partially correct	24 ms	2908 KB	partial
54	Partially correct	13 ms	2820 KB	partial
55	Partially correct	19 ms	2908 KB	partial
56	Partially correct	12 ms	2824 KB	partial
57	Partially correct	12 ms	2904 KB	partial
58	Partially correct	12 ms	2904 KB	partial
59	Partially correct	13 ms	2908 KB	partial

Subtask #6
7.5 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	348 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	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Partially correct	0 ms	348 KB	partial
8	Partially correct	1 ms	348 KB	partial
9	Partially correct	12 ms	2396 KB	partial
10	Partially correct	208 ms	31764 KB	partial
11	Partially correct	0 ms	348 KB	partial
12	Partially correct	0 ms	348 KB	partial
13	Partially correct	0 ms	348 KB	partial
14	Partially correct	0 ms	348 KB	partial
15	Partially correct	0 ms	348 KB	partial
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Partially correct	0 ms	344 KB	partial
19	Partially correct	0 ms	348 KB	partial
20	Partially correct	0 ms	348 KB	partial
21	Correct	0 ms	348 KB	ok
22	Partially correct	0 ms	348 KB	partial
23	Partially correct	0 ms	348 KB	partial
24	Partially correct	0 ms	344 KB	partial
25	Partially correct	1 ms	348 KB	partial
26	Partially correct	0 ms	348 KB	partial
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	348 KB	ok
29	Partially correct	0 ms	348 KB	partial
30	Partially correct	0 ms	348 KB	partial
31	Partially correct	0 ms	348 KB	partial
32	Partially correct	1 ms	348 KB	partial
33	Partially correct	0 ms	348 KB	partial
34	Partially correct	1 ms	344 KB	partial
35	Partially correct	0 ms	348 KB	partial
36	Partially correct	0 ms	348 KB	partial
37	Partially correct	0 ms	348 KB	partial
38	Partially correct	0 ms	348 KB	partial
39	Correct	0 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Partially correct	0 ms	348 KB	partial
42	Partially correct	0 ms	348 KB	partial
43	Partially correct	0 ms	348 KB	partial
44	Partially correct	0 ms	348 KB	partial
45	Partially correct	0 ms	348 KB	partial
46	Partially correct	0 ms	348 KB	partial
47	Partially correct	12 ms	2904 KB	partial
48	Partially correct	12 ms	2692 KB	partial
49	Partially correct	12 ms	2908 KB	partial
50	Partially correct	12 ms	2904 KB	partial
51	Partially correct	12 ms	2908 KB	partial
52	Partially correct	23 ms	2688 KB	partial
53	Correct	22 ms	2692 KB	ok
54	Partially correct	12 ms	2904 KB	partial
55	Partially correct	16 ms	2908 KB	partial
56	Partially correct	12 ms	2904 KB	partial
57	Partially correct	12 ms	2700 KB	partial
58	Partially correct	24 ms	2908 KB	partial
59	Partially correct	13 ms	2820 KB	partial
60	Partially correct	19 ms	2908 KB	partial
61	Partially correct	12 ms	2824 KB	partial
62	Partially correct	12 ms	2904 KB	partial
63	Partially correct	12 ms	2904 KB	partial
64	Partially correct	13 ms	2908 KB	partial
65	Partially correct	204 ms	39444 KB	partial
66	Partially correct	198 ms	39504 KB	partial
67	Partially correct	190 ms	39572 KB	partial
68	Partially correct	190 ms	39504 KB	partial
69	Partially correct	183 ms	39508 KB	partial
70	Partially correct	196 ms	39504 KB	partial
71	Partially correct	188 ms	39508 KB	partial
72	Partially correct	192 ms	39504 KB	partial
73	Correct	212 ms	39504 KB	ok
74	Correct	188 ms	39504 KB	ok
75	Partially correct	223 ms	39684 KB	partial
76	Partially correct	186 ms	39504 KB	partial
77	Partially correct	191 ms	39504 KB	partial
78	Partially correct	194 ms	39572 KB	partial
79	Partially correct	199 ms	39508 KB	partial
80	Partially correct	200 ms	39508 KB	partial
81	Partially correct	194 ms	39504 KB	partial
82	Partially correct	190 ms	39508 KB	partial
83	Partially correct	207 ms	39688 KB	partial
84	Partially correct	199 ms	39508 KB	partial
85	Partially correct	206 ms	39696 KB	partial
86	Partially correct	193 ms	39560 KB	partial
87	Partially correct	212 ms	39560 KB	partial
88	Partially correct	200 ms	39688 KB	partial
89	Partially correct	202 ms	39508 KB	partial
90	Partially correct	195 ms	39576 KB	partial
91	Partially correct	189 ms	39448 KB	partial
92	Partially correct	196 ms	39508 KB	partial
93	Partially correct	186 ms	39556 KB	partial
94	Partially correct	182 ms	39508 KB	partial
95	Partially correct	182 ms	39508 KB	partial
96	Partially correct	191 ms	39508 KB	partial
97	Partially correct	197 ms	39688 KB	partial
98	Partially correct	181 ms	39684 KB	partial
99	Partially correct	212 ms	39572 KB	partial
100	Partially correct	183 ms	39504 KB	partial
101	Partially correct	188 ms	39508 KB	partial
102	Partially correct	202 ms	39504 KB	partial
103	Partially correct	194 ms	39504 KB	partial
104	Partially correct	199 ms	39760 KB	partial
105	Partially correct	203 ms	39508 KB	partial
106	Partially correct	204 ms	39508 KB	partial
107	Partially correct	201 ms	39504 KB	partial
108	Partially correct	208 ms	39504 KB	partial
109	Partially correct	214 ms	39444 KB	partial

답안 #1018296

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 1.5 / 6.0

Subtask #2 2.0 / 8.0

Subtask #3 5.5 / 22.0

Subtask #4 4.5 / 18.0

Subtask #5 4.0 / 16.0

Subtask #6 7.5 / 30.0

Subtask #0
0.0 / 0.0

Subtask #1
1.5 / 6.0

Subtask #2
2.0 / 8.0

Subtask #3
5.5 / 22.0

Subtask #4
4.5 / 18.0

Subtask #5
4.0 / 16.0

Subtask #6
7.5 / 30.0