← Real problems

noip20p3

unratedStatement on DMOJ

CP Lang

46 lines0.3 spec
// NOIP 2020 "Ball Moving": n + 1 tubes of capacity m, n colours of m balls,
// one tube empty; sort by colour in at most 820000 moves. Divide and conquer
// on colours: split the tubes into "low" and "high" halves, then recurse.
let (n, m) = read<(2..=50, 2..=400)>()
domain Tube = 1..=n + 1
var tube = [Tube] t => if t <= n: read<List<1..=n>>(len: m) else: List()
var moves = List<(Tube, Tube)>()

fn mv(from: Tube, to: Tube, count: Int = 1):
    for _ in 0..count:
        tube[to].push(tube[from].pop()!)
        moves.push((from, to))

fn split(cols: List<Tube>, colours: Range<1..=n>):
    if colours.len <= 1:
        return
    let mid = colours.mid.l
    let spare = Tube.find(t => t not in cols and tube[t].is_empty())!
    fn low(t: Tube) -> Int = tube[t].count(c => c <= mid)

    for a in cols:
        let helper = cols.find(t => t != a)!
        let (lo, hi) = (low(a), m - low(a))
        mv(helper, spare, m - lo)
        for c in tube[a].rev.clone():
            mv(a, if c <= mid: spare else: helper)
        if m - lo > lo:
            mv(helper, a, m - lo); mv(spare, a, lo)
        else:
            mv(spare, a, lo); mv(helper, a, m - lo)
        mv(spare, helper, m - lo)

    fn bottom_low(t: Tube) = tube[t].first! <= mid
    fn mixed(t: Tube) = 0 < low(t) < m
    while let (a, b) = cols.adjacent.find(p => mixed(p.0) and mixed(p.1) and bottom_low(p.0) == bottom_low(p.1)):
        let side = if bottom_low(a): (t: Tube) => m - low(t) else: low
        mv(a, spare, side(a)); mv(b, spare, side(b))
        mv(b, a, m - tube[a].len)
    let (lo, hi) = cols.partition(bottom_low)
    split(lo, colours.l..mid.r)
    split(hi, mid.r..colours.r)

split(Tube.take(n).collect(), 1..=n)
print(moves.len)
for (a, b) in moves:
    print(a, b)

Accepted C++

231 lines · 0.71 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << " ";
        }
        out << arr[i];
    }
    return out;
}

constexpr int maxn = 55;

int n, m, ce;
vector<int> arr[maxn];
vector<bool> arrb[maxn];
vector<pair<int, int>> ans;

#ifdef LOCAL
#undef assert
void assert(bool b) {
    if (!b) {
        bool* _asan = new bool[1];
        bool tmp = _asan[1412];
        exit(1);
    }
}
#endif

void dbg_arr() {
    cerr << "---ARR---" << endl;
    for (int i = 0; i <= n; i++) {
        cerr << arr[i] << endl;
    }
}

void dbg_arrb() {
    cerr << "---ARRB---" << endl;
    for (int i = 0; i <= n; i++) {
        cerr << arrb[i] << endl;
    }
}

void move(int u, int v, int cnt = 1) {
    assert(u != v);
    for (int i = 0; i < cnt; i++) {
        assert(sz(arr[u]));
        assert(sz(arr[v]) + 1 <= m);
        ans.emplace_back(u, v);
        arr[v].push_back(arr[u].back());
        arr[u].pop_back();
        arrb[v].push_back(arrb[u].back());
        arrb[u].pop_back();
    }
}

void dfs(vector<int> cols, int ql, int qr) {
    dbg(ql, qr);
    if (ql == qr) {
        return;
    }
    int qmid = (ql + qr) / 2;
    for (int i = 0; i <= n; i++) {
        arrb[i].resize(sz(arr[i]));
        for (int j = 0; j < sz(arr[i]); j++) {
            arrb[i][j] = arr[i][j] > qmid;
        }
    }
    for (auto& a : cols) {
        int c0, c1 = ce, cnt0 = int(count(begin(arrb[a]), end(arrb[a]), false)),
                cnt1 = m - cnt0;
        for (c0 = 0; c0 == a || c0 == c1; c0++)
            ;
        dbg(c0, c1);
        move(c0, c1, cnt0);
        for (int i = sz(arr[a]) - 1; i >= 0; i--) {
            if (arrb[a][i]) {
                move(a, c1);
            } else {
                move(a, c0);
            }
        }
        if (cnt0 > cnt1) {
            move(c0, a, cnt0);
            move(c1, a, cnt1);
        } else {
            move(c1, a, cnt1);
            move(c0, a, cnt0);
        }
        move(c1, c0, cnt0);
    }
    int cnt0[n + 1], cnt1[n + 1];
    auto upd_cnt = [&](int i) -> void {
        cnt0[i] = int(count(begin(arrb[i]), end(arrb[i]), false));
        cnt1[i] = m - cnt0[i];
    };
    auto finished = [&](int i) -> bool {
        return !cnt0[i] || !cnt1[i];
    };
    for (auto& a : cols) {
        upd_cnt(a);
    }
    while (true) {
        bool changed = false;
        for (auto& a : cols) {
            for (auto& b : cols) {
                if (a == b || finished(a) || finished(b) ||
                    arrb[a][0] != arrb[b][0]) {
                    continue;
                }
                changed = true;
                int *ccnt0 = cnt0, *ccnt1 = cnt1;
                if (arrb[a][0]) {
                    swap(ccnt0, ccnt1);
                }
                move(a, ce, ccnt1[a]);
                move(b, ce, ccnt1[b]);
                move(b, a, m - ccnt0[a]);
                int leftc0 = ccnt0[a] + ccnt0[b] - m,
                    leftc1 = ccnt1[a] + ccnt1[b];
                if (leftc0 > leftc1) {
                    move(ce, b, leftc1);
                } else {
                    move(b, ce, leftc0);
                    swap(b, ce);
                }
                upd_cnt(a);
                upd_cnt(b);
            }
        }
        if (!changed) {
            break;
        }
    }
    vector<int> unfinished;
    dbg_arrb();
    for (auto& a : cols) {
        if (!finished(a)) {
            unfinished.push_back(a);
        }
    }
    if (sz(unfinished)) {
        dbg(unfinished);
        dbg_arrb();
        assert(sz(unfinished) == 2);
        int a = unfinished[0], b = unfinished[1];
        assert(cnt0[a] == cnt1[b]);
        if (arrb[a][0]) {
            swap(a, b);
        }
        move(a, ce, cnt1[a]);
        move(b, a, cnt0[b]);
        move(ce, b, cnt1[a]);
    }
    dbg_arrb();
    vector<int> cl, cr;
    for (auto& a : cols) {
        if (arrb[a][0]) {
            cr.push_back(a);
        } else {
            cl.push_back(a);
        }
    }
    dfs(cl, ql, qmid);
    dfs(cr, qmid + 1, qr);
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        arr[i].resize(m);
        for (auto& a : arr[i]) {
            cin >> a;
            a--;
        }
    }
    vector<int> cols(n);
    iota(begin(cols), end(cols), 0);
    ce = n;
    dfs(cols, 0, n - 1);
    cout << sz(ans) << endl;
    for (auto& [u, v] : ans) {
        cout << u + 1 << " " << v + 1 << endl;
    }
    dbg_arr();
    for (auto& a : arr) {
        if (sz(a)) {
            for (auto& b : a) {
                assert(b == a[0]);
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}