#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define InfL 2000000000 #define InfLL 4000000000000000000LL #define mod 1000000007 #define rep(i,n) for(int i=0;i=0;i--) using namespace std; typedef long long ll; typedef double db; typedef long double ld; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vb; typedef vector vd; bool debug = false; // false : 提出, true : fin - fout double time_ratio = 1.0; clock_t time_ini; string file_No = "0000"; ifstream fin; ofstream fout; ofstream fout_debug; int Gaussian_size = 1000000; vector Gaussian_(Gaussian_size); constexpr int width = 25; // フィールドの幅 constexpr int height = 60; // フィールドの高さ constexpr int max_turn = 1000; // ゲームの最大ターン数 int xR(int x) { int ans = x + 1; ans %= 25; return ans; } int xL(int x) { int ans = x - 1; ans += 25; ans %= 25; return ans; } void debug_init() { string txt = ".txt"; string ifname = "in\\"; ifname = ifname + file_No + txt; fin.open(ifname); string ofname = "out\\"; ofname = ofname + file_No + txt; fout.open(ofname); string ofname_debug = "debug\\"; ofname_debug = ofname_debug + file_No + txt; fout_debug.open(ofname_debug); time_ratio = 0.133; // 5950X // time_ratio = 0.183; // 12700KF } void debug_end() { fin.close(); fout.close(); fout_debug.close(); } double time_diff() { ll time_tmp = clock(); const double time = time_ratio * static_cast(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0; return time; } int xor128() { static int x = 123456789, y = 362436069, z = 521288629, w = 88675123; int t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } double RAND_() { while (1) { double rand_ = (double)(xor128() % InfL) / (double)InfL; if (rand_ >= 0 && rand_ < 1) return rand_; } } double Gaussian() { double X = RAND_(); double Y = RAND_(); double Z = sqrt(-2.0 * log(X)) * cos(2.0 * acos(-1.0) * Y); return Z; } struct Pi_est { vector n; vector P; int t = 0; void init() { n.resize(25, 0); P.resize(25, 0.045); } void re_est(vector x) { t++; for (int xtmp : x) n[xtmp]++; rep(xtmp, 25) { P[xtmp] = (double)n[xtmp] / (double)t; P[xtmp] = max(0.01, P[xtmp]); P[xtmp] = min(0.08, P[xtmp]); } return; } }; Pi_est pi_est; struct Enemy { int h, p, x, y, hrem, id; void init(int h_, int p_, int x_, int id_) { h = h_; p = p_; x = x_; y = 59; id = id_; hrem = h_; } }; struct Input { int n; vector h, p, x; void readProblem(istream& in = cin) { in >> n; if (n == -1) return; h.resize(n); p.resize(n); x.resize(n); rep(i, n) in >> h[i] >> p[i] >> x[i]; pi_est.re_est(x); return; } }; struct Output { char ans = 'S'; void resize_all() { } void writeSolution(ostream& out = cout) { out << ans << "\n"; return; } }; Input input[1000]; Output output[1000]; struct Field { int power = 100; int score = 0; int X = 12; int idtmp; bool stop = false; vector E; set id_active; vector id_x; vector id_xy; void init() { id_x.resize(25); id_xy.resize(25, vi(60+10, -1)); } void read(int t) { rep(x, 25) { rep(y, 60) id_xy[x][y] = -1; } set id_erase; for (int id : id_active) { E[id].y--; if (E[id].y == -1) { id_erase.insert(id); id_x[E[id].x].erase(id_x[E[id].x].begin()); } else { id_xy[E[id].x][E[id].y] = id; if (E[id].y == 0) { if (X == E[id].x) stop = true; } } } for (int id : id_erase) id_active.erase(id); rep (i, input[t].n) { Enemy e; e.init(input[t].h[i], input[t].p[i], input[t].x[i], idtmp); id_xy[input[t].x[i]][59] = idtmp; E.push_back(e); id_x[e.x].push_back(idtmp); id_active.insert(idtmp); idtmp++; } } }; Field field; struct Plan { int score = 0; int power = field.power; int X = 12; string ans; vector to; void make_to() { vector bs; for (int id : field.id_active) bs.push_back(make_pair(field.E[id].y, id)); sort(bs.begin(), bs.end()); to.clear(); for (pii b : bs) { to.push_back(b.second); } } void re_to() { int S = to.size(); set id_ex; rrep(i, S) { id_ex.insert(to[i]); if (field.id_active.find(to[i]) == field.id_active.end()) to.erase(to.begin() + i); } for (int id : field.id_active) { if (id_ex.find(id) == id_ex.end()) to.push_back(id); } } void make_ans() { ans = ""; vector E = field.E; vector id_x = field.id_x; int x = X; int t = 0; int k = 0; score = 0; power = field.power; set bset; bset.insert(-1); while (1) { if (k >= to.size()) break; if (field.id_xy[x][t] != -1) { score = -1; break; } int id = to[k]; int xto = field.E[id].x; int len = (xto - x + 25) % 25; if (len > 12) len -= 25; int tnext = t + abs(len); if (field.E[id].y - tnext <= 0) { k++; continue; } if (len > 0) { int xnext = xR(x); if (bset.find(field.id_xy[xnext][t]) == bset.end() || bset.find(field.id_xy[xnext][t + 1]) == bset.end()) ans.push_back('S'); else { ans.push_back('R'); x = xnext; } } else if (len < 0) { int xnext = xL(x); if (bset.find(field.id_xy[xnext][t]) == bset.end() || bset.find(field.id_xy[xnext][t + 1]) == bset.end()) ans.push_back('S'); else { ans.push_back('L'); x = xnext; } } else ans.push_back('S'); int s = id_x[x].size(); if (s > 0) { int idtmp = id_x[x][0]; int hrem = E[idtmp].hrem; E[idtmp].hrem -= power / 100; if (hrem <= 0) { power += E[idtmp].p; score += E[idtmp].h; id_x[x].erase(id_x[x].begin()); bset.insert(idtmp); if (id == idtmp) k++; } } t++; if (t >= 60) break; } } }; Plan plan; void solve_init() { rep(t, 1000) output[t].resize_all(); field.init(); return; } void solveA(int t) { field.read(t); if (field.stop) return; return; } void solveB(int t) { char ans = 'S'; plan.re_to(); plan.make_ans(); ll sc1 = plan.score; ll sc2 = plan.power; ll le = plan.ans.length(); ll sc = sc1 * 100000 + sc2 * 100000 + plan.ans.length(); double start_temp = 0.0; double end_temp = 0.0; double TIME_LIMIT = 1.95 * t; ll loop_count = 0; double time_now = 0.0; double temp = 0.0; int S = plan.to.size(); while (1) { //break; if (loop_count % 1000 == 0) { time_now = time_diff(); if (time_now > TIME_LIMIT) //if(loop_count == 1000) break; temp = start_temp + (end_temp - start_temp) * time_now / TIME_LIMIT; } loop_count++; ll scdiff = 0; int i = xor128() % S; int j = xor128() % S; vi to_old = plan.to; int type = xor128() % 1; if (type == 0) { if (i == j) continue; swap(plan.to[i], plan.to[j]); } else if (type == 1) { vector torand(S); rep(s, S) torand[s] = make_pair(xor128(), plan.to[s]); sort(torand.begin(), torand.end()); rep(s, S) plan.to[s] = torand[s].second; } rep(x, 25) { vector ss; vi slist; rep(s, S) { if (field.E[plan.to[s]].x != x) continue; slist.push_back(s); ss.push_back(make_pair(field.E[plan.to[s]].y, plan.to[s])); } sort(ss.begin(), ss.end()); int P = slist.size(); rep(p, P) { plan.to[slist[p]] = ss[p].second; } } plan.make_ans(); ll scnew1 = plan.score; ll scnew2 = plan.power; scdiff = scnew1 * 100000 + scnew2 * 100000 + plan.ans.length() - sc; //cout << plan.ans.length() << endl; double prob = exp(scdiff / temp); //if (scdiff > 0) { bool d = false; if (scnew1 >= 0) { if (prob > RAND_()) d = true; } else { if (prob > RAND_()) d = true; } if (d) { sc += scdiff; } else plan.to = to_old; } plan.make_ans(); ans = plan.ans[0]; if (ans == 'R') { field.X = xR(field.X); plan.X = xR(plan.X); } if (ans == 'L') { field.X = xL(field.X); plan.X = xL(plan.X); } int s = field.id_x[field.X].size(); if (s > 0) { int id = field.id_x[field.X][0]; field.E[id].hrem -= field.power / 100; if (field.E[id].hrem <= 0) { field.id_x[field.X].erase(field.id_x[field.X].begin()); int y = field.E[id].y; field.id_xy[field.X][y] = -1; field.power += field.E[id].p; field.score += field.E[id].h; field.id_active.erase(id); } } output[t].ans = ans; return; } int main(int argc, char* argv[]) { if (argc >= 2) file_No = argv[1]; time_ini = clock(); if (debug) debug_init(); pi_est.init(); solve_init(); plan.make_to(); rep(t, 1000) { debug ? input[t].readProblem(fin) : input[t].readProblem(); solveA(t); if (field.stop) return 0; solveB(t); debug ? output[t].writeSolution(fout) : output[t].writeSolution(); } fout_debug << field.score << endl; if (debug) debug_end(); return 0; }