結果

問題 No.5017 Tool-assisted Shooting
ユーザー nikaj
提出日時 2023-07-16 16:47:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 5,554 bytes
コンパイル時間 1,214 ms
コンパイル使用メモリ 149,764 KB
実行使用メモリ 24,408 KB
スコア 4,169,524
平均クエリ数 993.68
最終ジャッジ日時 2023-07-16 16:48:14
合計ジャッジ時間 12,716 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

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; }

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];

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;
        }


        bool stay = false;
        pii t(-1, -1);
        if (hp[0][X] > 0) {
            cerr << "Dead at " << turn << endl;
            break;
        }
        newX = X;
        ans = "S";
        double 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";
                }
            }
            t = pii(i, X);
            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;
                }
            }
        }
        if (DBG) cerr << bv << " " << ans << endl;
        X = newX;
        for (int i = 1; i < H; i++) if (hp[i][X] > 0) {
            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