gistfile1.cpp

using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define iter(v) __typeof((v).end())
typedef long long ll;
typedef pair <int,int> PII;

int n, m;

bool checkBipartite(vector < vector <int> > mat) {
    int n = mat.size();
    queue <int> Q;
    vector <int> vis(n, -1);
    rep (i, n) {
        if (vis[i] == -1) {
            Q.push(i);
            vis[i] = 0;
            while (!Q.empty()) {
                int u = Q.front();
                Q.pop();
                rep (v, n) if (mat[u][v] != -1) {
                    if (vis[v] == -1) {
                        vis[v] = mat[u][v] ^ vis[u];
                        Q.push(v);
                    } else if (vis[v] != (mat[u][v] ^ vis[u])) {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}

vector <int> S, T;
vector < vector <int> > mat;

bool dfs(vector <int> &pos, vector < PII > &res, int i) {
    if (i == (int)pos.size()) {
        do {
            rep (i, S.size()) res.pb(mp(S[i], T[i]));
            rep (i, n / 2) {
                rep (j, n / 2) {
                    mat[i][j] = ((res[i].first < res[j].first  && res[j].first  < res[i].second) ^
                                (res[i].first < res[j].second && res[j].second < res[i].second)) ? 1 : -1;
                }
            }
            if (checkBipartite(mat))
                return 1;
            rep (i, S.size()) res.pop_back();
        } while (next_permutation(T.begin(), T.end()));
        sort(T.begin(), T.end());
    } else {
        if (S.size() > T.size()) {
            T.pb(pos[i]);
            if (dfs(pos, res, i + 1)) return 1;
            T.pop_back();
        }
        if (pos.size() + T.size() > S.size() + i) {
            S.pb(pos[i]);
            if (dfs(pos, res, i + 1)) return 1;
            S.pop_back();
        }
    }
    return 0;
}

bool gao1(vector <int> v) {
    mat = vector < vector <int> > (n / 2);
    rep (i, n / 2) mat[i] = vector <int> (n / 2);
    vector <int> pos;
    rep (i, n) if (v[i] == -1) pos.pb(i);
    S.clear();
    T.clear();
    vector <PII> res;
    rep (i, n)
        if (v[i] != -1)
            for (int j = i + 1; j < n; j++)
                if (v[i] == v[j])
                    res.pb(mp(i, j));
    return dfs(pos, res, 0);
}

bool gao2(vector <int> v) {
    vector <PII> _pair;
    rep (i, n)
        if (v[i] != -1)
            rep (j, n)
                if (i < j && v[i] == v[j])
                    _pair.pb(mp(i, j));
    vector <int> pos(n, -1);
    int cnt = 0;
    rep (i, n)
        if (v[i] == -1)
            pos[i] = cnt++;
    int rest = m;
    vector < vector <int> > mat(rest + 1);
    rep (i, rest + 1) mat[i] = vector <int> (rest + 1, -1);
    m = _pair.size();
    rep (mask, 1 << m) {
        bool flag = 1;
        rep (i, m)
            rep (j, m) {
                if ((!(mask & 1 << i) == !(mask & 1 << j)) &&
                    ((_pair[i].first < _pair[j].first  && _pair[j].first  < _pair[i].second) ^ (_pair[i].first < _pair[j].second && _pair[j].second < _pair[i].second))) {
                        flag = 0;
                }
            }
        if (!flag) continue;
        rep (i, rest + 1) rep (j, rest + 1) mat[i][j] = -1;
        rep (i, m) {
            int x = _pair[i].first - 1;
            int y = _pair[i].second;
            int w = 0;
            for (int j = x + 1; j < y; j++) w += v[j] == -1;
            w &= 1;
            while (~x && v[x] != -1) x--; x = ~x ? pos[x] + 1 : 0;
            while (~y && v[y] != -1) y--; y = ~y ? pos[y] + 1 : 0;
            if (mask & 1 << i) {
                if (mat[x][y] == 1) {flag = 0; break;}
                mat[x][y] = mat[y][x] = 0;
            } else {
                if (mat[x][y] == !w) {flag = 0; break;}
                mat[x][y] = mat[y][x] = w;
            }
        }
        mat[0][rest] = mat[rest][0] = 0;
        if (flag && checkBipartite(mat)) {
            cout << mask << endl;
            return 1;
        }
    }
    return 0;
}

class DisjointSemicircles {
public:
string getPossibility(vector <int> labels) {
    n = labels.size();
    cout << n << endl;
    m = 0;
    rep (i, n) m += labels[i] == -1;
    bool ans = m <= 12 ? gao1(labels) : gao2(labels);
    cout << ans << endl;
    return ans ? "POSSIBLE" : "IMPOSSIBLE";
}
}