0
Your rating: None

CodeChef submission 789013 (C++ 4.3.2)

CodeChef submission 789013 (C++ 4.3.2) plaintext list. Status: TLE, problem LUCKY3, contest JAN12. By jfogh (jfogh), 2012-01-11 14:38:19.
  1. #include <set>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <string>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <sstream>
  8. #include <algorithm>
  9. #include <map>
  10. #include <cmath>
  11. #include <iostream>
  12. #include <iomanip>
  13. #include <queue>
  14.  
  15. using namespace std;
  16.  
  17. typedef long long ll;
  18. typedef pair<int, int> pii;
  19.  
  20. #define PB push_back
  21. #define MP make_pair
  22. #define FOR(i,from,to) for (int i = from; i < to; i++)
  23. #define FORit(c,it) for (typeof(c.begin()) it=c.begin(); c.end()!=it;++it)
  24. #define SZ(v) v.size()
  25. #define LEN(s) s.length()
  26. #define X first
  27. #define Y second
  28. #define INIT(m,v) memset(m,v,sizeof(m))
  29. #define ALL(c) c.begin(), c.end()
  30. #define V vector
  31.  
  32. static ll dp[1<<19];
  33.  
  34. static int
  35. convert(int d) {
  36.     int res = 0, digits = 0;
  37.     for (int ii = 0; d; ++ii) {
  38.         int rem = d % 10;
  39.         d /= 10;
  40.         int digit;
  41.         if (4 > rem)
  42.             digit = 0;
  43.         else if (4 == rem)
  44.             digit = 1;
  45.         else if (7 > rem)
  46.             digit = 2;
  47.         else if (7 == rem)
  48.             digit = 3;
  49.         else
  50.             return -1;
  51.         res |= digit << ii * 2 + 3;
  52.         digits = ii + 1;
  53.     }
  54.     res |= digits - 1;
  55.  
  56.     return res;
  57. }
  58.  
  59. static inline int
  60. combine(int a, int b) {
  61.     int res=max((a & 0x7), (b & 0x7));
  62.     int digits=res + 1;
  63.     FOR(ii,0,digits)
  64.         res |= max((b >> ii * 2 + 3) & 0x3, (a >> ii * 2 + 3) & 0x3) << ii * 2 + 3;
  65.     return res;
  66. }
  67.  
  68. int
  69. main (int argc, char **argv) {
  70.     int T;
  71.     scanf("%d", &T);
  72.     FOR(tt,0,T) {
  73.         int n;
  74.         scanf("%d", &n);
  75.         FOR(kk,0,1<<19)
  76.             dp[kk]=0;
  77.         dp[0]=1;
  78.         FOR(ii,0,n) {
  79.             int d;
  80.             scanf("%d", &d);
  81.             d = convert(d);
  82.             if (-1 != d) {
  83.                 FOR(kk,0,1<<19) {
  84.                     int jj = (1<<19)-1-kk;
  85.                     int a = combine(d,jj);
  86.                     dp[a]+=dp[jj];
  87.                 }
  88.             }
  89.         }
  90.         ll res=0;
  91.         FOR(digits,0,8) {
  92.             FOR(ii,0,1<<digits+1) {
  93.                 int index = digits;
  94.                 FOR(jj,0,digits+1) {
  95.                     index |= ((ii>>jj) & 0x1) << jj * 2 + 4;
  96.                     index |= 1 << jj * 2 + 3;
  97.                 }
  98.                 res+=dp[index];
  99.             }
  100.         }
  101.         printf("%lld\n",res);
  102.     }
  103.   
  104.     return 0;
  105. }
  106.

Comments