結果

問題 No.5018 Let's Make a Best-seller Book
ユーザー bowwowforeachbowwowforeach
提出日時 2023-10-01 15:31:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 311 ms / 400 ms
コード長 24,542 bytes
コンパイル時間 3,335 ms
コンパイル使用メモリ 228,456 KB
実行使用メモリ 24,396 KB
スコア 48,584
平均クエリ数 52.00
最終ジャッジ日時 2023-10-01 15:32:21
合計ジャッジ時間 21,397 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 117 ms
23,640 KB
testcase_01 AC 132 ms
23,364 KB
testcase_02 AC 74 ms
23,652 KB
testcase_03 AC 77 ms
24,372 KB
testcase_04 AC 101 ms
24,384 KB
testcase_05 AC 95 ms
23,832 KB
testcase_06 AC 121 ms
23,388 KB
testcase_07 AC 152 ms
24,012 KB
testcase_08 AC 142 ms
23,508 KB
testcase_09 AC 77 ms
24,024 KB
testcase_10 AC 150 ms
24,276 KB
testcase_11 AC 62 ms
23,832 KB
testcase_12 AC 95 ms
24,024 KB
testcase_13 AC 113 ms
23,664 KB
testcase_14 AC 110 ms
24,240 KB
testcase_15 AC 227 ms
23,388 KB
testcase_16 AC 51 ms
23,520 KB
testcase_17 AC 134 ms
23,664 KB
testcase_18 AC 147 ms
24,036 KB
testcase_19 AC 110 ms
23,652 KB
testcase_20 AC 58 ms
23,664 KB
testcase_21 AC 143 ms
23,664 KB
testcase_22 AC 70 ms
24,312 KB
testcase_23 AC 169 ms
24,288 KB
testcase_24 AC 216 ms
24,396 KB
testcase_25 AC 100 ms
23,520 KB
testcase_26 AC 102 ms
23,412 KB
testcase_27 AC 73 ms
23,652 KB
testcase_28 AC 100 ms
24,012 KB
testcase_29 AC 144 ms
24,012 KB
testcase_30 AC 136 ms
24,036 KB
testcase_31 AC 173 ms
23,832 KB
testcase_32 AC 103 ms
24,036 KB
testcase_33 AC 247 ms
24,060 KB
testcase_34 AC 108 ms
23,676 KB
testcase_35 AC 111 ms
24,048 KB
testcase_36 AC 186 ms
24,024 KB
testcase_37 AC 86 ms
24,384 KB
testcase_38 AC 143 ms
23,628 KB
testcase_39 AC 202 ms
23,724 KB
testcase_40 AC 77 ms
23,400 KB
testcase_41 AC 192 ms
24,024 KB
testcase_42 AC 311 ms
24,360 KB
testcase_43 AC 176 ms
23,676 KB
testcase_44 AC 124 ms
23,520 KB
testcase_45 AC 181 ms
24,012 KB
testcase_46 AC 117 ms
24,048 KB
testcase_47 AC 57 ms
23,664 KB
testcase_48 AC 90 ms
23,520 KB
testcase_49 AC 84 ms
23,832 KB
testcase_50 AC 260 ms
23,364 KB
testcase_51 AC 72 ms
23,616 KB
testcase_52 AC 78 ms
23,520 KB
testcase_53 AC 153 ms
23,412 KB
testcase_54 AC 82 ms
23,820 KB
testcase_55 AC 267 ms
23,532 KB
testcase_56 AC 201 ms
24,348 KB
testcase_57 AC 77 ms
23,652 KB
testcase_58 AC 94 ms
24,048 KB
testcase_59 AC 65 ms
23,820 KB
testcase_60 AC 288 ms
23,412 KB
testcase_61 AC 161 ms
24,264 KB
testcase_62 AC 117 ms
23,376 KB
testcase_63 AC 120 ms
23,400 KB
testcase_64 AC 197 ms
23,412 KB
testcase_65 AC 107 ms
24,024 KB
testcase_66 AC 84 ms
24,312 KB
testcase_67 AC 260 ms
24,360 KB
testcase_68 AC 123 ms
24,276 KB
testcase_69 AC 163 ms
24,264 KB
testcase_70 AC 90 ms
23,520 KB
testcase_71 AC 125 ms
23,376 KB
testcase_72 AC 47 ms
23,652 KB
testcase_73 AC 82 ms
23,832 KB
testcase_74 AC 109 ms
24,024 KB
testcase_75 AC 99 ms
23,532 KB
testcase_76 AC 90 ms
24,048 KB
testcase_77 AC 98 ms
23,844 KB
testcase_78 AC 110 ms
24,372 KB
testcase_79 AC 117 ms
23,832 KB
testcase_80 AC 101 ms
23,628 KB
testcase_81 AC 83 ms
23,844 KB
testcase_82 AC 112 ms
23,844 KB
testcase_83 AC 165 ms
24,048 KB
testcase_84 AC 103 ms
23,628 KB
testcase_85 AC 91 ms
23,412 KB
testcase_86 AC 104 ms
24,252 KB
testcase_87 AC 105 ms
23,832 KB
testcase_88 AC 193 ms
23,388 KB
testcase_89 AC 81 ms
23,628 KB
testcase_90 AC 213 ms
24,360 KB
testcase_91 AC 185 ms
23,652 KB
testcase_92 AC 146 ms
23,664 KB
testcase_93 AC 136 ms
23,676 KB
testcase_94 AC 73 ms
24,036 KB
testcase_95 AC 116 ms
24,360 KB
testcase_96 AC 128 ms
23,664 KB
testcase_97 AC 133 ms
23,652 KB
testcase_98 AC 145 ms
23,652 KB
testcase_99 AC 152 ms
23,676 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:410:22: 警告: class ‘CapArr<T, CAP>’ is implicitly friends with itself
  410 |         friend class CapArr;
      |                      ^~~~~~

ソースコード

diff # 

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


#define TIME_LIMIT (350)

#define NOT_SUBMIT 0
#define VALIDATION 0

#define IO_FILE 0

#define OUTPUT_INFO 0
#define OUTPUT_FINAL_INFO 0
#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) {
			if constexpr (is_enum<T>::value) {
				memset(data(), underlying_type<T>::type(e), size);
			}
			else {
				memset(data(), e, size);
			}
		}
		else {
			for (int i = 0; i < size; ++i) {
				array_[i] = e;
			}
		}
	}

	void AssignIota(int size) {
		resize(size);
		iota(begin(), end(), 0);
	}
	void Iota(int size) {
		resize(size);
		iota(begin(), end(), 0);
	}

	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 LESS>
	void stable_sort(LESS&& less) {
		::stable_sort(begin(), end(), less);
	}

};




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 contains(T i) const {
		return indexTable.IsChecked(i);
	}
	bool IsContain(T i) const {
		return contains(i);
	}

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



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

	template <class T>
	inline T operator()(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 = 52;
constexpr int N = 10;

template <class T> using NArr = CapArr<T, N>;
template <class U> using TArr = CapArr<U, T>;





constexpr double LinearParam(double ax, double ay, double bx, double by, double cx) {
	double r = (cx - ax) / (bx - ax);
	double cy = ay + (by - ay) * r;
	return cy;
}

constexpr double LinearParam2(
	double left, double right, double top, double bottom,
	double valueLT, double valueRT, double valueLB, double valueRB,
	double x, double y) {
	double rx = (x - left) / (right - left);
	double ry = (y - top) / (bottom - top);

	double dst = (1 - rx) * (1 - ry) * valueLT
		+ (1 - rx) * ry * valueLB
		+ rx * (1 - ry) * valueRT
		+ rx * ry * valueRB;
	return dst;
}

int LinearParamInt(double ax, double ay, double bx, double by, double cx) {
	return (int)round(LinearParam(ax, ay, bx, by, cx));
}
int LinearParam2Int(
	double left, double right, double top, double bottom,
	double valueLT, double valueRT, double valueLB, double valueRB,
	double x, double y) {
	return (int)round(LinearParam2(left, right, top, bottom,
		valueLT, valueRT, valueLB, valueRB,
		x, y));
}





enum class ActionType {
	Order,
	CM,
};

struct Result {
	ActionType type_;
	NArr<int> Ls_;		
	int level_;			
};

struct IOServer {

	int turn_ = 0;
	int money_ = 2000000;
	NArr<int> Ss_;		
	NArr<int> Ps_;		
	NArr<int> Rs_;		

	int totalSale_ = 0;


	void InitInput(ChronoTimer& timer) {
		istream& is = cin;
		int dummy;
		is >> dummy >> dummy >> dummy;
		timer.Init();		

		Ss_.assign(N, 0);
		Ps_.assign(N, 0);
		Rs_.assign(N, 0);
	}

	void Output(const Result& result) {
		VASSERT(turn_ < T);
		ostream& os = cout;

		if (result.type_ == ActionType::Order) {
			os << 1;
			REP(i, N) {
				os << " " << result.Ls_[i];
			}
			os << endl;
		}
		else {
			os << 2 << " " << result.level_ << endl;
		}

		istream& is = cin;
		is >> money_;

		REP(i, N) {
			is >> Ss_[i];
		}
		REP(i, N) {
			is >> Ps_[i];
		}
		REP(i, N) {
			is >> Rs_[i];
		}

		REP(i, N) {
			totalSale_ += Ss_[i];
		}


		++turn_;
	}

	void Finalize() {
		VASSERT(turn_ == T);
	}
};
IOServer server;

struct Solver {
	Xor64 rand_;

	void Run(ChronoTimer& timer) {
		Result r;
		r.Ls_.resize(N);

		NArr<double> Ds;		
		Ds.assign(N, 1);

		NArr<int> Ss;		
		Ss.assign(N, 0);

		int ninkiTurn = 40;

		REP(t, T) {
			if (t < ninkiTurn) {
				int orderNinki = 0;
				NArr<int> orderZaiko = server.Rs_;		
				REP(i, N) {
					double Z = 1;
					double b = -pow(1.05, 2 * server.Ps_[i]) * square(Ds[i]) * square(Z);
					double upperZaiko = -b / square(0.3);

					double bestScore = -1e100;
					int bestZaiko = server.Rs_[i];
					int bestNinkiDiff = 0;
					FOR(newZaiko, server.Rs_[i], (int)ceil(upperZaiko)) {
						double sale = sqrt(newZaiko) * pow(1.05, server.Ps_[i]) * Ds[i] * Z;

						int isale = (int)floor(sale);
						int ninkiDiff = 0;
						if (isale * 10 >= newZaiko * 3) {
							if (server.Ps_[i] < 60) {
								ninkiDiff = 1;
							}
						}
						else if (isale * 10 < newZaiko * 1) {
							if (server.Ps_[i] > -60) {
								ninkiDiff = -1;
							}
						}

						double score = sale;
						score += 100 * ninkiDiff;

						if (score > bestScore) {
							bestScore = score;
							bestZaiko = newZaiko;
							bestNinkiDiff = ninkiDiff;
						}
					}
					orderNinki += bestNinkiDiff;
					orderZaiko[i] = bestZaiko;
				}

				{
					r.type_ = ActionType::Order;
					int money = server.money_;
					REP(i, N) {
						int order = orderZaiko[i] - server.Rs_[i];
						int cost = order * 500;
						if (cost <= money) {
							r.Ls_[i] = order;
							money -= cost;
						}
						else {
							r.Ls_[i] = 0;
						}
					}
				}

				{
					constexpr double LeftRate = 0.3;		
					int usableMoney = (int)floor(server.money_ * LeftRate);

					int bestNinki = -1;
					int bestLevel = -1;
					FOR(level, 1, 6) {
						int cost = 500000 * (1 << (level - 1));
						int totalNinki = 0;
						if (cost <= usableMoney) {
							REP(i, N) {
								int newNinki = server.Ps_[i] + level;
								chmin(newNinki, 60);
								int addNinki = newNinki - server.Ps_[i];
								totalNinki += addNinki;
							}
						}
						if (totalNinki > bestNinki) {
							bestNinki = totalNinki;
							bestLevel = level;
						}
					}

					if (bestNinki >= 0 && bestNinki > orderNinki) {
						r.type_ = ActionType::CM;
						r.level_ = bestLevel;
					}
				}
			}
			else {
				r.type_ = ActionType::Order;
				r.Ls_.assign(N, 0);

				int AppendCount = server.money_ / 500;
				REP(i, AppendCount) {
					int money = server.money_;
					int bestI = -1;
					double bestDiff = -1e100;
					REP(i, N) {
						double Z = 1;
						double curSale = sqrt(server.Rs_[i] + r.Ls_[i]) * pow(1.05, server.Ps_[i]) * Ds[i] * Z;
						double nextSale = sqrt(server.Rs_[i] + r.Ls_[i] + 1) * pow(1.05, server.Ps_[i]) * Ds[i] * Z;
						double diff = nextSale - curSale;
						if (diff > bestDiff) {
							bestDiff = diff;
							bestI = i;
						}
					}
					r.Ls_[bestI] += 1;
				}
			}

			REP(i, N) {
				int zaiko = server.Rs_[i];
				int ninki = server.Ps_[i];
				if (r.type_ == ActionType::Order) {
					zaiko += r.Ls_[i];
				}
				else {
					ninki += r.level_;
					chmin(ninki, 60);
				}

				double Z = 1;
				int predictSale = (int)floor(sqrt(zaiko) * pow(1.05, ninki) * Ds[i] * Z);
				Ss[i] = predictSale;
			}


			server.Output(r);


			constexpr double DUpdateRate = 1.01;		

			REP(i, N) {
				if (server.Ss_[i] == Ss[i]) {
				}
				else if (server.Ss_[i] < Ss[i]) {
					Ds[i] /= DUpdateRate;
					chmax(Ds[i], 0.5);
				}
				else {
					Ds[i] *= DUpdateRate;
					chmin(Ds[i], 1.5);
				}
			}



		}
	}
};

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

        static Solver solver;
        timer.StartMs(TIME_LIMIT);

        solver.Run(timer);

        server.Finalize();

    }
};
0