#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; using lint = long long int; using P = pair; using PL = pair; #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) #define ALL(a) (a).begin(),(a).end() constexpr int MOD = 1000000007; constexpr lint B1 = 1532834020; constexpr lint M1 = 2147482409; constexpr lint B2 = 1388622299; constexpr lint M2 = 2147478017; constexpr int INF = 2147483647; void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";} templatevoid chmax(T &a, const T &b) { if (avoid chmin(T &a, const T &b) { if (b> PARAMS = { {1, 1}, {2, 1}, {2, 2}, {3, 2}, {4, 2}, {5, 2}, {6, 2}, {3, 3}, {4, 3}, {5, 3}, {6, 3}, {7, 3}, {8, 3}, {9, 3}, {10, 3} }; vector T; vector U; lint N, K; lint M = 14; lint calc_score(vector &cnt) { double score1 = 0; REP(i, K) { vector B(N), X(N); int ptr = 0; REP(j, M) { REP(k, cnt[j]) { B[ptr] = PARAMS[j][0]; lint t = PARAMS[j][0] * 2 + PARAMS[j][1] * 2; t = T[i] - t; t %= PARAMS[j][1] * 4; if(t < PARAMS[j][1]) { X[ptr] = t; } else if(t < PARAMS[j][1] * 3) { X[ptr] = PARAMS[j][1] * 2 - t; } else { X[ptr] = t - PARAMS[j][1] * 4; } ptr++; } } REP(j, N) FOR(k, j+1, N) score1 += (double)abs(X[j] - X[k]) / (B[j] + B[k]); } double score2 = 0; REP(i, K) { vector X(N); int ptr = 0; REP(j, M) { REP(k, cnt[j]) { lint t = PARAMS[j][0] * 2 + PARAMS[j][1] * 2; t = U[i] - t; t %= PARAMS[j][1] * 4; if(t < PARAMS[j][1]) { X[ptr] = t; } else if(t < PARAMS[j][1] * 3) { X[ptr] = PARAMS[j][1] * 2 - t; } else { X[ptr] = t - PARAMS[j][1] * 4; } ptr++; } } lint ma = 0; REP(j, N) FOR(k, j+1, N) chmax(ma, abs(X[j] - X[k])); score2 += 1.0 / sqrt(1.0 + (double)ma / 20.0); } score1 *= 20000000 / N / (N-1) / K; score2 *= 10000000 / K; return round(score1) * round(score2); }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> K; T = vector(K); REP(i, K) cin >> T[i]; U = vector(K); REP(i, K) cin >> U[i]; vector pat(N); REP(i, N) pat[i] = i%2; vector B(N); vector> XT(K, vector(N)), XU(K, vector(N)); vector>> st(K); double score1 = 0, score2 = 0; REP(i, K) { REP(j, N) { B[j] = PARAMS[pat[j]][0]; lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2; t = T[i] - t; t %= PARAMS[pat[j]][1] * 4; if(t < PARAMS[pat[j]][1]) { XT[i][j] = t; } else if(t < PARAMS[pat[j]][1] * 3) { XT[i][j] = PARAMS[pat[j]][1] * 2 - t; } else { XT[i][j] = t - PARAMS[pat[j]][1] * 4; } } REP(j, N) FOR(k, j+1, N) score1 += (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]); } REP(i, K) { REP(j, N) { lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2; t = U[i] - t; t %= PARAMS[pat[j]][1] * 4; if(t < PARAMS[pat[j]][1]) { XU[i][j] = t; } else if(t < PARAMS[pat[j]][1] * 3) { XU[i][j] = PARAMS[pat[j]][1] * 2 - t; } else { XU[i][j] = t - PARAMS[pat[j]][1] * 4; } } REP(j, N) FOR(k, j+1, N) st[i].insert(abs(XU[i][j] - XU[i][k])); score2 += 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0); } lint best_score = round(score1 * 20000000 / N / (N-1) / K) * round(score2 * 10000000 / K); cerr << best_score << endl; double time = 0; int loop = 0; double start_temp = 13, end_temp = 10; double temp = start_temp; auto start_time = std::chrono::system_clock::now(); while(true) { if(loop%100 == 0) { auto now_time = std::chrono::system_clock::now(); time = std::chrono::duration_cast(now_time-start_time).count(); temp = start_temp + (end_temp - start_temp) * time / (TIME_LIMIT); cerr << "LOOP:" << loop << " SCORE:" << best_score << " TIME:" << time << endl; if(time > TIME_LIMIT) break; } loop++; int j, x, tmp; while(true) { j = rand() % N; x = rand() % M; if(pat[j] != x) break; } REP(i, K) REP(k, N) if(j != k) score1 -= (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]); REP(i, K) { score2 -= 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0); REP(k, N) if(j != k) st[i].erase(st[i].find(abs(XU[i][j] - XU[i][k]))); } tmp = pat[j]; pat[j] = x; B[j] = PARAMS[pat[j]][0]; REP(i, K) { lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2; t = T[i] - t; t %= PARAMS[pat[j]][1] * 4; if(t < PARAMS[pat[j]][1]) { XT[i][j] = t; } else if(t < PARAMS[pat[j]][1] * 3) { XT[i][j] = PARAMS[pat[j]][1] * 2 - t; } else { XT[i][j] = t - PARAMS[pat[j]][1] * 4; } } REP(i, K) { lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2; t = U[i] - t; t %= PARAMS[pat[j]][1] * 4; if(t < PARAMS[pat[j]][1]) { XU[i][j] = t; } else if(t < PARAMS[pat[j]][1] * 3) { XU[i][j] = PARAMS[pat[j]][1] * 2 - t; } else { XU[i][j] = t - PARAMS[pat[j]][1] * 4; } } REP(i, K) REP(k, N) if(j != k) score1 += (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]); REP(i, K) { REP(k, N) if(j != k) st[i].insert(abs(XU[i][j] - XU[i][k])); score2 += 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0); } lint score = round(score1 * 20000000 / N / (N-1) / K) * round(score2 * 10000000 / K); double prob = exp(((double)score-best_score)/pow(10, temp)); if(score > best_score || prob > (rand()%INF)/(double)INF) { //ok best_score = score; } else { //ng REP(i, K) REP(k, N) if(j != k) score1 -= (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]); REP(i, K) { score2 -= 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0); REP(k, N) if(j != k) st[i].erase(st[i].find(abs(XU[i][j] - XU[i][k]))); } pat[j] = tmp; B[j] = PARAMS[pat[j]][0]; REP(i, K) { lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2; t = T[i] - t; t %= PARAMS[pat[j]][1] * 4; if(t < PARAMS[pat[j]][1]) { XT[i][j] = t; } else if(t < PARAMS[pat[j]][1] * 3) { XT[i][j] = PARAMS[pat[j]][1] * 2 - t; } else { XT[i][j] = t - PARAMS[pat[j]][1] * 4; } } REP(i, K) { lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2; t = U[i] - t; t %= PARAMS[pat[j]][1] * 4; if(t < PARAMS[pat[j]][1]) { XU[i][j] = t; } else if(t < PARAMS[pat[j]][1] * 3) { XU[i][j] = PARAMS[pat[j]][1] * 2 - t; } else { XU[i][j] = t - PARAMS[pat[j]][1] * 4; } } REP(i, K) REP(k, N) if(j != k) score1 += (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]); REP(i, K) { REP(k, N) if(j != k) st[i].insert(abs(XU[i][j] - XU[i][k])); score2 += 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0); } } } REP(i, N) cout << PARAMS[pat[i]][0] << " " << PARAMS[pat[i]][1] << " " << 100 << "\n"; }