Codeforces-949A. Zebras

一个01串，问是否能分成k个子序列，使每个串始于0，终于0，且01交替出现。若可以，输出任意一种方案，否则输出-1

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 int len;
 9 const int maxn = 2e5 + 10;
10 char s[maxn];
11 int nxt[maxn];
12 int bgn[maxn];
13 
14 int main() {
15     int ans= 0;
16     scanf("%s", s + 1);
17     len = strlen(s + 1);
18     queue<int> q0, q1;
19     for (int i = 1; i <= len; i++) {
20         if (s[i] == '0') {
21             if (q1.empty()) {
22                 q0.push(i);
23                 bgn[ans++] = i;
24             } else {
25                 int tmp = q1.front(); 
26                 q1.pop();
27                 q0.push(i);
28                 nxt[tmp] = i;
29             }
30         } else {
31             if (q0.empty()) {
32                 ans = -1;
33                 break;
34             } else {
35                 int tmp = q0.front();
36                 q0.pop();
37                 q1.push(i);
38                 nxt[tmp] = i;
39             }
40         }
41     }
42     if (!q1.empty()) {
43         puts("-1");
44     } else {
45         printf("%d
", ans);
46         for (int i = 0; i < ans; i++) {
47             int t = bgn[i];
48             int cnt = 1;
49             while (nxt[t]) {t = nxt[t]; cnt++;}
50             t = bgn[i];
51             printf("%d %d", cnt, t);
52             while (nxt[t]) {
53                 printf(" %d", nxt[t]);
54                 t = nxt[t];
55             }
56             puts("");
57 
58         }
59     }
60     return 0;
61 }