2110327-Algorithm-Design/a63_q1b_virus2.cpp at main · faith-cr/2110327-Algorithm-Design · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

int check(std::vector<int> &v, int start, int stop, bool &valid);

int main() {
    std::ios_base::sync_with_stdio(false);std::cin.tie(0);
    int n, k;std::cin >> n >> k;
    std::vector<int> v(pow(2, k));
    //queries
    while (n--) {
        for (int i = 0; i < pow(2, k); i++) {
            std::cin >> v[i];
        }
        bool valid = true;
        check(v, 0, v.size()-1, valid);
        std::cout << ((valid) ? "yes\n" : "no\n");
    }
    return 0;
}

int check(std::vector<int> &v, int start, int stop, bool &valid) {
    if (! valid) return -1;
    if (start+1 == stop) {
        if (v[start] == 0 && v[stop] == 0) return 0;
        if (v[start] == 1 && v[stop] == 1) return 2;
        return 1;
    }
    int mid = (start+stop)/2;
    int left = check(v, start, mid, valid);
    int right = check(v, mid+1, stop, valid);
    if (! valid) return -1;
    int res = abs(left-right);
    if (res > 1) {
        valid = false;
        return -1;
    }
    return left+right; //return number of one
}

// bool valid(std::vector<int> &v, int start, int stop) {
//     if (start+3 == stop) {
//         if (v[start] == v[start+1] && v[start+2] == v[start+3] && v[start+1] != v[start+2]) {
//             return false;
//         }
//         return true;
//     }
//     int mid = (start+stop)/2;
//     if(! valid(v, 0, mid) || ! valid(v, mid+1, stop)) return false;
//     1left - 1 right not exceeding 1
// }

/*
5 2
0 0 0 0
0 0 1 1
0 1 1 1
1 0 0 0
0 1 0 1

yes
no
yes
yes
yes

4 3
0 0 1 1 0 0 1 1
0 0 1 1 1 0 0 0
0 1 0 1 0 1 1 1
0 1 0 1 1 1 0 0

no
no
yes
no

3 4
1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1
1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1
no
yes
yes
*/