#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include #include #include #include #include #include #include #include #include #include #include #include #include struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else // return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) // return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) // return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // enums // structs // constants constexpr int n = 50; constexpr int k = 50; // inputs array t, u; // outputs array b, m, e; // internals void receive_input() { int _n, _k; cin >> _n >> _k; for (int i = 0; i < k; i++) cin >> t[i]; for (int i = 0; i < k; i++) cin >> u[i]; } void init() { } inline ll calc_pendulum_pos(ll bm, ll time) { ll in_cycle_time = time % (bm * 4); if (in_cycle_time <= bm) return in_cycle_time; else if (in_cycle_time <= bm * 3) return bm * 2 - in_cycle_time; else return in_cycle_time - bm * 4; } void solve1() { auto calc_pendulum_pos = [](ll bm, ll time) { ll in_cycle_time = time % (bm * 4); if (in_cycle_time <= bm) return in_cycle_time; else if (in_cycle_time <= bm * 3) return bm * 2 - in_cycle_time; else return in_cycle_time - bm * 4; }; ll best_score = 0; ll best_bm1 = -1; ll best_bm2 = -1; for (int bm1 = 1; bm1 * 3 < min(t[0], u[0]); bm1++) { ll t_score = 0; ll u_score = 0; for (int i = 0; i < k; i++) { ll pos1 = calc_pendulum_pos(bm1, t[i]); ll pos2 = -pos1; t_score += (ll)(1e7 * (double) abs(pos1 - pos2) / (double) (bm1 * 3)); } for (int i = 0; i < k; i++) { ll pos1 = calc_pendulum_pos(bm1, u[i]); ll pos2 = -pos1; u_score += (ll)(1e7 / (sqrt(abs(pos1 - pos2) / 20.0 + 1.0))); } ll total_score = (t_score / k) * (u_score / k); if (total_score > best_score) { best_score = total_score; best_bm1 = bm1; best_bm2 = -1; } } for (ll bm1 = 1; ; bm1++) { for (ll bm2 = 1; bm2 <= bm1; bm2++) { ll t_score = 0; ll u_score = 0; for (int i = 0; i < k; i++) { ll pos1 = calc_pendulum_pos(bm1, t[i]); ll pos2 = calc_pendulum_pos(bm2, t[i]); t_score += (ll)(1e7 * (double) abs(pos1 - pos2) / (double) (bm1 + bm2)); } for (int i = 0; i < k; i++) { ll pos1 = calc_pendulum_pos(bm1, u[i]); ll pos2 = calc_pendulum_pos(bm2, u[i]); u_score += (ll)(1e7 / (sqrt(abs(pos1 - pos2) / 20.0 + 1.0))); } ll total_score = (t_score / k) * (u_score / k); if (total_score > best_score) { best_score = total_score; best_bm1 = bm1; best_bm2 = bm2; } } if (theTimer.time() > 0.100) break; } cerr << "score = " << best_score << endl; if (best_bm2 == -1) { for (int i = 0; i < n / 2; i++) { b[i] = best_bm1 * 2; m[i] = best_bm1; e[i] = best_bm1; } for (int i = n / 2; i < n; i++) { b[i] = best_bm1; m[i] = best_bm1; e[i] = 1; } } else { for (int i = 0; i < n / 2; i++) { b[i] = best_bm1; m[i] = best_bm1; e[i] = 1; } for (int i = n / 2; i < n; i++) { b[i] = best_bm2; m[i] = best_bm2; e[i] = 1; } } } void solve2() { auto calc_pendulum_pos = [](ll b, ll m, ll e, ll time) { ll b2 = b * 2; ll m2 = m * 2; ll e2 = e * 2; ll decay_cycle_limit = ((b2 - m2) + e2 - 1) / e2; ll decay_end_time = (decay_cycle_limit * (b2 + (b2 - e2 * (decay_cycle_limit - 1)))) / 2; if (time < decay_end_time) { ll ng = -1; ll ok = decay_cycle_limit + 1; while (abs(ng - ok) > 1) { ll target_cycle = (ng + ok) / 2; ll cycle_end_time = (target_cycle * (b2 + (b2 - e2 * (target_cycle - 1)))) / 2; if (time < cycle_end_time) ok = target_cycle; else ng = target_cycle; } ll direction = ((ok - 1) % 2 == 0) ? 1 : -1; ll in_cycle_time = time - ((ok - 1) * (b2 + (b2 - e2 * (ok - 2)))) / 2; ll cycle_length = b2 - e2 * (ok - 1); if (in_cycle_time < 0 || cycle_length <= in_cycle_time) { assert(false); } if (in_cycle_time <= cycle_length / 2) return in_cycle_time * direction; else return (cycle_length - in_cycle_time) * direction; } else { ll direction = ((decay_cycle_limit + (time - decay_end_time) / m2) % 2 == 0) ? 1 : -1; ll in_cycle_time = (time - decay_end_time) % m2; if (in_cycle_time <= m) return in_cycle_time * direction; else return (m2 - in_cycle_time) * direction; } }; ll best_score = 0; ll best_b1 = 1; ll best_m1 = 1; ll best_e1 = 1; ll best_b2 = 1; ll best_m2 = 1; ll best_e2 = 1; for (ll b1 = 1; ; b1++) { for (ll m1 = b1; m1 >= 1; m1--) { for (ll e1 = 1; e1 <= b1 - m1 + 1; e1++) { for (ll b2 = 1; b2 <= b1; b2++) { for (ll m2 = b2; m2 >= 1; m2--) { for (ll e2 = 1; e2 <= b2 - m2 + 1; e2++) { ll t_score = 0; ll u_score = 0; for (int i = 0; i < k; i++) { ll pos1 = calc_pendulum_pos(b1, m1, e1, t[i]); ll pos2 = calc_pendulum_pos(b2, m2, e2, t[i]); t_score += (ll)(1e7 * (double) abs(pos1 - pos2) / (double) (b1 + b2)); } for (int i = 0; i < k; i++) { ll pos1 = calc_pendulum_pos(b1, m1, e1, u[i]); ll pos2 = calc_pendulum_pos(b2, m2, e2, u[i]); u_score += (ll)(1e7 / (sqrt(abs(pos1 - pos2) / 20.0 + 1.0))); } ll total_score = (t_score / k) * (u_score / k); if (total_score > best_score) { cerr << b1 << " " << m1 << " " << e1 << " " << b2 << " " << m2 << " " << e2 << " " << t_score / k << " " << u_score / k << " " << total_score << endl; best_score = total_score; best_b1 = b1; best_m1 = m1; best_e1 = e1; best_b2 = b2; best_m2 = m2; best_e2 = e2; } } if (theTimer.time() > 1.900) break; } if (theTimer.time() > 1.900) break; } if (theTimer.time() > 1.900) break; } if (theTimer.time() > 1.900) break; } if (theTimer.time() > 1.900) break; } cerr << "score = " << best_score << endl; for (int i = 0; i < n / 2; i++) { b[i] = best_b1; m[i] = best_m1; e[i] = best_e1; } for (int i = n / 2; i < n; i++) { b[i] = best_b2; m[i] = best_m2; e[i] = best_e2; } } void solve() { // solve1(); solve2(); } void output_ans() { for (int i = 0; i < n; i++) cout << b[i] << " " << m[i] << " " << e[i] << endl; } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); receive_input(); init(); solve(); output_ans(); return 0; }