yuji314159 · July 7, 2015 11:01 · Jul 7, 2015
diff --git a/e.cpp b/e.cpp
@@ -0,0 +1,85 @@
+#include <cstdio>
+#include <string>
+#include <algorithm>
+
+using namespace std;
+
+bool block(int k1, int locked1, int k2, int locked2)
+{
+    return (locked1 & (1 << k2));
+}
+
+bool dead_lock(int k1, int locked1, int k2, int locked2)
+{
+    return (locked1 & (1 << k2)) && (locked2 & (1 << k1));
+}
+
+bool p[10][1 << 10];
+
+bool safe(const string &s)
+{
+    fill(&p[0][0], &p[10][0], false);
+
+    int locked = 0;
+    for (int i = 0; i < s.size(); ++i) {
+        if (s[i] == 'u') {
+            locked = 0;
+        } else {
+            const int k = s[i] - '0';
+            if (locked & (1 << k))
+                return false;
+            p[k][locked] = true;
+            locked |= 1 << k;
+        }
+    }
+
+    /*for (int a = 0; a < 10; ++a)*/ {
+        int locked = 0;
+        for (int i = 0; i < s.size(); ++i) {
+            if (s[i] == 'u') {
+                locked = 0;
+            } else {
+                const int k = s[i] - '0';
+                for (int t = 0; t < 10; ++t) {
+                    for (int l = 0; l < (1 << 10); ++l) {
+                        if (!p[t][l])
+                            continue;
+                        if (locked & l)
+                            continue;
+                        if (dead_lock(k, locked, t, l))
+                            return false;
+                        if (block(k, locked, t, l)) {
+                            p[k][locked | l] = true;
+                        } else if (block(t, l, k, locked)) {
+                            p[t][locked | l] = true;
+                        }
+                    }
+                }
+                locked |= 1 << k;
+            }
+        }
+    }
+
+    return true;
+}
+
+int main()
+{
+    for (;;) {
+        int n;
+        scanf("%d", &n);
+        if (n == 0)
+            break;
+        //fprintf(stderr, "%d\n", n);
+
+        char s[10001];
+        scanf("%s", s);
+
+        if (safe(string(s)))
+            puts("SAFE");
+        else
+            puts("UNSAFE");
+    }
+
+    return 0;
+}