結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 nikaj
|
| 提出日時 | 2023-07-16 18:54:26 |
| 言語 | C++11 (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 1,396 ms / 2,000 ms |
| コード長 | 12,249 bytes |
| コンパイル時間 | 2,584 ms |
| コンパイル使用メモリ | 172,436 KB |
| 実行使用メモリ | 25,448 KB |
| スコア | 4,697,607 |
| 平均クエリ数 | 1000.00 |
| 最終ジャッジ日時 | 2023-07-16 18:59:26 |
| 合計ジャッジ時間 | 131,470 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
double TL = 0.01;
int STANDARD = 1;
int DBG = 0;
#include <bits/stdc++.h>
using namespace std;
#define F0(i,n) for (int i=0; i<n; i++)
#define F1(i,n) for (int i=1; i<=n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const int inf = 1000009;
const double pi = acos(-1.0);
typedef pair<int, int> pii;
typedef long long ll;
const double EPS = 1e-9;
const int MOD = 998244353;
#define PR(x) cerr << #x << "=" << x << endl
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<class A, class B, class C>
ostream& operator<<(ostream& os, const tuple<A, B, C>& p) { os << "(" << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ")"; return os; }
istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; }
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) { os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os; }
template<class T>
ostream& operator<<(ostream& os, const set<T>& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}" << endl; return os; }
template<class T, class R>
ostream& operator<<(ostream& os, const map<T,R>& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}" << endl; return os; }
//#pragma GCC optimize("O3")
#ifndef __APPLE__
inline ll GetTSC() {
ll lo, hi;
asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
return lo + (hi << 32);
}
inline double GetSeconds() {
return GetTSC() / 3.0e9;
}
#else
#include <sys/time.h>
double GetSeconds() {
timeval tv;
gettimeofday(&tv, 0);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
#endif
const int MAX_RAND = 1 << 30;
struct Rand {
ll x, y, z, w, o;
Rand() {}
Rand(ll seed) { reseed(seed); o = 0; }
inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0; F0(i, 20) mix(); }
inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); }
inline ll rand() { mix(); return x & (MAX_RAND - 1); }
inline int nextInt(int n) { return rand() % n; }
inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; }
inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; }
double nextDouble() { return rand() * 1.0 / MAX_RAND; }
};
Rand my(2023);
double saveTime;
double t_o[20];
ll c_o[20];
void Init() {
saveTime = GetSeconds();
F0(i, 20) t_o[i] = 0.0;
F0(i, 20) c_o[i] = 0;
}
double Elapsed() { return GetSeconds() - saveTime; }
void Report() {
double tmp = Elapsed();
cerr << "-------------------------------------" << endl;
cerr << "Elapsed time: " << tmp << " sec" << endl;
double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl;
F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl;
cerr << "-------------------------------------" << endl;
}
struct AutoTimer {
int x;
double t;
AutoTimer(int x) : x(x) {
t = Elapsed();
}
~AutoTimer() {
t_o[x] += Elapsed() - t;
}
};
#define AT(i) AutoTimer a##i(i)
//#define AT(i)
int X, turn;
int n, m, S, str, score, newX;
string ans;
const int N = 32;
const int M = 64;
int P[N];
const int W = 25;
const int H = 60;
const int DX[]={-1,0,1,0};
const int DY[]={0,1,0,-1};
const string CS="nesw";
const string HS="URDL";
int hp[M][N], pw[M][N], ihp[M][N], f[N];
double bv;
int bmoves;
int bdir;
void Greedy() {
bv = -1.0;
for (int i = 1; i < H; i++) if (hp[i][X] > 0) {
if ((i) * str >= hp[i][X]) {
double av = 1.0 * pw[i][X] / ((hp[i][X] + str - 1) / str - 1);
if (av > bv) {
bv = av;
newX = X;
ans = "S";
}
}
break;
}
for (int dir = -1; dir <= 1; dir += 2) {
int cX = X;
F1(steps, 25) {
if (hp[steps - 1][cX]) break;
cX = (cX + dir + W) % W;
if (hp[steps - 1][cX]) break;
for (int i = steps; i < H; i++) if (hp[i][cX] > 0) {
// TODO
if ((i - steps + 1) * str >= hp[i][cX]) {
double av = 1.0 * pw[i][cX] / (((hp[i][cX] + str - 1) / str) + steps - 2);
if (av > bv) {
bv = av;
newX = (X + dir + W) % W;
ans = dir == -1 ? "L" : "R";
}
}
break;
}
}
}
}
struct State {
vector<int> hits;
int X;
int S;
int fd;
ll Hash() {
ll ret = S;
ret = ret * 239 + X;
for (int t : hits) ret = ret * 239 + t;
return ret;
}
};
const int BB = 1 << 16;
State bb[BB], ns;
const int BUFF = 1 << 23;
int buff[BUFF], buff_pos;
int bn;
typedef double EvalType;
const int MAXB = 1000;
set<pair<EvalType, int>> pq[MAXB+1];
unordered_map<ll, int> Hashes;
int id[M][N], nx[M][N];
vector<pii> active;
void Prepare() {
active.clear();
F0(i, H) F0(j, W) if (hp[i][j]) {
id[i][j] = SZ(active);
active.push_back(pii(i, j));
}
F0(i, H) F0(j, W) {
int x = i + 1;
while (x < H && !hp[x][j]) x++;
nx[i][j] = x;
}
}
inline int HP(int x, int y, vector<int>& hits) {
return (x < H && hp[x][y]) ? hits[id[x][y]] : 0;
}
int Target(int x, int y, vector<int>& hits) {
while (x < H && HP(x, y, hits) <= 0) x = nx[x][y];
return x < H ? id[x][y] : -1;
}
int BC, BW, maxT;
void BeamStep() {
F0(level, maxT) {
F0(e, BW) {
if (pq[level].empty()) break;
int lindex = pq[level].begin()->second;
pq[level].erase(pq[level].begin());
State s = bb[lindex];
// TODO: stay
for (int dir = -1; dir <= 1; dir += 1) {
int cX = s.X;
int str = s.S / 100 + 1;
//PR(dir);
F1(steps, 10) {
if (HP(level + steps - 1, cX, s.hits) > 0) break;
cX = (cX + dir + W) % W;
if (HP(level + steps - 1, cX, s.hits) > 0) break;
int id = Target(level + steps, cX, s.hits);
if (id == -1) continue;
int i = active[id].first;
//assert(active[id].second == cX);
ll cur_hp = HP(i, cX, s.hits);
//assert(cur_hp > 0);
if ((i - (level + steps) + 1) * str < cur_hp) continue;
int shots = (cur_hp + str - 1) / str;
int moves = level + steps - 1 + shots;
int newS = s.S + pw[active[id].first][active[id].second];
int fd = level == 0 ? dir : s.fd;
double av = 1.0 * newS;
if (av > bv) {
bmoves = moves;
bv = av;
bdir = fd;
}
ll eval = -newS;
if (moves < maxT && ((SZ(pq[moves]) < BC || (--pq[moves].end())->first > eval))) {
ns = s;
ns.X = cX;
int attack_turn = level;
for (int x = (s.X + dir + W) % W; x != cX; x = (x + dir + W) % W) {
int nx = Target(attack_turn, x, s.hits);
if (nx != -1) {
ns.hits[nx] -= str;
//assert(ns.hits[nx] > 0);
}
attack_turn++;
}
ns.hits[id] = 0;
ns.S = newS;
ns.fd = fd;
ll h = ns.Hash();
if (!Hashes.count(h) || Hashes[h] <= ns.S) {
Hashes[h] = ns.S;
pq[moves].insert(make_pair(eval, bn));
if (SZ(pq[moves]) > BC) {
pq[moves].erase(--pq[moves].end());
}
bb[bn++] = ns;
}
}
//cerr << steps << " " << cX << " " << id << " " << shots << endl;
if (shots == 1 || dir == 0) break;
}
}
}
}
}
void BeamSearch() {
Hashes.clear();
bv = -1.0;
bdir = 0;
maxT = 45;
BC = 24;
bn = 0;
F0(i, maxT + 1) pq[i].clear();
Prepare();
State s0;
s0.X = X;
s0.hits.assign(SZ(active), 0);
F0(i, SZ(active)) s0.hits[i] = hp[active[i].first][active[i].second];
s0.S = S;
pq[0].insert(make_pair(0, 0));
bb[bn++] = s0;
/*
int BEAM_STEPS = 0;
while (Elapsed() < TL) {
BW = 1;
BEAM_STEPS += BW;
BeamStep();
}
PR(BEAM_STEPS);
*/
BW = BC;
BeamStep();
//cerr << turn << " " << bdir << " " << bv << " " << bmoves << endl;
//PR(bn);
//if (bn > BB / 4) throw;
//PR(buff_pos);
//if (buff_pos > BUFF / 4) throw;
if (DBG) {
F0(i, MAXB) {
if (SZ(pq[i])) cerr << i << " " << SZ(pq[i]) << endl;
}
}
}
void Solve() {
X = 12;
str = 1;
score = 0;
S = 0;
for (turn = 1; turn <= 1000; turn++) {
cin >> n;
if (n == -1) break;
F0(h, H) F0(w, W) {
hp[h][w] = hp[h + 1][w];
ihp[h][w] = ihp[h + 1][w];
pw[h][w] = pw[h + 1][w];
}
F0(i, n) {
int h, p, x;
cin >> h >> p >> x;
hp[H-1][x] = h;
ihp[H-1][x] = h;
pw[H-1][x] = p;
f[x]++;
}
if (DBG && turn <= 187) {
for (int i = 30; i >= 0; i--) {
F0(j, W) if (hp[i][j]) {
int d = (hp[i][j] + str - 1) / str;
d = min(d, 9);
cerr << d;
} else cerr << ".";
cerr << endl;
}
F0(j, W) if (j == X) cerr << "X"; else cerr << " "; cerr << endl << endl;
}
if (hp[0][X] > 0) {
cerr << "Dead at " << turn << endl;
break;
}
//Greedy();
BeamSearch();
if (bdir == -1) ans = "L";
else if (bdir == 0) ans = "S";
else ans = "R";
X = (X + bdir + W) % W;
if (DBG) cerr << bv << " " << ans << endl;
for (int i = 1; i < H; i++) if (hp[i][X] > 0) {
pii t = pii(i, X);
hp[t.first][t.second] -= str;
if (hp[t.first][t.second] <= 0) {
S += pw[t.first][t.second];
score += ihp[t.first][t.second];
str = 1 + S / 100;
hp[t.first][t.second] = 0;
ihp[t.first][t.second] = 0;
pw[t.first][t.second] = 0;
}
break;
}
cout << ans << endl;
}
PR(score);
if (0)
F0(i, W) {
cerr << P[i] << " " << f[i] << endl;
}
}
void ReadInput() {
F0(i, W) cin >> P[i];
}
int main(int argc, char* argv[]) {
int seed1 = 0, seed2 = 0;
if(argc>1) {
seed1 = seed2 = atoi(argv[1]);
if (argc > 2) {
DBG = atoi(argv[2]);
}
STANDARD=0;
}
if(STANDARD) {
Solve();
return 0;
}
for (int seed=seed1; seed<=seed2; seed++) {
if(seed>=0 && seed<5000) {
char inp[128];
sprintf(inp, "in/%04d.txt", seed);
char outp[128];
sprintf(outp, "out/%04d.txt", seed);
ignore = freopen(inp, "r", stdin);
ignore = freopen(outp, "w", stdout);
ReadInput();
//cerr << "Seed #" << seed << " ";
Solve();
//cout << "Score would be " << bscore << endl;
} else {
// Generate
throw;
}
}
return 0;
}