Submission #847919

#	Time	Username	Problem	Language	Result	Execution time	Memory
847919		pipev	Soccer Stadium (IOI23_soccer)	C++17	Compilation error	0 ms	0 KiB

soccer

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<vector<vector<int>>>& combinations, vector<vector<int>> toCombine, int itemsLeft, vector<vector<int>> currentCombination) {
    if (itemsLeft == 0) {
        combinations.push_back(currentCombination);
        return;
    }
    for (int i = 0; i < toCombine.size(); i++) {
        vector<vector<int>> currentCombinationClone = currentCombination;
        vector<vector<int>> toCombineClone = toCombine;

        currentCombinationClone.push_back(toCombine[i]);
        toCombineClone.erase(toCombineClone.begin() + i);

        backtrack(combinations, toCombineClone, itemsLeft - 1, currentCombinationClone);
    }
}

bool checkValidity(vector<vector<int>> s, vector<vector<int>> F) {
    vector<vector<vector<int>>> combinations;

    backtrack(combinations, s, 2, {});

    /*for (vector<vector<int>> x : combinations) {
        cout << x[0][0] << " " << x[0][1] << "  ;  " << x[1][0] << " " << x[1][1] << endl;
    }*/

    for (vector<vector<int>> comb : combinations) {
        bool validCombination = false;

        //cout << comb[0][0] << " " << comb[0][1] << "  ;  " << comb[1][0] << " " << comb[1][1] << endl;

        // misma fila
        if (comb[0][1] == comb[1][1]) {
            bool foundShit = false;

            int starter, ender;

            if (comb[0][0] > comb[1][0]) {
                starter = comb[1][0];
                ender = comb[0][0];
            } else {
                starter = comb[0][0];
                ender = comb[1][0];
            }

            for (int i = starter; i <= ender; i++) {
                if (F[i][comb[0][1]] == 1) {
                    foundShit = true;
                    break;
                }
            }

            if (!foundShit) {
                validCombination = true;
            } else {
                return false;
            }
        }


        // misma columna
        if (comb[0][0] == comb[1][0]) {
            bool foundShit = false;

            int starter, ender;

            if (comb[0][0] > comb[1][0]) {
                starter = comb[1][0];
                ender = comb[0][0];
            } else {
                starter = comb[0][0];
                ender = comb[1][0];
            }

            for (int i = starter; i <= ender; i++) {
                if (F[i][comb[0][0]] == 1) {
                    foundShit = true;
                    break;
                }
            }

            if (!foundShit) {
                validCombination = true;
            } else {
                return false;
            }
        }

        // 2 movimientos

        // primero c despues r
        int starter, ender;

        if (comb[0][0] > comb[1][0]) {
            starter = comb[1][0];
            ender = comb[0][0];
        } else {
            starter = comb[0][0];
            ender = comb[1][0];
        }


        // cout << starter << ", " << ender << endl;
        bool foundShit = false;
        for (int i = starter; i <= ender; i++) {
            //cout << i << ", "  << comb[0][1] << ", " << F[i][comb[0][1]] << endl;

            if (F[i][comb[0][1]] == 1) {
                //cout << "autista1" << endl;
                foundShit = true;
                break;
            }
        }

        if (!foundShit) {
            int currentY = comb[1][1];

            if (comb[0][1] > comb[1][1]) {
                starter = comb[0][1];
                ender = comb[1][1];
            } else {
                starter = comb[1][1];
                ender = comb[0][1];
            }

            //cout << starter << ", " << ender << ", " << currentY << endl;

            bool foundShit = false;
            for (int i = starter; i <= ender; i++) {
                if (F[currentY][i] == 1) {
                        //cout << "autista2" << endl;
                        //cout << "err2" << endl;
                    foundShit = true;
                    break;
                }
            }

            if (!foundShit) {
                validCombination = true;
            }
        }

        // ahora primero r y despues c
        if (comb[0][1] > comb[1][1]) {
            starter = comb[1][1];
            ender = comb[0][1];
        } else {
            starter = comb[0][1];
            ender = comb[1][1];
        }

        //cout << starter << ", " << ender << endl;

        foundShit = false;
        for (int i = starter; i <= ender; i++) {

            if (F[comb[0][0]][i] == 1) {
                //cout << "autista3" <<endl;
                foundShit = true;
                break;
            }
        }

        if (!foundShit) {
            int currentY = comb[1][0];

            if (comb[0][0] > comb[1][0]) {
                starter = comb[1][0];
                ender = comb[0][0];
            } else {
                starter = comb[0][0];
                ender = comb[1][0];
            }

            bool foundShit = false;
            for (int i = starter; i <= ender; i++) {
                if (F[i][currentY] == 1) {
                    //cout << "autista4" <<endl;
                    foundShit = true;
                    break;
                }
            }

            if (!foundShit) {
                validCombination = true;
            }
        }

        // validacion
        if (!validCombination) {
            //cout << comb[0][0] << " " << comb[0][1] << "  ;  " << comb[1][0] << " " << comb[1][1] << endl;
            return false;
        }
    }

    return true;
}

bool present(vector<vector<int>> where, vector<int> what) {
    for (vector<int> x : where) {
        if (x[0] == what[0] && x[1] == what[1]) {
            return true;
        }
    }
    return false;
}

int biggest_stadium(int N, vector<vector<int>> F) {
    vector<int> sValues;

    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            vector<vector<int>> currentCells = {{x, y}};

            if (F[x][y] == 1) {
                continue;
            }

            bool foundExpansion = true;

            while (foundExpansion) {
                foundExpansion = false;

                for (vector<int> cell : currentCells) {
                    // derecha
                    if (cell[0] != N - 1 && F[cell[0] + 1][cell[1]] == 0 && !present(currentCells, {cell[0] + 1, cell[1]})) {
                        //cout << "a" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0] + 1, cell[1]});

                        /*for (vector<int> x: currentCells) {
                            cout << x[0] << ", " << x[1] << ", ";
                        }*/

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // izquierda
                    if (cell[0] != 0 && F[cell[0] - 1][cell[1]] == 0 && !present(currentCells, {cell[0] - 1, cell[1]})) {
                        //cout << "b" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0] - 1, cell[1]});

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // arriba
                    if (cell[1] != 0 && F[cell[0]][cell[1] - 1] == 0 && !present(currentCells, {cell[0], cell[1] - 1})) {
                        //cout << "c" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0], cell[1] - 1});

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // abajo
                    if (cell[1] != N - 1 && F[cell[0]][cell[1] + 1] == 0 && !present(currentCells, {cell[0], cell[1] + 1})) {
                        //cout << "d" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0], cell[1] + 1});

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // arriba derecha
                    if (cell[0] != N - 1 && cell[1] != 0 && F[cell[0] + 1][cell[1] - 1] == 0 && !present(currentCells, {cell[0] + 1, cell[1] - 1})) {
                        //cout << "e" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0] + 1, cell[1] - 1});

                        /*for (vector<int> x: currentCells) {
                            cout << x[0] << ", " << x[1] << ", ";
                        }
                        cout << endl;*/

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // arriba izquierda
                    if (cell[0] != 0 && cell[1] != 0 && F[cell[0] - 1][cell[1] - 1] == 0 && !present(currentCells, {cell[0] - 1, cell[1] - 1})) {
                        //cout << "f" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0] - 1, cell[1] - 1});

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // abajo derecha
                    if (cell[0] != N - 1 && cell[1] != N - 1 && F[cell[0] + 1][cell[1] + 1] == 0 && !present(currentCells, {cell[0] + 1, cell[1] + 1})) {
                        //cout << "g" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0] + 1, cell[1] + 1});

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }

                    // abajo izquierda
                    if (cell[0] != 0 && cell[1] != N - 1 && F[cell[0] - 1][cell[1] + 1] == 0 && !present(currentCells, {cell[0] - 1, cell[1] + 1})) {
                        //cout << "h" << endl;
                        vector<vector<int>> currentCellsClone = currentCells;
                        currentCellsClone.push_back({cell[0] - 1, cell[1] + 1});

                        if (checkValidity(currentCellsClone, F)) {
                            currentCells = currentCellsClone;
                            foundExpansion = true;
                            break;
                        }
                    }
                }


            }
            sValues.push_back(currentCells.size());
        }
    }
    int m = sValues[0];
    for (int x : sValues) {
        if (x > m) {
            m = x;
        }
    }
    return m;
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> F;

    for (int i = 0; i < n; i++) {
        vector<int> toAppend;
        string line;
        cin >> line;

        for (int k = 0; k < n; k++) {
            toAppend.push_back(line[k] - '0');
        }

        F.push_back(toAppend);
    }

    //vector<vector<int>> F = {{0, 0, 0}, {0, 0, 1}, {0, 0, 0}};

    //vector<vector<int>> s = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {3, 0}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {4, 3}, {4, 4}};

    //vector<vector<int>> s = {{0, 2}, {1, 0}};

    //cout << checkValidity(s, F);

    cout << biggest_stadium(n, F);

    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'void backtrack(std::vector<std::vector<std::vector<int> > >&, std::vector<std::vector<int> >, int, std::vector<std::vector<int> >)':
soccer.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < toCombine.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccSaPGR9.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc5K6kMb.o:soccer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status