SRM 625

500.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_L(i, hd, suc) for (int i=hd;i;i=suc[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)


typedef long long LL;


const int INF = 0x3f3f3f3f;

template<class T> inline T& checkMin(T &a,const T b){if (b<a) a=b;return a;}
//}


const int N = 50009 * 2, M = (N + 150009) * 2;

int D[N], hd[N], suc[M], to[M], cap[M];
int n, m, s, t;

inline void add_edge(int x, int y, int c){
    suc[m] = hd[x], to[m] = y, cap[m] = c, hd[x] = m++;
    suc[m] = hd[y], to[m] = x, cap[m] = 0, hd[y] = m++;
}

inline void add_edgee(int x, int y, int c){
    suc[m] = hd[x], to[m] = y, cap[m] = c, hd[x] = m++;
    suc[m] = hd[y], to[m] = x, cap[m] = c, hd[y] = m++;
}

#define v to[i]
#define c cap[i]
#define f cap[i^1]

bool bfs(){
    static int Q[N]; int cz = 0, op = 1;
    fill(D, D+n, 0), D[Q[0] = s] = 1; while (cz < op){
        int u = Q[cz++]; REP_G(i, u) if (!D[v] && c){
            D[Q[op++] = v] = D[u] + 1;
            if (v == t) return 1;
        }
    }
    return 0;
}

LL Dinitz(){

    to[0] = s;
    LL max_flow = 0;

    while (bfs()){

        static int sta[N], cur[N]; int top = 0;
        sta[0] = 0, cur[s] = hd[s]; while (top != -1){

            int u = to[sta[top]], i; if (u == t){
                int d = INF; REP_1(ii, top) i = sta[ii], checkMin(d, c);                  max_flow += d;
                DWN_1(ii, top, 1){i = sta[ii], f += d, c -= d; if (!c) top = ii - 1;}
                u = to[sta[top]];
            }

            for (i=cur[u];i;i=suc[i])
                if (D[u] + 1 == D[v] && c) break;

            if (!i) D[u] = 0, --top;
            else {
                cur[u] = suc[i], cur[v] = hd[v];
                sta[++top] = i;
            }
        }
    }

    if (max_flow >= INF) return -1;
    return max_flow;
}

#undef c
int r, c;

void init(){
    s = 0, m = 2; n = 2*r*c+1;
    fill(hd, hd+n+1, 0);
}

int V(int x, int y, int t = 0){
    return x*c+y+1 + t*r*c;
}

class BlockTheBlockPuzzle {
    public:
    int minimumHoles(vector <string> board) {
    	r = board.size (), c = board[0].size (); init();

    	REP_2(i, j, r, c) if (board[i][j] == 'b'){
    	    add_edge(s, V(i, j, 1), INF);
    	    add_edge(V(i, j), V(i, j, 1), INF);
    	}
    	else if (board[i][j] == '$'){
    	    t = V(i, j, 1); add_edge(V(i, j), V(i, j, 1), INF);
            board[i][j] = 'b';
    	}
    	else if (board[i][j] == '.'){
            add_edge(V(i, j), V(i, j, 1), 1);
    	}

        REP_2(i, j, r, c){
    	    if (j+3 < c){
                int cc = (board[i][j+1] == 'b') || (board[i][j+2] == 'b') ? INF : (board[i][j+1] == '.') + (board[i][j+2] == '.');
                add_edge(V(i, j, 1), V(i, j+3), cc);
                add_edge(V(i, j+3, 1), V(i, j), cc);
    	    }
    	    if (i+3 < r){
                int cc = (board[i+1][j] == 'b') || (board[i+2][j] == 'b') ? INF : (board[i+1][j] == '.') + (board[i+2][j] == '.');
                add_edge(V(i, j, 1), V(i+3, j), cc);
                add_edge(V(i+3, j, 1), V(i, j), cc);
    	    }
        }

    	return Dinitz();
    }

// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {"b..$",
 "....",
 "HHHH",
 "HHHH"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; verify_case(0, Arg1, minimumHoles(Arg0)); }
	void test_case_1() { string Arr0[] =

	{"............H..", "...............", "...............", "HHH$HHH.....H..", "HHHHHHH........", "HHHHHHHH.......", "......b..H.....", "...............", "...............", "...H..H..H.....", "...............", "...............", "...............", "...............", "..............."};


	 vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(1, Arg1, minimumHoles(Arg0)); }
	void test_case_2() { string Arr0[] = {".....H.............b.............", "..........b......................", ".H...............b...............", "..b..........H...................", "........H........................", "............b.....H..............", ".................................", "..H.........H........H...........", "..........H.....H................", "..bH........H.......b............", "..b................b.............", ".............H..................b", ".b......................bHb..H...", "Hb.............b.....b.......b...", ".................................", "....H..............H.............", "b...........b.b..................", ".H.H.H..H.b...b......b.b.b..bH...", "..............................H.b", ".......b..................H......", ".H.H........H....................", "...H................b............", ".................b...............", "............b....H...b...bb......", "..........b................b.H...", "..b............................H.", ".........H......................H", "...........b....b................", ".b...b................H.......H..", ".......H.$bbHb.........b.........", "H......H..bH..................b..", "........H.......H.H.....b.....H..", "...............b.....b...HH......"};
        vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; verify_case(2, Arg1, minimumHoles(Arg0)); }
	void test_case_3() { string Arr0[] = {"b..$...",
 "...H...",
 ".......",
 "b..b..b",
 "...H...",
 ".......",
 "b..b..b"}

; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; verify_case(3, Arg1, minimumHoles(Arg0)); }
	void test_case_4() { string Arr0[] = {"b..b..b",
 "..b..b.",
 ".......",
 "b..$bbb",
 ".b.....",
 "....b..",
 "b..b..b"}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(4, Arg1, minimumHoles(Arg0)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main() {
    BlockTheBlockPuzzle ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

900.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define Ts *this
#define rTs return Ts
typedef long long LL;
const int MOD = int(1e9) + 7;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}

// <<= '2. Number Theory .,//{
namespace NT{
#define gcd __gcd
inline LL lcm(LL a, LL b){return a*b/gcd(a,b);}

inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;}
inline int sum(int a, int b){a += b; if (a >= MOD) a -= MOD; return a;}
/* 模数两倍刚好超 int 时。
inline int sum(uint a, int b){a += b; a %= MOD;if (a < 0) a += MOD; return a;}
inline void INC(int &a, int b){a = sum(a, b);}
*/

inline void DEC(int &a, int b){a -= b; if (a < 0) a += MOD;}
inline int dff(int a, int b){a -= b; if (a < 0) a  += MOD; return a;}
inline void MUL(int &a, int b){a = (LL)a * b % MOD;}
inline int pdt(int a, int b){return (LL)a * b % MOD;}

inline int gcd(int m, int n, int &x, int &y){

    x = 1, y = 0; int xx = 0, yy = 1, q;

    while (1){
        q = m / n, m %= n;
        if (!m){x = xx, y = yy; return n;}
        DEC(x, pdt(q, xx)), DEC(y, pdt(q, yy));
        q = n / m, n %= m;
        if (!n) return m;
        DEC(xx, pdt(q, x)), DEC(yy, pdt(q, y));
    }
}

inline int sum(int a, int b, int c){return sum(a, sum(b, c));}
inline int sum(int a, int b, int c, int d){return sum(sum(a, b), sum(c, d));}
inline int pdt(int a, int b, int c){return pdt(a, pdt(b, c));}
inline int pdt(int a, int b, int c, int d){return pdt(pdt(a, b), pdt(c, d));}

inline int pow(int a, LL b){
    int c(1); while (b){
        if (b&1) MUL(c, a);
        MUL(a, a), b >>= 1;
    }
    return c;
}

template<class T> inline T pow(T a, LL b){
    T c(1); while (b){
        if (b&1) c *= a;
        a *= a, b >>= 1;
    }
    return c;
}

template<class T> inline T pow(T a, int b){
    return pow(a, (LL)b);
}

inline int _I(int b){
    int a = MOD, x1 = 0, x2 = 1, q; while (1){
        q = a / b, a %= b;
        if (!a) return x2;
        DEC(x1, pdt(q, x2));

        q = b / a, b %= a;
        if (!b) return x1;
        DEC(x2, pdt(q, x1));
    }
}

inline void DIV(int &a, int b){MUL(a, _I(b));}
inline int qtt(int a, int b){return pdt(a, _I(b));}

struct Int{
    int val;

    operator int() const{return val;}

    Int(int val = 0):val(val){
        val %= MOD; if (val < 0) val += MOD;
    }
    Int(LL _val){
        _val %= MOD; if (_val < 0) _val += MOD;
        val = _val;
    }
    Int& operator +=(const int& rhs){INC(val, rhs);rTs;}
    Int operator +(const int& rhs) const{return sum(val, rhs);}
    Int& operator -=(const int& rhs){DEC(val, rhs);rTs;}
    Int operator -(const int& rhs) const{return dff(val, rhs);}
    Int& operator *=(const int& rhs){MUL(val, rhs);rTs;}
    Int operator *(const int& rhs) const{return pdt(val, rhs);}
    Int& operator /=(const int& rhs){DIV(val, rhs);rTs;}
    Int operator /(const int& rhs) const{return qtt(val, rhs);}
    Int operator-()const{return MOD-*this;}
};

} using namespace NT;//}


const int N = 2009;
Int dp[2][N], Binom[N][N];

class Seatfriends {
public:
	int countseatnumb(int n, int m, int g) {

        REP(i, N){Binom[i][0] = 1; REP_1(j, i) Binom[i][j] = Binom[i-1][j-1] + Binom[i-1][j];}

#define u dp[q][j]
#define v dp[p]

        int p = 0, q = 1; RST(dp[p]); dp[p][1] = n;

        FOR(i, 1, m){
            swap(p, q); RST(dp[p]);
            REP_1(j, g) if (u){
                v[j] += u*j*2;
                v[j+1] += u*j;
                v[j-1] += u*j;
            }
        }

        if (n == m) return dp[p][0];
		Int res = 0; REP_1(i, g) res += dp[p][i] * Binom[n-m-1][i-1];
		return res;
	}
};


// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			int N                     = 3;
			int K                     = 2;
			int G                     = 1;
			int expected__            = 6;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 1: {
			int N                     = 4;
			int K                     = 2;
			int G                     = 1;
			int expected__            = 8;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 2: {
			int N                     = 2;
			int K                     = 2;
			int G                     = 1;
			int expected__            = 2;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 3: {
			int N                     = 5;
			int K                     = 4;
			int G                     = 2;
			int expected__            = 120;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 4: {
			int N                     = 42;
			int K                     = 23;
			int G                     = 7;
			int expected__            = 917668006;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 5: {
			int N                     = ;
			int K                     = ;
			int G                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 6: {
			int N                     = ;
			int K                     = ;
			int G                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 7: {
			int N                     = ;
			int K                     = ;
			int G                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = Seatfriends().countseatnumb(N, K, G);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE