JAPLJ Contest C: Cosmos

問題
http://judge.imoz.jp/page.php?page=view_problem&pid=44&cid=8
回答(1回目) - Time Limit Exceeded - 50% Scored
予想通りTLE
回答(2回目) - Accepted

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int n;
char buf[1000100];
int ret[1000100];
int hoge[1000100];

bool f(int a, int b) {
    if (a < b) {
        for (int i = a+1; i <= b; i += max(1,abs(hoge[a+1] - hoge[i]))) {
            if (buf[a] != buf[i] && hoge[a+1] == hoge[i]) {
                if ((i == a+1 || f(a+1, i-1)) && (i == b || f(i+1, b))) {
                    ret[a] = i;
                    ret[i] = a;
                    return true;
                }
            }
        }
        return false;
    } else {
        for (int i = 0; i <= b; i += max(1,abs(hoge[a+1] - hoge[i]))) {
            if (buf[a] != buf[i] && hoge[a+1] == hoge[i]) {
                if (i == 0) {
                    if ((a == n-1 || f(a+1, n-1)) && (i == b || f(i+1, b))) {
                        ret[a] = i;
                        ret[i] = a;
                        return true;
                    }
                } else {
                    if ((f(a+1, i-1)) && (i == b || f(i+1, b))) {
                        ret[a] = i;
                        ret[i] = a;
                        return true;
                    }
                }
            }
        }
        for (int i = a+1; i < n; i += max(1,abs(hoge[a+1] - hoge[i]))) {
            if (buf[a] != buf[i] && hoge[a+1] == hoge[i]) {
                if (i == n-1) {
                    if ((i == a+1 || f(a+1, i-1)) && (b == 0 || f(0, b))) {
                        ret[a] = i;
                        ret[i] = a;
                        return true;
                    }
                } else {
                    if ((i == a+1 || f(a+1, i-1)) && (f(i+1, b))) {
                        ret[a] = i;
                        ret[i] = a;
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

int main() {
    fgets(buf, sizeof(buf), stdin);
    n = 2*atoi(buf);
    fgets(buf, sizeof(buf), stdin);
    hoge[0] = 0;
    for (int i = 0; i < n; ++ i) {
        hoge[i+1] = hoge[i] + ((buf[i] == 'W') ? +1 : -1);
    }
    if (f(0, n-1)) {
        for (int i = 0; i < n; ++ i) {
            printf("%d\n", ret[i]+1);
        }
    } else {
        puts("-1");
    }
}