Codeforces #469 Div2C

今日は心が乱れっぱなしでつらかった.寝不足と風邪がきいてるのかもしれないね.

Codeforces #469 Div2C Zebras

0と1からなる文字列が与えられる.この文字列をいくつかの0101...010という形の列に分割したい.分割できるならその例を一つ出力し,ないなら-1を出力せよ.

上手い方法がわからずEditorialを読んだ.列を0101...010という形の列(タイプA)と0101...01という形の列(タイプB)に分類する.前から見ていって1が出てきたらその時点で出来ているタイプAの列に追加する(その列はタイプBになる).ただしタイプAの列が1つも存在していなかったら-1.0が出てきたらタイプBの列に追加する(その列はタイプAになる).ただしタイプBの列が1つも存在していなかったらこれを一つのタイプAの列とする.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;

int main() {
    string S;
    cin >> S;
    vector<vector<int>> v;
    queue<int> a, b;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '0') {
            if (b.empty()) {
                v.push_back({ i });
                a.push(v.size() - 1);
            }
            else {
                v[b.front()].push_back({ i });
                a.push(b.front());
                b.pop();
            }
        }
        else {
            if (a.empty()) {
                cout << -1 << endl;
                return 0;
            }
            v[a.front()].push_back(i);
            b.push(a.front());
            a.pop();
        }
    }
    if (!b.empty()) {
        cout << -1 << endl;
        return 0;
    }
    cout << v.size() << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i].size();
        for (int j = 0; j < v[i].size(); j++) {
            cout << " " << v[i][j] + 1;
        }
        cout << endl;
    }
}