oj.uz

Submission #948280

# Submission time Handle Problem Language Result Execution time Memory
948280 2024-03-18T03:05:19 Z Nhoksocqt1 Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 999392 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][503][503][503];
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 l = 1; l <= nSize; ++l) {
            for (int r = l; r <= nSize; ++r)
                dp[0][i][l][r] = dp[1][i][l][r] = 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] = 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 l = 1; l <= nSize; ++l) {
                for (int r = nSize; r >= l; --r) {
                    if(!dp[pre][i][l][r])
                        continue;

                    if(i > 1 && getSum(i - 1, l, i - 1, r) == 0)
                        dp[cur][i - 1][l][r] = max(dp[cur][i - 1][l][r], dp[pre][i][l][r] + r - l + 1);

                    if(j < nSize && getSum(j + 1, l, j + 1, r) == 0)
                        dp[cur][i][l][r] = max(dp[cur][i][l][r], dp[pre][i][l][r] + r - l + 1);

                    if(l < r) {
                        dp[pre][i][l + 1][r] = max(dp[pre][i][l + 1][r], dp[pre][i][l][r]);
                        dp[pre][i][l][r - 1] = max(dp[pre][i][l][r - 1], dp[pre][i][l][r]);
                    }

                    res = max(res, dp[pre][i][l][r]);
                    dp[pre][i][l][r] = 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 <= 500)
        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))
      |                                                                                 ~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 1 ms 2500 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 2 ms 4952 KB ok
8 Correct 16 ms 6572 KB ok
9 Correct 248 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 2500 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 2 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 4488 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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2500 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 2 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 4488 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 3 ms 20828 KB ok
16 Correct 3 ms 20828 KB ok
17 Correct 2 ms 20828 KB ok
18 Correct 3 ms 20828 KB ok
19 Correct 3 ms 20828 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 3 ms 20828 KB ok
23 Correct 3 ms 21084 KB ok
24 Correct 3 ms 20828 KB ok
25 Correct 3 ms 20828 KB ok
26 Correct 3 ms 20928 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2500 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 2 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 4488 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 3 ms 20828 KB ok
18 Correct 3 ms 20828 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 3 ms 20828 KB ok
21 Correct 3 ms 20828 KB ok
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 3 ms 20828 KB ok
25 Correct 3 ms 21084 KB ok
26 Correct 3 ms 20828 KB ok
27 Correct 3 ms 20828 KB ok
28 Correct 3 ms 20928 KB ok
29 Correct 3 ms 20824 KB ok
30 Correct 22 ms 66136 KB ok
31 Correct 8 ms 66140 KB ok
32 Correct 7 ms 66140 KB ok
33 Correct 7 ms 66136 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2396 KB ok
36 Correct 12 ms 66140 KB ok
37 Correct 8 ms 66108 KB ok
38 Correct 8 ms 66140 KB ok
39 Correct 8 ms 66068 KB ok
40 Correct 8 ms 66160 KB ok
41 Correct 10 ms 66136 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2500 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 2 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 4488 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 3 ms 20828 KB ok
18 Correct 3 ms 20828 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 3 ms 20828 KB ok
21 Correct 3 ms 20828 KB ok
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 3 ms 20828 KB ok
25 Correct 3 ms 21084 KB ok
26 Correct 3 ms 20828 KB ok
27 Correct 3 ms 20828 KB ok
28 Correct 3 ms 20928 KB ok
29 Correct 3 ms 20824 KB ok
30 Correct 22 ms 66136 KB ok
31 Correct 8 ms 66140 KB ok
32 Correct 7 ms 66140 KB ok
33 Correct 7 ms 66136 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2396 KB ok
36 Correct 12 ms 66140 KB ok
37 Correct 8 ms 66108 KB ok
38 Correct 8 ms 66140 KB ok
39 Correct 8 ms 66068 KB ok
40 Correct 8 ms 66160 KB ok
41 Correct 10 ms 66136 KB ok
42 Execution timed out 4633 ms 999392 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2500 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 2392 KB ok
8 Correct 2 ms 4952 KB ok
9 Correct 16 ms 6572 KB ok
10 Correct 248 ms 38184 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 2 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 4488 KB ok
19 Correct 1 ms 4444 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Correct 3 ms 20828 KB ok
23 Correct 3 ms 20828 KB ok
24 Correct 2 ms 20828 KB ok
25 Correct 3 ms 20828 KB ok
26 Correct 3 ms 20828 KB ok
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 3 ms 20828 KB ok
30 Correct 3 ms 21084 KB ok
31 Correct 3 ms 20828 KB ok
32 Correct 3 ms 20828 KB ok
33 Correct 3 ms 20928 KB ok
34 Correct 3 ms 20824 KB ok
35 Correct 22 ms 66136 KB ok
36 Correct 8 ms 66140 KB ok
37 Correct 7 ms 66140 KB ok
38 Correct 7 ms 66136 KB ok
39 Correct 1 ms 2396 KB ok
40 Correct 1 ms 2396 KB ok
41 Correct 12 ms 66140 KB ok
42 Correct 8 ms 66108 KB ok
43 Correct 8 ms 66140 KB ok
44 Correct 8 ms 66068 KB ok
45 Correct 8 ms 66160 KB ok
46 Correct 10 ms 66136 KB ok
47 Execution timed out 4633 ms 999392 KB Time limit exceeded
48 Halted 0 ms 0 KB -