// Problem : Hammering (NAIPC 2019) // Author : Darcy Best // Expected Result : AC // Complexity : O(rc) // ========= INITAL CHECK: // - If the start and final configs are the same, then answer is YES. // ========= MARK HITTABLE ROWS: // - In the fianl config, if 2 or more are down in any given row/col, // then that row is not hittable. // - If there is a peg that needs X --> X and *one of* its row/col is not hittable, // then the other one isn't hittable either. // - If there is a peg that needs O --> X, then *both* row and column // must be hittable. // - If there is a peg that needs X --> O, then *at least one* of its row // or column must be hittable. // ========= FINAL CHECK: // - In the region of hittable cells, if there are no X's in the final configuration, // then answer is NO. // - In the region of hittable cells, if there are no O's in the inital configuration, // then answer is NO. // // ========= DO THE HITTING: // - The answer at this point is YES. Here is how: // (1) Hit every cell in the hittable region so that there is only one peg up (one that // needs to be an X). // (2) Hit each other X in the final configuration. #include #include #include #include using namespace std; bool chk(){ int r,c; cin >> r >> c; vector A(r), B(r); for(auto& x : A) cin >> x; for(auto& x : B) cin >> x; if(A == B) return true; vector hittable_row(r,true), hittable_col(c,true); for(int i=0;i 1) hittable_row[i] = false; } for(int j=0;j 1) hittable_col[j] = false; } for(int i=0;i 0 && BX_cnt > 0; } int main(){ cout << chk() << endl; }