oj.uz

Submission #180290

# Submission time Handle Problem Language Result Execution time Memory
180290 2020-01-08T15:53:08 Z Linca_Robert Sajam (COCI18_sajam) C++14
90 / 90
 77 ms 9248 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e4 + 5;

int cnt[2][DIM], N, K, a[DIM][DIM], nr;
bool mrk[2][DIM];
char s[DIM];

int main(){

    cin >> N >> K;
    for( int i = 1; i <= N; i++ ){
        cin >> s + 1;
        for( int j = 1; j <= N; j++ ){
            char x = s[j];
            a[i][j] = (x == 'o');
            cnt[0][i] += a[i][j];
            cnt[1][j] += a[i][j];
            nr += a[i][j];
        }
    }

    if( nr <= K ){
        printf( "DA\n" );
        return 0;
    }

    for( int pas = 1; pas <= 2 * N; pas++ ){
        int maxi = 0, tp, ind;
        for( int t = 0;  t <= 1; t++ )
            for( int i = 1; i <= N; i++ )
                if( maxi < cnt[t][i] && mrk[t][i] == false )
                    maxi = cnt[t][i], tp = t, ind = i;
        nr += N - 2 * cnt[tp][ind];
        cnt[tp][ind] = N - cnt[tp][ind];
        mrk[tp][ind] = true;

        if( tp == 0 ){
            for( int j = 1; j <= N; j++ ){
                cnt[1][j] -= a[ind][j];
                a[ind][j] ^= 1;
                cnt[1][j] += a[ind][j];
            }
        }else{
            for( int i = 1; i <= N; i++ ){
                cnt[0][i] -= a[i][ind];
                a[i][ind] ^= 1;
                cnt[0][i] += a[i][ind];
            }
        }

        if( nr <= K ){
            printf( "DA\n" );
            return 0;
        }

    }

    printf( "NE\n" );
    return 0;
}

Compilation message

sajam.cpp: In function 'int main()':
sajam.cpp:14:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> s + 1;
                ~~^~~
sajam.cpp:30:27: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int maxi = 0, tp, ind;
                           ^~~
sajam.cpp:35:34: warning: 'tp' may be used uninitialized in this function [-Wmaybe-uninitialized]
         nr += N - 2 * cnt[tp][ind];
                       ~~~~~~~~~~~^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 14 ms 2936 KB Output is correct
3 Correct 21 ms 3832 KB Output is correct
4 Correct 62 ms 8264 KB Output is correct
5 Correct 21 ms 3844 KB Output is correct
6 Correct 10 ms 2296 KB Output is correct
7 Correct 21 ms 3576 KB Output is correct
8 Correct 68 ms 8292 KB Output is correct
9 Correct 6 ms 1528 KB Output is correct
10 Correct 69 ms 8428 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 1 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6136 KB Output is correct
2 Correct 60 ms 7260 KB Output is correct
3 Correct 34 ms 5336 KB Output is correct
4 Correct 30 ms 4960 KB Output is correct
5 Correct 56 ms 8056 KB Output is correct
6 Correct 24 ms 3960 KB Output is correct
7 Correct 42 ms 6136 KB Output is correct
8 Correct 45 ms 6492 KB Output is correct
9 Correct 15 ms 2804 KB Output is correct
10 Correct 77 ms 9124 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7548 KB Output is correct
2 Correct 55 ms 7416 KB Output is correct
3 Correct 31 ms 5116 KB Output is correct
4 Correct 43 ms 6008 KB Output is correct
5 Correct 41 ms 6264 KB Output is correct
6 Correct 70 ms 9064 KB Output is correct
7 Correct 21 ms 3448 KB Output is correct
8 Correct 32 ms 5752 KB Output is correct
9 Correct 46 ms 6264 KB Output is correct
10 Correct 77 ms 9208 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5112 KB Output is correct
2 Correct 31 ms 5112 KB Output is correct
3 Correct 67 ms 9080 KB Output is correct
4 Correct 10 ms 4092 KB Output is correct
5 Correct 32 ms 5240 KB Output is correct
6 Correct 71 ms 8952 KB Output is correct
7 Correct 23 ms 3960 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 25 ms 4344 KB Output is correct
10 Correct 25 ms 4216 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9248 KB Output is correct
2 Correct 65 ms 8952 KB Output is correct
3 Correct 46 ms 8444 KB Output is correct
4 Correct 38 ms 5880 KB Output is correct
5 Correct 42 ms 6008 KB Output is correct
6 Correct 49 ms 6136 KB Output is correct
7 Correct 25 ms 3960 KB Output is correct
8 Correct 57 ms 7672 KB Output is correct
9 Correct 33 ms 4984 KB Output is correct
10 Correct 74 ms 8820 KB Output is correct