Skip to content

Instantly share code, notes, and snippets.

@lychees

lychees/NarrowPassage2.cpp

Created November 4, 2014 12:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lychees/568c58a47009028fb228 to your computer and use it in GitHub Desktop.
Save lychees/568c58a47009028fb228 to your computer and use it in GitHub Desktop.
Download ZIP
SRM 628
Raw
NarrowPassage2.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<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_N(i, n) for (i=0;i<n;++i)
#define ECH(it, A) for (__typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it)
typedef long long LL;
typedef double DB;
const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
template<class T> inline bool checkMin(T &a,const T b){return b < a ? a = b, 1 : 0;}
template<class T> inline bool checkMax(T &a,const T b){return a < b ? a = b, 1 : 0;}
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
// --------
const int dx[] = {-1, 0, 1, 0, 0, 0};
const int dy[] = {0, 1, 0, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 1, -1};
const int N = 10;
vector <string> XY, YZ, ZX;
int Ban[N][N][N]; bool allN;
int n, t;
bool inGrid(int x, int y, int z){
return x >= 0 && y >= 0 && x < n && y < n && z >= 0 && z < n;
}
void dfs(int i, int j, int k){
Ban[i][j][k] = t; REP(d, 6){
int x = i + dx[d], y = j + dy[d], z = k + dz[d];
if (inGrid(x, y, z) && !Ban[x][y][z]) dfs(x, y, z);
}
}
bool ckk(){
int k; REP(i, n) REP(j, n){
if (XY[i][j] == 'Y'){
REP_N(k, n) if (Ban[i][j][k] == t) break;
if (k == n) return 0;
}
if (YZ[i][j] == 'Y'){
REP_N(k, n) if (Ban[k][i][j] == t) break;
if (k == n) return 0;
}
if (ZX[i][j] == 'Y'){
REP_N(k, n) if (Ban[j][k][i] == t) break;
if (k == n) return 0;
}
}
return 1;
}
bool ck(){
REP(i, n) REP(j, n) REP(k, n) if (!Ban[i][j][k]){
++t, dfs(i, j, k);
if (ckk()) return 1;
}
return allN;
}
class ShadowSculpture {
public:
string possible(vector <string> XY, vector <string> YZ, vector <string> ZX) {
::XY = XY, :: YZ = YZ, ::ZX = ZX; n = XY.size(), t = 0; allN = 1;
RST(Ban); REP(i, n) REP(j, n){
if (XY[i][j] == 'N') REP(k, n) Ban[i][j][k] = -1; else allN = 0;
if (YZ[i][j] == 'N') REP(k, n) Ban[k][i][j] = -1; else allN = 0;
if (ZX[i][j] == 'N') REP(k, n) Ban[j][k][i] = -1; else allN = 0;
}
return ck() ? "Possible" : "Impossible";
}
};
// 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 string &expected, const string &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: {
string XY[] = {"YYYYY", "YYNYY", "YYYYY", "YYNYY", "YYYYY"};
string YZ[] = {"YYYYY", "YYNYY", "YYYYY", "YYNYY", "YYYYY"};
string ZX[] = {"YYYYY", "YYNYY", "YYYYY", "YYNYY", "YYYYY"};
string expected__ = "Possible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string XY[] = {"YN","NY"};
string YZ[] = {"YN","NY"};
string ZX[] = {"YN","NY"};
string expected__ = "Impossible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string XY[] = {"YYY","YNY","YYY"};
string YZ[] = {"YYY","YNY","YYY"};
string ZX[] = {"YYY","YNY","YYY"};
string expected__ = "Possible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string XY[] = {"YYY","YNY","YYY"};
string YZ[] = {"NYY","YNY","YYY"};
string ZX[] = {"YYY","YNY","YYN"};
string expected__ = "Impossible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string XY[] = {"N"};
string YZ[] = {"N"};
string ZX[] = {"N"};
string expected__ = "Possible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
string XY[] = ;
string YZ[] = ;
string ZX[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
string XY[] = ;
string YZ[] = ;
string ZX[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 7: {
string XY[] = ;
string YZ[] = ;
string ZX[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
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
Raw
ShadowSculpture.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<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_N(i, n) for (i=0;i<n;++i)
#define ECH(it, A) for (__typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it)
typedef long long LL;
typedef double DB;
const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
template<class T> inline bool checkMin(T &a,const T b){return b < a ? a = b, 1 : 0;}
template<class T> inline bool checkMax(T &a,const T b){return a < b ? a = b, 1 : 0;}
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
// --------
const int dx[] = {-1, 0, 1, 0, 0, 0};
const int dy[] = {0, 1, 0, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 1, -1};
const int N = 10;
vector <string> XY, YZ, ZX;
int Ban[N][N][N]; bool allN;
int n, t;
bool inGrid(int x, int y, int z){
return x >= 0 && y >= 0 && x < n && y < n && z >= 0 && z < n;
}
void dfs(int i, int j, int k){
Ban[i][j][k] = t; REP(d, 6){
int x = i + dx[d], y = j + dy[d], z = k + dz[d];
if (inGrid(x, y, z) && !Ban[x][y][z]) dfs(x, y, z);
}
}
bool ckk(){
int k; REP(i, n) REP(j, n){
if (XY[i][j] == 'Y'){
REP_N(k, n) if (Ban[i][j][k] == t) break;
if (k == n) return 0;
}
if (YZ[i][j] == 'Y'){
REP_N(k, n) if (Ban[k][i][j] == t) break;
if (k == n) return 0;
}
if (ZX[i][j] == 'Y'){
REP_N(k, n) if (Ban[j][k][i] == t) break;
if (k == n) return 0;
}
}
return 1;
}
bool ck(){
REP(i, n) REP(j, n) REP(k, n) if (!Ban[i][j][k]){
++t, dfs(i, j, k);
if (ckk()) return 1;
}
return allN;
}
class ShadowSculpture {
public:
string possible(vector <string> XY, vector <string> YZ, vector <string> ZX) {
::XY = XY, :: YZ = YZ, ::ZX = ZX; n = XY.size(), t = 0; allN = 1;
RST(Ban); REP(i, n) REP(j, n){
if (XY[i][j] == 'N') REP(k, n) Ban[i][j][k] = -1; else allN = 0;
if (YZ[i][j] == 'N') REP(k, n) Ban[k][i][j] = -1; else allN = 0;
if (ZX[i][j] == 'N') REP(k, n) Ban[j][k][i] = -1; else allN = 0;
}
return ck() ? "Possible" : "Impossible";
}
};
// 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 string &expected, const string &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: {
string XY[] = {"YYYYY", "YYNYY", "YYYYY", "YYNYY", "YYYYY"};
string YZ[] = {"YYYYY", "YYNYY", "YYYYY", "YYNYY", "YYYYY"};
string ZX[] = {"YYYYY", "YYNYY", "YYYYY", "YYNYY", "YYYYY"};
string expected__ = "Possible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string XY[] = {"YN","NY"};
string YZ[] = {"YN","NY"};
string ZX[] = {"YN","NY"};
string expected__ = "Impossible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string XY[] = {"YYY","YNY","YYY"};
string YZ[] = {"YYY","YNY","YYY"};
string ZX[] = {"YYY","YNY","YYY"};
string expected__ = "Possible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string XY[] = {"YYY","YNY","YYY"};
string YZ[] = {"NYY","YNY","YYY"};
string ZX[] = {"YYY","YNY","YYN"};
string expected__ = "Impossible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string XY[] = {"N"};
string YZ[] = {"N"};
string ZX[] = {"N"};
string expected__ = "Possible";
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
string XY[] = ;
string YZ[] = ;
string ZX[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
string XY[] = ;
string YZ[] = ;
string ZX[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 7: {
string XY[] = ;
string YZ[] = ;
string ZX[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = ShadowSculpture().possible(vector <string>(XY, XY + (sizeof XY / sizeof XY[0])), vector <string>(YZ, YZ + (sizeof YZ / sizeof YZ[0])), vector <string>(ZX, ZX + (sizeof ZX / sizeof ZX[0])));
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