oj.uz

Submission #112157

# Submission time Handle Problem Language Result Execution time Memory
112157 2019-05-17T15:54:46 Z dolphingarlic Sajam (COCI18_sajam) C++14
90 / 90
 3111 ms 3684 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 173 ms 896 KB Output is correct
3 Correct 332 ms 1588 KB Output is correct
4 Correct 2260 ms 3168 KB Output is correct
5 Correct 410 ms 1272 KB Output is correct
6 Correct 72 ms 640 KB Output is correct
7 Correct 363 ms 1448 KB Output is correct
8 Correct 2199 ms 3360 KB Output is correct
9 Correct 28 ms 512 KB Output is correct
10 Correct 3021 ms 3380 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 2496 KB Output is correct
2 Correct 1612 ms 2864 KB Output is correct
3 Correct 787 ms 1952 KB Output is correct
4 Correct 645 ms 1684 KB Output is correct
5 Correct 1975 ms 3076 KB Output is correct
6 Correct 387 ms 1304 KB Output is correct
7 Correct 1107 ms 2340 KB Output is correct
8 Correct 1273 ms 2416 KB Output is correct
9 Correct 149 ms 896 KB Output is correct
10 Correct 3111 ms 3684 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 3120 KB Output is correct
2 Correct 1575 ms 2896 KB Output is correct
3 Correct 663 ms 1820 KB Output is correct
4 Correct 959 ms 2272 KB Output is correct
5 Correct 1271 ms 2372 KB Output is correct
6 Correct 2626 ms 3564 KB Output is correct
7 Correct 279 ms 1084 KB Output is correct
8 Correct 1041 ms 2184 KB Output is correct
9 Correct 1387 ms 2352 KB Output is correct
10 Correct 2990 ms 3672 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 1888 KB Output is correct
2 Correct 678 ms 1952 KB Output is correct
3 Correct 2457 ms 3540 KB Output is correct
4 Correct 370 ms 1292 KB Output is correct
5 Correct 735 ms 1996 KB Output is correct
6 Correct 2341 ms 3576 KB Output is correct
7 Correct 353 ms 1236 KB Output is correct
8 Correct 432 ms 1492 KB Output is correct
9 Correct 446 ms 1496 KB Output is correct
10 Correct 372 ms 1456 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2676 ms 3560 KB Output is correct
2 Correct 2745 ms 3488 KB Output is correct
3 Correct 2235 ms 3312 KB Output is correct
4 Correct 969 ms 2212 KB Output is correct
5 Correct 1054 ms 2180 KB Output is correct
6 Correct 1341 ms 2352 KB Output is correct
7 Correct 434 ms 1400 KB Output is correct
8 Correct 2106 ms 2924 KB Output is correct
9 Correct 625 ms 1856 KB Output is correct
10 Correct 1984 ms 3500 KB Output is correct