結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 よーちゃん
|
| 提出日時 | 2023-07-16 18:59:30 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 9,308 bytes |
| コンパイル時間 | 2,432 ms |
| コンパイル使用メモリ | 154,532 KB |
| 実行使用メモリ | 28,028 KB |
| スコア | 43,001 |
| 平均クエリ数 | 70.93 |
| 最終ジャッジ日時 | 2023-07-16 19:06:18 |
| 合計ジャッジ時間 | 119,954 ms |
|
ジャッジサーバーID （参考情報） |
judge9 / judge14 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 27 RE * 41 TLE * 32 |
ソースコード
#include <iostream>#include <algorithm>#include <bitset>#include <map>#include <queue>#include <deque>#include <set>#include <stack>#include <string>#include <cstring>#include <utility>#include <vector>#include <complex>#include <valarray>#include <fstream>#include <cassert>#include <cmath>#include <functional>#include <iomanip>#include <numeric>#include <climits>#include <random>#include <time.h>#define InfL 2000000000#define InfLL 4000000000000000000LL#define mod 1000000007#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=(n-1);i>=0;i--)using namespace std;typedef long long ll;typedef double db;typedef long double ld;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef vector<int> vi;typedef vector<ll> vl;typedef vector<bool> vb;typedef vector<db> vd;bool debug = false; // false : 提出, true : fin - foutdouble time_ratio = 1.0;clock_t time_ini;string file_No = "0000";ifstream fin;ofstream fout;ofstream fout_debug;int Gaussian_size = 1000000;vector<double> 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<double>(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<int> n;vector<double> P;int t = 0;void init() {n.resize(25, 0);P.resize(25, 0.045);}void re_est(vector<int> 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<int> 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<Enemy> E;set<int> id_active;vector<vi> id_x;vector<vi> 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<int> 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<int> to;void make_to() {vector<pii> 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<int> 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<Enemy> E = field.E;vector<vi> id_x = field.id_x;int x = X;int t = 0;int k = 0;score = 0;power = field.power;set<int> 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;}}elseans.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<pii> 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<pii> 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;}elseplan.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;}