fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <string>
  5. #include <algorithm>
  6. #include <set>
  7. #include <random>
  8. #include <string>
  9. #include <sstream>
  10. #define fi first
  11. #define se second
  12. #define rep(i,n) for(int i = 0; i < (n); ++i)
  13. #define rrep(i,n) for(int i = 1; i <= (n); ++i)
  14. #define drep(i,n) for(int i = (n)-1; i >= 0; --i)
  15. #define srep(i,s,t) for (int i = s; i < t; ++i)
  16. #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
  17. #define rng(a) a.begin(),a.end()
  18. #define maxs(x,y) x = max(x,y)
  19. #define mins(x,y) x = min(x,y)
  20. #define pb push_back
  21. #define sz(x) (int)(x).size()
  22. #define pcnt __builtin_popcountll
  23. #define uni(x) x.erase(unique(rng(x)),x.end())
  24. #define snuke srand((unsigned)clock()+(unsigned)time(NULL));
  25. #define df(x) int x = in()
  26. #define dame { puts("-1"); return 0;}
  27. #define show(x) cout<<#x<<" = "<<x<<endl;
  28. #define PQ(T) priority_queue<T,vector<T>,greater<T> >
  29. #define bn(x) ((1<<x)-1)
  30. #define newline puts("")
  31. #define v(T) vector<T>
  32. #define vv(T) vector<vector<T>>
  33. using namespace std;
  34. typedef long long int ll;
  35. typedef unsigned uint;
  36. typedef unsigned long long ull;
  37. typedef pair<int,int> P;
  38. typedef vector<int> vi;
  39. typedef vector<vi> vvi;
  40. typedef vector<ll> vl;
  41. typedef vector<P> vp;
  42. inline int in() { int x; scanf("%d",&x); return x;}
  43. inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
  44. template<typename T>istream& operator>>(istream&i,vector<T>&v)
  45. {rep(j,sz(v))i>>v[j];return i;}
  46. template<typename T>string join(const vector<T>&v)
  47. {stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
  48. template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
  49. {if(sz(v))o<<join(v);return o;}
  50. template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
  51. {return i>>v.fi>>v.se;}
  52. template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
  53. {return o<<v.fi<<","<<v.se;}
  54. const int MX = 200005, INF = 1001001001;
  55. const ll LINF = 1e18;
  56. typedef v(string) vs;
  57. #include <random>
  58. random_device _rd;
  59. mt19937 _mt(_rd()+time(0));
  60. inline int rnd(int n) { return _mt()%n;}
  61. inline int rnd(int l, int r) { return _mt()%(r-l+1)+l;}
  62.  
  63. const int di[] = {-1,-1,0,1,1,0,0}, dj[] = {0,-1,-1,0,1,1,0}; // <\^>\v.
  64.  
  65. const int SZ = 11;
  66. const int cell_num[] = {0,5,6,7,8,9,8,7,6,5,0};
  67. const int cell_begin[] = {0,1,1,1,1,1,2,3,4,5,0};
  68. const int S = 6, N = 6;
  69.  
  70. int h, w;
  71. vvi board;
  72. vp pos;
  73. int n;
  74. ll full;
  75. vl to;
  76.  
  77. void init() {
  78.   h = w = SZ;
  79.   board = vvi(h,vi(w,-1));
  80.   rep(i,h) {
  81.     rep(j,cell_num[i]) {
  82.       pos.pb(P(i,cell_begin[i]+j));
  83.     }
  84.   }
  85.   n = sz(pos);
  86.   rep(i,n) board[pos[i].fi][pos[i].se] = i;
  87.   to = vl(n);
  88.   rep(i,n) {
  89.     rep(v,7) {
  90.       int ni = pos[i].fi+di[v], nj = pos[i].se+dj[v];
  91.       if (board[ni][nj] == -1) continue;
  92.       to[i] |= 1ll<<board[ni][nj];
  93.     }
  94.   }
  95.   full = (1ll<<n)-1;
  96. }
  97.  
  98. void print(ll s, ll b=0) {
  99.   rep(i,n) if (s>>i&1) b |= to[i];
  100.   vs t(h-2,string((w-2)*2-1,' '));
  101.   rep(i,n) {
  102.     char c = '.';
  103.     if (b>>i&1) c = 'x';
  104.     if (s>>i&1) c = 'o';
  105.     t[pos[i].fi-1][pos[i].se*2-2+(5-pos[i].fi)] = c;
  106.   }
  107.   rep(i,sz(t)) cout<<t[i]<<endl;
  108.   newline;
  109. }
  110.  
  111. ll ans;
  112. #define PRUNE if (n-pcnt(b)+pcnt(s) < S*N) return;
  113. void dfs(ll s, ll ns, ll b) {
  114.   if (pcnt(s) == S*N) {
  115.     ++ans;
  116.     print(s, full^s);
  117.     return;
  118.   }
  119.   PRUNE;
  120.   if (pcnt(ns) == S) {
  121.     while (ns) {
  122.       ll x = ns&-ns;
  123.       ns ^= x;
  124.       b |= to[pcnt(x-1)];
  125.     }
  126.   }
  127.   PRUNE;
  128.   if (ns) {
  129.     ll tmp = ns;
  130.     ll nb = 0;
  131.     while (tmp) {
  132.       ll x = tmp&-tmp;
  133.       tmp ^= x;
  134.       nb |= to[pcnt(x-1)];
  135.     }
  136.     nb &= ~b;
  137.     while (nb) {
  138.       ll x = nb&-nb;
  139.       nb ^= x;
  140.       b |= x;
  141.       dfs(s|x, ns|x, b);
  142.     }
  143.   } else {
  144.     ll tmp = full^b;
  145.     while (tmp) {
  146.       ll x = tmp&-tmp;
  147.       tmp ^= x;
  148.       b |= x;
  149.       dfs(s|x, x, b);
  150.       PRUNE;
  151.     }
  152.   }
  153. }
  154.  
  155. ll input() {
  156.   vl ci(256,-1);
  157.   ci['.'] = 0; ci['x'] = 1;
  158.   ll res = 0;
  159.   rep(i,n) {
  160.     char c;
  161.     scanf(" %c",&c);
  162.     res |= ci[c]<<i;
  163.   }
  164.   return res;
  165. }
  166.  
  167.  
  168. int main() {
  169.   init();
  170.   ll b = input();
  171.   dfs(0,0,b);
  172.   cout<<ans<<endl;
  173.   return 0;
  174. }
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
Success #stdin #stdout 0.55s 5548KB
comments (?)
stdin
copy 
. . . . . 
   . . . . .    
   x x . . . .   
  . . . . . . .  
 . x . . . . . . 
x x . x . . . . .
 . . . . . . . . 
  . . . . . . .  
   . x . x . .   
    . . . . .
stdout
copy 
    o o x o o    
   o o o x o x   
  x x o x o x o  
 o o x x o o x o 
o o o o x x x o x
 x x x x o x o o 
  o o o x o x o  
   o o x o o x   
    x o x o o    

1
https://ideone.com/9uabQU
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!