oj.uz

Submission #948259

# Submission time Handle Problem Language Result Execution time Memory
948259 2024-03-18T02:26:04 Z Nhoksocqt1 Soccer Stadium (IOI23_soccer) C++17
19.5 / 100
 958 ms 285964 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};

struct State {
    int x, y, t;

    State(int _x = 0, int _y = 0, int _t = 0) : x(_x), y(_y), t(_t) {};
};

ii range[MAXN];
int dp[2][33][33][33][33][33];
int sum[MAXN][MAXN], nSize;
bool dx[MAXN][MAXN][4], tmp[MAXN][MAXN], isTree[MAXN][MAXN];

bool checkGrid2(void) {
    int minL(nSize), maxR(0);
    bool ok(0);
    for (int i = 1; i <= nSize; ++i) {
        range[i] = {0, 0};
        bool hasEmpty(0);
        for (int j = 1; j <= nSize; ++j) {
            if(hasEmpty && isTree[i][j - 1] && !isTree[i][j])
                return false;

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

        if(ok && range[i].fi > 0 && range[i - 1].fi == 0)
            return false;

        ok |= (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)
            return false;

        if(i > 2 && descR && range[i - 1].se < range[i].se)
            return false;

        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;
        }
    }

    for (int i = 1; i <= nSize; ++i) {
        if(range[i].fi <= 0)
            continue;

        int nowL = range[i].fi, nowR = range[i].se;
        if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
            return false;
    }

    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            if(!isTree[j][i]) {
                int k(j);
                while(k <= nSize && !isTree[k][i])
                    ++k;

                --k;
                if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
                    return false;

                break;
            }
        }
    }

    return true;
}

int calc(int i, int j) {
    return (i - 1 + j - 1) * nSize - (i - 1) * (j - 1);
}

int sub1(void) {
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            if(isTree[i][j]) {
                return max({calc(i, j), calc(nSize - i + 1, j), calc(i, nSize - j + 1), calc(nSize - i + 1, nSize - j + 1)});
            }
        }
    }

    abort();
}

int sub2(void) {
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j)
            tmp[i][j] = isTree[i][j];
    }

    int res(0);
    for (int mask = 0; mask < (1 << (nSize * nSize)); ++mask) {
        if(__builtin_popcount(mask) <= res)
            continue;

        bool check(1);
        for (int i = 1; i <= nSize; ++i) {
            for (int j = 1; j <= nSize; ++j) {
                if((mask >> ((i - 1) * nSize + j - 1) & 1) && isTree[i][j])
                    check = 0;

                isTree[i][j] = !(mask >> ((i - 1) * nSize + j - 1) & 1);
            }
        }

        if(check && checkGrid2())
            res = __builtin_popcount(mask);

        for (int i = 1; i <= nSize; ++i) {
            for (int j = 1; j <= nSize; ++j)
                isTree[i][j] = tmp[i][j];
        }
    }

    return res;
}

inline int getSum(int x, int y, int u, int v) {
    return sum[u][v] - sum[u][y - 1] - sum[x - 1][v] + sum[x - 1][y - 1];
}

int DP4(void) {
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + isTree[i][j];
    }

    for (int i = 1; i <= nSize; ++i) {
        for (int ul = 1; ul <= nSize; ++ul) {
            for (int ur = ul; ur <= nSize; ++ur) {
                for (int dl = 1; dl <= nSize; ++dl) {
                    for (int dr = dl; dr <= nSize; ++dr) {
                        if(!(ul <= dl && dr <= ur || dl <= ul && ur <= dr))
                            continue;

                        dp[0][i][ul][ur][dl][dr] = dp[1][i][ul][ur][dl][dr] = 0;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= nSize; ++i) {
        for (int l = 1; l <= nSize; ++l) {
            for (int r = l; r <= nSize; ++r) {
                if(isTree[i][r])
                    break;

                dp[1][i][l][r][l][r] = r - l + 1;
            }
        }
    }

    int res(0);
    for (int len = 1; len <= nSize; ++len) {
        int pre(len & 1), cur(!pre);
        for (int i = 1; i + len - 1 <= nSize; ++i) {
            int j(i + len - 1);
            for (int ul = nSize; ul > 0; --ul) {
                for (int ur = ul; ur <= nSize; ++ur) {
                    for (int dl = nSize; dl > 0; --dl) {
                        for (int dr = dl; dr <= nSize; ++dr) {
                            if(dp[pre][i][ul][ur][dl][dr] == 0 || !(ul <= dl && dr <= ur || dl <= ul && ur <= dr))
                                continue;

                            if(j < nSize && getSum(j + 1, dl, j + 1, dr) == 0)
                                dp[cur][i][ul][ur][dl][dr] = max(dp[cur][i][ul][ur][dl][dr], dp[pre][i][ul][ur][dl][dr] + dr - dl + 1);

                            if(i > 1 && getSum(i - 1, ul, i - 1, ur) == 0)
                                dp[cur][i - 1][ul][ur][dl][dr] = max(dp[cur][i - 1][ul][ur][dl][dr], dp[pre][i][ul][ur][dl][dr] + ur - ul + 1);

                            if(len > 1) {
                                if(ul > 1 && !isTree[i][ul - 1])
                                    dp[pre][i][ul - 1][ur][dl][dr] = max(dp[pre][i][ul - 1][ur][dl][dr], dp[pre][i][ul][ur][dl][dr] + 1);

                                if(ur < nSize && !isTree[i][ur + 1])
                                    dp[pre][i][ul][ur + 1][dl][dr] = max(dp[pre][i][ul][ur + 1][dl][dr], dp[pre][i][ul][ur][dl][dr] + 1);

                                if(dl > 1 && !isTree[j][dl - 1])
                                    dp[pre][i][ul][ur][dl - 1][dr] = max(dp[pre][i][ul][ur][dl - 1][dr], dp[pre][i][ul][ur][dl][dr] + 1);

                                if(dr < nSize && !isTree[j][dr + 1])
                                    dp[pre][i][ul][ur][dl][dr + 1] = max(dp[pre][i][ul][ur][dl][dr + 1], dp[pre][i][ul][ur][dl][dr] + 1);
                            }

                            //cout << len << ' ' << i << ' ' << ul << ' ' << ur << ' ' << dl << ' ' << dr << ' ' << dp[pre][i][ul][ur][dl][dr] << '\n';
                            res = max(res, dp[pre][i][ul][ur][dl][dr]);
                            dp[pre][i][ul][ur][dl][dr] = 0;
                        }
                    }
                }
            }
        }
    }

    return res;
}

int sub4(void) {
    int res = DP4();
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j)
            tmp[nSize - i + 1][j] = isTree[i][j];
    }

    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j)
            isTree[i][j] = tmp[i][j];
    }

    res = max(res, DP4());
    return res;
}

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];
        }
    }

    if(cntTree == 1)
        return sub1();

    if(nSize <= 3)
        return sub2();

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

    if(nSize <= 30)
        return sub4();

    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];
            //F[i][j] = min(1, max(0, Random(-4, 1))); cout << F[i][j] << " \n"[j + 1 == n];
        }
    }

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

    return 0;
}

#endif // Nhoksocqt1

Compilation message

soccer.cpp: In function 'bool checkGrid2()':
soccer.cpp:99:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |         if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
      |              ~~~~~~~~~~~~^~~~~~~~~~~~~~
soccer.cpp:99:91: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |         if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
      |                                                                             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:111:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  111 |                 if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
      |                      ~~~~~~~~~~~^~~~~~~~~~~~~
soccer.cpp:111:93: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  111 |                 if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
      |                                                                                 ~~~~~~~~~~~~^~~~~~~~~~~~~~
soccer.cpp: In function 'int DP4()':
soccer.cpp:186:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  186 |                         if(!(ul <= dl && dr <= ur || dl <= ul && ur <= dr))
      |                              ~~~~~~~~~^~~~~~~~~~~
soccer.cpp:216:78: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  216 |                             if(dp[pre][i][ul][ur][dl][dr] == 0 || !(ul <= dl && dr <= ur || dl <= ul && ur <= dr))
      |                                                                     ~~~~~~~~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 29020 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2392 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 2 ms 4700 KB ok
8 Correct 16 ms 6572 KB ok
9 Correct 240 ms 38188 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 29020 KB partial
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4440 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Partially correct 10 ms 45400 KB partial
16 Partially correct 5 ms 45404 KB partial
17 Correct 5 ms 45404 KB ok
18 Correct 7 ms 45656 KB ok
19 Partially correct 5 ms 45404 KB partial
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2392 KB ok
22 Partially correct 5 ms 45560 KB partial
23 Partially correct 5 ms 45404 KB partial
24 Partially correct 6 ms 45404 KB partial
25 Partially correct 5 ms 45404 KB partial
26 Partially correct 6 ms 45580 KB partial

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 29020 KB partial
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Partially correct 10 ms 45400 KB partial
18 Partially correct 5 ms 45404 KB partial
19 Correct 5 ms 45404 KB ok
20 Correct 7 ms 45656 KB ok
21 Partially correct 5 ms 45404 KB partial
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2392 KB ok
24 Partially correct 5 ms 45560 KB partial
25 Partially correct 5 ms 45404 KB partial
26 Partially correct 6 ms 45404 KB partial
27 Partially correct 5 ms 45404 KB partial
28 Partially correct 6 ms 45580 KB partial
29 Partially correct 5 ms 45404 KB partial
30 Partially correct 680 ms 285964 KB partial
31 Partially correct 619 ms 285720 KB partial
32 Partially correct 607 ms 285720 KB partial
33 Correct 629 ms 285524 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2480 KB ok
36 Partially correct 619 ms 285676 KB partial
37 Partially correct 605 ms 285716 KB partial
38 Partially correct 606 ms 285720 KB partial
39 Partially correct 607 ms 285724 KB partial
40 Incorrect 958 ms 285716 KB wrong
41 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 29020 KB partial
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Partially correct 10 ms 45400 KB partial
18 Partially correct 5 ms 45404 KB partial
19 Correct 5 ms 45404 KB ok
20 Correct 7 ms 45656 KB ok
21 Partially correct 5 ms 45404 KB partial
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2392 KB ok
24 Partially correct 5 ms 45560 KB partial
25 Partially correct 5 ms 45404 KB partial
26 Partially correct 6 ms 45404 KB partial
27 Partially correct 5 ms 45404 KB partial
28 Partially correct 6 ms 45580 KB partial
29 Partially correct 5 ms 45404 KB partial
30 Partially correct 680 ms 285964 KB partial
31 Partially correct 619 ms 285720 KB partial
32 Partially correct 607 ms 285720 KB partial
33 Correct 629 ms 285524 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2480 KB ok
36 Partially correct 619 ms 285676 KB partial
37 Partially correct 605 ms 285716 KB partial
38 Partially correct 606 ms 285720 KB partial
39 Partially correct 607 ms 285724 KB partial
40 Incorrect 958 ms 285716 KB wrong
41 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 29020 KB partial
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 2 ms 4700 KB ok
9 Correct 16 ms 6572 KB ok
10 Correct 240 ms 38188 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4440 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4440 KB ok
17 Correct 1 ms 4444 KB ok
18 Correct 1 ms 4444 KB ok
19 Correct 1 ms 4444 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Partially correct 10 ms 45400 KB partial
23 Partially correct 5 ms 45404 KB partial
24 Correct 5 ms 45404 KB ok
25 Correct 7 ms 45656 KB ok
26 Partially correct 5 ms 45404 KB partial
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2392 KB ok
29 Partially correct 5 ms 45560 KB partial
30 Partially correct 5 ms 45404 KB partial
31 Partially correct 6 ms 45404 KB partial
32 Partially correct 5 ms 45404 KB partial
33 Partially correct 6 ms 45580 KB partial
34 Partially correct 5 ms 45404 KB partial
35 Partially correct 680 ms 285964 KB partial
36 Partially correct 619 ms 285720 KB partial
37 Partially correct 607 ms 285720 KB partial
38 Correct 629 ms 285524 KB ok
39 Correct 1 ms 2396 KB ok
40 Correct 1 ms 2480 KB ok
41 Partially correct 619 ms 285676 KB partial
42 Partially correct 605 ms 285716 KB partial
43 Partially correct 606 ms 285720 KB partial
44 Partially correct 607 ms 285724 KB partial
45 Incorrect 958 ms 285716 KB wrong
46 Halted 0 ms 0 KB -