제출 #944585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944585		Nhoksocqt1	축구 경기장 (IOI23_soccer)	C++17	24 / 100	251 ms	38172 KiB

soccer

#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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30