题解
和leetcode上面某题几乎一样。
注意排序就行。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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
using namespace std;
int n, m, cnt = 0, op[105] = {0};
int res[105], ans[10][105], tot = 0;
int ori[10], b[2][10], c[3], to[10];
void ssort(){
for(int i = 0; i < tot; ++i)
ori[i] = i;
for(int i = n - 1; i >= 0; --i){
c[0] = c[1] = 0;
for(int j = 0; j < tot; ++j){
int curbit = ans[ori[j]][i];
b[curbit][c[curbit]++] = ori[j];
}
c[1] += c[0];
for(int j = tot - 1; j >= 0; --j){
int curbit = ans[ori[j]][i];
to[--c[curbit]] = ori[j];
}
for(int j = 0; j < tot; ++j)
ori[j] = to[j];
}
}
bool judge(){
for(int i = 0; i < n; ++i)
if((op[i] == 1 && res[i] == 0) || (op[i] == -1 && res[i] == 1))
return false;
memcpy(ans[tot], res, sizeof(res)), tot++;
return true;
}
inline void reset(){
fill(res, res + n, 1);
}
void process(int x){
if(x == 1){
for(int i = 0; i < n; ++i)
res[i] ^= 1;
}else if(x == 2){
for(int i = 0; i < n; i += 2)
res[i] ^= 1;
}else if(x == 3){
for(int i = 1; i < n; i += 2)
res[i] ^= 1;
}else if(x == 4){
for(int i = 0; i < n; i += 3)
res[i] ^= 1;
}
}
int main(){
scanf("%d%d", &n, &m);
int t;
while(scanf("%d", &t), t > 0)
op[t - 1] = 1;
while(scanf("%d", &t), t > 0){
if(op[t - 1] == 1){
printf("IMPOSSIBLE\n");
return 0;
}
op[t - 1] = -1, cnt++;
}
bool flag = false;
if(m == 0){
if(cnt > 0) {
printf("IMPOSSIBLE\n");
return 0;
}
else{
for(int i = 0; i < n; ++i)
printf("1");
putchar('\n');
return 0;
}
}else if(m & 1){
reset();
if(m > 1) flag |= judge();//0
process(1), flag |= judge();//1
process(2), flag |= judge();//3
process(1), flag |= judge();//2
reset(), process(4), flag |= judge();//4
if(m > 1){
process(2), flag |= judge();//24
process(1), flag |= judge();//34
process(2), flag |= judge();//14
}
}else{
reset(), flag |= judge();//0
process(1), flag |= judge();//1
process(2), flag |= judge();//3
process(4), flag |= judge();//34
process(1), flag |= judge();//24
process(3), flag |= judge();//14
reset(), process(2), flag |= judge();//2
if(m > 2)
reset(), process(4), flag |= judge();//4
}
if(!flag){
printf("IMPOSSIBLE\n");
return 0;
}
ssort();
for(int i = 0; i < tot; ++i){
for(int j = 0; j < n; ++j)
printf("%d", ans[ori[i]][j]);
putchar('\n');
}
return 0;
}