結果

問題 No.5017 Tool-assisted Shooting
ユーザー nikajnikaj
提出日時 2023-07-16 18:54:26
言語 C++11
(gcc 11.4.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,215 ms
24,472 KB
testcase_01 AC 1,298 ms
24,636 KB
testcase_02 AC 1,069 ms
23,464 KB
testcase_03 AC 1,242 ms
23,924 KB
testcase_04 AC 1,120 ms
23,676 KB
testcase_05 AC 1,187 ms
24,036 KB
testcase_06 AC 1,224 ms
23,996 KB
testcase_07 AC 1,281 ms
24,948 KB
testcase_08 AC 1,166 ms
24,436 KB
testcase_09 AC 1,241 ms
24,048 KB
testcase_10 AC 1,228 ms
24,324 KB
testcase_11 AC 1,149 ms
23,388 KB
testcase_12 AC 1,173 ms
23,924 KB
testcase_13 AC 1,188 ms
24,124 KB
testcase_14 AC 1,316 ms
24,196 KB
testcase_15 AC 1,307 ms
25,448 KB
testcase_16 AC 1,129 ms
24,372 KB
testcase_17 AC 1,197 ms
24,120 KB
testcase_18 AC 1,230 ms
23,900 KB
testcase_19 AC 1,212 ms
24,284 KB
testcase_20 AC 1,268 ms
24,764 KB
testcase_21 AC 1,289 ms
24,620 KB
testcase_22 AC 1,090 ms
24,084 KB
testcase_23 AC 1,191 ms
23,644 KB
testcase_24 AC 1,300 ms
24,120 KB
testcase_25 AC 1,301 ms
24,844 KB
testcase_26 AC 1,116 ms
24,384 KB
testcase_27 AC 1,205 ms
23,892 KB
testcase_28 AC 1,341 ms
24,336 KB
testcase_29 AC 1,079 ms
23,464 KB
testcase_30 AC 1,054 ms
23,400 KB
testcase_31 AC 1,140 ms
24,868 KB
testcase_32 AC 1,258 ms
24,904 KB
testcase_33 AC 1,334 ms
24,308 KB
testcase_34 AC 1,193 ms
23,680 KB
testcase_35 AC 1,229 ms
24,412 KB
testcase_36 AC 1,123 ms
23,800 KB
testcase_37 AC 1,261 ms
24,260 KB
testcase_38 AC 1,205 ms
23,800 KB
testcase_39 AC 1,273 ms
24,024 KB
testcase_40 AC 1,247 ms
24,668 KB
testcase_41 AC 1,154 ms
24,012 KB
testcase_42 AC 1,277 ms
24,956 KB
testcase_43 AC 1,171 ms
24,040 KB
testcase_44 AC 1,299 ms
24,524 KB
testcase_45 AC 1,221 ms
23,724 KB
testcase_46 AC 1,343 ms
24,076 KB
testcase_47 AC 1,091 ms
24,076 KB
testcase_48 AC 1,324 ms
24,392 KB
testcase_49 AC 1,221 ms
24,480 KB
testcase_50 AC 1,167 ms
24,324 KB
testcase_51 AC 1,274 ms
24,516 KB
testcase_52 AC 1,330 ms
24,184 KB
testcase_53 AC 1,233 ms
24,104 KB
testcase_54 AC 1,352 ms
24,500 KB
testcase_55 AC 1,123 ms
24,136 KB
testcase_56 AC 1,227 ms
24,104 KB
testcase_57 AC 1,145 ms
24,136 KB
testcase_58 AC 1,229 ms
24,044 KB
testcase_59 AC 1,335 ms
24,584 KB
testcase_60 AC 1,149 ms
24,124 KB
testcase_61 AC 1,173 ms
23,836 KB
testcase_62 AC 1,150 ms
24,188 KB
testcase_63 AC 1,246 ms
24,068 KB
testcase_64 AC 1,266 ms
24,604 KB
testcase_65 AC 1,375 ms
25,436 KB
testcase_66 AC 1,396 ms
24,764 KB
testcase_67 AC 1,254 ms
23,872 KB
testcase_68 AC 1,127 ms
23,876 KB
testcase_69 AC 1,180 ms
24,116 KB
testcase_70 AC 1,206 ms
24,440 KB
testcase_71 AC 1,215 ms
25,004 KB
testcase_72 AC 1,105 ms
24,184 KB
testcase_73 AC 1,310 ms
24,240 KB
testcase_74 AC 1,109 ms
24,012 KB
testcase_75 AC 1,291 ms
24,612 KB
testcase_76 AC 1,236 ms
24,252 KB
testcase_77 AC 1,318 ms
25,008 KB
testcase_78 AC 1,191 ms
23,860 KB
testcase_79 AC 1,224 ms
23,948 KB
testcase_80 AC 1,306 ms
24,276 KB
testcase_81 AC 1,206 ms
23,940 KB
testcase_82 AC 1,161 ms
24,624 KB
testcase_83 AC 1,232 ms
24,232 KB
testcase_84 AC 1,241 ms
24,556 KB
testcase_85 AC 1,275 ms
24,300 KB
testcase_86 AC 1,315 ms
24,892 KB
testcase_87 AC 1,176 ms
23,984 KB
testcase_88 AC 1,318 ms
24,568 KB
testcase_89 AC 1,273 ms
23,964 KB
testcase_90 AC 1,251 ms
24,340 KB
testcase_91 AC 1,309 ms
24,660 KB
testcase_92 AC 1,078 ms
24,084 KB
testcase_93 AC 1,254 ms
24,316 KB
testcase_94 AC 1,160 ms
23,664 KB
testcase_95 AC 1,250 ms
23,940 KB
testcase_96 AC 1,176 ms
24,164 KB
testcase_97 AC 1,148 ms
24,232 KB
testcase_98 AC 1,238 ms
24,612 KB
testcase_99 AC 1,269 ms
24,800 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 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;
}
0