oj.uz

Submission #944567

# Submission time Handle Problem Language Result Execution time Memory
944567 2024-03-13T00:34:45 Z Nhoksocqt1 Soccer Stadium (IOI23_soccer) C++17
3.5 / 100
 260 ms 42836 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 2003;
const int lx[] = {-1, 0, 0, 1}, ly[] = {0, -1, 1, 0};

ii range[MAXN];
int nSize;
bool isTree[MAXN][MAXN];

int biggest_stadium(int n, vector<vector<int>> F) {
    nSize = n;

    int cntTree(0);
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            isTree[i][j] = (F[i - 1][j - 1]);
            cntTree += isTree[i][j];
        }
    }

    int minL(nSize), maxR(0);
    bool hasOk(0), check(1);
    for (int i = 1; i <= nSize; ++i) {
        bool hasEmpty(0);
        for (int j = 1; j <= nSize; ++j) {
            if(hasEmpty && isTree[i][j - 1] && !isTree[i][j])
                check = 0;

            hasEmpty |= (!isTree[i][j]);
            if(!isTree[i][j]) {
                range[i].se = j;
                if(!range[i].fi)
                    range[i].fi = j;
            }
        }

        if(hasOk && range[i].fi > 0 && range[i - 1].fi == 0)
            check = 0;

        hasOk |= (range[i].fi > 0);
        if(range[i].fi > 0)
            minL = min(minL, range[i].fi);

        maxR = max(maxR, range[i].se);
    }

    int upL(-1), upR(-1), downL(-1), downR(-1);
    int leftL(-1), leftR(-1), rightL(-1), rightR(-1);
    bool descL(0), descR(0);
    for (int i = 1; i <= nSize; ++i) {
        if(range[i].fi == 0)
            continue;

        if(i > 2 && descL && range[i - 1].fi > range[i].fi)
            check = 0;

        if(i > 2 && descR && range[i - 1].se < range[i].se)
            check = 0;

        if(i > 1 && range[i - 1].fi > 0 && range[i - 1].fi < range[i].fi)
            descL = 1;

        if(i > 1 && range[i - 1].se > 0 && range[i - 1].se > range[i].se)
            descR = 1;

        if(upL < 0)
            upL = range[i].fi, upR = range[i].se;

        downL = range[i].fi, downR = range[i].se;
        if(range[i].fi == minL) {
            leftR = i;
            if(leftL < 0)
                leftL = i;
        }

        if(range[i].se == maxR) {
            rightR = i;
            if(rightL < 0)
                rightL = i;
        }
    }

    if(!(leftL <= rightL && rightR <= leftR || rightL <= leftL && leftR <= rightR))
        check = 0;

    if(!(upL <= downL && downR <= upR || downL <= upL && upR <= downR))
        check = 0;

    if(cntTree == 0 || check)
        return nSize * nSize - cntTree;

    return 1;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "soccer"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<vector<int>> F;
    int n;
    cin >> n;

    F.resize(n);
    for (int i = 0; i < n; ++i) {
        F[i].resize(n);
        for (int j = 0; j < n; ++j)
            cin >> F[i][j];
    }

    int ans = biggest_stadium(n, F);
    cout << "ANSWER: " << ans << '\n';

    return 0;
}

#endif // Nhoksocqt1

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:96:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   96 |     if(!(leftL <= rightL && rightR <= leftR || rightL <= leftL && leftR <= rightR))
      |          ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:99:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |     if(!(upL <= downL && downR <= upR || downL <= upL && upR <= downR))
      |          ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Partially correct 1 ms 600 KB partial
7 Partially correct 1 ms 2652 KB partial
8 Partially correct 17 ms 4956 KB partial
9 Partially correct 260 ms 42836 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 348 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 1 ms 348 KB partial
7 Partially correct 1 ms 348 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Partially correct 1 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 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 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 1 ms 348 KB partial
8 Partially correct 1 ms 348 KB partial
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Partially correct 1 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 0 ms 348 KB partial
16 Partially correct 1 ms 456 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 Correct 1 ms 344 KB ok
21 Correct 0 ms 452 KB ok
22 Incorrect 0 ms 348 KB wrong
23 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.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 344 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 1 ms 348 KB partial
10 Partially correct 1 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
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 0 ms 348 KB ok
17 Partially correct 0 ms 348 KB partial
18 Partially correct 1 ms 456 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 Correct 1 ms 344 KB ok
23 Correct 0 ms 452 KB ok
24 Incorrect 0 ms 348 KB wrong
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.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 344 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 1 ms 348 KB partial
10 Partially correct 1 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
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 0 ms 348 KB ok
17 Partially correct 0 ms 348 KB partial
18 Partially correct 1 ms 456 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 Correct 1 ms 344 KB ok
23 Correct 0 ms 452 KB ok
24 Incorrect 0 ms 348 KB wrong
25 Halted 0 ms 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 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Partially correct 1 ms 600 KB partial
8 Partially correct 1 ms 2652 KB partial
9 Partially correct 17 ms 4956 KB partial
10 Partially correct 260 ms 42836 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 1 ms 348 KB partial
15 Partially correct 1 ms 348 KB partial
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Partially correct 1 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 0 ms 348 KB partial
23 Partially correct 1 ms 456 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 1 ms 344 KB ok
28 Correct 0 ms 452 KB ok
29 Incorrect 0 ms 348 KB wrong
30 Halted 0 ms 0 KB -