oj.uz

Submission #311205

# Submission time Handle Problem Language Result Execution time Memory
311205 2020-10-09T15:57:02 Z phathnv Sajam (COCI18_sajam) C++11
90 / 90
 138 ms 1528 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "SAJAM"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1001;

int n, k;
char s[N];
bitset <N> a[N];

void readInput(){
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++){
        scanf("%s", s + 1);
        for(int j = 1; j <= n; j++)
            a[i][j] = (s[j] == 'o');
    }
}

int calc(int x1, int x2){
    int res = (a[x1] ^ a[x2]).count();
    if (res > n / 2)
        res = n - res;
    return res;
}

void solve(){
    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= n; j++)
            cnt += calc(i, j);
        if (cnt <= k){
            printf("DA");
            return;
        }
    }
    if (k < n){
        printf("NE");
        return;
    }

    for(int i = 1; i <= n; i++){
        a[1][i].flip();

        int cnt = 1;
        for(int j = 1; j <= n; j++)
            cnt += calc(1, j);
        if (cnt <= k){
            printf("DA");
            return;
        }

        a[1][i].flip();
    }
    printf("NE");
}

int main(){
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    readInput();
    solve();
    return 0;
}

Compilation message

sajam.cpp: In function 'void readInput()':
sajam.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sajam.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |         scanf("%s", s + 1);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 20 ms 640 KB Output is correct
8 Correct 72 ms 1432 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 70 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 9 ms 1280 KB Output is correct
6 Correct 23 ms 768 KB Output is correct
7 Correct 45 ms 1016 KB Output is correct
8 Correct 47 ms 1024 KB Output is correct
9 Correct 14 ms 544 KB Output is correct
10 Correct 77 ms 1528 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1152 KB Output is correct
2 Correct 8 ms 1148 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 74 ms 1420 KB Output is correct
7 Correct 18 ms 640 KB Output is correct
8 Correct 41 ms 896 KB Output is correct
9 Correct 46 ms 1024 KB Output is correct
10 Correct 79 ms 1528 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 110 ms 1408 KB Output is correct
4 Correct 37 ms 640 KB Output is correct
5 Correct 44 ms 888 KB Output is correct
6 Correct 134 ms 1408 KB Output is correct
7 Correct 43 ms 640 KB Output is correct
8 Correct 46 ms 760 KB Output is correct
9 Correct 49 ms 768 KB Output is correct
10 Correct 46 ms 752 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1408 KB Output is correct
2 Correct 10 ms 1408 KB Output is correct
3 Correct 109 ms 1280 KB Output is correct
4 Correct 80 ms 896 KB Output is correct
5 Correct 44 ms 1016 KB Output is correct
6 Correct 84 ms 1024 KB Output is correct
7 Correct 43 ms 640 KB Output is correct
8 Correct 111 ms 1244 KB Output is correct
9 Correct 61 ms 768 KB Output is correct
10 Correct 138 ms 1400 KB Output is correct