Submission #1056336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056336		perekopskad	Soccer Stadium (IOI23_soccer)	C++17	29.50 / 100	295 ms	130996 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
    { cout << #x << " = " << x << el; }

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

const ll N = 2e3 + 10;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));

/*
5
1 1 0 0 1
0 0 0 0 0
0 0 0 0 0
1 1 0 0 0
1 1 0 1 1
*/
ll pref[N][N], n;
vector <pii> v;

ll get(ll x1, ll y1, ll x2, ll y2) {
    ll res = pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
    return res;
}

bool check(ll i, ll j, ll i2, ll j2) {
    ll f = get(min(i, i2), j, max(i, i2), j) + get(i2, min(j, j2), i2, max(j, j2));
    ll s = get(min(i, i2), j2, max(i, i2), j2) + get(i, min(j, j2), i, max(j, j2));
    if(f && s)
        return 0;
    return 1;
}

bool good(ll x, ll y) {
    for(auto [i, j] : v)
        if(!check(i, j, x, y)) return 0;

    return 1;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    int cnt = 0; n = N;
    fr(i, 0, N - 1)
        fr(j, 0, N - 1)
            cnt += F[i][j];

    if(cnt > 1) {
        fr(i, 1, n)
            fr(j, 1, n)
                pref[i][j] = F[i - 1][j - 1] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];

        v.clear();
        ll ans = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(F[i - 1][j - 1]) continue;
                ans++;
                v.pb({i, j});
            }
        }

        ll i = 1, j = 1;
        while(F[i - 1][j - 1]) {
            j++;
            if(j > N) {
                i++; j = 1;
            }
        }
        if(!good(i, j)) return 1;

        i = 1; j = 1;
        while(F[i - 1][j - 1]) {
            i++;
            if(i > N) {
                j++; i = 1;
            }
        }
        if(!good(i, j)) return 1;

        i = 1; j = N;
        while(F[i - 1][j - 1]) {
            j--;
            if(j < 1) {
                i++; j = N;
            }
        }
        if(!good(i, j)) return 1;

        i = 1; j = N;
        while(F[i - 1][j - 1]) {
            i++;
            if(i > N) {
                j--; i = 1;
            }
        }
        if(!good(i, j)) return 1;

        i = N; j = 1;
        while(F[i - 1][j - 1]) {
            i--;
            if(i < 1) {
                j++; i = N;
            }
        }
        if(!good(i, j)) return 1;

        i = N; j = 1;
        while(F[i - 1][j - 1]) {
            j++;
            if(j > N) {
                i--; j = 1;
            }
        }
        if(!good(i, j)) return 1;

        i = N; j = N;
        while(F[i - 1][j - 1]) {
            i--;
            if(i < 1) {
                j--; i = N;
            }
        }
        if(!good(i, j)) return 1;

        i = N; j = N;
        while(F[i - 1][j - 1]) {
            j--;
            if(j < 1) {
                i--; j = N;
            }
        }
        if(!good(i, j)) return 1;

        return ans;
    }

    ll ans = N * N;
    fr(i, 0, N - 1) {
        fr(j, 0, N - 1) {
            if(F[i][j]) {
                ll x = min(i + 1, N - i);
                ll y = min(j + 1, N - j);
                chmin(ans, N * N - x * y);
            }
        }
    }

    return ans;
}

/*
int main()
{
    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 2 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 4 / 16
• Subtask 6: 7.5 / 30