結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 nikaj
|
| 提出日時 | 2023-07-16 21:17:28 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 1,862 ms / 2,000 ms |
| コード長 | 12,272 bytes |
| コンパイル時間 | 3,027 ms |
| コンパイル使用メモリ | 164,880 KB |
| 実行使用メモリ | 27,712 KB |
| スコア | 4,757,709 |
| 平均クエリ数 | 1000.00 |
| 最終ジャッジ日時 | 2023-07-16 21:20:27 |
| 合計ジャッジ時間 | 176,113 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,730 ms
25,460 KB |
| testcase_01 | AC | 1,728 ms
25,480 KB |
| testcase_02 | AC | 1,517 ms
25,776 KB |
| testcase_03 | AC | 1,693 ms
25,368 KB |
| testcase_04 | AC | 1,574 ms
25,648 KB |
| testcase_05 | AC | 1,602 ms
25,756 KB |
| testcase_06 | AC | 1,654 ms
25,308 KB |
| testcase_07 | AC | 1,704 ms
25,556 KB |
| testcase_08 | AC | 1,584 ms
25,576 KB |
| testcase_09 | AC | 1,684 ms
25,308 KB |
| testcase_10 | AC | 1,675 ms
25,444 KB |
| testcase_11 | AC | 1,598 ms
25,120 KB |
| testcase_12 | AC | 1,664 ms
25,664 KB |
| testcase_13 | AC | 1,651 ms
25,636 KB |
| testcase_14 | AC | 1,737 ms
25,688 KB |
| testcase_15 | AC | 1,787 ms
27,688 KB |
| testcase_16 | AC | 1,495 ms
25,260 KB |
| testcase_17 | AC | 1,689 ms
25,284 KB |
| testcase_18 | AC | 1,687 ms
25,208 KB |
| testcase_19 | AC | 1,659 ms
25,124 KB |
| testcase_20 | AC | 1,647 ms
25,372 KB |
| testcase_21 | AC | 1,715 ms
25,468 KB |
| testcase_22 | AC | 1,513 ms
25,540 KB |
| testcase_23 | AC | 1,605 ms
25,752 KB |
| testcase_24 | AC | 1,708 ms
27,308 KB |
| testcase_25 | AC | 1,706 ms
25,428 KB |
| testcase_26 | AC | 1,571 ms
25,136 KB |
| testcase_27 | AC | 1,660 ms
25,560 KB |
| testcase_28 | AC | 1,783 ms
27,356 KB |
| testcase_29 | AC | 1,487 ms
25,156 KB |
| testcase_30 | AC | 1,486 ms
25,112 KB |
| testcase_31 | AC | 1,579 ms
25,212 KB |
| testcase_32 | AC | 1,686 ms
27,408 KB |
| testcase_33 | AC | 1,750 ms
27,576 KB |
| testcase_34 | AC | 1,651 ms
25,212 KB |
| testcase_35 | AC | 1,698 ms
25,288 KB |
| testcase_36 | AC | 1,593 ms
25,572 KB |
| testcase_37 | AC | 1,658 ms
25,640 KB |
| testcase_38 | AC | 1,633 ms
25,232 KB |
| testcase_39 | AC | 1,707 ms
25,440 KB |
| testcase_40 | AC | 1,705 ms
25,684 KB |
| testcase_41 | AC | 1,633 ms
25,560 KB |
| testcase_42 | AC | 1,694 ms
27,676 KB |
| testcase_43 | AC | 1,641 ms
25,140 KB |
| testcase_44 | AC | 1,773 ms
25,268 KB |
| testcase_45 | AC | 1,583 ms
25,344 KB |
| testcase_46 | AC | 1,692 ms
25,636 KB |
| testcase_47 | AC | 1,556 ms
25,684 KB |
| testcase_48 | AC | 1,766 ms
25,720 KB |
| testcase_49 | AC | 1,616 ms
25,600 KB |
| testcase_50 | AC | 1,681 ms
25,264 KB |
| testcase_51 | AC | 1,731 ms
25,516 KB |
| testcase_52 | AC | 1,742 ms
27,596 KB |
| testcase_53 | AC | 1,601 ms
25,404 KB |
| testcase_54 | AC | 1,781 ms
27,712 KB |
| testcase_55 | AC | 1,621 ms
25,376 KB |
| testcase_56 | AC | 1,657 ms
25,488 KB |
| testcase_57 | AC | 1,517 ms
25,576 KB |
| testcase_58 | AC | 1,707 ms
25,144 KB |
| testcase_59 | AC | 1,746 ms
25,468 KB |
| testcase_60 | AC | 1,589 ms
25,736 KB |
| testcase_61 | AC | 1,627 ms
25,304 KB |
| testcase_62 | AC | 1,500 ms
25,296 KB |
| testcase_63 | AC | 1,687 ms
25,592 KB |
| testcase_64 | AC | 1,731 ms
25,200 KB |
| testcase_65 | AC | 1,862 ms
27,424 KB |
| testcase_66 | AC | 1,740 ms
27,536 KB |
| testcase_67 | AC | 1,672 ms
25,368 KB |
| testcase_68 | AC | 1,507 ms
25,708 KB |
| testcase_69 | AC | 1,620 ms
27,488 KB |
| testcase_70 | AC | 1,590 ms
25,616 KB |
| testcase_71 | AC | 1,687 ms
27,648 KB |
| testcase_72 | AC | 1,463 ms
25,236 KB |
| testcase_73 | AC | 1,747 ms
25,268 KB |
| testcase_74 | AC | 1,525 ms
25,356 KB |
| testcase_75 | AC | 1,647 ms
25,428 KB |
| testcase_76 | AC | 1,673 ms
25,352 KB |
| testcase_77 | AC | 1,771 ms
27,328 KB |
| testcase_78 | AC | 1,645 ms
25,532 KB |
| testcase_79 | AC | 1,586 ms
25,700 KB |
| testcase_80 | AC | 1,706 ms
25,112 KB |
| testcase_81 | AC | 1,611 ms
25,456 KB |
| testcase_82 | AC | 1,644 ms
25,720 KB |
| testcase_83 | AC | 1,702 ms
25,324 KB |
| testcase_84 | AC | 1,609 ms
25,364 KB |
| testcase_85 | AC | 1,682 ms
25,232 KB |
| testcase_86 | AC | 1,759 ms
25,884 KB |
| testcase_87 | AC | 1,595 ms
25,340 KB |
| testcase_88 | AC | 1,689 ms
25,168 KB |
| testcase_89 | AC | 1,700 ms
25,592 KB |
| testcase_90 | AC | 1,716 ms
25,580 KB |
| testcase_91 | AC | 1,726 ms
27,432 KB |
| testcase_92 | AC | 1,464 ms
25,672 KB |
| testcase_93 | AC | 1,697 ms
25,648 KB |
| testcase_94 | AC | 1,543 ms
25,568 KB |
| testcase_95 | AC | 1,681 ms
25,748 KB |
| testcase_96 | AC | 1,666 ms
25,584 KB |
| testcase_97 | AC | 1,642 ms
25,112 KB |
| testcase_98 | AC | 1,751 ms
25,132 KB |
| testcase_99 | AC | 1,696 ms
25,456 KB |
ソースコード
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, an;
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 {
int *hits;
int X;
int S;
int HP;
int fd;
};
const int BB = 1 << 20;
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, double> Hashes;
int id[M][N], nx[M][N];
vector<pii> active;
void Prepare() {
active.clear();
an = 0;
F0(i, H) F0(j, W) if (hp[i][j]) {
id[i][j] = an++;
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, int* hits) {
return (x < H && hp[x][y]) ? hits[id[x][y]] : 0;
}
int Target(int x, int y, 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, 11) {
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 newH = s.HP + ihp[active[id].first][active[id].second];
int fd = level == 0 ? dir : s.fd;
int bt1 = 500;
int bt2 = 700;
double av = 0;
if (turn > bt1) av += 1.0 * (turn - bt1) / (1000 - bt1)* newH;
if (turn < bt2) av += 2.0 * (bt2 - turn) / bt2 * newS;
double eval = -av;
if (moves + turn <= 1001 && av > bv) {
bmoves = moves;
bv = av;
bdir = fd;
}
if (moves < maxT && ((SZ(pq[moves]) < BC || (--pq[moves].end())->first > eval))) {
ns.hits = buff + buff_pos; buff_pos += an;
F0(i, an) ns.hits[i] = s.hits[i];
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;
ns.HP = newH;
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) break;
}
}
}
}
}
void BeamSearch() {
bv = -1.0;
bdir = 0;
maxT = 45;
BC = 36;
bn = 0;
buff_pos = 0;
F0(i, maxT + 1) pq[i].clear();
Prepare();
State s0;
s0.X = X;
s0.HP = 0;
s0.hits = buff + buff_pos; buff_pos += an;
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;
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;
}