oj.uz

Submission #948263

# Submission time Handle Problem Language Result Execution time Memory
948263 2024-03-18T02:30:46 Z Nhoksocqt1 Soccer Stadium (IOI23_soccer) C++17
19.5 / 100
 1703 ms 463700 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][2];
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;

                        for (int t = 0; t < 4; ++t)
                            dp[t >> 1][i][ul][ur][dl][dr][t & 1] = 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][0] = 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(!(ul <= dl && dr <= ur || dl <= ul && ur <= dr))
                                continue;

                            for (int last = 0; last < 2; ++last) {
                                if(!dp[pre][i][ul][ur][dl][dr][last])
                                    continue;

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

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

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

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

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

                                    if(last && dr < nSize && !isTree[j][dr + 1])
                                        dp[pre][i][ul][ur][dl][dr + 1][last] = max(dp[pre][i][ul][ur][dl][dr + 1][last], dp[pre][i][ul][ur][dl][dr][last] + 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][last]);
                                dp[pre][i][ul][ur][dl][dr][last] = 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:217:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  217 |                             if(!(ul <= dl && dr <= ur || dl <= ul && ur <= dr))
      |                                  ~~~~~~~~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 35160 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 4544 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 2 ms 4700 KB ok
8 Correct 16 ms 6556 KB ok
9 Correct 235 ms 38184 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 4440 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 4444 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 8 ms 35160 KB partial
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 4440 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 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
14 Correct 1 ms 4444 KB ok
15 Partially correct 9 ms 53596 KB partial
16 Partially correct 7 ms 53596 KB partial
17 Partially correct 6 ms 53784 KB partial
18 Correct 6 ms 53596 KB ok
19 Partially correct 6 ms 53596 KB partial
20 Correct 0 ms 2396 KB ok
21 Correct 1 ms 2392 KB ok
22 Partially correct 6 ms 53596 KB partial
23 Partially correct 6 ms 53816 KB partial
24 Partially correct 6 ms 53816 KB partial
25 Partially correct 7 ms 53596 KB partial
26 Partially correct 6 ms 53596 KB partial

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 35160 KB partial
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4440 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
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Partially correct 9 ms 53596 KB partial
18 Partially correct 7 ms 53596 KB partial
19 Partially correct 6 ms 53784 KB partial
20 Correct 6 ms 53596 KB ok
21 Partially correct 6 ms 53596 KB partial
22 Correct 0 ms 2396 KB ok
23 Correct 1 ms 2392 KB ok
24 Partially correct 6 ms 53596 KB partial
25 Partially correct 6 ms 53816 KB partial
26 Partially correct 6 ms 53816 KB partial
27 Partially correct 7 ms 53596 KB partial
28 Partially correct 6 ms 53596 KB partial
29 Partially correct 6 ms 53596 KB partial
30 Partially correct 1305 ms 441092 KB partial
31 Partially correct 1176 ms 462464 KB partial
32 Partially correct 1195 ms 463700 KB partial
33 Correct 1144 ms 462660 KB ok
34 Correct 1 ms 2392 KB ok
35 Correct 1 ms 2396 KB ok
36 Partially correct 1192 ms 459004 KB partial
37 Partially correct 1226 ms 461156 KB partial
38 Partially correct 1150 ms 459000 KB partial
39 Partially correct 1177 ms 460904 KB partial
40 Incorrect 1703 ms 461140 KB wrong
41 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 35160 KB partial
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4440 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
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Partially correct 9 ms 53596 KB partial
18 Partially correct 7 ms 53596 KB partial
19 Partially correct 6 ms 53784 KB partial
20 Correct 6 ms 53596 KB ok
21 Partially correct 6 ms 53596 KB partial
22 Correct 0 ms 2396 KB ok
23 Correct 1 ms 2392 KB ok
24 Partially correct 6 ms 53596 KB partial
25 Partially correct 6 ms 53816 KB partial
26 Partially correct 6 ms 53816 KB partial
27 Partially correct 7 ms 53596 KB partial
28 Partially correct 6 ms 53596 KB partial
29 Partially correct 6 ms 53596 KB partial
30 Partially correct 1305 ms 441092 KB partial
31 Partially correct 1176 ms 462464 KB partial
32 Partially correct 1195 ms 463700 KB partial
33 Correct 1144 ms 462660 KB ok
34 Correct 1 ms 2392 KB ok
35 Correct 1 ms 2396 KB ok
36 Partially correct 1192 ms 459004 KB partial
37 Partially correct 1226 ms 461156 KB partial
38 Partially correct 1150 ms 459000 KB partial
39 Partially correct 1177 ms 460904 KB partial
40 Incorrect 1703 ms 461140 KB wrong
41 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 35160 KB partial
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4544 KB ok
7 Correct 1 ms 2392 KB ok
8 Correct 2 ms 4700 KB ok
9 Correct 16 ms 6556 KB ok
10 Correct 235 ms 38184 KB ok
11 Correct 1 ms 4440 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 4444 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 9 ms 53596 KB partial
23 Partially correct 7 ms 53596 KB partial
24 Partially correct 6 ms 53784 KB partial
25 Correct 6 ms 53596 KB ok
26 Partially correct 6 ms 53596 KB partial
27 Correct 0 ms 2396 KB ok
28 Correct 1 ms 2392 KB ok
29 Partially correct 6 ms 53596 KB partial
30 Partially correct 6 ms 53816 KB partial
31 Partially correct 6 ms 53816 KB partial
32 Partially correct 7 ms 53596 KB partial
33 Partially correct 6 ms 53596 KB partial
34 Partially correct 6 ms 53596 KB partial
35 Partially correct 1305 ms 441092 KB partial
36 Partially correct 1176 ms 462464 KB partial
37 Partially correct 1195 ms 463700 KB partial
38 Correct 1144 ms 462660 KB ok
39 Correct 1 ms 2392 KB ok
40 Correct 1 ms 2396 KB ok
41 Partially correct 1192 ms 459004 KB partial
42 Partially correct 1226 ms 461156 KB partial
43 Partially correct 1150 ms 459000 KB partial
44 Partially correct 1177 ms 460904 KB partial
45 Incorrect 1703 ms 461140 KB wrong
46 Halted 0 ms 0 KB -