結果

問題 No.5017 Tool-assisted Shooting
ユーザー nikajnikaj
提出日時 2023-07-16 21:05:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,390 ms / 2,000 ms
コード長 12,265 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 168,076 KB
実行使用メモリ 26,536 KB
スコア 4,752,976
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-16 21:08:05
合計ジャッジ時間 133,280 ms
ジャッジサーバーID
（参考情報） 		judge17 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,251 ms
24,404 KB
testcase_01 AC 1,287 ms
25,916 KB
testcase_02 AC 1,171 ms
23,936 KB
testcase_03 AC 1,254 ms
24,952 KB
testcase_04 AC 1,181 ms
23,960 KB
testcase_05 AC 1,212 ms
25,224 KB
testcase_06 AC 1,270 ms
24,756 KB
testcase_07 AC 1,226 ms
25,176 KB
testcase_08 AC 1,182 ms
24,204 KB
testcase_09 AC 1,244 ms
24,564 KB
testcase_10 AC 1,164 ms
24,700 KB
testcase_11 AC 1,177 ms
24,232 KB
testcase_12 AC 1,250 ms
24,768 KB
testcase_13 AC 1,227 ms
24,844 KB
testcase_14 AC 1,248 ms
25,148 KB
testcase_15 AC 1,317 ms
25,652 KB
testcase_16 AC 1,153 ms
23,792 KB
testcase_17 AC 1,221 ms
24,992 KB
testcase_18 AC 1,254 ms
24,472 KB
testcase_19 AC 1,238 ms
24,692 KB
testcase_20 AC 1,245 ms
25,312 KB
testcase_21 AC 1,233 ms
24,648 KB
testcase_22 AC 1,140 ms
24,044 KB
testcase_23 AC 1,215 ms
23,884 KB
testcase_24 AC 1,201 ms
25,204 KB
testcase_25 AC 1,293 ms
25,072 KB
testcase_26 AC 1,142 ms
24,536 KB
testcase_27 AC 1,225 ms
24,848 KB
testcase_28 AC 1,285 ms
25,468 KB
testcase_29 AC 1,141 ms
24,248 KB
testcase_30 AC 1,117 ms
23,988 KB
testcase_31 AC 1,155 ms
24,664 KB
testcase_32 AC 1,229 ms
25,448 KB
testcase_33 AC 1,251 ms
25,356 KB
testcase_34 AC 1,202 ms
24,228 KB
testcase_35 AC 1,238 ms
25,100 KB
testcase_36 AC 1,169 ms
24,524 KB
testcase_37 AC 1,221 ms
24,956 KB
testcase_38 AC 1,211 ms
24,816 KB
testcase_39 AC 1,233 ms
24,460 KB
testcase_40 AC 1,243 ms
25,008 KB
testcase_41 AC 1,206 ms
24,692 KB
testcase_42 AC 1,267 ms
25,436 KB
testcase_43 AC 1,207 ms
24,700 KB
testcase_44 AC 1,251 ms
25,320 KB
testcase_45 AC 1,209 ms
24,592 KB
testcase_46 AC 1,250 ms
24,672 KB
testcase_47 AC 1,180 ms
24,400 KB
testcase_48 AC 1,316 ms
24,880 KB
testcase_49 AC 1,190 ms
25,016 KB
testcase_50 AC 1,152 ms
24,528 KB
testcase_51 AC 1,285 ms
25,120 KB
testcase_52 AC 1,291 ms
25,020 KB
testcase_53 AC 1,253 ms
24,932 KB
testcase_54 AC 1,303 ms
25,528 KB
testcase_55 AC 1,188 ms
24,680 KB
testcase_56 AC 1,236 ms
24,476 KB
testcase_57 AC 1,148 ms
24,472 KB
testcase_58 AC 1,226 ms
24,936 KB
testcase_59 AC 1,295 ms
25,664 KB
testcase_60 AC 1,189 ms
24,296 KB
testcase_61 AC 1,228 ms
24,712 KB
testcase_62 AC 1,142 ms
24,952 KB
testcase_63 AC 1,239 ms
25,012 KB
testcase_64 AC 1,281 ms
24,908 KB
testcase_65 AC 1,390 ms
26,536 KB
testcase_66 AC 1,277 ms
25,560 KB
testcase_67 AC 1,236 ms
24,760 KB
testcase_68 AC 1,123 ms
24,624 KB
testcase_69 AC 1,211 ms
25,024 KB
testcase_70 AC 1,201 ms
24,356 KB
testcase_71 AC 1,228 ms
25,964 KB
testcase_72 AC 1,174 ms
24,348 KB
testcase_73 AC 1,317 ms
24,656 KB
testcase_74 AC 1,178 ms
24,620 KB
testcase_75 AC 1,278 ms
25,124 KB
testcase_76 AC 1,249 ms
25,192 KB
testcase_77 AC 1,296 ms
25,348 KB
testcase_78 AC 1,219 ms
24,532 KB
testcase_79 AC 1,193 ms
24,372 KB
testcase_80 AC 1,295 ms
24,848 KB
testcase_81 AC 1,200 ms
24,156 KB
testcase_82 AC 1,166 ms
25,124 KB
testcase_83 AC 1,229 ms
24,344 KB
testcase_84 AC 1,200 ms
25,036 KB
testcase_85 AC 1,229 ms
25,272 KB
testcase_86 AC 1,312 ms
24,948 KB
testcase_87 AC 1,184 ms
24,304 KB
testcase_88 AC 1,253 ms
25,672 KB
testcase_89 AC 1,270 ms
24,568 KB
testcase_90 AC 1,286 ms
25,044 KB
testcase_91 AC 1,278 ms
25,500 KB
testcase_92 AC 1,102 ms
24,152 KB
testcase_93 AC 1,213 ms
25,096 KB
testcase_94 AC 1,157 ms
24,184 KB
testcase_95 AC 1,262 ms
24,624 KB
testcase_96 AC 1,248 ms
25,240 KB
testcase_97 AC 1,200 ms
24,644 KB
testcase_98 AC 1,279 ms
24,792 KB
testcase_99 AC 1,278 ms
24,920 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 HP;
    int fd;
};

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, double> 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, 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 = 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;
                        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 = 24;

    bn = 0;

    F0(i, maxT + 1) pq[i].clear();

    Prepare();

    State s0;
    s0.X = X;
    s0.HP = 0;
    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;
}
0