#include #include #include #include #include #include #include #include #include using i64 = long long; struct Timer { std::chrono::high_resolution_clock::time_point st; Timer() { st = now(); } std::chrono::high_resolution_clock::time_point now() { return std::chrono::high_resolution_clock::now(); } std::chrono::milliseconds::rep span() { auto ed = now(); return std::chrono::duration_cast(ed - st).count(); } }; struct Xor64 { using state_type = std::uint64_t; using result_type = std::uint64_t; state_type a; static constexpr result_type min() { return std::numeric_limits::min(); } static constexpr result_type max() { return std::numeric_limits::max(); } constexpr Xor64(state_type seed = 88675123): a(seed) {} constexpr void seed(state_type seed = 88675123) { a = seed; } constexpr result_type operator()() { a ^= a << 7; a ^= a >> 9; return a; } void discard(unsigned long long z) { while(z --> 0) { (*this)(); } } }; struct Enemy { int x = -1; int power = -1; int score = -1; int hp = -1; inline bool exist() { return hp >= 1; } }; struct Action { int act; int attack_y = -1; }; struct State { const int X = 25; const int Y = 60; const int H = 1000; int turn = 0; int x = 12; int power_sum = 0; i64 score = 0; std::vector> field; State() { field.resize(X, std::vector(H + Y + 100)); } int level() const { return 1 + power_sum / 100; } Action forward(int act, const std::vector& new_enemies) { x = (x + act + X) % X; if(field[x][turn].exist()) { score -= 1e8; } Action action = Action { .act = act }; for(int y = turn; y < turn + Y; y++) { if(field[x][y].exist()) { int dmg = level(); score += std::min(field[x][y].hp, dmg); field[x][y].hp -= dmg; if(!field[x][y].exist()) { //score += field[x][y].score; power_sum += field[x][y].power; } action = Action { .act = act, .attack_y = y }; break; } } turn++; if(field[x][turn].exist()) { score -= 1e8; } for(auto e: new_enemies) { field[e.x][turn + Y - 1] = e; } return action; } void backward(const Action& act) { if(field[x][turn].exist()) { score += 1e8; } turn--; if(act.attack_y != -1) { if(!field[x][act.attack_y].exist()) { //score -= field[x][act.attack_y].score; power_sum -= field[x][act.attack_y].power; } int dmg = level(); field[x][act.attack_y].hp += dmg; score -= std::min(field[x][act.attack_y].hp, dmg); } if(field[x][turn].exist()) { score += 1e8; } x = (x - act.act + X) % X; } }; struct EulerTourEdge { bool is_down; bool is_leaf; Action act; i64 score; int id; }; struct EulerTourTree { std::vector edges; std::vector> leaf_scores; }; i64 sol_score = 0; i64 sol_act = 0; std::vector empty_enemies; const int FLAG_LENGTH = 3 * 25 * 25; using flagset = std::bitset; void extend_euler_tree(const State& init_state, const EulerTourTree& cur_tree, EulerTourTree& next_tree, const flagset& flag) { //std::cerr << "---" << std::endl; State state = init_state; int ids = 0; std::vector down_actions; int downed = 0; for(int ei = 0; ei < cur_tree.edges.size(); ei++) { auto& e = cur_tree.edges[ei]; //std::cerr << e.is_down << " " << e.is_leaf << " " << " " << e.action << " " << e.score << std::endl; if(e.is_down) { down_actions.push_back(e.act); state.forward(e.act.act, empty_enemies); { int score = state.score; if(sol_score < score) { sol_score = score; sol_act = down_actions.front().act; } } } else { // up if(e.is_leaf /* && !state.is_done() */ && flag.test(e.id)) { for(int dir = -1; dir <= 1; dir++) { { // completion edge for new leaf for(; downed < down_actions.size(); downed++) { next_tree.edges.push_back( EulerTourEdge { .is_down = true, .is_leaf = false, .act = down_actions[downed], .score = 0, }); } auto act = state.forward(dir, empty_enemies); i64 score = state.score; next_tree.edges.push_back( EulerTourEdge { .is_down = true, .is_leaf = false, .act = act, .score = 0, }); next_tree.edges.push_back( EulerTourEdge { .is_down = false, .is_leaf = true, .act = {}, .score = score, .id = ids++, }); next_tree.leaf_scores.push_back({ score, ids - 1, state.x}); state.backward(act); } } } if(down_actions.empty()) { next_tree.edges.push_back( EulerTourEdge { .is_down = false, .is_leaf = false, .act = {}, .score = 0, }); return; } state.backward(down_actions.back()); if(downed == down_actions.size()) { next_tree.edges.push_back( EulerTourEdge { .is_down = false, .is_leaf = false, .act = {}, .score = 0, }); downed--; } down_actions.pop_back(); } } } int beam_search(const State& init_state) { const int beam_width = 50; EulerTourTree cur_tree; EulerTourTree next_tree; sol_score = -1e9; sol_act = -2; cur_tree.edges.push_back( EulerTourEdge { .is_down = 0, .is_leaf = 1, .act = {}, .score = init_state.score, .id = 0, }); cur_tree.leaf_scores.push_back({ init_state.score, 0, init_state.x}); std::vector cnt(25); for(int depth = 0; depth < 25; depth++) { auto& score = cur_tree.leaf_scores; int w = std::min(beam_width, (int)score.size()); std::sort(score.begin(), score.end(), std::greater>()); //std::cerr << depth << " " << std::get<0>(score[0]) << " " << std::get<0>(score.back()) << std::endl; next_tree.edges.clear(); next_tree.leaf_scores.clear(); flagset flag; std::fill(cnt.begin(), cnt.end(), 0); for(int i = 0; i < score.size(); i++) { auto& [s, id, x] = score[i]; if(cnt[x]++ < 2) { flag.set(id); } } extend_euler_tree(init_state, cur_tree, next_tree, flag); std::swap(cur_tree, next_tree); } return sol_act; } char act_to_char(int act) { static char ac[] = "LSR"; return ac[act + 1]; } void solve() { const int T = 1000; State init_state; int before_act = 0; for(int t = 0; t < T; t++) { int N; std::cin >> N; if(N == -1) { return; } std::vector es(N); for(int i = 0; i < N; i++) { std::cin >> es[i].hp >> es[i].power >> es[i].x; es[i].score = es[i].hp; } init_state.forward(before_act, es); int act = beam_search(init_state); //std::cerr << act << " " << init_state.score << " " << init_state.x << std::endl; before_act = act; /* for(int x = 0; x < 25; x++) { std::cerr << x << ":\t"; for(int y = init_state.turn; y < init_state.turn + 60; y++) { std::cerr << init_state.field[x][y].exist(); } std::cerr << std::endl; } if(init_state.score < 0) { return; } */ std::cerr << init_state.score << std::endl; std::cout << act_to_char(act) << std::endl; } } int main() { solve(); Xor64 mt(786); }