← Real problems

btoi18p4

unratedStatement on DMOJ

CP Lang

74 lines0.3 spec
// BOI 2018 "Alternating Current": wires cover wrapping arcs of a ring of n
// segments; give each wire a direction so both directions cover the ring.
// A wire inside another takes the opposite direction of its outermost holder.
// The k outermost wires alternate round the ring; when k is odd, two adjacent
// outermost wires share a direction, which works when the opposite side still
// covers their union from their own nested wires and their two neighbours.
let (n, m) = read<(3..=1e5, 2..=1e5)>()
domain Seg = 1..=n
domain Wire = [m]
let ends = read<[Wire](a: Seg, b: Seg)>()
let lo = [Wire] w => Int(ends[w].a)
let hi = [Wire] w => Int(ends[w].b) + (if ends[w].b < ends[w].a: n else: 0)

// Whether the arcs `on`, each repeated one lap either way, cover segments lo..=hi.
// O(s log s) in the number of arcs, never O(n), so the per-top checks stay O(m log m) in total.
fn covers(on: List<Wire>, part: (lo: Int, hi: Int)) -> Bool:
    var reach = part.lo - 1
    for (l, h) in [(lo[w] + s, hi[w] + s) for w in on for s in [-n, 0, n]].sorted():
        if reach >= part.hi:
            break
        if l > reach + 1:
            return false
        reach = max(reach, h)
    reach >= part.hi

let whole = (lo: 1, hi: n)
var holder: [Wire]?Wire = []
var reach: ?(end: Int, by: Wire) = None
let copies = [(start: lo[w] + s, end: hi[w] + s, w: w) for w in Wire for s in [0, n]]
for c in copies.sorted(by: c => (c.start, desc(c.end))):
    match reach:
        Some(r) if c.end <= r.end and r.by != c.w => holder[c.w] = holder[c.w] ?? Some(r.by)
        _ => reach = Some((end: c.end, by: c.w))
fn top(w: Wire) -> Wire = iterate(from: Some(w), step: v => holder[v]).last()!
let tops = Wire.filter(w => holder[w].is_none()).collect().sorted(by: w => lo[w])
domain T = [tops.len]
var rank: [Wire]?T = []
for t in T:
    rank[tops[Int(t)]] = Some(t)
let inside = Wire.filter(w => holder[w].is_some()).collect().group(by: w => top(w))
fn kids(t: T) -> List<Wire> = inside.get(tops[Int(t)]) ?? List()

fn spread(side: T -> Bool) -> ?[Wire]Bool:
    let dir = [Wire] w => if holder[w].is_none(): side(rank[w]!) else: not side(rank[top(w)]!)
    let both = [false, true].all(d => covers(Wire.filter(w => dir[w] == d).collect(), whole))
    if both: Some(dir) else: None

// Top t can share its neighbour's direction when its own nested wires and its two neighbouring
// tops still cover it from the other side.
fn alone(t: T) -> Bool =
    covers(kids(t) + [tops[Int(T.ring.prev(t))], tops[Int(T.ring.next(t))]], (lo: lo[tops[Int(t)]], hi: hi[tops[Int(t)]]))

let answer: ?[Wire]Bool =
    if T.len % 2 == 0 or T.len == 1:
        spread(t => Int(t) % 2 == 1)
    elif T.len == 3:
        T.first_some(b => spread(t => T.ring.dist(b, t) % 2 == 0))
    elif not covers(Wire.collect(), whole):
        None
    else:
        let free = [T] t => alone(t)
        let good = T.filter(t => free[t]).collect().len
        T.first_some(b =>
            let c = T.ring.next(b)
            let (wb, wc) = (tops[Int(b)], tops[Int(c)])
            let pair = (lo: lo[wb], hi: hi[wc] + (if lo[wc] < lo[wb]: n else: 0))
            let others = [tops[Int(T.ring.prev(b))], tops[Int(T.ring.next(c))]]
            if good - Int(free[b]) - Int(free[c]) == T.len - 2 and covers(kids(b) + kids(c) + others, pair):
                spread(t => T.ring.dist(c, t) % 2 == 0)
            else: None)

match answer:
    Some(dir) => print(dir.map(d => Int(d)), sep: "")
    None => print("impossible")

Accepted C++

276 lines · 1.42 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((x).size())

void solve() {
	int n, m;
	cin >> n >> m;
	array<int, 3> arr[m];
	for (int i = 0; i < m; i++) {
		auto& [l, r, ci] = arr[i];
		cin >> l >> r;
		l--;
		r--;
		ci = i;
		if (l > r) {
			r += n;
		}
	}
	sort(arr, arr + m, [&](const auto& a, const auto& b) -> bool {
		if (a[0] != b[0]) {
			return a[0] < b[0];
		}
		return a[1] > b[1];
	});
	for (auto& [l, r, _] : arr) {
		if (r >= n) {
			r -= n;
		}
	}
	int par[m];
	pair<int, int> mx {-1, -1};
	for (int i = 0; i < 2 * m; i++) {
		int ci = i >= m ? i - m : i;
		auto [l, r, _] = arr[ci];
		if (l > r) {
			r += n;
		}
		if (i >= m) {
			l += n;
			r += n;
		}
		if (r <= mx.first) {
			par[ci] = mx.second;
		} else {
			par[ci] = ci;
			mx = {r, ci};
		}
	}
	for (int i = 0; i < m; i++) {
		int u = i;
		while (par[u] != u) {
			u = par[u];
		}
		par[i] = u;
	}
	vector<int> vals;
	int inds[m];
	for (int i = 0; i < m; i++) {
		if (par[i] == i) {
			inds[i] = sz(vals);
			vals.push_back(i);
		}
		dbg(i, arr[i][0], arr[i][1], par[i]);
	}
	auto covers_all = [&](const vector<pair<int, int>>& arr) -> bool {
		vector<int> e[n];
		for (auto& [l, r] : arr) {
			e[l].push_back(r);
		}
		int mx = -1;
		for (int i = 0; i < n; i++) {
			for (auto& a : e[i]) {
				mx = max(mx, a);
			}
			if (mx < i) {
				return false;
			}
		}
		return true;
	};
	auto check = [&](const vector<bool>& distr) -> void {
		vector<pair<int, int>> segs[2];
		auto add = [&](int i, int l, int r) -> void {
			if (r >= n) {
				r -= n;
			}
			if (l > r) {
				segs[i].emplace_back(l, n - 1);
				segs[i].emplace_back(0, r);
			} else {
				segs[i].emplace_back(l, r);
			}
		};
		bool ans[m];
		for (int i = 0; i < m; i++) {
			auto& [l, r, ci] = arr[i];
			if (par[i] == i) {
				ans[ci] = distr[inds[i]];
			} else {
				ans[ci] = !distr[inds[par[i]]];
			}
			dbg(i, inds[par[i]], ans[ci]);
			add(ans[ci], l, r);
		}
		if (covers_all(segs[0]) && covers_all(segs[1])) {
			for (auto& a : ans) {
				cout << a;
			}
			cout << endl;
			exit(0);
		}
	};
	int k = sz(vals);
	dbg(k);
	if (k % 2 == 0 || k == 1) {
		vector<bool> distr(k);
		for (int i = 0; i < k; i++) {
			distr[i] = i & 1;
		}
		check(distr);
		cout << "impossible" << endl;
		return;
	} else if (k <= 3) {
		for (int i = 0; i < k; i++) {
			vector<bool> distr(k);
			int j = i;
			bool cur = true;
			while (true) {
				distr[j] = cur;
				cur ^= true;
				j = j + 1 == k ? 0 : j + 1;
				if (j == i) {
					break;
				}
			}
			check(distr);
		}
		cout << "impossible" << endl;
		return;
	}
	{
		vector<pair<int, int>> cur;
		for (auto& [l, r, _] : arr) {
			if (l > r) {
				cur.emplace_back(l, n - 1);
				cur.emplace_back(0, r);
			} else {
				cur.emplace_back(l, r);
			}
		}
		if (!covers_all(cur)) {
			cout << "impossible" << endl;
			return;
		}
	}
	auto covers = [&](const vector<pair<int, int>>& segs, int ql, int qr) -> bool {
		if (!sz(segs)) {
			return false;
		}
		vector<pair<int, int>> evts;
		for (auto& [l, r] : segs) {
			evts.emplace_back(l - n, 1);
			evts.emplace_back(r - n + 1, -1);
			evts.emplace_back(l, 1);
			evts.emplace_back(r + 1, -1);
			evts.emplace_back(l + n, 1);
			evts.emplace_back(r + n + 1, -1);
		}
		sort(begin(evts), end(evts));
		int prev = -1, cur = 0;
		for (auto& [ind, x] : evts) {
			if (prev != -1 && ind != prev) {
				if (!cur) {
					if (ql <= ind - 1 && ind - 1 <= qr) {
						return false;
					} else if (ql <= prev && prev <= qr) {
						return false;
					}
				}
			}
			cur += x;
			prev = ind;
		}
		return true;
	};
	bool can[k];
	vector<pair<int, int>> child[k];
	for (int i = 0; i < m; i++) {
		auto& [l, r, _] = arr[i];
		if (l > r) {
			r += n;
		}
		if (par[i] != i) {
			child[inds[par[i]]].emplace_back(l, r);
		}
	}
	array<int, 2> carr[k];
	for (int i = 0; i < k; i++) {
		carr[i] = {arr[vals[i]][0], arr[vals[i]][1]};
	}
	for (int i = 0; i < k; i++) {
		int a = (i + k - 1) % k, b = (i + 1) % k;
		vector<pair<int, int>> cur = child[i];
		cur.emplace_back(carr[a][0], carr[a][1]);
		cur.emplace_back(carr[b][0], carr[b][1]);
		can[i] = covers(cur, carr[i][0], carr[i][1]);
		dbg(i, can[i], carr[a][0], carr[a][1], carr[b][0], carr[b][1], carr[i][0], carr[i][1]);
	}
	int cnt = 0;
	for (auto& a : can) {
		cnt += a;
	}
	for (int i = 0; i < k; i++) {
		int a = i, b = (i + 1) % k, c = (i + 2) % k, d = (i + 3) % k;
		int ccnt = cnt - can[b] - can[c];
		if (ccnt != k - 2) {
			continue;
		}
		vector<pair<int, int>> cur;
		cur.insert(cur.end(), begin(child[b]), end(child[b]));
		cur.insert(cur.end(), begin(child[c]), end(child[c]));
		cur.emplace_back(carr[a][0], carr[a][1]);
		cur.emplace_back(carr[d][0], carr[d][1]);
		if (!covers(cur, carr[b][0], carr[c][1])) {
			continue;
		}
		dbg(i, carr[b][0], carr[c][1]);
		vector<bool> distr(k);
		bool cb = true;
		while (true) {
			distr[c] = cb;
			cb ^= true;
			if (c == b) {
				break;
			}
			c = c + 1 == k ? 0 : c + 1;
		}
		check(distr);
//		assert(false);
	}
	cout << "impossible" << endl;
}

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