結果

問題 No.5017 Tool-assisted Shooting
ユーザー bowwowforeachbowwowforeach
提出日時 2023-07-16 18:53:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,615 ms / 2,000 ms
コード長 35,284 bytes
コンパイル時間 4,699 ms
コンパイル使用メモリ 242,184 KB
実行使用メモリ 24,444 KB
スコア 4,072,131
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-16 18:58:34
合計ジャッジ時間 143,564 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,322 ms
24,148 KB
testcase_01 AC 1,493 ms
23,424 KB
testcase_02 AC 1,068 ms
24,276 KB
testcase_03 AC 1,242 ms
23,544 KB
testcase_04 AC 1,241 ms
24,384 KB
testcase_05 AC 1,278 ms
23,424 KB
testcase_06 AC 1,317 ms
24,312 KB
testcase_07 AC 1,335 ms
23,976 KB
testcase_08 AC 1,266 ms
24,384 KB
testcase_09 AC 1,261 ms
24,384 KB
testcase_10 AC 1,368 ms
23,628 KB
testcase_11 AC 1,154 ms
23,452 KB
testcase_12 AC 1,146 ms
23,364 KB
testcase_13 AC 1,316 ms
23,340 KB
testcase_14 AC 1,390 ms
23,476 KB
testcase_15 AC 1,364 ms
23,844 KB
testcase_16 AC 1,326 ms
23,328 KB
testcase_17 AC 1,303 ms
23,964 KB
testcase_18 AC 1,392 ms
23,976 KB
testcase_19 AC 1,388 ms
23,960 KB
testcase_20 AC 1,281 ms
24,300 KB
testcase_21 AC 1,400 ms
23,316 KB
testcase_22 AC 1,138 ms
24,060 KB
testcase_23 AC 1,247 ms
24,152 KB
testcase_24 AC 1,351 ms
24,288 KB
testcase_25 AC 1,414 ms
23,532 KB
testcase_26 AC 1,132 ms
23,664 KB
testcase_27 AC 1,321 ms
23,592 KB
testcase_28 AC 1,407 ms
23,856 KB
testcase_29 AC 1,142 ms
24,048 KB
testcase_30 AC 1,103 ms
24,048 KB
testcase_31 AC 1,210 ms
23,328 KB
testcase_32 AC 1,412 ms
23,436 KB
testcase_33 AC 1,414 ms
24,384 KB
testcase_34 AC 1,297 ms
23,544 KB
testcase_35 AC 1,218 ms
23,424 KB
testcase_36 AC 1,181 ms
23,544 KB
testcase_37 AC 1,268 ms
23,708 KB
testcase_38 AC 1,429 ms
23,760 KB
testcase_39 AC 1,344 ms
24,000 KB
testcase_40 AC 1,362 ms
23,544 KB
testcase_41 AC 1,324 ms
24,336 KB
testcase_42 AC 1,397 ms
23,484 KB
testcase_43 AC 1,235 ms
23,436 KB
testcase_44 AC 1,399 ms
23,812 KB
testcase_45 AC 1,336 ms
23,444 KB
testcase_46 AC 1,493 ms
23,904 KB
testcase_47 AC 1,114 ms
23,472 KB
testcase_48 AC 1,419 ms
23,628 KB
testcase_49 AC 1,269 ms
23,964 KB
testcase_50 AC 1,334 ms
24,060 KB
testcase_51 AC 1,314 ms
23,988 KB
testcase_52 AC 1,437 ms
24,444 KB
testcase_53 AC 1,379 ms
24,012 KB
testcase_54 AC 1,321 ms
24,000 KB
testcase_55 AC 1,201 ms
23,772 KB
testcase_56 AC 1,313 ms
23,388 KB
testcase_57 AC 1,171 ms
24,300 KB
testcase_58 AC 1,331 ms
24,444 KB
testcase_59 AC 1,431 ms
23,364 KB
testcase_60 AC 1,316 ms
24,336 KB
testcase_61 AC 1,248 ms
24,312 KB
testcase_62 AC 1,237 ms
23,604 KB
testcase_63 AC 1,369 ms
24,084 KB
testcase_64 AC 1,266 ms
24,372 KB
testcase_65 AC 1,615 ms
23,484 KB
testcase_66 AC 1,435 ms
23,364 KB
testcase_67 AC 1,301 ms
24,300 KB
testcase_68 AC 1,293 ms
23,664 KB
testcase_69 AC 1,375 ms
23,784 KB
testcase_70 AC 1,385 ms
23,832 KB
testcase_71 AC 1,416 ms
23,784 KB
testcase_72 AC 1,079 ms
23,964 KB
testcase_73 AC 1,384 ms
23,412 KB
testcase_74 AC 1,074 ms
23,988 KB
testcase_75 AC 1,327 ms
24,216 KB
testcase_76 AC 1,278 ms
24,324 KB
testcase_77 AC 1,456 ms
24,012 KB
testcase_78 AC 1,335 ms
23,496 KB
testcase_79 AC 1,251 ms
24,324 KB
testcase_80 AC 1,470 ms
24,000 KB
testcase_81 AC 1,355 ms
24,000 KB
testcase_82 AC 1,278 ms
23,484 KB
testcase_83 AC 1,176 ms
23,484 KB
testcase_84 AC 1,273 ms
23,832 KB
testcase_85 AC 1,372 ms
23,964 KB
testcase_86 AC 1,297 ms
23,412 KB
testcase_87 AC 1,329 ms
24,000 KB
testcase_88 AC 1,437 ms
23,412 KB
testcase_89 AC 1,440 ms
24,288 KB
testcase_90 AC 1,436 ms
23,664 KB
testcase_91 AC 1,518 ms
23,496 KB
testcase_92 AC 1,310 ms
23,556 KB
testcase_93 AC 1,411 ms
24,060 KB
testcase_94 AC 1,070 ms
24,264 KB
testcase_95 AC 1,353 ms
23,784 KB
testcase_96 AC 1,369 ms
24,184 KB
testcase_97 AC 1,307 ms
23,988 KB
testcase_98 AC 1,367 ms
23,436 KB
testcase_99 AC 1,272 ms
24,360 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:409:22: 警告: class ‘CapArr<T, CAP>’ is implicitly friends with itself
  409 |         friend class CapArr;
      |                      ^~~~~~

ソースコード

diff #

#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 0
#define UNIT_TEST 0

#define TIME_LIMIT (1970)

#define NOT_SUBMIT 0
#define VALIDATION 0

#define IO_FILE 0

#define OUTPUT_INFO 0
#define OUTPUT_FINAL_INFO 1
#define OUTPUT_LOG 0
#define OUTPUT_VISUAL 0

#define FIX_RESULT 0



#define TIME_LIMIT_US (TIME_LIMIT * 1000)

#ifdef __clang_version__
#pragma clang diagnostic ignored "-Wunknown-pragmas"
#pragma clang diagnostic ignored "-Wunknown-warning-option"
#pragma clang diagnostic ignored "-Wmissing-braces"
#endif


#ifndef _MSC_VER
#pragma GCC target ("avx2")
#pragma GCC optimize "O3,omit-frame-pointer,inline"
#pragma GCC optimize ("unroll-loops")

#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-function"
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#endif

#define _USE_MATH_DEFINES
#ifdef __clang_version__

#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <cfenv>
#include <cinttypes>
#include <cstdint>
#include <cwchar>
#include <cwctype>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

#else
#include <bits/stdc++.h>
#endif

using namespace std;


#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i)
#define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i)


#define ALL(x) (x).begin(),(x).end()

template <class T, class U> inline void chmin(T& a, U&& b) { if (b < a) { a = b; } }
template <class T, class U> inline void chmax(T& a, U&& b) { if (a < b) { a = b; } }
template <class T, class U, class V> inline void clip(T& v, U&& lower, V&& upper) {
	if (v < lower) { v = lower; }
	else if (v > upper) { v = upper; }
}
template <class T> inline constexpr T square(T v) { return v * v; }

template <class T, int SIZE>
constexpr int len(const T(&)[SIZE]) { return SIZE; }

#define cauto const auto

#include <cstdint>

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using s8 = int8_t;
using s16 = int16_t;
using s32 = int32_t;
using s64 = int64_t;



using TimePoint = chrono::high_resolution_clock::time_point;

struct ChronoTimer {
private:
	TimePoint startTime_;
	TimePoint endTime_;

public:
	inline void Init() {
		startTime_ = chrono::high_resolution_clock::now();
		endTime_ = startTime_;
	}

	inline void Start(int limit) {
		endTime_ = startTime_ + chrono::milliseconds(limit);
	}
	inline void StartMs(int limit) {
		endTime_ = startTime_ + chrono::milliseconds(limit);
	}
	inline void StartUs(int limit) {
		endTime_ = startTime_ + chrono::microseconds(limit);
	}

	inline void Join() {
	}

	inline bool IsOver() const {
		return chrono::high_resolution_clock::now() >= endTime_;
	}

	inline int ElapseTimeMs() const {
		return (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - startTime_).count();
	}
	inline int ElapseTimeUs() const {
		return (int)chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - startTime_).count();
	}

	void SetElapseTimeMs(int ms) {
		auto now = chrono::high_resolution_clock::now();
		auto limit = endTime_ - startTime_;
		startTime_ = now - chrono::milliseconds(ms);
		endTime_ = startTime_ + limit;
	}

	inline int LeftToUS(const TimePoint& limit) const {
		return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::high_resolution_clock::now()).count();
	}

	inline double NowRate() const {
		return (chrono::high_resolution_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count();
	}

	inline TimePoint Now() const {
		return chrono::high_resolution_clock::now();
	}
	inline TimePoint StartTime() const {
		return startTime_;
	}
	inline TimePoint EndTime() const {
		return endTime_;
	}

	TimePoint GetLimitTimePointUs(int limit) const {
		return startTime_ + chrono::microseconds(limit);
	}
};

TimePoint Now() {
	return chrono::high_resolution_clock::now();
}


template <class T>
void InstanceRun(int argc, const char* argv[]) {
	T* m = new T;
	m->Run(argc, argv);
	quick_exit(0);
}

struct Main;

signed main(int argc, const char* argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(0);
	InstanceRun<Main>(argc, argv);
}


struct MemoryException {};


#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)


#define VABORT() VALIDATE_ABORT()
#define VASSERT(exp) VALIDATE_ASSERT(exp)






template <class A, class B>
struct pr {
	union {
		A a;
		A x;
		A first;
	};
	union {
		B b;
		B y;
		B second;
	};

	bool operator == (pr const& r) const { return a == r.a && b == r.b; }
	bool operator != (pr const& r) const { return !((*this) == r); }
	bool operator < (pr const& r) const {
		if (a == r.a) {
			return b < r.b;
		}
		return a < r.a;
	}
	bool operator > (pr const& r) const {
		return r < (*this);
	}


	pr& operator += (pr const& v) {
		a += v.a;
		b += v.b;
		return *this;
	}
	pr& operator -= (pr const& v) {
		a -= v.a;
		b -= v.b;
		return *this;
	}

	template <class C, class D>
	auto operator + (pr<C, D> const& v) const {
		return pr<decltype(a + v.a), decltype(b + v.b)>{ a + v.a, b + v.b };
	}

	template <class C, class D>
	auto operator - (pr<C, D> const& v) const {
		return pr<decltype(a - v.a), decltype(b - v.b)>{ a - v.a, b - v.b };
	}

	template <class C, class D>
	explicit operator pr<C, D>() const {
		return { C(a), D(b) };
	}

	template <class T>
	auto operator * (T const& v) const -> pr<decltype(x * v), decltype(y * v)> {
		return { x * v, y * v };
	}
	template <class T>
	auto operator / (T const& v) const -> pr<decltype(x / v), decltype(y / v)> {
		return { x / v, y / v };
	}

	template <class T>
	pr& operator *= (T const& v) {
		x *= v;
		y *= v;
		return *this;
	}
	template <class T>
	pr& operator /= (T const& v) {
		x /= v;
		y /= v;
		return *this;
	}

	pr operator -() const {
		return pr{ -x, -y };
	}

	void flip() { swap(x, y); }

	friend istream& operator>>(istream& is, pr& p) {
		is >> p.a >> p.b;
		return is;
	}
	friend ostream& operator<<(ostream& os, pr const& p) {
		os << p.a << " " << p.b;
		return os;
	}

	template <size_t I>
	auto get() const {
		if constexpr (I == 0) {
			return x;
		}
		else if constexpr (I == 1) {
			return y;
		}
	}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;

static_assert(is_trivially_copyable<pint>::value, "not trivially_copyable");

template <class A, class B>
struct tuple_size<pr<A, B>> : integral_constant<size_t, 2> {};

template <class A, class B>
struct tuple_element<0, pr<A, B>> { using type = A; };
template <class A, class B>
struct tuple_element<1, pr<A, B>> { using type = B; };

inline pdouble ToDouble(const pint& p) {
	return pdouble{ double(p.x), double(p.y) };
}
inline pint round(const pdouble& d) {
	return pint{ (int)round(d.x), (int)round(d.y) };
}
inline double norm(const pdouble& d) {
	return sqrt((d.x * d.x) + (d.y * d.y));
}
inline double norm(const pint& d) {
	return norm(ToDouble(d));
}
inline int norm2(const pint& d) {
	return square(d.x) + square(d.y);
}
inline pdouble normalized(const pdouble& d) {
	return d / norm(d);
}
inline double dot(const pdouble& a, const pdouble& b) {
	return a.x * b.x + a.y * b.y;
}
inline double cross(const pdouble& a, const pdouble& b) {
	return a.x * b.y - a.y * b.x;
}



template <class T, int CAP>
class CapArr {
private:
	friend class CapArr;

	static_assert(is_trivially_copyable<T>::value);

	T array_[CAP];
	int size_ = 0;

public:


	bool operator == (const CapArr<T, CAP>& r) const {
		if (size_ != r.size_) {
			return false;
		}
		REP(i, size_) {
			if (!(array_[i] == r.array_[i])) {
				return false;
			}
		}
		return true;
	}
	template <class U, int U_CAP>
	bool operator != (const CapArr<U, U_CAP>& r) const {
		return !(*this == r);
	}

	bool MemEqual(const CapArr<T, CAP>& r) const {
		if (size_ != r.size_) {
			return false;
		}
		return memcmp(data(), r.data(), sizeof(T) * size_) == 0;
	}

	constexpr int capacity() const {
		return CAP;
	}

	int size() const {
		return size_;
	}
	bool empty() const {
		return size_ == 0;
	}

	void clear() {
		size_ = 0;
	}

	void resize(int size) {
		size_ = size;
	}

	void assign(int size, const T& e) {
		size_ = size;
		if constexpr (sizeof(T) == 1) {
			memset(data(), e, size);
		}
		else {
			for (int i = 0; i < size; ++i) {
				array_[i] = e;
			}
		}
	}

	void MemAssign(int size, int byte) {
		size_ = size;
		memset(data(), byte, sizeof(T) * size);
	}

	void MemCopy(const CapArr<T, CAP>& from) {
		size_ = from.size_;
		memcpy(data(), from.data(), sizeof(T) * from.size_);
	}

	const T* data() const {
		return &array_[0];
	}
	T* data() {
		return &array_[0];
	}

	T& front() {
		return array_[0];
	}
	const T& front() const {
		return array_[0];
	}

	T& back() {
		return array_[size_ - 1];
	}
	const T& back() const {
		return array_[size_ - 1];
	}

	T& operator[](int index) {
		return array_[index];
	}

	const T& operator[](int index) const {
		return array_[index];
	}

	T* begin() {
		return &array_[0];
	}
	T* end() {
		return &array_[size_];
	}
	const T* begin() const {
		return &array_[0];
	}
	const T* end() const {
		return &array_[size_];
	}

	[[nodiscard]] T& push() {
		auto& ref = array_[size_];
		++size_;
		return ref;
	}
	void push(const T& e) {
		array_[size_] = e;
		++size_;
	}

	void pop() {
		--size_;
	}

	int find(const T& value) const {

		REP(i, size_) {
			if (array_[i] == value) {
				return i;
			}
		}
		return -1;
	}
	bool contains(const T& value) const {
		for (const auto& v : *this) {
			if (v == value) {
				return true;
			}
		}
		return false;
	}

	void insert(int index, const T& value) {
		insert(index, &value, 1);
	}

	void insert(int index, const T* mem, int size) {
		if (index == size_) {
			memcpy(data() + index, mem, sizeof(T) * size);
			size_ += size;
		}
		else {
			memmove(data() + index + size, data() + index, sizeof(T) * (size_ - index));
			memcpy(data() + index, mem, sizeof(T) * size);
			size_ += size;
		}
	}

	template <int RCAP>
	void append(const CapArr<T, RCAP>& r) {
		insert(size(), r.data(), r.size());
	}

	void remove(int index) {
		remove(index, index + 1);
	}

	void remove(int start, int end) {
		int size = end - start;
		memmove(data() + start, data() + end, sizeof(T) * (size_ - end));
		size_ -= size;
	}

	void RemoveSwap(int index) {
		array_[index] = array_[size_ - 1];
		--size_;
	}

	void RemoveInsert(int start, int end, const T* p, int size) {
		int newEnd = start + size;
		if (size_ - end > 0 && newEnd != end) {
			memmove(data() + newEnd, data() + end, sizeof(T) * (size_ - end));
		}

		memcpy(data() + start, p, sizeof(T) * size);

		size_ -= end - start;
		size_ += size;
	}

};




template <class T, int CAPACITY>
struct CapacityQueue {
private:
	array<T, CAPACITY> ar_ = {};
	int start_ = 0;
	int end_ = 0;

public:
	inline void clear() {
		start_ = 0;
		end_ = 0;
	}

	inline void push(const T& v) {
		ar_[end_] = v;
		++end_;
	}

	inline T* push() {
		T* ptr = &ar_[end_];
		++end_;
		return ptr;
	}

	inline const T& get() const  {
		return ar_[start_];
	}

	inline T pop() {
		return ar_[start_++];
	}

	inline bool empty() const {
		return start_ == end_;
	}

	inline bool exist() const {
		return start_ != end_;
	}

	inline int size() const {
		return end_ - start_;
	}

	inline int total_push_count() const {
		return end_;
	}

	const T& operator[](int i) const{
		return ar_[i];
	}
	int end_size() const {
		return end_;
	}
	int direct_start() const {
		return start_;
	}
	int direct_end() const {
		return end_;
	}

	inline auto begin() -> decltype(ar_.begin()) {
		return ar_.begin() + start_;
	}
	inline auto end() -> decltype(ar_.begin()) {
		return ar_.begin() + end_;
	}
	inline auto begin() const -> decltype(ar_.begin()) {
		return ar_.begin() + start_;
	}
	inline auto end() const -> decltype(ar_.begin()) {
		return ar_.begin() + end_;
	}

	const T& front() const {
		return ar_[start_];
	}
	const T& back() const {
		return ar_[end_ - 1];
	}


};

template <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;






template <int S>
struct CheckMapS {
private:
    array<u32, S> checked_ = {};
    u32 mark_ = 1;

public:
    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_ = {};
            ++mark_;
        }
    }
    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }
    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
    bool operator[](int i) const {
        return checked_[i] == mark_;
    }

    bool operator == (const CheckMapS<S>& r) const {
        REP(i, S) {
            if (this->IsChecked(i) != r.IsChecked(i)) {
                return false;
            }
        }
        return true;
    }
};

template <class T, int S>
struct CheckMapDataS {
private:
    array<T, S> data_;
    array<u32, S> checked_ = {};
    u32 mark_ = 1;

public:
    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_ = {};
            ++mark_;
        }
    }

    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }

    void Set(int i, const T& value) {
        checked_[i] = mark_;
        data_[i] = value;
    }

    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
    const T& Get(int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    T& Ref(int i) {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    const T& Ref(int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    T& operator[](int i) {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    const T& operator[](int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }

    T GetIf(int i, const T& defaultValue) const {
        if (checked_[i] == mark_) {
            return data_[i];
        }
        return defaultValue;
    }
};

template <class T, int CAP>
struct CapacitySet {
private:
	CapArr<T, CAP> elemens;
	CheckMapDataS<T, CAP> indexTable;

public:
	CapacitySet() {
	}

	constexpr int capacity() {
		return CAP;
	}

	void Fill() {
		indexTable.Clear();
		elemens.resize(CAP);
		iota(ALL(elemens), 0);
		REP(i, CAP) {
			indexTable.Set(i, i);
		}
	}

	void Clear() {
		elemens.clear();
		indexTable.Clear();
	}

	void Add(T ai) {
		indexTable.Set(ai, elemens.size());
		elemens.push(ai);
	}

	void ForceAdd(T ai) {
		if (indexTable.IsChecked(ai)) {
			return;
		}
		indexTable.Set(ai, elemens.size());
		elemens.push(ai);
	}

	void Remove(int ai) {
		T removeIndex = indexTable[ai];
		T lastIndex = elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable.Set(elemens[lastIndex], removeIndex);
		}
		elemens.pop();
		indexTable.Reset(ai);
	}

	void ForceRemove(T ai) {
		if (!indexTable.IsChecked(ai)) {
			return;
		}
		T removeIndex = indexTable[ai];
		T lastIndex = elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable.Set(elemens[lastIndex], removeIndex);
		}
		elemens.pop();
		indexTable.Reset(ai);
	}

	bool IsContain(T ai) const {
		return indexTable.IsChecked(ai);
	}

	int size() const {
		return elemens.size();
	}
	bool empty() const {
		return elemens.empty();
	}

	T At(int index) const {
		return elemens[index];
	}

	T operator[](int index) const {
		return elemens[index];
	}

	auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};
template <class T, int CAP>
using CapSet = CapacitySet<T, CAP>;



inline int popcount(uint64_t bit) {
#if _MSC_VER
	return (int)__popcnt64(bit);
#else
	return __builtin_popcountll(bit);
#endif
}

int msb(uint64_t v) {
	if (v == 0) return false;
	v |= (v >> 1);
	v |= (v >> 2);
	v |= (v >> 4);
	v |= (v >> 8);
	v |= (v >> 16);
	v |= (v >> 32);
	return popcount(v) - 1;
}

inline uint64_t RotateLeft(uint64_t bit, uint64_t shift) {
	return (bit << shift) | (bit >> (64ULL - shift));
}
inline uint64_t RotateRight(uint64_t bit, uint64_t shift) {
	return (bit >> shift) | (bit << (64ULL - shift));
}


#if _MSC_VER
#include <intrin.h>
#endif

inline int FindBitRL(uint64_t bit) {
	if (bit == 0) {
		return -1;
	}
#if _MSC_VER
	unsigned long index = 0;
	_BitScanForward64(&index, bit);
	return (int)index;
#else
	return __builtin_ctzll(bit);
#endif
}

inline int FindBitLR(uint64_t bit) {
	if (bit == 0) {
		return -1;
	}
#if _MSC_VER
	unsigned long index = 0;
	_BitScanReverse64(&index, bit);
	return 63 - (int)index;			
#else
	return __builtin_clzll(bit);
#endif
}



template <class K>
struct CapHashSet {
	size_t m_capacity;
	K* m_keys;
	uint8_t* m_states;
	size_t m_mask;
	int m_count = 0;


	void init(size_t capacity) {
		m_capacity = 1ULL << (msb(capacity) + 1);
		m_mask = m_capacity - 1;
		m_keys = (K*)malloc(m_capacity * sizeof(K));
		m_states = (uint8_t*)calloc(m_capacity, sizeof(uint8_t));
		m_count = 0;
	}

	void clear() {
		memset(m_states, 0, m_capacity * sizeof(uint8_t));
		m_count = 0;
	}

	inline void set(K key) {
		size_t i = key & m_mask;
		for (;;) {
			if (m_states[i]) {
				if (key == m_keys[i]) {
					break;
				}
			}
			else {
				m_states[i] = 1;
				m_keys[i] = key;
				++m_count;
				break;
			}
			(++i) &= m_mask;
		}
	}
	inline void insert(K key) {
		set(key);
	}

	inline bool contains(K key) const {
		size_t i = key & m_mask;
		for (;;) {
			if (m_states[i]) {
				if (key == m_keys[i]) {
					return true;
				}
			}
			else {
				break;
			}
			(++i) &= m_mask;
		}
		return false;
	}

	bool enter(K key) {
		size_t i = key & m_mask;
		for (;;) {
			if (m_states[i]) {
				if (key == m_keys[i]) {
					return false;
				}
			}
			else {
				m_states[i] = 1;
				m_keys[i] = key;
				++m_count;
				return true;
			}
			(++i) &= m_mask;
		}
	}

	int GetCount() const {
		return m_count;
	}

};

#include <cstdint>


struct Xor64 {
	using result_type = uint64_t;
	static constexpr result_type min() { return 0; }
	static constexpr result_type max() { return UINT64_MAX; }

private:
	Xor64(const Xor64& r) = delete;
	Xor64& operator =(const Xor64& r) = delete;
public:

	uint64_t x;
	inline Xor64(uint64_t seed = 0) {
		x = 88172645463325252ULL + seed;
	}

	inline uint64_t operator()() {
		x = x ^ (x << 7);
		return x = x ^ (x >> 9);
	}

	inline uint64_t operator()(uint64_t l, uint64_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint64_t operator()(uint64_t r) {
		return (*this)() % r;
	}
	inline double GetDouble() {
		return (*this)() / (double)UINT64_MAX;
	}
	inline bool GetProb(double E) {
		return GetDouble() <= E;
	}
};



#define PARAM_CATEGORY(NAME, VALUE, ...) int NAME = VALUE;
#define PARAM_INT(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) int NAME = VALUE;
#define PARAM_DOUBLE(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) double NAME = VALUE;


#define PARAM_LOWER(v)
#define PARAM_UPPER(v)
#define START_TUNING
#define END_TUNING

#define PARAM_GROUP(NAME)
#define PARAM_GROUP_END




constexpr
struct {
} HP;

constexpr int T_Max = 1000;
constexpr int W = 25;
constexpr int H = 60;

constexpr int level_up = 100;  

template <class T> using WHArr = CapArr<T, W * H>;
template <class T> using WArr = CapArr<T, W>;
template <class T> using HArr = CapArr<T, H>;






enum class Action {
	S,
	L,
	R,
};
char ActionToChar[3] = { 'S', 'L', 'R' };
int ActionToDir[3] = { 0, -1, 1 };

struct Enemy {
	int initHp;
	int hp;
	int power;

	void init() {
		initHp = -1;
		hp = -1;
		power = -1;
	}

	bool exist() const {
		return hp > 0;
	}
	void clear() {
		initHp = -1;
		hp = -1;
		power = -1;
	}
};

struct Player {
	int x;
	int score;
	int power;
	int level;

	void init() {
		x = 12;
		score = 0;
		power = 0;
		level = 1;
	}

	void move(Action a) {
		x += ActionToDir[(int)a];
		if (x < 0) {
			x = W - 1;
		}
		else if (x >= W) {
			x = 0;
		}
	}
};

struct State {
	WArr<HArr<Enemy>> enemies;
	Player player;
	int turn;
	int destroyCount;
	bool gameOver;

	void init() {
		enemies.resize(W);
		REP(x, W) {
			enemies[x].resize(H);
			REP(y, H) {
				enemies[x][y].init();
			}
		}
		player.init();
		turn = 0;
		destroyCount = 0;
		gameOver = false;
	}

	void moveEnemy() {
		REP(x, W) {
			REP(y, H) {
				auto& e = enemies[x][y];
				if (e.exist()) {
					if (y - 1 >= 0) {
						enemies[x][y - 1] = e;
						if (y - 1 == 0 && x == player.x) {
							gameOver = true;
						}
					}
					e.clear();
				}
			}
		}
	}

	void spawnEnemy(istream& is) {
		int n = 0;
		is >> n;
		if (n < 0) {
			quick_exit(0);
			return;
		}

		int h, p, x;
		REP(i, n) {
			is >> h >> p >> x;
			auto& e = enemies[x][H - 1];
			e.initHp = h;
			e.hp = h;
			e.power = p;
		}
	}

	void move(Action a) {
		player.move(a);
	}
	void attack() {
		REP(y, H) {
			auto& e = enemies[player.x][y];
			if (e.exist()) {
				if (y == 0) {
					gameOver = true;
				}
				else {
					e.hp -= player.level;
					if (e.hp <= 0) {
						player.score += e.initHp;
						player.power += e.power;
						player.level = 1 + player.power / level_up;
						e.clear();
						++destroyCount;
					}
				}
				break;
			}
		}
		++turn;
	}

	void moveAndAttack(Action a) {
		move(a);
		attack();
	}

	int findFrontEnemy(int x) const {
		REP(y, H) {
			if (enemies[x][y].exist()) {
				return y;
			}
		}
		return -1;
	}
};

struct IOServer {
	State state_;

	void InitInput(ChronoTimer& timer) {
		istream& is = cin;

		timer.Init();		
		state_.init();

	}

	void TurnInput() {
		istream& is = cin;
		state_.moveEnemy();
		state_.spawnEnemy(is);

	}

	void Output(Action action) {
		ostream& os = cout;
		os << ActionToChar[(int)action] << endl;

		state_.moveAndAttack(action);
	}

	void Finalize() {
	}
};
IOServer server;


template <class OBJECT>
struct ObjectPool {
	static_assert(is_trivially_copyable<OBJECT>::value, "not trivially copyable");		

	OBJECT* pool_ = nullptr;			
	OBJECT** reusable_ = nullptr;		
	int capacity_ = 0;			
	int usedTotalCount_ = 0;	
	int usedPoolCount_ = 0;		
	int reusableCount_ = 0;		

	int maxTotalCount_ = 0;

	~ObjectPool() {
		if (pool_) {
			free(pool_);
		}
		if (reusable_) {
			free(reusable_);
		}
	}


	void Init(int capacity) {
		if (capacity != capacity_) {
			if (pool_) {
				free(pool_);
			}
			if (reusable_) {
				free(reusable_);
			}
			pool_ = (OBJECT*)malloc(capacity * sizeof(OBJECT));
			reusable_ = (OBJECT**)malloc(capacity * sizeof(OBJECT*));
			capacity_ = capacity;
		}
		usedTotalCount_ = 0;
		usedPoolCount_ = 0;
		reusableCount_ = 0;
	}

	void Clear() {
		usedTotalCount_ = 0;
		usedPoolCount_ = 0;
		reusableCount_ = 0;
	}

	inline OBJECT* New() {
		if (reusableCount_) {
			++usedTotalCount_;
			--reusableCount_;
			chmax(maxTotalCount_, usedTotalCount_);
			return reusable_[reusableCount_];
		}

		if (usedPoolCount_ >= capacity_) {
		}
		++usedTotalCount_;
		chmax(maxTotalCount_, usedTotalCount_);
		return &pool_[usedPoolCount_++];
	}

	inline void Delete(OBJECT* obj) {
		reusable_[reusableCount_] = obj;
		++reusableCount_;
		--usedTotalCount_;
	}

	inline void Delete(OBJECT** start, int count) {
		memcpy(&reusable_[reusableCount_], start, sizeof(OBJECT*) * count);
		reusableCount_ += count;
		usedTotalCount_ -= count;
	}

	inline int GetUsedCount() const {
		return usedTotalCount_;
	}

	inline string Usage() const {
		stringstream ss;
		ss << usedTotalCount_ << " (" << (int)floor(usedTotalCount_ * 100 / (double)capacity_ + 0.5) << " %)";
		return ss.str();
	}

	inline int UsedRate() const {
		return (int)round(usedTotalCount_ * 100 / (double)capacity_);
	}

	inline int GetCapacity() const {
		return capacity_;
	}

	inline int GetMaxUseCount() const {
		return maxTotalCount_;
	}

	inline int GetMaxUsedRate() const {
		return (int)round((double)GetMaxUseCount() * 100 / (double)capacity_);
	}
	inline string MaxUsage() const {
		stringstream ss;
		ss << maxTotalCount_ << " / " << capacity_ << " (" << (int)floor(maxTotalCount_ * 100 / (double)capacity_ + 0.5) << " %)";
		return ss.str();
	}
	double GetMemoryRate() const {
		return usedTotalCount_ / (double)capacity_;
	}
};


template <class NODE, class SCORE_LESS_COMPARER>
struct BeamSearch {
public:
	struct Nexts {
		vector<NODE*>& nodes_;
		Nexts(vector<NODE*>& nodes) : nodes_(nodes) {}
		void Add(NODE* node) {
			nodes_.emplace_back(node);
		}
	};

private:
	using NodePool = ObjectPool<NODE>;
	using HashTable = CapHashSet<u64>;

	NodePool nodePool_;
	HashTable hashTable_;
	int widthLimit_;			
	double startTimeRate_;		
	vector<NODE*> nodes_;
	vector<NODE*> nextNodes_;

public:
	NODE* New() {
		return nodePool_.New();
	}

	void Delete(NODE* node) {
		nodePool_.Delete(node);
	}

	bool ContainHash(u64 hash) const {
		return hashTable_.contains(hash);
	}

	void AddHash(u64 hash) {
		hashTable_.set(hash);
	}


	const vector<NODE*> RefFinalNodes() {
		return nodes_;
	}


	void Initialize(int widthLimit, int maxExpandCount, int hashTableSize = 0, int poolSize = -1, double startTimeRate = 0.5) {
		int widthCapacity = widthLimit * maxExpandCount;
		if (poolSize < 0) {
			poolSize = widthLimit + widthLimit * maxExpandCount;
		}
		nodePool_.Init(poolSize);
		hashTable_.init(hashTableSize);
		widthLimit_ = widthLimit;
		startTimeRate_ = startTimeRate;

		nodes_.reserve(widthCapacity);
		nextNodes_.reserve(widthCapacity);
	}

	template <class CREATE_ROOT_NODES, class CREATE_NEXT_NODES>
	void Run(ChronoTimer& timer, int beamDepth, int timeLimitMs, CREATE_ROOT_NODES&& createRootNodes, CREATE_NEXT_NODES&& createNextNodes) {

		SCORE_LESS_COMPARER less;
		auto greater = [&](const NODE* a, const NODE* b) {
			return less(b, a);
		};

		nodePool_.Clear();
		hashTable_.clear();
		nodes_.clear();
		nextNodes_.clear();

		Nexts nexts(nextNodes_);

		auto startTime = timer.ElapseTimeUs();
		auto limitTimePoint = timer.GetLimitTimePointUs(timeLimitMs * 1000);

		int finishedNodeCount = 0;
		{
			createRootNodes(nexts);
			REP(depth, beamDepth) {
				swap(nodes_, nextNodes_);

				if (nodes_.empty()) {
					break;
				}

				auto nowTime = timer.ElapseTimeUs();
				int timeLeft = timer.LeftToUS(limitTimePoint);
				int turnLeft = beamDepth - depth;
				double turnRate = depth / (double)(depth + turnLeft);
				double timeRate = startTimeRate_ + (1.0 - startTimeRate_) * turnRate;
				int turnTime = int(timeLeft * timeRate / turnLeft);
				timer.StartUs(nowTime + turnTime);

				int width = widthLimit_;
				auto elapsedTime = nowTime - startTime;
				if (elapsedTime && finishedNodeCount) {
					double timeNode = finishedNodeCount / (double)elapsedTime;		
					chmin(width, (int)ceil(timeNode * turnTime));
					chmax(width, 1);
				}

				if (nodes_.size() > width) {
					nth_element(nodes_.begin(), nodes_.begin() + width, nodes_.end(), greater);
					nodePool_.Delete(nodes_.data() + width, (int)nodes_.size() - width);
					nodes_.resize(width);
				}

				sort(nodes_.begin(), nodes_.end(), greater);

				nodePool_.Delete(nextNodes_.data(), (int)nextNodes_.size());
				nextNodes_.clear();

				hashTable_.clear();

				for (auto& node : nodes_) {
					createNextNodes(depth, node, nexts);
					if (timer.IsOver()) {
						break;
					}
					++finishedNodeCount;
				}

			}
		}

		if (nextNodes_.empty()) {
			swap(nodes_, nextNodes_);
		}

		cerr << "total node " << finishedNodeCount << endl;
	}

	template <class CREATE_ROOT_NODES, class CREATE_NEXT_NODES>
	void Run(ChronoTimer& timer, CREATE_ROOT_NODES&& createRootNodes, CREATE_NEXT_NODES&& createNextNodes) {
		nodePool_.Clear();
		nodes_.clear();
		nextNodes_.clear();
		hashTable_.clear();

		SCORE_LESS_COMPARER less;
		auto greater = [&](const NODE* a, const NODE* b) {
			return less(b, a);
		};

		Nexts nexts(nextNodes_);

		int finishedNodeCount = 0;
		int depth = 0;
		{
			createRootNodes(nexts);
			while (!timer.IsOver()) {
				swap(nodes_, nextNodes_);

				int width = widthLimit_;

				if (nodes_.size() > width) {
					nth_element(nodes_.begin(), nodes_.begin() + width, nodes_.end(), greater);
					nodePool_.Delete(nodes_.data() + width, (int)nodes_.size() - width);
					nodes_.resize(width);
				}

				nodePool_.Delete(nextNodes_.data(), (int)nextNodes_.size());
				nextNodes_.clear();


				for (auto& node : nodes_) {
					createNextNodes(depth, node, nexts);

					if (timer.IsOver()) {
						break;
					}
				}
				finishedNodeCount += (int)nodes_.size();
				++depth;

				if (nextNodes_.empty()) {
					break;
				}

			}
		}
	}




	template <class CREATE_ROOT_NODES, class CREATE_NEXT_NODES>
	void Run(int beamWidth, int beamDepth, CREATE_ROOT_NODES&& createRootNodes, CREATE_NEXT_NODES&& createNextNodes) {
		nodePool_.Clear();
		nodes_.clear();
		nextNodes_.clear();
		hashTable_.clear();

		SCORE_LESS_COMPARER less;
		auto greater = [&](const NODE* a, const NODE* b) {
			return less(b, a);
		};

		Nexts nexts(nextNodes_);

		int finishedNodeCount = 0;
		{
			createRootNodes(nexts);
			REP(depth, beamDepth) {
				swap(nodes_, nextNodes_);

				if (nodes_.size() > beamWidth) {
					nth_element(nodes_.begin(), nodes_.begin() + beamWidth, nodes_.end(), greater);
					nodePool_.Delete(nodes_.data() + beamWidth, (int)nodes_.size() - beamWidth);
					nodes_.resize(beamWidth);
				}

				nodePool_.Delete(nextNodes_.data(), (int)nextNodes_.size());
				nextNodes_.clear();


				for (auto& node : nodes_) {
					createNextNodes(depth, node, nexts);
				}
				finishedNodeCount += (int)nodes_.size();

				if (nextNodes_.empty()) {
					break;
				}
			}
		}
	}
};

struct Node {
	Action firstAction;
	State state;
	double evalScore;
};
static constexpr int StateSize = sizeof(Node);

struct RawComparer {
	bool operator()(const Node* a, const Node* b) const {
		return a->evalScore < b->evalScore;
	}
};

struct Solver {
	Xor64 rand_;

	using Search = BeamSearch<Node, RawComparer>;
	using Nexts = Search::Nexts;
	Search search;

	void Run(ChronoTimer& timer) {
		search.Initialize(1000, 16, 0, -1, 0.5);

		REP(t, T_Max) {
			server.TurnInput();

			double bestEvalScore = -1e100;
			Action bestAction = Action::S;


			auto Eval = [&](const State& state) {
				double eval = 0;
				double turnRate = state.turn / (double)T_Max;
				double baseHP = 7.5 + 0.15 * state.turn;
				double destroyTurn = baseHP / (double)(state.player.level + state.player.power / 100.0);

				eval -= pow(destroyTurn, 20) * 1000;

				eval += state.player.power;
				eval -= sqrt(state.turn) * 20000000;
				eval += state.player.score * 10 * pow(turnRate, 2.0);

				if (state.gameOver) {
					eval -= 1e10;
				}
				return eval;
			};

			auto FindEnemy = [&](const State& state) {
				cauto& player = state.player;
				return state.findFrontEnemy(player.x);
			};

			auto DestroyTurn = [&](const State& state, int enemyY) {
				cauto& player = state.player;
				cauto& enemy = state.enemies[player.x][enemyY];
				int attackCount = enemyY;
				int damage = attackCount * player.level;
				if (damage >= enemy.hp) {
					int destroyTurn = (enemy.hp + player.level - 1) / player.level;
					return destroyTurn;
				}
				return -1;
			};

			auto createRootNodes = [&](Nexts& nextNodes) {
				Node* node = search.New();
				node->state = server.state_;
				node->evalScore = 0;
				nextNodes.Add(node);
			};

			auto createNextNodes = [&](int depth, const Node* node, Nexts& nextNodes) {
				if (node->state.turn >= T_Max) {
					return;
				}

				{
					int enemyY = FindEnemy(node->state);
					if (enemyY >= 0) {
						int destroyTurn = DestroyTurn(node->state, enemyY);
						if (destroyTurn >= 0) {
							Node* nextNode = search.New();
							nextNode->state = node->state;
							REP(dt, destroyTurn) {
								nextNode->state.move(Action::S);
								nextNode->state.attack();
								nextNode->state.moveEnemy();
							}
							nextNode->evalScore = Eval(nextNode->state);
							if (depth == 0) {
								nextNode->firstAction = Action::S;
							}
							else {
								nextNode->firstAction = node->firstAction;
							}
							nextNodes.Add(nextNode);

							if (nextNode->evalScore > bestEvalScore) {
								bestEvalScore = nextNode->evalScore;
								bestAction = nextNode->firstAction;
							}
						}
					}
				}

				for (Action action : {Action::L, Action::R}) {
					State state = node->state;
					REP(appendTurn, 4) {
						State tmpState = state;
						tmpState.move(action);
						tmpState.attack();
						tmpState.moveEnemy();
						if (tmpState.gameOver) {
							state.move(Action::S);
							state.attack();
							state.moveEnemy();
							if (tmpState.gameOver) {
								break;
							}
						}
						else {
							state.move(action);
							state.attack();
							state.moveEnemy();

							int enemyY = FindEnemy(state);
							if (enemyY >= 0) {
								int destroyTurn = DestroyTurn(state, enemyY);
								if (destroyTurn >= 0) {
									Node* nextNode = search.New();
									nextNode->state = state;
									REP(dt, destroyTurn) {
										nextNode->state.move(Action::S);
										nextNode->state.attack();
										nextNode->state.moveEnemy();
									}
									nextNode->evalScore = Eval(nextNode->state);
									if (depth == 0) {
										nextNode->firstAction = action;
									}
									else {
										nextNode->firstAction = node->firstAction;
									}
									nextNodes.Add(nextNode);

									if (nextNode->evalScore > bestEvalScore) {
										bestEvalScore = nextNode->evalScore;
										bestAction = nextNode->firstAction;
									}
								}
							}
						}
					}
				}
			};

			search.Run(16, 3, createRootNodes, createNextNodes);

			server.Output(bestAction);
		}

	}
};


struct Main {
    void Run(int argc, const char* argv[]) {
        ChronoTimer timer;
        server.InitInput(timer);

        static Solver solver;
        timer.StartMs(TIME_LIMIT);

        solver.Run(timer);

        cerr << "time " << timer.ElapseTimeMs() << endl;
        server.Finalize();
    }
};
0