Submission #847919

#TimeUsernameProblemLanguageResultExecution timeMemory
847919pipevSoccer Stadium (IOI23_soccer)C++17
Compilation error
0 ms0 KiB
#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