← Real problems

noi14p5

mediumgreedysimulationStatement on DMOJ

CP Lang

31 lines0.3 spec
// noi14p5 Random Number Generator: build the board from the generator, then take values smallest
// first; a cell (r, c) fits the monotone path iff every row above stays at or left of c and every
// row below at or right of it.
let (x0, a, b, c, d) = read<(0..=100_000_000, 0..=300, 0..=100_000_000, 0..=100_000_000, 1..=100_000_000)>()
let (n, m, q) = read<(1..=5000, 1..=5000, 0..=50_000)>()
domain Row = 1..=n
domain Col = 1..=m
domain Grid = (Row, Col)
domain Value = 1..=n * m
var board: [Grid]Value = [Grid] p => Value.nth(0)
for (k, p) in Grid.items:
    board[p] = Value.nth(k)
var x = x0
for (k, p) in Grid.items:
    x = (a * x * x + b * x + c) % d
    board.swap(p, Grid.nth(x % (k + 1)))
for (u, v) in read<[q](Value, Value)>():
    board.swap(Grid.nth(Int(u) - 1), Grid.nth(Int(v) - 1))
let at = board.inverse()
var lo: [Row]Col = Col.first!
var hi: [Row]Col = Col.last!
var path: List<Value> = []
for v in Value:
    let (r, col) = at[v]
    if lo[r] <= col and col <= hi[r]:
        path.push(v)
        for above in ..r:
            hi[above] = min(hi[above], col)
        for below in r.next..:
            lo[below] = max(lo[below], col)
print(path)

Accepted C++

119 lines · 4.32 s on the judge
#include "bits/extc++.h"

using namespace std;

template<class T, class U = less<T>>
using rt = __gnu_pbds::tree<T, __gnu_pbds::null_type, U, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<class T, class U>
void sep(T &out, const string &s, const U &u) {
	out << u;
}

template<class T, class Head, class ...Tail>
void sep(T &out, const string &s, const Head &h, const Tail &...t) {
	out << h << s;
	sep(out, s, t...);
}

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

//imagine a language where int = long
#define long int64_t

//typing too hard
#define endl "\n"

#define sz(x) int((x).size())

struct cowng {
	long x, a, b, c, d;

	cowng(int64_t x, int64_t a, int64_t b, int64_t c, int64_t d): x(x), a(a), b(b), c(c), d(d) {}

	long operator()() {
		return x = ((c + b * x + a * x * x) % d);
	}
};

void solve() {
	long rx, ra, rb, rc, rd;
	cin >> rx >> ra >> rb >> rc >> rd;
	cowng rng(rx, ra, rb, rc, rd);
	int n, m, q;
	cin >> n >> m >> q;
	int arr[n * m];
	iota(arr, arr + n * m, 0);
	for(int i = 0; i < n * m; i++) {
		swap(arr[i], arr[rng() % (i + 1)]);
	}
	while(q--) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		swap(arr[u], arr[v]);
	}
	int pos[n * m];
	for(int i = 0; i < n * m; i++) {
		pos[arr[i]] = i;
	}
	int top[m + 2], bot[m + 2];
	top[0] = bot[0] = 0;
	top[m + 1] = bot[m + 1] = n - 1;

	bool marked[m + 2] {};
	int nl[m + 2], nr[m + 2];
	fill(nl, nl + m + 2, 0);
	fill(nr, nr + m + 2, m + 1);
	vector<int> ans;
	for(int i = 0; i < n * m; i++) {
		int x = pos[i] % m, y = pos[i] / m;
		x++;
		dbg(i + 1, x, y, nl[x], nr[x], bot[nl[x]], top[nr[x]]);
		if(bot[nl[x]] <= y && y <= top[nr[x]]) {
			ans.push_back(i);
			if(marked[x]) {
				bot[x] = max(bot[x], y);
				top[x] = min(top[x], y);
			}else {
				marked[x] = true;
				bot[x] = top[x] = y;
				for(int j = nl[x]; j < x; j++) {
					nr[j] = x;
				}
				for(int j = x + 1; j <= nr[x]; j++) {
					nl[j] = x;
				}
			}
		}
	}
	sort(begin(ans), end(ans));
	for(auto &a: ans) {
		cout << a + 1 << " ";
	}
	cout << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int t = 1;
//	cin >> t;
	for(int _ = 1; _ <= t; _++) {
		dbg(_);
//		cout << "Case #" << _ << ": ";
		solve();
	}
}