結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
24,336 KB
testcase_01 AC 66 ms
24,324 KB
testcase_02 AC 65 ms
23,388 KB
testcase_03 AC 65 ms
23,628 KB
testcase_04 AC 67 ms
24,324 KB
testcase_05 AC 66 ms
24,408 KB
testcase_06 AC 68 ms
23,544 KB
testcase_07 AC 66 ms
23,556 KB
testcase_08 AC 67 ms
23,520 KB
testcase_09 AC 66 ms
23,820 KB
testcase_10 AC 75 ms
24,324 KB
testcase_11 AC 66 ms
23,412 KB
testcase_12 AC 66 ms
24,360 KB
testcase_13 AC 66 ms
23,400 KB
testcase_14 AC 65 ms
23,376 KB
testcase_15 AC 66 ms
23,652 KB
testcase_16 AC 65 ms
23,820 KB
testcase_17 AC 67 ms
23,532 KB
testcase_18 AC 65 ms
23,424 KB
testcase_19 AC 66 ms
24,252 KB
testcase_20 AC 66 ms
23,652 KB
testcase_21 AC 66 ms
23,664 KB
testcase_22 AC 64 ms
23,820 KB
testcase_23 AC 65 ms
23,664 KB
testcase_24 AC 66 ms
24,348 KB
testcase_25 AC 40 ms
24,408 KB
testcase_26 AC 78 ms
23,628 KB
testcase_27 AC 65 ms
24,048 KB
testcase_28 AC 65 ms
23,640 KB
testcase_29 AC 66 ms
23,376 KB
testcase_30 AC 73 ms
24,360 KB
testcase_31 AC 65 ms
24,036 KB
testcase_32 AC 65 ms
23,664 KB
testcase_33 AC 66 ms
24,264 KB
testcase_34 AC 65 ms
24,336 KB
testcase_35 AC 64 ms
23,700 KB
testcase_36 AC 66 ms
24,036 KB
testcase_37 AC 65 ms
24,036 KB
testcase_38 AC 70 ms
24,036 KB
testcase_39 AC 64 ms
23,520 KB
testcase_40 AC 65 ms
23,388 KB
testcase_41 AC 66 ms
23,424 KB
testcase_42 AC 67 ms
23,832 KB
testcase_43 AC 65 ms
23,400 KB
testcase_44 AC 65 ms
24,252 KB
testcase_45 AC 66 ms
24,324 KB
testcase_46 AC 66 ms
23,400 KB
testcase_47 AC 65 ms
24,372 KB
testcase_48 AC 64 ms
23,832 KB
testcase_49 AC 64 ms
24,012 KB
testcase_50 AC 65 ms
23,652 KB
testcase_51 AC 65 ms
23,832 KB
testcase_52 AC 64 ms
24,048 KB
testcase_53 AC 65 ms
24,264 KB
testcase_54 AC 64 ms
23,640 KB
testcase_55 AC 65 ms
23,856 KB
testcase_56 AC 74 ms
23,664 KB
testcase_57 AC 64 ms
24,036 KB
testcase_58 AC 65 ms
23,844 KB
testcase_59 AC 65 ms
24,036 KB
testcase_60 AC 65 ms
24,372 KB
testcase_61 AC 64 ms
24,240 KB
testcase_62 AC 65 ms
23,544 KB
testcase_63 AC 72 ms
24,324 KB
testcase_64 AC 65 ms
24,048 KB
testcase_65 AC 65 ms
23,832 KB
testcase_66 AC 65 ms
23,628 KB
testcase_67 AC 65 ms
23,364 KB
testcase_68 AC 65 ms
24,252 KB
testcase_69 AC 64 ms
23,544 KB
testcase_70 AC 74 ms
24,036 KB
testcase_71 AC 66 ms
23,664 KB
testcase_72 AC 65 ms
24,024 KB
testcase_73 AC 65 ms
23,388 KB
testcase_74 AC 65 ms
23,412 KB
testcase_75 AC 65 ms
23,688 KB
testcase_76 AC 75 ms
23,820 KB
testcase_77 AC 66 ms
23,832 KB
testcase_78 AC 64 ms
24,384 KB
testcase_79 AC 66 ms
24,348 KB
testcase_80 AC 65 ms
23,640 KB
testcase_81 AC 65 ms
23,556 KB
testcase_82 AC 66 ms
23,640 KB
testcase_83 AC 78 ms
23,856 KB
testcase_84 AC 65 ms
23,424 KB
testcase_85 AC 65 ms
24,360 KB
testcase_86 AC 65 ms
23,412 KB
testcase_87 AC 65 ms
24,024 KB
testcase_88 AC 65 ms
24,024 KB
testcase_89 AC 65 ms
23,424 KB
testcase_90 AC 64 ms
23,412 KB
testcase_91 AC 66 ms
23,544 KB
testcase_92 AC 86 ms
23,244 KB
testcase_93 AC 65 ms
23,664 KB
testcase_94 AC 65 ms
24,276 KB
testcase_95 AC 65 ms
24,036 KB
testcase_96 AC 66 ms
24,012 KB
testcase_97 AC 65 ms
23,844 KB
testcase_98 AC 65 ms
24,348 KB
testcase_99 AC 75 ms
24,264 KB
権限があれば一括ダウンロードができます

ソースコード

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