题目大意就是给出灯的个数，和对灯的操作规则，和经过C步操作后亮着的部分灯和熄灭的部分灯，求灯最后的可能情况，如果没有输出`IMPOSSIBLE’
- 按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。
- 按钮2：当按下此按钮，将改变所有奇数号的灯。
- 按钮3：当按下此按钮，将改变所有偶数号的灯。
- 按钮4：当按下此按钮，将改变所有序号是3*K+1 (K >= 0)的灯。例如：1,4,7…
注意到当每对一个操作实施两次和没实施效果一样，故可将大于4的C减小到3或4；
然后从开始进行搜索没一盏灯进行一步操作后的可能情况，知道进行了C步操作，如果满足题目条件则保存数据再搜索下一组情况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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
using namespace std;
int op[105];
int cl[105];
int n;
int c;
int clk=0;
int opk=0;
bool found=false;
struct prog{
int a1;
int a2;
int a3;
int a4;
bool str[105];
};
prog ans[10000];
int p=0;
bool istrue(bool* lap)
{
int i;
for(i=0;i<opk;i++)
{
if(lap[op[i]-1]!=true)
return false;
}
for(i=0;i<clk;i++)
{
if(lap[cl[i]-1]!=false)
return false;
}
return true;
}
void change(bool* lap,int k)
{
int st=0;
int ad=k;
if(k==4)
{
st=1;
ad=2;
}
int i;
for(i=st;i<n;i+=ad)
lap[i]=!lap[i];
}
void DFS(bool *lap,int k)
{
int i,j;
if(k/2==c/2)
{
if(istrue(lap))
{
for(j=0;j<n;j++)
ans[p].str[j]=lap[j];
for(j=0;j<25;j++)
{
ans[p].a1=ans[p].a1*2+ans[p].str[j];
}
for(j=25;j<50;j++)
{
ans[p].a2=ans[p].a2*2+ans[p].str[j];
}
for(j=50;j<75;j++)
{
ans[p].a3=ans[p].a3*2+ans[p].str[j];
}
for(j=75;j<100;j++)
{
ans[p].a4=ans[p].a4*2+ans[p].str[j];
}
p++;
found=true;
}
return ;
}
for(i=1;i<=4;i++)
{
bool tmp[105];
for(j=0;j<n;j++)
{
tmp[j]=lap[j];
}
change(tmp,i);
DFS(tmp,k+1);
}
}
int cmp(const void *a,const void *b)
{
if((*(prog *)a).a1!=(*(prog *)b).a1)
return (*(prog *)a).a1-(*(prog *)b).a1;
if((*(prog *)a).a2!=(*(prog *)b).a2)
return (*(prog *)a).a2-(*(prog *)b).a2;
if((*(prog *)a).a3!=(*(prog *)b).a3)
return (*(prog *)a).a3-(*(prog *)b).a3;
return (*(prog *)a).a4-(*(prog *)b).a4;
}
int main()
{
memset(ans,0,sizeof(ans));
bool lap[105];
freopen("lamps.in","r",stdin);
freopen("lamps.out","w",stdout);
memset(lap,true,sizeof(lap));
cin>>n;
cin>>c;
while(1)
{
cin>>op[opk];
if(op[opk]==-1)
break;
opk++;
}
while(1)
{
cin>>cl[clk];
if(cl[clk]==-1)
break;
clk++;
}
if(c>4)
{
if(c%2)
c=3;
else
c=4;
}
DFS(lap,0);
int i,j;
if(!found)
cout<<"IMPOSSIBLE"<<endl;
else
{
qsort(ans,p,sizeof(ans[0]),cmp);
for(i=0;i<p;i++)
{
if(i&&ans[i].a1==ans[i-1].a1&&ans[i].a2==ans[i-1].a2&&ans[i].a3==ans[i-1].a3&&ans[i].a4==ans[i-1].a4)
continue;
for(j=0;j<n;j++)
{
cout<<ans[i].str[j];
}
cout<<endl;
}
}
return 0;
}