USACO 2.2 Party Lamps

Search space would be huge so reducing and consolidating states is required. Key observations:

1. Press same button twice yield no effect. Thus there is at most 2 ^ 4 = 16 switch state.
2. The switch state can be further reduced by enumerating all possible switch states and consolidate. Essentially, when the count of key press is larger than three, every switch state (among the maximum 16 states in total) could possibly appear.
3. The lamp state has a cycle of six.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <bitset>
#include <cstring>

using namespace std;

// Total # of lamps.
int N;
// Total # of button pressed.
int C;
int cur;

// All possible final state, with different key combinations.
//char lampStates[][7] =
vector<string> lampStates = {
     "111111",  // (),(1,2,3)
     "011011",  // (1,2,3,4),(4)
     "101010",  // (1,2),(3)
     "001110",  // (1,2,4),(3,4)
     "010101",  // (1,3),(2)
     "110001",  // (1,3,4),(2,4)
     "000000",  // (1),(2,3)
     "100100"   // (1,4),(2,3,4)
};

// Number of key presses required to reach a given lampState[index].
vector<vector<int>> keyStates = { {0,3},{1,4},{1,2},{2,3}, {1,2},{2,3},{1,2},{2,3} };
vector<bool> on(6, false);
vector<bool> off(6, false);

bool validate(int index) {
    for (int i = 0; i < 7; ++i) {
        if ((on[i] && lampStates[index][i] == '0') ||
            (off[i] && lampStates[index][i] == '1')) {
            return false;
        }
    }
    return true;
}

struct Result {
    string s;
    bool operator < (const Result& a) const {
        return strcmp(s.c_str(),  a.s.c_str()) < 0;
    }
} result[8];

void parseInput() {
    ifstream fin("lamps.in");
    fin >> N;
    fin >> C;
    int cur;
    fin >> cur;
    while (cur != -1) {
        on[(cur - 1) % 6] = true;
        fin >> cur;
    }

    fin >> cur;
    while (cur != - 1) {
        off[(cur - 1) % 6] = true;
        fin >> cur;
    }
}

int main() {
    parseInput();
    ofstream fout("lamps.out");
    int count = 0;
    if(C < 3) {
        for(int i = 0; i < 8; ++i)
            for(int j = 0; j <= 1; ++j) {
                if((keyStates[i][j] == C ||
                    keyStates[i][j] == C - 2) && validate(i))
                    result[count++].s = lampStates[i];
            }
    } else {
        for(int i = 0; i < 8; ++i)
            if(validate(i)) {
                result[count++].s = lampStates[i];
            }
    }

    if(count == 0) {
        fout << "IMPOSSIBLE" << endl;
    } else {
        sort(result, result + count);
        for(int i = 0; i < count; ++i) {
            int k = N;
            while(k >= 6) {
                fout << result[i].s;
                k -= 6;
            }
            int j = 0;
            while(j < k) {
                fout << result[i].s[j++];
            }
            fout << endl;
        }
    }
    return 0;
}