oj.uz

Submission #137639

# Submission time Handle Problem Language Result Execution time Memory
137639 2019-07-28T07:56:43 Z 윤교준(#3280) RLE (BOI06_rle) C++14
70 / 100
 703 ms 524292 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<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;

int **dp, **dpi;

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

int N, K;

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 process() {
	dp = new int*[K+1];
	dpi = new int*[K+1];
	for(int i = 0; i <= K; i++) {
		dp[i] = new int[N];
		fill(dp[i], dp[i]+N, INF);
		dpi[i] = new int[N];
	}
	dp[0][0] = 0;
	for(int i = 0; i < K; i++) {
		int totmni = int(min_element(dp[i], dp[i]+N) - dp[i]);
		int totmn = dp[i][totmni];
		for(int j = 0; j < N; j++) {
			if(totmn < dp[i][j]-3) {
				dp[i+1][j] = totmn;
				dpi[i+1][j] = totmni;
			} else {
				dp[i+1][j] = dp[i][j]-3;
				dpi[i+1][j] = j;
			}
			if(j == A[i]) dp[i+1][j] += Del[i];
		}
	}

	vector<int> V;
	int j = int(min_element(dp[K], dp[K]+N) - dp[K]);
	for(int i = K; i--;) {
		V.eb(j);
		j = dpi[i+1][j];
	}
	revv(V);

	makeSeq(V);
}

void precal() {
	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];
	}
}

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
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 25 ms 3608 KB Output is correct
7 Correct 177 ms 21344 KB Output is correct
8 Correct 250 ms 31520 KB Output is correct
9 Correct 468 ms 94268 KB Output is correct
10 Correct 168 ms 17752 KB Output is correct
11 Correct 270 ms 91596 KB Output is correct
12 Correct 563 ms 209664 KB Output is correct
13 Correct 496 ms 120212 KB Output is correct
14 Runtime error 479 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 465 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 432 ms 53548 KB Output is correct
17 Runtime error 644 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 643 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 703 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 695 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)