Advertisement
Guest User

e.cpp

a guest
Jun 26th, 2015
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. //#define __GLIBCXX_DEBUG
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define REP(i, n) for(int i = 0; i < (int)(n); ++i)
  6. #define pb push_back
  7. #define ALL(a) (a.begin()), (a.end())
  8. #define mp make_pair
  9. #define F first
  10. #define S second
  11. #define SZ(a) ((int)(a.size()))
  12.  
  13. typedef long long ll;
  14. typedef pair<int, int> PI;
  15.  
  16. int main(int argc, char *argv[])
  17. {
  18.  
  19.   int n;
  20.   while (cin >> n && n){
  21.     string S;
  22.     cin >> S;
  23.     int dp[11][11][1 << 10];
  24.     memset(dp, 0, sizeof(dp));
  25.     bool unsafe = false;
  26.    
  27.     REP(i, n) if (i == 0 || S[i - 1] == 'u'){
  28.       int s = i;
  29.       if (S[s] == 'u' || S[s + 1] == 'u') continue;
  30.       // cout << s << endl;
  31.      
  32.       int mask = 0;
  33.       while (S[s] != 'u'){
  34.         if (mask & (1 << (S[s] - '0'))){
  35.           unsafe = true;
  36.         } else {
  37.           // cout << s << " " << S[s] << " " << mask << endl;
  38.           dp[0][S[s] - '0'][mask] = 1;
  39.         }
  40.         mask |= 1 << (S[s] - '0');
  41.         s++;
  42.       }
  43.     }
  44.  
  45.  
  46.     REP(t, 10) if (t > 0){
  47.       REP(d, 10) REP(mask, 1 << 10) if (dp[t - 1][d][mask]){
  48.         REP(i, n - 1) if (S[i] == 'u' && S[i + 1] != 'u'){
  49.           int n_mask = 0;
  50.           int p = i + 1;
  51.           while (S[p] != 'u' && (mask & (1 << (S[p] - '0'))) == 0){
  52.             n_mask |= 1 << (S[p] - '0');
  53.             p++;
  54.           }
  55.           // cout << t << " " << d << " " << mask << " " << p << " " << n_mask << endl;
  56.          
  57.           if (S[p] != 'u'){
  58.             if ((n_mask  | mask) & (1 << d)) unsafe = true;
  59.             dp[t][d][mask | n_mask] = 1;
  60.           }
  61.         }
  62.       }
  63.     }
  64.     if (unsafe) {
  65.       cout << "UNSAFE" << endl;
  66.     } else {
  67.       cout << "SAFE" << endl;
  68.     }
  69.   }
  70.   return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement