結果
| 問題 |
No.5018 Let's Make a Best-seller Book
|
| コンテスト | |
| ユーザー |
bowwowforeach
|
| 提出日時 | 2023-10-01 13:54:53 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 31 ms / 400 ms |
| コード長 | 21,222 bytes |
| コンパイル時間 | 3,132 ms |
| コンパイル使用メモリ | 223,100 KB |
| 実行使用メモリ | 24,384 KB |
| スコア | 537 |
| 平均クエリ数 | 52.00 |
| 最終ジャッジ日時 | 2023-10-01 13:55:04 |
| 合計ジャッジ時間 | 10,992 ms |
|
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
| 純コード判定しない問題か言語 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
main.cpp:410:22: 警告: class ‘CapArr<T, CAP>’ is implicitly friends with itself
410 | friend class CapArr;
| ^~~~~~
ソースコード
#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);
REP(t, T) {
r.type_ = ActionType::Order;
REP(i, N) {
r.Ls_[i] = 1;
}
server.Output(r);
}
}
};
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();
}
};
bowwowforeach