結果

問題 No.5017 Tool-assisted Shooting
ユーザー matsup10matsup10
提出日時 2023-07-16 22:07:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 4,802 bytes
コンパイル時間 8,176 ms
コンパイル使用メモリ 330,492 KB
実行使用メモリ 24,324 KB
スコア 300,496
平均クエリ数 293.29
最終ジャッジ日時 2023-07-16 22:08:09
合計ジャッジ時間 15,084 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
24,300 KB
testcase_01 AC 39 ms
23,868 KB
testcase_02 AC 33 ms
23,940 KB
testcase_03 AC 31 ms
23,736 KB
testcase_04 AC 36 ms
24,324 KB
testcase_05 AC 40 ms
23,448 KB
testcase_06 AC 70 ms
23,340 KB
testcase_07 AC 33 ms
23,568 KB
testcase_08 AC 35 ms
23,460 KB
testcase_09 AC 31 ms
24,180 KB
testcase_10 AC 31 ms
23,340 KB
testcase_11 AC 33 ms
23,640 KB
testcase_12 AC 31 ms
23,460 KB
testcase_13 AC 38 ms
23,928 KB
testcase_14 AC 40 ms
23,400 KB
testcase_15 AC 38 ms
24,096 KB
testcase_16 AC 40 ms
23,736 KB
testcase_17 AC 40 ms
23,304 KB
testcase_18 AC 63 ms
24,228 KB
testcase_19 AC 47 ms
24,060 KB
testcase_20 AC 41 ms
23,736 KB
testcase_21 AC 37 ms
23,676 KB
testcase_22 AC 38 ms
23,688 KB
testcase_23 AC 72 ms
23,520 KB
testcase_24 AC 44 ms
24,240 KB
testcase_25 AC 72 ms
24,300 KB
testcase_26 AC 37 ms
23,580 KB
testcase_27 AC 47 ms
23,292 KB
testcase_28 AC 36 ms
24,072 KB
testcase_29 AC 31 ms
23,880 KB
testcase_30 AC 71 ms
23,748 KB
testcase_31 AC 31 ms
24,240 KB
testcase_32 AC 42 ms
23,292 KB
testcase_33 AC 33 ms
24,048 KB
testcase_34 AC 31 ms
23,892 KB
testcase_35 AC 41 ms
23,424 KB
testcase_36 AC 37 ms
23,568 KB
testcase_37 AC 32 ms
23,328 KB
testcase_38 AC 33 ms
23,292 KB
testcase_39 AC 31 ms
23,676 KB
testcase_40 AC 54 ms
24,048 KB
testcase_41 AC 39 ms
23,328 KB
testcase_42 AC 35 ms
23,508 KB
testcase_43 AC 49 ms
23,328 KB
testcase_44 AC 40 ms
23,652 KB
testcase_45 AC 31 ms
23,412 KB
testcase_46 AC 31 ms
23,688 KB
testcase_47 AC 45 ms
23,652 KB
testcase_48 AC 36 ms
23,424 KB
testcase_49 AC 72 ms
24,168 KB
testcase_50 AC 32 ms
24,300 KB
testcase_51 AC 37 ms
23,520 KB
testcase_52 AC 33 ms
23,544 KB
testcase_53 AC 32 ms
24,108 KB
testcase_54 AC 46 ms
23,928 KB
testcase_55 AC 30 ms
23,904 KB
testcase_56 AC 39 ms
24,192 KB
testcase_57 AC 71 ms
23,412 KB
testcase_58 AC 30 ms
24,312 KB
testcase_59 AC 31 ms
23,856 KB
testcase_60 AC 30 ms
23,748 KB
testcase_61 AC 47 ms
23,436 KB
testcase_62 AC 40 ms
23,652 KB
testcase_63 AC 43 ms
23,664 KB
testcase_64 AC 39 ms
23,412 KB
testcase_65 AC 41 ms
24,216 KB
testcase_66 AC 33 ms
23,328 KB
testcase_67 AC 46 ms
23,736 KB
testcase_68 AC 50 ms
23,448 KB
testcase_69 AC 36 ms
23,424 KB
testcase_70 AC 38 ms
23,916 KB
testcase_71 AC 46 ms
23,892 KB
testcase_72 AC 32 ms
24,288 KB
testcase_73 AC 37 ms
24,036 KB
testcase_74 AC 32 ms
24,108 KB
testcase_75 AC 31 ms
23,460 KB
testcase_76 AC 72 ms
24,000 KB
testcase_77 AC 50 ms
23,328 KB
testcase_78 AC 46 ms
23,340 KB
testcase_79 AC 37 ms
23,424 KB
testcase_80 AC 53 ms
23,436 KB
testcase_81 AC 35 ms
23,760 KB
testcase_82 AC 54 ms
23,412 KB
testcase_83 AC 35 ms
23,916 KB
testcase_84 AC 72 ms
23,304 KB
testcase_85 AC 31 ms
23,412 KB
testcase_86 AC 48 ms
23,652 KB
testcase_87 AC 37 ms
24,060 KB
testcase_88 AC 43 ms
23,508 KB
testcase_89 AC 38 ms
23,508 KB
testcase_90 AC 30 ms
23,460 KB
testcase_91 AC 36 ms
24,084 KB
testcase_92 AC 54 ms
24,048 KB
testcase_93 AC 45 ms
23,292 KB
testcase_94 AC 38 ms
23,424 KB
testcase_95 AC 32 ms
23,940 KB
testcase_96 AC 38 ms
23,880 KB
testcase_97 AC 41 ms
24,060 KB
testcase_98 AC 71 ms
23,688 KB
testcase_99 AC 43 ms
23,892 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/extc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=a;i<=int(b);i++)
#define ALL(x) x.begin(),x.end()
#define INF INT_MAX
#define INFL LLONG_MAX / 4
using namespace atcoder;
using mint = modint998244353;
template<typename T> void chmin(T& a, T b) { a = min(a, b); }
template<typename T> void chmax(T& a, T b) { a = max(a, b); }
#define PR(x) cerr << #x << "=" << x << endl
using i128 = __int128_t;

int main_proc() {
  // h, p

  int score = 0;
  vector f(1100, vector<pair<int, int>>(25));
  vector f_(1100, vector<pair<int, int>>(25));
  vector<queue<int>> opp_ys(25);
  int new_opp_y = 59;
  int pow_sum = 0;
  int pos_x = 12;
  auto get_lv = [&]() {
    return 1 + pow_sum / 100;
  };

  auto valid = [&](int pos_y, char to) -> bool {
    if(to == 'L') {
      return f[pos_y+1][(pos_x+24)%25].first == 0 && f[pos_y][(pos_x+24)%25].first == 0;
    } else if(to == 'R') {
      // PR(f[pos_y+2][(pos_x+1)%25].first);
      return f[pos_y+1][(pos_x+1)%25].first == 0 && f[pos_y][(pos_x+1)%25].first == 0;
    } else {
      // PR(f[pos_y+1][pos_x].first);
      return f[pos_y+1][pos_x].first == 0;
    }
  };

  REP(pos_y, 1000) {
    // PR(pos_y);
    PR(pos_x);
    int n;
    cin >> n;
    if(n == -1) return 0;
    REP(i, n) {
      int h, p, x;
      cin >> h >> p >> x;
      f[new_opp_y][x] = {h, p};
      f_[new_opp_y][x] = {h, p};
      opp_ys[x].push(new_opp_y);
    }
    new_opp_y++;

    vector<int> min_reach_turns(25, 1000);
    min_reach_turns[pos_x] = 1;
    REP(pm, 2){ 
      int now_pos_y = pos_y;
      FOR(i, 1, 24) {
        int offset = pm ? i : 25-i;
        int new_pos_x = (pos_x + offset) % 25;
        now_pos_y++;
        // PR(now_pos_y);
        // PR(new_pos_x);
        while(f[now_pos_y][new_pos_x].first && f[now_pos_y+1][new_pos_x].first) {
          now_pos_y++;
        }
        chmin(min_reach_turns[new_pos_x], now_pos_y - pos_y);
      } 
    }
    
    int min_req_turn = 1000;
    char next_to = 'S';
    
    REP(x, 25) {
      if(opp_ys[x].empty()) continue;
      int now_opp_y = opp_ys[x].front();

      int req_turn = f[now_opp_y][x].first / get_lv() + min_reach_turns[x] - 1;
      if(req_turn + pos_y >= now_opp_y) continue;
      if(min_req_turn > req_turn) {
        
        if(pos_x == x) {
          next_to = 'S';
        }
        if(abs(pos_x - x) < 13) {
          if(pos_x < x) next_to = 'R';
          if(pos_x > x) next_to = 'L';
        } else {
          if(pos_x < x) next_to = 'L';
          if(pos_x > x) next_to = 'R';
        }
        min_req_turn = req_turn;
      }
    }

    if(valid(pos_y, next_to)) {
      // PR(pos_y);
      // PR(pos_x);
      
      if(next_to == 'L') pos_x = (pos_x + 24) % 25;
      if(next_to == 'R') pos_x = (pos_x + 1) % 25;
    } else if (valid(pos_y, 'S')) {
      next_to = 'S';
      // PR(pos_y);
      // PR(pos_x);
      // PR(min_req_turn);
    } else if (valid(pos_y, 'R')) {
      pos_x = (pos_x + 1) % 25;
      next_to = 'R';
    } else {
      pos_x = (pos_x + 24) % 25;
      next_to = 'L';
    }

    // if(pos_y > 100) break;

    if(opp_ys[pos_x].size()) {
      f[opp_ys[pos_x].front()][pos_x].first-=get_lv();
      if(f[opp_ys[pos_x].front()][pos_x].first <= 0) {
        score += f_[opp_ys[pos_x].front()][pos_x].first;
        pow_sum += f[opp_ys[pos_x].front()][pos_x].second;
        f[opp_ys[pos_x].front()][pos_x] = {0, 0};
        opp_ys[pos_x].pop();
      }
    }
    REP(i, 25) {
      if(opp_ys[i].front() == pos_y) opp_ys[i].pop();
    }
    cout << next_to << endl;
    
  }

  PR(score);
  return 0;
}

void test1(int dn) {
  string fn = "/Users/tm/Desktop/atcoder/yukicoder/yukicoder_9774/yukicoder_9774/tools/in/00";
  if(dn<10) fn += '0';
  fn += to_string(dn);
  fn += ".txt";
  ifstream in(fn);
  cin.rdbuf(in.rdbuf());

  string fno = "/Users/tm/Desktop/atcoder/yukicoder/yukicoder_9774/yukicoder_9774/Visualizer_for_Mac/input.txt";
  ofstream out(fno);
  std::streambuf* strbuf = cout.rdbuf(out.rdbuf());
  REP(i, 10000) {
    if (cin.fail()) break;
    int s;
    if(i < 25) {
      cin >> s;
      cout << s << ' ';
    } else {
      if(i == 25) cout << endl;
      cin >> s;
      cout << s << endl;
      REP(j, s) {
        REP(k, 3) {
          int x;
          cin >> x; 
          cout << x << ' ';
        }
        cout << endl;
      }
    }
  }

  in = ifstream(fn);
  cin.rdbuf(in.rdbuf());

  fno = "/Users/tm/Desktop/atcoder/yukicoder/yukicoder_9774/yukicoder_9774/Visualizer_for_Mac/output.txt";
  out = ofstream(fno);
  vector<int> p(25);
  REP(i, 25) cin >> p[i];
  main_proc();
  std::cout.rdbuf(strbuf);
  
  return;
}

void test() {
  REP(i, 10) test1(i);
}

int main() {

  // test1(0);
  main_proc();
  return 0;
}
0