oj.uz

Submission #944575

# Submission time Handle Problem Language Result Execution time Memory
944575 2024-03-13T01:07:38 Z Nhoksocqt1 Soccer Stadium (IOI23_soccer) C++17
24 / 100
 4500 ms 38652 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[MAXN][MAXN][4], nSize;
bool dx[MAXN][MAXN][4], tmp[MAXN][MAXN], isTree[MAXN][MAXN];

bool bfsCheck(int x, int y) {
    int cntEmpty(0);
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            for (int t = 0; t < 4; ++t) {
                dp[i][j][t] = (isTree[i][j]) ? -1 : 1e9;
                dx[i][j][t] = 0;
            }

            cntEmpty += (!isTree[i][j]);
        }
    }

    deque<State> dq;
    for (int t = 0; t < 4; ++t) {
        dq.push_back(State(x, y, t));
        dp[x][y][t] = 1;
    }

    int maxdp(0), cnt(0);
    while(sz(dq)) {
        int x(dq.front().x), y(dq.front().y), t(dq.front().t);
        dq.pop_front();

        if(dx[x][y][t])
            continue;

        dx[x][y][t] = 1;
        for (int id = 0; id < 4; ++id) {
            int u(x + lx[id]), v(y + ly[id]);
            if(min(u, v) < 1 || max(u, v) > nSize || dp[u][v][id] <= dp[x][y][t] + (t != id))
                continue;

            dp[u][v][id] = dp[x][y][t] + (t != id);
            if(t == id) {
                dq.push_front(State(u, v, id));
            } else {
                dq.push_back(State(u, v, id));
            }
        }
    }

    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            int mindp = min({dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]});
            maxdp = max(maxdp, mindp);
            cnt += (!isTree[i][j] && mindp < int(1e9));
        }
    }

    return (maxdp <= 2 && cnt == cntEmpty);
}

bool checkGrid(void) {
    vector<ii> p;
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            if(isTree[i][j])
                continue;

            if((i == 1) + (j == 1) + (i == nSize) + (j == nSize) + (i > 1 && isTree[i - 1][j]) + (j > 1 && isTree[i][j - 1]) + (j < nSize && isTree[i][j + 1]) + (i < nSize && isTree[i + 1][j]) >= 2 && !bfsCheck(i, j))
                return false;

            if((i == 1) + (j == 1) + (i == nSize) + (j == nSize) + (i > 1 && isTree[i - 1][j]) + (j > 1 && isTree[i][j - 1]) + (j < nSize && isTree[i][j + 1]) + (i < nSize && isTree[i + 1][j]) >= 2)
                p.push_back(ii(i, j));
        }
    }

    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 && checkGrid())
            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;
}

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 || checkGrid())
        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];
            //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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 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 6492 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 2 ms 4700 KB ok
8 Correct 15 ms 6488 KB ok
9 Correct 238 ms 37972 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 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 2 ms 6492 KB ok
8 Correct 1 ms 6488 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB partial
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 2 ms 6492 KB ok
9 Correct 1 ms 6488 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 2 ms 6492 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Partially correct 1 ms 4440 KB partial
16 Partially correct 1 ms 4596 KB partial
17 Partially correct 1 ms 4444 KB partial
18 Partially correct 1 ms 4548 KB partial
19 Partially correct 1 ms 4440 KB partial
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Partially correct 1 ms 4444 KB partial
23 Partially correct 1 ms 4444 KB partial
24 Partially correct 1 ms 4532 KB partial
25 Partially correct 1 ms 4440 KB partial
26 Partially correct 1 ms 4444 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 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 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 2 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6492 KB ok
17 Partially correct 1 ms 4440 KB partial
18 Partially correct 1 ms 4596 KB partial
19 Partially correct 1 ms 4444 KB partial
20 Partially correct 1 ms 4548 KB partial
21 Partially correct 1 ms 4440 KB partial
22 Correct 1 ms 4444 KB ok
23 Correct 1 ms 4444 KB ok
24 Partially correct 1 ms 4444 KB partial
25 Partially correct 1 ms 4444 KB partial
26 Partially correct 1 ms 4532 KB partial
27 Partially correct 1 ms 4440 KB partial
28 Partially correct 1 ms 4444 KB partial
29 Partially correct 1 ms 4440 KB partial
30 Partially correct 1 ms 4444 KB partial
31 Partially correct 1 ms 4444 KB partial
32 Partially correct 1 ms 4444 KB partial
33 Partially correct 1 ms 4444 KB partial
34 Correct 2 ms 4444 KB ok
35 Correct 1 ms 4444 KB ok
36 Partially correct 1 ms 4444 KB partial
37 Partially correct 1 ms 4444 KB partial
38 Partially correct 1 ms 4444 KB partial
39 Partially correct 1 ms 4444 KB partial
40 Partially correct 1 ms 4444 KB partial
41 Partially correct 1 ms 4440 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 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 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 2 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6492 KB ok
17 Partially correct 1 ms 4440 KB partial
18 Partially correct 1 ms 4596 KB partial
19 Partially correct 1 ms 4444 KB partial
20 Partially correct 1 ms 4548 KB partial
21 Partially correct 1 ms 4440 KB partial
22 Correct 1 ms 4444 KB ok
23 Correct 1 ms 4444 KB ok
24 Partially correct 1 ms 4444 KB partial
25 Partially correct 1 ms 4444 KB partial
26 Partially correct 1 ms 4532 KB partial
27 Partially correct 1 ms 4440 KB partial
28 Partially correct 1 ms 4444 KB partial
29 Partially correct 1 ms 4440 KB partial
30 Partially correct 1 ms 4444 KB partial
31 Partially correct 1 ms 4444 KB partial
32 Partially correct 1 ms 4444 KB partial
33 Partially correct 1 ms 4444 KB partial
34 Correct 2 ms 4444 KB ok
35 Correct 1 ms 4444 KB ok
36 Partially correct 1 ms 4444 KB partial
37 Partially correct 1 ms 4444 KB partial
38 Partially correct 1 ms 4444 KB partial
39 Partially correct 1 ms 4444 KB partial
40 Partially correct 1 ms 4444 KB partial
41 Partially correct 1 ms 4440 KB partial
42 Partially correct 42 ms 29776 KB partial
43 Partially correct 37 ms 29784 KB partial
44 Partially correct 49 ms 35816 KB partial
45 Partially correct 44 ms 35612 KB partial
46 Partially correct 41 ms 31268 KB partial
47 Partially correct 44 ms 38652 KB partial
48 Execution timed out 4549 ms 34832 KB Time limit exceeded
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 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 6492 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 2 ms 4700 KB ok
9 Correct 15 ms 6488 KB ok
10 Correct 238 ms 37972 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 2 ms 6492 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6492 KB ok
18 Correct 2 ms 6492 KB ok
19 Correct 1 ms 6492 KB ok
20 Correct 1 ms 6492 KB ok
21 Correct 1 ms 6492 KB ok
22 Partially correct 1 ms 4440 KB partial
23 Partially correct 1 ms 4596 KB partial
24 Partially correct 1 ms 4444 KB partial
25 Partially correct 1 ms 4548 KB partial
26 Partially correct 1 ms 4440 KB partial
27 Correct 1 ms 4444 KB ok
28 Correct 1 ms 4444 KB ok
29 Partially correct 1 ms 4444 KB partial
30 Partially correct 1 ms 4444 KB partial
31 Partially correct 1 ms 4532 KB partial
32 Partially correct 1 ms 4440 KB partial
33 Partially correct 1 ms 4444 KB partial
34 Partially correct 1 ms 4440 KB partial
35 Partially correct 1 ms 4444 KB partial
36 Partially correct 1 ms 4444 KB partial
37 Partially correct 1 ms 4444 KB partial
38 Partially correct 1 ms 4444 KB partial
39 Correct 2 ms 4444 KB ok
40 Correct 1 ms 4444 KB ok
41 Partially correct 1 ms 4444 KB partial
42 Partially correct 1 ms 4444 KB partial
43 Partially correct 1 ms 4444 KB partial
44 Partially correct 1 ms 4444 KB partial
45 Partially correct 1 ms 4444 KB partial
46 Partially correct 1 ms 4440 KB partial
47 Partially correct 42 ms 29776 KB partial
48 Partially correct 37 ms 29784 KB partial
49 Partially correct 49 ms 35816 KB partial
50 Partially correct 44 ms 35612 KB partial
51 Partially correct 41 ms 31268 KB partial
52 Partially correct 44 ms 38652 KB partial
53 Execution timed out 4549 ms 34832 KB Time limit exceeded
54 Halted 0 ms 0 KB -