Submission #112157

#	Time	Username	Problem	Language	Result	Execution time	Memory
112157		dolphingarlic	Sajam (COCI18_sajam)	C++14	90 / 90	3111 ms	3684 KiB

sajam

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

pair<int, bool> getRowCol(vector<vector<char> > grid, int n) {
    vector<int> rows(n, 0), columns(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rows[i] += grid[i][j] == 'x' ? 1 : 0;
            columns[i] += grid[j][i] == 'x' ? 1 : 0;
        }
    }

    int max_rows = *max_element(rows.begin(), rows.end());
    int max_columns = *max_element(columns.begin(), columns.end());
    if (max_rows >= max_columns  && max_rows > n / 2) {
        return pair<int, bool>(find(rows.begin(), rows.end(), max_rows) - rows.begin(), true);
    } else if (max_columns >= max_rows && max_columns > n / 2) {
        return pair<int, bool>(find(columns.begin(), columns.end(), max_columns) - columns.begin(), false);
    } else {
        return pair<int, bool>(-1, false);
    }
}

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

    vector<vector<char> > grid(n);
    for (int i = 0; i < n; i++) {
        grid[i] = vector<char>(n);
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    if (k == 0) {
        pair<int, bool> result = getRowCol(grid, n);
        while (result.first != -1) {
            if (result.second) {
                for (int i = 0; i < n; i++) {
                    grid[result.first][i] = grid[result.first][i] == 'x' ? 'o' : 'x';
                }
            } else {
                for (int i = 0; i < n; i++) {
                    grid[i][result.first] = grid[i][result.first] == 'x' ? 'o' : 'x';
                }
            }

            result = getRowCol(grid, n);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'x') {
                    cout << "NE" << endl;
                    return 0;
                }
            }
        }
        cout << "DA" << endl;
    } else {
        pair<int, bool> result = getRowCol(grid, n);
        while (result.first != -1) {
            if (result.second) {
                for (int i = 0; i < n; i++) {
                    grid[result.first][i] = grid[result.first][i] == 'x' ? 'o' : 'x';
                }
            } else {
                for (int i = 0; i < n; i++) {
                    grid[i][result.first] = grid[i][result.first] == 'x' ? 'o' : 'x';
                }
            }

            result = getRowCol(grid, n);
        }

        int on = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'x') {
                    on++;
                }
            }
        }

        if (on > k) {
            cout << "NE" << endl;
        } else {
            cout << "DA" << endl;
        }
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15