Skip to content

Instantly share code, notes, and snippets.

@lychees
Last active Aug 29, 2015
Embed
What would you like to do?
SRM 625
#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
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment