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
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <map>
#include <set>

int main() {
    int t, n, len, off;
    std::string s;
    char *data;
    char *pos;
    char prev;
    long long res;
    bool infection;
    std::map<int, std::set<char*>, std::greater<int> > dict;

    std::cin >> t;
    while(t--) {
        std::cin >> n >> s;
        data = s.data();
        prev = ' ';
        len = 0;
        res = 0;
        infection = false;
        dict.clear();
        while(*data) {
            if(*data == '0') {
                if(*data != prev) {
                    pos = data;
                    len = 1;
                } else {
                    len++;
                }
            } else {
                infection = true;
                if(len) {
                    auto found = dict.find(len);
                    if(found == dict.end()) {
                        dict[len] = {};
                    }
                    dict[len].insert(pos);

                    len = 0;
                }
            }
            prev = *data;
            data++;
        }
        if(len) {
            auto found = dict.find(len);
            if(found == dict.end()) {
                dict[len] = {};
            }
            dict[len].insert(pos);
        }

        data = s.data();
        off = 0;
        if(infection) {
            for(auto const& el : dict) {
                if(off > el.first) {
                    break;
                }
                if(el.second.count(data)) {
                    int xx = el.first-off;
                    if(xx > 0) {
                        res += xx;
                    }
                    off++;
                    dict[el.first].erase(data);
                }
                if(el.second.count(data+s.size()-el.first)) {
                    int xx = el.first-off;
                    if(xx > 0) {
                        res += xx;
                    }
                    off++;
                    dict[el.first].erase(data+s.size()-el.first);
                }
                for(auto const& x : el.second) {
                    int xx = el.first-off;
                    if(xx > 1) {
                        res += xx-1;
                        off+=2;
                    } else if(xx > 0) {
                        res++;
                        off++;
                    }
                }
            }
            res = n-res;
        } else {
            res = 0;
        }
        
        std::cout << res << std::endl;
    }

    return 0;
}