#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template void ndarray(vector& vec, const V& val, int len) { vec.assign(len, val); } template void ndarray(vector& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); } template bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template std::pair operator+(const std::pair &l, const std::pair &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template std::pair operator-(const std::pair &l, const std::pair &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template std::vector sort_unique(std::vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template int arglb(const std::vector &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template int argub(const std::vector &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template IStream &operator>>(IStream &is, std::vector &vec) { for (auto &v : vec) is >> v; return is; } template OStream &operator<<(OStream &os, const std::vector &vec); template OStream &operator<<(OStream &os, const std::array &arr); template OStream &operator<<(OStream &os, const std::unordered_set &vec); template OStream &operator<<(OStream &os, const pair &pa); template OStream &operator<<(OStream &os, const std::deque &vec); template OStream &operator<<(OStream &os, const std::set &vec); template OStream &operator<<(OStream &os, const std::multiset &vec); template OStream &operator<<(OStream &os, const std::unordered_multiset &vec); template OStream &operator<<(OStream &os, const std::pair &pa); template OStream &operator<<(OStream &os, const std::map &mp); template OStream &operator<<(OStream &os, const std::unordered_map &mp); template OStream &operator<<(OStream &os, const std::tuple &tpl); template OStream &operator<<(OStream &os, const std::vector &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::array &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } #if __cplusplus >= 201703L template std::istream &operator>>(std::istream &is, std::tuple &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template OStream &operator<<(OStream &os, const std::tuple &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } #endif template OStream &operator<<(OStream &os, const std::unordered_set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::deque &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::pair &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template OStream &operator<<(OStream &os, const std::map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif struct Pendulum { int b; // 初期振幅 int m; // 最小振幅 int e; // 減衰振幅 std::vector init; Pendulum() = default; Pendulum(int b_, int m_, int e_) : b(b_), m(m_), e(e_) { assert(1 <= m and m <= b); assert(1 <= e); init.push_back(0); for (int dir = 1, a = b_; a > m or dir < 0; dir = -dir, a = max(m, a - e)) { for (int t = 1; t <= a; ++t) init.push_back(dir * t); for (int t = a - 1; t >= 0; --t) init.push_back(dir * t); } } int get(int t) const { assert(t >= 0); if (t < int(init.size())) return init.at(t); int md = (t - init.size() + 1) % (m * 4); if (md < m) return md; if (md < m * 3) return m * 2 - md; return md - m * 4; } }; constexpr int maxb = 5; vector>> pendulums(maxb + 1); const Pendulum& get_pendulum(const tuple &bme) { return pendulums.at(std::get<0>(bme)).at(std::get<1>(bme)).at(std::get<2>(bme)); } struct Input { int n; vector T; vector U; template Input(OStream &os) { int k; os >> n >> k; T.resize(k), U.resize(k); os >> T >> U; } }; plint evaluate_plint(const Input &in, const vector> &bmes) { const int n = bmes.size(); lint rett = 0, retu = 0; for (int t : in.T) { double tmp = 0; REP(i, bmes.size()) { int xi = get_pendulum(bmes[i]).get(t), bi = std::get<0>(bmes[i]); REP(j, i) { int xj = get_pendulum(bmes[j]).get(t), bj = std::get<0>(bmes[j]); tmp += double(abs(xi - xj)) / (bi + bj); } } tmp = tmp * 2e7 / (n * (n - 1)); rett += roundl(tmp); } rett = roundl(1.0 * rett / in.T.size()); for (int u : in.U) { constexpr int INF = 1 << 30; int xhi = -INF, xlo = INF; for (const auto &bme : bmes) { int x = get_pendulum(bme).get(u); chmax(xhi, x); chmin(xlo, x); } double tmp = 1e7 / sqrtl((xhi - xlo) * 0.05 + 1); retu += roundl(tmp); } retu = roundl(1.0 * retu / in.U.size()); return {rett, retu}; } double evaluate_d(const Input &in, const vector> &bmes) { auto p = evaluate_plint(in, bmes); return 1.0 * p.first * p.second; } template void dump(OStream &os, const vector> &bmes) { for (auto [b, m, e] : bmes) os << b << ' ' << m << ' ' << e << endl; } uint32_t rand_int() // XorShift random integer generator { static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123; uint32_t t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } double rand_double() { return (double)rand_int() / UINT32_MAX; } int main() { vector> bmes, sol; FOR(b, 1, maxb + 1) { pendulums.at(b).resize(b + 1); FOR(m, 1, b + 1) { pendulums.at(b).at(m).resize(max(2, b - m + 1)); FOR(e, 1, max(1, b - m) + 1) { pendulums.at(b).at(m).at(e) = Pendulum(b, m, e); bmes.emplace_back(b, m, e); } } } // dbg(bmes); REP(t, 50) sol.emplace_back(t % 2 + 1, 1, 1); Input instance(cin); dbg(instance.T); dbg(instance.U); auto ev = evaluate_plint(instance, sol); double eval_tmp = evaluate_d(instance, sol); REP(_, 1000) { int i = rand_int() % bmes.size(); // FIXME int j = rand_int() % sol.size(); // FIXME auto bme = bmes.at(i); swap(sol.at(j), bme); double eval_nxt = evaluate_d(instance, sol); if (chmax(eval_tmp, eval_nxt)) { dbg(eval_tmp); } else { swap(sol.at(j), bme); } } dump(cout, sol); }