Bittipeli

#include <iostream>
#include <algorithm>
#include <cstring>

typedef long long int ll;

using namespace std;

int state  [100000] = {0};
int checked[100000] = {0};
int conv   [100000] = {0};
int moves  [100000] = {0};
int numMoves = 0;
int n;
int qaq = 0;

int nextMove() {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        if (state[0] > 1) {
            moves[numMoves] = 1;
            ++numMoves;
        } else {
            cout << "QAQ" << endl;
            qaq = 1;
        }
        return 0;
    }
    checked[0] = state[0] > 1;
    checked[n-1] = state[n-1] > 1;
    for (int i = 1; i < n-1; ++i) {
        if (state[i] > 1) {
            checked[i] = min(i,n-1-i) + 1;
        } else {
            checked[i] = 0;
        }
    }

    int m = 0;
    int l = 0;
    int o = 1;
    for (int i = 0; i < n; ++i) {
        if (checked[i] > m) {
            l = i;
            m = checked[i];
        }
        if (state[i] > 1) {
            conv[i] = o;
            ++o;
        } else {
            conv[i] = 0;
        }
    }

    for (int j = 0; j < m; ++j) {
        checked[0] = max(checked[0], checked[1]-1);
        checked[n-1] = max(checked[n-1], checked[n-2]-1);
        for (int i = 1; i < n-1; ++i) {
            checked[i] = max(max(checked[i], checked[i+1]-1), checked[i-1]-1);
        }
    }

    for (int i = 0; i < n; ++i) {
        if (checked[i] == 0) {
            cout << "QAQ" << endl;
            qaq = 1;
            return 0;
        }
    }

    if (l == 0) {
        memmove(state, state + 1, n - 1);
        --n;
    } else if (l == n - 1) {
        --n;
    } else {
        state[l-1] += state[l+1];
        memmove(state+l, state+l+2, n-l-2);
        n-=2;
    }

    moves[numMoves] = conv[l];
    ++numMoves;

    return 1;
}

int main() {

    string input;
    cin >> input;
    n = input.length();
    int last = input[0] == '1';
    size_t i = 0;
    int j = 0;
    while (i < input.length()) {
        int c = input[i] == '1';
        if (c != last) {
            ++j;
            last = c;
        }
        ++state[j];
        ++i;
    }
    n=j+1;

    while (nextMove()) {}

    if (!qaq) {
        cout << numMoves << endl;
        for (int i = 0; i < numMoves; ++i) {
            cout << moves[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: WRONG ANSWER

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: WRONG ANSWER

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: WRONG ANSWER

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: ACCEPTED

Test 20

Group: 1

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: WRONG ANSWER

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 2

Verdict: ACCEPTED

Test 33

Group: 2

Verdict: ACCEPTED

Test 34

Group: 2

Verdict: ACCEPTED

Test 35

Group: 2

Verdict: WRONG ANSWER

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: ACCEPTED

Test 38

Group: 2

Verdict: WRONG ANSWER

Test 39

Group: 2

Verdict: ACCEPTED

Test 40

Group: 2

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: WRONG ANSWER

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: WRONG ANSWER

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED

Test 55

Group: 3

Verdict: WRONG ANSWER

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: ACCEPTED

Test 58

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 59

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 60

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 61

Group: 4

Verdict: ACCEPTED

Test 62

Group: 4

Verdict: WRONG ANSWER

Test 63

Group: 4

Verdict: ACCEPTED

Test 64

Group: 4

Verdict: ACCEPTED

Test 65

Group: 4

Verdict: ACCEPTED

Test 66

Group: 4

Verdict: WRONG ANSWER

Test 67

Group: 4

Verdict: ACCEPTED

Test 68

Group: 4

Verdict: ACCEPTED

Test 69

Group: 4

Verdict: ACCEPTED

Test 70

Group: 4

Verdict: ACCEPTED

Test 71

Group: 4

Verdict: ACCEPTED

Test 72

Group: 4

Verdict: ACCEPTED

Test 73

Group: 4

Verdict: ACCEPTED

Test 74

Group: 4

Verdict: ACCEPTED

Test 75

Group: 4

Verdict: WRONG ANSWER

Test 76

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 77

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 78

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 79

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 80

Group: 4

Verdict: TIME LIMIT EXCEEDED