JMK no matter what

문제 링크: 몇년째 풀진 못하고 고민만 하던 문젠데, 결국 탑코더 포럼에 올려서 질문하자, "백트래킹으로 되요" 라는 대답이... 헐... 난 왜 이렇게 할 생각을 못해봤을까. (당연히 시간 안에 안나올 줄 알았지. orz) 자료구조도 모호하게밖에 생각 안 나고.. 해서 그냥 냅뒀는데, 이렇게 간단하게 풀릴 줄이야. ㅠㅠ

막상 짜보니 랭크리스트 1등.... orz

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

int n, m;
vector<pair<int,int> > knowledge[26];
int tot;
int msb(int x)
{
    int ret = -1;
    while(x) { x /= 2; ret++; }
    return ret;
}

inline int sgn(int x) { if(x == 0) return 0; if(x > 0) return 1; return -1; }
inline int weigh(int x) { return sgn(x - (tot - x)); }

bool validate(int here, int* w, int* taken)
{

    int avail[30], an = 0;
    REP(i,n) if(!taken[i]) avail[an++] = i+1;
    int smallest[30], largest[30];
    smallest[0] = largest[0] = 0;
    FOR(i,1,an+1)
    {
        smallest[i] = smallest[i-1] + avail[i-1];
        largest[i] = largest[i-1] + avail[an-i];
    }
    FOR(mx,here,n)
    {
        REP(sce,knowledge[mx].sz)
        {
            const int mask = knowledge[mx][sce].first;
            const int sign = knowledge[mx][sce].second;
            int missing = __builtin_popcount(mask), thisSide = 0;
            REP(i,here+1) if(mask & (1<<i)) { missing--; thisSide += w[i]; }
            if(sign == 1)
            {
                if(weigh(thisSide + largest[missing]) != 1) return false;
            }
            else if(sign == 0)
            {
                if(weigh(thisSide + largest[missing]) < 0) return false;
                if(weigh(thisSide + smallest[missing]) > 0) return false;
            }
            else
            {
                if(weigh(thisSide + smallest[missing]) != -1) return false;
            }
        }
    }

    return true;
}
void go(int here, int* w, int* taken)
{
    if(here == n)
    {
        printf("Solution:");
        REP(i,n) printf(" %d", w[i]);
        printf("\n");
        throw 1;
    }

    REP(hw,n) if(!taken[hw])
    {
        taken[hw] = 1;
        w[here] = hw+1;
        if(validate(here, w, taken))
            go(here+1, w, taken);
        taken[hw] = 0;
    }
}

int main()
{
    while(scanf("%d %d", &n, &m) == 2)
    {
        REP(i,26) knowledge[i].clear();
        tot = n*(n+1)/2;

        REP(it,m)
        {
            int seen = 0;
            REP(i,n+1)
            {
                char buf[4];
                scanf("%s", buf);
                if(isalpha(buf[0]))
                    seen += (1 << (buf[0] - 'a'));
                else
                {
                    int others = (1<<n)-1-seen;
                    const static string sgn("<=>");
                    int actualSign = int(sgn.find(buf[0])) - 1;
                    if(seen) knowledge[msb(seen)].pb(make_pair(seen, actualSign));
                    if(others) knowledge[msb(others)].pb(make_pair(others, -actualSign));
                }
            }
        }
        REP(i,n)
        {
            sort(all(knowledge[i]));
            knowledge[i].erase( unique(all(knowledge[i])), knowledge[i].end() );
        }
        try
        {
            int w[26], taken[26];
            CLEAR(taken,0);
            go(0, w, taken);
            printf("No solution possible!\n");
        }
        catch(int)
        {
        }
    }
}