CF949A Zebras 构造

是一道不错的构造题。
我们观察，一个 $1$ 的前后必须都有 $0$.
那么，我们开一个二维数组 $(vector)$，这样每遇到一个 $0$ 就将 $0$ 加入到当前的 $G[cnt]$ 中，并
++$cnt$， 这样满足的性质是 $k$ 到 $cnt$ 的所有状态都是已 $1$ 结尾的（或者为空），以此来判断是否有解。

Code:

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 200000 + 5;
char str[maxn];
vector<int> G[maxn];
inline void fail(){ printf("-1");  exit(0); }
int main()
{
    scanf("%s", str);
    int n = strlen(str), cnt = 0, k = 0;
    for(int i = 0;i < n; ++i)
    {
        if(str[i] == '0')  {
            G[cnt++].push_back(i + 1);
        }
        else
        {
            if(cnt == 0) fail(); 
            G[--cnt].push_back(i + 1);       
            k = max(k, cnt);
        }
    }
    if(k >= cnt) fail();
    printf("%d
", cnt);
    for(int i = 0;i < cnt; ++i)
    {
        printf("%d ", G[i].size());
        for(int j = 0;j < G[i].size(); ++j) printf("%d ",G[i][j]);
        printf("
");
    }
    return 0;
}