Submission #979980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979980	2024-05-11T18:33:18 Z	vjudge1	Soccer Stadium (IOI23_soccer)	C++17	3.5 / 100	324 ms	110356 KB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using vvi = vector <vi>;
using vll = vector <ll>;

int biggest_stadium (int n, vvi f) {
    ll all = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            all += f[i][j] == 0;
        }
    }
    vvi ps(n+1, vi(n+1, 0));
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++)
            ps[i+1][j+1] = !f[i][j];
    for (ll i = 0; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            ps[i][j] += ps[i][j-1];
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= n; j++) {
            ps[i][j] += ps[i-1][j];
        }
    }
    auto query = [&](ll il, ll ir, ll jl, ll jr) { // [il, ir] and [jl, jr] 0-indexed
        ir++; jr++;
        return ps[ir][jr] - ps[ir][jl] - ps[il][jr] + ps[il][jl];
    };
    vvi nxtI(n, vi(n)), prvI(n, vi(n)), nxtJ(n, vi(n)), prvJ(n, vi(n));
    for (ll j = 0; j < n; j++) prvI[0][j] = (f[0][j] ? 0 : -1);
    for (ll i = 1; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            prvI[i][j] = (f[i][j] ? i : prvI[i-1][j]);
        }
    }
    for (ll i = 0; i < n; i++) prvJ[i][0] = (f[i][0] ? 0 : -1);
    for (ll i = 0; i < n; i++) {
        for (ll j = 1; j < n; j++) {
            prvJ[i][j] = (f[i][j] ? i : prvJ[i][j-1]);
        }
    }
    for (ll j = 0; j < n; j++) nxtI[n-1][j] = (f[n-1][j] ? n-1 : n);
    for (ll i = n-2; i >= 0; i--) {
        for (ll j = 0; j < n; j++) {
            nxtI[i][j] = (f[i][j] ? i : nxtI[i+1][j]);
        }
    }
    for (ll i = 0; i < n; i++) nxtJ[i][n-1] = (f[i][n-1] ? n-1 : n);
    for (ll i = 0; i < n; i++) {
        for (ll j = n-2; j >= 0; j--) {
            nxtJ[i][j] = (f[i][j] ? i : nxtJ[i][j+1]);
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (f[i][j]) continue;
            ll il = prvI[i][j], ir = nxtI[i][j];
            ll jl = prvJ[i][j], jr = nxtJ[i][j];
            ll cou = 0;
            cou += query(0, il, 0, jl);
            cou += query(ir, n-1, 0, jl);
            cou += query(0, il, jr, n-1);
            cou += query(ir, n-1, jr, n-1);
            if (cou != 0) return 0;
        }
    }
    for (ll i = 0; i < n; i++) {
        ll j = 0;
        for (; j < n; j++) if (!f[i][j]) break;
        for (; j < n; j++) if (f[i][j]) break;
        for (; j < n; j++) if (!f[i][j]) break;
        if (j != n) return 0;
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < i; j++) {
            swap(f[i][j], f[j][i]);
        }
    }
    for (ll i = 0; i < n; i++) {
        ll j = 0;
        for (; j < n; j++) if (!f[i][j]) break;
        for (; j < n; j++) if (f[i][j]) break;
        for (; j < n; j++) if (!f[i][j]) break;
        if (j != n) return 0;
    }
    return all;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	348 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	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	Partially correct	0 ms	348 KB	partial
7	Partially correct	1 ms	604 KB	partial
8	Partially correct	21 ms	7260 KB	partial
9	Partially correct	324 ms	110356 KB	partial

Subtask #2

2.0 / 8.0

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

Subtask #3

0.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	348 KB	partial
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	344 KB	ok
4	Partially correct	1 ms	344 KB	partial
5	Partially correct	1 ms	348 KB	partial
6	Partially correct	1 ms	348 KB	partial
7	Partially correct	0 ms	348 KB	partial
8	Partially correct	0 ms	348 KB	partial
9	Correct	1 ms	344 KB	ok
10	Correct	0 ms	348 KB	ok
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	Correct	0 ms	348 KB	ok
15	Partially correct	1 ms	348 KB	partial
16	Partially correct	0 ms	348 KB	partial
17	Partially correct	0 ms	348 KB	partial
18	Partially correct	0 ms	348 KB	partial
19	Partially correct	0 ms	348 KB	partial
20	Incorrect	0 ms	348 KB	wrong
21	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	348 KB	partial
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	344 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Partially correct	1 ms	344 KB	partial
7	Partially correct	1 ms	348 KB	partial
8	Partially correct	1 ms	348 KB	partial
9	Partially correct	0 ms	348 KB	partial
10	Partially correct	0 ms	348 KB	partial
11	Correct	1 ms	344 KB	ok
12	Correct	0 ms	348 KB	ok
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	Partially correct	1 ms	348 KB	partial
18	Partially correct	0 ms	348 KB	partial
19	Partially correct	0 ms	348 KB	partial
20	Partially correct	0 ms	348 KB	partial
21	Partially correct	0 ms	348 KB	partial
22	Incorrect	0 ms	348 KB	wrong
23	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	348 KB	partial
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	344 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Partially correct	1 ms	344 KB	partial
7	Partially correct	1 ms	348 KB	partial
8	Partially correct	1 ms	348 KB	partial
9	Partially correct	0 ms	348 KB	partial
10	Partially correct	0 ms	348 KB	partial
11	Correct	1 ms	344 KB	ok
12	Correct	0 ms	348 KB	ok
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	Partially correct	1 ms	348 KB	partial
18	Partially correct	0 ms	348 KB	partial
19	Partially correct	0 ms	348 KB	partial
20	Partially correct	0 ms	348 KB	partial
21	Partially correct	0 ms	348 KB	partial
22	Incorrect	0 ms	348 KB	wrong
23	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	348 KB	partial
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	344 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	21 ms	7260 KB	partial
10	Partially correct	324 ms	110356 KB	partial
11	Partially correct	1 ms	344 KB	partial
12	Partially correct	1 ms	348 KB	partial
13	Partially correct	1 ms	348 KB	partial
14	Partially correct	0 ms	348 KB	partial
15	Partially correct	0 ms	348 KB	partial
16	Correct	1 ms	344 KB	ok
17	Correct	0 ms	348 KB	ok
18	Partially correct	0 ms	348 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	1 ms	348 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	Incorrect	0 ms	348 KB	wrong
28	Halted	0 ms	0 KB	-