oj.uz

Submission #137652

# Submission time Handle Problem Language Result Execution time Memory
137652 2019-07-28T08:16:10 Z 윤교준(#3280) RLE (BOI06_rle) C++14
70 / 100
 708 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];
ll SDel[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() {
	for(int i = 0; i < K; i++) SDel[A[i]] += Del[i];
	vector<int> AV;
	for(int i = 0; i < N; i++) AV.eb(i);
	sort(AV.begin()+1, AV.end(), [&](int a, int b) {
		return SDel[a] < SDel[b];
	});
	int L = min(N, 20000000 / N);
	if(L < sz(AV)) AV.resize(L);

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

	vector<int> V;
	int j = int(min_element(dp[K], dp[K]+L) - dp[K]);
	for(int i = K; i--;) {
		V.eb(AV[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 4 ms 1016 KB Output is correct
6 Correct 24 ms 3604 KB Output is correct
7 Correct 178 ms 21396 KB Output is correct
8 Correct 243 ms 31520 KB Output is correct
9 Correct 472 ms 94272 KB Output is correct
10 Correct 167 ms 17772 KB Output is correct
11 Correct 280 ms 91980 KB Output is correct
12 Correct 569 ms 209568 KB Output is correct
13 Correct 504 ms 120292 KB Output is correct
14 Runtime error 494 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 473 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 405 ms 41008 KB Output is correct
17 Runtime error 637 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 638 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 708 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 707 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)