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
#include<bits/stdc++.h>
using namespace std;

vector<pair<bool, int> > v;
string s;
int l, p;

void popraw(){
    while(v[l].second == 0)
        l++;
    while(v[p].second == 0)
        p--;
}

int main(){
    cin >> s;
    //a->0, b->1
    v.push_back({s[0] == 'b', 1});
    for(int i = 1 ; i < s.size() ; i++){
        int it = v.size() - 1;
        int x = v[it].second;
        if(s[i] == s[i-1]){
            v[it] = {v[it].first, x+1};
        }
        else{
            v.push_back({!v[it].first, 1});
        }
    }
    long long wynik = 0;
    p = v.size() - 1;
    l = 0;

    while(true){
        while(v[l].first == v[p].first){
            if(l == p){
                cout << wynik;
                return 0;
            }
            int mini = min(v[l].second, v[p].second);
            v[l].second -= mini;
            v[p].second -= mini;
            popraw();
        }
        if(v[l].second <= v[p].second){
            wynik += v[l].second;
            v[p].second--;
            v[l+1].second--;
            if(v[l+1].second == -1){
                cout << -1;
                return 0;
            }
            if(v[l+1].second == 0){
                if(l + 2 > p){
                    cout << wynik;
                    return 0;
                }
                v[l + 2].second += v[l].second;
                v[l].second = 0;
                l += 2;
            }
            while (v[p].second == 0)
                p--;
            
        }
        else if(v[l].second > v[p].second){
            wynik += v[p].second;
            v[l].second--;
            v[p-1].second--;
            if(v[p-1].second == -1){
                cout << -1;
                return 0;
            }
            if(v[p-1].second == 0){
                if(p - 2 < l){
                    cout << wynik;
                    return 0;
                }
                v[p-2].second += v[p].second;
                v[p].second = 0;
                p -= 2;
            }
            while(v[l].second == 0)
                l++;
        }


    }
}