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"); } }