superman

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 const int ON = 1, OFF = -1;
  6 
  7 int n, c;
  8 int FinalStatus[100];
  9 
 10 string ans[16];
 11 int ans_cnt;
 12 
 13 bool x[100];
 14 
 15 string x2string(bool x[], int n)
 16 {
 17     string ts;
 18     for (int i = 0; i < n; i++)
 19         ts += (x[i] + '0');
 20     return ts;
 21 }
 22 
 23 void addAns()
 24 {
 25     string ts = x2string(x, n);
 26 
 27     int i;
 28     for (i = 0; i < ans_cnt; i++)
 29         if (ans[i] == ts)
 30             break;
 31     if (i == ans_cnt)
 32         ans[ans_cnt++] = ts;
 33 }
 34 
 35 bool check(int k)
 36 {
 37     if (k == 0)
 38     {
 39         if (c % 2 != 0)
 40             return false;
 41     }
 42     else
 43         if(c % k)
 44             return false;
 45     for (int i = 0; i < n; i++)
 46     {
 47         if (FinalStatus[i] == OFF && x[i] == true)
 48             return false;
 49         if (FinalStatus[i] == ON && x[i] == false)
 50             return false;
 51     }
 52     return true;
 53 }
 54 
 55 void Button_4(int k)
 56 {
 57     if (check(k))
 58         addAns();
 59 
 60     for (int i = 0; i < n; i += 3) x[i] ^= 1;
 61     if (check(k + 1))
 62         addAns();
 63     for (int i = 0; i < n; i += 3) x[i] ^= 1;
 64 }
 65 
 66 void Button_3(int k)
 67 {
 68     Button_4(k);
 69 
 70     for (int i = 0; i < n; i += 2) x[i] ^= 1;
 71     Button_4(k + 1);
 72     for (int i = 0; i < n; i += 2) x[i] ^= 1;
 73 }
 74 
 75 void Button_2(int k)
 76 {
 77     Button_3(k);
 78 
 79     for (int i = 1; i < n; i += 2) x[i] ^= 1;
 80     Button_3(k + 1);
 81     for (int i = 1; i < n; i += 2) x[i] ^= 1;
 82 }
 83 
 84 void Button_1(int k)
 85 {
 86     Button_2(k);
 87 
 88     for (int i = 0; i < n; i++) x[i] ^= 1;
 89     Button_2(k + 1);
 90     for (int i = 0; i < n; i++) x[i] ^= 1;
 91 }
 92 
 93 int main()
 94 {
 95     freopen("lamps.in", "r", stdin);
 96     freopen("lamps.out", "w", stdout);
 97 
 98     cin >> n >> c;
 99 
100     int t;
101     while (true)
102     {
103         cin >> t;
104         if (t == -1) break;
105         FinalStatus[t - 1] = ON;
106     }
107     while (true)
108     {
109         cin >> t;
110         if (t == -1) break;
111         FinalStatus[t - 1] = OFF;
112     }
113 
114     if (c == 0)
115     {
116         int i;
117         for (i = 0; i < n; i++)
118             if (FinalStatus[i])
119                 break;
120         if (i == n)
121         {
122             for (int i = 0; i < n; i++)
123                 cout << 1;
124             cout << endl;
125         }
126         else
127             cout << "IMPOSSIBLE" << endl;
128         exit(0);
129     }
130 
131     //=========================
132     for (int i = 0; i < n; i++)
133         x[i] = true;
134 
135     Button_1(0);
136 
137     sort(ans, ans + ans_cnt);
138     for (int i = 0; i < ans_cnt; i++)
139         cout << ans[i] << endl;
140 
141     if (ans_cnt == 0)
142         cout << "IMPOSSIBLE" << endl;
143 
144     return 0;
145 }
146