// If M is the number of moves in input then this is O(M*N*N). #include "validate.h" #include #define MAX_MOVES 100000 using namespace std; typedef pair ii; void get_int(istream &sol, feedback_function feedback, int &n) { if(!(sol >> n)) feedback("Invalid or missing integer."); } void move(int x, ii d, ii inc, ii *locs, int n) { // moves xth block to (x + d.x, y + d.y). int i, z = locs[x].first + d.first, w = locs[x].second + d.second; for (i = 0; i < n; i++) if (z == locs[i].first && w == locs[i].second) break; if (i < n) move(i, d, inc, locs, n); locs[x] = ii(z, w); } int burn(ii *locs, ii inc, int n) { // burns whats on the burner. returns the number of blocks that are left. int i; for (i = 1; i < n; i++) if (locs[i] == inc) break; if (i == n) return n; swap(locs[i], locs[n - 1]); return n - 1; } int main(int argc, char **argv) { init_io(argc, argv); int i, n, x, y, m; get_int(judge_in, judge_error, n); n++; ii inc, locs[n], d; get_int(judge_in, judge_error, x); get_int(judge_in, judge_error, y); locs[0] = ii(x, y); get_int(judge_in, judge_error, x); get_int(judge_in, judge_error, y); inc = ii(x, y); for (i = 1; i < n; i++) { get_int(judge_in, judge_error, x); get_int(judge_in, judge_error, y); locs[i] = ii(x, y); } string inp; int move_cnt = 0; while (author_out >> inp) { move_cnt++; if (move_cnt == MAX_MOVES + 1) wrong_answer("Too many moves used."); for(int i = 0; i < inp.length(); i++){ inp[i] = tolower(inp[i]); } if (inp == "up") d = ii(0, 1); else if (inp == "down") d = ii(0, -1); else if (inp == "left") d = ii(-1, 0); else if (inp == "right") d = ii(1, 0); else wrong_answer("Input direction should be 'up', 'down', 'left', or 'right'."); move(0, d, inc, locs, n); n = burn(locs, inc, n); //printf(">> locs after move %d\n", move_cnt); //for (i = 0; i < n; i++) printf(">> %d %d\n", locs[i].first, locs[i].second); } //printf(">> n = %d\n", n); //for (i = 0; i < n; i++) printf(">> %d %d\n", locs[i].first, locs[i].second); if (n > 1) wrong_answer("Not all boxes are burnt."); accept(); }