Submission #1037949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1037949	2024-07-29T10:54:50 Z	fv3	Soccer Stadium (IOI23_soccer)	C++17	3.5 / 100	245 ms	99412 KB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int nt = 1;
vector<vector<int>> st_h, st_v;

int getvrange(int l, int r, int k, int x, int y, int i)
{
    if (l > r) swap(l, r);
    if (r < x || l > y) return 0;
    if (x >= l && y <= r) return st_v[i][k];
    int c = (x + y) / 2;
    return getvrange(l, r, k*2, x, c, i) + getvrange(l, r, k*2|1, c+1, y, i);
}

int gethrange(int l, int r, int k, int x, int y, int i)
{
    if (l > r) swap(l, r);
    if (r < x || l > y) return 0;
    if (x >= l && y <= r) return st_h[i][k];
    int c = (x + y) / 2;
    return gethrange(l, r, k*2, x, c, i) + gethrange(l, r, k*2|1, c+1, y, i);
}

int biggest_stadium(int N, vector<vector<int>> F)
{
    int res = 0;

    while (nt < N)
        nt *= 2;

    st_v = st_h = vector<vector<int>>(N, vector<int>(2*nt));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            st_h[i][nt + j] = F[i][j];
            st_v[i][nt + j] = F[j][i];
        }

        for (int j = nt - 1; j >= 1; j--)
        {
            st_h[i][j] = st_h[i][j*2] + st_h[i][j*2|1];
            st_v[i][j] = st_v[i][j*2] + st_v[i][j*2|1];
        }
    }

    int top;
    int topl, topr;
    for (int i = 0; i < N; i++)
    {
        if (st_h[i][1] == N) continue;
        for (int j = 0; j < N; j++)
        {
            if (F[i][j]) continue;
            if (gethrange(j, j + (N - st_h[i][1] - 1), 1, 0, nt - 1, i))
                return -1;

            top = i;
            topl = j;
            cerr << st_h[i][1] << '\n';
            topr = j + (N - st_h[i][1] - 1);

            break;
        }
        break;
    }

    int btm;
    int btml, btmr;
    for (int i = N-1; i >= 0; i--)
    {
        if (st_h[i][1] == N) continue;
        for (int j = 0; j < N; j++)
        {
            if (F[i][j]) continue;
            if (gethrange(j, j + (N - st_h[i][1] - 1), 1, 0, nt - 1, i))
                return -1;

            btm = i;
            btml = j;
            btmr = j + (N - st_h[i][1] - 1);
            break;
        }
        break;
    }

    int lft;
    int lft_up, lft_dwn;
    for (int i = 0; i < N; i++)
    {
        if (st_v[i][1] == N) continue;
        for (int j = 0; j < N; j++)
        {
            if (F[j][i]) continue;
            if (getvrange(j, j + (N - st_v[i][1] - 1), 1, 0, nt - 1, i))
                return -1;

            lft = i;
            lft_up = j;
            lft_dwn = j + (N - st_v[i][1] - 1);
            break;
        }
        break;
    }

    int right;
    int right_up, right_dwn;
    for (int i = N-1; i >= 0; i--)
    {
        if (st_v[i][1] == N) continue;
        for (int j = 0; j < N; j++)
        {
            if (F[j][i]) continue;
            if (getvrange(j, j + (N - st_v[i][1] - 1), 1, 0, nt - 1, i))
                return -1;

            right = i;
            right_up = j;
            right_dwn = j + (N - st_v[i][1] - 1);
            break;
        }
        break;
    }

    if (!(lft_up >= right_up && lft_dwn <= right_dwn) && !(lft_up <= right_up && lft_dwn >= right_dwn))
        return -1;

    int v = max(max(lft_up, right_up), min(lft_dwn, right_dwn));
    if (!(topl >= btml && topr <= btmr) && !(topl <= btml && topr >= btmr))
        return -1;
    int h = max(max(topl, btml), min(topr, btmr));

    int cnt = 0;
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            if (F[y][x]) continue;
            cnt++;

            if (gethrange(x, h, 1, 0, nt - 1, y))
                return -1;

            if (getvrange(y, v, 1, 0, nt - 1, x))
                return -1;
        }
    }

    return cnt;

    /*for (int i = 0; i < vpi.size(); i++)
    {
        int x, y;
        tie(x, y) = vpi[i];

        for (int j = i+1; j < vpi.size(); j++)
        {
            int nx, ny;
            tie(nx, ny) = vpi[j];


            bool b1 = getvrange(y, ny, 1, 0, nt - 1, x) || gethrange(x, nx, 1, 0, nt - 1, ny);
            bool b2 = getvrange(y, ny, 1, 0, nt - 1, nx) || gethrange(x, nx, 1, 0, nt - 1, y);

            cerr << x << " " << y << " : " << nx << " " << ny << " = " << b1 << ", " << b2 << "\n";

            if (b1 && b2)
                return -1;
        }
    }

    return vpi.size();*/
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:30:9: warning: unused variable 'res' [-Wunused-variable]
   30 |     int res = 0;
      |         ^~~
soccer.cpp:51:9: warning: variable 'top' set but not used [-Wunused-but-set-variable]
   51 |     int top;
      |         ^~~
soccer.cpp:72:9: warning: variable 'btm' set but not used [-Wunused-but-set-variable]
   72 |     int btm;
      |         ^~~
soccer.cpp:91:9: warning: variable 'lft' set but not used [-Wunused-but-set-variable]
   91 |     int lft;
      |         ^~~
soccer.cpp:110:9: warning: variable 'right' set but not used [-Wunused-but-set-variable]
  110 |     int right;
      |         ^~~~~
soccer.cpp:129:18: warning: 'right_up' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |     if (!(lft_up >= right_up && lft_dwn <= right_dwn) && !(lft_up <= right_up && lft_dwn >= right_dwn))
      |           ~~~~~~~^~~~~~~~~~~
soccer.cpp:129:41: warning: 'right_dwn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |     if (!(lft_up >= right_up && lft_dwn <= right_dwn) && !(lft_up <= right_up && lft_dwn >= right_dwn))
      |                                 ~~~~~~~~^~~~~~~~~~~~
soccer.cpp:129:18: warning: 'right_up' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |     if (!(lft_up >= right_up && lft_dwn <= right_dwn) && !(lft_up <= right_up && lft_dwn >= right_dwn))
      |           ~~~~~~~^~~~~~~~~~~
soccer.cpp:129:41: warning: 'right_dwn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |     if (!(lft_up >= right_up && lft_dwn <= right_dwn) && !(lft_up <= right_up && lft_dwn >= right_dwn))
      |                                 ~~~~~~~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
1.5 / 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	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	604 KB	partial
8	Partially correct	15 ms	6748 KB	partial
9	Partially correct	245 ms	99412 KB	partial

Subtask #2
2.0 / 8.0

#	Verdict	Memory	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	344 KB	ok
9	Correct	348 KB	ok
10	Partially correct	344 KB	partial
11	Partially correct	344 KB	partial
12	Partially correct	344 KB	partial
13	Correct	348 KB	ok

Subtask #3
0.0 / 22.0

#	Verdict	Memory	Grader output
1	Partially correct	344 KB	partial
2	Correct	348 KB	ok
3	Correct	348 KB	ok
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	Partially correct	348 KB	partial
9	Correct	344 KB	ok
10	Correct	348 KB	ok
11	Partially correct	344 KB	partial
12	Partially correct	344 KB	partial
13	Partially correct	344 KB	partial
14	Correct	348 KB	ok
15	Partially correct	344 KB	partial
16	Partially correct	348 KB	partial
17	Partially correct	348 KB	partial
18	Partially correct	348 KB	partial
19	Partially correct	348 KB	partial
20	Correct	348 KB	ok
21	Correct	348 KB	ok
22	Incorrect	348 KB	wrong
23	Halted	0 KB	-

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

#	Verdict	Memory	Grader output
1	Partially correct	344 KB	partial
2	Correct	348 KB	ok
3	Correct	348 KB	ok
4	Correct	348 KB	ok
5	Correct	348 KB	ok
6	Partially correct	348 KB	partial
7	Partially correct	348 KB	partial
8	Partially correct	348 KB	partial
9	Partially correct	348 KB	partial
10	Partially correct	348 KB	partial
11	Correct	344 KB	ok
12	Correct	348 KB	ok
13	Partially correct	344 KB	partial
14	Partially correct	344 KB	partial
15	Partially correct	344 KB	partial
16	Correct	348 KB	ok
17	Partially correct	344 KB	partial
18	Partially correct	348 KB	partial
19	Partially correct	348 KB	partial
20	Partially correct	348 KB	partial
21	Partially correct	348 KB	partial
22	Correct	348 KB	ok
23	Correct	348 KB	ok
24	Incorrect	348 KB	wrong
25	Halted	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	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	604 KB	partial
9	Partially correct	15 ms	6748 KB	partial
10	Partially correct	245 ms	99412 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	344 KB	ok
17	Correct	0 ms	348 KB	ok
18	Partially correct	0 ms	344 KB	partial
19	Partially correct	0 ms	344 KB	partial
20	Partially correct	0 ms	344 KB	partial
21	Correct	0 ms	348 KB	ok
22	Partially correct	0 ms	344 KB	partial
23	Partially correct	0 ms	348 KB	partial
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	Correct	0 ms	348 KB	ok
28	Correct	0 ms	348 KB	ok
29	Incorrect	0 ms	348 KB	wrong
30	Halted	0 ms	0 KB	-

Submission #1037949

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 1.5 / 6.0

Subtask #2 2.0 / 8.0

Subtask #3 0.0 / 22.0

Subtask #4 0.0 / 18.0

Subtask #5 0.0 / 16.0

Subtask #6 0.0 / 30.0

Subtask #0
0.0 / 0.0

Subtask #1
1.5 / 6.0

Subtask #2
2.0 / 8.0

Subtask #3
0.0 / 22.0

Subtask #4
0.0 / 18.0

Subtask #5
0.0 / 16.0

Subtask #6
0.0 / 30.0