#include using namespace std; // Random Number Generation {{{ mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count()); int randint(int l, int r) { return rng() % (r-l+1) + l; } //}}} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); const int N = 24; const int B = 4; const int per_b = N/B; const int D = 6; vector A(D, vector(N)); for (auto &d : A) { iota(begin(d), end(d), 0LL); shuffle(begin(d), end(d), rng); } int cur_score = 0; vector meets(N, vector(N)); for (auto const& d : A) { for (int bi = 0; bi < B; bi++) { for (int i = bi*per_b; i < (bi+1)*per_b; i++) { for (int j = i+1; j < (bi+1)*per_b; j++) { auto [a, b] = minmax(d[i], d[j]); cur_score -= !!meets[a][b]; meets[a][b]++; cur_score += !!meets[a][b]; } } } } auto add_person = [&](int di, int bi, int pi, int delta) { auto const& d = A[di]; int pi_idx = bi*per_b + pi; for (int i = bi*per_b; i < (bi+1)*per_b; i++) { if (i == pi_idx) continue; auto [a, b] = minmax(d[pi_idx], d[i]); cur_score -= !!meets[a][b]; meets[a][b] += delta; cur_score += !!meets[a][b]; } }; // Needs bi != bj auto swap_people = [&](int di, int bi, int bj, int pi, int pj) { add_person(di, bi, pi, -1); add_person(di, bj, pj, -1); int pi_idx = bi*per_b + pi; int pj_idx = bj*per_b + pj; swap(A[di][pi_idx], A[di][pj_idx]); add_person(di, bi, pi, +1); add_person(di, bj, pj, +1); }; auto score_brute = [&]() { vector> ok(N, vector(N)); for (auto &d : meets) fill(begin(d), end(d), 0); cur_score = 0; for (auto const& d : A) { for (int bi = 0; bi < B; bi++) { for (int i = bi*per_b; i < (bi+1)*per_b; i++) { for (int j = i+1; j < (bi+1)*per_b; j++) { auto [a, b] = minmax(d[i], d[j]); ok[a][b] = true; meets[a][b]++; } } } } int sum = 0; for (auto const& oki : ok) { sum += accumulate(begin(oki), end(oki), 0LL); } cur_score = sum; return sum; }; for (int it = 0; it < 100'000'000; it++) { int di = randint(0, D-1); int bi = randint(0, B-2); int bj = randint(bi+1, B-1); int pi = randint(0, per_b-1); int pj = randint(0, per_b-1); int before = cur_score; swap_people(di, bi, bj, pi, pj); if (before > cur_score) { swap_people(di, bi, bj, pi, pj); } if (cur_score == N*(N-1)/2) break; if (it % 100000 == 0) { cout << "Checkpoint " << it << ' ' << cur_score << endl; shuffle(begin(A[di]), end(A[di]), rng); score_brute(); cout << "AfterShuffle " << it << ' ' << cur_score << endl; } } if (cur_score != N*(N-1)/2) cout << "Solution not found!" << endl, exit(0); for (int di = 0; di < D; di++) { cout << "Day " << di+1 << endl; for (int bi = 0; bi < B; bi++) { cout << "Boat " << bi+1 << ": "; for (int i = per_b*bi; i < per_b*(bi+1); i++) { cout << A[di][i]+1 << ' '; if (A[di][i]+1 < 10) cout << ' '; } cout << endl; } cout << endl; } }