Submission #1122570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122570		deera	Soccer Stadium (IOI23_soccer)	C++17	52 / 100	448 ms	44404 KiB

soccer

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

struct Point {
    int x, y;
    Point(int x, int y): x(x), y(y) {}
};

bool operator<(const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int biggest_stadium(int N, vector<vector<int>> F) {
    int num_trees = 0;
    for (auto i: F) for (int j: i) num_trees += j;

    if (num_trees == 0) {
        return N*N;
    }
    
    if (num_trees == 1) {
        int x, y;
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) 
            if (F[i][j] == 1) {
                x = i, y = j; 
                break;
            }

        return N*N - min(x + 1, N - x) * min(y + 1, N - y);
    }

    for (int i = 0; i < N; i++) {
        F[i].insert(F[i].begin(), 1);
        F[i].push_back(1);
    }

    F.insert(F.begin(), vector<int>(N + 2, 1));
    F.push_back(vector<int>(N + 2, 1));

    N += 2;

    if (N <= 10) {

        vector<vector<set<Point>>> quads[4];
        for (auto &q: quads) q.resize(N, vector<set<Point>>(N, set<Point>()));

        // index, dx, dy, starting x, starting y, x increment, y increment
        int m = N - 1;
        int quad_dirs[4][7] = {
            {0, -1, -1, 0, 0,  1,  1},
            {1, -1,  1, 0, m,  1, -1},
            {2,  1,  1, m, m, -1, -1},
            {3,  1, -1, m, 0, -1,  1}
        };

        for (auto [idx, dx, dy, sx, sy, ix, iy]: quad_dirs) {
            for (int i = sx; i < N && i >= 0; i += ix) for (int j = sy; j < N && j >= 0; j += iy) {
                if (F[i][j] == 1) continue;

                int a[2] = {i + dx, j};
                int b[2] = {i, j + dy};
                if (F[a[0]][a[1]] == 0) 
                    for (auto p: quads[idx][a[0]][a[1]]) if (p.y == j) quads[idx][i][j].insert(p);
                if (F[b[0]][b[1]] == 0) 
                    for (auto p: quads[idx][b[0]][b[1]]) if (p.x == i) quads[idx][i][j].insert(p);

                quads[idx][i][j].insert(Point(i, j));
            }
        }

        vector<vector<set<Point>>> lines = vector<vector<set<Point>>>(N, vector<set<Point>>(N, set<Point>()));
        for (int i = 0; i < N; i++) 
        for (int j = 0; j < N; j++) 
        for (int k = 0; k < 4; k++) 
            for (auto p: quads[k][i][j]) lines[i][j].insert(p);

        for (auto [idx, dx, dy, sx, sy, ix, iy]: quad_dirs) {
            for (int i = sx; i < N && i >= 0; i += ix) for (int j = sy; j < N && j >= 0; j += iy) {
                if (F[i][j] == 1) continue;

                int a[2] = {i + dx, j};
                int b[2] = {i, j + dy};
                if (F[a[0]][a[1]] == 1 || F[b[0]][b[1]] == 1) continue;

                set<Point> temp;
                set_intersection(quads[idx][a[0]][a[1]].begin(), quads[idx][a[0]][a[1]].end(),
                          quads[idx][b[0]][b[1]].begin(), quads[idx][b[0]][b[1]].end(),
                          inserter(temp, temp.begin()));
                for (auto p: temp) quads[idx][i][j].insert(p);
            }
        }

        int max_area = 0;
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
            if (F[i][j] == 1) continue;

            auto print_union = [&](set<Point> &a, set<Point> &b, set<Point> &c) {
                // return;
                set<Point> t;
                for (auto p: a) t.insert(p);
                for (auto p: b) t.insert(p);
                for (auto p: c) t.insert(p);
                for (int x = 0; x < N; x++) {
                    for (int y = 0; y < N; y++) {
                        if (x == i && y == j) cerr << "X ";
                        else cerr << (t.count(Point(x, y)) ? 'x' : (F[x][y] ? '-': ' ')) << " ";
                    }
                    cerr << endl;
                }
                cerr << endl;
            };
            
            auto union_size = [&](set<Point> &a, set<Point> &b, set<Point> &c) {
                set<Point> t;
                for (auto p: a) t.insert(p);
                for (auto p: b) t.insert(p);
                for (auto p: c) t.insert(p);
                
                vector<pair<int, int>> rows = vector<pair<int, int>>(N, {N, 0});
                int max_row_len = 0;
                for (auto p: t) {
                    rows[p.x].first  = min(rows[p.x].first , p.y);
                    rows[p.x].second = max(rows[p.x].second, p.y);
                    max_row_len = max(max_row_len, rows[p.x].second - rows[p.x].first);
                }

                int max_row_beg = N, max_row_end = 0;
                for (int i = 0; i < N; i++) {
                    if (rows[i].first == 0 && rows[i].second == N) continue;
                    if (rows[i].second - rows[i].first == max_row_len) {
                        max_row_beg = min(max_row_beg, i);
                        max_row_end = max(max_row_end, i);
                    }
                }

                int max_ext_len = 0;
                int best_i = 0;
                for (int i = max_row_beg; i <= max_row_end; i++) {
                    // try to see if it's extendable
                    set<Point> l_ext;
                    for (auto p: quads[0][i][rows[i].first  - 1]) if (p.x >= max_row_beg) l_ext.insert(p);
                    for (auto p: quads[3][i][rows[i].first  - 1]) if (p.x <= max_row_end) l_ext.insert(p);

                    set<Point> r_ext;
                    for (auto p: quads[1][i][rows[i].second + 1]) if (p.x >= max_row_beg) r_ext.insert(p);
                    for (auto p: quads[2][i][rows[i].second + 1]) if (p.x <= max_row_end) r_ext.insert(p);

                    if (r_ext.size() + l_ext.size() > max_ext_len) {
                        // set<Point> s;
                        // for (auto p: r_ext) s.insert(p);
                        // for (auto p: l_ext) s.insert(p);

                        deque<Point> vec_r = deque<Point>(r_ext.begin(), r_ext.end());
                        deque<Point> vec_l = deque<Point>(l_ext.begin(), l_ext.end());
                        sort(vec_r.begin(), vec_r.end());
                        sort(vec_l.begin(), vec_l.end(), [](Point a, Point b) {
                            return a.x > b.x || (a.x == b.x && a.y > b.y);
                        });

                        while (vec_r.size() && vec_l.size()) {
                            Point r = vec_r.back();
                            Point l = vec_l.back();

                            if (r_ext.count(Point(l.x, r.y)) && l_ext.count(Point(r.x, l.y))) {
                               break;
                            } else {
                                if (rows[max_row_beg].first - r.y > l.y - rows[max_row_beg].second) {
                                    vec_l.pop_back();
                                } else {
                                    vec_r.pop_back();
                                }
                            }
                        }

                        sort(vec_r.begin(), vec_r.end(), [](Point a, Point b) {
                            return a.x > b.x;
                        });
                        sort(vec_l.begin(), vec_l.end(), [](Point a, Point b) {
                            return a.x < b.x;
                        });

                        while (vec_r.size() && vec_l.size()) {
                            Point r = vec_r.back();
                            Point l = vec_l.back();

                            if (r_ext.count(Point(l.x, r.y)) && l_ext.count(Point(r.x, l.y))) {
                               break;
                            } else {
                                if (rows[max_row_beg].first - r.y > l.y - rows[max_row_beg].second) {
                                    vec_l.pop_back();
                                } else {
                                    vec_r.pop_back();
                                }
                            }
                        }
                        
                        

                        if (vec_r.size() + vec_l.size() > max_ext_len) {
                            max_ext_len = vec_r.size() + vec_l.size();
                            best_i = i;
                        }
                    }
                }


                int size = t.size() + max_ext_len;

                // if (size == 6) {
                //     cerr << "ext" << endl;
                //     cerr << max_row_beg << " " << max_row_end << endl;
                //     set<Point> e = set<Point>();
                //     int i = best_i;
                //     print_union(quads[0][i][rows[i].first  - 1], e, e);
                //     print_union(quads[3][i][rows[i].first  - 1], e, e);
                //     print_union(quads[1][i][rows[i].second + 1], e, e);
                //     print_union(quads[2][i][rows[i].second + 1], e, e);

                //     print_union(max_ext, max_ext, max_ext);
                //     print_union(t, t, t);
                //     print_union(t, max_ext, max_ext);
                // }

                return size;
            };

            auto extreme = [&](set<Point> &t) {
                int minx = N, maxx = 0, miny = N, maxy = 0;
                for (auto p: t) {
                    minx = min(minx, p.x);
                    maxx = max(maxx, p.x);
                    miny = min(miny, p.y);
                    maxy = max(maxy, p.y);
                }

                vector<Point> res;
                for (auto p: t) {
                    if (p.x == minx || p.x == maxx || p.y == miny || p.y == maxy) res.push_back(p);
                }
                return res;
            };

            for (int k = 0; k < 4; k++) {
                int a = k, b = (k + 1) % 4, c = (k + 2) % 4;

                vector<Point> a_extreme = extreme(quads[a][i][j]);
                vector<Point> c_extreme = extreme(quads[c][i][j]);

                bool possible = true;
                for (auto ap: a_extreme) for (auto cp: c_extreme) {
                    if (ap.x == cp.x && ap.y == cp.y) continue;
                    if (!(
                        quads[b][i][j].count(Point(ap.x, cp.y)) ||
                        quads[b][i][j].count(Point(cp.x, ap.y))
                    )) {
                        possible = false;
                        break;
                    }
                }

                if (possible) {
                    int area = union_size(quads[a][i][j], quads[b][i][j], quads[c][i][j]);

                    if (area > max_area) {
                        max_area = area;
                        print_union(quads[a][i][j], quads[b][i][j], quads[c][i][j]);

                        // for (auto p: a_extreme) cerr << p.x << " " << p.y << endl;
                        // cerr << endl;
                        // for (auto p: c_extreme) cerr << p.x << " " << p.y << endl;
                        // cerr << endl;

                        set<Point> t;
                        print_union(quads[a][i][j], t, t);
                        print_union(t, quads[b][i][j], t);
                        print_union(t, t, quads[c][i][j]);
                    }
                }
            }



            for (int k = 0; k < 4; k++) {
                int area = union_size(quads[k][i][j], quads[(k + 1) % 4][i][j], lines[i][j]);

                if (area > max_area) {
                    max_area = area;
                    print_union(quads[k][i][j], quads[(k + 1) % 4][i][j], lines[i][j]);
                }
            }
        }

        return max_area;
    }



    // for (auto row: F) {
    //     bool beg = false, end = false;
    //     for (int i: row) {
    //         if (i == 0 && !beg) beg = true;
    //         if (i == 1 &&  beg) end = true;
    //         if (i == 0 &&  end) return 0;
    //     }
    // }

    bool beg, end;
    for (int i = 0; i < N; i++) {
        beg = false, end = false;
        for (int j = 0; j < N; j++) {
            if (F[j][i] == 0 && !beg) beg = true;
            if (F[j][i] == 1 &&  beg) end = true;
            if (F[j][i] == 0 &&  end) return 0;
        }

        beg = false, end = false;
        for (int j = 0; j < N; j++) {
            if (F[i][j] == 0 && !beg) beg = true;
            if (F[i][j] == 1 &&  beg) end = true;
            if (F[i][j] == 0 &&  end) return 0;
        }
    }


    auto valid = [&](int n) {
        return n >= 0 && n < N;
    };

    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    vector<vector<bool>> seen(N, vector<bool>(N, false));
    queue<tuple<int, int, bool>> q;

    bool f1 = false, f0 = false;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (!f1 && F[i][j] == 1)
            q.push({i, j, 1}), f1 = 1, seen[i][j] = true;
        if (!f0 && F[i][j] == 0)
            q.push({i, j, 0}), f0 = 1, seen[i][j] = true;
    }

    while (!q.empty()) {
        auto [x, y, t] = q.front();
        q.pop();

        for (auto [dx, dy]: dirs) {
            int nx = x + dx, ny = y + dy;
            if (valid(nx) && valid(ny) && !seen[nx][ny] && F[nx][ny] == t) {
                q.push({nx, ny, t});
                seen[nx][ny] = true;
            }
        }
    }

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (!seen[i][j]) return 0; // islands!!!

    
    // most extreme zeros
    // Point minx = {N, N}, maxx = {0, 0}, miny = {N, N}, maxy = {0, 0};
    // for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
    //     if (F[i][j] == 0) {
    //         if (i < minx.x) minx = {i, j};
    //         if (i > maxx.x) maxx = {i, j};
    //         if (j < miny.y) miny = {i, j};
    //         if (j > maxy.y) maxy = {i, j};
    //     }
    // }

    // Point points[4] = {minx, maxx, miny, maxy};

    vector<Point> points;

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (F[i][j] == 0) {
            int corners[4][2][2] = {
                {{ 1, 0}, {0,  1}},
                {{ 1, 0}, {0, -1}},
                {{-1, 0}, {0,  1}},
                {{-1, 0}, {0, -1}}
            };

            for (auto [a, b]: corners) {
                int ax = i + a[0], ay = j + a[1];
                int bx = i + b[0], by = j + b[1];

                if (F[ax][ay] + F[bx][by] == 2) {
                    points.push_back(Point(i, j));
                    break;
                }
            }
        }
    }


    for (int i = 0; i < points.size(); i++) for (int j = i + 1; j < points.size(); j++) {
        if (F[points[i].x][points[j].y] + F[points[j].x][points[i].y] == 2) {
            return 0; // 3 or more kicks
        }
    }

    int zeros = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (F[i][j] == 0) zeros++;
    }

    return zeros;
}

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