oj.uz

Submission #137767

# Submission time Handle Problem Language Result Execution time Memory
137767 2019-07-28T09:30:39 Z 윤교준(#3280) RLE (BOI06_rle) C++14
90 / 100
 2500 ms 131336 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

const int MAXN = 100055;
const int MAXK = 2000055;

struct SOL {
	SOL() : V(), n(0) {}
	vector<int> V;
	int n;

	void push(int x) { V.eb(x); n++; }
	void prt() const {
		cout << n << '\n';
		for(int v : V) cout << v << ' ';
		cout << '\n';
	}
	bool operator < (const SOL &t) const {
		return n < t.n;
	}
} Ans;

struct SEG {
	ll dp[MAXN*3], dmn[MAXN*3];
	pii di[MAXN*3];
	int dmni[MAXN*3];

	void init(int i, int s, int e) {
		dp[i] = dmn[i] = INFLL;
		di[i] = {s, -1};
		dmni[i] = -1;
		if(s == e) return;
		int m = (s+e) >> 1;
		init(i<<1, s, m);
		init(i<<1|1, m+1, e);
	}

	void prop(int i, int s, int e) {
		if(INFLL <= dmn[i]) return;
		if(dmn[i] < dp[i]) {
			dp[i] = dmn[i];
			di[i] = {s, dmni[i]};
		}
		if(s != e) {
			if(dmn[i] < dmn[i<<1]) {
				dmn[i<<1] = dmn[i];
				dmni[i<<1] = dmni[i];
			}
			if(dmn[i] < dmn[i<<1|1]) {
				dmn[i<<1|1] = dmn[i];
				dmni[i<<1|1] = dmni[i];
			}
		}
		dmn[i] = INFLL;
	}
	void cal(int i) {
		int j = dp[i<<1] < dp[i<<1|1] ? (i<<1) : (i<<1|1);
		dp[i] = dp[j];
		di[i] = di[j];
	}

	void upd(int i, int s, int e, int p, int q, int x, ll r) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dmn[i] = r;
			dmni[i] = x;
			prop(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|1, m+1, e, p, q, r);
		cal(i);
	}
	void upd(int i, int s, int e, int x, int y, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			dp[i] = r;
			di[i] = {x, y};
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, x, y, r);
		upd(i<<1|1, m+1, e, x, y, r);
		cal(i);
	}
	pair<ll, pii> get(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return {INFLL, {-1, -1}};
		if(p <= s && e <= q) return {dp[i], di[i]};
		int m = (s+e) >> 1;
		auto ret = min(get(i<<1, s, m, p, q), get(i<<1|1, m+1, e, p, q));
		cal(i);
		return ret;
	}
} seg;

vector<pii> SDel[MAXN];
vector<int> AI[MAXN];
int dp[MAXK], bfi[MAXK], bfc[MAXK];

int A[MAXK]; ll B[MAXK];
int C[MAXK], D[MAXK], Del[MAXK];

int N, K;

void makeSeq(const vector<int>&);
int sigDel(int c, int x) { return prev(lower_bound(allv(SDel[c]), pii(x, -INF))) -> second; }

void process() {
	seg.init(1, 0, N-1);
	for(int i = 0;; i++) {
		vector<int> AV;
		if(i < K) {
			AV.eb(0);
			if(A[i]) AV.eb(A[i]);
		}
		else for(int j = 0; j < N; j++) AV.eb(j);
		dp[i] = INF;
		auto upd = [&](int c, int j, int t) {
			if(dp[i] <= t) return;
			//printf("UPD i=%d, c=%d, j=%d, t=%d\n", i, c, j, t);
			dp[i] = t;
			bfi[i] = j;
			bfc[i] = c;
		};
		for(int a : AV) upd(a, 0, sigDel(a, i) - 3*(a ? (i-1) : i));
		pair<ll, pii> ret = seg.get(1, 0, N-1, 0, N-1);
		if(ret.first < INF) {
			ret.first -= 3*i;
			//printf("SEX i=%d, %d %d | %lld\n", i, ret.second.second, ret.second.first, ret.first);
			upd(ret.second.first, ret.second.second, ret.first);
		}

		if(i == K) break;
		seg.upd(1, 0, N-1, 0, N-1, i, dp[i] + 3*i + 3);
		ret = seg.get(1, 0, N-1, A[i], A[i]);
		ret.first += Del[i];
		seg.upd(1, 0, N-1, A[i], ret.second.second, ret.first);
	}

	/*
	for(int i = 0; i <= K; i++)
		printf("%d ; %d / %d %d\n", i, dp[i], bfc[i], bfi[i]);
	*/

	vector<int> V;
	for(int i = K, ni, nc; i;) {
		ni = bfi[i]; nc = bfc[i];
		for(; ni < i; i--) V.eb(nc);
	}
	revv(V);
	makeSeq(V);
}

void makeSeq(const vector<int> &XV) {
	SOL sol;
	for(int i = 0, x = 0, y; i < K; i++) {
		y = XV[i];
		if(x != y) {
			sol.push(x);
			sol.push(y);
			sol.push(0);
			x = y;
		}
		if(x == A[i]) {
			ll k = B[i];
			for(ll t; k;) {
				t = min(ll(N), k);
				sol.push(x);
				sol.push(x);
				sol.push(t-1);
				k -= t;
			}
		} else {
			int c = A[i]; ll k = B[i];
			for(ll t; k;) {
				if(k < 4) {
					sol.push(c);
					k--;
					continue;
				}
				t = min(ll(N+2), k);
				sol.push(x);
				sol.push(c);
				sol.push(t-3);
				k -= t;
			}
		}
	}
	if(sol < Ans) swap(Ans, sol);
}

void precal() {
	for(int i = 0; i < N; i++) SDel[i].eb(-1, 0);
	for(int i = 0; i < K; i++) {
		ll k = B[i], ret = 0;
		for(ll t; k;) {
			if(k < 4) {
				ret += k;
				break;
			}
			t = min(ll(N+2), k);
			ret += 3;
			k -= t;
		}
		C[i] = ret;
		k = B[i]; ret = 0;
		for(ll t; k;) {
			t = min(ll(N), k);
			ret += 3;
			k -= t;
		}
		D[i] = ret;
		Del[i] = D[i] - C[i];

		AI[A[i]].eb(i);
		SDel[A[i]].eb(i, SDel[A[i]].back().second + Del[i]);
	}
}

void runNoChange() {
	SOL sol;
	for(int i = 0; i < K; i++) {
		if(!A[i]) {
			ll k = B[i];
			for(ll t; k;) {
				t = min(ll(N), k);
				sol.push(0);
				sol.push(0);
				sol.push(t-1);
				k -= t;
			}
		} else {
			int c = A[i]; ll k = B[i];
			for(ll t; k;) {
				if(k < 4) {
					sol.push(c);
					k--;
					continue;
				}
				t = min(ll(N+2), k);
				sol.push(0);
				sol.push(c);
				sol.push(t-3);
				k -= t;
			}
		}
	}
	if(sol < Ans) swap(Ans, sol);
}

void runNoAlphabet() {
	bitset<MAXN> chk;
	for(int i = 0; i < K; i++) chk[A[i]] = true;
	int x = 1; for(; x < N && chk[x]; x++);
	if(x == N) return;

	SOL sol;
	sol.push(0); sol.push(x); sol.push(0);
	for(int i = 0; i < K; i++) {
		int c = A[i]; ll k = B[i];
		for(int t; k;) {
			if(k < 4) {
				sol.push(c);
				k--;
				continue;
			}
			t = min(ll(N+2), k);
			sol.push(x);
			sol.push(c);
			sol.push(t-3);
			k -= t;
		}
	}
	if(sol < Ans) swap(Ans, sol);
}

void input() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int L; cin >> N >> L;
	vector<pii> T;
	vector<int> V(L);
	for(int i = 0; i < L; i++) cin >> V[i];
	for(int i = 0, x = 0; i < L;) {
		if(V[i] != x) {
			T.eb(V[i], 1);
			i++;
		} else if(x == V[i+1]) {
			T.eb(x, V[i+2]+1);
			i += 3;
		} else if(!V[i+2]) {
			x = V[i+1];
			i += 3;
		} else {
			T.eb(V[i+1], V[i+2]+3);
			i += 3;
		}
	}
	for(auto &v : T) {
		int a, b; tie(a, b) = v;
		if(K && A[K-1] == a) B[K-1] += b;
		else {
			A[K] = a; B[K] = b;
			K++;
		}
	}
}

int main() {
	input();
	precal();
	Ans.n = INF;

	runNoChange();
	runNoAlphabet();

	process();

	Ans.prt();
	return 0;
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 9 ms 7672 KB Output is correct
5 Correct 9 ms 7672 KB Output is correct
6 Correct 34 ms 10136 KB Output is correct
7 Correct 196 ms 25084 KB Output is correct
8 Correct 249 ms 27552 KB Output is correct
9 Correct 562 ms 68108 KB Output is correct
10 Correct 179 ms 24552 KB Output is correct
11 Correct 171 ms 19552 KB Output is correct
12 Correct 514 ms 56108 KB Output is correct
13 Correct 423 ms 45776 KB Output is correct
14 Correct 288 ms 26812 KB Output is correct
15 Correct 169 ms 17936 KB Output is correct
16 Correct 398 ms 49184 KB Output is correct
17 Correct 654 ms 56792 KB Output is correct
18 Correct 900 ms 65732 KB Output is correct
19 Execution timed out 2552 ms 131336 KB Time limit exceeded
20 Execution timed out 2529 ms 127728 KB Time limit exceeded