[ create a new paste ] login | about

Link: http://codepad.org/j4u5hp4U    [ raw code | fork ]

boleynsu - C++, pasted on Sep 10:
//Boleyn Su's Template for Codeforces
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <climits>
using namespace std;

#define lp for(;;)
#define rep(i,n) for (int i=0;i<(n);++i)
#define ft(i,a,b) for (int i=(a);i<=(b);++i)
#define fdt(i,a,b) for (int i=(a);i>=b;--i)
#define feach(e,s,t) for (t::iterator e=(s).begin();e!=(s).end();++e)
#define whl while
#define rtn return
#define fl(x,y) memset((x),char(y),sizeof(x))
#define clr(x) fl(x,0)
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define all(x) (x).begin(),(x).end()
#define srt(x) sort(all(x))
#define vec vector
#define pr pair
#define que queue
#define prq priority_queue
#define itr iterator
#define prt(x) cout<<#x<<"="<<(x)<<endl
#define asrtWA(s) do if(!(s))exit(0);whl(0)
#define asrtTLE(s) do if(!(s))whl(1);whl(0)
#define asrtRE(s) do if(!(s))*(int*)0=0;whl(0)

typedef long long int lli;
typedef double db;
typedef char* cstr;
typedef string str;
typedef vec<int> vi;
typedef vec<vi> vvi;
typedef vec<bool> vb;
typedef vec<vb> vvb;
typedef vec<str> vs;
typedef pr<int, int> pii;
typedef pr<str,int> psi;
typedef map<int,int> mii;
typedef map<str,int> msi;
typedef map<char,int> mci;
typedef set<int> si;
typedef set<str> ss;
typedef que<int> qi;
typedef prq<int> pqi;

const int oo=(~0u)>>1;
const lli ooll=(~0ull)>>1;
const db inf=1e8;
const db eps=1e-8;
const db pi=acos(-1.0);

template<typename type>inline bool cmax(type& a,const type& b){rtn a<b?a=b,true:false;}
template<typename type>inline bool cmin(type& a,const type& b){rtn a>b?a=b,true:false;}
template<typename type>inline type sqr(const type& x){rtn x*x;}
int dbcmp(const db& a,const db& b){rtn (a>b+eps)-(a<b-eps);}
int sgn(const db& x){rtn dbcmp(x,0);}
template<typename type>inline type lb(type x){rtn x&(-x);}
template<typename type>inline void bit_inc(vec<type>& st,int x,type inc){whl(x<sz(st))st[x]+=inc,x+=lb(x);}
template<typename type>inline type bit_sum(const vec<type>& st,int x){type s=0;while (x>0)s+=st[x],x-=lb(x);rtn s;}
inline void make_set(vi& set,int size){set.resize(size);rep(i,size)set[i]=i;}
inline int find_set(vi& set,int x){if(set[x]!=x)set[x]=find_set(set,set[x]);rtn set[x];}
inline bool union_set(vi& set,int a,int b){a=find_set(set,a),b=find_set(set,b);rtn a==b?false:set[a]=b,true;}
/*
int main()
{
}
*/
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-25
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN=12;
const int MAXSTATE=1000001;
int N,M,K;
char m[MAXN][MAXN];
int sc,SC;
pii s_[MAXSTATE],S_[MAXSTATE];
int f_[MAXSTATE],F_[MAXSTATE];
pii* s=s_;
pii* S=S_;
int* f=f_;
int* F=F_;
void qsort(int l,int r)
{
     int i=l,j=r;
     pii mid=S[(l+r)>>1];
     while (i<=j)
     {
           while (S[i]<mid) i++;
           while (S[j]>mid) j--;
           if (i<=j)
           {
              pii SS;
              int SF;
              SS=S[i],S[i]=S[j],S[j]=SS,SF=F[i],F[i]=F[j],F[j]=SF;
              i++,j--;
           }
     }
     if (l<j) qsort(l,j);
     if (i<r) qsort(i,r);
}

void run()
{
    cin>>N>>M>>K;
    int lasti=-1,lastj=-1;
    for (int i=0;i<N;i++)
        for (int j=0;j<M;j++)
        {
            cin>>m[i][j];
            if (m[i][j]!='*') lasti=i,lastj=j;
        }

    int answer=0;

    SC=0;
    S[SC]=mp(0,0);
    F[SC]=1;
    SC++;
    for (int i=0;i<N;i++)
    {
        for (int j=0;j<M;j++)
        {
            pii* ss;
            int* sf;
            ss=s,s=S,S=ss,sf=f,f=F,F=sf;
            sc=SC,SC=0;

            #define getp(state,p) (((state)>>((p)<<1))&3)
            #define replace(state,p,n) (((state)&(~(3<<((p)<<1))))|n<<((p)<<1))
            #define getl(state) getp(state,j)
            #define getu(state) getp(state,j+1)
            #define replacedr(state,d,r) replace(replace(state,j,d),j+1,r)
            #define getcl(state,p,ns)\
            do\
            {\
              ns=replacedr(state,0,0);\
              int get=2;\
              for (int i=p+2;i<=M;i++)\
              {\
                  if (getp(ns,i)==1) get++;\
                  else if (getp(ns,i)==2) get--;\
                  if (get==1)\
                  {\
                     ns=replace(ns,i,1);\
                     break;\
                  }\
              }\
            }\
            while (false)
            #define getcr(state,p,ns)\
            do\
            {\
              ns=replacedr(state,0,0);\
              int get=2;\
              for (int i=p-1;i>=0;i--)\
              {\
                  if (getp(ns,i)==2) get++;\
                  else if (getp(ns,i)==1) get--;\
                  if (get==1)\
                  {\
                     ns=replace(ns,i,2);\
                     break;\
                  }\
              }\
            }\
            while (false)
            if (m[i][j]=='*')
            {
               for (int si=0;si<sc;si++)
               {
                   int l=getl(s[si].x),u=getu(s[si].x);
                   if (!(l|u))
                   {
                      int ns;
                      ns=replacedr(s[si].x,0,0);
                      S[SC]=mp(ns,s[si].y);
                      F[SC]=f[si];
                      SC++;
                   }
               }
            }
            else
            {
                for (int si=0;si<sc;si++)
                {
                    int l=getl(s[si].x),u=getu(s[si].x);
                    if (l&&u)
                    {
                       bool odd=false;
                       rep(k,j) if (getp(s[si].x,k)) odd=!odd;

                       int ns;
                       if (l==2&&u==1)
                       {
                    	   ns=replacedr(s[si].x,0,0);
                           S[SC]=mp(ns,s[si].y);
                           F[SC]=f[si];
                           SC++;
                       }
                       else if (l==1&&u==1)
                       {
                    	   getcl(s[si].x,j,ns);
                           S[SC]=mp(ns,s[si].y);
                           F[SC]=f[si];
                           SC++;
                       }
                       else if (l==2&&u==2)
                       {
                    	   getcr(s[si].x,j,ns);
                           S[SC]=mp(ns,s[si].y);
                           F[SC]=f[si];
                           SC++;
                       }
                       else if (!odd)
                       {
                    	    ns=replacedr(s[si].x,0,0);
                            if ((!ns)&&i==lasti&&j==lastj&&s[si].y+1==K) (answer+=f[si])%=1000000007;
                            if (s[si].y+1<K)
                            {
                            	S[SC]=mp(ns,s[si].y+1);
                            	F[SC]=f[si];
                            	SC++;
                            }
                       }
                    }
                    else if (l||u)
                    {
                         int ns;
                         ns=replacedr(s[si].x,l,u);
                         S[SC]=mp(ns,s[si].y);
                         F[SC]=f[si];
                         SC++;
                         ns=replacedr(s[si].x,u,l);
                         S[SC]=mp(ns,s[si].y);
                         F[SC]=f[si];
                         SC++;
                    }
                    else
                    {
                         int ns;
                         ns=replacedr(s[si].x,1,2);
                         S[SC]=mp(ns,s[si].y);
                         F[SC]=f[si];
                         SC++;
                    }
                }
            }
            {
                qsort(0,SC-1);
                int RSC=0;
                int i=0;
                while (i<SC)
                {
                      int j=i+1;
                      while (j<SC&&S[i]==S[j]) (F[i]+=F[j])%=1000000007,j++;
                      S[RSC]=S[i];
                      F[RSC++]=F[i];
                      i=j;
                }
                SC=RSC;
            }
        }
        {
            int RSC=0;
            int i=0;
            while (i<SC)
            {
                  while (i<SC&&getp(S[i].x,M)) i++;
                  if (i<SC) S[RSC]=mp(S[i].x<<(1<<1),S[i].y),F[RSC++]=F[i++];
            }
            SC=RSC;
        }
    }
    cout<<answer<<endl;
}
int main()
{
	int T;
	for (scanf("%d\n",&T);T;T--) run();
}


Create a new paste based on this one


Comments: