mickypinata

USACO-T029: Party Lamps

Dec 1st, 2021
414
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: lamps
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int L = 100;
  11.  
  12. vector<string> ans;
  13. vector<int> on, off;
  14. bitset<L> base, mask[4];
  15.  
  16. int main(){
  17.     freopen("lamps.in", "r", stdin);
  18.     freopen("lamps.out", "w", stdout);
  19.  
  20.     int n, nPress;
  21.     scanf("%d%d", &n, &nPress);
  22.     int x;
  23.     while(true){
  24.         scanf("%d", &x);
  25.         if(x == -1){
  26.             break;
  27.         }
  28.         on.push_back(x);
  29.     }
  30.     while(true){
  31.         scanf("%d", &x);
  32.         if(x == -1){
  33.             break;
  34.         }
  35.         off.push_back(x);
  36.     }
  37.     for(int i = 0; i < n; ++i){
  38.         mask[0][i] = 1;
  39.         base[i] = 1;
  40.     }
  41.     for(int i = 0; i < n; i += 2){
  42.         mask[1][i] = 1;
  43.     }
  44.     for(int i = 1; i < n; i += 2){
  45.         mask[2][i] = 1;
  46.     }
  47.     for(int i = 0; i < n; i += 3){
  48.         mask[3][i] = 1;
  49.     }
  50.     for(int b = 0; b < (1 << 4); ++b){
  51.         bitset<L> lamp = base;
  52.         int cnt = 0;
  53.         for(int i = 0; i < 4; ++i){
  54.             if((b & (1 << i)) != 0){
  55.                 lamp ^= mask[i];
  56.                 ++cnt;
  57.             }
  58.         }
  59.         if(cnt > nPress || (nPress - cnt) % 2 == 1){
  60.             continue;
  61.         }
  62.         bool ok = true;
  63.         for(int x : on){
  64.             if(lamp[x - 1] == 0){
  65.                 ok = false;
  66.                 break;
  67.             }
  68.         }
  69.         if(!ok){
  70.             continue;
  71.         }
  72.         for(int x : off){
  73.             if(lamp[x - 1] == 1){
  74.                 ok = false;
  75.                 break;
  76.             }
  77.         }
  78.         if(!ok){
  79.             continue;
  80.         }
  81.         ans.push_back(lamp.to_string());
  82.         ans.back() = ans.back().substr(L - n, n);
  83.         reverse(ans.back().begin(), ans.back().end());
  84.     }
  85.     sort(ans.begin(), ans.end());
  86.     for(string &str : ans){
  87.         cout << str << '\n';
  88.     }
  89.     if(ans.empty()){
  90.         cout << "IMPOSSIBLE\n";
  91.     }
  92.  
  93.     fclose(stdin);
  94.     fclose(stdout);
  95.     return 0;
  96. }
  97.  
RAW Paste Data