oj.uz

답안 #944585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944585 2024-03-13T01:18:18 Z Nhoksocqt1 축구 경기장 (IOI23_soccer) C++17
24 / 100
 251 ms 38172 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 sum[MAXN][MAXN], 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);
}

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

bool checkGrid2(void) {
    vector<ii> p;
    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]);
            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)
                p.push_back(ii(i, j));
        }
    }

    if(sz(p) > 4 * nSize)
        return false;

    for (int it = 0; it < sz(p); ++it) {
        int x(p[it].fi), y(p[it].se);
        for (int jt = it + 1; jt < sz(p); ++jt) {
            int u(p[jt].fi), v(p[jt].se);
            if(!(getSum(min(u, x), y, max(u, x), y) == 0 && getSum(u, min(y, v), u, max(y, v)) == 0 || getSum(x, min(y, v), x, max(y, v)) == 0 && getSum(min(u, x), v, max(u, x), v) == 0)) {
                return false;
            }
        }
    }

    return true;
}

bool checkGrid(void) {
    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;
        }
    }

    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 || checkGrid2())
        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

Compilation message

soccer.cpp: In function 'bool checkGrid2()':
soccer.cpp:106:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  106 |             if(!(getSum(min(u, x), y, max(u, x), y) == 0 && getSum(u, min(y, v), u, max(y, v)) == 0 || getSum(x, min(y, v), x, max(y, v)) == 0 && getSum(min(u, x), v, max(u, x), v) == 0)) {
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2396 KB partial

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 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 6488 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 4700 KB ok
8 Correct 21 ms 6556 KB ok
9 Correct 251 ms 38172 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6604 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6744 KB ok
13 Correct 1 ms 6492 KB ok

Subtask #3
5.5 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2396 KB partial
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6604 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6744 KB ok
14 Correct 1 ms 6492 KB ok
15 Partially correct 1 ms 2396 KB partial
16 Partially correct 1 ms 2396 KB partial
17 Partially correct 1 ms 2392 KB partial
18 Partially correct 1 ms 2392 KB partial
19 Partially correct 1 ms 2392 KB partial
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2392 KB ok
22 Partially correct 1 ms 2396 KB partial
23 Partially correct 1 ms 2396 KB partial
24 Partially correct 1 ms 2396 KB partial
25 Partially correct 1 ms 2396 KB partial
26 Partially correct 1 ms 2396 KB partial

Subtask #4
4.5 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2396 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 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6604 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6744 KB ok
16 Correct 1 ms 6492 KB ok
17 Partially correct 1 ms 2396 KB partial
18 Partially correct 1 ms 2396 KB partial
19 Partially correct 1 ms 2392 KB partial
20 Partially correct 1 ms 2392 KB partial
21 Partially correct 1 ms 2392 KB partial
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2392 KB ok
24 Partially correct 1 ms 2396 KB partial
25 Partially correct 1 ms 2396 KB partial
26 Partially correct 1 ms 2396 KB partial
27 Partially correct 1 ms 2396 KB partial
28 Partially correct 1 ms 2396 KB partial
29 Partially correct 1 ms 2396 KB partial
30 Partially correct 1 ms 2808 KB partial
31 Partially correct 1 ms 2648 KB partial
32 Partially correct 1 ms 2652 KB partial
33 Partially correct 1 ms 2648 KB partial
34 Correct 1 ms 2648 KB ok
35 Correct 1 ms 2648 KB ok
36 Partially correct 1 ms 2652 KB partial
37 Partially correct 1 ms 2652 KB partial
38 Partially correct 1 ms 2652 KB partial
39 Partially correct 1 ms 2652 KB partial
40 Partially correct 1 ms 2652 KB partial
41 Partially correct 1 ms 2648 KB partial

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2396 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 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6604 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6744 KB ok
16 Correct 1 ms 6492 KB ok
17 Partially correct 1 ms 2396 KB partial
18 Partially correct 1 ms 2396 KB partial
19 Partially correct 1 ms 2392 KB partial
20 Partially correct 1 ms 2392 KB partial
21 Partially correct 1 ms 2392 KB partial
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2392 KB ok
24 Partially correct 1 ms 2396 KB partial
25 Partially correct 1 ms 2396 KB partial
26 Partially correct 1 ms 2396 KB partial
27 Partially correct 1 ms 2396 KB partial
28 Partially correct 1 ms 2396 KB partial
29 Partially correct 1 ms 2396 KB partial
30 Partially correct 1 ms 2808 KB partial
31 Partially correct 1 ms 2648 KB partial
32 Partially correct 1 ms 2652 KB partial
33 Partially correct 1 ms 2648 KB partial
34 Correct 1 ms 2648 KB ok
35 Correct 1 ms 2648 KB ok
36 Partially correct 1 ms 2652 KB partial
37 Partially correct 1 ms 2652 KB partial
38 Partially correct 1 ms 2652 KB partial
39 Partially correct 1 ms 2652 KB partial
40 Partially correct 1 ms 2652 KB partial
41 Partially correct 1 ms 2648 KB partial
42 Partially correct 19 ms 9812 KB partial
43 Partially correct 22 ms 10016 KB partial
44 Partially correct 18 ms 9560 KB partial
45 Partially correct 18 ms 9564 KB partial
46 Partially correct 23 ms 9556 KB partial
47 Incorrect 18 ms 9560 KB wrong
48 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2396 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 2396 KB ok
8 Correct 1 ms 4700 KB ok
9 Correct 21 ms 6556 KB ok
10 Correct 251 ms 38172 KB ok
11 Correct 1 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 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 1 ms 6604 KB ok
18 Correct 1 ms 6492 KB ok
19 Correct 1 ms 6492 KB ok
20 Correct 1 ms 6744 KB ok
21 Correct 1 ms 6492 KB ok
22 Partially correct 1 ms 2396 KB partial
23 Partially correct 1 ms 2396 KB partial
24 Partially correct 1 ms 2392 KB partial
25 Partially correct 1 ms 2392 KB partial
26 Partially correct 1 ms 2392 KB partial
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2392 KB ok
29 Partially correct 1 ms 2396 KB partial
30 Partially correct 1 ms 2396 KB partial
31 Partially correct 1 ms 2396 KB partial
32 Partially correct 1 ms 2396 KB partial
33 Partially correct 1 ms 2396 KB partial
34 Partially correct 1 ms 2396 KB partial
35 Partially correct 1 ms 2808 KB partial
36 Partially correct 1 ms 2648 KB partial
37 Partially correct 1 ms 2652 KB partial
38 Partially correct 1 ms 2648 KB partial
39 Correct 1 ms 2648 KB ok
40 Correct 1 ms 2648 KB ok
41 Partially correct 1 ms 2652 KB partial
42 Partially correct 1 ms 2652 KB partial
43 Partially correct 1 ms 2652 KB partial
44 Partially correct 1 ms 2652 KB partial
45 Partially correct 1 ms 2652 KB partial
46 Partially correct 1 ms 2648 KB partial
47 Partially correct 19 ms 9812 KB partial
48 Partially correct 22 ms 10016 KB partial
49 Partially correct 18 ms 9560 KB partial
50 Partially correct 18 ms 9564 KB partial
51 Partially correct 23 ms 9556 KB partial
52 Incorrect 18 ms 9560 KB wrong
53 Halted 0 ms 0 KB -