結果

問題 No.5017 Tool-assisted Shooting
ユーザー ss
提出日時 2023-07-16 19:33:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 13,577 bytes
コンパイル時間 1,942 ms
コンパイル使用メモリ 182,012 KB
実行使用メモリ 24,396 KB
スコア 3,883,310
平均クエリ数 1001.00
最終ジャッジ日時 2023-07-16 19:33:56
合計ジャッジ時間 13,138 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#ifndef __UTIL__
#define __UTIL__
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
// Debug
template<class T>
void print_collection(std::ostream& out, T const& x);
template<class A>
std::ostream& operator<<(std::ostream& out, std::vector<A> const& x) { print_collection(out, x); return out; }
template<class A, size_t N>
std::ostream& operator<<(std::ostream& out, std::array<A, N> const& x) { print_collection(out, x); return out; }
template<class A>
std::ostream& operator<<(std::ostream& out, std::set<A> const& x) { print_collection(out, x); return out; }
template<class A>
std::ostream& operator<<(std::ostream& out, std::unordered_set<A> const& x) { print_collection(out, x); return out; }
template<class A, class B>
std::ostream& operator<<(std::ostream& out, std::map<A, B> const& x) { print_collection(out, x); return out; }
template<class A, class B>
std::ostream& operator<<(std::ostream& out, std::pair<A, B> const& x) {
  out << '(';
  out << x.first;
  out << ',';
  out << x.second;
  out << ')';
  return out;
}
template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>);
template<class... A>
std::ostream& operator<<(std::ostream& out, std::tuple<A...> const& x) {
  print_tuple(out, x, std::index_sequence_for<A...>{});
  return out;
}
template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>){
  using swallow = int[];
  out << '(';
  (void)swallow{0, (void(out << (I == 0? "" : ", ") << std::get<I>(a)), 0)...};
  out << ')';
}
template<class T>
void print_collection(std::ostream& out, T const& x) {
  int f = 0;
  out << '[';
  for(auto const& i: x) {
    out << (f++ ? "," : "");
    out << i;
  }
  out << "]";
}
static inline void d1_impl_seq() { std::cerr << "}"; }
template <class T, class... V>
void d1_impl_seq(T const& t, V const&... v) {
  std::cerr << t;
  if(sizeof...(v)) { std::cerr << ", "; }
  d1_impl_seq(v...);
}
static inline void d2_impl_seq() { }
template <class T, class... V>
void d2_impl_seq(T const& t, V const&... v) {
  std::cerr << " " << t;
  d2_impl_seq(v...);
}
#define D0(x) do { std::cerr << __FILE__ ":" << __LINE__ << ":" << __func__ <<  " " << x << std::endl; } while (0)
// #ifdef DEBUG
#define D1(x...) do {                                         \
    std::cerr << __LINE__ << "  {" << #x << "} = {";  \
    d1_impl_seq(x);                                           \
    std::cerr << std::endl << std::flush;                     \
  } while(0)
// #else
// #define D1(x...) {}
// #endif
#define D2(x...) do {                     \
    std::cerr << "!";                     \
    d2_impl_seq(x);                       \
    std::cerr << std::endl << std::flush; \
  } while(0)
using namespace std;
static constexpr int INF = 1<<30;
// #define NDEBUG
static std::vector<std::string> split(const std::string &s, char delim) {
  std::vector<std::string> elems;
  std::stringstream ss(s);
  std::string item;
  while (getline(ss, item, delim)) {
    if (!item.empty()) {
      elems.push_back(item);
    }
  }
  return elems;
}
struct XorShift {
  unsigned int x, y, z, w;
  double nL[65536];
  XorShift() { init(); }
  void init()
  {
    x = 314159265; y = 358979323; z = 846264338; w = 327950288;
    double n = 1 / (double)(2 * 65536);
    for (int i = 0; i < 65536; i++) {
      nL[i] = log(((double)i / 65536) + n);
    }
  }
  inline unsigned int next() { unsigned int t=x^x<<11; x=y; y=z; z=w; return w=w^w>>19^t^t>>8; }
  inline double nextLog() { return nL[next()&0xFFFF]; }
  inline int nextInt(int m) { return (int)(next()%m); } // [0, m)
  int nextInt(int min, int max) { return min+nextInt(max-min+1); } // [min, max]
  inline double nextDouble() { return (double)next()/((long long)1<<32); } // [0, 1]
};
XorShift rng;
template <typename T>
inline void rough_shuffle(vector<T>& lv) {
    int n = lv.size();
    for (int i = n; i > 0; --i) {
        int id = rng.nextInt(i);
        swap(lv[id], lv[i-1]);
    }
}
std::size_t calc_hash(std::vector<int> const& vec) {
  std::size_t seed = vec.size();
  for(auto& i : vec) {
    seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}
struct Timer {
  double LIMIT; // FIXME: 時間制限(s)
  Timer() : LIMIT(0.95) { reset(); }
  Timer(double limit) : LIMIT(limit) { reset(); }
    chrono::system_clock::time_point start;
    void reset() {
        start = chrono::system_clock::now();
    }
 
    double get() {
        auto end = chrono::system_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(end - start).count()/1000.0;
    }
};
namespace atcoder {
// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }
    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }
    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }
    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }
    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }
    std::vector<int> groups(int a) {
      // aと同じgroupに属する頂点のリストを返す
      std::vector<int> result;
      for (int i = 0; i < _n; ++i) {
        if (leader(a) != leader(i)) continue;
        result.push_back(i);
      }
      return result;
    }
  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};
}  // namespace atcoder
#endif
// #pragma GCC optimize("O3")
// #include "util/marathon/pos.hpp"
using namespace std;
int DX[9] = {0, 1, 0, -1, -1, -1, 1, 1, 0};
int DY[9] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
namespace pos {
    int W = 0, H = 0; // xとyのサイズ
    static constexpr int UP = 0;
    static constexpr int RIGHT = 1;
    static constexpr int DOWN = 2;
    static constexpr int LEFT = 3;
    bool isOrthogonal(int d1, int d2) {
      // UP, RIGHT, DOWN, LEFTのdir同士が直行しているか
      assert (0 <= d1 && d1 <= 3);
      assert (0 <= d2 && d2 <= 3);
      return (d1+d2) % 2;
    }
}
struct Pos {
  int x = -1, y = -1;
  Pos() {}
  Pos(int i): x(i%pos::W), y(i/pos::W) {}
  Pos(int x, int y): x(x), y(y) {}
  bool operator == (const Pos &other) const { 
    return (other.x == x) && (other.y == y);
  }
  bool operator != (const Pos &other) const { 
    return !((*this) == other);
  }
  int euclid(const Pos &other) const {
    return sqrt((x-other.x)*(x-other.x)+(y-other.y)*(y-other.y));
  }
  int manhattan(const Pos &other) const {
    return abs(x-other.x)+abs(y-other.y);
  }
  Pos to(int d) const { return Pos(x+DX[d],y+DY[d]); }
  int id() const { return y*pos::W+x; }
  bool outside() const {
    return x < 0 || x >= pos::W || y < 0 || y >= pos::H;
  }
  friend std::ostream& operator<<(std::ostream& os, const Pos &p) {
    os << '(' << p.x << ',' << p.y << ')';
    return os;
  }
};
namespace pos {
    Pos nullpos;
}
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using pii = pair<int, int>;
static constexpr int W = 25;
static constexpr int H = 60;
int turn_ = 0;
int LEFT = -1;
int STAY = 0;
int RIGHT = 1;
map<int, char> dir2char_ = {
  {-1,'L'},
  {0,'S'},
  {1,'R'},
};
namespace util {
  int getLDist(int fromx, int tox) {
    // 左方向の距離
    int dist = fromx-tox;
    if (dist < 0) dist += W;
    return dist;
  }
  int getRDist(int fromx, int tox) {
    int dist = tox-fromx;
    if (dist < 0) dist += W;
    return dist;
  }
  int to(int fromx, int tox) {
    if (fromx == tox) return STAY;
    int l = getLDist(fromx,tox);
    int r = getRDist(fromx,tox);
    if (l <= r) return LEFT;
    else return RIGHT;
  }
  Pos to(Pos p, int dir) {
    if (dir == LEFT) return Pos((p.x+W-1)%W, p.y+1);
    if (dir == STAY) return Pos(p.x, p.y+1);
    if (dir == RIGHT) return Pos((p.x+1)%W, p.y+1);
    assert(false);
  }
}
struct Enemy {
  int inithp = 0, hp = 0, power = -1;
  Enemy() {}
  Enemy(int h, int p): inithp(h), hp(h), power(p) {}
  int get_turn_to_kill(int level) {
    return (hp + level - 1) / level;
  }
  friend std::ostream& operator<<(std::ostream& os, const Enemy &e) {
    os << "[E]";
    os << "inithp = " << e.inithp;
    os << ",hp = " << e.hp;
    os << ",power = " << e.power;
    return os;
  }
};
using FieldType = array<array<Enemy, H>, W>; 
struct Field {
  int me = 12; // x座標
  int level = 1;
  int power_ = 0;
  FieldType arr;
  void step(int dir) {
    // 移動
    me += dir;
    if (me < 0) me += W;
    if (me >= W) me -= W;
    
    int y = getY(me);
    if (y != H) {
      arr[me][y].hp -= level;
      // 殺した敵を削除
      if (arr[me][y].hp <= 0) {
        power_ += arr[me][y].power;
        assert(power_ >= 0);
        arr[me][y] = Enemy();
      }
    }
    level = 1 + power_ / 100;
    assert(level > 0);
    REP(x,W) {
      REP3(y,1,H) {
        arr[x][y-1] = arr[x][y];
      }
      arr[x][H-1] = Enemy();
    }
  }
  bool exists(const Pos &p) const { return arr[p.x][p.y].power >= 0; }
  void setEnemy(int x, int hp, int power) {
    arr[x][H-1] = Enemy(hp, power);
  }
  friend std::ostream& operator<<(std::ostream& os, const Field &f) {
    REP(x,W) {
      REP(y,H) {
        int hp = f.arr[x][y].hp;
        if (hp >= 100) os << hp/100 << '+';
        else {
          os << hp;
          if (hp < 10) os << ' ';
        }
      }
      os << '\n';
    }
    return os;
  }
  int getY(int x) { // 一番近い敵のy座標
    REP(y,H) {
      if (exists(Pos(x,y))) return y;
    }
    return H;
  }
};
Field field_;
double BAD = -1000000000;
struct State {
  Field field;
  double evaluateKillEnemy(int x) {
    // xにいる一番近い敵を殺した場合の良さを計算
    // 高いほど良い
    int me = field.me;
    double ret = 0;
    int l = util::getLDist(me, x);
    int r = util::getRDist(me, x);
    int dir = util::to(me, x);
    int turn_to_reach = min(l, r);
    if (turn_to_reach == 0) turn_to_reach = 1;
    Pos p(me,0);
    REP(i,turn_to_reach) {
      Pos np = util::to(p,dir);
      Pos np2 = Pos(np.x,np.y+1);
      // D1(me,x,np,turn_to_reach);
      // D1(np);
      if (field.exists(np) || field.exists(np2)) {
        // D1(turn_,me,np,x);
        return -4; // 移動中に敵にぶつかって死ぬ
      }
      p = np;
    }
    int y = field.getY(x);
    if (y == H) {
      return -1; // 敵がいない
    }
    if (y-turn_to_reach <= 1) return -2; // 先に敵がいなくなる
    Enemy enemy = field.arr[x][y];
    int damage = (y-turn_to_reach-1)*field.level;
    if (damage < enemy.hp) return -3; // 敵を殺しきれない
    int turn_to_kill = enemy.get_turn_to_kill(field.level);
    return (double)enemy.power/(turn_to_kill+turn_to_reach);
  }
};
bool readInput() {
  int n;
  std::cin >> n;
  if(n == -1) return true;
  if (n >= W) return true;
  assert(n < W);
  for(int i = 0; i < n; i++) {
    int h, p, x;
    std::cin >> h >> p >> x;
    // D1(n, h, p, x);
    field_.setEnemy(x, h, p);
  }
  return false;
}
void writeOutput(int dir) {
  cout << dir2char_[dir] << endl;
}
void test () {
  D1(util::to(10,10));
  D1(util::to(10,11));
  D1(util::to(11,10));
  D1(util::to(1,23));
  D1(util::to(23,1));
}
int solve (int turn) {
  State s;
  s.field = field_;
  double best = BAD;
  int bestx = -1;
  REP(x,W) {
    double score = s.evaluateKillEnemy(x);
    // D1(turn, x, score);
    if (score > best) {
      bestx = x;
      best = score;
    }
  }
  // D1(turn,s.field.level,s.field.me,bestx,best,s.field.getY(bestx));
  // cerr << s.field;
  // output
  int dir = STAY;
  if (bestx != -1) {
    dir = util::to(s.field.me, bestx);
  }
  return dir;
}
int main() 
{
  pos::W = 25; pos::H = 60;
#ifdef LOCAL
  std::string s;
  getline(cin,s);
#endif
  writeOutput(STAY);
  REP(turn,1000) {
    turn_ ++;
    if (readInput()) return 0;
    int dir = solve(turn);
    field_.step(dir);
    writeOutput(dir);
    // if (turn > 0) return 0;
    // if (turn > 284) return 0;
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0